Crafting Interpretersを読んだ

2019-12-22
#compiler #book

Crafting Interpreters という、スクリプト言語を作るという内容のオンラインで公開されている本があったので読んでみた。

本の中で実装するのはLoxという動的型付言語で、オブジェクト指向言語でクラス定義や継承などもサポートしている。

実装は2通りで行っていて、本のパート2：ツリーウォークインタプリタではJavaを使って構文木を作ってそれを直接評価する方式、実践的なパート3：バイトコードバーチャルマシンではC言語上でバイトコードを生成して実行する方式を説明している。

ツリーウォークインタプリタ

言語実装の導入的な内容。

スキャナ

スキャナはLexも正規表現も使わずに、文字単位で見ていってトークンをリストに返す。

パーサ

パーサはYaccなどは使わずに、再帰下降法で処理。 ひとつうまい点は、構文木のノードをコードで生成するようにしていて、章が進むにつれて新しい文法を追加する際に簡単に拡張できるようにしている。

インタプリタ（ビジターパターン）

実行はパーサで構築した構文木を順にたどって評価していく。 構文木をたどるにはどうするか。

構文木の各ノードがクラスになっているので、オブジェクト指向的にはベースクラスに仮想関数を定義して、実クラスでオーバーライドして機能を実装する、という方法がある。 しかしこの方法は言語実装にはあまり合わない。 そこでビジターパターンという方法を紹介している。

式のベースクラス Expr に抽象メソッドとしてビジターを受け入れる accept メソッドを宣言：

class Expr {
  abstract <R> R accept(Visitor<R> visitor);

する （戻り値はジェネリックで用途によって変更できるようにする）。

ビジターはインタフェースで、各ノードの場合の処理をメソッドとして宣言する：

//class Expr

  interface Visitor<R> {
    R visitBinaryExpr(Binary expr);  // 二項演算の処理
    R visitUnaryExpr(Unary expr);    // 単項演算の処理
    ...
  }

式を継承した実体クラスのクラス側でビジターのメソッドを呼び出す：

//class Expr

  // 二項演算
  static class Binary extends Expr {
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitBinaryExpr(this);
    }
  }

ビジターの実体は処理したい機能に対してクラスを用意してビジターインタフェースをimplementsし、構文木のノードのタイプごとの処理メソッドを @Override で実装する：

// ツリーウォークインタプリタ
class Interpreter implements Expr.Visitor<Object> {
  @Override
  public Object visitBinaryExpr(Expr.Binary expr) {
    // 二項演算の場合の処理
  }

  ...

起動には accept を呼んでやる：

//class Interpreter

  private Object evaluate(Expr expr) {
    return expr.accept(this);
  }
}

これを呼び出すと、 Exprを継承した実クラスのaccept -> 対応するinterpreter.visitXXXX という二段階の呼び出しで実クラスに対応するメソッドが呼び出される。

このデザインパターンを使うと機能ごとにクラスにまとめられるし、ノードの全種類を実装してないとコンパイラがエラーを出してくれるので漏れないし、非常にうまい方法だなと感じた。

関数、ローカル変数、クロージャ

ナイーブに関数呼び出し、スコープ突入時にヒープに 環境 を作成し、リンクで親環境につなげる。 実行時に環境をたどって操作する。

クロージャも自然に実現できる （すべてヒープ上なので効率はあまりよくない）。

クラス

メソッド呼び出しは this をバインドした環境を生成し、普通の関数のように呼び出すというもの。 動的な環境生成を挟むので、あまり効率はよくなさそう。

親クラスのメソッドを呼び出すための super は、クロージャ同様に使用している静的スコープの親クラスを参照する必要がある。

いろいろエッジケースの実装が大変そうである…。

バイトコードバーチャルマシン

ツリーウォーク版は効率度外視のナイーブな実装でJVMにおんぶにだっこだったが、パート3ではC言語上でバイトコードVM実装という、かなりガチな内容。

VMはスタックマシン方式で、スタックを用いて計算する。

値の表現

値の表現は型の種類＋種類ごとの情報を持つ共用体というまっとうな手法で、tagged pointerのようなトリッキーなことはしてない。

スキャナ

ソースを一括で読み込んでパーサが終わるまでメモリ上に保持しておく。 文字列リテラルはトークン用に別途メモリを確保せずに、ソースの該当部分を指すポインタだけにしている。 メモリ確保をしてしまうと解放を考える必要があるので、うまい方法だなと思った。

パーサ（＆コード生成）：Prattパーシング

C言語版でも式のパースにはJava版と同様に再帰下降法を使って構文木を構築するんだろうと想像していたら違って、 Prattパーシング という方法を使う。 Prattパーシングも実装言語上で再帰はするんだけど演算子の優先度ごとにCの関数呼び出しを行うんじゃなく、テーブルを使って処理中の演算子と次の演算子トークンの優先度を比べて結合を決める。

さらにすごいことに、パースした結果として構文木を作るのではなく、直接バイトコードを生成する！ 先読みができないので実装言語の文法が制限されたり、出力するコードに凝った処理を加えられなかったりという制限が必要になってしまうが、メモリが自前管理だから構文木を作らなければ解放も考えなくて済むのでいい方法だ。

ハッシュテーブル

Java版では HashMap を使ったが、C版では自前で実装する必要がある。

キーを計算するハッシュ関数にはFNV-1a、 衝突した場合には次のスロットをたどるlinear probing、 エントリの削除には墓石（門番）を置く、

キーとなる文字列に対するハッシュ値の計算を毎回行わないようにするため、文字列はすべてインターンしてあらかじめハッシュ値を計算しておく。

制御構造

飛び先をバイトコードのオフセットで持つようにする。 さすがにオフセットが1バイトだけだと厳しいのか、2バイト固定となっている。

命令セットとしてちょっと面白いのは、条件分岐は前方へのジャンプだけしか用意してなくて、後方に戻る場合には無条件ジャンプだけになっている。 do-while 文がないのでそれで十分かもしれない。

ひとつトリッキーなのはfor構文で for (初期化; 条件式; 継続処理) 本体 とあるが、loxは１パスコンパイラでループ本体を処理する前に継続処理のコード生成をする必要がある。 しかし実行処理的には本文を済ませた後に継続処理、そして再び条件式の順に実行する必要がある。 これを処理するために、for 文1回のループで本体末尾から継続処理に、継続処理末尾から条件式部に2度ジャンプを行うコードを生成する。 いいのか悪いのか…。

関数呼び出し：スタックフレーム

関数呼び出し時の引数はスタックに格納して受け渡す。 メモリの動的確保がいらないので効率がよい。

クロージャ：Upvalue

環境をスタックフレームとしてスタック上に割り付ける方式の場合に、クロージャで束縛される変数をどうするか。 スコープを抜けてスタックフレームが解放された後にも束縛された変数にアクセスされる可能性があるので保持される必要がある。

スタックベースのScheme実装で読んだときのように束縛される変数で代入されるものはBoxingでヒープに確保してなんやかんやするのかなぁ、と想像していたがPrattパーサで1パスでコード出力という制限があるので、そうはできない。

結論はUpvalueという方式でクロージャを実装する（これはどうやらLuaのクロージャの実装方法を参考にしているようだ）。 無名関数内で上位のスコープで宣言されている変数が参照されたら、ヒープ上にUpvalueを作成する。 スコープから抜けるときにUpvalueの値をスタックからヒープにコピーして、スタックフレームが解放されても値が保持されるようにする。

クロージャで束縛された変数に対してだけヒープ操作が必要で、それ以外のローカル変数はスタック上だけで済むのでペナルティがない、というのがよいところ。 （ただしScheme実装では代入されるものだけBoxingして、参照だけの変数はコピーを渡していたので、その分は不利だと思う。）

あまりよく動作を理解していないので、また後で読み返したい。

追記：1パスコンパイラでのクロージャの実装方法(Upvalue)

ガベージコレクション：マーク＆スイープ

GCは地道に実装。

オブジェクトをCのローカル変数に保持している状態でGCが走っても回収されないようにするために、一時的にスタックに積んでおく操作が必要になる。

クラス

本がまだ書き途中で、C言語VM版はまだ書かれていない。

Java版ではインスタンスメソッド呼び出し時に毎回 this のバインディングでヒープ確保が必要になっていたが、C版では最初の引数として渡すようにして回避するものと期待。

感想

よかった点：

  • １章ごとにひとつずつ機能を追加しながら動かせる、そして各ステップが大きくない（一部を除き）。
  • 外部ツールを用いずにスクラッチで作成している。
  • 実装する言語仕様が結構本格的。
    • オブジェクト指向サポートがプロトタイプベースじゃなくてクラスベース。
  • クロージャで動的確保が必要になる機能をいかにして効率よく実装するかを説明している。
  • 最下層のメモリ管理・GCまで自前実装して解説している。
  • 説明されているコードがちゃんと動く。

いまいち？な点:

  • ちょっとソースがうまくモジュール化されていない印象を受けた。 VMの命令コードが chunk.h に定義されていたり、オブジェクトの解放処理が memory に定義されていたり、相互に依存している。
  • 実行時のオブジェクト生成時にGCで回収されないために細心の注意が必要。 mrubyのようにアリーナで管理とかできないものか。

しかし全体を通して、いつか「ぼくがかんがえたさいきょうのすくりぷとげんご」を作りたいワナビーとしては、ものすごく参考になるいい内容だった。

参考

関連記事

新着記事