Crafting Interpretersの言語実装をRustで進めている話

Rustアドベントカレンダー（その1）3日目の記事です。

qiita.com

id:udzura と申します。Rustは2021年になると同時に始めたので、いまだ経験1年未満ですが、僭越ながらも今回アドベントカレンダーに参加いたします。

今回はタイトルの通り、RustでCrafting Interpretersを進めている話です。Crafting Interpretersとは、Loxと名付けられたインタプリタ言語をJavaやCで実装していき、その過程で言語実装の肝要を学ぶことができるという書籍です。Web版は無料で閲覧できます。

craftinginterpreters.com

現在II章まで終わり、実装はGitHubにアップしています。 Lox本体のソースコード部分 と同じMITライセンスにしています。

github.com

この記事では、進めた上で工夫した点、頑張った点を小学生の日記のように残していきます...。

Visitorパターンの実装

まず、II章の実装の元のコードはJavaです。なのでOOPらしくパターンがいくつか出てきます。Visitorパターンはふつうのコンパイラを作ろうなどにも出てきており、言語実装でASTを辿っていくような場面でよく見かけるようです。

Rustにおいては、まず、ExprやStmtを表現するタプル型を作り、

pub type ExprP = Box<Expr>;
pub type ExprV = Vec<Expr>;
// ...

#[derive(Debug, Clone)]
pub struct Assign(pub TokenP, pub ExprP);
#[derive(Debug, Clone)]
pub struct Binary(pub ExprP, pub TokenP, pub ExprP);
#[derive(Debug, Clone)]
pub struct Call(pub ExprP, pub TokenP, pub ExprV);
#[derive(Debug, Clone)]
pub struct Get(pub ExprP, pub TokenP);
//...

このタプルを包み込むenumを作成しました。

#[derive(Debug, Clone)]
#[non_exhaustive]
pub enum Expr {
    Assign_(Assign),
    Binary_(Binary),
    Call_(Call),
    Get_(Get),
    Grouping_(Grouping),
    Literal_(Lit),
    Logical_(Logical),
    Set_(Set),
    Super_(Super),
    This_(This),
    Unary_(Unary),
    Variable_(Variable),

    Null,
    Dummy,
}

Visitorはtraitと関連型で実現し、それぞれの関数の引数にはenum Exprではなく、型を解いた後のタプルを取るようにしました。

pub trait ExprVisitor {
    type R;

    fn visit_assign(&mut self, expr: &Assign) -> Self::R;
    fn visit_binary(&mut self, expr: &Binary) -> Self::R;
    fn visit_call(&mut self, expr: &Call) -> Self::R;
    fn visit_get(&mut self, expr: &Get) -> Self::R;
    fn visit_grouping(&mut self, expr: &Grouping) -> Self::R;
    fn visit_literal(&mut self, expr: &Lit) -> Self::R;
    fn visit_logical(&mut self, expr: &Logical) -> Self::R;
    fn visit_set(&mut self, expr: &Set) -> Self::R;
    fn visit_super(&mut self, expr: &Super) -> Self::R;
    fn visit_this(&mut self, expr: &This) -> Self::R;
    fn visit_unary(&mut self, expr: &Unary) -> Self::R;
    fn visit_variable(&mut self, expr: &Variable) -> Self::R;

    fn visit_null(&mut self) -> Self::R;
}

// match 文で簡単に取り出せる
impl Expr {
    pub fn accept<T>(&self, visitor: &mut T) -> <T as ExprVisitor>::R
    where
        T: ExprVisitor,
    {
        use Expr::*;
        match self {
            Assign_(expr) => visitor.visit_assign(expr),
            Binary_(expr) => visitor.visit_binary(expr),
            Call_(expr) => visitor.visit_call(expr),
            Get_(expr) => visitor.visit_get(expr),
            Grouping_(expr) => visitor.visit_grouping(expr),
            Literal_(expr) => visitor.visit_literal(expr),
            Logical_(expr) => visitor.visit_logical(expr),
            Set_(expr) => visitor.visit_set(expr),
            Super_(expr) => visitor.visit_super(expr),
            This_(expr) => visitor.visit_this(expr),
            Unary_(expr) => visitor.visit_unary(expr),
            Variable_(expr) => visitor.visit_variable(expr),
            Null => visitor.visit_null(),
            _ => panic!("[BUG] invalid type of expr."),
        }
    }
}

この方針でII章の実装を完走できたので、悪くはなかったのではないかと思います。

ただ、元のJavaのコードはこの部分はコード生成で、Rust移植版でも実装が進むにつれExprのタイプの追加に伴い手を加える箇所が増えてしまいました。Rust版のも build.rs で生成する風にしても良かったのかも。マクロもいけるのかな、力がないのでちょっと...。

Object への対処

II章では、Lox内での値の型がそのまんまJavaの型に対応するような設計思想となっています。したがって、Loxの値を扱う箇所ではObjectを引数に取ったり返すメソッドが要所要所で出てきたり、アップキャストやダウンキャストも割と出てくるコードとなります。

Rustでそれは困ったのですが、言語内部の型をAny traitで実現するよりは Value という型を導入してしまうことにしました。

#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub enum Value {
    // Object(Box<dyn Any>),
    Nil,
    Boolean(bool),
    Number(f64),
    LoxString(String),
    LoxFunction(Function),
    LoxClass(Class),
    LoxInstance(Instance),
}

関連してというか、たとえばこのメソッド内のこの変数はnullになりうるかならないのか？、あるいは変更されるのかされないのか？、などが読み進むにつれて判明するので、定義を遡って変更する必要が出て、手戻りのようになって困ることはありました。先に一通り全体を読んで進めたほうがよかったのかも。

Callableトレイトへのアップキャスト

Loxでは「呼び出すことができる」型として、FunctionとClassが存在します。Java版では両方がLoxCallableインタフェースを実装しています。同様にRust版でも、CallableトレイトをFunctionとClassという型に実装させました。

しかしRustはアップキャストが簡単ではないので、こういうとき、どうやって呼び出し部分のコードが冗長になるのを避けようかと悩みました。が、共通処理を impl Callable を取る関数に抜き出せば済むと気づきました。

pub trait Callable {
    fn arity(&self) -> u8;
    fn call(
        &self,
        interpreter: &mut Interpreter,
        arguments: &[Value],
    ) -> Result<Value, RuntimeBreak>;
}

impl ExprVisitor for Interpreter {
    fn visit_call(&mut self, expr: &Call) -> Self::R {
        let callee = self.evaluate(expr.0.as_ref())?;
        let mut arguments: Vec<Value> = vec![];
        for v in expr.2.iter() {
            arguments.push(self.evaluate(v)?);
        }

        // 関数内で関数を定義すれば保守しやすい
        fn invoke_callable(
            this: &mut Interpreter,
            value: impl Callable,
            arguments: &[Value],
            expr: &Call,
        ) -> Result<Value, RuntimeBreak> {
            if arguments.len() != value.arity() as usize {
                return Err(RuntimeBreak::raise(
                    expr.1.as_ref().to_owned(),
                    &format!("..."),
                ));
            }

            value.call(this, arguments)
        }

        match callee {
            // Callable な型の時だけそれぞれ invoke_callable() を呼ぶ
            Value::LoxFunction(function) => invoke_callable(self, function, &arguments, expr),
            Value::LoxClass(class) => invoke_callable(self, class, &arguments, expr),
            _ => Err(RuntimeBreak::raise(
                expr.1.as_ref().to_owned(),
                "Can only call functions and classes.",
            )),
        }
    }
}

言語環境のネスト

章が進むにつれ、Loxの実行時点での環境（変数など）の情報を保持する Environment という型を導入することになります。これは、「親の環境」への参照を保持する構造体です。自分の環境で変数が見つからなければ親を探しに行く、という用途を想定しています。

#[derive(Debug, Default)]
pub struct Environment {
    pub enclosing: Option<Rc<RefCell<Environment>>>,
    pub values: HashMap<String, Value>,
}

こういう型は他の言語ではともかくRustではなかなか骨が折れます。特に、「現在のEnvironmentから指定回数辿った環境に、指定の名前の変数があるか」を調べる関数*1などが必要になり、如何ともしがたくてここだけ unsafe 操作をしています。

/// e.g. Environment::get_at(env, 3, "this".to_token())
impl Environment {
    pub fn get_at(
        environment: Rc<RefCell<Self>>,
        distance: usize,
        name: &Token,
    ) -> Result<Value, RuntimeBreak> {
        unsafe { &*Self::ancestor(environment, distance) }.get(name)
    }

    pub fn assign_at(
        environment: Rc<RefCell<Self>>,
        distance: usize,
        name: &Token,
        value: Value,
    ) -> Result<(), RuntimeBreak> {
        unsafe { &mut *Self::ancestor(environment, distance) }.assign(name, value)
    }

    fn ancestor(environment: Rc<RefCell<Self>>, distance: usize) -> *mut Environment {
        let mut environment = environment.as_ptr();
        for _ in 0..distance {
            environment = unsafe { &*environment }
                .enclosing
                .as_ref()
                .expect("Too much distance")
                .as_ptr();
        }
        environment
    }
}

正直ここはめちゃくちゃ煮詰まって書いてたので、冷静になればもっと素直に書けるような気もしますが...。

その他

予約語がJavaとRustで割と違っていたので、地味に困ることもありました。 match ã‚„ where あたりはRustでのみ予約語ですね。

  // Loxではこういう関数が出てくるが、 r#where も書きたくない...
  // というかstaticメソッドがそもそも困る...
  private static void report(int line, String where,
                             String message) {
    System.err.println(
        "[line " + line + "] Error" + where + ": " + message);
    hadError = true;
  }

全体の感想

Crafting Interpreters でやっているような、一定レベルで現実的な機能を持ったプログラミング言語の実装はRustの教材として非常によかったように思いました。元の言語がRustではないのは正直大変でしたが、単なる「写経」ではなく、「翻訳」をする必要があったのはいっそう勉強になったように思います。

言語を実装するにはそれなりに複雑なデータ構造を扱う必要があり、これはRustの所有権や借用、内部可変性などをどう使っていくかについての良い素材だと思います。

また、特にスキャナやパーサの実装においてはRustの型の表現力は非常に強力な武器だと感じました*2。その他、メモリ安全性や速度といった側面からも、Rustは言語実装に向いた言語だなあと再確認できました。

後半の章では、言語VMの導入を含んだまた違ったアプローチの言語実装手法で進められているようなので、そちらも楽しみにしています*3。

皆様も是非Crafting Interpretersを進めて（あと、作者を支援する意味でも購入して）みると良いかと思います。写経でも、Rustへの翻訳でも、あるいは他の言語で作ってみるのも面白そうです*4。

最後にURLを再掲して本稿の締めとさせていただきます。

craftinginterpreters.com

*1:永続データ構造の実現のためです: https://craftinginterpreters.com/resolving-and-binding.html#persistent-environments

*2:自転車本にパーサの章があるのも頷けます。

*3:といいつつ少しやりかけています

*4:実際同じように翻訳をしている人は何名かいらっしゃるようです https://github.com/topics/craftinginterpreters