Routines of Substitution (Review)
Early post-war computing can often seem alien as terminology mixed metaphors and the pioneers brought their own distinct toolsets to the field. Thus, it seems fitting that a powerful influence on computing design would come from a “Martian”: John von Neumann. During the war, von Neumann surveyed computing capabilities within the United States, which introduced him to the ENIAC and the Harvard Mark I. Von Neumann joined as a consultant to the EDVAC project, a successor to the ENIAC, where he and the team worked out the concept of a stored-program computer.
Mark Priestley’s Routines of Substitution: John von Neumann’s Work on Software Development, 1945-1948 is a technical history of von Neumann’s programming work, with special focus on the “meshing” algorithm he wrote as part of a merge sort, his diagrammatic programming language, and the integration and execution of subroutines within a program. While the “Von Neumann Architecture,” as documented in First Draft of a Report on the EDVAC, is the most famous outcome of his work at this time, this study illuminates the invention process and the practical aspects of implementation.
Routines of Substitution book cover
Priestley, Mark. 2018. Routines of Substitution: John von Neumann’s Work on Software Development, 1945-1948. SpringerBriefs in History of Computing. https://doi.org/10.1007/978-3-319-91671-2.
The book begins with von Neumann’s first program for the EDVAC, a program for sorting records. (Records being a modern term; metaphors at this point included the key field called the star and the other fields planets.) For 1945, sorting was an unexpected use case for a digital computer. The expectation, as Knuth jokes in (Knuth 1970), was a partial differential equation. Priestley tracks the impetus to an unspecified statistical problem brought forward by Samuel Wilks (pg 14) in April 1945. Solving this statistical problem required sorting. Although delegating sorting to IBM card sorting machines was possible, the round trip times would kill efficiency. Instead, sorting would be done within the EDVAC’s memory. Although we do not have documents describing a complete sorting implementation, we do have documentation for the “meshing” or merging subroutine for a merge sort as worked out by Von Neumann.
Meshing: Given two ordered sequences, produce a third ordered sequence containing all elements of the first two sequences.
Priestely describes the interplay between the EDVAC orders (machine instructions) and von Neumann’s algorithm. In contrast to Knuth’s write-up (Knuth 1970), Priestely uses von Neumann’s notation, rather than transcribing it to an assembly language form. Because of this, Priestely is able to show the greater use of self-modifying code and the principal role of substitution within programs. The von Neumann architecture is principally noted as mixing instructions and data. The EDVAC orders can leave out conditional jump instructions because they re-write the destinations of unconditional jumps. Although more difficult for a modern reader to follow, the lack of translation yields greater historical insight.
The second half of the book focuses on von Neumann’s proposed software development process and the role of subroutines. One of the principal technical tasks in crafting a program was setting or computing all the necessary address locations within the code, since there were no relative addressing modes nor was there a stack. In von Neumann’s process, the source code is translated into machine instructions very early, which forces address specification to be made every time a program is run. In contrast, the EDSAC team, who was also building a “von Neumman”-style computer but translated symbolic instructions to machine instructions later in the process, developed an automatic and less-error prone approach. The book ends with a discussion of the limited role of subroutines in von Neumman’s program design and how it may reflect how the production of mathematical tables were organized.
Routines of Substitution is a specialized work and best understood with a background in computer design. It sheds light on some of the earliest formal thinking about programming and how some of that thinking did not pan out. While challenging, it is also rewarding to study. Recommended.
Further Reading
Knuth, Donald. 1970. “Von Neumann’s First Computer Program.” ACM Computing Surveys 2 (4): 247–60. https://doi.org/10.1145/356580.356581.
Wilkes, M. V. 1951. The Preparation of Programs for an Electronic Digital Computer, with Special Reference to the EDSAC and the Use of a Library of Subroutines. Cambridge, Mass.: Addison-Wesley Press.