It Began with Babbage (31 page)

However, there was much more to programming and its methodology than this. At the time Goldstine and von Neumann wrote
Planning and Coding Problems for an Electronic Computing Instrument
, work was already underway in Cambridge in England on the EDSAC. And Maurice Wilkes understood clearly that as soon as the EDSAC was working, the focus of interest must shift to the realm of programming. He understood that even the simplest task demanded of the EDSAC required a nontrivial program of some sort.
²⁴
And so, very early during the EDSAC project, he assembled a group of people interested in the problem of program development. A committee was assembled to create a library of
subroutines
on which users could draw without having to write them from scratch every time they were needed.
²⁵

Thus, it was not enough to create a language for expressing a program in some human-comprehensible term; it was not enough to show how the description should be transformed into code for a real computer. “Higher level” building blocks had to be created to facilitate the ordinary user's task of programming a stored-program computer. The subroutine was such a type of building block.

The idea of the subroutine had actually occurred to John Mauchly even before this time. In January 1947, he presented a paper titled
Preparation of Problems for EDVAC-Type Machines
at the Harvard symposium on digital computing machines organized by Howard Aiken (see
Chapter 8
, Section XVI). In this paper, Mauchly dwelled on a basic decision problem that all computer designers would face: to distinguish between operations that must be built into the machine (hardwired, in present-centered terms) and
those that should be programmed.
²⁶
He made the point that this would depend on the frequency of operations and the ease with which the “nonbuilt” operations could be programmed on a given machine.

He then noted that some operations that are not “built-in” may still occur with sufficient frequency that, although it may not be justified to “build them into” the machine, one should not have to program them
ab initio
every time. Rather, he imagined magnetic tapes that would contain small programs that performed these operations, prepared once and for all, which could then be summoned into use whenever needed by different programmers for their respective programs. Mauchly used the term
subroutines
to signify such frequently used and usable programs. But, he warned, they must be sufficiently flexible to be genuinely general purpose.
²⁷
In fact, half of Mauchly's paper was devoted to the topic of subroutines and how to implement them in a practical way.

That same year, a month after Mauchly's presentation, in his lecture to the London Mathematical Society (see
Chapter 8
, Section VIII), Alan Turing also mentioned, although far more briefly, the necessity of what he called “subsidiary tables”—essentially, subroutines.
²⁸

There is also anecdotal evidence, recalled many years later, that Grace Murray Hopper, who had worked with Aiken on the development of the Harvard Mark I and coauthored a three-part paper on that machine (see
Chapter 5
, Sections V and VI), was aware of the subroutine concept at that time (the mid 1940s). Recollecting her experiences in a keynote address given at a conference on the history of programming languages in June 1978, she spoke of writing subroutines, although they were not called as such, but rather thought of simply as “pieces of code.”
²⁹

Thus the concept of the subroutine was much “in the air” in the mid to late 1940s. The question of who “invented” the subroutine, like the larger question of who “invented” the stored-program computer, is highly problematic, for it depends on what we mean by
invention
.

If we were to signify by “invention” the
conceptualization
of an idea, then Mauchly should probably have the credit. If Hopper's recollection was correct, then the
term
“subroutine” existed as early as 1944. Mauchly, however, clearly conceived the notion of subroutines existing as entities (on magnetic tape) independent of the physical computer but summoned to use on and by the physical computer when required. Subroutines are programs that would become building blocks in the creation of larger programs. Here was an idea of the
autonomy
of a computer program—an artifact at once apart from the physical computer but with a usefulness that depended on the physical computer—a realization of the liminality of programs (see Prologue, Section III).

On the other hand, if invention in the world of useful artifacts entails not just the conception or ideation but the
construction
of the first artifacts that carry the idea into a complete, demonstrable form, then it would seem that David Wheeler in the Cambridge University Mathematical Laboratory was the “real” inventor of the subroutine as a class of liminal computational artifacts.

Wheeler, as a student of Trinity College, Cambridge, read for the mathematics tripos and obtained his degree in 1948.
³⁰
He joined the EDSAC project as a research student immediately after graduation.
³¹
When the time came for the EDSAC group to think about how the machine should be used, Wilkes suggested to Wheeler that he should “imagine” that the machine was completed and investigate how it should be used.
³²

This kind of “imagining” could never have happened in the days when an artifact's conceptual design existed entirely in the mind of a single creator, and the creator made the artifact based on his private mental concept, had computer designs still been at the “craft stage” (see
Chapter 2
, Section VIII).
³³
Wheeler's “imagining” was possible because the EDSAC existed, if not materially, then in abstract form as a design that was shared by members of the EDSAC team. In present-centered language, this design was the EDSAC architecture—a liminal artifact, abstract on the one hand, yet its physical realization sufficiently well understood that Wheeler could “imagine” the workings of the physical computer as if it had been completed and in use.

Wheeler's response was twofold. The first was the development and use of subroutines and the creation of a subroutine library. At the Cambridge conference in June 1949, Wheeler presented a paper titled
Planning the Use of a Paper Library
and began by noting that “different problems have many parts in common.”
³⁴
He went on to say that these “parts” may be prepared “once and for all” but—echoing Mauchly—they must be sufficiently flexible so that they can be adapted to differing problem contexts, thus the prospect of a library of subroutines.
³⁵

Then, after defining “programme” and “routine,” he explained that a subroutine “is the coded form of an element in a routine (e.g., square root, input and binary decimal conversion, etc.)” (see Section I, this chapter). He went on to state the advantages of a subroutine and a library of such entities: simplification of the task of preparing problems for computation, facilitating the understanding of routines by other users, and, if the subroutines are correct then the chances of errors in a routine as a whole are considerably reduced. These advantages originate in the fact that subroutines are larger functional “units” in a program than the order codes themselves.

Wheeler did not just conceive an idea, however; he actually built subroutines and demonstrated how they could be used. He identified certain problems engendered by the subroutine concept and proposed solutions to them.

One of the problems was that instructions (orders) within a subroutine refer to memory locations (addresses) of the “data” (
operands
, as they were being called by 1951
³⁶
) relevant to that subroutine only. This meant that the subroutine would have to be placed in a fixed set of locations in the EDSAC memory. It would always have to be placed in that same set of locations. Wheeler proposed, instead, a more flexible solution that allowed for the “relocatability” of a subroutine, which involved putting the subroutine on the tape in such a way that it deferred fixing its location in memory until when it would be input into the machine. The latter task, in turn, would necessitate a “special” subroutine.
³⁷

Another problem was to make a subroutine for a particular kind of task sufficiently general by using parameters that could be set to specific values for each instance of the subroutine's use. These parameters could be “external”—set to values at the beginning of the subroutine's use, which would remain fixed throughout the execution of the subroutine—or “internal,” meaning that their values could vary during the solution of the problem.
³⁸

A third problem was where and how a subroutine should be invoked for execution. Here, Wheeler distinguished between two types of subroutines. In the first, and simpler, situation, control is transferred to the beginning order of the subroutine and, when the latter ends, execution control simply flows to the order located immediately after the subroutine in memory. Wheeler termed such a subroutine “open.”
³⁹
But, this was not very flexible, for if the subroutine was required to be used at several points in the main program, as many copies of the subroutine would have to be inserted in the appropriate places. Instead, Wheeler conceived the
closed
subroutine, which would be called from some location within a program and, on its execution, control would be transferred to the point in the “calling” program immediately after the location from when the subroutine was called.
⁴⁰

So, a closed subroutine can be placed anywhere in the EDSAC memory,
outside
the main program. When it was needed to be called from a point in the calling (main) program—say, from address
n
—control “jumps” to the first instruction in the subroutine. At the end of the subroutine's execution, control “jumps back” to address
n
+ 1. This mechanism came to be called the
Wheeler jump
(
Figure 9.2
).

Wheeler's other major invention was as consequential as that of the subroutine. To understand the nature of this second contribution, let us follow his own words:

It is inconvenient to write our orders in their binary form, and so we shall write them in the following form. The first five binary digits [within an order, called the
function digits
, which specify the function or operation to be performed] will be represented by the capital letter that represents these digits on the keyboard perforator. The next 11 binary digits [signifying the operand in memory] will be represented by an integer n in the normal decimal form. This integer is the address referred to in the order.… The last digit [signifying the length of the operand, “long” (binary 1) or “short” (binary 0)] will be represented by D if … [long] and if … [short] it will be represented by F.
⁴¹

Thus, an instruction that in binary form is 11100 0 0000001110 1 would be written as
A 14 D
. Wheeler was using a
symbolic
notation to specify an instruction. A fragment of a program would look like that presented in
Table 9.1
.
⁴²

We have seen that the flow diagram invented by Goldstine and von Neumann was also a symbolic system, as was the notation von Neumann used to describe his sorting program. However, Wheeler's symbolism was more consequential. It was more than a notation. We realize this when he writes about his “initial orders”:

TABLE
9.1 A Fragment of an Assembly Language Program for the EDSAC