paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An operational interpretation of coinductive types

共归纳类型的操作解释
LMCS vol.Volume 16, Issue 12020匹配度 2/10 · 论文属于纯PL形式语义/类型论,研究共归纳类型的操作语义与类型正确性准则,未涉及LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析。与用户当前关注的PL×AI交叉方向基本无关,仅在广义PL理论上有微弱关联。引用 0 inbox
Łukasz Czajka
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:为严格正嵌套高阶(共)归纳类型提出基于重写的操作语义,用极限刻画无限归约并给出类型正确性准则。

本文研究严格正嵌套高阶(共)归纳类型的操作语义,旨在刻画惰性高阶函数式语言中无限归约序列的“极限”行为。作者提出基于重写的解释:将惰性数据解释为可能无限的完全展开项,从而把项重写中的生产性(productivity)概念推广到含高阶函数与嵌套(共)归纳定义的情形。核心结果是近似定理:若项可归约到共归纳类型解释中无限对象的任意大有限近似,则它在极限意义下归约到该类型解释中的无限对象。论文还引入一个类型系统作为有限项的充分语法正确性准则,并借助近似定理证明每个良类型项在该语义中都有良定义解释。

问题
如何为高阶函数式语言中含嵌套(共)归纳定义的惰性数据结构定义操作语义,并正确处理无限归约序列的极限,是本文要解决的问题。
方法
作者提出基于项重写的操作解释,用可能无限的完全展开项解释惰性数据,并证明近似定理;同时设计带类型标注的类型系统作为充分语法正确性准则。
评估
评估以理论证明为主:证明近似定理,并利用它证明每个良类型项在语义中有良定义解释。
原文摘要(Abstract)

We introduce an operational rewriting-based semantics for strictly positive nested higher-order (co)inductive types. The semantics takes into account the "limits" of infinite reduction sequences. This may be seen as a refinement and generalization of the notion of productivity in term rewriting to a setting with higher-order functions and with data specified by nested higher-order inductive and coinductive definitions. Intuitively, we interpret lazy data structures in a higher-order functional language by potentially infinite terms corresponding to their complete unfoldings. We prove an approximation theorem which essentially states that if a term reduces to an arbitrarily large finite approximation of an infinite object in the interpretation of a coinductive type, then it infinitarily (i.e. in the "limit") reduces to an infinite object in the interpretation of this type. We introduce a sufficient syntactic correctness criterion, in the form of a type system, for finite terms decorated with type information. Using the approximation theorem, we show that each well-typed term has a well-defined interpretation in our semantics.

链接与引用

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

BibTeX
@article{000119,
  title = {An operational interpretation of coinductive types},
  author = {Łukasz Czajka},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 1},
  year = {2020},
  doi = {10.23638/lmcs-16(1:11)2020}
}