「Go言語でつくるインタプリタ」をRustで実装しました。

はじめに

こんにちは。DSOC 研究開発部 Architect Group Data Direction Teamの有山です。
気温が上がってきて夏っぽくなってきましたね。毎年夏用にTシャツを集めるのが趣味なのですが、今年は個人的にブームが再燃してるGOODENOUGH*1を古着で集めようかなと考えています。

ところで皆さんは普段何の言語を書いていますか? Data Direction Groupでは主にPythonを使用していますが、ある時から四則演算の計算順序やif文の条件分岐はどうして正しく動くのだろうと疑問に思うようになり、実際に正しく動かしているシステムを理解してみたくなりました。色々検討した結果、「Go言語で作るインタプリタ」という本が内容的にも分量的にもちょうどよく、これを読み進めることにしました。

初めは読みながらコードを写経していましたが、複雑なロジックについては理解した気になってしまっていたので、いい機会と思いGo以外の言語でちょうど気になっていたRustで移植してみました。今回はインタプリタの実装や、Rustで実装する上でのポイントついて紹介していこうと思います。

成果物

できたインタプリタは下記となります。GoのソースコードをRustで模倣したものなのでリポジトリ名はimitation_interpreterとしました。
github.com

学習用のため、改行がサポートされていない等多少の不具合がありますが、変数への代入やif文、関数の使用など最低限のプログラミングはできるようになっています。
実行環境はcargo*2をインストールしていればローカルで、してないけど動かしてみたいという方はDockerfileをREADMEに記載のコマンドでdocker runしてみてください。

この本について

この本はmonkeyというC言語ライクな架空のプログラミング言語を評価するインタプリタの実装を、Goのソースコードを中心に解説しています。この本の内容を最後まで読むと下記のプログラムを評価するインタプリタを作ることができます。

• C言語風の構文
• 変数束縛
• 整数と真偽値
• 算術式
• 組み込み関数
• 第一級の高階関数
• クロージャ
• 文字列データ型
• 配列データ型
• ハッシュデータ型

実装はインタプリタを図の赤枠のパーツに分割し、段階的に実装していきます。

次の章から実際に一部のソースコードや図を使いつつ、これらのパーツの実装について解説していこうと思います。

字句解析器

まずはじめに開発するのは字句解器です。字句解析とはソースコードを解釈しやすい形式にすることで、プログラムを単語に分割し、それぞれの単語に型をつけることです。
例えばlet x = 5;というプログラムがあった場合、このプログラムはlet、x、=、5、;という型のついた単語に分割され、構文解析器に渡されます。この単語のことをトークンと呼びます。
実装としては、monkeyで出力する単語の種類をトークンとして定義し、それを字句解析器(Lexer)がパターンマッチングで解析していきます。

pub enum TokenKind {
     ILLEGAL,     // ILLEGAL
     EOF,         // EOF

    // identifier and literal
     IDENT,       // IDENT
     INT,         // 123...

    // operator
     ASSIGN,      // =
     PLUS,        // +

     LPAREN,      // (
     RPAREN,      // )

     // keyword
     FUNCTION,    // FUNCTION
     LET,         // LET
}
pub struct Token {
    pub token_type: TokenKind,
    pub literal: String
}

pub struct Lexer<'a>  {
    input:        &'a str,
    position:     usize, // current input position
    read_position: usize, // next input position
    ch:           u8, // a letter which is currently read
}

impl<'a>  Lexer<'a>  {
    pub fn new(input: &'a str) -> Self {
        let mut l = Lexer{
                      input,
                      position: 0,
                      read_position: 0,
                      ch: 0
                    };
        l.read_char();
        return l;
    }

    pub fn new_token(token_type: TokenKind, ch: u8)-> Token {
        Token {
              token_type,
              literal: String::from_utf8(vec![ch]).unwrap(),
        }
    }

    pub fn next_token(&mut self) -> Token { 
        // スペースに意味はないためスキップする。
        self.skip_whitespace();
        let token;
        match self.ch { // ソースコードをパターンマッチしてトークンを定義する。
            b'*' => {
                token = Self::new_token(TokenKind::ASTERISK, self.ch);
            }
            b'/' => {
                token = Self::new_token(TokenKind::SLASH, self.ch);
            }
            b'<' => {
                token = Self::new_token(TokenKind::LT, self.ch);
            }
            b'>' => {
                token = Self::new_token(TokenKind::GT, self.ch);
            }
        self.read_char();
        return token;
    }
}

new()メソッドでソースコードを受け取り、next_token()メソッドで単語をパターンマッチしてトークンの構造体を返します。monkeyはスペースに意味を持たせないため、このメソッドの中でスキップする処理を行います。
let five = 5;の結果は以下のようになります。

Token { token_type: LET, literal: "let" }
Token { token_type: IDENT, literal: "five" }
Token { token_type: ASSIGN, literal: "=" }
Token { token_type: INT, literal: "5" }
Token { token_type: SEMICOLON, literal: ";" }

構文解析器

次に開発するのは構文解析器、いわゆるパーサーです。このパーサーを実装することで、例えば1 + 2 * 3のような計算を正しい優先順位で計算することができます。
このパーサーの実装では、プログラムの優先順位をシンプルに表すために木構造を組み立てます。1 + 2 * 3というプログラムを例にすると下記の木ができます。

また、もう少し複雑な計算をする場合は、さらに木のネストを深くします。例えば4 + 5 * (6 - 7) + 8 * 9だと以下のようになります。

この木のことを抽象構文木(Abstract syntax tree; AST)と言い、これを最深部の左から右の順に計算していきます。ここで「抽象」とつくのはこの木が必要最低限の要素だけで表現されるからです。例えば上の例でいうカッコは、計算上必要ですが、木を作る上では冗長なのでASTには出現しないということです。
ASTを解説するためにわかりやすく四則演算を例に挙げましたが、一般的なプログラムもこのASTを作って解釈していきます。

実装では、プログラム(Program)をrootとして、文(Statement)、式(Expression)にプログラムを分解して構文解析します。文とは戻り値がなく、それ単独で完結する言語要素で、式は戻り値があり、文の一部となるものです。
例えば、let x = 1 * (2 + 3);を構文解析した場合、以下のようなASTができます。この場合、文はlet x =1 * (2 + 3);のことで、式は1 * (2 + 3)です。1 * (2 + 3)はlet文の一部ですし、実行すれば5が返ってきますね。ここを理解するのはやや難しいかもしれませんが、ノートなどに式をASTで書いてみると理解しやすくなると思います。

実装はenumでStatement、Expressionを作り、パターンを網羅的に定義して、パーサーがパターンマッチして解析していきます。

pub struct Program {
    pub statements: Vec<Statement>
}
pub enum Statement {
    LetStatement{identifier: Expression,
                 value: Expression},
    Return(Expression),
    ExpressionStatement(Expression),
    Block(Vec<Statement>),
}
pub enum Expression {
    Identifier(String),
    String(String),
    Integer(i32),
}

pub struct Parser<'a>  {
    lexer: lexer::Lexer<'a>,
    current_token: Token,
    next_token: Token,
}

impl<'a>  Parser<'a>  {
    pub fn new(l: lexer::Lexer<'a>) -> Self {
        let mut p = Parser{
            lexer: l,
            current_token: Token{token_type: TokenKind::DEFAULT, literal: "default".to_string() },
            next_token: Token{token_type: TokenKind::DEFAULT, literal: "default".to_string() },
        };
        p.next_token();
        p.next_token();
        p
    }
    pub fn parse_program(&mut self) -> Result<Program, Errors> {
        let mut statements: Vec<Statement> = vec![];

        // read token until it reaches at the end of the sentence.
        while !self.is_current_token(TokenKind::EOF){
            let statement = self.parse_statement()?;
            statements.push(statement);
            self.next_token();
        };
        Ok(Program {statements: statements})
    }

    fn parse_statement(&mut self) -> Result<Statement, Errors> {
        match self.current_token.token_type {
            TokenKind::LET => {
                Ok((self.parse_let_statement()?))
            },
            TokenKind::RETURN => {
                Ok(self.parse_return_statement()?)
            },
            _ => {
                Ok(self.parse_expression_statement()?)
            }
        }
    }
    fn parse_expression(&mut self, precedence: Precedence) -> Result<Expression, Errors> {
        let mut exp = match self.current_token.token_type {
            TokenKind::IDENT => {Expression::Identifier(self.parse_identifier()?)},
            TokenKind::STRING => {Expression::String(self.parse_string()?)},
            TokenKind::INT => Expression::Integer(self.parse_integer()?),
            TokenKind::TRUE => Expression::Bool(true),
            _ => return Err(Errors::TokenInvalid(self.current_token.clone()))
        };
    }
}

字句解析した結果をnew()メソッドで受け、parse_program()メソッドで再帰的にASTを構築していきます。
let x = 1 * (2 + 3)の結果は下記のようになります。

LetStatement { 
    identifier: Identifier("x"),
    value: InfixExpression { 
        left_expression: Integer(1),
        operator: "*",
        right_expression: InfixExpression {
             left_expression: Integer(2),
             operator: "+",
             right_expression: Integer(3)
             }
        }
  }

評価

最後は評価を開発します。本書では構文解析器で構築したASTを順番通りにホスト言語(Rust)で逐次実行していきます。このような方法をTree-walkingインタプリタと呼びます。余談ですが、Ruby1.8以下ではこの方法が実際に使われていたそうです。(1.9以降はパフォーマンス向上のため、ASTをバイトコードにコンパイルし、仮想マシン上で評価する方式に変わったそうです。)
ちなみにこの辺りからRustの文法に慣れてきて実装するのが楽になっていく実感がありました。
実装はホスト言語で表現するために、Objectという型を定義し、ASTの値をObjectに変換していきます。

pub enum Object {
    Identifier(String),
    String(String),
    Integer(i32),
    Boolean(bool),
    Return(Box<Object>),
    Let(Box<Object>),
    Array(Vec<Object>),
}

    pub fn evaluate(&mut self, program: &ast::Program) -> Result<Object, Errors> {
        let mut result = Object::Default;
        // evaluate sentence per semicolon.
        for statement in program.statements.iter() {
            result = self.evaluate_statement(statement)?;
            // if statement contains 'return', process should be broken and return value.
            if let Object::Return(value) = result {
                return Ok(*value)
            }
            // if the result of evaluation, process should be broken.
            if result == Object::Error(Errors::InvalidInfix){
                return Ok(result)
            }
        }
        Ok(result)
    }
    fn evaluate_statement(&mut self, statement: &ast::Statement) -> Result<Object, Errors> {
        match statement {
            ast::Statement::ExpressionStatement(expression) => self.evaluate_expression(expression),
            ast::Statement::Block(stmt) => self.evaluate_block_statements(stmt),
            ast::Statement::Return(expression) => {
                                    let return_expression = self.evaluate_expression(expression)?;
                                    Ok(Object::Return(Box::new(return_expression)))
                                    },
            ast::Statement::LetStatement{identifier ,value} => {
                                                 if let Expression::Identifier(identifier) = identifier {
                                                    // if expression is identifier, evaluate value, and 
                                                    // append identifier as variable.
                                                    let evaluated_value = self.evaluate_expression(&value)?;
                                                    let value = self.set(identifier.to_owned(), evaluated_value);
                                                    return Ok(value)
                                                 }
                                                 Ok(Object::Null)
                                                },
            _ => Err(Errors::NodeError),
            }
        }
fn evaluate_expression(&mut self, expression: &ast::Expression) -> Result<Object, Errors> {
    match expression {
        ast::Expression::String(value) => Ok(Object::String(value.to_owned())),
        ast::Expression::Integer(value) => Ok(Object::Integer(*value)),
        ast::Expression::Bool(bool) => Ok(Object::Boolean(*bool)),
        ast::Expression::Array(value) =>{
            let array = self.evaluate_arguments(value.to_vec())?;
            Ok(Object::Array(array))
        }
    }
}

evaluate_expression()関数で受け取った式をひたすらObjectに変換していきます。
let x = 5; x; を評価した場合、Integer(5)という結果が返ります。ターミナルには5という結果が表示されて欲しいですが、ここはRustのFormatterという、値を適当に整形して表示してくれる機能を使って表現することにしました。

pub enum Object {
    Integer(i32),
}

impl fmt::Display for Object {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
       match self {
           // Integerの内部の値のみ表示される。
           Object::Integer(value) => write!(f, "{}", value), 

Rustで実装できるようになるまでにやったこと

Rustは一般的に他の言語と比べて学習コストが高い言語と言われています。その理由は多機能な言語であるということが大きいですが、それとは別にWebで調べた時のナレッジが他の言語と比べても少ないということもあると思います。
このブログでRustの文法を解説していくのは限界がある一方で、少しでもナレッジ不足が改善すればと思い、今回は参照した書籍やドキュメントについて時系列に軽く解説していこうと思います。

実装前

まず開発を始める前に、公式ドキュメントを読み進めました。無料かつ、とても丁寧に書かれているため、初めに読むドキュメントとしてはとてもよかったと思います。
11章くらいまでの知識は必須そうだったので一通り読み、序盤の数当てゲームのプログラムを写経しながら文法を覚えていきました。後の章は関係ありそうなところだけやるようにしました。そのため、ほとんど手をつけてない分野もありこの辺りは課題かなと思ってます。

実装中

実装中は主に公式ドキュメントと合わせてプログラミング言語Rust入門を参照して進めました。この本はC言語など、Rustのベース知識を知らなくても理解できるように初心者向けに書かれているのでとてもわかりやすかったです。
Rustは文字列の扱いや型変換が他の言語と比べて難しい印象ですが、筆者もその気持ちを汲んでくれたのかページを多く割いて丁寧に解説してくれていたのがよかったです。DBアクセスやWebAPIの使用など、普段の開発でも使いそうなサンプルコードが載っているのも魅力的で、Rustを現場で使うという方にもお勧めできます。

また、Rustで同じようなことをしているGithubリポジトリを探してコミットログを参考にする事もしました。問題集の答えを見るようで敬遠する人もいるのかもしれませんが、本ではカバーしきれない記法やライブラリについて学べたり、コミットログを追うことで自分がハマったポイントをどう回避しているのかを知る事もできるのでとても参考になりました。

Rustを書く上でやっておいたほうが良いこと

rls(Rust Language Server)を使って開発環境を構築する。

Rustは型や所有権システムという独自の機能を持つことから制約の多い言語です。そのため、コンパイルエラーで引っかかることが多く、今回の開発もエラーを直していくうちに動くものができたという感覚でした。(自分が不慣れだったこともあります。)
普段VSCodeをエディタとして使用していますが、これにrls*3というExtensionをインストールすることでエディタ上で文法エラーや型の確認を行うことができ、開発時間の節約につながりました。特にRustは型制約があるにも関わらずプログラム上で型を確認することが難しいので、この型の確認をエディタでできるというのはすごく助かりました。

また、テストを行う場合も関数単位で実行できるので、パターンマッチで新規で開発した関数だけをデバッグしたいという時にとても便利でした。

インストールは下記を参考に行いました。
marketplace.visualstudio.com

返り値の型にはResult型を使う。

構文解析器や評価の実装方針として、トークンをパターンマッチしてそれを処理する関数を実行していきます。そのため、トークンごとに段階的に関数を実装してmatch文を拡張させていくわけですが、未実装のトークンに対しては、実装していないので適切な型を持つ返り値を返せないという問題があります。

この場合、Result型という正常終了した時の値(Ok(T))と異常終了した時の値(Err(E))の値を返り値として定義できる型を使います。上のコード例だと、enumで定義したExpression型を正常終了時、Errors型を異常終了時の返り値として定義しています。APIを使った実装など、関数内でエラーを返したいというのはよくあることだと思いますが、Result型を使うことでその辺りを自由度高く実装できると思います。
Errorsは専用のerrors.rsファイルにenumで定義しておいて細かくエラー定義をしておくとエラーハンドリングが楽になるかなと思います。

最後に

テストコードを入れて約2千行でインタプリタを実装することができ、言語処理やRustへの入門としてはとてもいい勉強になりました。(まえがきに専門書とブログの中間を目指したと記載があり、その通りだったかも?)
特に構文解析器のロジックを実装し、複雑な式をパースできたときは計算式がなぜ正しく動くのかを理解できた実感がありました。Rustは評判の通り学習コストの高い言語で、書きはじめのころはかなりつらい思いをしましたが、所有権システムなど、Rust固有の文法を学ぶことはプログラミングの低レイヤを学ぶことになるので、普段スクリプト言語で開発している身としては学び甲斐のある良い言語だったなと今は思っています。

このブログを書くタイミングで知ったのですが、この本にはWriting A Compiler In Goという続編があるので、せっかく覚えたRustの知識を風化させないためにも今度はコンパイラを作ってみようかなと考えています。
ちなみに今回紹介した本は弊社のGeekSeek*4という制度で購入し、同じDSOCのエンジニアである藤田、湯村と3名で、同制度で勉強会を開いて読み進めていてました。
こういうエンジニアフレンドリな制度を認めてくれる会社や勉強会の企画等をしてくれた二人には感謝したいと思います。

最後となりますが、現在Data Direction Teamでは、共に働く仲間を募集しています。
ご興味のある方がいらっしゃれば、まずはお話だけでも構いませんのでお問い合わせをお待ちしています。
hrmos.co

*1:日本のストリートブランドで藤原氏がデザイナーを務めた。2017年で活動終了している。

*2:Rustのコードをビルド、実行、テスト、パッケージ管理ができる、Rustで開発するなら必ず使うツール。https://doc.rust-jp.rs/book/second-edition/ch01-03-hello-cargo.html

*3:Rust Language Serverの略で、IDEやエディタにRustプログラムに色々な補完をしてくれるバックエンドサーバー。https://github.com/rust-lang/rls

*4:生産性向上のためにガジェット、ソフトウェア、書籍を会社負担で購入できる制度。詳しくはこちらのブログで紹介されています。