Go言語でつくるインタプリタ (T. Ball, 設樂 洋爾 (訳), O'Reilly) を Rust で実装しながら一通り読み終わったので復習がてらまとめます. ただし第 3 章まで実装して一通り使えるようになった時点で満足したので, 第 4 章と付録は流し読みしただけでほとんど実装していません.
なお, ちょっと検索すると同じように Rust で実装したという記事がいくつもヒットします. とはいえ, このリストにさらにひとつ記事を追加しても誰も困らないでしょう.
- Writing An Interpreter In Rust して、Wasm で動かしてみた
- 「Go言語でつくるインタプリタ」を Rust で移植してみた
- 『Go言語でつくるインタプリタ』をRustで実装 ①字句解析器
以下の Rust コードは全部を示すのではなく, 見やすいように要点だけを抜き出したものです. 全コードはこちら: https://github.com/osanshouo/monkey-interpreter
字句解析
トークン (token)
トークンとは Monky (本書で実装するオリジナルのスクリプト言語) のコードに現れる個々の要素すべてのことを指します. let などのキーワード, 整数リテラル, 真理値リテラル, 識別子, アスタリスクやセミコロンなどの記号からなります.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Token {
Illegal,
EOF,
// 中略 //
If,
Let,
Ident(String),
Integer(i32),
}
字句解析器 (lexer)
ソースコードをトークン列に変換するのが字句解析です. 『Go言語でつくるインタプリタ』や他の人の Rust 実装を見ると入力をバイト列として扱っていますが, chars で char のイテレータに変換する方が直接的ですし, 入力を UTF-8 に拡張するのも簡単だと思います.
/// 字句解析器
pub struct Lexer<'a> {
input: std::str::Chars<'a>,
cur: char,
peek: char,
}
impl<'a> Lexer<'a> {
/// 入力 Monkey コードを受け取り Lexer インスタンスを生成する.
pub fn new(input: &'a str) -> Self {
let mut lexer = Lexer {
input: input.chars(), // 遅延評価で事足りる
cur: '\u{0}',
peek: '\u{0}',
};
lexer.read_char();
lexer.read_char();
lexer
}
// 省略 //
pub fn next_token(&mut self) -> Token {
// 省略 //
}
}
構文解析
演算子 (operator)
Rust の enum の威力を最大限発揮するために, 『Go言語でつくるインタプリタ』には登場しませんが, Monky に含まれる前置演算子と中置演算子を表す専用の enum をつくっておきます. さらに, 中置演算子の優先順位もここで定義しておきます. enum に PartialOrd が derive できることにこれを実装していて初めて気づいたんですが, 便利すぎて感動です.
/// 前置演算子
pub enum Prefix {
Bang,
Minus,
}
/// 中置演算子
pub enum Infix {
Plus,
Minus,
Asterisk,
Slash,
Eq,
NotEq,
LT,
GT,
}
// 省略 //
/// 中置演算子の優先順位
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum Precedence {
Lowest,
Equals,
LessGreater,
Sum,
Product,
Prefix,
Call,
}
抽象構文木 (AST)
インタプリタ内部では, 与えられたソースコードを評価する前にトークン列から抽象構文木 (abstract syntax tree, AST) と呼ばれる構造へと変換します. src/ast.rs では AST を表現する enum を実装します. なお『Go言語でつくるインタプリタ』を読みながらだとトレイトで実装したくなりますが, それだと型で分岐する処理を書けないので enum 一択だと思います.
pub enum Statement {
Let{ident: Expression, value: Expression},
Return(Expression),
Expression(Expression),
Block(Vec<Statement>),
}
pub struct Program {
pub(crate) statements: Vec<Statement>,
}
// 省略 //
pub enum Expression {
Ident(String),
String(String),
Integer(i32),
Bool(bool),
Prefix {op: operator::Prefix, right: Box<Expression>},
Infix {op: operator::Infix, left: Box<Expression>, right: Box<Expression>},
If {condition: Box<Expression>, consequence: Box<Statement>, alternative: Option<Box<Statement>>},
Function {parameters: Vec<Expression>, body: Box<Statement>},
Call {function: Box<Expression>, arguments: Vec<Expression>},
}
構文解析器 (parser)
字句解析器の出力をもとに AST を構成する処理をゴリゴリ書きます. 一番込み入っている部分です. 中置演算子の扱いが言われてみればなるほどという感じでここが一番勉強になりました. 『Go言語でつくるインタプリタ』の演算子毎の処理の分岐の扱いは Rust で HashMap を使ってそのまま書き直すのはたぶんかなり面倒で, べた書きするべきだと思います.
pub struct Parser<'a> {
l: Lexer<'a>,
cur_token: Token,
peek_token: Token,
}
impl<'a> Parser<'a> {
// 省略 //
pub fn parse_program(&mut self) -> Result<ast::Program, MonkeyError> {
let mut program = ast::Program::new();
while !self.cur_token_is(Token::EOF) {
program.statements.push(
self.parse_statement()?
);
self.next_token();
}
Ok(program)
}
}
なおエラー型 MonkeyError は src/error.rs で定義しています.
評価
オブジェクト (object)
Monky で扱うデータ型を Rust 上で表現するために Object という enum を導入します.
#[derive(Debug, Clone)]
pub enum Object {
String(String),
Integer(i32),
Bool(bool),
Null,
ReturnValue(Box<Object>),
Function{parameters: Vec<ast::Expression>, body: ast::Statement, env: Environment},
}
// 省略 //
環境 (env)
変数を値に束縛するためには情報を保持する環境です. これは識別子をオブジェクトに映す HashMap です.
pub struct Environment {
store: HashMap<String, Object>,
host: Option<Rc<RefCell<Environment>>>,
}
// 省略 //
評価器 (eval)
最後に AST を評価して返り値を求める過程が評価です. 必要な情報はすべて AST に入っているので, これを淡々と評価してオブジェクトにしていけばできます. クロージャ固有の環境は Rc で包んで持つ必要があるという点が Go との一番大きなギャップでしょう (最初は参照で持たせようとしてましたがよく考えたら明らかに無理でした).
#[derive(Debug, Clone, PartialEq)]
pub struct Evaluator {
env: Rc<RefCell<Environment>>,
}
impl Evaluator {
pub fn eval(&mut self, program: &ast::Program) -> Result<Object, MonkeyError> {
let mut result = Object::Null;
for stmt in program.statements.iter() {
result = self.eval_statement(stmt)?;
if let Object::ReturnValue(value) = result {
return Ok(*value);
}
}
Ok(result)
}
// 省略 //
}
実行
REPL
REPL (Read-Evaluate-Print-Loop) は以上の部品を繋げるだけです.
const PROMPT: &str = ">> ";
pub fn start() -> Result<(), io::Error> {
let mut env = Environment::new();
eprint!("{}", PROMPT);
for line in io::stdin().lock().lines() {
// 省略 //
}
Ok(())
}
メイン関数 (main)
バイナリとして使う場合, コマンドライン引数なしなら REPL を起動し, ファイルのパスを引数として渡すとそのファイルを開いて実行するのが期待される動作だと思います.
fn main() {
eprintln!("This is the Monky programming language!");
match env::args().nth(1) {
Some(fp) => {
let input = fs::read_to_string(fp).unwrap();
evaluate(&input).unwrap();
},
None => repl::start().unwrap(),
}
}
テスト
単体テストは各モジュールファイルに書き, フィボナッチ数列のテストのみ tests/fibonacci.rs, tests/fibonacci.monkey に切り出しました.
let phi = fn(n) {
if (n == 0) { return 1; }
if (n == 1) { return 1; }
phi(n-1) + phi(n-2);
};
puts( "Fib(", 0, ") =", phi(0) );
puts( "Fib(", 1, ") =", phi(1) );
puts( "Fib(", 2, ") =", phi(2) );
puts( "Fib(", 3, ") =", phi(3) );
puts( "Fib(", 4, ") =", phi(4) );
1000行くらいのコードで関数の再帰的な定義が動くインタープリタが完成しました. 満足です. ちなみに『Go言語でつくるインタプリタ』の本文は Hello world で終わっていて「やり遂げた」感がすごいです (このために文字列と puts 関数まではがんばって実装しました).
感想
字句解析や AST に関して知りたかったことが実装できて満足です. 『Go言語でつくるインタプリタ』の記述は口語調で手取り足取りという感じで, インタプリタ実装のチュートリアルをこなしている感じです. ただ, まずテストを提示してそれをパスするように実装するというテスト駆動開発スタイルで書かれているんですが, Rust 移植する際にテストを書こうにも自分のコードの型設計を決めないとテストが書きづらく, そのためには後の Go 実装をのぞき見しないといけないというあたりで若干苦労しました. とはいえ, Go に特徴的な機能・構文は出てこないため, Go を一行も書いたことがなかったですが, Go のコードを理解できないということはなかったです. AST やインタプリタの仕組みに興味があるが予備知識が足りなさそうで手を出せずにいる方におすすめの本です.