Lox (Crafting Interpreters)にdefer文を追加する

Crafting InterpretersはRobert Nystromによるインタプリタ方式のプログラミング言語処理系の作り方の解説本である。
ハードカバー・電子書籍が発売されているほか、著者のページでWeb版が無料公開されており、自作言語界隈では人気を博している。
Crafting Interpretersでは著者が考案したLox言語のインタプリタを実装していくこととなる。本の前半部分ではAST評価器を扱い、後半部分ではバイトコードVMを用いたインタプリタを実装する。
Lox言語はシンプルとはいえ、クロージャやクラスの継承といった高度な機能も備えたオブジェクト指向スクリプト言語であり、読者は小さなインタプリタからステップ・バイ・ステップでだんだんと完全な処理系を構築していく。
Crafting Interpretersの素晴らしいところには次の点が挙げられるだろう:

  • 平易な文章に加えて豊富な例とイラストによってインタプリタの実装を分かりやすく伝えることに成功している
  • それにもかかわらず、自前のGCやNaN Boxingのような高度な話題も提供している
  • 公式のGitHubリポジトリで網羅的なテストケースを公開しており、読者が自分の実装の完全性を確かめられる

大変教育的な本なので言語処理系に興味のある人はぜひ一度挑戦してみるのがよい。

さて、私は先月ごろCrafting InterpretersのバイトコードVMのRust実装に挑戦しており、公式のテストケースが全て通るところまで完成していた*1。
この記事ではVMのコード実装に手を加えることでGo言語のdefer文をLoxに導入してみる。

まずは例を見るのが分かりやすいだろう。

{
    var i = 100;
    defer {
        print i; // expect: 300
    }
    i = 300;
}

このプログラムでは、deferの直後に指定したブロックが、スコープの終わりまで遅延して実行され、結果としてprint文が300を出力する。（本来Go言語でのdeferは関数末尾で実行されるのだが、今回の記事ではスコープの終わりで実行することにした。理由は読めば分かる）

実はLoxにdeferを追加するのは非常に簡単である。LoxのバイトコードVMはスタックマシンであり、またローカル変数はスタック上の位置で表現される*2。
例えば、

fun f() {
    var a = "foo"; // "foo"がスタックの1番目に積まれる
    {
        var b = "bar"; // "bar"がスタックの2番目に積まれる
        print(a + b); // expect: foobar
        // "bar"がpop
    }
    // "foo"がpop
}

というプログラムでは、ローカル変数aがスタックの1番目に、bがスタックの2番目に対応している。
実はスタックの0番目も存在し、それは関数fに対応する。
ローカル変数に対応するスタック上の位置は静的に決定できるため、生成されたバイトコードには変数名はもはや存在せず、必要なのは計算した位置だけというわけだ。

このローカル変数とスタック上の位置の対応を維持するため、スコープの終了時にはそのスコープに含まれている変数の数だけスタックから値をポップしてあげる必要がある。
言い換えれば、LoxのバイトコードVMにはすでにスコープの終わりに任意の処理を実行する仕掛けが搭載されているのである！
実際、Crafting Interpretersではこの仕掛けを使うことで、クロージャのキャプチャする変数がスコープから抜ける際に参照がダングリングしないよう繋ぎ変える処理を行っている。

この仕掛けを再利用してやると、次のようにdefer文が実現できる:

  1. defer文のブロックを0引数関数としてコンパイルする
  2. その関数で初期化される特別な無名のローカル変数を追加する
  3. このローカル変数がスコープから抜ける際、スタックからポップする代わりに関数を呼び出す

疑似コードで書くと次の通り:

{
    var i = 100;
    var __defer = fun() {
        print i; // 無名関数はローカル変数iへの参照をキャプチャする
    }
    i = 300;
    // __deferがスコープから抜けるので、関数として呼び出す: __defer()
    // iがスコープから抜けるのでpop
}

この実装のためには、バイトコードコンパイラでローカル変数を扱う際にdeferで生成された特別なローカル変数かどうかを表すフラグを追加してさえあげればよい。
スコープの終了時に、変数のフラグが立っていたらdefer関数とみなして関数呼び出し命令を発行し、そうでなければ単にポップ命令を発行することで実装が完了する。
関数呼び出し命令はリターン時に関数をスタックからポップしてくれるのでそれもちょうどよい。

実は、関数を呼び出すためにはスタックを調整する必要があるのだが、deferのケースではその必要も無い。
上でスタックの0番目が関数に対応していると述べたことを覚えているだろうか？
deferを実行するタイミングでは、deferで呼び出す関数がスタックのトップに来ており、またこの関数は0引数なのでスタックの調整をせずにそのまま呼び出せるのだ。

ということを昨晩ベッドの中で思いついたので今日実装してみたというわけ。実装も30分ぐらいで済んだ割にはdeferという非自明な機能が実現できたのでとても満足だ。
実装のdiffはこんな感じ:
github.com
まあ、この処理系ではファイル等のリソースが存在しないのでdeferが活躍する場も無いのだけれど…

*1:ソースコードは https://github.com/pandaman64/rlox で公開している

*2:原著ではイラストも含めて分かりやすく説明されているからぜひ読もう。自分には絵心が無かった…