一句话:提出基于Krivine抽象机变体的λ演算空间代价模型,首次支持对数空间,并研究其时间行为与call-by-value移植。
本文探讨λ演算能否作为合理的计算模型,特别是能否度量算法的空间消耗。既有文献对时间消耗已给出肯定答案,但空间方面所知甚少。作者提出一种新的λ演算合理空间代价模型,其基础是Krivine抽象机的一个变体。该模型首次能够容纳对数空间。论文还分析该机器的时间行为,并说明如何将相关结果迁移到call-by-value λ演算。这一工作为λ演算中的空间复杂度与合理代价语义提供了新方案。
Can the λ-calculus be considered a reasonable computational model? Can we use it for measuring the time 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.