paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Semantics of pattern unification

模式合一的语义
JFP vol.352026匹配度 2/10 · 该论文属于纯 PL 理论:研究模式合一(pattern unification)的范畴语义与 Agda 实现,不涉及 LLM/Agent、静态分析在 ML/Agentic 程序中的应用、浮点程序分析或贝叶斯程序分析。虽然形式化验证与类型系统背景可能间接相关,但与该研究画像的核心交叉方向距离较远。引用 0 inbox
AMBROISE LAFONT, NEEL KRISHNASWAMI
crossref: 2026-09-10

AI 速览

一句话:提出广义元变量语法与范畴语义,证明特定条件下 Miller 模式合一算法可推广,并用 Agda 实现。

本文研究二阶合一的判定片段——Miller 的模式合一,并为其提出一种带元变量语法的推广。作者用范畴语义刻画这种语法,给出使 Miller 合一算法仍可适用的条件,从而把可判定性从简单类型 λ 演算扩展到更一般的签名结构,包括有序 λ 演算和 System F 等内蕴多态语法。虽然不显式处理方程,但通过在正规形式上工作,仍覆盖简单类型 λ 演算模 βη 等式这一原始设定。作者还在 Agda 中实现了通用合一算法,以说明该语义分析的有效性。

问题
如何在比简单类型 λ 演算更一般的带元变量语法上推广 Miller 模式合一,并刻画算法适用的语义条件。
方法
采用范畴语义分析带元变量语法,以推广绑定签名的签名结构描述语法,并在 Agda 中实现通用合一算法。
评估
通过范畴语义证明在给定条件下 Miller 算法可推广,并以 Agda 实现覆盖有序 λ 演算、System F 及模 βη 的正规形式等实例。
原文摘要(Abstract)

Abstract 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.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

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