November 14, 2008: A better RAM-less computer.
Ignore everything I said about the "simple" calculating machine described in the previous post. It was meant to support non-interactive batch processing. It is very easy to build an interactive stack based processor, but interactivity limits the machine to human capabilities. The key point I missed was that batch processing can be transformed into interactive processing with the addition of a second tape. The first tape has the desired instructions. The second tape holds the scratch stack. Numbers and operations are copied one at a time from the instruction tape to the scratch tape, emulating interactivity. So all that nonsense about copying out of order instructions was completely unessessary.
One of the great sci-fi authors (Clarke?) once classified various stages of catastrophe, in terms of population loss. Basically, a civilization could survive losing up to 90% of its population without significant technological or cultural regression. More than 98% and technology would take a back seat to the business of survival. Clearly, this is flawed. The global literacy rate is only 82%. Lose that segment of population, and just about all technology and history is gone. Maybe he meant from the population at random.
But could you rebuild? This document was prepared on a computer, in a text editor. As a programmer, I can write an editor. I could write the programming language for the editor. As a computer engineer, I am familiar with various computer architectures. Register, stack, von Neumann, Harvard, RISC, CISC. Familiar enough that I could lay out most of the boolean gates to make the basic components of a computer. As an electrical engineer, I can take this one step further and lay out the silicon required for each gate, maybe even produce the lithography stencils for a given quality of silicon. Then things start to get a little hazy. Refining and doping the silicon crystal; temperatures, pressures, molar concentrations. The specifics of an integrated circuit foundry. Eventually the details of your domain become somebody else's business, and you would be lost without them.
Okay, how about something not based on silicon? The first computers were made in Germany out of telephone relays. Painfully slow, a billion times slower than silicon. This has not stopped people from building modern relay computers.
Any relay based computer should be as minimal as possible. Well, any computer regardless of construction should be as simple as possible, but I've been reading a lot of Chuck Moore lately. Early computers were notorious for their complexity, largely caused by the decimal numbering system. ENIAC required ten wires for each digit. Binary computers require 3.32 wires for the same range. Technically, ENIAC needed (on average) 20 wires per digit, as frequent failures mandated redundant systems.
Even RISC is too heavy. I will not advocate the practical use of OISC, but a subset of RISC which I will call BISC, for bitwise instruction set computer. Bitwise XOR, NOT, AND, OR, shift left and shift right. Comparison, branching. That is everything. This subset can emulate higher level commands. For example, there would not be a true ALU. Addition requires XOR (sum), AND (carry), left shift the carry, repeat until the AND term equals zero. Pretty minimal, but still easy enough to program.
Presume for a moment we've got a working ALU-like system. Memory is the next problem. Relays are a pain to use for storage. Huge and expensive. The cheapest and most practical form of storage is paper tape, either punched or scan-tron style inked. This form of memory is rather unique, being write-once-read-many (WORM) and infinite in one direction. This is much more restricted than the classic Turing Machine. Can computation be performed on such a medium?
Let's expand on the basic punched tape system to produce a full computer system. It will most closely resemble the punch card machines of lore. Single user, no operating system, programmed in assembly, with minimal user interaction. With the exception of a few registers, all I/O and storage will be performed on paper tape. The tape could be punched, or it could be coated with iodine and electrically darkened. The specifics are being ignored for now, instead focusing on minimal building blocks. It is assumed that any element capable of switching (transistors, tubes, or relays) are prohibitively expensive and must be kept to a minimum.
Paper tape is the medium of choice for nearly all storage. While bits can be stored electronically, doing so with anything less than VLSI silicon or magnetic storage is very expensive. Paper is cheap and can be, for all practical purposes, infinitely long. With different sorts of hardare attached to it, paper tape easily supports four different data types. These will form the basis for all parts of the computer.
The simplest structure is the array. A series of numbers can be encoded one after another. The reading head can ratchet forward one notch and report the new value. Similarly, arrays can be used for output by appended values. Note that arrays do not keep track of the current index. Also notable is that arrays are either read only or write only. In general, they model simple I/O devices.
The most heavily used structure is the stack. The stack tape starts off completely blank. Each row of the tape has a data segment and two extra bits for flags. When a value is pushed to the stack, the head advances forward until it finds a blank spot on the tape, where it records the value and marks a 'written' bit. When popping a value from the tape, the head rewinds until it encounters the first unpopped value, marks the 'popped' bit and reads the value. For those not familiar with stack computers, stacks do everything from passing function parameters and return values, to keeping track of subroutine extry/exit points.
The most convenient structure is the associative list or dictionary. It attaches labels to chucks of data. There are two forms, read only and read/write. The R/W version acts like a global store for variables. When writing, the head advaces forward until it finds a blank piece of tape. It marks the write flag, writes the name of the varible, and marks the name flag. The head advances one position, marks the write flag and writes the value of the varible. Reading a variable starts from the end of the tape, rewinding until it encounters the most recent version. This is prohibitevly slow, and is technically optional for the simplest possible computer. But is is easier to write out an infrequently used value than to juggle it up and down the stack.
The read only form comes with a counter register. This register is a time saving device. When jumping between values, a quick comparison tells whether to move up for down the tape (it is assumed the labels are in order). For the computer described, a read only associative list holds the program listing. Each label is the name of a function, and the counter register holds the name of the currently executed function. A second register holds the current line number and acts the the program counter.
The fourth data type really does not count and is very impractical. I include it only for completeness. It is like a write only list, however the most recent value may be read. This emulates a register. Such a register would be much slower than even a relay and would only be cost effective is read/write heads were cheaper than bits of storage. A foolish purist could replace the handful of registers in the machine with this contraption.
Input device, output device, one stack for data, a second stack for return jumps, a method of reading instructions and an optional global variable store. Altogether this forms a fairly conventional stack based computer. All that is missing is an ALU, an assembly language, and the various instruction decoders to make it all go.
Working off the the assumption that computational units are excedingly expensive (and the implicit assumption that it is more important to make the machine run at all than to run fast), I would argue that an ALU is optional. More on this later, with examples.
Simple calculation is easy enough. It is fairly trivial to implement an RPN stack calculator. Pushing and popping a stack will be emulated on the paper tape. There will be a read head that scans the tape three elements at a time. Each tape slot will start off blank. Writing to the tape will mark a flag on that position as being written. Executing a position will mark a second flag. These two flags allow the head to shuttle back and forth between appending to the first free space and executing the current location in the stack.
There are six rules the head follows. N means 'number', O means 'operation', x means either. The three head positions are labeled bottom, middle and top.
BMT -> bottom, middle, top. NNN -> append bottom, advance NNO -> append result, advance xOO -> append top, advance xON -> advance ONO -> append middle, append top, advance, advance, advance ONN -> advance
An example computation, finding the average of 4, 5 and 6. The
w mark executed and written positions
eewwwww 456++3/ append bottom, advance BMT
eeewwwww 456++3/4 append result, advance BMT eeeewwwww 456++3/4B append top, advance BMT eeeeewwwww 456++3/4B+ advance BMT eeeeeewwww 456++3/4B+ append mid & top, advance*3 BMT eeeeeeeeewww 456++3/4B+3/ append result, advance BMT eeeeeeeeeewww 456++3/4B+3/F advance BMT eeeeeeeeeeeww 456++3/4B+3/F append mid & top, advance*3 BMT eeeeeeeeeeeewww 456++3/4B+3/F3/ advance BMT eeeeeeeeeeeeeww 456++3/4B+3/F3/ advance BMT eeeeeeeeeeeeeew 456++3/4B+3/F3/ append result, advance BMT 456++3/4B+3/F3/5 done</span>
Two things jump out. First, this is woefully inefficient, as it spends most of its time copying data and moving along the tape. Only a quarter of the steps actually do arithmetic. Second, all work is logged so debugging should be interesting.
Regarding the assembly language, Forth seems like a logical starting point. Chuck Moore's Machine Forth (very similar to Venture Forth for his SEA-Forth processor) is a surprisingly good fit. There are a few amenities that should be made to accomodate the sluggish nature of paper tapes. More on this later.
To be an easily usable computer, there should be four tapes. One tape for the program, one tape for the initial data, one tape for scratch work and one tape for output. Preferably, the program and data tapes will be read only, so that a program may be re-run. The old IBM punch cards could not be re-used, so maybe this is expecting too much. At the very least, all tapes are interchangeable, so that compilers and other meta-programs may exist.
Still working out a general purpose paper tape BISC Forth machine.