夏のインターン講義「1営業日で書くJavaScriptコンパイラ」の設計と実装

今年、クックパッドでは夏のインターンと題して20名弱のインターンを受け入れました。 このインターンは前半と後半に大きく分かれており、 後半が社員に混じって業務をするいわゆる普通のインターンで、 前半は7日間にわたってプログラミング関連の講義を受けるという仕組みです。

わたし（青木）はその前半の過程において、「プログラミングパラダイム」という 1 日の講義を担当し、 JavaScriptの処理系を書くという、ツッコミどころの多い課題を実施しました。 本稿では、その講義を開発する際に考慮したこと、特に難易度調整についてお話しします。 また講義のために開発したJavaScript処理系「JetSpider」についても軽くふれます。

▼講義資料

講義のコンセプト

「プログラミングパラダイム関係でなんかやって、1日で」という注文を聞いて最初にわたしが思ったことは、 「それは無理だろ」この一言に尽きます。「関数型」だの「オブジェクト指向」だのと言った プログラミングパラダイムの話をゼロから講義するなんて1日でできるわけないですし、 パラダイムの背後にある言語の話を4つか5つはこなす必要があります。 どう考えても分量的に無理であることに加え、完全に講義になってしまい、面白くありません。

ではどうするか。

こういうときのわたしの戦略はだいたい決まっていて、 なんとかギリギリ許されるかもしれない範囲でテーマを勝手に極大解釈することにしています。 今回は、「プログラミングパラダイム……を学ぶうえでの礎になることならなんでも可」 という文言を脳内で勝手に付与して、言語処理系の話をすることにしました。 わざわざわたしに振ってきたということは、たぶん言語処理系っぽい内容が 期待されているのだろうな（わたしは言語処理系の本を何冊か書いているので）というメタな読みも働いていました。

わたしの講義資料を見ていただければわかるように、 なぜプログラミングパラダイムで言語処理系の話をするのか…… といった雰囲気の話が冒頭に書いてあっていくらかそれっぽく見えるのですが……

まあ、ぶっちゃこのへんは全部後付けですね！！ 結論を先に決めてあとから書きました。

講義におけるUXの設定

言語処理系で何か講義をしようと決めましたが、もう少し具体化しなければいけません。 具体的に課題を決めるうえで考えたことは、なによりも、 「できるだけマゾい（つらい）課題にしよう」ということでした。

ここで言う「マゾい」とは、分量が多いということではなく、 全力で考えないと対処できない、ということです。 わざわざあえてマゾくするのは、わたしの趣味……ではなく、 困難な課題のほうがやりきったときの達成感がある、難しいほうが楽しい、という信念によります。 UX的に言うと、次のような体験を得てほしいと思ったわけです。

f:id:mineroaoki:20151020135407p:plain

また、わたし以外の講義はどれも入門的な内容や半日の講義だったため、 難易度を上げるならこの講義しかないだろうなという思惑もありました。

ですからわたしの講義のコンセプトは「とにかくマゾく！」。 ちょうどわたしの講義は前半最後の日だったので、 この講義のラスボスとなってインターン生を地獄に叩き落とす気持ちで講義を作りました。 いたいけなインターンたちを苦しませるのは超たのし……心が痛みますが、 インターン全体のクオリティを上げるためにはやむをえません。

課題を具体化する

さて、そんなことを頭の片隅に置きつつ、 3日くらい他のことをやりながら考えたマゾい課題の一例がこちらです。

  • JavaアセンブラだけでHaskellインタプリタを書く
  • Prologの処理系をOCamlで書く
  • ネイティブコードコンパイラを設計・実装する
  • x86アセンブラでインタプリタを書く

いやいやいやいや……。

これは無理だろ！！！（一人ツッコミ）

いくらマゾくすると言っても、誰もやりきれない課題にしてしまっては意味がありません。 こんな酷いリストの中でも「JavaScriptの処理系を実装する」という 課題は比較的無難そう（？）だったので、これに仮決めしました。

ですがJavaScript処理系という課題にしても「全部書け」だとやはり分量が多すぎますから、 やるなら処理系の一部だけにすべきでしょう。具体的には処理系のモジュール 1 つ…… つまり、パーサー、コードジェネレーター、VM、インタープリターの評価器、のどれか、くらいが妥当だろうと当たりを付けました。 そしてパーサーはわりとよくある話ですし、言語処理系以外でもさわる機会があるので、 コードジェネレーター（構文木からターゲットのコードを生成するモジュール）を書いてもらうことにしました。

それに、コードジェネレーターならばバイトコードをさわる機会も作れます。 きっと最近の若者はバイトコードのようにオフセット計算が必要だったり制御構造がgotoしかないような言語には それほど慣れていないでしょうから、効果的にマゾくできることが期待できそうです。

ソース言語を決める

処理対象の言語（ソース言語）の選定については、次のような基準で選びました。

  1. 多くの人が言語を知っていること（ソース言語の仕様を調べなくていいから）
  2. マルチパラダイムである（例えばJavaだとOOPすぎる）
  3. 基本部分がそれほどリッチでなく動的型付け（実装が楽になるから）
  4. 見ためがあまりRubyに似ていない（Rubyはコンパイラを書くのに使うので混乱を避けたい）
  5. バイトコードVMの実装がすでにある（自力実装するのはダルい）

1でLisp、Haskell、OCamlが消え、2と3でJava、C#、Cが消え、3と4でRubyとPythonが消えて、 3、4、5でPerlが消えます。残るのはJavaScriptくらいなので消去法でJavaScriptになりました。

さきほど述べたように、バイトコードを生成させると決めた時点でかなりマゾくなっているはずなので、 このあたりで難易度を上げることは避けて、できるだけ無難に選びます。

記述言語を決める

コンパイラ自体を何の言語で書くかも重要です。例えばHaskellで書くとしたら、 （あまり知らない）Haskellを覚えながら（あまり知らない）コンパイラを書くということになってしまい、主眼がブレます。 今回のインターンでは、スマホアプリ以外はRubyで書く講義が多かったので、 ここも無難にRubyで書いてもらうことにしました。

そして偶然ですが、RKellyという Ruby製のJavaScriptパーサーも見付けたので、 これを使えばパーサーは書かなくて済みそうという点も大きなポイントでした。 コンパイラのモジュールの中でもパーサーはちょっと面倒ですから、 ここを省けると開発の手間を大きく削減できます。

JavaScriptのVMを決める

以上で課題の大枠は決定しました。 即ち、「JavaScriptコンパイラのコードジェネレーターをRubyで書く」です。

残る課題はコンパイラの残りの部分とVMを用意することです。 コンパイラは適当に書けそうな目処が立っているので、VMをどうにかしなければいけません。 JavaScriptのVMなんてそのへんに死ぬほど転がっているので適当に選べばよいだろうと たかをくくっていたのですが、なかなかどうして意外とぴったり目的にかなうものがありません。

  • みんな大好きGoogle V8はJavaScriptを直接機械語にコンパイルするのでバイトコードを経由しない
  • WebKitのJSエンジン（JavaScriptCore）はWebKit内蔵なのでWebKitが全部必要になって超ダルい
  • Rhinoはバイトコードが露出してないのと、JVMの面倒な話（クラスローダーとか）に関わりたくないのと、できれば最終的にネイティブコードにまで落ちるVMを選びたい
  • FirefoxのJSエンジン（SpiderMonkey）もバイトコードが露出していない

そんな中でもDukTapeという組み込み向けJS処理系はコンパクトで バイトコードを突っ込むインターフェイスもあり、ドキュメントも揃っていて なかなかよさそうだったのですが、今回は最終的にSpiderMonkeyを選びました。

そのときの決め手はズバリ、「作るのが面白そうだから」です。 VMのコードに触れるのわたしだけであり、講義の難易度には影響しないので、ここは完全に自分の趣味で決めました。 きれいでコンパクトで最小限の機能のほうが楽であろうことはわかっているのですが、 しかし、そんなものはさわってても（わたしが）面白くありません。 どうせいじるなら、巨大でユーザー数が多くて高速な本気のコードをさわりたいのです。

なお、いちおう追加の言い訳をしておくと、コンパイラを作る側の気持ちを考えても、 いかにも講義のために作ったような半端なVMをターゲットにするのでは楽しくないだろうと思います。 たとえコンパイラ側が 1 日で作ったざっくりコンパイラであっても、 VMさえ速ければそれなりの速度を出すことができます。 どうせなら十分に手のかかっている強力なVMを使ったほうが面白いでしょう。

ちなみにSpiderMonkey単体のソースコードはこのへんから入手できます。 Firefoxを全部コンパイルするとか心底やりたくないので、これは大変嬉しいですね。 コンパイルはわりと普通に ./configure ; make で通ります。 このあたりがすんなり行けたこともSpiderMonkeyを選んだ理由の1つです。

JetSpider VMのアーキテクチャ

ここで、今回講義のために作成したJavaScript処理系ーーJetSpiderーーのアーキテクチャを簡単に紹介します。 結論から言うと、JetSpiderは次のようなアーキテクチャになっています。

f:id:mineroaoki:20151020135413p:plain

SpiderMonkeyを単体のバイトコードVMとして使ううえで最大の問題は、バイトコードが露出していないことでした。 SpiderMonkeyのAPIリファレンス を眺めてもらえるとわかるのですが、 JavaScriptのソースコードをコンパイルしたりファイルから読み込むAPIはあっても、 コンパイル後のバイトコードを保存したり、ロードしたりするためのAPIがありません。

せいぜい使えそうなAPIと言えば、 バイトコードを保持する内部データ構造であるJSScript構造体を実行する JS_ExecuteScript関数 くらいでしょうか。 つまり、Javaで言うクラスファイルのような、オブジェクトファイルに類するものが足りないわけです。 そこは自力で実装してやる必要がありそうです。

最初は適当にJSScript構造体のメンバを全部吐けばどうにかなるだろうと思っていたのですが、 実際に手をつけてみたらあまりにも面倒で嫌になってしまいました。 そこで手当たりしだいにソースコードをgrepしまくったところ、 XDR（eXternal Data Representation）という データ直列化の仕組みが実装されていることに気付きました。

XDRという概念は歴史的にはSun RPCが由来っぽく、 XDR APIというAPIを使うことで様々なデータ構造を直列化できます。 そしてSpiderMonkeyでも、非公開関数のJS_XDRScript関数を呼べば、 JSScript構造体をセーブ・ロードできることがわかったのです。

（え、非公開なのにどうやって呼ぶかって？ そんなの、extern付けて再コンパイルすればいいでしょ！！ 具体的には SpiderMonkey.diff をごらんください）

つまり、あとはRubyからこのXDR仕様のフォーマットでJSScript構造体を吐いてやり、 それを読み込んで実行するだけの簡単なラッパーを書けば済むわけです。 Rubyからバイナリを吐くのはひたすらpackしまくるだけの簡単なお仕事ですね。 JetSpiderでは以下のようなコードでオブジェクトファイル生成を実装しました。

      def serialize_JSScript(f)
        f.uint32 JSXDR_MAGIC_SCRIPT_CURRENT
        f.uint16 local_variables.size
        f.uint16 arguments.size
        f.uint16 upvars.size
        f.uint16(padding = 0)
        f.uint32(*vars_bitmap)
        var_names.each do |name|
          f.jsstring name
        end
        code = bytecode()
        f.uint32 code.length
        f.uint32 prolog_length
        f.uint16 JS_VERSION
        （以下略）

f.uint32やf.uint16は内部でpackを使ってバイナリを出力するDSLです。

これでVM側の実装も目処が立ちました。

可視化で難易度を下げる

効率的に講義を進めるために、コンパイラ・VMの両方で特に気を付けていた点があります。 それは、とにかくできる限りのデータと動作を可視化するということです。

JetSpider（今回講義のために作成したJavaScript処理系）では、コンパイラもVMも、 コマンドラインオプションを指定することでほとんどあらゆるものをダンプできます。 例えば--dump-astオプションで構文木をダンプ、--dump-semオプションで意味情報付き構文木をダンプ、などです。 VMのほうも、--disassembleオプションを付けるとコードを逆アセンブル、--traceオプションでVMの命令をトレースすることができます。

▼--dump-astオプションによるAST可視化

% ./bin/jetspider --dump-ast exp/arith.js
type: SourceElementsNode
value:
- type: FunctionDeclNode
  value: f
  arguments:
  - type: ParameterNode
    value: x
  function_body:
    type: FunctionBodyNode
    value:
      type: SourceElementsNode
      value:
      - type: ReturnNode
        value:
          type: AddNode
          left:
            type: NumberNode
            value: 1
          value:
            type: MultiplyNode
            left:
              type: ResolveNode
              value: x
            value:
              type: NumberNode
              value: 3

今回の講義では、コードジェネレーター以外はすでに用意されています。 言い換えると、コードジェネレーター以外は自分の知らないコードなわけです。 すべてのコードを読まないと動作が理解できないようだとやはり 1 日では終わらなくなるので、 残りの部分については、ソースコードを読まずとも内部動作を理解できるようにしておく必要があります。 その手段が可視化です。

以前に言語処理系の本を書いたときに、 可視化を充実させれば処理系が容易に理解できることはわかっていましたから、 言語処理系の課題を出すと決めた時点で徹底的に可視化することも決めていました。

逆アセンブルで難易度を下げる

可視化機能を充実させたことで、わたしの開発も楽になりました。 特に役立った機能がVMに付けた逆アセンブラです。 SpiderMonkeyのコンパイラにコンパイルさせたバイトコードを逆アセンブルすると 「正解」のコンパイル結果がわかるので、コンパイラの実装が凄まじく簡単になるのです。 例えば次のような簡単なif文のコンパイル結果を逆アセンブルすると下記のような出力が得られます。

▼if文

if (1 < 3) {
    print(7);
} else {
    print(9);
}

▼コンパイル結果の逆アセンブル

main:
00000: 3f         one 
00001: dd 03      int8 3
00003: 14         lt  
00004: 07 00 10   ifeq 20 (16)
00007: d9 00 00   callgname "print"
00010: dd 07      int8 7
00012: 3a 00 01   call 1
00015: 02         popv
00016: 06 00 0d   goto 29 (13)
00019: bd         nullblockchain
00020: d9 00 00   callgname "print"
00023: dd 09      int8 9
00025: 3a 00 01   call 1
00028: 02         popv
00029: c5         stop

ここまでわかっていれば、ほとんど何も考えずに実装できますね！

ここで手を抜けたおかげで、コンパイラはコードジェネレータの参考実装を含めてほぼ 2 日で実装できました。 あたかもすでにテストが実装されているTDDのようなものです。 このプロセスがあまりにラクで楽しかったので、講義でもこの方式を大々的に取り入れたくらいです。

ただ、この手法にはちょっとした罠もあります。 SpiderMonkeyのコンパイラが賢いおかげで、いかにもテスト用っぽい簡単なコードを書くと、 定数たたみこみ最適化によってプログラムがことごとくシンプルに変形されてしまい、 目的のコードがわからなくなるのです。

▼簡単すぎるコードを書いてしまうと……

print(1 + 2);

▼足し算が消滅してしまう

main:
00000: d9 00 00   callgname "print"
00003: dd 03      int8 3
00005: 3a 00 01   call 1
00008: 02         popv
00009: c5         stop

この最適化の罠は講義においても猛威を奮い、多くのインターン生が苦しみました。 今度また同じ講義をやるときには、最適化をオフにする実装を入れておきたいところです。

まとめ

本稿では夏のインターンで行った「プログラミングパラダイム」の講義について、 そのコンセプトと設計、および実装をお話ししました。

実習を含む講義の設計は難易度の調整が肝だとわたしは考えています。 難しくするための要素（バイトコードの生成）とそれ以外の要素（記述言語など）とで扱いを明確に分けて、 難しくするところ以外はできるかぎり理解しやすくする工夫をする、というところがポイントでしょう。 今回は幸いにもそこの難易度調整がうまくできたようで、 6割くらいのインターン生が時間ギリギリで全部の課題を終わらせることができました。

ちなみに、インターン生の中にも言語処理系に慣れている人と慣れていない人がいたので、 「追加課題」というかたちで課題数を増減させることでも多少難易度が変わるようにしておきました。 しかし、こちらはだいぶ自由選択にまかせたこともあり、それほどうまくいかなかったように思います。 次に同じような課題をやることがあれば、講義の運用についてももう少し詰めておきたいところです。

（青木峰郎 / Minero Aoki）