"男人还是男孩"Knuth测试如何运作？

Question

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

Answer 1

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

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