This chapter is from the book
This chapter is from the book
This chapter is from the book
ALGOL and the X1: 1958–1962
Dijkstra’s efforts at the MC were taking place at a formative time in computing. Hopper’s 1954 symposium on Automatic Programming8 had generated a lot of buzz. At that symposium, J. H. Brown9 and J. W. Carr III10 presented a paper on their efforts to create a universal programming language that was machine independent. Saul Gorn11 presented a similar paper. Both papers advocated for divorcing the structure of the language from the physical structure of the hardware.
This was a revolutionary concept that flew in the face of the thinking of the day. Languages like FORTRAN, MATH-MATIC, and eventually even COBOL were strongly wed to the physical architecture of the machines of the day. This strong binding was thought to be necessary to achieve efficiency of execution. Brown and Carr acknowledged that universal languages might be slower, but they argued that they would reduce programming time and programmer error.
As an example of the wedding between language and physical architecture, consider the type int in the C language. Depending upon the machine, it is either a 16-, 32-, or 64-bit integer. I once worked on a machine in which it was an 18-bit integer. In C, an int is wedded to the machine word. Many languages of the day simply assumed that the data format of the language was the data format of the machine, including memory layout. Subroutine arguments were assigned fixed locations, precluding any kind of recursion or reentrancy.
In May of 1958, Carr and several others met in Zurich to begin the definition of a universal machine-independent programming language. They named it ALGOL.12 The stated goal was to create a language based upon mathematical notation that could be used for the publishing of algorithms and mechanically translated into machine programs.
John Backus created a formal notation to describe an early (1958) version of the language. Peter Naur recognized the genius of the notation and named it Backus Normal Form (BNF13). He then used it to specify the 1960 version of ALGOL.
Meanwhile, Dijkstra and the MC were busy building the X1 computer. This was a fully transistorized machine, with up to 32K of 27-bit words. The first 8K of the address space was read-only memory and contained boot programs and a primitive assembler. The X1 was one of the first machines to have a hardware interrupt—something that Dijkstra would make strategic use of. The machine also had an index register! At last, real pointers! Otherwise, it was similar in many ways to the ARRA and ARMAC machines.
The memory cycle time was 32 μs and the add time was 64 μs. It could therefore execute over 10,000 instructions per second.
)
In 1959 Wijngaarden and Dijkstra joined in the effort to define the ALGOL language. In 1960, with the BNF specification complete, Dijkstra and his close colleague Jaap Zonneveld surprised the computing world by quickly writing a compiler for the X1.
“Surprised” might be an understatement. Naur wrote: “The first news of the success of the Dutch project, in June 1960, fell like a bomb in our group.”14 That bomb might explain some of the tension that arose later. I imagine Dijkstra & Co were viewed as upstarts who scooped everybody else.
Of their success, Dijkstra wrote:15 “The combination of no prior experience in compiler writing and a new machine [the X1] without established ways of use greatly assisted us in approaching the problem of implementing ALGOL 60 with a fresh mind.”
One of the techniques Dijkstra and Zonneveld used was “dual programming.” Each would independently implement a feature and then they would compare the results. Dijkstra called this an “engineering approach.” It has been suggested16 that this approach so significantly reduced their debugging time that it led to a net reduction in their development time.
This was at a time when most teams implementing the language were debating which features to leave in or out. Dijkstra and Zonneveld left nothing out. They implemented the full specification—in six weeks.
Indeed, they even implemented the part of the specification that virtually everyone had planned on omitting: recursion.
This is ironic because recursion had been voted out of the language. Dijkstra and John McCarthy had strenuously advocated for recursion, but the rest of the committee thought that recursion was too inefficient and was otherwise useless. However, the wording of the resolution was ambiguous enough that Dijkstra sneaked the feature in anyway.
This got him into some trouble with the other members of the ALGOL team. Indeed, the issue of recursion versus efficiency generated quite a bit of tension. In a meeting in 1962, one of the members17 got up and directed a nasty comment toward Dijkstra, Naur, and other proponents of recursion18—a comment that was greeted with loud applause and laughter:
“And the question is—to state it once more—that we want to work with this language, really to work and not to play with it, and I hope we don’t become a kind of ALGOL play-boys.”
One reason that Dijkstra and Zonneveld were successful when so many other teams were still struggling was because Dijkstra created an abstraction boundary between the language and the machine. The compiler converted ALGOL source code into a p-code,19 and an associated runtime system interpreted that p-code. Nowadays, we would call that runtime system a VM.20
This division allowed the language compiler to ignore the machine itself—which was one of the goals originally sought by Carr, Brown, Gorn, and the ALGOL team. Ignoring the machine made the compiler much easier to write. In short, Dijkstra invented a machine that was perfect for ALGOL, and then he made up the difference in his runtime system.
Of course, this caused certain inefficiencies. Simulating a p-code is always slower21 than raw machine language. But Dijkstra justified this by stalwartly refusing to worry about efficiency in the short term. His focus was more upon the long-term direction of language and computer architecture. Thus, he said:22
“In order to get as clear a picture as possible of the real needs of the programmer, I intend to pay, for a while, no attention to the well-known criteria ‘space and time’. ”
He went on to say:
“I am convinced that [the] problems [of program correctness] will prove to be much more urgent than, for example, the exhaustive exploitation of specific machine features….”
And just to cap things off:
“. . .Recursion] is such a neat and elegant concept that I can hardly imagine that it will not have a marked influence on the design of new machines in the near future.”
And, of course, he was right. The PDP-11, with all its lovely index registers, one of which was a dedicated stack pointer, was only a decade away.
At the very start of the ALGOL project, Dijkstra and Zonneveld were concerned that Wijngaarden would (as was his wont) take undue credit. So the two clean-shaven programmers conspired to remain unshaven until the compiler worked. Only those with a beard could take credit for the compiler. Six weeks later, with the compiler working, Zonneveld shaved, but Dijkstra remained bearded from that point on.
