How does the "Man Or Boy" Knuth test work?

Question

Can anyone explain how the Man Or Boy Test returns a value of -67?
I tried in vain to write down the result, or trace it with a debugger. Any help would be appreciated.
A list of different implementations can be found here.

Answer 1

This is a nice page on this Man or Boy test. It shows the following interesting facts:

k = 10: A = -67 and A is called 722 times, B is called (A - 1) times.

Writing a complete calltrace is a bit useless in this case, as the function is recursive in nature, with the addition that the functions are not pure (as you can see in the Haskell translation, it requires the use of STate Monads, wrapped around k, to keep the impurity away): each function's scope (in this case the variable k: it's decreased by one) is modified each call or recursion and these modifications are required for the calculation of the correct answer.

I find the JavaScript translation a bit more readable, than the original ALGOL60 implementation:

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)));

The trick is bookkeeping: what references to functions cause which side-effects (modification of variables) and in term cause a correct function evaluation. However, this bookkeeping is tedious, as I explained earlier.

Modern languages, such as this JavaScript example, have correct interpreters/compilers to handle these bookkeeping cases. The time ALGOL60 compilers were made, some of the implementations were not correct. The test was made to separate the incorrect implementations from those that are correct.