Early Calls

Nowadays, the papers write about viruses, lawsuits and bugs. But imagine, while hammering at the keys or struggling to write up your thesis, that your research could inspire coverage such as this:

The brain will carry out mathematical research. It may make sensational discoveries in engineering, astronomy, and atomic physics. It may even solve economic and philosophical problems too complicated for the human mind. There are millions of vital questions we wish to put to it.

I thought I'd start my Dobbs blogging by posting about a historic book I saw recently. Oxford's Oxfam charity bookshop maintains a window display of interesting and "collectable" second-hand books. Last week, between the brightly-coloured fishing boats and Galilean sun adorning a children's bible history entitled Μέ τή σημαία τῆς Ἀγάπης and a wobbly purple beast named Dong co ma świecący nos — The Dong with the luminous nose in Polish — I spotted a thin cream-covered hardback with by it the sign:

For non-British readers, that's the price of 17 Big Macs, 5 Da Vinci Codes, or £10 more than one of those huge great Wiley tomes about PHP or Perl. Markets are supposed to go to equilibrium for fair prices to emerge, but there can't be many Preparation of Programs for an Electronic Digital Computer in circulation, so how on earth was this price decided?

Anyway, I didn't buy the book, but I thought I'd wander down to the Bodleian and look at the copy from the stacks. It's actually by Wilkes, David Wheeler, and Stanley Gill, and is subtitled With special reference to the EDSAC and the use of a library of subroutines. A preface by Douglas Hartree begins:

To the potential user of an automatic digital calculating machine, the successful design and construction of the machine itself is only a first step, though certainly an important one. In order that the machine should in practice be useful to him in the calculations he may desire to carry out with its aid, the provision of an adequate organization for using the machine is as important as the machine itself.

That "organization" is the subroutine, which, a Cambridge obituary tells me, was invented by David Wheeler. And that's the crux of the book. As Hartree explains:

One form of such an organization is based on a library of subroutines for carrying out standard processes, and facilities for using it. Provision of such a library has two important effects. First, it relieves the user of the machine of the greater part of the work of programming calculations in detail; a library subroutine can be incorporated as a unit in his program, without it being necessary for him to work through the sequence of operations by which the calculation carried out by the subroutine is effected; and it is quite possible for eighty percent of a complete program to be carried out by the use of such library subroutines. And secondly, in making up a program, use of library subroutines which have been thoroughly checked limits the possibilities of mistakes in programming, and correspondingly reduces the expenditure of time, both of the machine and of the programmer, in diagnosing and correcting mistakes. In order that such a library of subroutines should be practically useful, it seems desirable, if not indeed necessary, that the subroutines should be drawn up in a form which provide a certain amount of flexibility in their use, so that slight variations can be made in them in order to suit the contexts in which they may be used in particular applications.

And, being 1951, EDSAC's memory had 1024 17-bit words, only half of which were working when the book was written. Evaluating e^x, say timing results from the library spec, took 0.93 seconds. A "computer" might be a person; the second paragraph of Chapter 1 warns:

A human computer is capable of reasonable extension of his instructions when faced with a situation which has not been fully envisaged in advance, and he will have past experience to guide him. This is not the case with a machine.

Programs were input on five-hole paper tape, using a simple assembly code. Here, from page 6, is an example that calculates x+y+xy, where x and y are in locations 50 and 51. The result goes into location 52:

    A 50 F   Add contents of location 50 to accumulator. 
    A 51 F   Add contents of location 51 to accumulator. 
    H 50 F   Copy accumulator to multiplier register. 
    V 51 F   Multiply contents of location 51 by multiplier register, 
             add result to accumulator. 
    T 52 D   Transfer accumulator to location 52; 
             clear accumulator. 

The program that read tapes and translated such assembly code was called "initial orders" — and when did that particular name drop out of fashion? It occupies a 1½-page listing in Appendix B, only 40 instructions.

What about subroutines? A key point is that subroutines were prepared and stored so that they could be used in many different programs. Physically, this meant storing their source code on separate paper tapes, as this charming passage from Chapter 6 explains:

Subroutines in the library are punched on colored tape so that they can easily be distinguished from program tapes, which should be white. Several copies of each subroutine are provided and when not in use each copy is rolled in a small cardboard box. The boxes are filed in serial order in a steel cabinet. The master copy of each subroutine is kept under lock and key and is used only when all existing copies are damaged. The master tape is then used to prepare further copies by means of a duplicator. All copies must be checked against the master, by means of a comparator, before being put into the library for general use.

This meant that a subroutine had to work no matter where the assembler loaded it into memory, posing the problem of how to code location-independent jumps. Nowadsys, we'd write named labels into our assembly code and leave the assembler to resolve them. The examples shown by Wilkes, Wheeler and Gill aren't quite there yet. Their assembler, in effect, provided a single reusable label. You assigned to this by punching the assembly pseudo-instruction G K onto your tape. When the assembler read the G K from the tape, it stored the location of the next instruction in location 42. If you then punched the special symbol θ after an instruction, the assembler would add it to the contents of location 42 when building the instruction. Here's one of the authors' examples, which replaces the number in location 0 by its absolute value:

    G    K   Pseudo-code: makes the assembler store the 
             address of the S F below in location 42. 
             The 3 θ below will therefore point beyond 
             this, at the T 1 F instruction. 
    S    F   Subtract contents of location 0 from accumulator. 
    G  3 θ   Jump to T 1 F if accumulator is negative. 
    T    F   Transfer accumulator to location 0; 
             clear accumulator. 
    T  1 F   Transfer accumulator to location 1; 
             clear accumulator. 

If that's how subroutines were written, how did you call them? Using self-modifying code. Suppose the instruction at location m+1 will jump to the subroutine which starts at location n. Then at location m, you place an instruction that copies location m — i.e. itself — into the accumulator. The first part of the subroutine picks this up and massages it into an instruction that jumps to m+2, and then copies that instruction to the end of the subroutine. This mechanism, I read from tributes to Wheeler, was known as the "Wheeler jump". Here's an example:

                       The code below calls the subroutine
                       that starts at n.
m:     A  m  F         Add contents of location m into accumulator. This is the
                       current instruction, A m F.
m+1:   G  n  F         Goto location n if accumulator negative.
                       It will be, because of how A m F is represented, so
                       this enters the subroutine at n.

                       The code below is the subroutine.
       G     K
n:     A  3  F         Add 3 to accumulator. This contains A m F;
                       because of how instructions are represented, the
                       add converts it into E m+2, "goto m+2 if
                       accumulator non-negative".
n+1:   T p+2 θ         Transfer this goto instruction to location n+p+2;
                       clear accumulator.
n+2:                   First instruction of subroutine proper.
...        
n+p+1:                 Final instruction of subroutine proper.
n+p+2: Z     F         Becomes the goto.

Now, here's a little bit of local and national business history. Inside the Boodleian copy of The Preparation of Programs for an Electronic Digital Computer is a stamp declaring that until 1972, it belonged to the Pressed Steel Company. Cowley was once famous for its car industry, which began with bicycle manufacturer William Morris (later Lord Nuffield) producing the first Morris Oxford in 1913; and Pressed Steel, says The life & times of a car factory at Cowley..., was set up in 1926 as a joint Oxford-American venture to manufacture all-steel car bodies. By the 1960s, they had become Britain's largest independent body supplier. Were Pressed Steel experimenting with computer-aided design, perhaps on a Lyons Leo?

Pressed Steel aside, I wouldn't have thought there'd be many sales for such a specialised book. But in his Memoirs of a Computer Pioneer, Wilkes describes how a preliminary copy was shown to "a small publishing company — Addison-Wesley Press, Inc. — in Cambridge, Massachusetts". Addison-Wesley agreed to publish, under a royalty agreement designed to reduce their loss if no-one bought any copies. As it happened, they sold, 1000 copies within fifteen months of the book's publication in July 1951. Wilkes writes:

I like to think that its success contributed in a small way to the growth of Addison-Wesley from being a very small concern to its present large size.

But if Addison-Wesley were bold, Wilkes, Wheeler and Gill got the excitement. You may have read Douglas Hofstadter's book Gödel, Escher, Bach: an Eternal Golden Braid. In Chapter 10, Levels of Description, and Computer Systems, Hofstadter describes a hierarchy of levels which culminates in intelligent programs, and which begins: transistors; flip-flops and gates; registers and data paths; machine instructions; compiler or interpreter; Lisp; embedded pattern-matcher. Each level above "machine instructions" is a software virtual machine — a new level of description — implemented by defining appropriate subroutines in terms of those provided by the level below. Hofstadter believes that to reach true intelligence, many levels will be needed between "embedded pattern-matcher" and "intelligent program", perhaps even several dozen. But the point is that if we climb enough levels, we shall achieve intelligence. Surely Wilkes, Wheeler and Gill felt the same excitement: we can make the machine do anything at all, if we only pile the subroutines sufficiently high.

And they got the glory, spread thick down there at the point of the cone. In June 1949, reported The Star:

On the top floor of a rather drab building in a narrow Cambridge back street is an apparatus which seems to consist chiefly of a vast number of valves set in grey painted racks. ... this weird array of wires and valves is a "mechanical brain." It has just been completed and it is the most advanced in the world. It is probably the major scientific marvel of 1949 and although until now we have lagged behind America in mechanical brains this one puts us streets ahead ...

This is how it works. First Mr Wilkes fed a strip of paper punched with holes into a "ticker-tape" machine. As the paper ticked through ... miniature television screens showed a row of green blobs ... then almost instantaneously a teleprinter nearby began to print rows of figures. That was all. There were no dramatic sparks, no dramatic flashes ...