Uploaded April 2026 | Updated September 2026, 2 weeks ago

---

Title: Abstract interpretation for semi-dependent type theories
Abstract: ML-style module systems have a long and rich history which ultimately stems back to Lawvere’s seminal work on algebraic theories. While ML-style module systems have typically been confined to ML-descendants, analogous PL constructs that may be more familiar include Java-style interfaces or Haskell-style type classes. In my research for SGAI, I have adopted the perspective that module signatures are the appropriate programming language analogue for theories in a variety of doctrines of categorical algebra. Classical module signatures as found in ML can be are syntactic presentations of “theories for the doctrine of cartesian closed categories”; it is productive to vary “cartesian closed category” to “cartesian category”, “finite limit category”, “regular hyperdoctrine” (the categorical version of a restricted form of first-order logic), “symmetric monoidal categories”, etc. Then the module language for a doctrine extends the well-known internal language for the doctrine by adding “genericism”. For instance, it is well-known that the internal language of a symmetric monoidal category is given by a “linear do notation” where each variable may only be consumed once. However, typically an implementation of this internal language would fix a specific symmetric monoidal category. The module language allows varying the symmetric monoidal category, and potentially migrating expressions between various symmetric monoidal categories. This is of interest to SGAI because presentations of symmetric monoidal categories (e.g., module signatures for the symmetric monoidal doctrine) are Petri nets, and morphisms between them (e.g., module functors for the symmetric monoidal doctrine) are “hierarchical Petri nets”, where each transition in the codomain Petri net is associated with a process in the domain Petri net. Other applications to the SGAI program include the observation, going back to early work in ACT by Spivak, that databases schemas are productively thought of as theories in certain doctrines, with the choice of doctrine depending on the feature-set of the database engine.
Date: 2025-12-09