Jump over left menu
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?
California Institute of Technology, Pasadena, California.
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.
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
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