paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Classical (co)recursion: Mechanics

经典(余)递归:机制
JFP vol.332023匹配度 1/10 · 该论文主题是函数式编程中原始余递归的形式语义、抽象机与求值策略复杂度,属于纯 PL 理论;不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析, therefore 与用户当前研究画像几乎无交集。引用 1 inbox
PAUL DOWNEN, ZENA M. ARIOLA
crossref: 2026-09-10

AI 速览

一句话:为原始余递归建立与递归对等的计算基础,借抽象机与逻辑对偶揭示求值策略对(余)递归组合子复杂度的影响。

论文针对余递归相较递归长期被忽视、缺乏同等计算基础的问题,为原始余递归给出以计算为中心的基础,并构造一个与递归原始计算模型类似的终止演算。作者通过抽象机的实现细节加强递归与余递归的联系,并利用逻辑对偶从递归语法地推导出余递归。文章还考察求值策略对原始(余)递归组合子计算复杂度的影响,指出 call-by-name 更有利于高效递归,而 call-by-value 更有利于高效余递归。

问题
余递归虽与递归对偶,却长期被视为异类,缺少像递归那样成熟的计算基础与理解。
方法
作者基于计算给出原始余递归的终止演算,并借助抽象机与逻辑对偶,从递归语法地推导余递归,同时分析求值策略对复杂度的影响。
评估
以形式化演算与抽象机进行理论推导和复杂度对比,而非实证评估;结论是 call-by-name 下递归更高效,call-by-value 下余递归更高效。
原文摘要(Abstract)

Abstract Recursion is a mature, well-understood topic in the theory and practice of programming. Yet its dual, corecursion is underappreciated and still seen as exotic. We aim to put them both on equal footing by giving a foundation for primitive corecursion based on computation, giving a terminating calculus analogous to the original computational foundation of recursion. We show how the implementation details in an abstract machine strengthens their connection, syntactically deriving corecursion from recursion via logical duality. We also observe the impact of evaluation strategy on the computational complexity of primitive (co)recursive combinators: call-by-name allows for more efficient recursion, but call-by-value allows for more efficient corecursion.

链接与引用

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

BibTeX
@article{paperbot2150,
  title = {Classical (co)recursion: Mechanics},
  author = {PAUL DOWNEN and ZENA M. ARIOLA},
  journal = {Journal of Functional Programming},
  volume = {33},
  year = {2023},
  doi = {10.1017/s0956796822000168}
}