Reasoning about the garden of forking paths
Reasoning about the garden of forking paths
复制标题
关于分叉小径花园的推理
DOI：
10.1145/3473585
复制
发表时间：
2021
影响因子：
--
通讯作者：
Weirich, Stephanie
中科院分区：
文献类型：
--
作者：
Li, Yao;Xia, Li-yao;Weirich, Stephanie
惰性求值是函数式程序员的一个强大工具。它使按需计算的简洁表达和其他评估策略下不可用的组合形式。然而，惰性求值的状态性质使得很难分析程序的计算成本，无论是非正式的还是正式的。在这项工作中，我们提出了一个新的和简单的框架，正式推理懒惰的计算成本的基础上最近的模型懒惰的评价：千里眼呼叫的价值。我们的框架的关键特征是它的简单性，正如我们对千里眼单子的定义所表达的那样。这个单子既容易定义（大约20行Coq），也容易推理。我们表明，这个单子可以有效地用于机械原因懒惰的功能程序的计算成本在Coq。
Lazy evaluation is a powerful tool for functional programmers. It enables the concise expression of on-demand computation and a form of compositionality not available under other evaluation strategies. However, the stateful nature of lazy evaluation makes it hard to analyze a program's computational cost, either informally or formally. In this work, we present a novel and simple framework for formally reasoning about lazy computation costs based on a recent model of lazy evaluation: clairvoyant call-by-value. The key feature of our framework is its simplicity, as expressed by our definition of the clairvoyance monad. This monad is both simple to define (around 20 lines of Coq) and simple to reason about. We show that this monad can be effectively used to mechanically reason about the computational cost of lazy functional programs written in Coq.
登录
查看更多内容
惰性上下文中的改进：按需调用的操作理论
DOI：
--
发表时间：
1999
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Andrew Moran;David Sands
通讯作者：
David Sands
拥抱机械化正规化差距
DOI：
10.1145/3314221.3322484
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Antal Spector;Joachim Breitner;Yao Li;Stephanie Weirich
通讯作者：
Stephanie Weirich
使用构造类型理论验证 haskell 程序
DOI：
10.1145/1088348.1088355
发表时间：
2005
期刊：
ArXiv
影响因子：
--
作者：
Andreas Abel;Marcin Benke;Ana Bove;John Hughes;U. Norell
通讯作者：
U. Norell
Monad 翻译归纳和共归纳类型
DOI：
10.1007/3-540-39185-1_17
发表时间：
2002
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Tarmo Uustalu
通讯作者：
Tarmo Uustalu
效果的谓词转换器语义（功能性珍珠）
影响因子：
--
作者：
Wouter Swierstra;T. Baanen
通讯作者：
T. Baanen