blog.livewing.net

Brainf*ck インタプリタを作りつつ Rust を紹介

Brainf*ck は 8 種類の文字のみを用いるチューリング完全なプログラミング言語です。今回はインタプリタを Rust で作ってみます。正直 Brainf*ck インタプリタ実装の記事というよりは Rust の紹介記事みたいになっています。

Rust とは

Rust はメモリ安全なシステムプログラミング言語で、 C 言語とほぼ同等の速度で動きます。ガベージコレクションはありません。ダングリング参照を生成するなど怪しい書き方でプログラムを書くとコンパイルすら通らなくなります。メモリ管理が正しく行われているかどうかのチェックをプログラマがやらなくてよくなります。スレッドセーフに関してもコンパイラのチェックが入ります。

配列アクセス時のインデックスも範囲チェックが入るので、バッファオーバーランが起こりません。デバッグビルドではただの値のオーバーフローすらもチェックが入り、オーバーフローした際は panic しプログラムが停止します。ハードコードした 0u32 - 1 という式はコンパイルすら通りませんでした。もちろん、範囲チェックを明示的に無効にする関数もあります(unsafe ブロック内でやる必要がある可能性があります)。

一方、 if など構文のほとんどが式だったり、パターンマッチ機能も豊富なので、その手の方にとってはたまらないわけです。Swift などにある、値を持てる enum がパターンマッチングと合わせてバリバリ活用されています。型推論も「ここまでやるか」と思うほどよく効きます。マクロも C 言語のような単純置換ではなく言語を拡張するよう作用するので、予期しないエラーが発生しません。マクロで Rust コード中に React JSX みたいなものを書けるライブラリ yew なんかもあったりします。手続きマクロに至っては、展開中に外部コマンドの実行はおろかネットワークアクセスもできるなんでもありなマクロも定義できます。

さらに Rust コンパイラのバージョンを管理する rustup やパッケージマネージャの cargo が優秀すぎるので、 Rust の言語自体に慣れてしまえば快適に開発できます。もう C 言語を安心して書けないねぇ

プロジェクト作成

rustup で Rust をインストールしてから cargo new コマンドを叩いてプロジェクトを作ります。

$ cargo new bf-rs
$ cd bf-rs

試しに cargo run で一度実行してみましょう。まだ何もプログラムを書いていないけど。

$ cargo run
   Compiling bf-rs v0.1.0 (/path/to/bf-rs)
    Finished dev [unoptimized + debuginfo] target(s) in 0.14s
     Running `target/debug/bf-rs`
Hello, world!

ここまでで、 Rust や周辺ツールのインストールとプロジェクトの作成、 Hello, world! プログラムの作成とビルド、さらに実行までできました。あまりにも簡単すぎる。一生世界に挨拶している人や、 C 言語で ! を表現するのに \n を使っている人はここまでで終わりです。お疲れ様でした。

src/main.rs
fn main() {
    println!("Hello, world!");
}

ちなみに cargo new の時点で git init の実行と .gitignore の作成も自動で済んでいます。

Visual Studio Code で書く人は、拡張機能 matklad.rust-analyzer と vadimcn.vscode-lldb を入れて設定すると超快適にコーディングとデバッグができます。

ディレクトリ構成

単一プロジェクトの場合、ディレクトリ構成は極めてシンプルです。

bf-rs/
|- .git/       <- Git リポジトリ
|- .gitignore  <- Git で管理対象外とするファイルのリスト
|- Cargo.toml  <- クレート情報と依存クレートリスト
|- Cargo.lock  <- インストールされる依存クレートの正確なバージョンリスト
|- src/        <- ソースディレクトリ
|  `- main.rs  <- ソースファイル
`- target/     <- ビルド成果物など

基本的に、 Cargo.toml と src/ ディレクトリ内を操作します。

Cargo.toml は Node.js で言う package.json です。プロジェクトの名前やバージョン、依存するパッケージ(クレート)を列挙します。

Cargo.lock は Node.js で言う package-lock.json や yarn.lock です。依存するクレートの正確なバージョンのリストが自動で生成されます。このファイルは異なる環境での整合性を保つためにコミットしましょう。

src/ ディレクトリはその通りです。この中にプログラムを書いていきます。

target/ ディレクトリはビルドの成果物やドキュメントなどが入ります。バージョン管理システムからは外しておきましょう (cargo new で作ったならすでに .gitignore に書かれています)。

字句解析器を作る

ここからが本題です。 Brainf*ck の字句解析器(笑)を作ります。

と言っても 8 種類の文字しか使わないので、それ以外を全部取っ払って残ったものを配列に突っ込めば字句解析は終了です。

トークン一覧

使用する文字をおさらいしておくと、以下のようになります。ここで、 ptr はメモリのポインタを表します。

文字意味C 言語では
>ポインタをインクリメントptr++
<ポインタをデクリメントptr--
+ポインタが指す値をインクリメント(*ptr)++
-ポインタが指す値をデクリメント(*ptr)--
.ポインタが指す値を出力putchar(*ptr)
,入力から 1 byte 読んでポインタが指す先に格納*ptr = getchar()
[ポインタが指す値が 0 なら対応する ] の直後へジャンプwhile(*ptr) {
]ポインタが指す値が 0 でないなら対応する [ の直後へジャンプ}

token モジュールの作成

それでは早速作っていきましょう。まずは src/main.rs に token モジュールの宣言を書きます。

src/main.rs
mod token;

fn main() {
    println!("Hello, world!");
}

token モジュールの本体は src/token.rs に書きます。トークンは Token 列挙体で表すことにします。

src/token.rs
#[derive(Debug, PartialEq)]
pub enum Token {
    IncrementPointer,
    DecrementPointer,
    IncrementValue,
    DecrementValue,
    Output,
    Input,
    LoopBegin,
    LoopEnd,
}

enum 宣言の前に derive 属性が付いています。これは、括弧内の機能 (トレイト) を自動実装してくださいという意味になります。 Debug トレイトを実装することで、デバッグ出力をすることができるようになります。 PartialEq トレイトは、値の比較をすることができるようになります。これらは後の単体テストで役に立ちます。

enum 宣言の中身は見た通りだと思います。

次に、文字列スライス型 &str からトークン配列 Vec<Token> へ字句解析する tokenize 関数を作ります。

src/token.rs
pub fn tokenize(src: &str) -> Vec<Token> {
    let mut v = vec![];
    for c in src.chars() {
        v.push(match c {
            '>' => Token::IncrementPointer,
            '<' => Token::DecrementPointer,
            '+' => Token::IncrementValue,
            '-' => Token::DecrementValue,
            '.' => Token::Output,
            ',' => Token::Input,
            '[' => Token::LoopBegin,
            ']' => Token::LoopEnd,
            _ => continue,
        });
    }
    v
}

この関数では、

  1. トークンの空配列を作る
  2. 引数の文字列を 1 文字ずつ見て、 Token 列挙体の値に変えてトークン配列に追加
  3. トークン配列を返す

を行っています。

vec![] マクロで Vec<Token> 型の空配列 (配列というよりは動的配列、 C++ での std::vector に似ています) を作ります。特に型を指定していませんが、コンパイラが後の使用方法を見て完璧に推論しています。 let mut v: Vec<Token> = vec![]; とすれば明示的に型を指定できます。この配列の中身は操作されるので、 mut キーワードで変数を可変(ミュータブル)にする必要があります。試しに mut キーワードを外すとコンパイルエラーが出ます。 Rust では基本的にイミュータブルな世界であることを覚えておきましょう。

src.chars() で src の文字を走査するイテレータを取得できます。これを順番に回して行きます。

v.push() で配列 v の末尾に値を追加することができます。 push() に渡している引数に注目してください。 match 構文が引数の括弧内にドーンと書かれています。

Rust の match は C 言語での switch に相当します。しかし、 Rust の match は文ではなく式であり、match の各アームでは、文ではなく式が指定されているため、 match c { ... } がそのまま値となります。

_ はすべてにマッチするパターンです。 Brainf*ck では上記 8 種類の文字以外はすべてコメント扱いなので、 continue で次の文字へ進んでいます。

「continue は Token 型じゃないから match 式はコンパイルエラーじゃね?」という声が聞こえてきそうですが、 Rust の continue は ! 型 (never 型) であり、すべての型の subtype となります (TypeScript の never 型と同じです) 。したがって match 式全体の型は Token となります。

関数の最後では、セミコロン無しで v とだけ書かれています。 Rust の関数は、一番最後の式が return されます。つまり return v; という意味になります。セミコロンを付けてしまうと、式ではなく文になり、戻り値の型が () となってしまいます (空のタプルが unit 型となっています) 。

Rust では、代入や return は基本的にムーブなので、 tokenize 関数から return するときに v が無駄にコピーされることなく呼び出し元に返ります。 C++11 のように return std::move(v); みたいなことをする必要はありません。右辺値がどうこうは気にする必要無いわけです (C++ は C++ で楽しいけどね) 。

プログラムのチェック

Rust でプログラムを組んでいるときは、定期的にプログラムが正しく書かれているかどうかをコンパイラにチェックしてもらいましょう。

プロジェクトのルートディレクトリで cargo check を実行します。

$ cargo check
warning: variant is never constructed: `IncrementPointer`
 --> src/token.rs:3:5
  |
3 |     IncrementPointer,
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(dead_code)]` on by default

(中略)

warning: variant is never constructed: `LoopEnd`
  --> src/token.rs:10:5
   |
10 |     LoopEnd,
   |     ^^^^^^^

warning: function is never used: `tokenize`
  --> src/token.rs:13:8
   |
13 | pub fn tokenize(src: &str) -> Vec<Token> {
   |        ^^^^^^^^

warning: 9 warnings emitted

    Finished dev [unoptimized + debuginfo] target(s) in 0.00s

cargo check は、コンパイラにプログラムのチェックをしてもらうコマンドです。チェックをするだけで、ビルド自体は行いません。ビルドをしないのですばやくチェックできます。ちなみにビルドするときは cargo build です。そのまんまですね。

今回は「値が一切作られていないよ」「未使用のコードがあるよ」という警告が出力されています。

Rust のコンパイラは優秀で、メッセージが見やすいだけではなく改善するヒントが盛り込まれていることが多い印象です。

試しに tokenize 関数の最後を v から v; としてみましょう。式ではなく文になるためエラーとなります。

$ cargo check
    Checking bf-rs v0.1.0 (/path/to/bf-rs)
error[E0308]: mismatched types
  --> src/token.rs:13:31
   |
13 | pub fn tokenize(src: &str) -> Vec<Token> {
   |        --------               ^^^^^^^^^^ expected struct `std::vec::Vec`, found `()`
   |        |
   |        implicitly returns `()` as its body has no tail or `return` expression
...
28 |     v;
   |      - help: consider removing this semicolon
   |
   = note: expected struct `std::vec::Vec<token::Token>`
           found unit type `()`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0308`.
error: could not compile `bf-rs`.

To learn more, run the command again with --verbose.

help: consider removing this semicolon と出ています。「このセミコロンを取り除いてみては?」と言っています。

使えるエディタが制限されている環境 (そんなものはないと信じたい) でも快適に開発ができます。

Visual Studio Code で先述の通り rust-analyzer 拡張機能を入れて設定すれば、保存時に自動でチェックが走るようにすることもできます。おすすめです。

単体テストを書く

Rust にはテスト機能までもが組み込まれています。単体テストでは、実装のすぐそばにテストコードを書けるので、見た目もスッキリするし TDD (テスト駆動開発) もしやすくなります。

src/token.rs の末尾にテストモジュールとテストコードを書きます。

src/token.rs
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn tokenize_test() {
        assert_eq!(
            tokenize("><+-.,[]hello"),
            vec![
                Token::IncrementPointer,
                Token::DecrementPointer,
                Token::IncrementValue,
                Token::DecrementValue,
                Token::Output,
                Token::Input,
                Token::LoopBegin,
                Token::LoopEnd,
            ]
        );
    }
}

#[cfg(test)] は、ビルド設定が test の時のみ有効になるコードであることを示しています。つまり、 debug や release 構成などの場合はこのコードが無視されるということです。この tests モジュールはテスト時のみにしか使わないので cfg 属性を指定しています。

use super::*; は、 C++ での using namespace のようなものです。スコープ外のものをスコープに取り入れます。 super は特殊なパスで、 1 つ上のモジュールを参照します。 * はすべてのものなので、この use 文では 1 つ上のモジュール内のすべてを use するということになります。

この文がなければ、 tests モジュール内で super::Token::IncrementPointer みたいに書かなければいけなくなります。面倒なので use 文を使ってスコープに取り入れているわけです。 use super::*; はテストモジュールでの定型文みたいなものです。

テストコードは #[test] 属性がついた関数内に書きます。関数名は何でもいいです。

テストコードが何事もなく終了すると、そのテストは成功扱いになります。テストコード内で panic が発生し、進行不能になるとそのテストは失敗扱いになります。

今回のテストコードでは、 assert_eq マクロが使われています。文字通り、 2 つの引数が等価であることを表明するコードです。等価でない場合は panic マクロで panic します。

もちろん、 assert_ne マクロもあります。単に値が true であることを表明する assert マクロも使えます。 panic 時にテスト成功とする #[should_panic] 属性もあります。

テストを書いたら走らせましょう。実行方法は、もうお分かりですよね。 cargo test です。

$ cargo test
Compiling bf-rs v0.1.0 (/path/to/bf-rs)
    Finished test [unoptimized + debuginfo] target(s) in 0.21s
     Running target/debug/deps/bf_rs-****************

running 1 test
test token::tests::tokenize_test ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

無事にテストが通りました。お手軽にテストを書いて実行することができます。

ドキュメントコメントを書く

もう少し Rust の機能について書かせてください。ドキュメントコメントを書くと、それに基づいてドキュメントページを生成することができます。少し書いてみましょう。

src/token.rs
//! トークンの種類と字句解析。

/// Brainf*ck のトークン。
#[derive(Debug, PartialEq)]
pub enum Token {
    /// ポインタをインクリメント。
    IncrementPointer,
    /// ポインタをデクリメント。
    DecrementPointer,
    /// ポインタが指す値をインクリメント。
    IncrementValue,
    /// ポインタが指す値をデクリメント。
    DecrementValue,
    /// ポインタが指す値を出力。
    Output,
    /// 入力から 1 byte 読んでポインタが指す先に格納。
    Input,
    /// ポインタが指す値が 0 なら対応する `]` の直後へジャンプ。
    LoopBegin,
    /// ポインタが指す値が 0 でないなら対応する `[` の直後へジャンプ。
    LoopEnd,
}

通常の行コメントは // で始まりますが、ドキュメントコメントは /// で始まります。また、モジュール自体のドキュメントコメントは //! で始まります。

ドキュメントコメントを書いたら、 cargo doc でドキュメントページを生成できます。 cargo doc --open とすれば、ページ生成後に自動で Web ブラウザが開きます。

$ cargo doc --open
 Documenting bf-rs v0.1.0 (/path/to/bf-rs)
    Finished dev [unoptimized + debuginfo] target(s) in 0.56s
     Opening /path/to/bf-rs/target/doc/bf_rs/index.html

cargo doc では、自分が書いたドキュメントだけではなく、依存するクレートのドキュメントも生成されるので、オフラインでもドキュメントを参照できます。

ドキュメントコメント内でテストを行う doctest 機能もあります。コードの使用例を doctest として載せることで、「ドキュメント通り同じコードなのにうまく動かないじゃないか」といった事態を防ぐことができます。

ちなみにドキュメントコメント内では Markdown が使えます。つよい。

インタプリタを作る

話がずれましたが、いよいよインタプリタを作ります。

interpreter モジュールの作成

token モジュールと同じように、 interpreter モジュールを作ります。

src/main.rs
mod token;
mod interpreter;

fn main() {
    println!("Hello, world!");
}

構造体の定義

Interpreter という名前の構造体に、インタプリタの機能を実装していきます。まずはフィールドを定義します。

src/interpreter.rs
use crate::token::Token;

const MEMORY_SIZE: usize = 30000;

pub struct Interpreter {
    code: Vec<Token>,
    pc: usize,
    memory: [u8; MEMORY_SIZE],
    pointer: usize,
}

最初の use 文は、テストの時と同じように現在のスコープに Token を導入します。 crate は super と同様特殊なパスで、現在のクレートのルートを表しています。

const 文ではコンパイル時定数を宣言します。後述する配列の配列長はコンパイル時に値が分かっていないといけないので、 const 文で定義します。 Brainf*ck のメモリは最低 30000 bytes あれば良いので 30000 と定義しています。

struct 文で構造体を定義します。 code は Brainf*ck のコード、 pc はプログラムカウンタ、 memory はメモリ、 pointer はメモリのポインタをそれぞれ表します。 memory では [u8; MEMORY_SIZE] という型を書いています。これは u8 型の値を MEMORY_SIZE 個格納できる配列を表しています。

Rust ではプリミティブ型の名前が非常にわかりやすくつけられています。

整数型を以下に示します。 bit 数がプラットフォームの行は、 32 bit マシンなら 32 bit、 64 bit マシンなら 64 bit です。

bit 数符号付き符号無し
プラットフォームisizeusize
8i8u8
16i16u16
32i32u32
64i64u64
128i128u128

浮動小数点数型はお察しの通り、 f32 と f64 です。

というわけで、 [u8; MEMORY_SIZE] は 8 bit 符号なし整数の値を MEMORY_SIZE 個格納できる配列型となります。

各フィールドには pub キーワードがついていないため、プライベートフィールドになります。

コンストラクタの定義

フィールドの定義が終わったので、コンストラクタを定義します。

Rust では、コンストラクタメソッド特有の構文は無く、構造体のフィールドをすべて指定して初期化する構文となっています。しかし、毎回その構文だと面倒なので、関連関数を作ってやることが多いです。作りましょう。

src/interpreter.rs
impl Interpreter {
    pub fn new(code: Vec<Token>) -> Interpreter {
        Interpreter {
            code,
            pc: 0,
            memory: [0; MEMORY_SIZE],
            pointer: 0,
        }
    }
}

impl Interpreter の中には、 Interpreter に関連する関数を定義します。関連関数は、所謂インスタンスメソッドや static メソッドを定義します。関連関数の第 1 引数が self などである場合はインスタンスメソッドとなり、それ以外の場合は static メソッドになります。

今回書いた new 関数は static メソッドとなり、 Interpreter::new(...) で呼び出すことができます。

new 関数の中で、構造体の初期化構文が使われています。 Interpreter { ... } の部分です。この中に各フィールドの値を書きます。 JavaScript のオブジェクトリテラルとほぼ同じ記法です。

code の部分は code: code とも書けます。 JavaScript と同じように、フィールド名と変数名が同じなら省略して書けます。

memory の [0; MEMORY_SIZE] は、すべての要素が 0 である MEMORY_SIZE 個の配列を表しています。

プログラムカウンタとポインタは両方 0 で初期化して return してこの関数は終わりです。一番最後の式 (Interpreter { ... }) が return され、呼び出し元にムーブされます。

これで、 Brainf*ck プログラムのトークン列を受け取ってインタプリタを返す new 関数が完成しました。引数も基本的にムーブされるので、 new 関数を呼んだ後は呼び出し元で code を再利用できません。呼び出し元で再利用することは無いので、このような設計にしています。引数で参照を取れば再利用できますが、 Interpreter にライフタイムの指定が必要となります。その場合、 Interpreter インスタンスより code の参照の方が長生きでないとコンパイルエラーになります。

実行部分の枠組みを作る

インタプリタの肝となる部分を書きます。まずは入出力で必要になるトレイトを use します。

interpreter.rs
use std::io::{Read, Write};

impl ブロックの中に run 関数を追加します。途中まで書きます。

src/interpreter.rs
impl Interpreter {
    // (略)

    pub fn run(mut self, input: &mut impl Read, output: &mut impl Write) {
        while self.pc < self.code.len() {
            match self.code[self.pc] {
                _ => todo!("処理を書く"),
            }
            self.pc += 1;
        }
    }
}

関数の引数がすごいことになっていますが、そんなに難しくありません。

mut self は、所謂インスタンスメソッドの this にあたる引数です。 mut がついているので関数内で self を変更することができます。型を書いていませんが self の場合は自動的に self: Self となります。 Self 型は特殊な型で、実態はこの場合 Interpreter となります。

&mut impl Read と &mut impl Write は、それぞれ Read トレイトと Write トレイトを実装する任意の型を表します。静的ディスパッチするジェネリクスです。 mut がついているので変更可能です。さらに & がついているので参照を受け取ります。参照なので呼び出し元から関数内へ引数がムーブされることがありません。

この input と output を使って入出力を行います。

mut self には & がついていないので、 run 関数の実行後は self がスコープ外となり、破棄されます。実行後のポインタやメモリの状態は特に意味がないので破棄します。

関数の中身は至って普通です。 while でプログラムカウンタが最後になるまでループします。 match でプログラムポインタ部分のトークン通りの処理を行います。

処理はまだ書いていないので todo マクロを置いておきます。コメントで // TODO と書く時代は終わりました。

各トークンの処理を作る

match 内の処理を書いていきます。と言っても LoopBegin と LoopEnd 以外はそんなに難しくないのでささっと行きます。

src/interpreter.rs
match self.code[self.pc] {
    Token::IncrementPointer => self.pointer += 1,
    Token::DecrementPointer => self.pointer -= 1,
    Token::IncrementValue => {
        self.memory[self.pointer] = self.memory[self.pointer].wrapping_add(1);
    }
    Token::DecrementValue => {
        self.memory[self.pointer] = self.memory[self.pointer].wrapping_sub(1);
    }
    Token::Output => {
        output.write(&[self.memory[self.pointer]]).unwrap();
    }
    Token::Input => {
        let mut buf = [0; 1];
        input.take(1).read(&mut buf).unwrap();
        self.memory[self.pointer] = buf[0];
    }
    Token::LoopBegin => {
        if self.memory[self.pointer] == 0 {
            let mut p = self.pc + 1;
            let mut b = 1;
            loop {
                match self.code[p] {
                    Token::LoopBegin => b += 1,
                    Token::LoopEnd => b -= 1,
                    _ => {}
                }
                if b == 0 {
                    self.pc = p + 1;
                    break;
                }
                p += 1;
            }
            continue;
        }
    }
    Token::LoopEnd => {
        if self.memory[self.pointer] != 0 {
            let mut p = self.pc - 1;
            let mut b = 1;
            loop {
                match self.code[p] {
                    Token::LoopBegin => b -= 1,
                    Token::LoopEnd => b += 1,
                    _ => {}
                }
                if b == 0 {
                    self.pc = p + 1;
                    break;
                }
                p -= 1;
            }
            continue;
        }
    }
}

IncrementPointer と DecrementPointer は解説不要でしょう。 Rust にはインクリメント演算子 (++) やデクリメント演算子 (--) は無いので加算代入や減算代入演算子で書きます。

IncrementValue と DecrementValue も簡単ですが、 wrapping_add や wrapping_sub で加減算を行っています。Rust ではデバッグモードにおいては算術オーバーフローでも panic します。ポインタはオーバーフローが許されませんが、メモリにある値はオーバーフローしても大丈夫なので (というかオーバーフローを利用している Brainf*ck プログラムもある) 、オーバーフローを無視する wrapping_add や wrapping_sub を噛ませています。

Output は Write トレイトの機能を使って出力を書き込んでいます。 write 関数には、書き込むデータの配列の参照を渡します。ここでは、配列リテラルの参照をそのまま関数に渡しています。 write 関数の戻り値は Option 型で、 Rust において成功と失敗を表す型として頻繁に使われます。 Option 型の値はそのまま放っておくとコンパイラが警告を出すので、 unwrap を呼んで Option の処遇を決めています。 unwrap は、失敗を表す None だった場合、 panic する関数です。つまり、 write 関数が失敗した時は unwrap で panic します。

Input も同様に Read トレイトの機能を使って入力を受け取っています。まずデータ受け取り用のバッファ buf を用意します。 input に対して take 関数で 1 byte のみ読み出すようアダプタを作成して、 read で読み込みます。ここでも同様に unwrap します。

LoopBegin と LoopEnd では、 Brainf*ck プログラムを走査し、対応する括弧を探してジャンプする処理を行っています。 let mut p は走査用のプログラムカウンタ、 let mut b は走査時に遭遇した括弧の個数をカウントしています。対応する括弧が見つかったら、 self.pc にプログラムカウンタをセットして continue します。

これで Brainf*ck インタプリタの愚直な実装は終わりです。

もう少し簡単に実行できるようにする

入出力はほとんどの場合で標準入出力を使うと思うので、それを指定済みの run_with_stdio 関数を作りましょう。まず use 文から。

src/interpreter.rs
use std::io::{stdin, stdout, Read, Write};

もう気づいていると思いますが use 文はある程度まとめられます。

そして impl ブロック内に run_with_stdio 関数を追加します。

src/interpreter.rs
impl Interpreter {
    // (略)

    pub fn run_with_stdio(self) {
        self.run(&mut stdin(), &mut stdout());
    }
}

std::io::stdin と std::io::stdout はそれぞれ Read と Write トレイトを実装しています。

&mut である引数なので、引数を渡す側も &mut をつけます。つけなかったらコンパイルエラーです。エラーになったとしても &mut をつけろと提案されるので迷わないはずです。

run_with_stdio の引数 self に mut をつけなくていいのかと思う人もいると思いますが、結局 self は run 関数にムーブされるのでここでのミュータビリティは関係ありません。

Brainf*ck プログラムの実行

字句解析器とインタプリタができたので、あとは Brainf*ck プログラムを作って流し込むだけです。

Brainf*ck プログラムの読み込み

Brainf*ck プログラムを読み込む方法ですが、もちろんファイルを開いて読み込むのも良いです。しかしここでは簡単のため include_str マクロを使います。 include_str マクロを使うと、コンパイル時にテキストファイルを文字列スライス (&str) として埋め込むことができます。

src/main.rs 内の main 関数を書き換えます。

src/main.rs
use interpreter::Interpreter;
use token::tokenize;

fn main() {
    let src = include_str!("../bf/hello.bf");
    let code = tokenize(src);
    let interpreter = Interpreter::new(code);
    interpreter.run_with_stdio();
}

include_str マクロで Brainf*ck プログラムのソースコードを埋め込んでいます。 include_str に渡すパスは、マクロ呼び出しをしているソースファイル (つまり src/main.rs ) から見た相対パスです。

Brainf*ck プログラムを書く

bf/hello.bf に Brainf*ck プログラムを書きます。Brainf*ck プログラムの作成については割愛します。正直ここが一番しんどい

bf/hello.bf
+++++++++[>+>+++++>++++++++>+++++++++++<<<<-]>>>.>++.+++++++..+++.<<-.----------
--.>>++++++++.--------.+++.------.--------.<<+.<+.

これは Hello, world! を出力する Brainf*ck プログラムです。

保存して実行してみましょう。

$ cargo run
   Compiling bf-rs v0.1.0 (/path/to/bf-rs)
    Finished dev [unoptimized + debuginfo] target(s) in 0.32s
     Running `target/debug/bf-rs`
Hello, world!

できました。

複雑なプログラムを実行する

マンデルブロ集合を描画する Brainf*ck プログラムを作った人がいるらしいので、それを実行してみます。

Index of /brainfuck/utils/mandelbrot

この中の mandelbrot.b を使ってみます。実行には時間が掛かりそうなので、 release ビルドで実行します。 cargo run --release でビルドと実行ができます。

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB

綺麗に描画されましたが……あまりにも実行が遅すぎる。手元のマシンでは約 35 秒掛かりました。

というわけで次節からはインタプリタの高速化を行います。

インタプリタ高速化の方針

なぜこんなに遅いのか。

加減算をまとめる

今まで作ってきたインタプリタは愚直に 1 文字ずつ処理していました。

++++++++++

この Brainf*ck プログラムは指し示している値に 10 を加算するコードですが、これを 1 文字ずつ読み取って 1 ずつ加算していたら遅くて当たり前です。

これをまとめて「10 加算する」という命令にまとめてしまうことで実行時間の短縮が図れそうです。所謂ランレングス圧縮ですね。 Brainf*ck でプログラムカウンタがジャンプする位置は [ と ] だけなので + はまとめてしまっても問題ありません。

+ だけではなく - や > 、 < に関しても同じです。

イディオム

命令をまとめるのは単純な文字の連続のみではありません。

[-]

この Brainf*ck プログラムは指し示している値が 0 になるまで 1 を減算し続けるコードです。つまり、指し示している場所に 0 をセットします。

同じようにこれもまとめてしまいましょう。ループせず 0 を代入するようにすれば一瞬で終わります。

Brainf*ck には他にも色々なイディオムがありますが、割愛します。

ループのジャンプ位置をキャッシュ

[ と ] でジャンプする場所を毎回探索しているので遅くて当たり前です。実行中にプログラム自身を書き換える術は無いので、上記の命令をまとめる処理が終わった後、対応する [ と ] の場所はキャッシュしてしまいましょう。

高速化してみる

Token から Instruction への変換

まず、前節の「加減算をまとめる」と「イディオム」を実装します。

Brainf*ck プログラムは単に Token の列をそのまま実行していました。 Token を直接実行するのをやめ、 Token をより高レベルな Instruction に変換します。

optimize モジュールを作ります。

src/main.rs
mod optimize;

まず Instruction 列挙体を作ります。

src/optimize.rs
#[derive(Debug, PartialEq)]
pub enum Instruction {
    IncrementPointer(usize),
    DecrementPointer(usize),
    IncrementValue(usize),
    DecrementValue(usize),
    Output,
    Input,
    LoopBegin,
    LoopEnd,
    ZeroClear,
}

Token 列挙体とはいくつか異なります。

IncrementPointer などの末尾に (usize) とついています。Rust では、列挙体の値に付随する値を持たせることができます。 IncrementPointer(usize) では、ポインタをいくつインクリメントするかの値を持たせています。他も同様です。

また、 ZeroClear が追加されています。 Token には含まれない命令なので新しく追加しました。

LoopBegin と LoopEnd の括弧の対応についてはまだ手を加えません。

Instruction 列挙体ができたので、 Token 列を Instruction 列に変換する optimize 関数を作ります。が、その前にトークン列の判定をする関数を作りましょう。 count_run_length 関数と starts_with_zero_clear 関数です。

src/optimize.rs
fn count_run_length(code: &[Token]) -> usize {
    let first = &code[0];
    let mut count = 0;
    for token in code {
        if token == first {
            count += 1;
        } else {
            break;
        }
    }
    count
}

fn starts_with_zero_clear(code: &[Token]) -> bool {
    code.len() >= 3 && &code[0..3] == &[Token::LoopBegin, Token::DecrementValue, Token::LoopEnd]
}

これらは、 Token 列のスライス (配列の一部分の参照) を受け取って、結果を返す関数です。

count_run_length はスライスの先頭の要素が何個連続するかを返します。単純にスライスの先頭からループを回して、連続している回数をカウントしているだけです。

starts_with_zero_clear はスライスの先頭 3 要素が [-] になっているかどうかを調べます。スライスの len 関数でスライスの長さが 3 以上であることを確認し、かつ先頭 3 要素と配列を比較して一致しているかどうかを判定します。

ここで、スライス操作について説明します。 スライス slice に対して、 &slice[..] とすると、スライスのコピーを作ります。 &slice[1..3] とすると、スライスの [1, 3) の半開区間のスライスを取得できます。スライスの区間の先頭と末尾はそれぞれ省略可能で、省略した場合は先頭や末尾を指定したものとして扱われます。

作成した 2 つの関数とスライス操作を用いて optimize 関数を書くとこうなります。

src/optimize.rs
pub fn optimize(code: &[Token]) -> Vec<Instruction> {
    let mut v = vec![];
    let mut code = &code[..];
    while code.len() > 0 {
        let length;
        v.push(match code[0] {
            Token::IncrementPointer => {
                length = count_run_length(code);
                Instruction::IncrementPointer(length)
            }
            Token::DecrementPointer => {
                length = count_run_length(code);
                Instruction::DecrementPointer(length)
            }
            Token::IncrementValue => {
                length = count_run_length(code);
                Instruction::IncrementValue(length)
            }
            Token::DecrementValue => {
                length = count_run_length(code);
                Instruction::DecrementValue(length)
            }
            Token::Output => {
                length = 1;
                Instruction::Output
            }
            Token::Input => {
                length = 1;
                Instruction::Input
            }
            Token::LoopBegin => {
                if starts_with_zero_clear(code) {
                    length = 3;
                    Instruction::ZeroClear
                } else {
                    length = 1;
                    Instruction::LoopBegin
                }
            }
            Token::LoopEnd => {
                length = 1;
                Instruction::LoopEnd
            }
        });
        code = &code[length..];
    }
    v
}

基本的には token モジュールの tokenize 関数と同じですが、この関数ではスライスを使っています。

まず、引数 code をミュータブルなスライスとして再定義しています。 Rust では同名の変数を定義できます。同名の変数を定義された側 (最初からあった変数) は隠されます。この機能により変数名で悩むことが少し減ります。

次に while ループです。スライス code の長さが 0 になるまでループが回ります。ということは、ループ中にスライスの区間がどんどん短くなるよう更新されます。

while ループの中では、まず length という変数が宣言だけされています。この変数は後で必ず代入されます。

v に対して push を呼んでいます。この引数の match 式で Token から Instruction に変換されます。まず、 match 式でスライス code の先頭の Token で場合分けします。

Token::IncrementPointer など 4 つの場合では、同じトークンが連続している回数を数え、 Instruction::IncrementPointer(length) などを match 式の値とします。 length には、消費した Token 列のトークン数を代入しておきます。

Token::LoopBegin でも同様に判定を行い、ゼロクリアイディオムだった場合は Instruction::ZeroClear を match 式の値とします。 if も式なので、このような芸当が可能です。

v に対する push が終わったら、消費したトークン分、スライスの開始位置を更新する必要があります。 &code[length..] で更新します。 length は必ず代入されているため、エラーは起こりません。代入忘れがあると当然コンパイルエラーです。変数未初期化によるランタイムエラーはあり得ません。

すべてのトークンを消費したら、 Instruction 配列である v を返します。ムーブです。

ここでは触れていませんが、テストコードを書くことを推奨します。

本当はパーサコンビネータを使えばエレガントに変換処理ができますが、今回はまだ単純な例なので先頭から走査する方式としました。興味がある方はパーサコンビネータでも実装してみてください (ライブラリがあります) 。

Instruction から LoopCachedInstruction への変換

Instruction に変換できたので、 [ と ] の対応する位置をそれぞれキャッシュし、 LoopCachedInstruction へと変換します。 cache モジュールを作りましょう。

src/main.rs
mod cache;

LoopCachedInstruction 列挙体を作ります。

src/cache.rs
#[derive(Debug, PartialEq)]
pub enum LoopCachedInstruction {
    IncrementPointer(usize),
    DecrementPointer(usize),
    IncrementValue(usize),
    DecrementValue(usize),
    Output,
    Input,
    LoopBegin(usize),
    LoopEnd(usize),
    ZeroClear,
}

Instruction の LoopBegin と LoopEnd に対応位置を格納する usize 型の値を持たせます。

cache 関数でキャッシュを作ります。 use 文は適宜入れてください。

src/cache.rs
pub fn cache(instructions: &[Instruction]) -> Vec<LoopCachedInstruction> {
    let mut v = vec![];
    for (i, instruction) in instructions.iter().enumerate() {
        v.push(match instruction {
            Instruction::IncrementPointer(l) => LoopCachedInstruction::IncrementPointer(*l),
            Instruction::DecrementPointer(l) => LoopCachedInstruction::DecrementPointer(*l),
            Instruction::IncrementValue(l) => LoopCachedInstruction::IncrementValue(*l),
            Instruction::DecrementValue(l) => LoopCachedInstruction::DecrementValue(*l),
            Instruction::Output => LoopCachedInstruction::Output,
            Instruction::Input => LoopCachedInstruction::Input,
            Instruction::LoopBegin => {
                let mut p = i + 1;
                let mut b = 1;
                loop {
                    match instructions[p] {
                        Instruction::LoopBegin => b += 1,
                        Instruction::LoopEnd => b -= 1,
                        _ => {}
                    }
                    if b == 0 {
                        break;
                    }
                    p += 1;
                }
                LoopCachedInstruction::LoopBegin(p)
            }
            Instruction::LoopEnd => {
                let mut p = i - 1;
                let mut b = 1;
                loop {
                    match instructions[p] {
                        Instruction::LoopBegin => b -= 1,
                        Instruction::LoopEnd => b += 1,
                        _ => {}
                    }
                    if b == 0 {
                        break;
                    }
                    p -= 1;
                }
                LoopCachedInstruction::LoopEnd(p)
            }
            Instruction::ZeroClear => LoopCachedInstruction::ZeroClear,
        });
    }
    v
}

基本的に LoopBegin と LoopEnd でキャッシュ処理を行う以外はそのまま変換しています。

for では instructions.iter().enumerate() としています。 iter でスライスからイテレータを生成し、 enumerate でインデックスつきのイテレータを生成しています。これにより、インデックスを取りながら反復処理を行うことができます。

Instruction::IncrementPointer(l) で、付属する値を l として取り出すことができます。 l は参照なので、 LoopCachedInstruction に変換する際は *l として参照外しをする必要があります。

キャッシュ処理は Interpreter で実装した処理とほぼ同じです。解説は省略。

高速化に対応したインタプリタを作る

fast_interpreter モジュールに FastInterpreter 構造体を作ります。

src/main.rs
mod fast_interpreter;

Token 列の代わりに LoopCachedInstruction 列を持つ以外、フィールドは変わりません。 run 関数もお察しの通りだと思うので全部載せます。

src/fast_interpreter.rs
use crate::cache::LoopCachedInstruction;
use std::io::{stdin, stdout, Read, Write};

const MEMORY_SIZE: usize = 30000;

pub struct FastInterpreter {
    code: Vec<LoopCachedInstruction>,
    pc: usize,
    memory: [u8; MEMORY_SIZE],
    pointer: usize,
}

impl FastInterpreter {
    pub fn new(code: Vec<LoopCachedInstruction>) -> FastInterpreter {
        FastInterpreter {
            code,
            pc: 0,
            memory: [0; MEMORY_SIZE],
            pointer: 0,
        }
    }

    pub fn run(mut self, input: &mut impl Read, output: &mut impl Write) {
        while self.pc < self.code.len() {
            match self.code[self.pc] {
                LoopCachedInstruction::IncrementPointer(l) => self.pointer += l,
                LoopCachedInstruction::DecrementPointer(l) => self.pointer -= l,
                LoopCachedInstruction::IncrementValue(l) => {
                    self.memory[self.pointer] = self.memory[self.pointer].wrapping_add(l as u8);
                }
                LoopCachedInstruction::DecrementValue(l) => {
                    self.memory[self.pointer] = self.memory[self.pointer].wrapping_sub(l as u8);
                }
                LoopCachedInstruction::Output => {
                    output.write(&[self.memory[self.pointer]]).unwrap();
                }
                LoopCachedInstruction::Input => {
                    let mut buf = [0; 1];
                    input.take(1).read(&mut buf).unwrap();
                    self.memory[self.pointer] = buf[0];
                }
                LoopCachedInstruction::LoopBegin(p) => {
                    if self.memory[self.pointer] == 0 {
                        self.pc = p + 1;
                        continue;
                    }
                }
                LoopCachedInstruction::LoopEnd(p) => {
                    if self.memory[self.pointer] != 0 {
                        self.pc = p + 1;
                        continue;
                    }
                }
                LoopCachedInstruction::ZeroClear => self.memory[self.pointer] = 0,
            }
            self.pc += 1;
        }
    }

    pub fn run_with_stdio(self) {
        self.run(&mut stdin(), &mut stdout());
    }
}

対応する括弧はキャッシュしてあるので、もとの Interpreter の実装よりもスリムになっています。ジャンプ先は、対応する括弧の直後なので self.pc = p + 1; としています。

改良したインタプリタでの実行

main 関数を書き換えます。プログラムの変換処理が多いので少し長いです。

src/main.rs
fn main() {
    let src = include_str!("../bf/mandelbrot.bf");
    let code = tokenize(src);
    let code = optimize(&code);
    let code = cache(&code);
    let interpreter = FastInterpreter::new(code);
    interpreter.run_with_stdio();
}

そして実行。

$ cargo run --release

当環境では実行時間が約 6.5 秒まで縮みました。 5 倍以上も早くなりました。めでたしめでたし。

おわり

この記事で紹介した Rust の機能はほんの一部です。この記事で Rust に興味を持ってくれた方がいらっしゃるのかどうかは分かりませんが、もし Rust を使ってみたいと思ったら以下のドキュメントから入門することをおすすめします。

Home
Rust（プログラミング言語）の日本語文書・和訳文書、日本語コミュニティ紹介
doc.rust-jp.rs

また、 Brainf*ck は言語仕様が単純であることから、派生言語がたくさん作られています。代表的なものは、オランウータン向けの Ook! や京急の車掌さん向けの KQ 、ご注文はうさぎですか?OP中毒の人向けの Gochiusa があります。これらの言語のインタプリタは tokenize 関数を工夫するだけで作れますので、ぜひお試しください。言語自体を拡張した BrainCrash を実装してみるのも面白いでしょう。 LLVM 等を吐き出せばコンパイラだってできちゃいます。