How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics

By now it is difficult to imagine that once there was a time when the utility, and even the possibility, of recursion in programming was in doubt. Yet that was true of the programming community around 1960. Even the committee that was to create Algol 60 was divided on the issue. How recursion got into the language is a story of intrigue and misunderstandings. I came across this story for the first time when reading Gauthier van den Hove’s excellent MSc thesis [11]. It is also the subject of Chapter 3 in [12].

In the late 1950s a committee was formed to design a universal, machine-independent programming language. Such a language was not a superfluous luxury at the time: programmers were using programming systems provided by the hardware manufacturers that were not even uniform across the different models. Fortran was the first exception, but was at the time still tied to a single manufacturer. Lisp was a harbinger of things to come: machine-independent and not tied to a manufacturer. This is what Algol wanted to be, but then more official: sponsored by IFIP, the International Federation for Information Processing, established under the auspices of UNESCO.

McCarthy, fresh from the success of his Lisp project, was enthusiastic about recursion as an elegant way to get computers to do what they are best at: repeat execution of the same code with suitable modification each time around. In fact, the first Lisp had no iteration, so that the only way to add all elements of a linear list was to write a recursively defined function. As a member of the Algol committee he proposed making the possibility of recursion a feature of the new language. The proposal was crowded out by more pressing concerns. The result was that in the early months of 1960, when the report was to be finalized, there was no consensus on recursion.

There were plenty of reasons to be opposed. It was not clear whether it could be implemented: a flaky academic experiment like the Lisp interpreter was not an authoritative example for the solid, efficient compiler that the German faction of the committee had in mind. But committee members Naur and van Wijngaarden agreed with McCarthy that recursion was too tempting an opportunity to be missed. Van Wijngaarden had been egged on by his sidekick Edsger W. Dijkstra, who was in favour of recursion and who may well have supplied van Wijngaarden with his new, as yet unpublished, ideas about implementing recursion.

Naur was the committee member editing the final version of the Algol report. Two decades later Naur remembered it as follows [1]:

The last substantial change of language concepts was the admission of recursive procedure activations. This took place as follows. […] [O]n about February 10, […] I had a telephone call from A. van Wijngaarden, speaking also for E.W. Dijkstra. They pointed to an important lack of definition in the draft report, namely the meaning, if any, of an occurrence of a procedure identifier inside the body of the declaration other than in the left part of an assignment. They also made it clear that preventing recursive activations through rules of the description would be complicated because of the possibilities of indirect activation through procedures and their parameters. They proposed to clarify the matter by adding a sentence to section 5.4.4.: “Any other occurrence of the procedure identifier within the procedure body denotes activation of the procedure.” I got charmed with the boldness and simplicity of this suggestion and decided to follow it in spite of the risk of subsequent trouble over the question.

It turned out that there was “trouble over the question”. Several committee members had been tricked into approving a final version of the report that included an easily overlooked late addition that settled the controversy in the direction opposite to their wish. Committee member F.L. Bauer registered his protest by characterizing the addition of recursion to the language as an “Amsterdam plot” [1, Appendix 5].

That this was not paranoia on the part of Bauer is made clear by Dijkstra in an interview in 2001 [2]:

Recursion was a major step. It was introduced in a sneaky way. The draft ALGOL-60 report was circulated in one of the last weeks of December ’59. We studied it and realized that recursive calls were all but admitted, though it wasn’t stated. And I phoned Peter Naur — that call to Copenhagen was my first international telephone call, I’ll never forget the excitement! — and dictated him one suggestion with the suggestion that he include it. It was something like “Any other occurrence of the procedure identifier denotes reactivation of the procedure.” Something like that. That sentence has been inserted sneakily. And of all the people who sort of had to agree with the report, none saw that sentence. That’s how recursion was explicitly included.

But what was it that Bauer did not and that Dijkstra did implement? Indeed what does “recursion” mean? A closer look at the above testimonies of Naur and of Dijkstra shows that one speaks of “recursive procedure activations”, a runtime concept, whereas Dijkstra speaks of “recursion”, which can be interpreted as a property of source programs.

Here are some attempts at clarification of “recursion”.

1. It is possible that during execution a procedure is called for which there exists an activation record of an earlier call.
2. Calls to self, directly or indirectly, possibly through calls to procedures that are named as formal parameters.
3. Calls to self, directly or indirectly, or indirectly through calls to procedures that are not named as formal parameters.

Naur had in mind meaning 1, whereas Dijkstra probably had in mind meaning 2.

When the Bauer faction of the Algol committee discovered that they were victims of the Amsterdam Plot, it seemed a simple matter to define their preferred version of Algol: remove the offending sentence. They discovered that this did not eliminate recursion. At least not recursion according to meaning 1. And this is what they wanted to remove because they wanted static allocation of procedure activation records.

The publication of the Algol-60 report was followed by several attempts to redefine the language: SMALGOL [3], the ECMA subset [4], and SUBSET Algol [5]. These are united in their desire to disallow programs that need dynamic allocation of procedure activation records. All three are unanimous in deleting the last sentence of Section 5.4.4 of the Algol-60 report. They are agreed that this is not enough to banish the spectre of recursion, but have different attempts in this direction. For example, the last adds section 4.7.5.6 to the Algol-60 report:

No call of the procedure itself may occur during the execution of the statements of the body of any procedure, nor during the evaluation of those of its actual parameters, the corresponding formal parameters of which are called by name, nor during the evaluation of expressions occurring in declarations inside the procedure.

I understand the Algol-60 report, but not this sentence. The SUBSET people supply an alternative formulation for people like me:

Do not write recursive procedures. Do not use procedures recursively.

As Dijkstra had already foreseen, they should have added:
“And don’t try to do anything sneaky with procedure parameters.”.
This way one of the achievements of the Algol 60 was lost: a single document for the implementer and for the user.

One effective cure against recursion is to eliminate nested procedure declarations and to require a procedure to be declared before the first call to it. We see this for example in C, which has been characterized as “glorified assembler language” as a result of being that paragon of efficiency that the Bauer faction valued above all. The irony is that the designer of this paragon of efficiency saw no problem in dynamically allocating procedure activation records nor in allowing a procedure to call itself. Without modification, the requirement of declaration before call would eliminate the possibility of mutual recursion. As this would not give a problem with dynamic activation records, Ritchie relaxed the definition-before-use rule by allowing redundant declarations of procedure headings. At the expense of a redundant advance declaration the programmer can define mutually recursive procedures in C.

Of course we cannot blame the Bauer faction for not having the experience of later workers in the field. It is interesting that in 1960 there did exist knowledge that indicated how difficult it is to avoid the need for dynamic allocation when one wants the attractive procedure mechanism of Algol. This procedure mechanism is similar to that of lambda calculus, which was known since the 1930s. It seems clear in its compact definition that lambda calculus does not allow recursive function definitions. Yet already by 1935 at least two versions had been discovered of the Y combinator, an expression of the lambda calculus. And this combinator makes recursive function definitions possible in lambda calculus.

The lambda calculus is another example of how difficult it is to avoid recursion once one has a simple and general function definition mechanism. Again, one cannot blame the Bauer faction for not knowing these things. Indeed the use of the Y combinator for recursion did not become widely known until the 1970’s with the publication of books such as [7].

And it is safe to assume that the perpetrators of the Amsterdam plot did not know either. How is it then that they were so sure that they were on the right track? In the case of one of the plotters, E.W. Dijkstra, we do know. In October 1961 he published Mathematical Centre report MR 34 “On the Design of Machine-Independent Programming Languages” [8]. In this paper Dijkstra proposes general principles for language design that he considered relevant at the time and that, it seems to me, are still relevant today. It is safe to assume that a year before he was already convinced of these principles. The generality of these principles made it possible for him to dispense with knowledge of Y combinators and subsequent experience with efficient implementations of dynamic allocation of procedure activation records.

In one of the most cited papers in all of computing, F.P. Brooks [9] contrasts programming systems or languages that have fanatical adherents to a bunch of ho-hum items that, though perhaps useful, do not. He notes that the former were created by individuals, the latter by committees. By implication he suggests that committee-designed artefacts are necessarily in the ho-hum category. Brooks identifies the distinguishing criterion as conceptual integrity. Brooks places Algol 60 in the latter category, because committee-designed things supposedly necessarily lack conceptual integrity.

I went out for a second opinion, and found this, by Dijkstra [10, page 4]:

And then the 60s started with an absolute miracle, viz. ALGOL 60. This was a miracle because on the one hand this programming language had been designed by a committee, while on the other hand its qualities were so outstanding that in retrospect it has been characterized as “a major improvement on most of it successors” (C. A. R. Hoare).

How did the miracle happen? How was it possible for a large committee, of varying membership, which is what the Algol committee was, to dramatically advance the state of the art and then come up with a document that is terse, complete, and describes a language with conceptual integrity, that quality prized so highly by Brooks?

The answer is that there was a gestation period that began with the International Symposium on Automatic Computing held in October 1955 in Darmstadt. Several speakers proposed the need of a single universal, machine-independent, algorithmic language. The first of a succession of committees started work on this. Contact was sought, and found, with like-minded workers in the United States. It was a joint European/US committee that met in Zürich and agreed on criteria for such a language. A document was produced that was sufficiently detailed to merit the name of Algol 58.

Publication of this report aroused interest in further development of the language. Peter Naur was among the new members that joined the Algol committee. Algol 58 was in need of further development. Many new ideas were proposed. In several ways the committee was advancing beyond the most advanced existing ideas and beyond their own intellectual grasp.

And the committee was floundering. Naur, though the new kid on the block, saw the need for a structured discussion medium and created the Algol Bulletin. He started to consolidate results in the form of a language definition. He studied Backus’s formalism for syntax definition and applied it to the overburdened syntactic wish list for the new language. And got it ready just in time for handing out at the final design conference in January 1960 in Paris. No time for preparatory politics.

Bauer’s 1978 recollection [1, page 41]:

… explains one of the strange incidents of the Paris ALGOL-60 Conference … were surprised by Peter Naur handing them out at the beginning of the Paris Conference his 18 pages draft Report. Peter Naur had not been commissioned to do so, it was a fait accompli. It therefore sounds poetic if he has written that his draft Report was ‘chosen’ as the basis of the discussion; the Committee was simply forced to do so, after Peter Naur had gained this advantage. Likewise, he became automatically the Editor; it was only a question of politeness to invite him. Since there was some concern that he would use this position to exert some influence of his own on the language (what has happened indeed, as he indicates himself), this development was not considered to be very healthy by some Committee members.

In other words, some Committee members were truly pissed off. On the next page:

It should be mentioned, however, that there was not only scepticism among the Committee members, but also resignation that there was nothing one could do when the Editor did arbitrarily change the outcome of the Conference: it was to be swallowed for the sake of loyalty.

And yet Bauer writes:

On the other hand, this situation has certainly helped to get a draft of the Report finished in spite of the very tight time schedule of the six day Paris Meeting.

This explains the miracle: after the creative, explorative, and floundering stage of the Algol enterprise, the new kid on the block appears, and takes over. The old guard vaguely recognizes that he rescues the enterprise, but does it ever hurt. Bauer, for one, may never have forgiven Naur; the spite quoted above was written in 1978, long after the events. To me they indicate the extent to which Algol 60, the “miracle”, was Naur’s creation.

In summary, let me justify the lurid subtitle: “A tale of intrigue, betrayal, and advanced programming language semantics”. There was intrigue: van Wijngaarden and Dijkstra phoning Naur with the intention of getting him to make (what they thought) a crucial change to the Algol 60 report. There was betrayal of trust, because they intended the change to settle unobtrusively an issue that they knew was controversial and they knew that there was a high probability that the change was so unobtrusive that it would not be noticed. Finally there was advanced programming language semantics. This only in retrospect, now that further study of Algol 60 has recently revealed that the controversial addition did not make a difference to the semantics of the language, see van den Hove [13]. This is my reason for claiming that the episode recounted in this article involved advanced programming language semantics.

Acknowledgments

Until recently I did not realize there was a distinction between recursion and the possibility of multiple activation records for the same procedure. Similarly, I assumed that Peter Naur was just another member of the Algol committee, who happened to be editor. It is only because Gauthier van den Hove kindly showed me some of the results of his research that I learned the fascinating story that appears here. Mr van den Hove has posted his article [14].

Many thanks to Paul McJones for help in several ways.

References

[1] “The European Side of the Last Phase of the Development of Algol 60” by P. Naur; page 3. ACM SIGPLAN Notices 13(8), pp. 13– 44 (1978)
[2] Oral History interview conducted by Philip L. Frana on August 2, 2001, Austin, Texas. OH 330, Charles Babbage Institute, University of Minneapolis.
[3] “Smalgol-61”, G.A. Bachelor, J.R.H. Dempster, D.E. Knuth, and J. Speroni, eds. Comm. ACM 4(11), pp. 499–502 (1961).
[4] “ECMA subset of Algol 60” Comm. ACM 6(10), pp. 595–597 (1963).
[5] “Report on SUBSET Algol 60” Comm. ACM 7(10), pp. 626–628 (1964).
[6] Introduction to Combinators and Lambda Calculus by G.R. Hindley and J.P. Seldin. Cambridge University Press, 1986.
[7] Denotational Semantics by Joseph Stoy.
[8] also Annual Review in Automatic Programming vol.3, Richard Goodman, ed., pp 27 — 42, Pergamon Press 1963.
[9] “No Silver Bullet: Essence and Accidents of Software Engineering” by F.P. Brooks. Computer, 20 (4), pp. 10–19 (1987).
[10] “Computing Science: Achievements and Challenges” by E.W. Dijkstra. ACM SIGAPP Applied Computing Review 7 (2), pp. 2–9, 1999.
[11] Edsger Wybe Dijkstra: First Years in Computing Science (1951–1968) by Gauthier van den Hove. MSc thesis, University of Namur, 2009.
[12] The Dawn of Software Engineering: from Turing to Dijkstra by Edgar Daylight. Lonely Scholar, 2012.
[13]”On the origin of recursive procedures” by Gauthier van den Hove. Computer Journal, vol. 58(11), 2015, pp 2892-2899.
[14] http://www.fibonacci.org/GHE7.pdf