Mathematically Structured Programming Group
Next MSP101 seminar
Modular abstract syntax trees (MAST) – substitution tensors with second-class sorts
Ohad Kammar (University of Glasgow)
Monday 10 November 2025, 13:00, LT1414a and Online
Abstract
We adapt Fiore, Plotkin, and Turi's treatment of abstract syntax with binding, substitution, and holes to account for languages with second-class sorts. These situations include programming calculi such as the Call-by-Value λ-calculus (CBV) and Levy's Call-by-Push-Value (CBPV). Prohibiting second-class sorts from appearing in variable contexts means the presheaf of variables is no longer a left-unit for Fiore et al's substitution tensor product. We generalised their development to associative and right-unital skew monoidal categories. We reuse much of the development through skew bicategorical arguments. In ongoing work, we replace the skew monoidal structure with ordinary monoidal structure by recourse to substitution modules instead of substitution monoids.We apply the resulting theory in two scenarios. We employ the mathematical theory to circumvent the expression problem when proving substitution lemmata for varieties of CBV denotational semantics modularly. We employ a computational implementation of the theory to circumvent the expression problem when implementing intrinsically-typed foreign-function interfaces for the 29 theories of SMTLIB.
Joint work with Marcelo Fiore, Kajetan Granops, Mihail-Codrin Iftode, Georg Moser, and Sam Staton.
See the MSP101 seminar page for a full list of future and past talks.
Research Themes
Our vision is to use mathematics to understand the nature of computation, and to turn that understanding into the next generation of programming languages.
We see the mathematical foundations of computation and programming as inextricably linked. We study one so as to develop the other. This reflects the symbiotic relationship between mathematics, programming, and the design of programming languages — any attempt to sever this connection will diminish each component.
To achieve these research goals we use ideas from the following disciplines:
- Functional Programming and Type Theory
- What does the future of programming languages look like? How does one take the logical structure of computation and turn it into a programming abstraction? Type theory allows us to do this by providing a language at an intermediate level of abstraction between a programming language and its logical foundations. Indeed, type theory could be said to be the ideas factory for programming languages.
- Logic
- Different logics are suitable for expressing and verifying different properties of programming languages or systems. We make use of a range of methods such as proof theory and coalgebra to understand the computational nature of proofs and systems intended to run without interruption. Those methods are driven by emerging problems in areas such as AI and security. We have particular strengths in modal logic, quantitative properties of systems, and logics for reasoning about concurrency.
- Category Theory
- How does one understand structure abstractly? How can one build theories that systematically build complex systems by composing descriptions of simpler ones? One uses category theory — that's how! Ideas such as monads and initial algebra semantics attest to the deep contribution that category theory has made to computation.