.png){kind=icon}
.png){kind=icon}
Return
Semantics of pattern unification
.png){kind=icon}
PRE
AI
DOI：10.1017/S0956796825100130.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Journal
J
IF:
0.6
Papers:
8
Citations:
0