This chapter is from the book
This chapter is from the book
This chapter is from the book
The ARRA: 1952–1955
Wijngaarden hired Dijkstra to program the MC’s new ARRA computer. The problem was that the ARRA didn’t work. Five years before, Wijngaarden had traveled to Harvard and had seen Aiken’s Mark I and its successors. Impressed, Wijngaarden hired some young engineers to build a similar but much smaller machine: the ARRA.
The ARRA was designed to be a stored-program electromechanical beast. It had a drum memory, 1,200 relays, and some vacuum tube flip-flops for registers. The relays had to be cleaned regularly, but the contacts degraded so rapidly that the switching time was undependable, making the machine unreliable. After four years of development and constant repair, the poor machine was apparently only good for generating random numbers.
That was not a joke. They had written a demonstration program that simulated the rolling of a 13-dimensional cubic die.6 At one point, a minister of government came in to see this demo. They fearfully turned the machine on and, for once, it started printing proper random numbers. It worked!—for a moment. Then it unexpectedly halted. Wijngaarden, thinking on his feet, explained to the minister: “This is a highly remarkable situation: The cube is balancing on one of its corners and does not know which way to fall. If you push this button, you will give the cube a little push and the ARRA will continue its computation.” The minister pushed the button, and the machine once again started printing random numbers. The minister replied: “That is very interesting,” and left shortly thereafter.
The machine never worked again.
A frustrated Wijngaarden recruited Gerrit Blaauw, who had just gotten his Ph.D. at Harvard while working with Aiken on the Harvard Mark IV. Blaauw joined the team and in very short order convinced them that their machine had no hope of success, and that they needed to start from scratch with electronics and not electromechanical relays.
So the team started in on the design of the ARRA. Well, actually, it was the ARRA 2, but they didn’t want to advertise that there had ever been an ARRA 1.
So they just called the new machine the ARRA.
)
Being the “programmer,” Dijkstra would propose an instruction set to the hardware guys. They, in turn, would assess whether that instruction set was practical to build. They’d make amendments and toss them back to Dijkstra. This iteration continued until they were all ready to “sign in blood.” And then the hardware guys built the hardware, and Dijkstra started working on the programming manual and writing the IO primitives.
This division of labor established the idea that the hardware was a black box that executed the software, and the software was independent of the design of the hardware. This was an important step in computer architecture and a very early example of dependency inversion. The hardware depended on the needs of the software, rather than the software being subordinate to the dictates of the hardware.
They managed to complete the new machine 13 months later, in 1953. What’s more, it worked—and they put it to work 24 hours a day calculating things like wind patterns, water movements, and the behavior of airplane wings. The machine completely replaced the team of women “computers” who had previously been doing these calculations on desk calculators. Those women became the programmers of the new machine.
At some point, they hooked a loudspeaker up to one of the registers and could listen to the rhythmic sounds as it operated. This was a good debugging tool because you could hear when it was executing properly and when it got caught in a loop.
The ARRA was designed as a binary machine at a time when most computers were using decimal (BCD). The electronics were vacuum tubes. It had two working registers, had 1,024 30-bit words of drum memory, and could execute ∽40 instructions per second. The drum spun at 50 revs per second. The primary input device was five-channel paper tape. Output was typically sent to an automatic typewriter.
The instruction set that Dijkstra designed for the ARRA 2 should provide some insight into what he and his contemporaries thought a computer should be able to do: It was quite sparse, and focused much more on arithmetic than data manipulation. Later computers would reverse that decision!
Instructions in the ARRA 2 were 15 bits wide, so two instructions would fit into a 30-bit word. Those two instructions were referred to as a and b. So the machine could hold 2,048 instructions. The first five bits in an instruction were the operation code, and the last ten were the memory address (or an immediate value).
The two registers were named A and S. They were independently manipulated, but could also be used as a double-precision 60-bit number.
There were 24 instructions. Notice the lack of IO and indirect addressing. Notice also that Dijkstra used decimal to denote the operation codes. At the time, there was no thought of octal or hexadecimal:
0/n replace (A) with (A)+(n) 1/n replace (A) with (A)-(n) 2/n replace (A) with (n) 3/n replace (A) with -(n) 4/n replace (n) with (A) 5/n replace (n) by -(A) 6/n conditional control move to na 7/n control move to after na 8/n replace (S) with (s)+(n) 9/n replace (S) with (S)-(n) 10/n replace (S) with (n) 11/n replace (S) with -(n) 12/n replace (n) with (S) 13/n replace (n) with -(S) 14/n conditional control move to nb 15/n control move to nb 16/n replace [AS] with [n].[s]+[A] 17/n replace [AS] with -[n].[S]+[A] 18/n replace [AS] with [n].[S] 19/n replace [AS] with - [n].[s] 20/n divide [AS] by [n]:, place quotient in S, remainder in A 21/n divide [AS] by -[n]:, place quotient in S, remainder in A 22/n shift A->S, i.e. replace [AS] with [A].2^(29-n) 23/n shift S->A, i.e. replace [SA] with [S].2^(30-n) 24/n communication assignment
The two conditional control moves (jumps) executed only if the result of the last arithmetic operation was positive. The ARRA was a one’s complement machine, which means there were two representations of zero, one positive and the other negative. So testing for zero by subtracting was perilous.
Notice that if you want to jump to instruction a or b, you have to use a different jump instruction. That must have been hellish to deal with when you inserted an instruction into your program.
The drum memory was arranged into 64 channels containing 16 words each. I infer that each channel corresponded to a track on the drum. I also infer that there were 64 read heads, and that each read head was routed to the electronics through relays. Those relays took from 20 ms to 40 ms to open or close. So the efficiency-minded programmer had to take care not to jump around between tracks.
What’s more, it appears that the electronics for reading and writing the drum were able to read from two tracks at a time: one for instructions and another for data. This allowed the programmer to aggregate instructions on one track and data on another without having to change the state of the relays.
Just to add one extra complication, it appears that the actual tracks on the drum could only hold eight words around the drum circumference, but that each read/write head was actually a dual head that could read and write one or the other of two adjacent tracks. Thus, reading an entire 16-word channel required at least two revolutions of the drum.
Imagine having all that to think about while you are trying to write an interesting mathematical program.
Notice that the instruction set does not allow for indirect addressing. Either Dijkstra had not yet realized the importance of pointers, or the hardware designers could not easily implement indirection. So any indirect or indexed access had to be accomplished by modifying the addresses within existing instructions.
This was also the strategy for subroutines. The instruction set had no “call” instruction, nor any way to remember return addresses. So it was the programmers’ job to store the appropriate jump instruction in the last instruction of a subroutine, before jumping to that subroutine.
The primitive nature of these machines and instruction sets likely had a dual effect upon Dijkstra. First, being so swamped by all the hideous detail and the deeply constrained environment likely precluded any serious consideration of computer science. But second, it also likely instilled within him the strong desire to shed all such detail and drive toward abstraction. As we shall see, that’s exactly the path that Dijkstra took.
Indeed, there are hints of this battle between detail and abstract thinking in Dijkstra’s “Functionele Beschrijving Van De Arra” (“Functional Description of the ARRA”) from 1953. In that write-up, Dijkstra goes to great lengths to justify and explain the benefits of callable subroutines as opposed to the kind of “open subroutines” (code duplication) that Hopper had been using in the Mark I.
In his description of how to do a subroutine call, he says that “it would be nice to have control run through the same series of commands” instead of duplicating those commands over and over within the program, which “is quite bad [and] is wasteful of memory space.” But then he turns around and complains that jumping to a subroutine in that fashion will cause a great deal of drum-switching time, adding a full revolution of the drum to each call and each return.
Coming to terms with this dichotomy is the story, and the legacy, of Edsger Dijkstra.
