Writing an interpreter in GoをRustでやる
以前やったWriting an interpreter in GoをRustで作ったので、なぜ作ったか、何が得られたか、Goとの違いを感じた点などをまとめる
日本語版はGo言語でつくるインタプリタというオライリーの本がある(未読なのでどこまで同じなのかは知らない)
ちなみにGoでやったときの感想はこっちにまとめている。やったのがだいぶ前なので、この記事では前の記事との情報の重複は気にしない事にする
作業量の波はあるものの、全体でだいたい一ヶ月かかった
リポジトリは以下
https://github.com/LTKSK/rust_interpreter
READMEにある通り、以下の記事も参考にしている
・[Rust] 『Go言語でつくるインタプリタ』Rustで読了
・「Go言語でつくるインタプリタ」をRustで実装しました。
モチベーション
Rustの基礎文法を学習したので何か一つ作りたかったのが大きな動機
これより前にwasmで仮想DOMを実装するのに挑戦していたが、
そこでRustの理解不足を感じたのでより基礎的なところから始めたかった
インタプリタは依存ライブラリもなしで完結できる+覚えた基礎文法を使うのでちょうど良い課題だと感じた
何よりGoで実装した経験があって雰囲気がわかっているのと、調べると日本語の記事がいくつか出てきて答え合わせができそうなところも良かった
学べるもの
Rustの基本的な部分は一通り触れると思う
ただ先述の通り依存ライブラリは使わないので、外部crateの使い方といった部分は弱い
また複雑なlifetimeも出てこない（今回の実装ではcloneを多用しているのでそこを改善するとまた話が違うかもしれない）
本自体がTDDな雰囲気で進むので、testの書き方も自動的に(?)覚えることになる
match式や、当初不慣れだったOption,Resultは多用することになるので、
だいぶ身近に感じられるようになった
rustのenumは表現力が凄くて感動する。名前が同じだけで他の言語のenumとは比べない方が良いかもしれない
Rustでやって感じたGoとの違い
予め断っておくと、特にGoよりRustが良かったという話をしたいわけではなく、GoでやってたところがRustでこうだったという内容をまとめる
・Lexer
あまり大きな違いはない。強いていうならば、Go側のようにTypeとLiteralを用意しなくてもTokenというEnumを用意して、Displayあたりをimplしたほうがスッキリする
・Ast
AstはGoと大きく違う
初めはGoのinteface ≒ Rustのtraitだと考えていたのでtraitで実現しようとしたのだけれど、traitはstructのメンバ変数を規定できるものではなかったので、Goのような使い方はできなかった
代わりにEnumを使って、StatementやExpressionを表現することになる
Goでも結局使用時には型アサーションで求めている型なのかを判定しているので、そこがRustではmatch式に置き換わる感じ
Go側のString関数は、fmt::Display traitを実装するとスッキリ書けて良かった
・Parser
GoではPrefixやInfixのparseに予めTokenとparseに使う関数を対応付けたmapを作っておくけれど、これをRustでやろうとすると面倒なので、素直にparse_prefixのような関数を用意して、その中でmatchで振り分ける形にしている
・Evaluator
evaluatorの実装では四則演算の対応を行うときが、もっともRustの良さ(というかパターンマッチの便利さ)を感じられた
中置演算子を解決するevalInfixExpressionを例にだす
Goの場合は以下のようになる。各型毎に対応した演算用の関数を呼ぶ
func evalInfixExpression(
operator string,
left, right object.Object,
) object.Object {
switch {
case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
return evalIntegerInfixExpression(operator, left, right)
case left.Type() == object.FLOAT_OBJ && right.Type() == object.FLOAT_OBJ:
return evalFloatInfixExpression(operator, left, right)
case operator == "==":
return nativeBoolToBooleanObject(left == right)
case operator == "!=":
return nativeBoolToBooleanObject(left != right)
・・・中略・・・
return newError("unknown operator: %s %s %s",
left.Type(), operator, right.Type())
}
}Rustだとこう
fn eval_infix_expression(
op: ast::InfixOprator,
left: Object,
right: Object,
) -> Result<Object, Error> {
match op {
ast::InfixOprator::Plus => match (left, right) {
(Object::Integer(l), Object::Integer(r)) => Ok(Object::Integer(l + r)),
(Object::String(l), Object::String(r)) => Ok(Object::String(l + &r)),
_ => Err(EvalError {
msg: "Invalid infix expression".to_string(),
}),
},
ast::InfixOprator::Minus => match (left, right) {
(Object::Integer(l), Object::Integer(r)) => Ok(Object::Integer(l - r)),
_ => Err(EvalError {
msg: "Invalid infix expression".to_string(),
}),
},
ast::InfixOprator::Equal => match (left, right) {
(Object::Integer(l), Object::Integer(r)) => Ok(Object::Boolean(l == r)),
(Object::Boolean(l), Object::Boolean(r)) => Ok(Object::Boolean(l == r)),
(Object::String(l), Object::String(r)) => Ok(Object::Boolean(l == r)),
_ => Err(EvalError {
msg: "Invalid infix expression".to_string(),
}),
},
ast::InfixOprator::Nequal => match (left, right) {
(Object::Integer(l), Object::Integer(r)) => Ok(Object::Boolean(l != r)),
(Object::Boolean(l), Object::Boolean(r)) => Ok(Object::Boolean(l != r)),
(Object::String(l), Object::String(r)) => Ok(Object::Boolean(l != r)),
_ => Err(EvalError {
msg: "Invalid infix expression".to_string(),
}),
},
o => panic!("eval infix expression for {:?} is not implemented yet.", o),
}
}
}Rust側のエラーメッセージはちょっと適当なんだけれど、
取りうる組み合わせの中で、該当するやつだけつらつら並べて書いて行けば良いので楽だった。また演算子の判定が先に来るのも、各演算子毎にどの型の演算がサポートされているか見やすいの(褒め過ぎか？)
matchが式なのでnestできるところや、tupleを受けられるところもポイントだと思う
for文の実装について
実装について大部分は冒頭で紹介したリンク先を見た方が詳しい
ただプラスが何も無いのはあれなので今回は本の内容に加えてfor文を実装したのでその内容を示す
文法としては以下のような雰囲気のものを想定した
'for' <identifier> 'in' <array_expression> { <statements> }具体的には以下のような感じ
// 変数aが定義済みとして
for b in [1,2,3] { a = a + b; }ちなみに"python bnf"みたいに検索すると構文の定義が出てきて参考になるという学びがあった
実装は、まずforとinというキーワードをletやreturnのようにTokenとして扱えるようにする
次にAstでExpressionとして定義を追加する。内容の抜粋は以下
#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub enum Expression {
...
For {
parameter: String,
array: Box<Expression>, //Expression::Array only
statement: Box<Statement>,
},
...
}{}の中に当たる部分がStatementになっているけれど、StatementにはStatementの配列を持つBlockStatementがあるのでそれが割当てられる
forのparseは以下のような実装になった
fn parse_for_expression(&mut self) -> Result<ast::Expression, Error> {
// forの次に進む
self.next_token();
// identifierをparse
let parameter = match self.parse_expression(Precedence::Lowest)? {
ast::Expression::Identifier(i) => i,
o => {
return Err(Error::EvalError {
msg: format!("Expect identifier but got {}", o),
})
}
};
// inを読み込み(なければエラー)
if !self.expect_peek(Token::IN) {
return Err(Error::EvalError {
msg: format!("Expect `in` but got {}", self.peek_token),
});
}
if !self.expect_peek(Token::LBRACKET) {
return Err(Error::EvalError {
msg: format!("Expect `[` but got {}", self.peek_token),
});
}
// arrayのparse
let array = self.parse_array_expression()?;
// {}内のparse
if !self.expect_peek(Token::LBRACE) {
return Err(Error::EvalError {
msg: format!("Expect `{{` but got {}", self.peek_token),
});
}
let statement = self.parse_block_statement()?;
Ok(ast::Expression::For {
parameter,
array: Box::new(array),
statement: Box::new(statement),
})
}最後にEvalを実装する
arrayの値を都度env上にsetして、statementを評価するという流れになっている
最初関数呼び出しと同じ要領で拡張したenvを作成して投げ込んでいたのだけれど、そうすると後述の代入で上手く行かなくなった(一時的なenvの方に値を書き込んでしまう)ので、
Environmentにremove関数を追加して、forを抜けたら該当の関数を消すような処理にしている
fn eval_expression(
expression: ast::Expression,
env: &mut environment::Environment,
) -> Result<Object, Error> {
match expression {
...
ast::Expression::For {
parameter,
array,
statement,
} => {
let mut result = Object::Null;
// arrayの値を一つずつenv上のparameterにマッピング
if let ast::Expression::Array(array) = *array.clone() {
for object in eval_expressions(array, env)? {
env.set(parameter.clone(), object);
if let ast::Statement::Block(stmts) = *statement.clone() {
result = eval_block_statements(stmts, env)?;
}
}
env.remove(¶meter.clone());
}
Ok(result)
}
}
}代入の実装
実は本の中ではletによる変数定義は行うが、変数への再代入を行う処理は実装しない
なのでfor文を実装して1..10まで足し算するぞー、みたいな単純な処理が書けなかったので、合わせて対応することにした
代入はparse_prefixでIdentだった時、次のTokenがAssign(=のこと)だったら、parse_infixを呼ぶように置き換える
またその際にInfixOperatorのenumにAssignを追加しておく
生成されるAstは既存のExpression::Infixと同じなので、parserまではこれだけで良い
evaluatorはちょっと汚くて、eval_expressionに以下のようなコードを書いた
...
ast::Expression::Infix {
left,
operator,
right,
} => match operator {
ast::InfixOprator::Assign => match *left {
// Assignのoperatorの時だけ分岐を分ける
// eval_infixだと既にObjectになってしまっていて、
// Identifierのnameが取れないため
ast::Expression::Identifier(i) => {
let right = eval_expression(right.as_ref().clone(), env)?;
env.set(i, right.clone());
Ok(right)
}
_ => Err(Error::EvalError {
msg: format!("can not assign {} to {}", right, left),
}),
},
_ => {
let left = eval_expression(left.as_ref().clone(), env)?;
let right = eval_expression(right.as_ref().clone(), env)?;
eval_infix_expression(operator, left, right)
}
},
..._で受けているところが元々の処理。Objectになってしまうと変数名ではなくてその変数の値になってしまうので、それとは別の分岐を作る事にした
ちなみに最後にOk(right)を返しているので、意図せず以下のようなコードが動くようになって面白かった
let a = b = 1(なおここまで書いた時点でletなしでも変数定義ができる事に気づいてしまった。気が向いたら直したり直さなかったりしようと思う)
まぁ細かいことは置いとくとして、これでforと代入が実装できた事になる
修正箇所の少なさから、元々の設計の美しさを感じた
なおGoのインタプリタではプラスとしてfloatに対応したのだが、Rust側でやろうとしたところHashもOrdも使えないので、HashMapなどが使えなくなり早々に諦めたという経緯も共有しておく
外部traitか、自前実装を頑張ればいけるかもしれない
まとめ
言語学習の手段としてのインタプリタは非常に筋が良いと感じたので、
もし新しく言語を覚えた何か作りたい人にはおすすめしたい
また複数言語で実装することが結果的に両言語のできる範囲の理解に繋がったので、そういった面でも良かったなと感じた
Rustという言語は触っててぐっと来るものがあるので、一般的なプラクティスや、流行りのライブラリといった情報を追いかけていければなと思う
実は元々firecrackerを理解したいという気持ちからRustの勉強を初めたので、目標に近づくべく今は Writing an OS in Rustというサイトで低レイヤを勉強している。とりあえず心が折れても一ヶ月経つまでは頑張ってみようと思う
この記事が気に入ったらサポートをしてみませんか？