Man or boy test

The man or boy test was proposed by computer scientistDonald Knuth as a means of evaluating implementations of theALGOL 60 programming language. The aim of the test was to distinguishcompilers that correctly implemented "recursion andnon-local references" from those that did not.

There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the man-compilers from the boy-compilers.

— Donald Knuth

Knuth's example [ edit ]

InALGOL 60:

begin
  real procedure A(k, x1, x2, x3, x4, x5);
  value k; integer k;
  real x1, x2, x3, x4, x5;
  begin
    real procedure B;
    begin k := k - 1;
          B := A := A(k, B, x1, x2, x3, x4)
    end;
    if k ≤ 0 then A := x4 + x5 else B
  end
  outreal(1,A(10, 1, -1, -1, 1, 0))
end

This creates a tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called. Trying to work it through on paper is probably fruitless, but for k =10, the correct answer is −67, despite the fact that in the original paper Knuth conjectured it to be −121. The survey paper byCharles H. Lindsey mentioned in the references contains a table for different starting values. Even modern machines quickly run out ofstack space for larger values of k, which are tabulated below ( OEIS :  A132343 ).

k 0 1 1 0 2 −2 3 0 4 1 5 0 6 1 7 −1 8 −10 9 −30 10 −67 11 −138 12 −291 13 −642 14 −1,446 15 −3,250 16 −7,244 17 −16,065 18 −35,601 19 −78,985 20 −175,416 21 −389,695 22 −865,609 23 −1,922,362 24 −4,268,854 25 −9,479,595 26 −21,051,458

Explanation [ edit ]

There are three Algol features used in this program that can be difficult to implement properly in a compiler:

1. Nested function definitions : Since B is being defined in the local context of A , the body of B has access to symbols that are local to A — most notably k which it modifies, but also x1 , x2 , x3 , x4 , and x5 . This is straightforward in the Algol descendantPascal, but not possible in the other major Algol descendantC (without manually simulating the mechanism by using C's address-of operator, passing around pointers to local variables between the functions).
2. Function references : The B in the recursive call A(k,B,x1,x2,x3,x4) is not a call to B , but a reference to B , which will be called only when k is greater than zero. This is straightforward in standard Pascal (ISO 7185), and also in C. Some variants of Pascal (e.g. older versions ofTurbo Pascal) do not support procedure references, but when the set of functions that may be referenced is known beforehand (in this program it is only B ), this can be worked around.
3. Constant/function dualism : The x1 through x5 parameters of A may be numeric constants or references to the function B — the x4+x5 expression must be prepared to handle both cases as if the formal parameters x4 and x5 had been replaced by the corresponding actual parameter (call by name). This is probably more of a problem instatically typed languages than in dynamically typed languages, but the standard workaround is to reinterpret the constants 1, 0, and −1 in the main call to A as functions without arguments that return these values.

These things are however not what the test is about; they're merely prerequisites for the test to at all be meaningful. What the test is about is whether the different references to B resolve to the correct instance of B — one that has access to the same A -local symbols as the B that created the reference. A "boy" compiler might for example instead compile the program so that B always accesses the topmost A call frame.

See also [ edit ]