5

谁能解释一下男人或男孩测试如何返回 -67 的值？
我徒劳地试图写下结果，或者用调试器跟踪它。任何帮助，将不胜感激。
可以在此处找到不同实现的列表。

4

1 回答 1

3

这是这个男人或男孩测试的一个很好的页面。它显示了以下有趣的事实：

k = 10：A = -67，A 被调用 722 次，B 被调用 (A - 1) 次。

在这种情况下，编写完整的调用跟踪有点没用，因为函数本质上是递归的，而且函数不是纯函数（正如您在 Haskell 翻译中看到的那样，它需要使用 STate Monads，包裹在k,保持杂质远离）：每个函数的范围（在这种情况下，变量k：它减一）在每次调用或递归时都会被修改，并且这些修改是计算正确答案所必需的。

我发现 JavaScript 翻译比原来的 ALGOL60 实现更具可读性：

function A(k, x1, x2, x3, x4, x5) { 
    function B() {
        return A(--k, B, x1, x2, x3, x4);
    }
    return k <= 0 ? x4() + x5() : B();
} 
function K(n) { return function() {return n}; }
alert(A(10, K(1), K(-1), K(-1), K(1), K(0)));

诀窍是记账：对函数的哪些引用会导致哪些副作用（变量的修改），并且在术语中会导致正确的函数评估。然而，正如我之前解释的那样，这种簿记是乏味的。

现代语言，例如这个 JavaScript 示例，具有正确的解释器/编译器来处理这些簿记案例。在制作 ALGOL60 编译器时，一些实现不正确。进行测试是为了将不正确的实现与正确的实现区分开来。

于 2011-07-30T15:29:09.803 回答