Recurrence extraction for functional programs through call-by-push-value
Recurrence extraction for functional programs through call-by-push-value
复制标题
通过按值调用对功能程序进行递归提取
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
N. Danner
中科院分区：
文献类型：
--
作者：
G. A. Kavvos;Edward Morehouse;Daniel R. Licata;N. Danner
分析程序复杂性的主要方法是提取和求解一个递归，这个递归用输入的大小来表示程序的运行时间。我们开发了一种方法，自动提取这种递归高阶递归函数程序的语法。产生的递归程序是使用递归的按名称调用语言的程序，它根据输入的大小显式计算运行时间。为了以统一的方式实现这一点，同时涵盖按名称调用和按值调用评估策略，我们使用按推值调用（CBPV）作为中间语言。最后，我们使用域理论来开发一个指称成本语义的递归。
The main way of analysing the complexity of a program is that of extracting and solving a recurrence that expresses its running time in terms of the size of its input. We develop a method that automatically extracts such recurrences from the syntax of higher-order recursive functional programs. The resulting recurrences, which are programs in a call-by-name language with recursion, explicitly compute the running time in terms of the size of the input. In order to achieve this in a uniform way that covers both call-by-name and call-by-value evaluation strategies, we use Call-by-Push-Value (CBPV) as an intermediate language. Finally, we use domain theory to develop a denotational cost semantics for the resulting recurrences.
具有垃圾收集的功能程序的自动空间限制分析
DOI：
10.29007/xkwx
发表时间：
2018
期刊：
EPiC Series in Computing
影响因子：
--
作者：
Niu, Yue;Hoffmann, Jan
通讯作者：
Hoffmann, Jan