Paper Tape

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.

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 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.

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.