LoginSignup
2
0
@Syuparn

【Onyx】Crafting InterpretersのLox言語を実装してPlaygroundを作ってみた

Posted at

TL; DR

image.png

全機能移植済みです！ぜひ遊んでみてください1。

はじめに

『Crafting Interpreters』は、「Lox」という言語の実装を通じ、手を動かしながら言語処理系の作り方を学べる本です（リンク先は邦訳版）。lexer, parser, evaluatorの説明にとどまらず、レキシカルスコープやクラスの設計等実践的な内容も盛り込まれているのが特徴です。

本書ではLox言語をJavaとCで実装していますが、今回私は Onyxへ移植して写経しました2。本記事では、Onyxに移植した際設計について考えたことやハマった点を振り返りたいと思います。

ソースコードはこちらです。

Why Onyx?

オンライン上でLoxを実行できるPlayground（冒頭で紹介したページ）が作りたかったので、手軽にWebAssemblyへコンパイルできる言語を探していました。また、せっかくならオリジナルと別の言語を使いたかったという動機もあります。

当初RustかGoで作ろうと思っていたところ、Lox実装Wikiなるものを発見しました。

有志が作成した実装が所狭しと並んでいます。Go, Rust, Python, Ruby, TypeScript...メジャーな言語はあらかた移植版がすでに存在しました。
それならばと、昨年末(2023)に出たばかりのOnyxで 別の先駆者が現れる前に 実装したという顛末です。

（最初はかなり不純な動機でしたが OnyxはWASMへのコンパイルに特化した言語なので開発体験はかなり良かったです）

バージョン

  • Onyx: v0.1.9 (記事執筆時点の最新版)
  • Wasmer: v4.2.3
  • wasmer-sdk (js): v0.6.0

設計で考えたこと

以下、Onyxに移植するうえで、Javaとは勝手が違った場所について紹介します。

Lox全体の設計方針については『Crafting Interpreters』文中で解説されているため割愛します。買いましょう（ダイマ）

ASTやLoxObjectのポリモーフィズムをどう表現するか

本家のJava実装では、AST（Expr, Stmt ）やオブジェクト表現 (LoxObject)をインターフェースで表現しています。

Onyxにもインターフェースはあるのですが、言語仕様の制約から2か所本家と設計を変える必要がありました。

Exprをインターフェースで表現できない

1つ目の課題は Expr の実装に関してです。本書では、ASTの式を Expr というインターフェースで表し、その種類に応じて LiteralExpr, BinaryExpr 等の具象クラスを用意しています。

Onyxでは、インターフェース型を使用した場合ジェネリクスのように型引数（ポリモーフィック変数）を記載する必要があります。インターフェースがたとえジェネリックでなくても、具象型自体を表すためのポリモーフィック変数が必要です。

Runnable :: interface (T: type_expr) {
    t as T;
    { t->run() } -> void;
}

そのため、インターフェースを引数に取る場合にもポリモーフィック変数の指定が必要です。where 句を使用し、でその型がインターフェースを実装することを強制します。

// 型をポリモーフィック変数 `T` で表し、where句の制約でTがRunnableを実装することを強制
run :: (r: $T) where Runnable(T) {
    r->run();
}

しかし、インターフェースのシグネチャには現状 where 句が書けないため、インターフェースには自分以外のインターフェースを引数に取るメソッドが定義できません。 Expr は Visitorパターンを使用しているため、以下の実装がコンパイルエラーになってしまいました。

こう書きたいけど書けない
Expr :: interface (T: type_expr) {
    t as T;

    {t->accept(visitor: $T)}

    // where句はここには書けない！
    accept :: (expr: Expr, visitor: $T) -> Result(LoxObject, RuntimeError) where Visitor(T) {
        // ...
    }
}

インターフェースが使えないので、代わりに Exprをタグ付きユニオンで表現することにしました。

src/lox/expr.onyx
Expr :: union {
    Literal: LiteralExpr;
    Logical: LogicalExpr;
    // ...

    accept :: (expr: Expr, visitor: $T) -> Result(LoxObject, RuntimeError) where Visitor(T) {
        switch expr {
            case .Literal as e {
                return visitor->visit_literal_expr(e);
            }
            case .Logical as e {
                return visitor->visit_logical_expr(e);
            }
            // ...
        }
    }
}

戻り値に型パラメータ（ポリモーフィック変数）を使えない

続いて Visitor の実装に関してです。先ほどの例では Expr#accept の戻り値をしれっと Result(LoxObject, RuntimeError) と書いていましたが、元の実装ではジェネリック (Result($S, RuntimeError) ) です。

本書ではInterpreter を Visitor の具象クラスとし、戻り値をジェネリックにする設計を取っています。
しかし、Onyxのインターフェースは戻り値のみに現れるポリモーフィック変数を推論できません。そのため、Visitorを引数に取るメソッド Expr#accept が定義できませんでした。

以下はコンパイルエラー
// インターフェースでVisitorを定義、戻り値はジェネリック
Visitor :: interface (T: type_expr, S: type_expr) {
    t as T;

    { t->visit_literal_expr(LiteralExpr.{}) } -> Result(S, RuntimeError);
    { t->visit_logical_expr(LogicalExpr.{}) } -> Result(S, RuntimeError);
    { t->visit_binary_expr(BinaryExpr.{}) } -> Result(S, RuntimeError);
    // ...
}

Expr :: struct {
    // ...
    // Visitorをとるメソッド
    // $Sが引数側に現れていないので推論できない！
    accept :: (expr: Expr, visitor: $T) -> Result($S, RuntimeError) where Visitor(T, S) {
        // ...
    }
}

コンパイルを通すため、やむなく具象型 Result(LoxObject, RuntimeError) で定義しなおしました3。

src/lox/expr.onyx
Visitor :: interface (T: type_expr) {
    t as T;

    { t->visit_literal_expr(LiteralExpr.{}) } -> Result(LoxObject, RuntimeError);
    { t->visit_logical_expr(LogicalExpr.{}) } -> Result(LoxObject, RuntimeError);
    { t->visit_binary_expr(BinaryExpr.{}) } -> Result(LoxObject, RuntimeError);
    // ...
}

インターフェースとタグ付きユニオンについて詳細はこちらの記事をご覧ください。
(v0.1.8の時に書いたのですでに文法が少し異なりますが、使い分けのイメージをつかんでいただければ...)

ASTの入れ子構造にはポインタが必要

タグ付きユニオンを使うことで Expr や LoxObject を表現できましたが、別の要因で再びコンパイルエラーが発生しました。

Onyxの制約として、構造体の循環定義が禁止されています。

A :: struct {
    b: B;
}

B :: struct {
    a: A;
}

(/home/syuparn/tmp/sample.onyx:8,6) Waiting for type to be constructed.
 8 | B :: struct {
          ^~~~~~

そして、Expr をタグ付きユニオンで実装する場合、Expr と BinaryExpr で循環定義が発生してしまいコンパイルできません。

src/lox/expr.onyx
// 以下はコンパイルエラー
Expr :: union {
    Binary: BinaryExpr;
    // ...
}

BinaryExpr :: struct {
    left: Expr;
    operator: Token;
    right: Expr;
}

回避するために、メンバの型を Expr からポインタ &Expr に変更しました。

src/lox/expr.onyx
BinaryExpr :: struct {
    left: &Expr;
    operator: Token;
    right: &Expr;
}

OnyxにはGCや所有権が無いため、dangling pointerには気を付けましょう (N敗)。忘れたころに謎のランタイムエラーが発生します

ダメな例
right := p->_factor()?;
// right, exprの寿命が関数スコープのため、return時にexpr.left, expr.rightの参照先がfreeされてしまう！
expr = Expr.{Binary=BinaryExpr.{left=&expr, operator=operator, right=&right}};
return expr;

基本的にはAllocatorで寿命を延ばせばスコープを抜けても生き残ります。

修正後
right := p->_factor()?;
// allocateして寿命を延ばす（allocatorを明示的にfreeするまで生き残る）
expr_ptr := p->_alloc_expr(expr);
right_ptr := right=p->_alloc_expr(right)
expr = Expr.{Binary=BinaryExpr.{left=expr_ptr, operator=operator, right=right_ptr}};
return expr;

ポインタについて詳細はこちらの記事をご覧ください。

Expr#hashの実装

Loxでは、正確なレキシカルスコープを実現するため {Expr: クロージャのネストの深さ} の形式のmapを管理しています4。

mapのキー使用する型は、以下のインターフェースを実装する必要があります。

core/container/map.onyx
#local ValidKey :: interface (T: type_expr) {
    t as T;

    { hash.hash(t) } -> u32;
    { t == t       } -> bool;
}

== は hash で簡単に実装できるので、問題は LoxObject#hash です。

Expr をレキシカルスコープ管理のキーとして使用するため、hash では同値性ではなく同一性を担保する必要があります。同値性比較してしまうと、 同じ式を代入した別々の変数のスコープがごちゃ混ぜになってしまうためです。

sample.lox
// 1行目の式 `1` と2行目の式 `1` は別物として扱いたい
// （そうでないと`b` の静的解析の結果が `a` の結果を上書きしてしまう！）
var a = 1;
var b = 1;

Expr は大量にunionを使用しており、真面目に実装すると骨が折れそうです。今回は（手抜きですが）値をオートインクリメントする実装にしました。

src/lox/hash.onyx
// NOTE: スレッドセーフではないので注意！
_hash_value: u32 = 0

new_hash :: () -> u32 {
    _hash_value += 1;
    return _hash_value;
}
src/lox/expr.onyx
Expr :: union {
    Literal: LiteralExpr;
    Logical: LogicalExpr;
    // ...

    hash :: (expr: Expr) -> u32 {
        // switchの構文上同じことを繰り返し書くのはやむなし...
        switch expr {
            case .Literal as e {
                return e._hash;
            }
            case .Logical as e {
                return e._hash;
            }
            // ...
        }
    }
}

BinaryExpr :: struct {
    left: &Expr;
    operator: Token;
    right: &Expr;
    // デフォルト値をオートインクリメントのハッシュにする（他のExprも同様）
    _hash: u32 = new_hash();
}

戻り値の扱い

Lox言語では、関数呼び出しの評価時 return した値を呼び出し元へ戻す際に例外を使用しています。
大域脱出によってASTのネストをジャンプして一気に呼び出し元まで値を返すという仕組みです5。

オリジナル実装のJavaと異なりOnyxには大域脱出が無いため、代わりにエラー値に値を設定できるようにしました。

src/lox/runtime_error.onyx
RuntimeError :: struct {
    message: str;
    token: Token;
    // HACK: returnに使用
    value: ?LoxObject;
}
src/lox/interpreter.onyx
Interpreter :: struct {
    visit_return_stmt :: (interpreter: &Interpreter, stmt: ReturnStmt) -> Result(void, RuntimeError) {
        value := LoxObject.{Null=.{}};
        if !is_empty(stmt.value) {
            result := interpreter->evaluate(stmt.value?);
            if result->is_err() {
                return .{Err=result->err()?};
            }
            value = result->ok()?;
        }

        // HACK: エラーを使用して呼び出し元まで戻り値を返す
        return .{Err=RuntimeError.{value=Optional.make(value)}};
    }
}
src/lox/function.onyx
LoxFunction :: struct {
    call :: (f: LoxFunction, interpreter: &Interpreter, arguments: list.List(LoxObject)) -> Result(LoxObject, RuntimeError) {
        // ...
        result := interpreter->execute_block(f.declaration.body, environment);
        if result->is_err() {
            err := result->err()?;
            // HACK: エラーに値がある場合は戻り値なので取り出す
            if !is_empty(err.value) {
                return .{Ok=err.value?};
            }

            return .{Err=err};
        }
        // ...
}

ところで、大域脱出が無いと聞くと「エラーの持ち回りが大変」だと思われるかもしれません。が、Onyxでは マクロ Result#forward_err によってエラー値のみ早期リターンできるため、例外と同じくらいシンプルに記述できました。

// evaluateは `Result(LoxObject, RuntimeError)` を返すが、forward_err() によって
// 値の場合：LoxObjectを返す
// エラーの場合：早期リターン
obj := interpreter->evaluate(*expr.object)->forward_err();

詳しくはこちらの記事をご覧ください。

テスト

言語処理系は一か所にバグがあるとドミノ倒しで他の場所にも不具合が出てしまいます。つらい気持ちにならないよう、適宜テストを書きながら移植していました。

（本書にテストコードは無いのでこちらは自前実装です）

ユニットテスト

Onyxとしてテストの取り決めは今のところなさそうなので、Goのテストの書き方を参考にしました。

  • *_test.onyx にテストファイルを作成
    • ※言語にテストの機能があるわけではないため、あくまで *_test.onyx の名前のmain関数を実行しているだけ
  • テストケースはテーブル駆動で作成
Makefile
.PHONY: test-unit
test-unit:
	find src/ -name "*_test.onyx" | xargs -I{} onyx run {}
token_test.onyx
test_token_to_string :: () => {
    TestCase :: struct {
        token: Token;
        expected: str;
    }
    // テストケースのスライス
    tests := TestCase.[
        .{token=Token.{type=TokenType.AND, lexeme="&", literal=TokenLiteral.{Null=.{}}, line=1}, expected="AND & Null"},
        .{token=Token.{type=TokenType.STRING, lexeme="\"foo\"", literal=TokenLiteral.{String="foo"}, line=1}, expected="STRING \"foo\" String(\"foo\")"},
        .{token=Token.{type=TokenType.NUMBER, lexeme="123", literal=TokenLiteral.{Number=123}, line=1}, expected="NUMBER 123 Number(123.0000)"},
        .{token=Token.{type=TokenType.TRUE, lexeme="true", literal=TokenLiteral.{Bool=true}, line=1}, expected="TRUE true Bool(true)"},
        .{token=Token.{type=TokenType.NIL, lexeme="nil", literal=TokenLiteral.{Null=.{}}, line=1}, expected="NIL nil Null"},
    ];

    for tt in tests {
        // 組み込み関数のassertで検証（第二引数は失敗した場合のエラーメッセージ）
        assert(tprintf("{}", tt.token) == tt.expected, tprintf("\"{}\" != \"{}\"", tprintf("{}", tt.token), tt.expected));
    }
}

統合テスト

クラスやオブジェクト等のふるまいをテストする際は結合テストの方が都合が良いので、bats を使用しました。

batsはBash製のテストフレームワークで、コマンドの終了ステータスや出力内容をテストすることができます。ここでは、Loxを実行した際の出力結果を検証しています。

tests/testdata/src/instance_fields.lox
class Foo {}

var foo = Foo();

foo.bar = 123;
print foo.bar;

foo.bar = 456;
print foo.bar;
tests/class.bats
@test "instance fields" {
  run wasmer run --mapdir tests:tests onylox.wasm -- tests/testdata/src/instance_fields.lox
  assert_output "123"$'\n'"456"
}

また、テスト作成時にはLoxのシンタックスハイライト拡張機能を入れると開発がはかどります（製作者の方に感謝！）。

Playground作成

次に、本題のPlayground構築についてです。OnyxからWASMへのコンパイルは簡単でしたが、ブラウザ上で動かすまでにも少しハマりどころがありました。

wasmへのコンパイル

ターゲット

Onyxのコンパイルターゲットは3種類あります。

  • onyx: Onyxに特化した専用の形式
  • wasi: WASIX形式（※WASIではない！）6、Wasmer等で動く
  • js: ブラウザ上で動く

当初 js で試していましたが謎のエラーでクラッシュしてしまったので、wasi ターゲットを動かす方針で進めました。

wasi ターゲットはブラウザ用の形式ではありませんが、Wasmer SDKを使うとWASIを手軽にブラウザ上で動かせます。

Wasmer Registryへの登録

SDKから呼び出す事前準備として、Wasmer Registryにパッケージを登録する必要があります。

onyx build -r wasi でwasi形式にビルドしたwasmファイルを wasmer.toml とともにアップロードしました。GitHub Actions上だとログインが上手くいかなかったため、やむなくローカルから wasmer publish しました。

wasmがGitHub Pagesで動かない！

ビルドはできましたが、ブラウザ上で実行するまでにもうひと手間必要でした。

読み込み失敗→COOP, COEPヘッダを追加

（WebAssemblyを使っている方にはおなじみかもしれませんが）wasmファイルの読み込みには以下のレスポンスヘッダーを設定する必要があります。

  • Cross-Origin-Opener-Policy: same-origin
  • Cross-Origin-Embedder-Policy: require-corp

wasm実行では SharedArrayBuffer を利用しています。しかし、ブラウザ側はセキュリティ対策として SharedArrayBuffer が動作できる条件を「同じオリジンからしかオブジェクトを参照できない状態」に限定しているためです。

GitHub Pagesではユーザーがリクエストヘッダを制御することができないため、Service Workerを使用してヘッダを追加しました。

仕組みが複雑なので、詳細な仕組みは以下の参考記事をご覧ください。

document is not defined→モジュールを動的にimport

上記対応後、wasmを実行すると以下のエラーが発生するようになりました。

ReferenceError: document is not defined

WASMの起動をworker上で行うため、worker threadからDOMを参照できない場合に上記エラーが発生します。
解決するためには、Wasmer SDKを動的importに変える必要がありました。

before
import { init, Wasmer } from "@wasmer/sdk";

export async function initLox(): Promise<(source: string) => Promise<LoxResult>>{
  await init()
  const pkg = await Wasmer.fromRegistry('syuparn/onylox')

  // ...
}
after
xport async function runLox(source: string): Promise<LoxResult>{
  // ここで動的にimport
  const { init, Wasmer } = await import("@wasmer/sdk");

  await init()
  const pkg = await Wasmer.fromRegistry('syuparn/onylox')
  // ...
}

ここまでの対処は、SDK公式リファレンスを参考にしました。

色々な不具合を乗り越えて、ようやくPlaygroundが動きました！

image.png

おわりに

以上、Onyxで『Crafting Interpreters』のLox言語を実装してみた紹介でした。ハマりどころも多かったですが、言語実装とOnyx言語の習得を同時に進められたので一石二鳥でした。
また、実際にOnyxを使ってみて

  • 学習コストが低い
  • プログラムからコンパイル先のwasmがイメージしやすい

と感じました。今後wasmで何かツールを作る際には積極的に採用したいと思います7。

ここまでお読みいただきありがとうございました。

  1. 余談ですが、Playgroundのデザインは Lox (=サーモン)にちなんで鮭っぽい配色にしました。 ↩

  2. 正確にはインタープリタ編を読み終わりました。VM編も別の機会に挑戦したいです。 ↩

  3. ASTPrinter については、str の代わりに LoxObject でラップした文字列リテラルを返しています。 ↩

  4. 正確には、現在のスコープと変数定義個所のスコープの階層がいくつ異なるかを格納しています。 ↩

  5. 類書の『Go言語でつくるインタプリタ』の方では戻り値を別オブジェクトにラップすることで識別していたので新鮮でした。処理系の設計はホスト言語の仕様に強く影響を受けるのですね。 ↩

  6. WASIXはWASIのスーパーセットで、Wasmer社が主導で仕様策定しています。WASIXは標準のWASIのランタイムでは動かないので要注意です。 ↩

  7. ただし、現在beta版なので文法に破壊的変更が入る点に要注意です。v0.1.9でも for や switch の構文が変わりました。 ↩

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0