Can the $\lambda$-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 $\lambda$-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 $\lambda$-calculus.
翻译：$\ lambda$- calculus 是否可被视为合理的计算模型? 我们能否用它来测量算法的空间消耗时间 $\ textit{ 和} $ 空间消耗? 虽然文献中包含关于时间的正面答案, 但对于空间却不那么为人所知。 本文为 $\ lumbda$- calculus 提供了一个新的合理的空间成本模型, 其依据是克里维尼抽象机器的变量。 这个成本模型首次能够容纳对数空间。 此外, 我们研究我们的机器的时间行为, 并展示如何将我们的结果传输到调用量 $\ lambda$- calculuus 。
相关内容
微信扫码咨询专知VIP会员