從 Haskell 到 WebAssembly（1）

08-20

來自專欄不動點高校現充部128 人贊了文章

項目簡介

安利一下我最近在 Tweag I/O 做的項目：一個基於 GHC 的 Haskell to WebAssembly 編譯器。項目地址：tweag/asterius

目前項目處於 alpha 階段，可以編譯一些簡單的 Haskell 程序並在 Node.js 上運行。支持特性：

除 Template Haskell 以外的大多數 GHC 擴展
ghc-prim/integer-simple/base/array 中不涉及 IO 的部分。IO 靠運行時內建的介面以及 JavaScript FFI
運行時暫不支持垃圾回收，可在鏈接時設定 initial heap size，可在運行期動態申請新內存
可以通過 foreign import javascript 語法在 Haskell 程序中運行 JavaScript 片段，支持 first-class 的 JSRef 類型
除了需要打開 V8 的實驗性 BigInt 擴展以外，只要 JavaScript 引擎實現 WebAssembly MVP 版本的特性即可，無需 anyref/host-bindings/gc 等提案的支持
鏈接器支持 debug mode，可在運行期列印包含內存讀寫、控制流轉移的日誌
實現了 binaryen 的多層 Haskell 綁定，底層是 raw C bindings 以及自動編譯、鏈接 binaryen 庫的功能，中層是一套 Haskell IR 對應 binaryen IR，支持序列化、符號解析與跨模塊鏈接等，高層有一個 monadic EDSL，可以在 Haskell 里用 do-notation 之類的語法糖直接寫 WebAssembly 代碼

最簡單的試用方法是下載 Docker image，每個通過單元測試的 commit 會自動上傳一個 Ubuntu-based 的 image。直接 docker pull terrorjack/asterius 可以獲得對應 master 分支的最新 image，進一步指示參考 ahc-link --help 即可，可以將 .hs 編譯到一個 .wasm 文件和 .js 文件，.js 文件用 node 運行時會載入 .wasm 文件，初始化運行時，並運行 Main.main 對應的導出函數。運行自己寫的樣例時，不妨先參考幾個單元測試對應的輸入代碼。

當然，項目狀態距離能在瀏覽器里愉快地跑 Haskell 代碼還是有不少差距的，剩下的工作主要是運行時方面的：

storage manager 增加垃圾回收。雖然無腦默認開個 1G 的堆也已經可以運行不少 demo 了，這樣總不是個辦法對吧？當然，我要是有 Simon Marlow 十分之一的本事的話這個早就做出來了，原版的 GHC 裡面是並行分代 GC，我會先做個非並行非分代的實現然後慢慢迭代的（
scheduler 支持 Haskell 線程調度，包括運行 unbound thread、中斷和恢復 thread 等。這個弄完以後，foreign export javascript 就有戲了，畢竟一個前端語言如果不能從 JavaScript 調用進去的話那沒法用啊是不。

上面的坑填上以後還有不少周邊的工作可以做，比如加強 Cabal 支持，能編譯 Haskell 標準庫以外的更多庫、做個 WebIDL 到 Haskell 模塊的編譯器，調 Web API 更容易，etc。在做了，你智貓姐姐騙過人嗎（

大致介紹完了，接下來簡單說下 WebAssembly 和開發面向 WebAssembly 的編譯器的那些事，先講 non-Haskell specific 的部分，再講 Haskell specific 的。會分幾期慢慢講。

WebAssembly 介紹

總之，如果你是個吃瓜群眾，你只需要知道，WebAssembly 能讓你享受做前端開發以及寫 C/C++ 的雙份快樂（逃。目前使用第三方語言編譯到 WebAssembly 的使用體驗最完善的是 C/C++ 和 Rust。Rust 的話官方編譯器可以基於 LLVM 的 wasm32 實驗性後端生成代碼，而 C/C++ 自然是靠我們熟悉的 Emscripten，Emscripten 有 LLVM/binaryen 的模式可以選擇。教程網上很多我就不貼了。這裡主要寫如果你想自己寫編譯器，順帶蹭一波 WebAssembly 的熱點的話，大概需要了解的東西。

關於 WebAssembly 版本：目前主流 JavaScript 都實現了的是 WebAssembly MVP，另外 WebAssembly 官方有不少 proposal 在或快或慢地進行討論和實現，以下如果沒有特別聲明，WebAssembly 均一律指代 MVP 版本的 wasm32。

WebAssembly 跑起來是個什麼感覺：

首先你要有個 WebAssembly 的 binary file。WebAssembly 官方有一個 S-exp 的語法，那個是給人看的，還有一個 binary format，瀏覽器認 binary format。一個 binary 代表一個 WebAssembly 的 module。
然後，在 JavaScript 中調用相關介面編譯，讀入 binary，對其進行 parse 和 validation，生成一個 Module。這個 Module 暫時還不是可運行的。
對編譯成功生成的 Module 進行初始化。初始化的時候需要提供 import object，比如 WebAssembly module 中聲明需要導入什麼 JavaScript 函數的話，相關函數必須在 import object 里存在（不過並不在 JavaScript 側進行類型檢查）。
編譯/初始化都是非同步的，兩個步驟可以合一。初始化完，拿到 Instance 以後，Instance 的 exports 里是該模塊導出的函數，在 JavaScript 中可以運行這些函數，並獲得其運行結果，順帶觸發相關副作用。所有 WebAssembly 函數都是同步、運行到底的，不會返回 Promise 之類的玩意或者要讓你傳個 callback 啥的。

以上是跑起來的感覺，那麼寫起來的感覺呢？

類型系統：靜態強類型，沒有任何的隱式轉換，基本類型就只有 i32/i64/f32/f64 這幾種。函數類型是從若干個基本類型的參數值生成 0 個或 1 個基本類型的結果值。
線性內存：有一個 32 位定址的內存空間可以讀寫基本類型，支持 unaligned access。內存大小可以按 64KB 的頁為基本單位，聲明初始/最大大小、查詢當前大小和申請擴充。函數代碼等數據並不放在線性內存里。哦對了，0 也是合法的內存地址。
全局變數：除線性內存以外，另一個跨函數可以共享的全局狀態就是全局變數，可以聲明全局變數的初始化值，以及是否可變。
棧虛擬機：WebAssembly 沒有「表達式」概念，而是假設運行時實現了一個棧，多數指令的作用就是從棧頂彈出若干個基本類型的值，做做計算，把結果寫到棧頂。
函數抽象：呵呵，沒有尾調用。把想要支持被間接調用的函數放到一個表中，編號就是其「函數指針」，可以用 call_indirect 指令進行間接調用，間接調用在運行時進行類型檢查。另外，函數可以聲明局部變數。
異常處理：可以調用 trap 立即中止 WebAssembly 代碼，在 JavaScript 側拋出異常。WebAssembly 自身不能處理異常。
導入導出：支持導入導出的對象有：函數、全局變數、線性內存。函數必須滿足 WebAssembly 的函數類型要求。不用說，JavaScript 的引用類型是不支持的。另外 i64 也不行（不過有 workaround）
控制流：沒有任意跳轉指令。有 block/loop 指令、label 和作用域的概念，所有的跳轉指令只能跳轉到外層的 label，有點類似於 lambda calculus 裡面的參數綁定。

更具體的細節，可以去慢慢摳 WebAssembly spec，以及 MDN 上有關 WebAssembly 的 API 描述。如果有不清楚的地方，WebAssembly 官方有個 OCaml 寫的參考解釋器可以看看源碼。（參考解釋器不帶 JavaScript 引擎，所以如果想要觀測副作用，得通過修改全局變數/線性內存來實現）

生成 WebAssembly 模塊

以上介紹了單個 WebAssembly 模塊大概長什麼樣，以及怎麼跑起來。首先你需要有個 binary 模塊，這個東西怎麼生成，難道要對照 spec 自己拼二進位串？這裡列幾種不同的思路：

通過 S-exp 語法的源代碼，解析以後重新生成 binary。比如 WebAssembly 官方提供的 wabt 工具，可以在 S-exp 和 binary 之間進行轉換，並且支持 validate 和 interpret 操作。基於 wabt 的在線版工具 WebAssembly Studio 可以直接在網頁上編輯和運行 S-exp 格式的 WebAssembly 模塊。
通過 LLVM 的 wasm32 後端生成 WebAssembly module。前面可以對接 clang（不帶 C 標準庫支持），後面可以對接 lld，lld 實現了實驗性的 WebAssembly 鏈接功能。如果不關心單個 WebAssembly module，而是想要立等可取的整個 WebAssembly-based app，那麼直接 Emscripten 走起，C/C++ 標準庫和 SDL2 都有移植。
通過 binaryen 庫生成 WebAssembly module，這個主要就是面向編譯器開發者的。本項目底層也用到了 binaryen，所以接下來著重介紹 binaryen。

binaryen 本身是一個 WebAssembly 官方支持的 C++ 庫，提供了 C/JavaScript 介面可供第三方編譯器開發者使用。binaryen 庫主要支持的功能包括：

解析/生成/驗證單個 WebAssembly 模塊，支持 S-exp 文本格式的解析和輸出。與 V8/SpiderMonkey 等引擎相比，binaryen 支持的 WebAssembly 特性集相對保守，目前除了 MVP 以外，額外支持的特性只有 thread/atomics 相關指令。
解釋執行 WebAssembly 模塊。這個解釋器和官方的 spec 解釋器/wabt 解釋器支持的功能大致類似。
支持兩套不同的 IR：基於表達式的遞歸 IR，以及貼近 WebAssembly 底層的棧 IR。C API 中目前只支持表達式 IR，主要出於歷史原因：WebAssembly 草案最初是表達式 IR，binaryen 也這麼實現，後來轉向棧 IR 以後，表達式 IR 的介面仍然保留了下來。對於編譯器開發者而言，使用表達式 IR 可以稍微比棧 IR 省一點點工作（其實就是後序遍歷一下 AST 的事）
WebAssembly 中涉及函數名、函數類型名、函數表索引等需要索引的地方，一律是一個 i32，而在 binaryen 中可以用字元串命名，這點微小的工作對編譯器開發者還是很貼心的，不要求自行維護符號表。
最重要的是，binaryen 中提供了 Relooper 演算法的實現。很多編譯器涉及的中間表示是帶任意跳轉的控制流圖，控制流圖的節點之間不一定存在拓撲序，也就無法非常簡單地用一系列嵌套的 block/loop 來表示。Relooper 演算法接受控制流圖輸入，輸出基於 block/loop 實現的控制流。

所以，如果你是個編譯器開發者，想要體驗一波 WebAssembly 的代碼生成的話，大致需要做什麼事呢？

翻一下 MDN 上 WebAssembly 的文檔，大致知道怎麼在 JavaScript 中編譯和運行一個 binary 模塊。Node.js 中的介面大致相同，不過不支持流式編譯。
可以通過拼接文本生成 S-exp 源代碼，然後調 wabt 生成 binary，或者調用 binaryen 的介面。
拿到 binary 之後，再生成一個很小的 JavaScript wrapper 腳本，這個腳本負責讀入 binary 然後執行。
有什麼不理解的地方，多做做實驗，然後回頭翻一下 WebAssembly spec。不過，一開始一行代碼都不寫就去翻 spec，我是不推薦的，很容易自以為看懂了結果根本不是那麼回事。一點小小的人生經驗（逃

預定下一期介紹 asterius 編譯器的代碼生成器。