2008/09/25

編譯器提靴

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

其中 inta,b 的 a 是實作 interpreter 的語言、b 是 interpreter 接受的語言;compa,b,c(和 speca,b,c)中的 a 是實作 compiler 的語言、b 是 compiler 接受的語言、c 是 compiler 輸出的語言;pb 是以 b 語言寫成的程式;〚 p 〛a 是 p 程式在 a 語言下的語意。

現在定義以下代號:

  • h 為 host machine language、
  • u 是某種 universal, portable assembly language、
  • i 是高階的 implementation language。
這部 host machine 是個新平台,上面能用的資源只有 〚·〛h(機器執行)、inth,u(虛擬機器)、compu,i,u(各平台通用的編譯器)、compi,i,u(前者的源碼)、compi,i,h(從前一份源碼改寫、產生 native machine code 的新編譯器源碼)。其中 inth,u 和 compi,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 只需要寫 inth,u,就能達成上述四種目標呢?(當然必須提供的 specialisers/compilers 份數愈少愈好。)

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

Labels:

<< 回到主頁