paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The calculus of dependent lambda eliminations

依赖 lambda 消去演算
JFP vol.272017匹配度 2/10 · 该论文属于依赖类型论与形式语义的基础研究,提出 CDLE 并证明一致性,与用户核心关注的 LLM/静态分析、Agentic 程序分析、浮点程序分析或贝叶斯程序分析均无直接交集。虽然涉及形式化验证基础,但未使用 LLM/Agent,也不属于问题驱动的工具落地研究。引用 24 inbox
AARON STUMP
crossref: 2026-09-10

AI 速览

一句话:提出 CDLE:仅用纯 lambda 编码、无需辅助数据类型系统的依赖类型演算,并证明其逻辑一致性。

现代构造类型论通常基于纯依赖类型 lambda 演算,并附加用户定义数据类型。本文提出依赖 lambda 消去演算(CDLE),其核心是纯 lambda 编码,不引入辅助数据类型系统。为在 lambda 编码上支持归纳与大消去,作者定义了构造子约束递归类型,以及将简单类型项提升到类型层的 lifting 操作。文章使用格论指称语义为类型建立模型,并据此证明该语言逻辑一致。最后通过若干实例展示 CDLE 的表达能力,并在原型实现 Cedille 中检查这些例子。

问题
如何在仅使用纯 lambda 编码、没有辅助数据类型系统的依赖类型演算中支持归纳与大消去,并保证逻辑一致性。
方法
定义 CDLE,引入构造子约束递归类型与 lifting 操作,并以格论指称语义证明一致性。
评估
通过多个示例展示 CDLE 的表达能力,并在原型实现 Cedille 中检查这些例子。
原文摘要(Abstract)

Abstract Modern constructive type theory is based on pure dependently typed lambda calculus, augmented with user-defined datatypes. This paper presents an alternative called the Calculus of Dependent Lambda Eliminations, based on pure lambda encodings with no auxiliary datatype system. New typing constructs are defined that enable induction, as well as large eliminations with lambda encodings. These constructs are constructor-constrained recursive types, and a lifting operation to lift simply typed terms to the type level. Using a lattice-theoretic denotational semantics for types, the language is proved logically consistent. The power of CDLE is demonstrated through several examples, which have been checked with a prototype implementation called Cedille.

链接与引用

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

BibTeX
@article{paperbot72,
  title = {The calculus of dependent lambda eliminations},
  author = {AARON STUMP},
  journal = {Journal of Functional Programming},
  volume = {27},
  year = {2017},
  doi = {10.1017/s0956796817000053}
}