Productive coprogramming with guarded recursion
Productive coprogramming with guarded recursion
复制标题
具有保护递归的高效协同编程
DOI：
10.1145/2544174.2500597
复制
发表时间：
2013
影响因子：
--
通讯作者：
Atkey R
中科院分区：
文献类型：
--
作者：
Atkey R
全函数式编程提供了一个令人迷惑的愿景，即只要编译器接受一个程序，我们就可以保证它总是会终止。在不打算终止的程序的情况下，例如，服务器，我们保证程序总是高效的。生产力意味着，即使一个程序生成了无限数量的数据，每一个片段也将在有限的时间内生成。最终余代数的范畴论概念为具有无限输出的生产规划提供了理论基础。因此，我们把非良基数据的协同编程（coprogramming with non-well-foundedcodata）称为良基数据（well-foundeddata）的对偶（dual），比如有限列表（finite lists）和树（trees）。语法保护性检查器确保所有自递归调用都通过使用构造函数来保护。这样的检查确保了生产力。不幸的是，这些语法检查不是组合的，并且严重复杂化了共同编程。最初由中野提出的保护递归作为灵活的基于组合类型的共同编程方法的基础是诱人的。然而，正如我们所展示的那样，保护递归本身并不适合共同编程，因为没有办法对无限数据进行有限的观察。本文引入了时钟变量的概念，用来表示中野的保护递归.时钟变量允许我们“关闭”无限数据的生成，并进行有限的观察，这是单靠保护递归是不可能的。
Total functional programming offers the beguiling vision that, just by virtue of the compiler accepting a program, we are guaranteed that it will always terminate. In the case of programs that are not intended to terminate, e.g., servers, we are guaranteed that programs will always beproductive. Productivity means that, even if a program generates an infinite amount of data, each piece will be generated in finite time. The theoretical underpinning for productive programming with infinite output is provided by the category theoretic notion of final coalgebras. Hence, we speak ofcoprogramming with non-well-foundedcodata, as a dual to programming with well-founded data like finite lists and trees.Systems that offer facilities for productive coprogramming, such as the proof assistants Coq and Agda, currently do so through syntactic guardedness checkers. Syntactic guardedness checkers ensure that all self-recursive calls are guarded by a use of a constructor. Such a check ensures productivity. Unfortunately, these syntactic checks are not compositional, and severely complicate coprogramming.Guarded recursion, originally due to Nakano, is tantalising as a basis for a flexible and compositional type-based approach to coprogramming. However, as we show, by itself, guarded recursion is not suitable for coprogramming due to the fact that there is no way to make finite observations on pieces of infinite data. In this paper, we introduce the concept ofclock variablesthat index Nakano's guarded recursion. Clock variables allow us to "close over" the generation of infinite data, and to make finite observations, something that is not possible with guarded recursion alone.
登录
查看更多内容
通过“混合”归纳定义的计算充分性
DOI：
--
发表时间：
1993
期刊：
Mathematical Foundations of Programming Semantics
影响因子：
--
作者：
A. Pitts
通讯作者：
A. Pitts
影响因子：
0.6
作者：
Ghani N
通讯作者：
Ghani N
影响因子：
0.6
作者：
Capretta, Venanzio
通讯作者：
Capretta, Venanzio
归纳类型的方程理论
影响因子：
0.8
作者：
R. Loader
通讯作者：
R. Loader
混合感应和共感应
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
Nils Anders Danielsson;Thorsten Altenkirch
通讯作者：
Thorsten Altenkirch