Abstract machines for Open Call-by-Value
Abstract machines for Open Call-by-Value
复制标题
开放式按值调用的抽象机
DOI：
10.1016/j.scico.2019.03.002
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
Accattoli B
中科院分区：
文献类型：
--
作者：
Accattoli B
按值调用λ演算的理论依赖于弱评估和封闭项，这是编程语言研究中的自然假设。然而，为了对证明助手进行建模，需要强求值和开放项。开放值调用是弱求值与（可能）开放项的中间设置，在此之上，Grégoire 和 Leroy 设计了 Coq 的抽象机之一。本文提供了火球演算的抽象机器理论，这是开放式按值调用的最简单表示。文献中包含的机器要么简单但效率低，因为它们具有指数级开销，要么高效但繁重，因为它们依赖于环境标签和技术优化。我们引入了一种简单而高效的机器：它不使用标签，并且在双线性开销内实现火球演算。此外，我们对不同的优化如何影响开销的复杂性提供了新的精细理解，并证明我们使用的时间成本模型是最小的。
The theory of the call-by-valueλ-calculus relies on weak evaluation and closed terms, that are natural hypotheses in the study of programming languages. To model proof assistants, however, strong evaluation and open terms are required.Open call-by-valueis the intermediate setting of weak evaluation with (possibly) open terms, on top of which Grégoire and Leroy designed one of the abstract machines of Coq. This paper provides a theory of abstract machines for thefireball calculus, the simplest presentation of open call-by-value.The literature contains machines that are eithersimplebut inefficient, as they have an exponential overhead, orefficientbut heavy, as they rely on a labeling of environments and a technical optimization. We introduce a machine that issimpleandefficient: it does not use labels and it implements the fireball calculus within a bilinear overhead. Moreover, we provide a new fine understanding of how different optimizations impact on the complexity of the overhead, and evidence that the time cost model we work with is minimal.
登录
查看更多内容
按值调用的可解性
DOI：
10.1051/ita:1999130
发表时间：
1999
期刊：
RAIRO Theor. Informatics Appl.
影响因子：
--
作者：
Luca Paolini;S. D. Rocca
通讯作者：
S. D. Rocca
摇摇欲坠的抽象机器
DOI：
10.1145/3354166.3354169
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Accattoli B
通讯作者：
Accattoli B
DOI：
10.1007/978-3-662-44145-9_3
发表时间：
2014
期刊：
J. ACM
影响因子：
--
作者：
Beniamino Accattoli;C. Coen
通讯作者：
C. Coen
提炼抽象机器
影响因子：
--
作者：
Beniamino Accattoli;Pablo Barenbaum;Damiano Mazza
通讯作者：
Damiano Mazza
打开按值调用
影响因子：
--
作者：
Beniamino Accattoli;Giulio Guerrieri
通讯作者：
Giulio Guerrieri