knuth - "Man Or Boy"Knuth 测试如何进行？

Question

谁能解释一下 Man Or Boy Test返回值 -67？
我徒劳地尝试写下结果，或者用调试器跟踪它。任何帮助将不胜感激。
可以找到不同实现的列表 here .

Answer 1

This is a nice page在这个男人或男孩测试中。它显示了以下有趣的事实:

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

在这种情况下，编写完整的调用跟踪有点没用，因为该函数本质上是递归的，而且这些函数不是纯函数(您可以在 Haskell 翻译中看到，它需要使用 STate Monads，包裹在 k 周围，以保持杂质远离):每个函数的作用域(在本例中是变量 k:它减少了 1)每次调用或递归都会被修改，并且这些修改是计算正确答案所必需的。

我发现 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 编译器问世时，某些实现并不正确。进行测试是为了将不正确的实现与正确的实现区分开。