Rust で Brainfuck
Brainfuck は、インタプリタのサイズが小さくなるように設計されたプログラミング言語です。実装するのがとてもお手軽な一方、Brainfuckで書かれたコードは非常に読みにくくなります。
Rust で Brainfuck のインタプリタを実装してみます。以前、C# で実装してみたことがあるのでそれをRustで書いてみます。
最終的に "Hello World!!" を出力します。ソースコードは以下のようになります。
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-------------.<<+++++++++++++++.>.+++.------.--------.>+..
とりあえず、このソースコードを与えられたら "Hello World!!" とコンソール上に出力されるようなインタプリタを実装していきます。
Brainfuck の言語仕様
Brainfuck の言語仕様は非常にシンプルです。以下 Wikipedia の引用です。
1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
2. < ポインタをデクリメントする。C言語の「ptr–;」に相当。
3. + ポインタが指す値をインクリメントする。C言語の「(ptr)++;」に相当。
4. – ポインタが指す値をデクリメントする。C言語の「(ptr)–;」に相当。
5. . ポインタが指す値を出力に書き出す。C言語の「putchar(ptr);」に相当。
6. , 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「ptr=getchar();」に相当。
7. [ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
8. ] ポインタが指す値が0でないなら、対応する [ （の直後）にジャンプする。C言語の「}」に相当。
Brainfuck のソースコード上には上記8つの文字しか存在しません。それ以外の文字は無視されます。
インタプリタはバイト配列を持ち、配列を参照するためのインデックスであるデータポインタを持ちます。上記 1～4 はバイト配列とデータポインタを操作するための命令です。
5, 6 の命令は入出力です。
7, 8 がループの命令です。
実装サンプル
ということで実装してみました。
#[derive(Debug, Copy, Clone)]
enum Instruction {
Pincrement, // >
Pdecrement, // <
Increment, // +
Decrement, // -
Put, // .
Get, // ,
Begin, // [
End, // ]
None, // その他
}
struct Machine {
memory: [u8; 256],
pointer: usize,
index: usize,
instructions: Vec<Instruction>,
}
impl Machine {
pub fn new(input: &str) -> Self {
// 命令のリストを作成
let mut instructions: Vec<Instruction> = Vec::new();
for c in input.chars() {
match c {
'>' => instructions.push(Instruction::Pincrement),
'<' => instructions.push(Instruction::Pdecrement),
'+' => instructions.push(Instruction::Increment),
'-' => instructions.push(Instruction::Decrement),
'.' => instructions.push(Instruction::Put),
',' => instructions.push(Instruction::Get),
'[' => instructions.push(Instruction::Begin),
']' => instructions.push(Instruction::End),
_ => instructions.push(Instruction::None),
}
}
Machine {
memory: [0; 256],
pointer: 0,
index: 0,
instructions,
}
}
pub fn run(&mut self) {
while self.index < self.instructions.len() {
let instruction = self.instructions[self.index];
self.execute_command(instruction);
self.index += 1;
}
}
pub fn execute_command(&mut self, instruction: Instruction) {
// 命令コマンドを実行
match instruction {
Instruction::Pincrement => self.pointer += 1,
Instruction::Pdecrement => self.pointer -= 1,
Instruction::Increment => self.memory[self.pointer] += 1,
Instruction::Decrement => self.memory[self.pointer] -= 1,
Instruction::Put => {
let c = self.memory[self.pointer] as char;
print!("{}", c);
},
Instruction::Get => {
let mut buf = String::new();
std::io::stdin()
.read_line(&mut buf)
.expect("read_line error");
let value = buf.as_bytes()[0];
self.memory[self.pointer] = value;
},
Instruction::Begin => match self.memory[self.pointer] {
0 => {
let mut bracket_count = 1;
while bracket_count > 0 {
self.index += 1;
match self.instructions[self.index] {
Instruction::Begin => bracket_count += 1,
Instruction::End => bracket_count -= 1,
_ => {},
}
}
}
_ => {}
},
Instruction::End => match self.memory[self.pointer] {
0 => {},
_ => {
let mut bracket_count = 1;
while bracket_count > 0 {
self.index -= 1;
match self.instructions[self.index] {
Instruction::Begin => bracket_count -= 1,
Instruction::End => bracket_count += 1,
_ => {},
}
}
}
},
_ => {},
}
}
}
以下解説です。
Machine 構造体
Machine 構造体はすべての命令と、メモリ用の配列、ポインタ、現在実行中の命令を指すインデックスを値として保持しています。
Rust では、文字列に対してインデックスでの文字単位のアクセスができないので、命令用の列挙体(Instruction)を用意し、8つの命令とその他何もしない命令用の値を作成しています。それぞれがソースコードの1文字に対応します。
Debug はつけなくてもいいです。Copy(Clone) はインデックスで値を取り出したいのでつけています。参照でやり取りすればつけなくても実装できそうです。対応する文字はコメントのとおりです。
#[derive(Debug, Copy, Clone)]
enum Instruction {
Pincrement, // >
Pdecrement, // <
Increment, // +
Decrement, // -
Put, // .
Get, // ,
Begin, // [
End, // ]
None, // その他
}
それからMachine の生成時の処理(Machine::new())で、ソースコード文字列を走査して命令のVecを生成しています。chars() は UTF-8 で1文字ずつ返してくれるので命令に置き換えていきます。
命令の実行
execute_command(&mut self, instruction: Instruction) で指定された命令を実行します。
インクリメント、デクリメント
ポインタのインクリメント、デクリメントは単純にポインタの値を足し引きするだけです。
ポインタが指す値をインクリメント、デクリメントするには、ポインタを配列のインデックスにして、その配列が指す値を足し引きします。
match instruction {
Instruction::Pincrement => self.pointer += 1,
Instruction::Pdecrement => self.pointer -= 1,
Instruction::Increment => self.memory[self.pointer] += 1,
Instruction::Decrement => self.memory[self.pointer] -= 1,
...
}
入出力
出力は簡単です。ポインタが指す値を char 型に変換して出力します。as char で変換できるのは Ascii 文字だけです。u8 以外の型だとコンパイルエラーになります。char 型自体が UTF-8 に対応しているので、u32 などの値も変換できそうですがダメみたいですね。
入力は入力された文字列の先頭1バイトを取得し、ポインタが指す値に設定します。1文字だけ入力を受け付ける方法があるのか不明だったので1行読み取っています。0文字のときどうなるかは知りません。多分パニックに陥ると思います。
match instruction {
// ...
Instruction::Put => {
let c = self.memory[self.pointer] as char;
print!("{}", c);
},
Instruction::Get => {
let mut buf = String::new();
std::io::stdin()
.read_line(&mut buf)
.expect("read_line error");
let value = buf.as_bytes()[0];
self.memory[self.pointer] = value;
},
// ...
}
ループ
ループがこの言語のインタプリタを実装するにあたって一番面倒な部分です。
ループの開始命令("[")では、ポインタの指す値が0のときは、ループの中身を実行せず、対応するループ終了命令("]")の直後までジャンプします。0以外だと何もせず次の命令に進めます。
逆にループ終了命令("]")では、ポインタの指す値が0以外のときに、対応するループの開始命令("[")の直後までジャンプします。0の場合は何もせず次の命令に進みます。
対応する命令までジャンプするので、現在の命令を指すインデックスをいい感じにいじってやる必要があります。注意すべきはループが入れ子になっている以下のようなコードです。
[[][]]
開始の命令を見つけるたびにカウントアップし、終了の命令を見つけるたびにカウントダウンし、カウントが0になった時点で対応する命令を見つけたと判定しています。他にいい方法がありそうですが、ひとまずこれで行けます。
match instruction {
// ...
Instruction::Begin => match self.memory[self.pointer] {
0 => {
let mut bracket_count = 1;
while bracket_count > 0 {
self.index += 1;
match self.instructions[self.index] {
Instruction::Begin => bracket_count += 1,
Instruction::End => bracket_count -= 1,
_ => {},
}
}
}
_ => {}
},
Instruction::End => match self.memory[self.pointer] {
0 => {},
_ => {
let mut bracket_count = 1;
while bracket_count > 0 {
self.index -= 1;
match self.instructions[self.index] {
Instruction::Begin => bracket_count -= 1,
Instruction::End => bracket_count += 1,
_ => {},
}
}
}
},
// ...
}
実行
最後に実行部分です。
pub fn run(&mut self) {
while self.index < self.instructions.len() {
let instruction = self.instructions[self.index];
self.execute_command(instruction);
self.index += 1;
}
}
現在の命令を指すインデックスが、範囲内に存在すれば execute_command() を呼び、命令が終わればインデックスを次に進めるようにします。
以上、解説終了です。
Hello World を実行する
fn main() {
let input = "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-------------.<<+++++++++++++++.>.+++.------.--------.>+..";
let mut machine = Machine::new(input);
machine.run();
println!("",);
}
"Hello World!!" が出力されます。
以上。
