## Man Or Boy

### September 16, 2016

Knuth got it wrong:

(define (a k x1 x2 x3 x4 x5) (define (b) (set! k (- k 1)) (a k b x1 x2 x3 x4)) (if (<= k 0) (+ (x4) (x5)) (b)))

> (a 10 (lambda () 1) (lambda () -1) (lambda () -1) (lambda () 1) (lambda () 0)) -67

All of the `lambda`

s are necessary because *b* is a procedure, and thus all the numbers *x1*, *x2*, *x3*, *x4*, and *x5* must be represented as procedures. It is instructive to follow the recursion by hand for a few small values of *k*. Note that the sequence (A132343) becomes very large very quickly.

You can run the program at http://ideone.com/1JzXdF.

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.)