Skip to content

David Wheeler and the Closed Subroutine

Abstract

David Wheeler (1927–2004) spent almost his whole working life in one building, the Cambridge Mathematical Laboratory, later the Computer Laboratory. As a research student on EDSAC in 1949 he wrote the Initial Orders, the loader that let programs be written in letters and decimal numbers, and devised the “Wheeler jump” by which a closed subroutine returned to its caller. His 1951 PhD is usually counted as the first doctorate in computer science. He helped design the programming systems of the ILLIAC at Illinois, led Cambridge’s Titan, worked on the CAP computer and the Cambridge Ring, and in his late sixties published two pieces of work still in daily use: the Burrows–Wheeler transform, inside bzip2 and DNA sequence aligners, and the TEA block cipher.

EDSAC Team May 1949
Members of the Cambridge Mathematical Laboratory in May 1949, the month EDSAC first ran; Wheeler is among them. Image: Computer Laboratory, University of Cambridge, CC BY 2.0, via Wikimedia Commons.

Birmingham to Cambridge

David John Wheeler was born on 9 February 1927 in Birmingham and went up to Trinity College, Cambridge, to read mathematics. In 1947, still an undergraduate, he started helping with the computer that Maurice Wilkes was building at the Mathematical Laboratory, and after his BA in 1948 he stayed on there as a research student. EDSAC ran its first programs on 6 May 1949.

Initial Orders

Someone had to decide how a program on paper tape got into the machine, and the job fell to Wheeler. His Initial Orders were a short program wired permanently onto a bank of telephone uniselector switches and copied into memory when the machine started. They read the tape, translated instructions written as a letter for the operation and a decimal address into binary, and placed them in store. The version in use in 1949 took 31 words; a second version, Initial Orders 2, took 41 and could adjust addresses so that a block of code ran wherever it was loaded. The University of Cambridge describes Wheeler’s work as “the first computer program ever to be stored in a computer’s working memory”. The loader was in effect an assembler and relocating loader; whether it was the first assembler depends on the definition (see Kathleen Booth and the First Assembler). Wheeler described the scheme in “Programme Organization and Initial Orders for the EDSAC”, published in the Proceedings of the Royal Society in August 1950.

The Wheeler Jump

The second problem was reuse. Square roots, printing a number and integrating a differential equation came up in nearly every program, and the laboratory wanted to write each once. A piece of code copied into each program where it was needed was an open subroutine. Wheeler, Wilkes and Stanley Gill developed the closed subroutine, a single copy that could be called from anywhere and would return to the caller.

EDSAC had no instruction for this. Wheeler’s answer was for the calling program to load its own address into the accumulator and jump to the subroutine. The subroutine’s first instructions used that address to build a jump back and plant it at the subroutine’s own exit. The routine then ran and left through the instruction it had just written. The technique, which modifies its own code, became known as the Wheeler jump; later machines built the return address into a call instruction or a stack, but the call and return it implemented are the ones every programmer uses.

The subroutines went into a library of punched tapes in a filing cabinet, each with a written specification. In 1951 Wilkes, Wheeler and Gill published the library and the method as The Preparation of Programs for an Electronic Digital Computer, the first textbook on programming. The same year Wheeler received his PhD for a thesis on automatic computing with EDSAC and was elected a fellow of Trinity.

Info

First PhD in computer science? Wheeler’s 1951 Cambridge doctorate is the usual answer, and it was formally a PhD in mathematics; the subject did not yet have a name. The first dissertation in a degree programme named computer science is a different question: Richard Wexelblat’s PhD at the University of Pennsylvania’s Moore School, awarded in December 1965 with the first diploma to say “computer science”, is the one usually cited for that. Two others finished earlier, at commencements on the same day, 7 June 1965: Sister Mary Kenneth Keller with a PhD from the University of Wisconsin’s computer sciences department, and Irving Tang with a DSc in applied mathematics and computer science from Washington University in St. Louis.

In 1950 Wheeler also ran a calculation for the statistician Ronald Fisher on the frequency of a gene in a population, one of the first uses of a computer in biology.

Illinois

From 1951 to 1953 Wheeler was at the University of Illinois, where he helped design the programming systems for the ORDVAC and the ILLIAC, two machines built there on the pattern of the IAS computer. The Computer History Museum credited him with contributions to the ILLIAC’s architecture. Back in Cambridge he designed extensions to EDSAC, among them an index register, and the programming system of EDSAC 2, which replaced EDSAC in 1958.

Titan, CAP and the Ring

For Cambridge’s third machine, Titan, built with Ferranti as the prototype of the Atlas 2 and in service from 1964, the project ran under Wheeler’s lead, while Roger Needham, David Hartley and others wrote its time-sharing supervisor. He was responsible for the implementation of the CAP computer of the 1970s, a capability machine in which every reference to memory went through an unforgeable token, and worked with Andy Hopper and Needham on the Cambridge Ring, the laboratory’s slotted-ring local network. On sabbaticals he worked at the University of California and the University of Sydney, and he consulted for Bell Labs and for DEC’s research laboratory in Palo Alto.

On 24 August 1957 he married Joyce Margaret Blackler, an astrophysics research student who had used EDSAC for her own calculations since 1955. He became a fellow of Darwin College in 1964 and was made professor of computer science in the laboratory where he had started as a student.

Burrows–Wheeler

In 1983 Wheeler found a way to rearrange a block of text so that it compresses better. Write down every rotation of the block, sort the rotations, and keep only the last character of each, plus the position of the original. Characters that come before the same context end up next to each other, so the output has long runs of repeated letters, and the transformation can be reversed exactly. He did not publish it. Eleven years later Michael Burrows, then at DEC’s Systems Research Center, worked it into a complete compressor with him, and DEC released “A Block-sorting Lossless Data Compression Algorithm” as technical report 124 on 10 May 1994.

The Burrows–Wheeler transform became the core of Julian Seward’s bzip2 in 1996 (see Data Compression). Its second career came in genomics: the FM-index built on it lets programs such as Bowtie and BWA search a human genome for millions of short DNA reads on an ordinary computer.

TEA

Also in 1994 Wheeler and Needham presented the Tiny Encryption Algorithm at the Fast Software Encryption workshop in Leuven. TEA fitted in a few lines of C: a 64-bit block, a 128-bit key and 64 rounds of additions, shifts and exclusive-ors, with no lookup tables. Its simplicity had a cost. Every key has equivalent keys, so the effective key length is 126 bits, and when Microsoft used TEA as a hash in the original Xbox, that weakness helped hackers break its boot security. Wheeler and Needham answered with XTEA and then XXTEA (1998). Wheeler also designed the WAKE stream cipher.

Indirection

Wheeler’s best-known saying reached print through Butler Lampson, who credited him in his 1992 Turing Award lecture: “All problems in computer science can be solved by another level of indirection.” It is now called the fundamental theorem of software engineering (see Eponymous Laws). Another line attributed to him, “Compatibility means deliberately repeating other people’s mistakes”, circulates without a dated source.

Honours and Death

Wheeler was elected a fellow of the British Computer Society in 1970 and of the Royal Society in 1981, one of the first computer scientists in it. He received the IEEE Computer Society’s Computer Pioneer Award in 1985, became an ACM fellow in 1994 and a Computer History Museum fellow in October 2003. He formally retired in 1994 and kept coming to the laboratory. On 13 December 2004 he had a heart attack as he arrived there on his bicycle, and died. At the memorial in April 2005 the speakers ran from EDSAC and Titan through networking, programming languages, compression and security, and Wilkes, then 91, gave the closing remarks. The laboratory holds an annual Wheeler Lecture in his name.

📚 Sources