Element Model Type Theory
Generalized algebraic theories have long been part of our work at Topos, going back to the very beginnings of Catlab.jl. In this talk, I give a new implementation of generalized algebraic theories in Rust, which takes a different, more type-theoretic approach to generalized algebraic theories. This approach tightly integrates e-graphs into the type-checking process to enable an approximation to extensive equality, and in addition enables greater compositionality of theories, achieving a principled approach to “theory pushout” that has been long-desired. This new implementation is intended as a prototype for type-checking algorithms that will go into CatColab and enable “open notebooks” for compositional modeling, and I give an overview of how I envision that working. In addition to this application in scientific modeling, I believe that lessons from this implementation that I have learned about two-level type theory could be applicable in a wide variety of domains in which abstraction is desired that does not complicate the underlying semantics, such as finite state machines, probabilistic programming, SAT solving, systems programming, constraint programming, databases, and serialization formats.