Bootstrap magic

I'm giving a talk on Thursday for our CS club (a student ACM chapter). Our compilers course is hardly ever offered, because it ends up being a fairly arcane topic considering the career goals of the majority of our students. There are ways to make it more relevant of course, but I don't want to argue either way on that today.

Instead, I decided to put together a fun little talk for the club on some of the ‘big ideas’ in the area. Here's the abstract:

One of the more profound concepts in computer science is compiler bootstrapping: very often, the compiler for a programming language is written in that language itself. This begs an almost mystical question: what compiles the compiler? (And what compiled that compiler, and so on...) The first part of this talk is an adaptation of the famous Turing Award speech "Reflections on Trusting Trust" by Ken Thompson, co-inventor of the UNIX operating system. We explore the bootstrapping concept, and how to exploit it to devious ends. The second part is a very brief introduction to program analysis and compiler optimization, using static single assignment form.
I've been experimenting with some code to show that technique of teaching the compiler once, and then removing it from the source. Ken Thompson used the example of control codes, with a fragment of code that essentially said case '\n': return '\n'; but I found an enlightening post on the topic that cites this trick, from a Pascal compiler:
   insertSymbolConstantBinding("INTEGER_MAX", INTEGER_MAX)
The value of INTEGER_MAX was ‘taught’ to the compiler at some point in its evolution, but since the compiler compiles itself, it is no longer needed. Pray you don't lose all the binaries!

I'd like to turn the talk into a screen-cast, just because I'd like to experiment with that as a pedagogical format, and (I think) I have the tools. We're starting to see lots of ‘Web 2.0’ tool-builders publish video tutorials. I doubt I'll record any audio/video directly during my talk, but rather use that as a trial run of the script. Watch this space!

©20022015 Christopher League