"Man or boy" - Knuth's test case for Algol60 compilers

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

1 Like

One thing I’m getting from the Chilton site is that they’re running an Algol compiler in 8KW of store… There is hope for my 64K 6502 to be self-hosting for something other than BASIC yet…

Cheers,

-Gordon

2 Likes

Peter Naur’s Gier Algol did better: 1024 words of core and about 12K of drum

1 Like

It’s pretty amazing what could be done - even given the possibility that the word-based machines of the day had more powerful instruction sets.

Now that many retrocomputers can be fitted with solid state storage, swapping (which was surely necessary with a 1k word system) could be back on the cards. Bring back overlays! Or, maybe, banked memory and lots of it.

1 Like

There is a very good description of how that compiler worked in David Gries’ “Compiler Construction for Digital Computers.”
Essentially, it used a LOT of very simple passes. It’s quite a marvel and recommended reading for anyone that thinks computer memory has to be measured in Gigabytes!
EDIT: https://archive.org/details/compilerconstruc0000grie

1 Like

A minor detail:

if k ≤ then

– You could do this (omit zero)?

The Modified Report states, in section 3.4. “Boolean Expression” [1]

<relation> ::= <simple arithmetic expression> <relational operator> <simple arithmetic expression>

where <simple arithmetic expression> resolves towards <term> and <factor>, none of which may be empty.

[1] https://www.masswerk.at/algol60/report.htm#3_4

Good spot - but it looks to me likely to be a typo (or transcription error) in the Chilton Computing site. In fact, I see it is a typo - many Algol Bulletins are available on the ACM’s site, and AB17 is among them. See here - click through to an issue and then the Front Matter PDF which is actually the whole document. There’s some very interesting reading in there!

And, for fun, here’s a table from AB17 of compilers written or in progress, in Japan alone:

The table on the following page is extracted from the List of ALGOL and FORTRAN Compilers in Japan: May 1964, a report of the ALGOL/FORTRAN committee of the Japan Electronic Industry Development Association, by permission. The report gives similar information about 17 FORTRAN compilers, 13 of which are already in use.

1 Like

Yes, I would have also guessed it’s a typo, given the “: =” assignment following just after this – but you never know. (However, it may be a feature just a bit too “modern”, like the use of a sole decimal point for zero.)

Thanks for the ACM library link!