Whether the number of beta-steps in the lambda-calculus can be taken as a reasonable time cost model (that is, polynomially related to the one of Turing machines) is a delicate problem, which depends on the notion of evaluation strategy. Since the nineties, it is known that weak (that is, out of abstractions) call-by-value evaluation is a reasonable strategy while L\'evy's optimal parallel strategy, which is strong (that is, it reduces everywhere), is not. The strong case turned out to be subtler than the weak one. In 2014 Accattoli and Dal Lago have shown that strong call-by-name is reasonable, by introducing a new form of useful sharing and, later, an abstract machine with an overhead quadratic in the number of beta-steps. Here we show that also strong call-by-value evaluation is reasonable for time, via a new abstract machine realizing useful sharing and having a linear overhead. Moreover, our machine uses a new mix of sharing techniques, adding on top of useful sharing a form of implosive sharing, which on some terms brings an exponential speed-up. We give examples of families that the machine executes in time logarithmic in the number of beta-steps.
翻译:从90年代开始,人们就知道,一个薄弱的(即抽取的)逐倍价值评价是一种合理的战略,而L\'evy的最佳平行战略是强大的(即,它在所有地方都减少)不是。一个强有力的案例证明,它比弱的更微妙。2014年,Accattoli和Dal Lago显示,强有力的逐名共享形式是合理的,它引入了一种有用的共享新形式,后来,一个抽象的机器,在乙级步骤的数量中带有高端四边形。我们在这里也表明,强烈的逐倍价值评价在时间上是合理的,通过一种新的抽象机器实现有用的共享和直线式的间接。此外,我们的机器使用一种新的共享技术组合,除了分享不易的共享形式外,还添加了某种不易的共享形式,在某个术语中以指数式速度移动的方式运行该机器。