Reference. Formal metatheory of second-order abstract syntax
Despite extensive research both on the theoretical and practical fronts, formalising, reasoning about, and implementing languages with variable binding is still a daunting endeavour – repetitive boilerplate and the overly complicated metatheory of capture-avoiding substitution often get in the way of progressing on to the actually interesting properties of a language. Existing developments offer some relief, however at the expense of inconvenient and error-prone term encodings and lack of formal foundations. We present a mathematically-inspired language-formalisation framework implemented in Agda. The system translates the description of a syntax signature with variable-binding operators into an intrinsically-encoded, inductive data type equipped with syntactic operations such as weakening and substitution, along with their correctness properties. The generated metatheory further incorporates metavariables and their associated operation of metasubstitution, which enables second-order equational/rewriting reasoning. The underlying mathematical foundation of the framework – initial algebra semantics – derives compositional interpretations of languages into their models satisfying the semantic substitution lemma by construction.
Cite
Cited by (7)
Modular models of monoids with operations by lifting functors along fibrations yang-2026-modular
Inspired by Plotkin and Power’s algebraic treatment of computational effects and the principle of notions of computations as monoids, we propose a categorical framework for equational theories and models of monoids equipped with operations. This framework generalises Plotkin and Power’s algebraic treatment of effectful operations taking or returning values as input or output to operations that may take or return computations as input or output. Additionally, to give semantic models of computational effects in a modular way, we introduce a formal theory of modular constructions of algebraic structures based on the framework of lifting functors along fibrations.
Modular abstract syntax trees (MAST): substitution tensors with second-class sorts fiore-2025-modular
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 lambda-calculus (CBV) and Levy’s Call-by-Push-Value (CBPV). Prohibiting second-class sorts from appearing in variable contexts changes the characterisation of the abstract syntax from monoids in monoidal categories to actions in actegories. We reproduce much of the development through bicategorical arguments. We apply the resulting theory by proving substitution lemmata for varieties of CBV.
Frex: Dependently Typed Algebraic Simplification allais-2025-frex
We present a new design for an algebraic simplification library structured around concepts from universal algebra: theories, models, homomorphisms, and universal properties of free algebras and free extensions of algebras. The library’s dependently typed interface guarantees that both built-in and user-defined simplification modules are terminating, sound, and complete with respect to a well-specified class of equations. We have implemented the design in the Idris 2 and Agda dependently typed programming languages and shown that it supports modular extension to new theories, proof extraction and certification, goal extraction via reflection, and interactive development.
Scoped Effects, Scoped Operations, and Parameterized Algebraic Theories matache-2025-scoped
Notions of computation can be modeled by monads. Algebraic effects offer a characterization of monads in terms of algebraic operations and equational axioms, where operations are basic programming features, such as reading or updating the state, and axioms specify observably equivalent expressions. However, many useful programming features depend on additional mechanisms such as delimited scopes or dynamically allocated resources. Such mechanisms can be supported via extensions to algebraic effects including scoped effects and parameterized algebraic theories . We present a fresh perspective on scoped effects by translation into a variation of parameterized algebraic theories. The translation enables a new approach to equational reasoning for scoped effects and gives rise to an alternative characterization of monads in terms of generators and equations involving both scoped and algebraic operations. We demonstrate the power of our approach by way of equational characterizations of several known models of scoped effects.
Scoped Effects as Parameterized Algebraic Theories lindley-2024-scoped
Notions of computation can be modelled by monads. Algebraic effects offer a characterization of monads in terms of algebraic operations and equational axioms, where operations are basic programming features, such as reading or updating the state, and axioms specify observably equivalent expressions. However, many useful programming features depend on additional mechanisms such as delimited scopes or dynamically allocated resources. Such mechanisms can be supported via extensions to algebraic effects including scoped effects and parameterized algebraic theories . We present a fresh perspective on scoped effects by translation into a variation of parameterized algebraic theories. The translation enables a new approach to equational reasoning for scoped effects and gives rise to an alternative characterization of monads in terms of generators and equations involving both scoped and algebraic operations. We demonstrate the power of our fresh perspective by way of equational characterizations of several known models of scoped effects.
Modular Models of Monoids with Operations yang-2023-modular
Inspired by algebraic effects and the principle of notions of computations as monoids, we study a categorical framework for equational theories and models of monoids equipped with operations. The framework covers not only algebraic operations but also scoped and variable-binding operations. Appealingly, in this framework both theories and models can be modularly composed. Technically, a general monoid-theory correspondence is shown, saying that the category of theories of algebraic operations is equivalent to the category of monoids. Moreover, more complex forms of operations can be coreflected into algebraic operations, in a way that preserves initial algebras. On models, we introduce modular models of a theory, which can interpret abstract syntax in the presence of other operations. We show constructions of modular models (i) from monoid transformers, (ii) from free algebras, (iii) by composition, and (iv) in symmetric monoidal categories.
Semantic analysis of normalisation by evaluation for typed lambda calculus fiore-2022-semantic
This paper studies normalisation by evaluation for typed lambda calculus from a categorical and algebraic viewpoint. The first part of the paper analyses the lambda definability result of Jung and Tiuryn via Kripke logical relations and shows how it can be adapted to unify definability and normalisation, yielding an extensional normalisation result. In the second part of the paper, the analysis is refined further by considering intensional Kripke relations (in the form of Artin–Wraith glueing) and shown to provide a function for normalising terms, casting normalisation by evaluation in the context of categorical glueing. The technical development includes an algebraic treatment of the syntax and semantics of the typed lambda calculus that allows the definition of the normalisation function to be given within a simply typed metatheory. A normalisation-by-evaluation program in a dependently typed functional programming language is synthesised.
Cites 63 works (7 here)
With notes (7)
Formalizing category theory in Agda hu-2021-formalizing
A type- and scope-safe universe of syntaxes with binding: their semantics and proofs allais-2021-a
The syntax of almost every programming language includes a notion of binder and corresponding bound occurrences, along with the accompanying notions of α-equivalence, capture-avoiding substitution, typing contexts, runtime environments, and so on. In the past, implementing and reasoning about programming languages required careful handling to maintain the correct behaviour of bound variables. Modern programming languages include features that enable constraints like scope safety to be expressed in types. Nevertheless, the programmer is still forced to write the same boilerplate over again for each new implementation of a scope-safe operation (e.g., renaming, substitution, desugaring, printing), and then again for correctness proofs. We present an expressive universe of syntaxes with binding and demonstrate how to (1) implement scope-safe traversals once and for all by generic programming; and (2) how to derive properties of these traversals by generic proving. Our universe description, generic traversals and proofs, and our examples have all been formalised in Agda and are available in the accompanying material available online at https://github.com/gallais/generic-syntax .
Type-and-scope safe programs and their proofs allais-2017-type
Indexed containers altenkirch_indexed_2015
We show that the syntactically rich notion of strictly positive families can be reduced to a core type theory with a fixed number of type constructors exploiting the novel notion of indexed containers. As a result, we show indexed containers provide normal forms for strictly positive families in much the same way that containers provide normal forms for strictly positive types. Interestingly, this step from containers to indexed containers is achieved without having to extend the core type theory. Most of the construction presented here has been formalized using the Agda system.
Second-Order and Dependently-Sorted Abstract Syntax fiore-2008-second
Higher-order abstract syntax pfenning-1988-higher
Abstract syntax and variable binding fiore_etal_nd
We develop a theory of abstract syntax with variable binding. To every binding signature we associate a category of models consisting of variable sets endowed with compatible algebra and substitution structures. The syntax generated by the signature is the initial model. This gives a notion of initial algebra semantics encompassing the traditional one; besides compositionality, it automatically verifies the semantic substitution lemma.
External (56)
- Algebraic models of simple type theories (2020)
- A Cellular Howe Theorem (2020)
- A general approach to define binders using matching logic (2020)
- Programming language foundations in Agda (2020)
- A Complete Equational Axiomatisation of Partial Differentiation (2020)
- The linear-non-linear substitution 2-monad (2020)
- POPLMark reloaded: Mechanizing proofs by logical relations (2019)
- Bindings as bounded natural functors (2019)
- Autosubst 2: reasoning with multi-sorted de Bruijn terms and vector substitutions (2019)
- Initial algebra for a strictly positive endofunctor constructed using sized types and quotient types (Agda development) (2019)
- Binder aware recursion over well-scoped de Bruijn syntax (2018)
- Generic description of well-scoped, well-typed syntaxes (2018)
- List Objects with Algebraic Structure (2017)
- Formal metatheory of the Lambda calculus using Stoughton's substitution (2016)
- Needle & Knot: Binder Boilerplate Tied Up (2016)
- Pattern synonyms (2016)
- UniMath: a computer-checked library of univalent mathematics (2014)
- Multiversal Polymorphic Algebraic Theories: Syntax, Semantics, Translations, and Equational Logic (2013)
- Automatically Generated Infrastructure for De Bruijn Syntaxes (2013)
- Discrete Generalised Polynomial Functors (2012)
- GMeta: A Generic Formal Metatheory Framework for First-Order Representations (2012)
- Skew-closed categories (2012)
- Skew-monoidal categories and bialgebroids (2012)
- Strongly Typed Term Representations in Coq (2011)
- The Locally Nameless Representation (2011)
- General Bindings and Alpha-Equivalence in Nominal Isabelle (2011)
- A Solution to the PoplMark Challenge Based on de Bruijn Indices (2011)
- Binders unbound (2011)
- Second-Order Equational Logic (Extended Abstract) (2010)
- Second-Order Algebraic Theories (2010)
- MiniAgda: Integrating Sized and Dependent Types (2010)
- Dependently typed programming in Agda (2009)
- Engineering formal metatheory (2008)
- Parametric higher-order abstract syntax for mechanized semantics (2008)
- On the structure of substitution (2006)
- Mechanized Metatheory for the Masses: The PoplMark Challenge (2005)
- Type-preserving renaming and substitution (unpublished note) (2005)
- Free Σ-Monoids: A Higher-Order Syntax with Metavariables (2004)
- Functional pearl: I am not a number – I am a free variable (2004)
- The Coq proof assistant reference manual (2004)
- FreshML (2003)
- Abstract Syntax and Variable Binding for Linear Binders (2000)
- Monadic Presentations of Lambda Terms Using Generalized Inductive Types (1999)
- de Bruijn notation as a nested datatype (1999)
- A new approach to abstract syntax involving binders (1999)
- Semantical analysis of higher-order abstract syntax (1999)
- An algebraic generalization of Frege structures — binding algebras (1999)
- The abstract variable-binding calculus (1995)
- Substitution: A formal methods case study using monads and transformations (1994)
- Explicit substitutions (1990)
- The Lambda Calculus - Its Syntax and Semantics (1984)
- From lambda-calculus to cartesian closed categories (1980)
- A General Church-Rosser Theorem (unpublished note) (1978)
- An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types (IBM Research Report 6487) (1976)
- Closed categories generated by commutative monads (1971)
- On closed categories of functors (1970)