A Computational Understanding of Classical (Co)Recursion
A Computational Understanding of Classical (Co)Recursion
复制标题
对经典（联合）递归的计算理解
DOI：
10.1145/3414080.3414086
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Z. Ariola
中科院分区：
文献类型：
--
作者：
P. Downen;Z. Ariola
递归和归纳法是编程中成熟且易于理解的主题。然而它们的双重性，共递归和共归纳，仍然是外来的和不发达的编程特性。我们的目标是通过提供一个基于计算的共递归的基础，使它们处于平等的地位，类似于递归的原始计算基础。在较低的层次上，我们展示了如何通过抽象机器中的实现细节来加强两者之间的联系。在更高的层次上，我们发展了一个基于控制流的归纳和协归纳推理的句法方程理论。我们还观察到计算策略的影响：按名称调用具有有效递归和强归纳推理，而按值调用具有有效递归和强归纳推理。
Recursion and induction are mature, well-understood topics in programming. Yet their duals, corecursion and coinduction, are still exotic and underdeveloped programming features. We aim to put them on equal footing by giving a foundation for corecursion based on computation, analogous to the original computational foundation of recursion. At the lower level, we show how the connection between the two can be strengthened through their implementation details in an abstract machine. At the higher level, we develop a syntactic equational theory for inductive and coinductive reasoning based on control flow. We also observe the impact of evaluation strategy: call-by-name has efficient recursion and strong coinductive reasoning, but call-by-value has efficient corecursion and strong inductive reasoning.
登录
查看更多内容
使用扩展类型制作更快的 Curry
DOI：
10.1145/3331545.3342594
发表时间：
2019
期刊：
ACM SIGPLAN International Symposium on Haskell
影响因子：
--
作者：
Downen, Paul;Sullivan, Zachary;Ariola, Zena M.;Peyton Jones, Simon
通讯作者：
Peyton Jones, Simon
影响因子：
1.1
作者：
DOWNEN, PAUL;ARIOLA, ZENA M.
通讯作者：
ARIOLA, ZENA M.
DOI：
10.4230/lipics.csl.2018.21
发表时间：
2018
期刊：
Conference on Computer Science Logic (CSL 2018
影响因子：
--
作者：
Downen, P;Ariola, Z.M.
通讯作者：
Ariola, Z.M.
行动中的 Codata
DOI：
10.1007/978-3-030-17184-1_5
发表时间：
2019
期刊：
Programming Languages and Systems. ESOP 2019
影响因子：
--
作者：
Downen, Paul;Sullivan, Zachary;Ariola, Zena M;Peyton Jones, Simon
通讯作者：
Peyton Jones, Simon