Subroutines

Posted 02 Jan 2024

Earliest idea of creating subroutines.


Note: in line with my original idea, I’m going to post more short bits of information, to document the things I learned, along with the source. I wanted to use this blog partly as a research notebook, but the question of the first Operating System needed a long-form post.


The First Reference?

In 1947, Herman Goldstine and John von Neumann wrote a book entitled, “Planning and Coding of Problems for an Electronic Computing Instrument, Pt 2, Vol. 3” As you can see it was more a set of books than a single book. (I’ve seen various dates for this, but the title page has 1947 at the bottom, and a notation for IAS ECP reports 4, 8, and 11, with a date range of 1946-1957.)

Section 12 is titled “Combining Routines”. In this, they discuss taking various algorithms and computations, and combining them into a final program.

12.3 We call the coded sequence of a problem a routine, and one which is formed with the purpose of possible substitution into other routines, a subroutine. As mentioned above, we envisage that a properly organized automatic, high speed establishment will include an extensive collection of such subroutines, of lengths ranging from about 15-20 words upwards. I.e. a “library” of records in the form of the external memory medium, presumably magnetic wire or tape. The character of the problems which can thus be disposed of in advance by means of such subroutines will vary over a very wide spectrum – indeed a much wider one than is now generally appreciated. Some instances of this will appear in the subsequent Chapters 13 and 14. The discussions in those chapters will, in particular, give a more specific idea of what the possibilities are and what aims possess, in our opinion, the proper proportions.

Of note is the term “substitution”. I wonder if that means the subroutine would be copied into the program at the point it is needed (perhaps several times?), or if some more complex mechanism was intended.

Since they are careful to define these terms, routine and subroutine, I suspect this is a new idea. Given von Neumann’s habit of neglecting to credit other people’s work, it’s possible that this is derived from an earlier paper, or perhaps just a conversation. Von Neumman’s main contribution seems to be writing down and publicizing the ideas and work of others, which we might otherwise not have.

As usual, corrections are welcome. If you know of an earlier use, or details on exactly how these subroutines were used, I’d really like to know.


Follow Up

I found the answer to my implementation question. It’s in the first programming book ever written, “The Preparation of Programs for an Electronic Digital Computer”, by Maurice Wilkes, David Wheeler, and Stanley Gill. See here for more info.

The book divides subroutines into two types, which they call “closed” and “open”. The open type is a list of commands (“orders”) which implement the function. This is simply inserted into the main program where needed, during the preparation phase (think “compiler”, though those weren’t invented yet).

The closed type requires some extra work. A specific set of instruction codes are added to the main program, at the point it wishes to use the subroutine. This sets up a return address, by actually modifying the subroutine’s last instruction so it branches back to the next instruction of the main program.