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