Episode 7's homework — what assembled the first assembler?
In Episode 7 we saw that "the first Unix was written in PDP-7 assembly," and left homework — you need an assembler to turn assembly into machine code, but what assembled that first assembler? The PDP-7 didn't even have an assembler at first. There was no chicken. The answer was surprisingly physical. Thompson used a different machine. On the large machine GE-635 (running the OS GECOS), which was already up and running splendidly, he made machine code for the PDP-7, punched it onto paper tape, and carried it over to the PDP-7. This way of "borrowing someone else's machine" is called cross-assembly.
Episode 7's self-hosting ring — the assembler assembling itself — is strong once it starts turning. But before it turns, the PDP-7 has not a single assembler. "You need an assembler to turn assembly into machine code, but there's no assembler to turn that assembler into machine code." This is Episode 0's chicken and egg, exactly. Thompson's solution was to not try to solve it inside this machine.
Usually "assemble with an assembler" means, on the same machine, making machine code for that machine (native). But the machine that runs the assembler (the host) and the machine the machine code is aimed at (the target) can be different. An assembler running on the GE-635 (macros in GEMAP) emits machine code aimed at the PDP-7 — this is cross. In the figure below, switch between native and cross, and see why at first there was only cross.
The PDP-7-bound machine code produced by cross lives inside the GE-635. It has to be moved to the PDP-7. This is an era with no such thing as a network. What did they do? — They punched it out onto paper tape, carried the tape by hand, on foot, to the PDP-7, and fed it through the reader. The true nature of the "carry" from Episode 6's "carry the O-code to the new machine" is this foot-transport of punched tape. In the figure below, try running the whole sequence.
The idea of cross is this — "you don't have to build the target on the target; just borrow one running host." Even on a new machine with no chicken, you can get an egg from someone else's chicken. This is exactly the same skeleton as Episode 3's "borrow an existing cc to ignite gcc," Episode 6's "carry the O-code," and modern cross-compilation (making code for a new CPU or embedded device on the PC in front of you). For half a century, it's been "the way a new machine gives its first cry."
Once cross loads a minimal set of tools onto the PDP-7 — kernel, editor, shell, and the assembler — Unix can write and test programs on itself (self-supporting). As a finishing touch, Thompson wrote a PDP-7-native assembler and stopped using the GE-635 entirely. The answer to the "what assembled the first as?" that flickered in Episode 7's figure is filled in here — the first as was assembled by the GE-635's cross-assembler. The ring was ignited from someone else's machine.
So "what built that GE-635 toolchain?" — again it looks like passing the problem down a stage. But this time it's a little different. The GE-635 was itself once new, and was brought up from still older machines, or from more primitive means. Every "already-existing machine" was once a new machine. Cross is a chain of borrowing "the machine brought up just before," and this is finite. Trace it back and eventually you arrive at — the very first machine, with not a single host to borrow. There, the magic of cross does not work.
Trace the chain of cross back, and you always arrive at "the first machine, with no one to borrow from." The world's very first such computer has no other machine to assemble for it, and no finished paper tape to feed in. So how was the very first instruction put into that machine? — Next time, at last, the bottom. The answer is human hands.
(1) Cross-assembly does not solve the chicken and egg. It just gives up on "solving it inside this machine" and moves the problem to a different (already-running) machine. But that chain is finite, and traced back it bottoms out at the first machine (Episode 9). It is not an infinite regress.
(2) Details such as GE-635/GECOS/GEMAP, paper-tape transport, and the timing of the move to self-supporting vary in wording by source (the skeleton — "cross-assembler on GECOS → paper tape → PDP-7 → eventual independence with its own assembler" — agrees with Ritchie's own recollections). (3) The figures schematize the workflow and are not strict reproductions of the real machines' appearance or operation.
The answer to Episode 7's homework, "what assembled the first assembler," was a different machine. The not-yet-born PDP-7 had no assembler and couldn't start within itself. So Thompson ran an assembler (macros in GEMAP) on the already-running large machine GE-635 (GECOS), and made machine code aimed at the PDP-7 — cross-assembly, host ≠ target. The resulting machine code was punched as holes into paper tape, carried by hand, and read into the PDP-7. It is the muddy, real-world instance of Episode 6's "carry the O-code."
Eventually the PDP-7 gathered a kernel, editor, shell, and assembler, Unix became able to develop on itself (self-supporting), and Thompson wrote a PDP-7-native assembler and graduated from GECOS. The crux of cross is "you don't have to build the target on the target; just borrow a running host" — the same skeleton as Episode 3's existing cc and modern cross-compilation. But this only moves the chicken and egg to a different (already-existing) machine. The chain is finite, and traced back you arrive at the first machine with no one to borrow from. — Next time, at last, the bottom. The first byte was put in by human hands.
Print / save as PDF: ⌘+P (Ctrl+P on Windows). On screen, use Figure 1's buttons to switch between native and cross, and Figure 2's "▶" to replay the paper-tape transport workflow. "Show the answer" reveals each solution.