自作プログラミング言語と WebAssembly コンパイラ
これは Recruit Advent Calendar 2021 の 6 日目の記事です。
はじめに
このエントリでは、僕が趣味で作っている PicoML という自作プログラミング言語の話を書こうと思う。
作ってから半年くらい経っているのだけれど、如何せん自作言語という無用の長物であり、登壇などでコイツの話をすることもないため、ある種の供養みたいなものだと思ってもらって構わない。
PicoML の概要
まずは実装した言語の紹介から。ざっくり以下の特徴を備えた言語である。
- ML ベースの文法による関数型言語
- 単純 let 多相型推論による型チェック
- CLI として、Node.js 上での即時評価器（REPL）と WebAssembly をターゲットにしたコンパイラの双方を提供
REPL やコンパイラの実装は TypeScript で行っている。自分の勉強が主目的であったため、REPL やコンパイラの CLI を動作させるのに一切の依存 npm パッケージを必要としないようにしている。トークナイザや.wasm バイナリファイルの出力に至るまですべてフルスクラッチで記述した。気づいたら 13,000 行程度（本体 10,000 行/テストコード 3,000 行くらい）に育っている。
言語としての書き味は以下のようなイメージ。
もうちょっと込み入った例として、1 から 10 までの整数の階乗の計算式を書くとこんな感じ。
npm -g install pico-ml から REPL とコンパイラをインストールできるようにしてあるが、Web Playground も用意している。Web Playground 版は、ブラウザの JavaScript で PicoML のコンパイラを動的に動かして WASM を生成し、それを実行するようにしている。画面の左下に表示されているのが、コンパイルされた WASM のバイトコードだ。
Web Playground からどうぞ。
上述の例のとおり、if 式や再帰関数定義、リストとパターンマッチなどをできるようにしている。基本的に OCaml のサブセットとなっている。
逆にできないことは山のようにある。
- 扱えるデータ構造は整数・浮動小数・真偽値・関数・リストのみ。タプルとかない
- 評価・コンパイルできるのは式は一つまで。 utop のように「トップレベルに様々な変数を束縛して、後続の式から参照する」みたいなことはできない
- 標準関数のようなものは何も提供していない。
List.mapとかも自分で書く必要があるし、print関数もない - etc,,,
PicoML を作った理由
全体で 13,000 loc というと、僕にとってはまぁまぁなボリュームだ。
どれくらいのボリューム感なのか、他と比較してみると、例えば TypeScript で GraphQL Client を便利に開発するためのツールを作っている話 で紹介した ts-graphql-plugin という、やはり TypeScript 製のツールがある。ts-graphql-plugin は、僕が真面目に作っている OSS 類としてはコードが多い部類なんだけど、試しに先程測ってみたら 9,000 loc 程度だったので、PicoML はその 1.5 倍近くあることになる。
そこまでの手間をかけてまで何がしたかったのか、と問われたとしても明確な答えが返せなくて「一回くらいはプログラミング言語を実装する」という経験を積んでおきたかったから、と言うしかない。
日頃、Web フロントエンド関連の仕事をしている中で、抽象構文木を扱ってちょっとしたツールのようなものを用意することは割と多いのだけれど、業務の中では全体のツールチェインの隙間を埋めるためのグルーコードになる。最初から最後まで自分だけで実装するという機会は、自分で作らない限り巡り会えないと考えていたからかもしれない。
製作時系列
およそ 2 ヶ月半くらいで一通りを作っている。その後はたまに機能を足したりしていた。
- Phase 1. 2021/03/08–2021/04/03: 構文解析, 評価, 型推論部分
- Phase 2. 2021/04/03–2021/05/07: WebAssembly へのコンパイラ
- Phase 3. 2021/05/12–2021/05/21: Web Playground UI
以前に 「プログラミング言語の基礎概念」を読んだ というエントリを書いたのだけれど、これが上記の Phase 1 に相当する部分。
その時点のコードベースから fork して、演算子などを追加しつつコンパイラ部分を追加したのが Phase 2 だ。この時期は最初の 10 日間ほどは実装は一切せずに、WebAssembly の勉強をしていた。以下は当時の勉強メモ。
Phase 3 の Web Playground については、おまけみたいなものだ。CLI 側は気合入れて依存パッケージゼロで組んだけど、Playground 側は普通に React / Ace Editor でサクッと終わらせた。どうせ webpack でバンドルしてしまうので、zero dependencies の意味もフロントだとボヤけるし。
得たもの
冒頭で「無用の長物」と書いたが、フルスクラッチで PicoML というプログラミング言語の実装をしてみたからこそ得たものもあったと思う。
- プログラムを書くことそのものの楽しさ
- 新しい言語の知識
- 既に持っていた知識の再確認
コンパイラを実装するというのを言い換えると「プログラムを書くプログラムを書く」という意味になるけど、そんなの楽しいに決まっている。
PicoML の場合、やっていることは「TypeScript で OCaml を WebAssembly に生成する」ことになる。実装前の段階での僕とって勝手知ったる言語は TypeScript だけだったので、WebAssembly や OCaml は仕様書や入門者向けのドキュメントを読み漁りながら 1 から身につけていく作業だった。
特に WebAssembly Specifications は実装期間中は毎日のように読んでいたので、その過程で WAT (WebAssembly Text Format) の読み書きも体得できたし、Interface Types や Module Linking などの WebAssembly Spec Proposal を追いかけるモチベーションにもつながった。
一方で、既に自分自身の中に溜まっていた経験を再度引っ張りだすような部分も少なからずあった。抽象構文木関連の処理という意味では実装したことのある系統の処理も結構あって、たとえば「TypeScript で GraphQL から TypeScript の型定義を生成する」という機能が ts-graphql-plugin にあるのだけど、これもある種のコンパイラだ。DIY GraphQL Codegen という資料に AST to AST の概念をまとめたんだけど、この経験のお陰で PicoML だろうと（多分他の言語だろうと）エッセンスを抑えておけば、再利用のできる知識だと認識できた。
繰り返しになるのだけど、言語実装というのは本当に楽しくて、低レイヤを知りたい人のための C コンパイラ作成入門 がその楽しさを説明してくれている。
コンパイラ作成は大変楽しい作業です。最初のころはバカバカしいくらい単純なことしかできなかった自作言語が、開発を続けていくとたちまちのうちに自分でも驚くくらい C 言語っぽく成長していって、まるで魔法のようにうまく動くようになります。実際に開発をしてみると、その時点でうまくコンパイルできるとは思えない大きめのテストコードがエラーなしにコンパイルできて、完全に正しく動くことに驚くことがよくあります。そういうコードはコンパイル結果のアセンブリを見ても自分ではすぐには理解できません。時折、自作のコンパイラが作者である自分を超える知性を持っているように感じることすらあります。コンパイラは仕組みがわかっていても、どことなく、なぜここまでうまく動くのか不思議な感じがするプログラムです。きっとあなたもその魅力に夢中になることでしょう。
プログラマ万人がやるべき、とは思わない。前述の通り、そこそこ可処分時間が持っていかれるのは間違いないし、作ったところでその成果物自体が直接何かの役に立つことはまぁないだろう。でも、それを補って余りある楽しさがあるので、興味をもってくれる人がいたら、是非何かしらの言語実装にトライしてみてほしいと思う。
プログラミング言語をつくる流れ
以降では、「どのような流れでプログラミング言語が実装されていくか」の概略を解説していきたいと思う。
- 言語機能・仕様の設計
- 抽象構文木の設計と実装
- 即時評価機能の実装
- コンパイル機能の実装
1. 言語機能・仕様の設計
ここで考えることは、本来は山のようにある。関数型なのか手続き型なのか、変数をどのように取り扱わせるのか、評価戦略は正格なのか遅延なのか、etc… とはいえ、本当にゼロから設計することはなく、自分が知っている何かしらの言語を参考にすすめる筈だ。PicoML の場合、最初から「関数型言語であり、文法は OCaml のサブセット」という制約を強いているため、「OCaml の仕様のうち、どこまでを取り込むか」という意味になる。
また、設計したすべての機能を最初から作り込むのは無理がある。
ここでは一旦、「0 ~ 127 までの整数の足算と掛算ができる言語」というものを考える。これだって OCaml のサブセットであることには変わりない。
1 + 21 + 2 * 3(1 + 2) * (3 + 4)
2. 抽象構文木の設計と実装
言語機能のデザインが済んだら、設計した言語を抽象構文木で表すことを考える。
プログラム言語と呼ばれるものは総じて抽象構文木（AST; Abstract Syntax Tree）というツリー構造に変換される（インタープリタ系言語だとそうじゃないこともあるけど）。
例えば 1 + 2 という足算は以下のようになる。
抽象構文木のデータは、次のような構造体で表現する。
「抽象」というのは、「ソースコードの全情報が保持されるわけではない」ということだ。 1+2*3 も 1 + 2 * 3 も 1 + (2) * 3 も同じ形のデータ構造になる。一方で 1 + 2 * 3 と (1 + 2) * 3 が同じ結果の構造になってしまったら計算を正しく行えない。この 2 つの式は、以下のような抽象構文木に変換されないといけない。
プログラミング言語をソースコードから抽象構文木に変換する機能のことを「構文解析器」とか「パーサー」と呼んだりする。たとえば先程の (1 + 2) * 3 の変換処理であれば、 parse という関数を用意した上で以下のようなテストコートを書くことになる。
ここではパーサーの実装コードそのものには触れないでおくが（長くなってしまうので）、実装のやり方や考え方だけ簡単に触れておく。
パーサーを用意するには、たとえば PEG.js のような「パーサージェネレータ」と呼ばれるライブラリを利用する。
ただ、この程度の自作言語であれば自分で書くのもそれほど難しくない。再帰下降構文解析と呼ばれるテクニックが常套手段として用いられる。
パーサージェネレータにせよ、再帰下降構文解析にせよ、「そのプログラミング言語で表現可能なコードを表現するための生成規則」を定義することになる。生成規則は BNF や EBNF と呼ばれる記述方法で表現されることが多い。いまここで扱っている「自然数の加算・乗算ができる言語」は以下のように表現できる。
expr ::= mul ("+" mul)*
mul ::= group ("*" group)*
group ::= "(" expr ")" | nat
nat ::= "0" | "1" | "2" | ... | "127"一番目の規則の expr ::= mul ("+" mul)* は加算を表していて「式は mul という規則の結果 1 つに続いて『+ という記号と mul という規則の結果』が 0 回以上繰り返される」という意味を表している。"+" のように引用符付きで表しているのは、実際に言語中で利用される終端記号であり ("+" mul)* の括弧とアスタリスクは「当該部分の繰り返し」の意味だ。同じように mul の規則は group という規則から生成されていて、こちらは乗算を表している。
group の規則は式を括弧でグルーピングするための規則だ。 group ::= "(" expr ")" | nat の | は、パイプ記号で区切ったどちらか一方の生成規則が適用されるという意味なので、group という生成規則は「 expr 規則を括弧で囲んだものか、もしくは、 nat という規則のどちらか」ということになる。 nat 規則はただの自然数を生成 する規則だ。
再帰下降構文解析は、BNF で表現された生成規則それぞれにパーサーを実装していくことで言語全体のパーサーを組み立てる手法だ。ここで例示した BNF から構文木を生成するパーサーの例を TypeScript Playground に書き残しておく。
3. 即時評価機能の実装
即時評価機能、という呼び方があっているのかわからないが、後続のコンパイラと区別するためにそう呼ぶことにする。「パースした構文木の式をその場で計算する」という意味で使っている。
構文木が完成していれば、木構造を再帰的に評価していくだけなので簡単。
コンパイラを作る上では即時評価の機能は実装する必要はないのだけど「設計した言語を動かせるようにする」という楽しみが割と簡単に味わえるので、そういう意味ではオススメである。
また、「プログラミング言語の意味」を考える上でも、評価機能は重要だ。
例えば、上記の評価機能は「二項演算子は左右それぞれの項を評価した結果を加算（もしくは乗算）する」という操作を行っている。「足算・掛算のプログラミング言語を作っているのだから当たり前でしょ？」と思うかもしれない。
だが、実際のところは逆なのだ。「操作の規則が二項演算という構文に意味を与えた」のだ。(Node.js における) 数値の演算を、expr + expr や expr * expr という BNF（で表現可能な AST）に割り振ったのは、僕の恣意的な選択の結果だ。小難しい言葉でいうと、「操作論的意味論として、評価規則を定めることでプログラミング言語にセマンティクスを与えた」といえる。
今回のエントリでは詳細の解説は行わないが、「変数に値を束縛する」「関数を適用する」なども、評価規則を明文化できて初めてセマンティクスを表現できた、ということができる。
4. コンパイル機能の実装
最後はいわゆるコンパイラバックエンドと呼ばれる部分。まずは「どのような環境で動作させたいか」に従って、出力対象を決める必要がある。PicoML は以下の理由で WebAssembly を選択している。
- Node.js でもブラウザでも動作する
- 仕様そのものを学びたかった
ということで、あとは WebAssembly のランタイムが読める形式、要するに WASM を生成するだけだ。
先程から例として使っている自然数の加算・乗算器に即していうのであれば、たとえば「(1 + 2) * 3 を計算してその結果を返す WebAssembly モジュール」は以下の wasm となる。
00000000 | 0061 736d 0100 0000 0105 0160 0001 7f03
00000010 | 0201 0007 0801 046d 6169 6e00 000a 0c01
00000020 | 0a00 4101 4102 6a41 4103 6c0bいきなりバイト値の列を例示しても流石にチンプンカンプンなので、ここもステップ・バイ・ステップで説明していく。
まずは「ただ自然数定数を返す」だけの関数を持ったプログラムから。
WebAssembly にはバイナリ表現の WASM だけでなく、テキスト表現の WAT(Web Assembly Text format)という形式がある。WebAssembly の実行エンジンがサポートするのは飽くまで WASM だけだが、人間が読み書きしやすいように用意されているフォーマットが WAT だ。
以下が WAT による「整数の 1 を返すプログラム」の例。
3 行目の i32.const 1 が「32 bit 整数の 1」という意味だ。 (export "main") というのは「"main" という名前でこの関数をモジュール外に公開するよ」という意味。したがって、この WAT に対応する WASM は次のように JavaScript から実行できる。
さて、WAT ではいくつかの Abbreviation(短縮記法)が定義されており、先程の例も短縮記法で表現していた。 Abbreviation に頼らずに書くと、以下のように書き下される。
また、$mainFnType のような $ 始まりの部分は名前を付けた対象の参照を意味しているが、実体は順番でしかない。たとえば type $mainFnType は「type 宣言の 0 番目」だし、 func $main は「関数定義の 0 番目」に対応することになる。 $ ではなく、このインデックス値を使って WAT を書くこともできる。
ここまで来ると大分 WASM 形式に近づいてきている。これをバイナリ表現（WASM）で表すと次のようになる。
00000000 | 0061 736d 0100 0000 0105 0160 0001 7f03
00000010 | 0201 0007 0801 046d 6169 6e00 000a 0601
00000020 | 0400 4101 0bhttps://webassembly.github.io/wabt/demo/wat2wasm/ を使うと、WAT が WASM にどのように対応しているかのログを見ることができる。先程の例の WAT を変換すると次のログが得られる。
0000000: 0061 736d ; WASM_BINARY_MAGIC
0000004: 0100 0000 ; WASM_BINARY_VERSION
; section "Type" (1)
0000008: 01 ; section code
0000009: 00 ; section size (guess)
000000a: 01 ; num types
; func type 0
000000b: 60 ; func
000000c: 00 ; num params
000000d: 01 ; num results
000000e: 7f ; i32
0000009: 05 ; FIXUP section size
; section "Function" (3)
000000f: 03 ; section code
0000010: 00 ; section size (guess)
0000011: 01 ; num functions
0000012: 00 ; function 0 signature index
0000010: 02 ; FIXUP section size
; section "Export" (7)
0000013: 07 ; section code
0000014: 00 ; section size (guess)
0000015: 01 ; num exports
0000016: 04 ; string length
0000017: 6d61 696e ain ; export name
000001b: 00 ; export kind
000001c: 00 ; export func index
0000014: 08 ; FIXUP section size
; section "Code" (10)
000001d: 0a ; section code
000001e: 00 ; section size (guess)
000001f: 01 ; num functions
; function body 0
0000020: 00 ; func body size (guess)
0000021: 00 ; local decl count
0000022: 41 ; i32.const
0000023: 01 ; i32 literal
0000024: 0b ; end
0000020: 04 ; FIXUP func body size
000001e: 06 ; FIXUP section sizeWASM のマジックナンバーから始まり、type に相当するセクション、function に相当するセクション、 export に相当するセクションと続いていくのが見て取れる。export セクションの後に section "Code" (10) と来ているが、これが関数の本体部分だ。
豆知識だが、WASM のマジックナンバーである 0061736d は ASCII に直すと asm だ。Java の.class ファイルが c0ffee から始まるのと似ている。
WAT と WASM の関係が見えてきたところで、 $main 関数の中身を少しだけ書き換えてみよう。「1 を返す」から「1 + 2 を返す」に変更してみる。
i32.add というのが足算の命令だ。後述するが、WebAssembly の命令はシンプルなスタックマシンなので、実行する命令が後置されていく。
先ほどと同じ様に wat2wasm で変換ログを眺めてみると、最後の Code Section までは何も変わらないことがわかるはずだ（関数の中身しか書き換えてないから当たり前かもしれないが）。
// (中略)
; section "Code" (10)
000001d: 0a ; section code
000001e: 00 ; section size (guess)
000001f: 01 ; num functions
; function body 0
0000020: 00 ; func body size (guess)
0000021: 00 ; local decl count
0000022: 41 ; i32.const
0000023: 01 ; i32 literal
0000024: 41 ; i32.const
0000025: 02 ; i32 literal
0000026: 6a ; i32.add
0000027: 0b ; end
0000020: 07 ; FIXUP func body size
000001e: 09 ; FIXUP section size最後の 2 行に FIXUP *** size とあるのは、Code Section 全体のサイズと、0 番目の関数コード（= $main 関数のこと）のサイズがセクションのヘッダ側になるため。
0000020: 07 ; FIXUP func body size
000001e: 09 ; FIXUP section sizeこの例では、関数コードが以下に示す 7 バイトの列からなっているので、 func body size が 7 であり、関数の個数が 1 個であるため、7 + 1 (関数個数) + 1(func body size の分) = 9 となって、Code Section 全体のサイズが 9 バイトとというわけだ。
0000021: 00 ; local decl count
0000022: 41 ; i32.const
0000023: 01 ; i32 literal
0000024: 41 ; i32.const
0000025: 02 ; i32 literal
0000026: 6a ; i32.add
0000027: 0b ; end逆に、上記の関数コードのバイト列部分さえ生成すれば、後はその長さを数えて固定値のバイト列と組み合わせれば WASM を組み立てることができる。
さて、今は自然数の加算と乗算のみからなるプログラムを見てきているわけだが、32 ビット整数の演算は WebAssembly 仕様の Binary Format / Numeric Instructions に記載されている。
ここでスタックマシンの説明をするため、1 + 2 を実行する関数の WAT 例に戻ろう。
WebAssembly の関数はスタックマシンベースの計算モデルに従っている。次の図は上の WAT における main 関数の開始から修了までの 3 命令でスタックがどのように変化していくかを表している。
さらに WAT に i32.const 3 i32.mul を追加してみる。
スタックマシンは次のように動く。要するに (1 + 2) * 3 を実行したわけだ。
逆に次のように i32.add の位置を少しだけ変更すれば、これは 1 + 2 * 3 の例だ。
抽象構文木を思い出してほしい。抽象構文木によって中置演算子 + や * を構造的に表すことができた。
「左右のノード（オペランド）がスタックに積まれている状態で、演算を実行する」というルールで加算も乗算も表現できてしまう。コードで表現すると、以下の関数 compileToInstructions を実行すればよいということだ。
上記が加算乗算を実行する WASM プログラム出力コンパイラの中核となるコードとなるのだが、「3. 即時評価機能の実装」で記述した「加算乗算を即時評価する機能」のコード（下記）と見比べてみてほしい。どちらのコードの場合も「左右のノード（オペランド）に再帰的に作用させた結果を使って、親ノード結果とする」という構造は全く一緒だ。
大雑把且つ非常に簡単ではあるが、自作のプログラミング言語が WebAssembly にコンパイルされて動作するまでの流れは以上となる。ここまでで取り扱った、自然数の加算・乗算言語のコンパイラについて、 TypeScript Playground のリンクを貼っておく。
たかだか 200 行にも満たない程度のプログラムだが、「言語の生成規則から抽象構文木を作る」「構文木を探索し、ノード種別毎の処理を再帰的に呼び出していく」というエッセンスは詰まっている。 PicoML にしたって、最初はこの例のようなコードからスタートして、徐々に変数定義や関数適用のような複雑な機能を追加する形で実装を進めていた。
おわりに
今回のエントリでは、自作プログラミング言語 PicoML について、概要や実装したモチベーションと、簡単な計算式を WebAssembly にコンパイルする流れについて解説した。
他にも WebAssembly AST の取り扱いであったり、ML における環境やクロージャの概念をどのように WebAssembly の世界に落とし込むか、など紹介したいトピックはまだまだ色々あるのだけど、これらに言及しだすとキリが無くなってしまうため、また別に機会に取り上げていきたい。以下でソースコードを公開しているので、興味がある方は読んでみてください。
