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

Cite as @lafont-2026-semantics (helia, typst) · \cite{lafont-2026-semantics} (LaTeX)
BibTeX
bibtex · 9 lines
@article{lafont-2026-semantics,
  author    = {Ambroise Lafont and
               Neel Krishnaswami},
  title     = {Semantics of pattern unification},
  journal   = {J. Funct. Program.},
  volume    = {35},
  year      = {2025},,
  doi       = {10.1017/s0956796825100130},
}
hayagriva YAML (typst)
yaml · 14 lines
lafont-2026-semantics:
  type: article
  title: Semantics of pattern unification
  author:
  - Lafont, Ambroise
  - Krishnaswami, Neelakantan R.
  date: 2025
  serial-number:
    doi: 10.1017/s0956796825100130
  parent:
    type: periodical
    title: J. Funct. Program.
    publisher: Cambridge University Press (CUP)
    volume: 35
Cites 38 works (2 here)
With notes (2)

Two-dimensional monad theory blackwell_kelly_power_1989

Web

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.
DOI
External (36)
lafont-2026-semantics reference entries/refs/lafont-2026-semantics/lafont-2026-semantics.hel