## Man Or Boy

### September 16, 2016

During the development of Algol 60, Donald Knuth devised a nasty test of recursion:

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:

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)) endThis uses nothing known to be tricky or ambiguous. My question is: What should the answer be? Unfortunately, I don’t have to a man-compiler myself, and so I was forced to try hand calculations. My conjecture (probably wrong) is that the answer will be:

73 - 119 - 177 + 102 = - 121I’d be very glad to know the right answer.

Your task is to write a program that computes the right answer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Maybe you’d like to check this out: https://www.rosettacode.org/wiki/Man_or_boy_test

This goes up to 27…so I suppose I am a man compiler.

I modified the Algol 60 program by hand until GNU MARST would compile it: declared the xs (as integers), removed the space from inside an assignment operator, replaced the proper inequality symbol with its ASCII representation, added the 0 to compare against (huh?), and inserted a couple of semicolons. And added a “channel” where the result is printed: 1 for stdout.

MARST processes Algol 60 according to a Modified Report, 1976, which applies a Supplement to the Revised Report. (Scheme would later follow its Revised Report, 1978, with a Revised Revised Report.)

begin

real procedure A(k, x1, x2, x3, x4, x5);

value k; integer k;

integer 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

MARST translates Algol 60 to C. MARST agrees with those who say that the answer should be -67.

$ ./marst knuth.alg -o knuth.c

$ gcc knuth.c -L .libs -lalgol -lm -o knuth

$ LD_LIBRARY_PATH=.libs/ ./knuth

-67 $

MARST comes with a converter from earlier forms of the language. I haven’t tried the converter. Was that 0 really optional at some stage?

I’m also wondering why the result should be declared real. This is clearly integer arithmetic.

I object to the eating of the indentations. Happily they weren’t all that crucial this time.

This was a fun problem. Thanks!

@namako, that was beautiful.

Here are two solutions. The first, in Python 3, reads a lot like the original. The trickiest part was having B find the right instance of k.

And here is one in C. C is really badly suited for this process, though this C programs runs faster than Our Gracious Host’s solution in Ikarus Scheme. Most Scheme compilers have to search the environment for the nonlocal variable k, I think, while the C program increments k in O(1) time.

I tried to follow the spirit of Algol 60, using thunks and explicit stack frames to evaluate parameters with call-by-name semantics. If I limit the process’s stack size to 16 GB, I can also evaluate k=27. (My workstation only has 16 GB, so going higher is horribly slow as the virtual memory system thrashes.)

One more note. The first time I used Algol-60 was in the MIT introductory CS class, 6.031, in 1979. The last time I used Algol-60 was also in 6.031 in 1979. (-:

I’m stll puzzled at Knuth declaring those procedures “real”. They seem to work fine as “integer” (-67, using GNU MARST to compile).

(And I’m hoping to have it indented as intended this time.)