Reference. Semantics of pattern unification
We propose a notion of syntax with metavariables that generalises Miller’s decidable pattern fragment of second-order unification for simply typed -calculus. Using categorical semantics, we show that, under some conditions, a generalisation of Miller’s unification algorithm applies. To illustrate our semantic analysis, we implemented our generic unification algorithm in Agda. The syntax with metavariables given as input of the algorithm is specified by a notion of signature generalising binding signatures, covering a wide range of examples, including ordered -calculus and (intrinsic) polymorphic syntax such as System F. Although we do not explicitly handle equations, we also tackle simply typed -calculus modulo - and -equations (Miller’s original setting) by working on the syntax of normal forms.
Cite
Cites 38 works (2 here)
With notes (2)
Two-dimensional monad theory blackwell_kelly_power_1989
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 (36)
- A Category Theoretic View of Contextual Types: From Simple Types to Dependent Types (2022)
- Abstract and Concrete Type Theories (PhD thesis) (2021)
- Sound and complete bidirectional typechecking for higher-rank polymorphism with existentials and indexed types (2016)
- A categorical perspective on pattern unification (2014)
- Type Inference, Haskell and Dependent Types (PhD thesis) (2013)
- Polymorphic Abstract Syntax via Grothendieck Construction (2011)
- Higher-Order Dynamic Pattern Unification for Dependent Types and Records (2011)
- Pattern Unification for the Lambda Calculus with Linear and Affine Types (2010)
- Second-order equational logic (2010)
- Higher-order constraint simplification in dependent type theory (2009)
- Indexed Containers (2009)
- Nominal Unification from a Higher-Order Perspective (2008)
- Contextual modal type theory (2008)
- Relating nominal and higher-order pattern unification (2005)
- Free Σ-Monoids: A Higher-Order Syntax with Metavariables (2004)
- A modal foundation for meta-variables (2003)
- Tabled Higher-Order Logic Programming (2003)
- A concurrent logical framework I: Judgments and properties (2003)
- Nominal Unification (2003)
- A classification of accessible categories (2002)
- Properties of terms in continuation-passing style in an ordered logical framework (2000)
- Studies in Logic and the Foundations of Mathematics (1999)
- A new approach to abstract syntax involving binders (1999)
- Categories for the Working Mathematician, 2nd ed (1998)
- Internal Type Theory (1995)
- Locally Presentable and Accessible Categories (1994)
- Pullbacks equivalent to pseudopullbacks (1993)
- A Logic Programming Language with Lambda-Abstraction, Function Variables, and Simple Unification (1991)
- Unification and anti-unification in the calculus of constructions (1991)
- Category Theory for Computing Science (1990)
- What Is Unification?: A Categorical View of Substitution, Equation and Solution (1989)
- Computational Category Theory (1988)
- A left adjoint construction related to free triples (1977)
- Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem (1972)
- A note on inductive generalization (1970)
- Fibred and Cofibred Categories (1966)