compiler-construction - 为什么按值调用评估策略不是图灵完备的？

Question

我正在阅读一篇关于不同的文章 evaluation strategies (我在 wiki 中链接了文章，但我正在阅读另一篇不是英文的文章)。它说不像call-by-name和 call-by-need策略，call-by-value策略不是Turing complete .

谁能解释一下，为什么会这样？如果可能，请添加示例。

Answer 1

我对 claim 提出异议 在您正在阅读的文章中。 (我不会因此获得报酬，所以我将提供一个暗示性的论点，而不是证据。)

众所周知，至少在正态约简(又名调用)下，纯 lambda 演算是图灵完备的。但如果我们看看约翰雷诺兹的开创性论文 Definitional Interpreters for Higher-Order Programming Languages ，我们可以看到雷诺兹详细讨论了按名称调用和按值调用之间的区别。争论的一个关键部分是，为了做出适当的区分，我们可以将程序转换为 continuation-passing 风格。 CPS 变换对于按需求调用和按值调用是不同的，但是可以以任何一种方式评估生成的转换项。

因此，争论来了:编写一个模拟图灵机的 lambda 演算程序，然后使用 CBN 变换对其进行 CPS 变换，然后您可以使用 CBV 缩减策略评估生成的代码。砰!图灵完备。

在实践中，我敢打赌你可以编写一个 CBV 程序来模拟图灵机；选择一个合适的定点组合器可能就足够了，例如 Θ。 (更著名的 Y 组合器仅在按名称调用的减少策略下工作，即正常顺序减少。)

免责声明:我已经很久没有研究 lambda 演算了，而且我确信上面的论证中有几个细节是错误的。但我对实质有信心。这不是我第一次在有关编程语言理论的在线资源中发现明显的错误。