论文标题
$λ$ -calculus的合理空间，对数
Reasonable Space for the $λ$-Calculus, Logarithmically
论文作者
论文摘要
$λ$ -Calculus可以被视为合理的计算模型吗？我们可以使用它来测量$ \ textit {and} $的时间消耗算法的时间吗？尽管文献包含有关时间的积极答案，但对空间的了解少得多。本文基于Krivine Abstrack Machine上的一个变体，介绍了$λ$ -calculus的新的合理空间成本模型。该成本模型首次能够适应对数空间。此外，我们研究机器的时间行为，并展示如何将结果传输到逐个价值$λ$ -calculus。
Can the $λ$-calculus be considered a reasonable computational model? Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $λ$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $λ$-calculus.
