The man or boy test was proposed by computer scientist Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
as a means of evaluating implementations of the ALGOL 60
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...
programming language. The aim of the test was to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not.
Knuth's example
begin
real procedure A(k, x1, x2, x3, x4, x5);
value k; integer k;
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(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 the correct answer is −67, despite the fact that in the original paper Knuth conjectured it to be −121.
The survey paper by Charles H. Lindsey mentioned in the references contains a table for different starting values.
Even modern machines quickly run out of stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
space for larger values of k.
k
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
A
1
0
-2
0
1
0
1
-1
-10
-30
-67
-138
-291
-642
-1446
-3250
-7244
-16065
-35601
-78985
-175416
-389695
-865609
-1922362
-4268854
-9479595
Explanation
There are three Algol features used in this program that can be difficult to implement properly in a compiler:
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 descendant Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
, but not possible in the other major Algol descendant C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
(although C's address-of operator & makes it quite possible to pass around pointers to local variables in arbitrary functions, so this can be worked around).
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 it appears as x4 or x5 in the statement A:=x4+x5. This is conversely straightforward in C, but not possible in many dialects of Pascal (although the ISO 7185 standard supports function parameters). When the set of functions that may be referenced is known beforehand (in this program it is only B), this can be worked around.
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 in statically typed languages than in dynamically typed languages, but the standard work-around 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 which has access to the same A-local symbols as the B which created the reference. A "boy" compiler might for example instead compile the program so that B always accesses the topmost A call frame.
The ALGOL Bulletin was published by the Association for Computing Machinery regarding the ALGOL 60 and ALGOL 68 programming languages from March 1959 till August 1988.-Time-line of ALGOL Bulletin:- References :...
