paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An interpretation of system F through bar recursion

通过 bar recursion 解释 System F
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 该论文属于纯类型论与形式语义,研究System F到带bar recursion语言的翻译与归一化解释,未涉及LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户研究画像无直接关联。引用 5 inbox
Valentin Blot
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:首次将 System F 翻译到带 bar recursion 的简单类型全语言,并基于可实现性给出归一化解释。

System F 与 Spector 的 bar recursion 可分别计算解释二阶算术,但所得程序的计算行为迥异,二者关系尚不清楚。本文定义首个从 System F 到带 bar recursion 变体的简单类型全语言的翻译。翻译依赖二阶算术的可实现性解释:虽然由 Gödel 不完备定理无法在二阶算术内证明 System F 整体终止,但对每个 System F 项,二阶算术可证明其终止,且可实现性解释给出到达范式所需归约步数的界。作者利用该界通过原始递归计算范式;由于 System F 的归一化证明按类型推导归纳进行,翻译是组合式的。该工作为通过 bar recursion 研究多态性提供了新途径。

问题
如何比较 System F 与 Spector bar recursion 这两种二阶算术的计算解释,并建立从 System F 到 bar recursion 语言的翻译?
方法
利用二阶算术的可实现性解释,为每个 System F 项导出其归一化步数的界,并用原始递归在该界内计算范式,从而给出组合式翻译。
评估
通过翻译定义与归一化证明说明正确性:每个项在二阶算术中可证终止,可实现性给出归约步数界,且翻译因按类型推导归纳而是组合式的;摘要未报告实现或实验。
原文摘要(Abstract)

There are two possible computational interpretations of second-order arithmetic: Girard's system F or Spector's bar recursion and its variants. While the logic is the same, the programs obtained from these two interpretations have a fundamentally different computational behavior and their relationship is not well understood. We make a step towards a comparison by defining the first translation of system F into a simply-typed total language with a variant of bar recursion. This translation relies on a realizability interpretation of second-order arithmetic. Due to Gödel's incompleteness theorem there is no proof of termination of system F within second-order arithmetic. However, for each individual term of system F there is a proof in second-order arithmetic that it terminates, with its realizability interpretation providing a bound on the number of reduction steps to reach a normal form. Using this bound, we compute the normal form through primitive recursion. Moreover, since the normalization proof of system F proceeds by induction on typing derivations, the translation is compositional. The flexibility of our method opens the possibility of getting a more direct translation that will provide an alternative approach to the study of polymorphism, namely through bar recursion.

链接与引用

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

BibTeX
@inproceedings{Blot17,
  title = {An interpretation of system F through bar recursion},
  author = {Valentin Blot},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005066}
}