Algol System

Jump To Main Content

Jump Over Banner

Home

Jump Over Left Menu

Algol Bulletin

The Algol Bulletin was a major discussion forum on Algol matters. We have included a few examples of letters here concerning the quality of Algol compilers.

Man or boy?

Donald Knuth

California Institute of Technology, Pasadena, California.

Dear Editor:

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

This 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 = - 121

I'd be very glad to know the right answer.

Men Only: Gold Medalist

Alan Price and L.R. Hodges.

English Electric-Leo Computers Ltd. Kidsgrove. Stoke-on-Trent.

November 12th 1964

The answer to Donald Knuth's question is -67. Readers or the ALGOL Bulletin may be interested to know the answers for other values of k. The result for k=11 is -138.

These results were obtained by compiling the example using the Kidsgrove KDF9 ALGOL Compiler and took 12 seconds run time to compute k from 1 to 11.

Customized Compiler

W. L. van der Poel.

The Hague, 14th November 1964

We ran the Man or Boy test on our ALGOL compiler for ZEBRA. Because of the limited (8K) store of ZEBRA we came into some difficulties with the height of the stack for k = 10 but after cutting out several features, which are not needed in this test, we succeeded in turning out all values of A for k up to 10. The values agree with those calculated by the Mathematical Centre. We give here a value of A for another set of arguments:

A(10, 1, 2, 3, 4, 5) = 758

Seven Times Faster

F. R. A. Hopgood

Atlas Computer Laboratory, 7th April 1965

Readers may be interested in run-times for the Knuth Test on the I.C.T. Atlas Algol Compiler.

The test made by Price and Hodge for k=0(1)11 was repeated on the Atlas and a run-time of 1.5 seconds was obtained which compares with the 12 seconds using the KDF9 Kidsgrove Compiler.

The last word

Donald Knuth

California Institute of Technology, 16th November 1964

In my previous letter which was published under the title Man or boy? I gave an ALGOL 60 program which made heavy use of ALGOL's ability to refer to non-local quantities in the presence of recursion, when many quantities of the same name (but different scope) are present. 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!)

Since them my right hand has observed that the value of A(k, xl, x2, x3, x4, x5) is equal to cl × xl + c2 × x2 + c3 × x3 + c4 × x4 + c5 × x5 where the coefficients are given in the following table:

 k     c1(k)    c2(k)    c3(k)   c4(k)   c5(k)
 0      0        0        0       1       1
 1      0        0        1       1       0
 2      0        1        1       0       0
 3      1        1        0       0       0
 4      2        1        0       0       0
 5      3        2        1       0       0
 6      5        3        3       2       0
 7      8        6        9       6       0
 8     14       15       22      13       0
 9     29       37       48      26       0
10     66       85      102      54       0