Friday, July 28, 2006


In the summer of 1961 I attended a lecture in Los Angeles by a little-known Danish computer scientist. His name was Peter Naur [1], and his topic was the new algorithmic language Algol 60. He covered a lot of concepts that I hadn't picked up from my limited study of Algo, though of course I didn't really absorb very much of them from one lecture.

But I do remember one thing clearly:
At the end there was a question period, and the man next to me stood up. "It seems to me that there is an error in one of your slides."

Peter was puzzled, "No, I don't think so. Which slide, and what do you think is wrong with it?"

"It's the slide that shows a subroutine calling itself. [2] That's impossible to implement." [3]

Now Peter was even more puzzled, "But we have implemented the whole language, and run all the examples through our compiler."

The man sat down, but was still muttering to himself, "Impossible! Impossible!" And I suspect that much of the audience agreed with him.

Had the questioner but realized it, Algol 60's name parameters were a far greater implementation challenge than recursion, but the GIER compiler got them right, too.

Edited to add: I have just encountered some evidence that Alan Turing anticipated an important element of the call stack in his Pilot ACE proposal.

[1] Peter Naur is the latest recipient of the prestigious A. M. Turing Award, in large part for his work connected with the Algol 60 Report and the GIER compiler. Here is a picture of me with him at the ACM Awards Banquet in San Francisco last April.

[2] This may have been the striking example of doing double integration by calling the numerical integration procedure with a call of itself as a name parameter, and the other parameters controlled by "Jensen's device."
[3] At the time it was fairly common practice to statically allocate the memory for a subroutine's code, its local variables, and its return address all together. The call stack had been independently invented at least twice in Europe, under different names, but was still not widely understood in America.