🐷

Brainfuck を書いた

2022/07/30に公開

こんにちは

どうも、僕です。
最近、Twitter のスペースで typefuck という TypeScript の型定義だけで Brainfuck を表現するというものを教えてもらい、自分も Brainfuck を書いてみるかという気持ちになったので実装してみました。

Brainfuck に関しては、意外と実装してる人が多く、割と有名なジョークプログラムなんだなと感じたと同時に、派生言語が非常に多く、難読化に精を出している人が多くて驚きました。

自分の場合はあまり面白いジョークや難読化手法は思いつかなかったので仕様通りに実装をしてみました。（takurinton の10文字から、n の重複を除いた9文字を用いて命令を当てはめ、残った1文字は rm -rf / を実行するというようなものは思いつきましたが、あまりにも evil と判断したためやめました）

コードは takurinton/bf にあります。

https://github.com/takurinton/bf

Brainfuck とは

Brainfuck とは、コンパイラがなるべく小さくなるように設計されているチューリング完全の言語で、可読性や記述性が低く、上でも述べましたが難読性を高くしたり等の派生言語が多い言語になっています。
https://ja.wikipedia.org/wiki/Brainfuck

基本的な命令は8種類あり、以下のようになっています。
ここで定義されていない命令は無視されて次の処理に移ります。
非常にシンプルですが、非常にわかりにくいです。

命令	挙動
`>`	ポインタをインクリメントする
`<`	ポインタをデクリメントする
`+`	ポインタの指すメモリの値をインクリメントする
`-`	ポインタの指すメモリの値をデクリメントする
`.`	ポインタが指すメモリの値を出力する（print）
`,`	入力から1バイト読み込んでポインタが指すメモリの値に代入する
`[`	ポインタが指すメモリの値が0なら対応する `]` にジャンプする
`]`	ポインタが指すメモリの値が0でなければ対応する `[` にジャンプする

hello world

他の方の記事でも多く触れられていますが、「Hello World!\n」と出力するコードは以下のようになります。
すごいです。

一度書き込んだメモリは保存されてるので、例えば hello world は l が3回出現するのでそれを使い回す、なんてこともできます。

++++++++++
[
    >+++++++
    >++++++++++
    >+++++++++++
    >+++
    >+++++++++
    >+
    <<<<<<-
]
>++.
>+.
>--.. // l を2回出力してる、hello の ll の部分
+++.
>++.
>---.
<<.
+++.
------.
<-.
>>+.
>>.

Brainfuck の実行

今回実装した Brainfuck では、以下のような形で動くことを想定しています。文字列として Brainfuck のコードを持っておき、それを main 関数の中で実行しています。ソースコードのファイルを読み込んだり、インタプリタのような機能は現段階では想定していません。実装予定もないと思います。

実行の順番としては、

コードを定義する
コードを lexer 関数に入れてtoken の配列に変換する
取得した token の配列を run 関数に渡し、実行結果の文字列を得る
println! を用いて出力する

といった順序で処理が進みます。
その順番を示した、Hello World!\n と出力する main.rs は以下のようになります。

main.rs

mod bf;
mod tests;

fn main() {
    // print "Hello World!\n"
    let code = "++++++++++
[
    >+++++++
    >++++++++++
    >+++++++++++
    >+++
    >+++++++++
    >+
    <<<<<<-
]
>++.
>+.
>--..
+++.
>++.
>---.
<<.
+++.
------.
<-.
>>+.
>>.";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    let result = match output {
        Ok(output) => output,
        Err(error) => {
            println!("{:?}", error);
            return;
        }
    };
    println!("{}", result);
}

実行する方法はわかったので、次は実装の中身を見ていきます。

Token

まず、コードを解析するには Token を定義する必要があります。
Brainfuck で扱うための8つの命令を enum で定義していきます。

#[derive(Debug, PartialEq)]
pub enum Token {
    MoveRight,    // >
    MoveLeft,     // <
    Increment,    // +
    Decrement,    // -
    Output,       // .
    Input,        // ,
    JumpForward,  // [
    JumpBackward, // ]
}

次に、入力されてきた文字列を定義した Token に割り当てるトレイトを定義します。
lexer 関数をこの後定義しますが、そこでループを回し命令を1つずつ受け取る際に、この match で判定して Token に変換していきます。

impl Token {
    fn from_str(character: char) -> Option<Self> {
        match character {
            '>' => Some(Token::MoveRight),    // Move the pointer to the right.
            '<' => Some(Token::MoveLeft),     // Move the pointer to the left.
            '+' => Some(Token::Increment),    // Increment the value at the pointer.
            '-' => Some(Token::Decrement),    // Decrement the value at the pointer.
            '.' => Some(Token::Output),       // Output the value at the pointer.
            ',' => Some(Token::Input),        // Input a value at the pointer.
            '[' => Some(Token::JumpForward),  // Jump forward to the matching ] if the value at the pointer is zero.
            ']' => Some(Token::JumpBackward), // Jump backward to the matching [ if the value at the pointer is nonzero.
            _ => None,                        // This is treated as an unexpected token inside the lexer
        }
    }
}

Error

lexer 関数を定義する前に、Error を定義します。
今回定義する Error は以下の2種類です。

#[derive(Debug, PartialEq)]
pub enum Error {
    UnknownTokenError,
    RuntimeError,
}

1つずつ、想定するシーンを説明していきます。

UnknownTokenError

UnknownTokenError は Brainfuck で扱う8つの命令以外の命令（例えば a のようなアルファベット文字列）が入ってきた時に吐くエラーです。
本来、Brainfuck は8つ以外の文字列は無視して実行を進めるのですが、今回はここも縛るようにしました。
lexer 関数で入力を判定するときに呼ばれることを想定しています。

RuntimeError

RuntimeError はメモリがオーバーフロー・アンダーフローした時、または何かしらの理由でプログラムが panic を起こしたときにエラーとして丸めて返すために仕様します。
主に run 関数で呼ばれることを想定しています。

lexer

lexer 関数では、文字列でもらったコードを Vec<Token> にして Result 型にラップして　run 関数に渡せる状態にします。

例えば、

>>.

のような入力がきたら

[MoveRight, MoveRight, Output]

のような形で返すことを想定しています。
また、想定していない文字列が入ってきた場合は UnknownTokenError を返します。

コードは以下のようになっています。

pub fn lexer(code: String) -> Result<Vec<Token>, Error> {
    let tokens = code
        .chars()
        .filter(|c| match c {
	    // スペースや改行などを除外している、これをしないと UnknownTokenError として扱われてしまう
            ' ' | '\n' | '\r' | '\t' => false,
            _ => true,
        })
        .map(|character| {
            Ok(match Token::from_str(character) {
                Some(token) => token,
                None => return Err(Error::UnknownTokenError),
            })
        })
        .collect::<Result<Vec<Token>, Error>>()?;
    Ok(tokens)
}

run

run 関数は、lexer 関数で生成した Vec<Token> を用いて実際に Brainfuck の振る舞いを実装しています。

使う変数の定義

まずは、使う変数の定義をしますが、必要なのは

memory
pointer
input
output
index（ループで使う）
tokens（unwrap したもの）

になります。
メモリやポインタは Rust の配列と数字で表現します。
また、token　を検証する際には tokens をインデックスで参照する必要があるため、index も定義しておきます。当初、tokens は配列なのでイテレータとして扱えばいいと思っていたのですが、JumpForward と JumpBackward の際にジャンプする際にインデックスをこちらで握れないと実現できないのでこのような手法にしました。

実際に定義したものは以下になります。

let mut memory = vec![0; 256];
let mut pointer = 0;
let mut input = vec![];
let mut output = String::new();
let mut index = 0;
let tokens = tokens.unwrap();

token の処理

while 文を使い、index が tokens の長さを超えるまで繰り返します。
上で述べたように、JumpForward と JumpBackward の処理があるので token[index] のような参照方法になることを想定しています。
ループの中では match 式を用いてどの token に対応するのかを確かめ、1つずつ処理をしていきます。

while index < tokens.len() {
    match token[index] {
        ...
    }
}

MoveRight

MoveRight の処理は、pointer を見て256（最大値）ならばインクリメントするとオーバーフローしてしまうので RuntimeError を、そうでなければ pointer をインクリメントする処理を書いています。

Token::MoveRight => match pointer {
    256 => return Err(Error::RuntimeError),
    _ => pointer += 1,
},

MoveLeft

MoveLeft は MoveRight の逆で、アンダーフローをした際に RuntimeError を吐くようにしています。特に問題がなければデクリメントを行います。

Token::MoveLeft => match pointer {
    0 => return Err(Error::RuntimeError),
    _ => pointer -= 1,
},

Increment

Increment は MoveRight と同様にメモリの最大値を超えたら RuntimeError になるようにします。理由は同じでオーバーフローを防ぐためです。

Token::Increment => match pointer {
  256 => return Err(Error::RuntimeError),
  _ => memory[pointer] += 1,
},

Decrement

Decrement では、pointer の値が -1 の際にアンダーフロー（意図したインデックス参照にならない）が起きるため、pointer + 1 が 0 だったら RuntimeError を吐くようにします。
これは、pointer はインデックス参照のための整数として扱う想定で、パターンマッチで -1 という値を使えないため、pointer + 1 が 0 だった時のパターンマッチを行っています。

Token::Decrement => match pointer + 1 {
    0 => return Err(Error::RuntimeError),
    _ => memory[pointer] -= 1,
},

Output

Output の時は、現在のポインタが指すメモリの値を char 型にして output に追加します。
これが最終的な出力になります。
ここのエラーハンドリングとなると、どうなるんでしょう。少し思いつかなかったので保留にしてあります。（output.push した後の配列の長さが期待した数かどうかとか...？）

Token::Output => {
    output.push(memory[pointer] as u8 as char);
}

Input

Input では、input から読み込み、現在のポインタが指すメモリに代入します。
割とそのままな感じの処理になっています。

Token::Input => {
    let input_value = input.pop().unwrap();
    match input_value {
        _ => memory[pointer] = input_value,
    }
}

JumpForward

JumpForward では、対応する Backward を探します。
depth はネストしてる際の深さを表していて、対応していない Backward を誤って見つけないようにしています。

ここでは index を操作して対応する Backward を探しにいきますが、対応するものが見つからないとインデックスが増えてしまいエラーになるので、そのようなときには RuntimeError を吐くようにしています。

Token::JumpForward => match memory[pointer] {
    0 => {
        let mut depth = 1;
        let max = tokens.len();
        while depth > 0 {
            index += 1;
            if index >= max {
                return Err(Error::RuntimeError);
            }
            match tokens[index] {
                Token::JumpForward => depth += 1,
                Token::JumpBackward => depth -= 1,
                _ => (),
            }
        }
    }
    _ => {}
},

JumpBackward

JumpBackward では、対応する Forward を探します。
depth は JumpForward の時同様、ネストしてる際の深さを表していて、対応していない Forward を誤って見つけないようにしています。

エラーも、対応する Forward 同様、対応する Forward がない際にはインデックスが下がり続けてしまうのでそのような際には RuntimeError を吐くようにしています。

Token::JumpBackward => match memory[pointer] {
    0 => {}
    _ => {
        let mut depth = 1;
        while depth > 0 {
            index -= 1;
            match index {
                0 => return Err(Error::RuntimeError),
                _ => match tokens[index] {
                    Token::JumpForward => depth -= 1,
                    Token::JumpBackward => depth += 1,
                    _ => (),
                },
            }
        }
    }
},

全体のコードはこのようになります。

pub fn run(tokens: Result<Vec<Token>, Error>) -> Result<String, Error> {
    let mut memory = vec![0; 256]; // 30000 isn't enough for me.
    let mut pointer = 0;
    let mut input = vec![];
    let mut output = String::new();
    let mut index = 0;
    let tokens = tokens.unwrap();
    while index < tokens.len() {
        match tokens[index] {
            Token::MoveRight => match pointer {
                256 => return Err(Error::RuntimeError),
                _ => pointer += 1,
            },
            Token::MoveLeft => match pointer {
                0 => return Err(Error::RuntimeError),
                _ => pointer -= 1,
            },
            Token::Increment => match pointer {
                256 => return Err(Error::RuntimeError),
                _ => memory[pointer] += 1,
            },
            Token::Decrement => match pointer + 1 {
                0 => return Err(Error::RuntimeError),
                _ => memory[pointer] -= 1,
            },
            Token::Output => {
                let value = memory[pointer] as u8 as char;
                match value {
                    _ => output.push(value),
                }
            }
            Token::Input => {
                let input_value = input.pop().unwrap();
                match input_value {
                    _ => memory[pointer] = input_value,
                }
            }
            Token::JumpForward => match memory[pointer] {
                0 => {
                    let mut depth = 1;
                    let max = tokens.len();
                    while depth > 0 {
                        index += 1;
                        if index >= max {
                            return Err(Error::RuntimeError);
                        }
                        match tokens[index] {
                            Token::JumpForward => depth += 1,
                            Token::JumpBackward => depth -= 1,
                            _ => (),
                        }
                    }
                }
                _ => {}
            },
            Token::JumpBackward => match memory[pointer] {
                0 => {}
                _ => {
                    let mut depth = 1;
                    while depth > 0 {
                        index -= 1;
                        match index {
                            0 => return Err(Error::RuntimeError),
                            _ => match tokens[index] {
                                Token::JumpForward => depth -= 1,
                                Token::JumpBackward => depth += 1,
                                _ => (),
                            },
                        }
                    }
                }
            },
        }
        index += 1;
    }

    Ok(output)
}

テスト

プログラミング言語を作るならテストは必要です。
今回は lexer 関数と run 関数のテストを書きました。
全て網羅できてはいないのですが、最低限は担保できていると思います。

lexer

lexer では、以下の3つを確認するテストを行いました。

正しい長さの Token の配列が返ってきてるかどうか
Token が正しくマッピングできているか
期待しない Token が入ってきた際に UnknownTokenError を吐くかどうか

1つずつ見ていきます。

正しい長さの Token の配列が返ってきてるかどうか

これは、空文字や改行文字を含めた上で正しく Brainfuck の Token の長さが返ってきているかどうかを確かめるテストです。
正直、これは Rust の filter 関数のテストのようになってしまっているため不要かなと思いましたが、自分の考慮漏れの可能性を潰しておきたいので定義しました。

#[test]
fn test_lexer_length() {
    let code = " ><+-.,[]\n";
    let tokens = bf::lexer(code.to_string()).unwrap();
    assert_eq!(tokens.len(), 8);
}

Token が正しくマッピングできているか

これは、入ってきた Token が正しくマッピングできているか愚直に試しています。

#[test]
fn test_lexer() {
    let code = "><+-.,[]";
    let tokens = bf::lexer(code.to_string()).unwrap();
    assert_eq!(tokens[0], bf::Token::MoveRight);
    assert_eq!(tokens[1], bf::Token::MoveLeft);
    assert_eq!(tokens[2], bf::Token::Increment);
    assert_eq!(tokens[3], bf::Token::Decrement);
    assert_eq!(tokens[4], bf::Token::Output);
    assert_eq!(tokens[5], bf::Token::Input);
    assert_eq!(tokens[6], bf::Token::JumpForward);
    assert_eq!(tokens[7], bf::Token::JumpBackward);
}

UnknownTokenError を吐くかどうか

最後は Brainfuck で用いられる8つの命令以外の文字列が入ってきたときに、UnknownTokenError を吐くかどうかを確かめるテストです。ここでは abc という文字列を入れました。

#[test]
fn test_lexer_unexpected_token() {
    // code containts an unexpected token
    let code = "abc";
    let tokens = bf::lexer(code.to_string());
    assert_eq!(tokens, Err(bf::Error::UnknownTokenError));
}

run

run では大きく分けて以下の2つを確認するテストを行いました。

正しい出力がされる
オーバーフロー・アンダーフローの際や、対応する Forward/Backward が見つからなかった際に RuntimeError を吐くかどうか

正しい出力がされる

正しい出力がされるかどうかのテストです。
コードはいくつか用意しましたが、Braincfuck Text Editor というものを見つけたので、これを利用してテストを書きました。（自分で書くのは少し大変だったので）

#[test]
fn run_test_hello_world() {
    let code = "+++++++++[>++++++++<-]>.<+++++++++[>+++<-]>++.+++++++..+++.<+++++++++[>--------<-]>-------.<+++++++++[>++++++<-]>+.<+++++++++[>++<-]>++++++.+++.------.--------.<+++++++++[>-------<-]>----.<+++++++++[>++++++<-]>+++++.<+++++++++[>++<-]>.";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output.unwrap(), "Hello World!\n");
}

#[test]
fn run_test_takurinton() {
    let code = "+++++++++[>++++++++++++<-]>++++++++.<+++++++++[>--<-]>-.<+++++++++[>+<-]>+.<+++++++++[>+<-]>+.---.<+++++++++[>-<-]>.+++++.++++++.-----.-.";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output.unwrap(), "takurinton");
}

#[test]
fn run_test_add_number() {
    let code = "+++++++++[>+++++<-]>++++++.";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output.unwrap(), "3");
}

#[test]
fn run_test_multiplication_number() {
    let code = "+++++++++[>++++++<-]>++.";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output.unwrap(), "8");
}

RuntimeError を吐くかどうか

RuntimeError は、メモリのオーバーフロー・アンダーフロー、Forward/BackWard が対応していないときに起きるエラーです。
それらが正しく呼ばれるかどうかを、以下のテストケースで担保しました。

#[test]
fn test_run_move_right_overflow() {
    let code = ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

#[test]
fn test_run_move_left_underflow() {
    // underflow inumum pointer
    let code = "<";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

#[test]
fn test_run_increment_memory_overflow() {
    let code = ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

#[test]
fn test_run_decrement_memory_overflow() {
    let code = ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

#[test]
fn test_run_not_close_jump_forward() {
    let code = "[[[[";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

#[test]
fn test_run_not_open_jump_backward() {
    // ポインタが0の時は呼ばれないので、あらかじめ上げておく
    let code = "+++]]]]";
    let tokens = bf::lexer(code.to_string());
    let output = bf::run(tokens);
    assert_eq!(output, Err(bf::Error::RuntimeError));
}

まとめ

今回は愚直に Brainfuck の仕様通りの実装を行いましたが、おそらく Brainfuck のトランスパイラ等の難読化方面とはまた違う方面に舵を切る実装ができるとさらに面白みが期待できるのかなと思いました。

この記事で Brainfuck という言語の温度感と実装の容易性、入門のしやすさが伝われば嬉しいです。
インターネット上では多くの人が独自の Brainfuck や高速化、wasm として動かす等の実装をしています。
皆さんの俺の考えた最強の Brainfuck を見れる日を楽しみにしています。

こんにちは

Brainfuck とは

hello world

Brainfuck の実行

Token

Error

UnknownTokenError

RuntimeError

lexer

run

使う変数の定義

token の処理

MoveRight

MoveLeft

Increment

Decrement

Output

Input

JumpForward

JumpBackward

テスト

lexer

正しい長さの Token の配列が返ってきてるかどうか

Token が正しくマッピングできているか

UnknownTokenError を吐くかどうか

run

正しい出力がされる

RuntimeError を吐くかどうか

まとめ

Discussion