EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-SA 4.0

Semantics of pattern unification

AMBROISE LAFONT, NEEL KRISHNASWAMI

Journal of Functional Programming · 2026 · 35

DOI: 10.1017/s0956796825100130 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Functional Programming, online erschienen am 24.03.2026. Verfasst von AMBROISE LAFONT und 1 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose a notion of syntax with metavariables that generalises Miller’s decidable pattern fragment of second-order unification for simply typed $\lambda$ -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 $\lambda$ -calculus and (intrinsic) polymorphic syntax such as System F. Although we do not explicitly handle equations, we also tackle simply typed $\lambda$ -calculus modulo $\beta$ - and $\eta$ -equations (Miller’s original setting) by working on the syntax of normal forms.

Zitieren

APA

LAFONT, A., & KRISHNASWAMI, N. (2026). Semantics of pattern unification. Journal of Functional Programming, 35. https://doi.org/10.1017/s0956796825100130

Vancouver

LAFONT A, KRISHNASWAMI N. Semantics of pattern unification. Journal of Functional Programming. 2026;35. doi:10.1017/s0956796825100130

BibTeX
@article{LAFONT2026,
  author = {LAFONT, AMBROISE and KRISHNASWAMI, NEEL},
  title = {Semantics of pattern unification},
  journal = {Journal of Functional Programming},
  year = {2026},
  volume = {35},
  doi = {10.1017/s0956796825100130}
}
Kostenlos starten →