In 1964 Donald Knuth proposed a test:
I have written the following simple routine, which may separate the man-compilers from the boy-compilers:
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 ≤ then A : = x4 + x5 else B
end
outreal(A(10, 1, -1, -1, 1, 0))
end
At Rosetta Code we read:
The aim of the test was to distinguish compilers that correctly implemented “recursion and non-local references” from those that did not.
The original letter and a number of responses can be read on the ever-fascinating Chilton Computing site. Including some boasting of how fast Atlas was, or how difficult it was to run a program with deep recursion on ZEBRA, a machine with only 8k RAM.
Knuth followed up with a confession:
I gave an ALGOL 60 program… I have received answers of all types but unfortunately none of them agreed with my original conjecture of -121. Therefore in order to save face, if possible, let me say that a slight error in my hand calculations caused my conjecture to be faulty. (I have an excuse: at the time I did the original calculation I had broken my right wrist, so the calculations were done left-handed!)
Algol60 allows for the rather tricky call-by-name paradigm. Although at the time this was presumably felt to be natural, it’s much less popular now. Indeed, Knuth says “This uses nothing known to be tricky or ambiguous.”
