Bootstrapping in Compiler Design / Self-Hosting Compilers

1. Bootstrap 释义, again

Machine Learning 中已经见过了 Bootstrap Resampling (Bootstrapping) 和 Bootstrap Aggregating (Bagging), 现在又来一个，很好。

The word “bootstrap” comes from the old English phrase:

“To pull oneself up by one’s bootstraps.”

A bootstrap is a small loop of leather at the back of a boot, meant to help you pull your boots on.

The idiom describes something lifting itself up by its own straps, which sounds physically impossible, so it came to mean:

Doing something by using your own internal resources, without outside help.

就有一种 “左脚踏右脚原地飞升” 的既视感，所以一般翻译成 “自举”：

• 这里 “举” 取 raise up 的意义，比如 “举兵”、”举国”
• 而 “自举” 这个构词又和 “自学”、”自强” 是一致的

2. Bootstrapping in Compiler Design

我们定义：

• $L$: the target language (one to be compiled)
  • We can also think of $L$ as the set of all valid programs written in this language.
• $\Lambda$: a known language other than $L$ (e.g. C, Python)
  • We can also think of $\Lambda$ as the set of all valid programs written in this language.
• $B$: the set of binaries on the target platform (e.g. Win, MacOS)
  • Note that we don’t consider cross-platform compiling in this case

我们可以先用 $\Lambda$ 语言给 $L$ 写一个编译器程序，然后用 $\Lambda$ 自己的编译器来编译：

• $c_0 \in \Lambda$: a compiler (source code) written in $\Lambda$, to compile $L$ in to machine code or binaries (on the same platform of $B$)
• $b^{c_0} \in B$: the binary of $c_0$, generated by $\Lambda$’s compiler
  • We can also think of $b^{c_0} : L \to B$ as a function

假设此时我们再用 $L$ 语言写一个新的 compiler $c_1 \in L$. 由于 $c_1 \in L$, 它可以作为 $b^{c_0}$ 的输入，即我们可以用 old compiler’s binary $b^{c_0}$ 去编译 new compiler’s source code $c_1$, 得到 new compiler’s binary $b^{c_1}$:

\[b^{c_0}(c_1 \in L) = b^{c_1} \in B\]

注意这个 $b^{c_1} : L \to B$ 本身也是个 funciton，所以我们可以有：

\[b^{c_1}(c_1 \in L) = {b^{c_1}}' \in B\]

我们要求 $b^{c_1} = {b^{c_1}}’$.

继续这个过程 (比如说我要重构)，我们可以再写一个新的 compiler $c_2 \in L$:

\[\begin{align} b^{c_1}(c_2) &= b^{c_2} \in B \newline b^{c_2}(c_2) &= {b^{c_2}}' \in B \newline \text{subject to } & {b}^{c_2} = {b^{c_2}}' \end{align}\]

综上有：

• 这个从 $c_0 \in \Lambda$ 出发，一路迭代 $c_k \in L, \forall k \geq 1$ 的过程，我们称为 bootstrapping
• $c_0 \in \Lambda$ 称为 bootstrap (like everything starts from it)

$c_0 \to c_1 \to \dots \to c_k$ 这个 chain 何尝不是一种 version controlling

3. Self-Hosting Compilers

在 bootstrapping 的过程中，从 $c_1$ 开始，我们理论上就可以 discard $c_0$ 了 (当然我们会 version controlling 把它保存起来)。

Definition: A self-hosting compiler is one that can compile its own source code. $\blacksquare$

所以 $\forall k \geq 1$，$b^{c_k}$ 都是 self-hosting language.

强烈抵制 “A self-hosting compiler is one that can compile itself.” 这种看起来玄之又玄的说法：不区分 binary 和 source code 只会影响你的理解。在下定义时耍帅是我最不能理解的行为。

4. What if $L$ changed?

假设我有 language $L$ 和一个 self-hosting compiler $b^{c_k} : L \to B$.

此时我们给 $L$ 加了一些新的 feature，考虑这么两种情况：

1. 添加了新的 production rule，$L$ 变成了新语言 $L’ \supset L$
2. 添加了新的 keyword/syntax，$L$ 变成了新语言 $L’’ \supset L$

如果我们不想去修改 $c_0$ 再从头开始 bootstrapping，那么我们在写 $c_{k+1}$ 时就要坚持一个原则：

Just implement support for the new feature, but don’t use the new feature in the compiler source code itself.

具体到上述两种情况就是：

1. 我们在 $c_{k+1}$ 中不使用新的 production rule 所涉及的 statements, expression, etc.
2. 我们在 $c_{k+1}$ 中不使用新的 keyword/syntax

这么一来我们就能得到：

\[\begin{align} & c_{k+1} \in L \text{, but } c_{k+1} \not\in \big( L' \setminus L \big)\newline & b^{c_k}(c_{k+1}) = b^{c_{k+1}} \newline & b^{c_{k+1}} : L' \to B \end{align}\]

$L’’$ 的情况类似

由于 $b^{c_{k+1}}$ 已经支持了新的 feature，那么 $c_{k+2}$ source code 中就能使用这些新 feature 了。

上述这个 $c_{k+1} \in L$ 到 $c_{k+2} \in L’ \text{ or } L’’$ 的过程是一种 Two-Stage Compilation

代码组织上也可以用 conditional compilation 的技巧，比如：

#if NEW_SYNTAX_AVAILABLE
    // code using new syntax
#else
    // equivalent code in old syntax
#endif

当然，如果你新的 feature 导致的改动过大，抑或你要 re-design $L$，那么你可能还是要去修改 $c_0$ (或是选择另一个语言 $\Lambda’$ 写一个新的 ${c_0}’$) 并重新开始 bootstrapping.