Rom*_*man 7 compiler-construction computer-science programming-languages turing-complete
我正在阅读一篇关于不同评估策略的文章(我在wiki中链接了一篇文章,但我正在阅读另一篇不是英文的文章).·又不像到call-by-name和call-by-need战略,call-by-value战略是不是 图灵完整.
有人可以解释一下,为什么会这样？如果可能,请添加示例.
Nor*_*sey 10
我在您正在阅读的文章中对此声明提出质疑.(我没有得到这个,所以我要提供一个暗示性的论点,而不是证据.)
众所周知,至少在正常顺序减少(也称为名称调用)下,纯lambda演算是图灵完备的.但是,如果我们看看John Reynolds的高级编程语言的开创性论文" 定义解释器",我们可以看到Reynolds详细讨论了名称调用和按值调用之间的区别.论证的一个关键部分是,为了进行适当的区分,我们可以将程序转换为延续传递方式.CPS变换对于按需调用和按值调用是不同的,但是可以以任一样式评估所得到的变换项.
所以这里有一个论点:写一个模拟图灵机的lambda-calculus程序,然后使用CBN变换进行CPS变换,你可以使用CBV减少策略来评估结果代码.砰! 图灵完备.
在实践中,我打赌你可以写一个CBV程序来模拟图灵机; 它可能足以选择一个合适的定点组合器,例如Θ.(更有名的Y组合器仅在逐个名称缩减策略下工作,即正常顺序减少.)
免责声明:我没有多年研究过lambda演算,我确信在上面的论证中有几个细节错误.但我对这个实质有信心.这不是我第一次在关于编程语言理论的在线资源中发现一些明显错误的东西.