Ruby / Rails以外の開発一般

2024.01.05

Rust で JSON5 を実行するインタプリタを作って自作言語の高速スタートアップをしよう

yoshi

シェア
ツイート
ブックマーク
LINE

こんにち自作言語！（挨拶）　世の中のには 2 種類の人がいます。自作言語を作っている人と、これから自作言語を作る人です。（筆者の脳内調査）
いや別に自作言語作らない人もいるだろって思いました？　こんなタイトルの記事を読んでいるのだからあなたはこのどちらかですよね？　どちらでもない？　じゃあこれから自作言語を作る人になってください（圧）

かく言う私も長年自作言語ワナビーをやっており、ときおり制作に手を付けては放置し、結局なかなか作れずにいるという現状で、ここをどうにか突破したい、と思いこの記事を書いています。

あっちなみに、言うまでもないとは思いますがこの記事における言語＝プログラミング言語です。クウェンヤとかシンダールとかエスペラントとかリパラインとかの世界ではないです。ちなみにあっちはよく「人工言語」という言葉が使われるっぽいですね。もっとも「人工言語」は「自然言語」に対比する言葉で、プログラミング言語は全て人工なのですが。人工言語を自作するときはやっぱり自作言語って言うのかな？

えー、話がずれました。
モダンなプログラミング言語が実行までにどういうことをやるかと言うと、

パースして構造を解析する
中間言語への変換
中間言語の最適化
中間言語から各アーキテクチャへの変換
各アーキテクチャでの実行

みたいな感じです。

いや、分かりますよ、これはあくまでも一例という感じで、細かくはいろんなプロセスがあって、言語によって、あるいはビルドオプションなどによって採用されたりされなかったりするステージもある訳です。ランタイムに JIT コンパイルする言語処理系もありますし、TypeScript のようにターゲットが他の言語のソースコードになっているものもありますし。ざっくりとしたイメージとしてこんな感じ、というやつです。

で、当然、これ全部実装するのはむちゃくちゃ大変じゃないですか。まあ現在なら中間言語から先は LLVM に乗っかるという手がある訳ですが、それでも LLVM IR を書くのは中々骨が折れるし、オリジナルの文法を書こうと思うとパーサーを作るのも大変です。

本記事では、これらの工程をだいたい全部やらないことで解決したいと思います。

パースがめんどくさい？　じゃあパースなんてやらなくてもいいやと。
中間言語への変換がめんどくさい？　じゃあパース結果をそのまま実行すればいいだろと。

自作言語開発の序盤で一番面白いのは、やっぱりそれなりの複雑性をもったコードが実行できるようになることだと思うのです。最低限、関数が定義できて、再帰が実行できたら面白くなると思いませんか？
そこに最高速でたどり着くことを目指します。

最終的なコード: json5-interpreter - CodeSandbox

ソースコードは既にパース済みとする

パーサーを書かないというのはどういうことか？
まあ、書かないとは言ったけど実際にはプレーンテキストから Rust の構造体へ変換する必要はある訳でして、ただ、ここは完全に巨人の肩に乗っていきます。
すなわち、ソースコードに相当するものは JSON で記述して、serde でデシリアライズします。

あ、ただ JSON は手で書くのがだいぶかったるいので今回は json5 クレートを使い、ソースコードは JSON5 で記述できるようにします。

つまり、

use serde::{Serialize, Deserialize};

#[derive(Serialize, Deserialize)]
struct Program { /*..*/ }

として、シリアライズされた時に出力されるものがこの言語の文法です。

プログラムの構造を（雑に）定義する

自作言語の仕様を考えるときに、「数値があって、文字列があって、配列があって…」などといろんなものを定義しようとしていませんか？

そういうのはなるべくオミットしましょう。後からいくらでも増やせます。今必要なのは、本当に最低限なものです。

それでも必要があるものを列挙します。

プログラム全体を表す構造
- 文を表す構造
- 式を表す構造
  - 関数呼び出しを表す構造
  - 値を表す構造

「関数を表す構造」とか「ループを表す構造」とかなくて良いのか？
いいんです。もちろん後から追加することは考えていますが、最初はなくていいんです。
値も、今は i64 だけを使うことを考えましょう。関数呼び出しの構文だけあって、関数そのものはどうするのかと言うと、ランタイムに組み込みで用意します。

プログラム全体を表す構造

#[derive(Debug, Clone, Serialize, Deserialize)]
struct Program {
    statements: Vec<Statement>,
}

プログラム全体は、複数の文 (Statement) が並んだものとして定義します。

文を表す構文

#[derive(Debug, Clone, Serialize, Deserialize)]
enum Statement {
    Expression(Expression),
}

文は、将来の拡張のために enum で定義しますが、現状は式 (Expression) のみからなる式文だけです。

式を表す構文

#[derive(Debug, Clone, Serialize, Deserialize)]
enum Expression {
    Value(i64),
    FuncCall(Box<FuncCall>),
}

式は、現状では値そのもの(Value)か関数呼び出し(FuncCall)かのいずれかになります。 FuncCall が内部で Expression を持つため、 Box 化しておきます。

関数呼び出しを表す構文

#[derive(Debug, Clone, Serialize, Deserialize)]
struct FuncCall {
    func: Expression,
    args: Vec<Expression>,
}

関数呼び出しは、関数本体を表す式と、引数を表す式の配列から構成します。

インタプリタを定義する

ここまでの構造があれば、ソースコードの準備は整いました。
json5::from_str を使えばソース文字列から Program を作ることができるので、これを受け取って実行するための構造を考えましょう。

具体的にはこんな感じの物を作ります。

struct Interpreter { /*..*/ }

impl Interpreter {
    fn run(&mut self, program: &Program) {
        todo!()
    }
}

プログラムを実行する

impl Interpreter {
    fn run(&mut self, program: &Program) {
        program
            .statements
            .iter()
            .for_each(|statement| self.run_statement(statement));
    }

    fn run_statement(&mut self, statement: &Statement) {
        todo!()
    }
}

プログラムは文の配列なので、一つの文を実行する関数を用意し、順に呼び出します。

文を実行する

impl Interpreter {
    fn run_statement(&mut self, statement: &Statement) {
        match statement {
            Statement::Expression(expression) => {
                self.eval_expression(expression);
            }
        }
    }

    fn eval_expression(&mut self, expression: &Expression) -> i64 {
        todo!()
    }
}

文は（今のところ）式文のみなので、式を評価する関数を呼ぶだけです。式を評価する関数は i64 を返すようにしていますが、今はそれを利用しないので無視します。

式を評価する

impl Interpreter {
    fn eval_expression(&mut self, expression: &Expression) -> i64 {
        match expression {
            Expression::Value(value) => *value,
            Expression::FuncCall(func_call) => self.eval_function(func_call),
        }
    }

    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        todo!()
    }
}

式は値そのもの(i64)か関数呼び出しです。値そのものの場合、そのまま中身を返します。関数呼び出しの場合は関数を評価する関数を呼びます。

関数呼び出し

いまのところ、ここが一番複雑なところです。

呼び出すべき関数の特定

impl Interpreter {
    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        let func = self.eval_expression(&func_call.func);
        todo!()
    }
}

さて、関数呼び出しを行いたいのですが、ここまでのところで関数は定義されていません。
しかも、上記のように FuncCall::func を評価しても、返ってくるのは i64 です。

というわけで、呼び出すべき関数の情報を Interpreter に加えていきます。

struct Interpreter {
    functions: Vec<RuntimeFunction>,
}

enum RuntimeFunction {
    BuiltIn(Box<dyn Fn(Vec<i64>) -> i64>),
}

impl Interpreter {
    fn add_builtin_function(&mut self, f: impl 'static + Fn(Vec<i64>) -> i64) {
        self.functions.push(RuntimeFunction::BuiltIn(Box::new(f)))
    }
}

はい。これで i64 の値を functions のインデックスとみなせば関数を特定できることができるようになりました。

impl Interpreter {
    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        let func_index = self.eval_expression(&func_call.func);
        let func = &self.functions[func_index as usize];
        todo!()
    }
}

引数の評価

impl Interpreter {
    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        let func_index = self.eval_expression(&func_call.func);
        let args = func_call
            .args
            .iter()
            .map(|arg| self.eval_expression(arg))
            .collect::<Vec<_>>();
        let func = &self.functions[func_index as usize];
        todo!()
    }
}

引数は Expression の配列なので、全て eval_expression であらかじめ評価します。

関数呼び出し

impl Interpreter {
    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        let func_index = self.eval_expression(&func_call.func);
        let args = func_call
            .args
            .iter()
            .map(|arg| self.eval_expression(arg))
            .collect::<Vec<_>>();
        let func = &self.functions[func_index as usize];
        match func {
            RuntimeFunction::BuiltIn(f) => f(args)
        }
    }
}

ビルトイン関数は Box<dyn Fn(Vec<i64>) -> i64> の関数オブジェクトなので、そのまま普通に関数呼び出しできます。

ビルトイン関数の追加

さて、これで呼び出しの方は用意できましたが、そもそも現状ではビルトイン関数が存在しないので何も呼べません。
なので、ビルトイン関数を追加しましょう。
とりあえず追加するのは、

引数を加算する関数
引数を標準出力に出力する関数

です。

引数を加算する関数

// let mut interpreter: Interpreter;

interpreter.add_builtin_function(|args| {
    // とりあえず2引数以外はpanic
    let [x, y] = args.as_slice() else { panic!() };
    x + y
});

パターンマッチで引数をスライスにしたものをマッチさせてから加算しています。このように組み込み関数はラムダ式で簡単に追加できます。

引数を標準出力に出力する関数

// let mut interpreter: Interpreter;

interpreter.add_builtin_function(|args| {
    args.iter().for_each(|arg| println!("{arg}"));
    0
});

引数を順に全て出力しているだけです。特に戻り値はないのですが、値は今の所 i64 しかないので 0 を返しています（そのうち void とかにすべきところではあります）

この二つの関数を順番に追加することで、インデックス 0 は加算、インデックス 1 は出力の関数になります。

ここまで来たら最低限実行の準備は整いました。ソースコードを作っていきましょう。

ソースコード

とりあえず現状でできることの確認のために、「10 + 32 を実行して表示する」という処理をソースコードにします。こうなります。

{
  statements: [
    {
      Expression: {
        FuncCall: {
          func: { Value: 1 },
          args: [
            {
              FuncCall: {
                func: { Value: 0 },
                args: [{ Value: 10 }, { Value: 32 }],
              },
            },
          ],
        },
      },
    },
  ],
}

ちなみにこれは

Program {
    statements: vec![
        Statement::Expression(Expression::FuncCall(Box::new(
            FuncCall {
                func: Expression::Value(1),
                args: vec![Expression::FuncCall(Box::new(FuncCall {
                    func: Expression::Value(0),
                    args: vec![
                        Expression::Value(10),
                        Expression::Value(32),
                    ]
                }))],
            }
        )))
    ],
}

Rust でこういう構造を作ってシリアライズしたものをフォーマットしています。

実行

あとはこれを実行できるように、こんな感じの main 関数を作ります

fn main() {
    let mut source = File::open(args_os().nth(1).unwrap()).unwrap();
    let mut buf = vec![];
    source.read_to_end(&mut buf).unwrap();
    drop(source);
    let program: Program = from_str(std::str::from_utf8(&buf).unwrap()).unwrap();
    let mut interpreter = Interpreter{
        functions: vec![],
    };
    interpreter.add_builtin_function(|args| {
        let [x, y] = args.as_slice() else { panic!() };
        x + y
    });
    interpreter.add_builtin_function(|args| {
        args.iter().for_each(|arg| println!("{arg}"));
        0
    });

    interpreter.run(&program);
}

これで、第一引数にソースコードのファイル名を渡すと実行してくれる処理系ができました。

cargo run source.json

こんな感じで実行して、

こう出力されれば成功です。

関数定義をできるようにする

さて、当初の目標が再帰関数の定義だったので、このままではまだ足りないですよね？

関数定義をできるようにするには、

関数定義そのものの構造
return 文
ランタイムで定義した関数や引数を参照できるようにするもの

が必要になります。参照に関してはつまり変数が必要になるということです。

また、再帰関数を定義するには条件分岐も必要になるので、これも定義していきます

関数の定義

#[derive(Debug, Clone, Deserialize, Serialize)]
struct FuncDef {
    name: String,
    args: Vec<String>,
    body: Vec<Statement>,
}

関数の定義は以上のようになります。関数名、引数名の配列、文の配列です。

条件分岐

#[derive(Debug, Clone, Deserialize, Serialize)]
struct If {
    cond: Expression,
    body: Vec<Statement>
}

条件を表す式と、条件が真だった時に実行される文を定義します。

続いて、これらの構造を加えて、既存の構造体に変更を加えていきます。

`Statement` の変更

#[derive(Debug, Clone, Serialize, Deserialize)]
enum Statement {
    Expression(Expression),
    Return(Expression),
    FuncDef(FuncDef),
    If(If),
}

impl Interpreter {
    fn run(&mut self, program: &Program) {
        self.run_statements(&program.statements);
    }

    fn run_statements(&mut self, statement: &[Statement]) -> Option<i64> {
        for statement in statement {
            let Some(r) = self.run_statement(statement) else { continue; };
            return Some(r);
        }
        None
    }

    fn run_statement(&mut self, statement: &Statement) -> Option<i64> {
        match statement {
            Statement::Expression(expression) => {
                self.eval_expression(expression);
            }
            Statement::Return(expression) => {
                return Some(self.eval_expression(expression))
            }
            Statement::FuncDef(func_def) => {
                self.add_function(func_def);
            }
            Statement::If(if_) => {
                return self.run_if(if_)
            }
        }
        None
    }

    fn add_function(&mut self, func_def: &FuncDef) {
        todo!()
    }

    fn run_if(&mut self, if_: &If) -> Option<i64> {
        todo!()
    }
}

Statement の配列が各所に出てくるようになったので run_statements を追加し、また return 文により途中で実行を抜ける可能性が生まれたため戻り値を Option<i64> にしています。

関数の動的追加

use std::collections::HashMap;

struct Interpreter {
    functions: Vec<RuntimeFunction>,
    globals: HashMap<String, i64>,
}

enum RuntimeFunction {
    BuiltIn(Box<dyn Fn(Vec<i64>) -> i64>),
    Runtime(FuncDef),
}


impl Interpreter {
    fn add_function(&mut self, func_def: &FuncDef) {
        self.globals.insert(func_def.name.clone(), self.functions.len() as i64);
        self.functions.push(RuntimeFunction::Runtime(func_def.clone()))
    }
}

このようにすると、 globals から関数のインデックスを引くことができます。
また、組み込み関数にも名前を付けれるようになるので

impl Interpreter {
    fn add_builtin_function(&mut self, name: impl Into<String>, f: impl 'static + Fn(Vec<i64>) -> i64) {
        self.globals.insert(name.into(), self.functions.len() as i64);
        self.functions.push(RuntimeFunction::BuiltIn(Box::new(f)))
    }
}

こんな感じにしましょう。合わせて、先ほどのビルトイン関数の定義を、

interpreter.add_builtin_function("+", |args| {
    let [x, y] = args.as_slice() else { panic!() };
    x + y
});
interpreter.add_builtin_function("dbg", |args| {
    args.iter().for_each(|arg| println!("{arg}"));
    0
});

こうしてしまいましょう。

`Expression` の変更

#[derive(Debug, Clone, Serialize, Deserialize)]
enum Expression {
    Value(i64),
    Var(String),
    FuncCall(Box<FuncCall>),
}

impl Interpreter {
    fn eval_expression(&mut self, expression: &Expression) -> i64 {
        match expression {
            Expression::Value(value) => *value,
            Expression::Var(name) => self.globals.get(name).unwrap(),
            Expression::FuncCall(func_call) => self.eval_function(func_call),
        }
    }
}

変数が追加されたので、それに対応して Expression を拡張しました。

関数呼び出しの変更

struct Interpreter {
    functions: Vec<RuntimeFunction>,
    globals: HashMap<String, i64>,
    locals: HashMap<String, i64>,
    stack: Vec<HashMap<String, i64>>,
}


impl Interpreter {
    fn eval_function(&mut self, func_call: &FuncCall) -> i64 {
        let func_index = self.eval_expression(&func_call.func);
        let args = func_call
            .args
            .iter()
            .map(|arg| self.eval_expression(arg))
            .collect::<Vec<_>>();
        let func = &self.functions[func_index as usize];
        match func {
            RuntimeFunction::BuiltIn(f) => f(args),
            RuntimeFunction::Runtime(f) => self.eval_runtime_function(f.clone(), args), // ※
        }
    }

    fn eval_runtime_function(&mut self, func_def: FuncDef, args: Vec<i64>) -> i64 {
        self.stack.push(std::mem::take(&mut self.locals));
        for (i, arg) in func_def.args.iter().enumerate() {
            self.locals.insert(arg.into(), args[i]);
        }
        let r = self.run_statements(&func_def.body).unwrap_or(0);
        self.locals = self.stack.pop().unwrap();
        r
    }
}

（※ FuncDef を毎回コピーするのは効率が悪いのですが、ボローチェッカーの回避のためにこうしています。実際は Rc などリソース共有の仕組みを使うとコピーコストをかけずに関数定義を共有できます）

関数の引数を扱うにはローカル変数が必要なのでローカル変数とスタックを追加しました。
スタックはローカル変数を表す辞書の配列で、関数呼び出し前に現在のローカル変数を push します。
その後実引数リストと仮引数リストを突き合わせてローカル変数に登録し、run_expressions を呼ぶことで関数の中身を評価します。
関数から戻ったらスタックを pop してローカル変数を元に戻します。

合わせて、変数の探索もローカル変数 → グローバル変数になるよう変更します。

impl Interpreter {
    fn eval_expression(&mut self, expression: &Expression) -> i64 {
        match expression {
            Expression::Value(value) => *value,
            Expression::Var(name) => *self.locals.get(name).or_else(||self.globals.get(name)).unwrap(),
            Expression::FuncCall(func_call) => self.eval_function(func_call),
        }
    }
}

`if` 文の実行

impl Interpreter {
    fn run_if(&mut self, if_: &If) -> Option<i64> {
        let cond = self.eval_expression(&if_.cond);
        if cond == 0 {
            return None;
        }
        self.run_statements(&if_.body)
    }
}

値が i64 しかないので、昔の C 言語のように 0 かそれ以外で分岐するようにします。

再帰関数を定義してみる

ここまで来たら再帰関数が定義できるようになったので、フィボナッチ数の漸化式を定義して N 番目のフィボナッチ数を求められるようにしてみましょう。
ただし、フィボナッチ数の計算には減算と比較が必要なので（減算はマイナスの値を加算する、でも実現できるのですが）以下の組み込み関数を追加します。

interpreter.add_builtin_function("-", |args| {
    let [x, y] = args.as_slice() else { panic!() };
    x - y
});
interpreter.add_builtin_function("==", |args| {
    let [x, y] = args.as_slice() else { panic!() };
    (x == y) as i64
});

ソースコードはこうなります。

{
  statements: [
    {
      FuncDef: {
        name: "fib",
        args: ["n"],
        body: [
          {
            If: {
              cond: {
                FuncCall: {
                  func: { Var: "==" },
                  args: [{ Var: "n" }, { Value: 0 }],
                },
              },
              body: [{ Return: { Value: 0 } }],
            },
          },
          {
            If: {
              cond: {
                FuncCall: {
                  func: { Var: "==" },
                  args: [{ Var: "n" }, { Value: 1 }],
                },
              },
              body: [{ Return: { Value: 1 } }],
            },
          },
          {
            Return: {
              FuncCall: {
                func: { Var: "+" },
                args: [
                  {
                    FuncCall: {
                      func: { Var: "fib" },
                      args: [
                        {
                          FuncCall: {
                            func: { Var: "-" },
                            args: [{ Var: "n" }, { Value: 1 }],
                          },
                        },
                      ],
                    },
                  },
                  {
                    FuncCall: {
                      func: { Var: "fib" },
                      args: [
                        {
                          FuncCall: {
                            func: { Var: "-" },
                            args: [{ Var: "n" }, { Value: 2 }],
                          },
                        },
                      ],
                    },
                  },
                ],
              },
            },
          },
        ],
      },
    },
    {
      Expression: {
        FuncCall: {
          func: { Var: "dbg" },
          args: [{ FuncCall: { func: { Var: "fib" }, args: [{ Value: 10 }] } }],
        },
      },
    },
  ],
}

このソースコードでは 10 番目のフィボナッチ数を求めているので、

cargo run fib.json5

を実行して

が出力されたら成功です。

終わりに

という訳で、非常に駆け足ですが再帰関数が実行できるようになりました。

ここまで理解できれば、

FizzBuzz を実行できるように、値として文字列を扱えるようにする
配列やオブジェクトを扱えるようにする
引数以外の変数も使えるようにする

みたいなカスタマイズも可能でしょう。

さて、そうはいっても実際 JSON は読みにくいし書きにくい、と皆さん思っていると思います。分かります。フィボナッチ数のナイーブな実装だけでこんなにソースコードが冗長になるのは実際辛いです。
そうなると文法やパーサーの定義が必要になりますね。でも、パース結果がこの JSON や Rust のオブジェクトになるようにする、と考えれば見通しが立てやすいのではないでしょうか。

実際、この記事で扱った JSON5 はほとんど AST（抽象構文木）と呼ばれるものに近いです。実際はこれを直接実行するようなことはなく、最適化したり更に別の中間形式へ変換していくことになりますが、自作言語を作るにあたって、この記事でやったようなことができるようにするのは一つのマイルストーンとして有用だと思います。

Rustの借用の話をする

Rustを通して見るオブジェクト指向

シェア
ツイート
ブックマーク
LINE

Rust で JSON5 を実行するインタプリタを作って自作言語の高速スタートアップをしよう

ソースコードは既にパース済みとする

プログラムの構造を（雑に）定義する

プログラム全体を表す構造

文を表す構文

式を表す構文

関数呼び出しを表す構文

インタプリタを定義する

プログラムを実行する

文を実行する

式を評価する

関数呼び出し

呼び出すべき関数の特定

引数の評価

関数呼び出し

ビルトイン関数の追加

引数を加算する関数

引数を標準出力に出力する関数

ソースコード

実行

関数定義をできるようにする

関数の定義

条件分岐

Statement の変更

関数の動的追加

Expression の変更

関数呼び出しの変更

if 文の実行

再帰関数を定義してみる

終わりに

関連記事

Excelで改ページを挿入できない場合の対応方法（更新版）

Googleスプレッドシートのセル内に画像をぴったり埋め込み表示する方法

ドコモレピータ+αで自宅の携帯電波状況を劇的に改善！

チーム開発においてGit初心者が踏みがちな地雷まとめ

HTML5のLocal Storageを使ってはいけない（翻訳）

Rails: アサーションが動いていないテストを効果的に発見する方法（翻訳）

Rails: SidekiqからSolid Queueに移行したときの方法と注意点（翻訳）

Rubyバイナリのビルドでenable-load-relativeフラグを活用する（翻訳）

週刊Railsウォッチ: Prismの歴史と現況を振り返る、Steepの"narrowing"実装の内部ドキュメントほか（20240426後編）

週刊Railsウォッチ: RailsからOpenStructを削除、Playwrightベストプラクティスほか（20240425前編）

関連記事

2024年のファビコンを極める: 本当に必要なファイルはほぼ6つ（翻訳）

週刊Railsウォッチ（20190909-1/2前編）Rails 6のキャッシュバージョニング、Rubyのキーワード引数周りが変わる、Faker 2がリリースほか

RailsのJSON生成をPostgreSQLのJSON関数で高速化（翻訳）

CONTACT

`Statement` の変更

`Expression` の変更

`if` 文の実行