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.

This sounds like homework, can you explain how the first 9 iterations work? If you can do the first 4 then to determine how it gets -67 should be easy. That may help more answers to be forthcoming, I would guess. — James Black, Nov 17 '09 at 07:31
I was hoping to get an answer from someone who already knew the answer. If you think you are up to the task by all means, but this is most certainly not homework. All references to the test I can find say "Trying to work it through on paper is probably fruitless" in one form or another. — CaptainCasey, Nov 17 '09 at 22:00

score 3 · Answer 1 · edited Mar 19 '15 at 15:56

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.

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

1 Answers1