編譯器提靴

今天的高等編譯器設計提到如何做 compiler bootstrapping，在此用比較像代數的樣子重寫一遍（這樣的手法當然是學自 FLOLAC '08 的 Partial Evaluation 課程）。定義 interpreter 和 compiler（和 partial specialiser）的等式是

其中 int_a,b 的 a 是實作 interpreter 的語言、b 是 interpreter 接受的語言；comp_a,b,c（和 spec_a,b,c）中的 a 是實作 compiler 的語言、b 是 compiler 接受的語言、c 是 compiler 輸出的語言；p_b 是以 b 語言寫成的程式；〚 p 〛_a 是 p 程式在 a 語言下的語意。

現在定義以下代號：

• h 為 host machine language、
• u 是某種 universal, portable assembly language、
• i 是高階的 implementation language。

這部 host machine 是個新平台，上面能用的資源只有 〚·〛_h（機器執行）、int_h,u（虛擬機器）、comp_u,i,u（各平台通用的編譯器）、comp_i,i,u（前者的源碼）、comp_i,i,h（從前一份源碼改寫、產生 native machine code 的新編譯器源碼）。其中 int_h,u 和 comp_i,i,h 是 compiler team 要自己動手寫或改的，其他都是既有資源。

既然有虛擬機器作為媒介，最簡單的情況就是讓編譯器和產出的執行檔都在虛擬機器上執行：

這顯然不夠好，我們希望產出的程式能直接在 host machine 上面執行。因此：

藍色部份就是執行在 VM 上但產出 native code 的編譯器程式。老闆還是不滿意，因為編譯太慢了，所以再導一次，讓編譯器完全移植到 host machine 上面：

藍色部份就是原生編譯器的程式碼。產生的方式是先在 VM 上面以通用編譯器編譯「產生 native code 的編譯器源碼」，得到產出 native code 的通用編譯器，然後（一樣在 VM 上）再用這個編譯器編譯「產生 native code 的編譯器源碼」，得到產出 native code 的原生編譯器。

為了完整，也附上「產生通用碼的原生編譯器」的推導：

只要抓到訣竅，就會發現 compiler equation 的確有引導作用，能讓人輕鬆地導出 bootstrapping 的過程。

不過當 partial specialiser 走上舞台，事情就變得複雜了。Specialisers 有三個 Futamura projections（長相有點嚇人 XD）：

第一個 Futamura projection 說把 interpreter 針對某個程式特化，效果等同於編譯那個程式；第二個說把 specialiser 針對某個 interpreter 特化，就相當於造出一個 compiler；第三個則是最痛苦的 XD，它說把 specialiser 針對某個 specialiser 特化，就得到一個 compiler generator ─ 只要給這個 compiler generator 一個 interpreter，它就會造出一個對應的 compiler。那麼能不能提供一些完全和 h 無關的 specialisers/compilers 讓 compiler team 只需要寫 int_h,u，就能達成上述四種目標呢？（當然必須提供的 specialisers/compilers 份數愈少愈好。）

--
這絕對是 CS 裡面最神奇也最惱人（mind-boggling）的主題之一 XD。