Compiling a Piece of Paper
Bootstrapping
I was thinking about bootstrapping and thought about this awesome interview of Ken Thompson talking about Doug McIlroy.
I often share this story with my students when I teach Programming Languages.
In the interview, Ken Thompson explains how Doug McIlroy implemented a compiler on paper by hand, and then ran the compiler on itself on paper by hand, for a proprietary language called TMG (TransMoGrifier).
Outline of his process
Design TMG on Paper. Douglas McIlroy reverse engineers the TMG programming language spec entirely on paper.
Write a TMG Compiler in TMG (on Paper). Using “paper-TMG”, McIlroy writes a TMG program (still on paper) that can compile TMG code into machine code – a self-hosting compiler.
Simulate the TMG Compiler by Hand. Since the compiler is written in TMG but no TMG compiler implementation yet exists, he simulates running the TMG compiler by hand, manually performing each step the compiler would do to compile itself.
Generate Machine Code for the TMG Compiler. The result of this manual simulation is the machine code version of the TMG compiler.
Enter Machine Code into the PDP-7. He then types the resulting machine code directly into the PDP-7 computer.
Run the Compiler to Compile Other TMG Programs. With the TMG compiler now running natively on the machine, it can be used to compile other TMG programs, including possibly recompiling itself.
Pretty amazing!
Here is the interview starting at the timestamp where this comes up.