We study the weak call-by-value $\lambda$-calculus as a model for computational complexity theory and establish the natural measures for time and space -- the number of beta-reductions and the size of the largest term in a computation -- as reasonable measures with respect to the invariance thesis of Slot and van Emde Boas [STOC~84]. More precisely, we show that, using those measures, Turing machines and the weak call-by-value $\lambda$-calculus can simulate each other within a polynomial overhead in time and a constant factor overhead in space for all computations that terminate in (encodings) of 'true' or 'false'. We consider this result as a solution to the long-standing open problem, explicitly posed by Accattoli [ENTCS~18], of whether the natural measures for time and space of the $\lambda$-calculus are reasonable, at least in case of weak call-by-value evaluation. Our proof relies on a hybrid of two simulation strategies of reductions in the weak call-by-value $\lambda$-calculus by Turing machines, both of which are insufficient if taken alone. The first strategy is the most naive one in the sense that a reduction sequence is simulated precisely as given by the reduction rules; in particular, all substitutions are executed immediately. This simulation runs within a constant overhead in space, but the overhead in time might be exponential. The second strategy is heap-based and relies on structure sharing, similar to existing compilers of eager functional languages. This strategy only has a polynomial overhead in time, but the space consumption might require an additional factor of $\log n$, which is essentially due to the size of the pointers required for this strategy. Our main contribution is the construction and verification of a space-aware interleaving of the two strategies, which is shown to yield both a constant overhead in space and a polynomial overhead in time.
翻译:更确切地说,我们研究的是微弱的模拟计算价值 $\ lambda$- calculus,作为计算复杂度理论的模型,并确立时间和空间的自然测量标准 -- -- 计算中的贝塔减缩数量和最大条件的大小 -- -- 作为对斯洛特和范恩德博阿斯的变换理论[STOC~84]的合理测量标准。我们发现,使用这些措施,图灵机器和微弱的调-价值 $\ lambda$- calcululs, 可以在一个多数字的间接间接测算中相互模拟对方,而空间的常数间接测算中, 以“ 真正的” 或“ false ” 结尾的所有计算方法。我们认为这一结果可以解决长期的开放问题, 由Actcattolit [ entCSCS~ 18] 明确提出的, 自然测算时间和空域的空域空间空间空间的面积是否合理,至少以低调的计算方法为基础, 。在调值评估中, 。我们的证据依靠两种模拟的模拟时间的计算中的一种模拟策略的计算方法,