Computer algorithm for evaluating compiler implementations
The man or boy test was proposed by computer scientist Donald Knuth as a means of evaluating implementations of the ALGOL 60 programming language. The aim of the test was to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not.
 ;templatestyles src="Template:Blockquote/styles.css" / ;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.
Knuth's example.
In ALGOL 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 article Knuth conjectured it to be −121. Even modern machines quickly run out of stack space for larger values of "k", which are tabulated below (OEIS: ).
Explanation.
There are three Algol features used in this program that can be difficult to implement properly in a compiler:
These things are, however, not what the test is about; they are 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;