paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The theory of call-by-value solvability

传值调用可解性的理论
ICFP 6(ICFP)2022匹配度 2/10 · 该论文是纯传值调用 λ 演算可解性的形式语义与类型系统研究,虽属程序语言理论,但未涉及 LLM/Agent、静态分析在 ML/Agentic 程序中的应用、浮点程序分析或贝叶斯程序分析,与用户当前核心方向基本无直接交集。引用 12 inbox
Beniamino Accattoli, Giulio Guerrieri
crossref: 2026-09-10

AI 速览

一句话:系统研究传值调用 λ 演算的可解性,给出多重类型刻画并指出其与传名调用的语义差异。

未类型化传名调用 λ 演算的语义以可解项为核心,不可解项可视为无意义项;而传值调用(CbV)的可解性研究仍不成熟。本文重新设计一种精细的 CbV 演算表述,借此恢复传名调用中可解性的许多性质,特别是通过 multi types(多重类型)给出定性与定量刻画。同时,作者强调 CbV 中可解性作用不同:若像传名调用那样把不可解项等同于无意义项,会导出不一致的理论。

问题
在未类型化传值调用 λ 演算中,可解项的概念及其语义地位尚不清晰,需要厘清 CbV 可解性是否以及如何类比传名调用。
方法
通过精心设计的 CbV 演算表述,并使用多重类型(multi types)建立可解性的定性与定量刻画。
评估
理论证明与反例分析;证明 CbV 可恢复传名调用可解性的部分性质,同时表明将不可解项视为无意义会导致不一致。
原文摘要(Abstract)

The semantics of the untyped (call-by-name) lambda-calculus is a well developed field built around the concept of solvable terms, which are elegantly characterized in many different ways. In particular, unsolvable terms provide a consistent notion of meaningless term. The semantics of the untyped call-by-value lambda-calculus (CbV) is instead still in its infancy, because of some inherent difficulties but also because CbV solvable terms are less studied and understood than in call-by-name. On the one hand, we show that a carefully crafted presentation of CbV allows us to recover many of the properties that solvability has in call-by-name, in particular qualitative and quantitative characterizations via multi types. On the other hand, we stress that, in CbV, solvability plays a different role: identifying unsolvable terms as meaningless induces an inconsistent theory.

链接与引用

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

BibTeX
@article{paperbot1501,
  title = {The theory of call-by-value solvability},
  author = {Beniamino Accattoli and Giulio Guerrieri},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {ICFP},
  year = {2022},
  doi = {10.1145/3547652}
}