電気ひつじ牧場

技術メモと日常のあれこれ

Rustでbrainf*ckインタプリタ作ってみた

この記事は,HUITアドベントカレンダー202020日目の記事です.一昨年はスクリプト言語「Sheep」を作ってみた - Qiitaを書きました.去年は卒論で戦死してたのでアドカレがあったのかどうかも知らないです().

brainf*ckとは

ja.wikipedia.org

難読プログラミング言語の1つです.書いていると気が狂ってくるのでこのような名前になっています.可読性は最悪ですがチューリング完全な言語なので,巷にあるプログラミング言語で行える処理はbrainf*ckでも可能になっています.

命令内容はたったの8つです.

トーク 説明
> ポインタをインクリメントする
< ポインタをデクリメントする
+ ポインタの指す値をインクリメントする
- ポインタの指す値をデクリメントする
. ポインタが指す値を出力に書き出す
, 入力から1バイト読んで、ポインタが指す先に代入する
[ ポインタが指す値が0なら、対応する ] の直後にジャンプする
] ポインタが指す値が0でないなら、対応する [ の直後にジャンプする

ソースコード

言語処理系の実装に向いていると言われているRustで実装していきます.単純な言語なので一般的なプログラミング言語のようにイテレータpeek()して分岐したりパースしたりする必要はありません.

use anyhow::Result;
use std::io::{self, prelude::*};
const BUFFER_SIZE: usize = 30000;

fn main() -> Result<()> {
    loop {
        let mut input = String::new();
        io::stdin().read_line(&mut input)?;
        let input_chars: Vec<char> = input.chars().collect();
        exec(&input_chars)?;
        print!("\n");
    }
}

fn exec(input: &[char]) -> Result<()> {
    let mut buffer = [0; BUFFER_SIZE];
    let mut buffer_ptr = 0;
    let mut input_ptr = 0;
    let mut prev_paren = Vec::new();

    while input_ptr < input.len() {
        match input[input_ptr] {
            '>' => {
                buffer_ptr += 1;
            }
            '<' => {
                buffer_ptr -= 1;
            }
            '+' => {
                buffer[buffer_ptr] += 1;
            }
            '-' => {
                buffer[buffer_ptr] -= 1;
            }
            '.' => {
                print!("{}", char::from(buffer[buffer_ptr]));
            }
            ',' => {
                buffer[buffer_ptr] = io::stdin().bytes().next().and_then(|r| r.ok()).unwrap();
            }
            '[' => match buffer[buffer_ptr] {
                0 => {
                    while input_ptr < input.len() && input[input_ptr] == ']' {
                        input_ptr += 1;
                    }
                }
                _ => prev_paren.push(input_ptr),
            },
            ']' => match buffer[buffer_ptr] {
                0 => {
                    prev_paren.pop().ok_or(anyhow::anyhow!("invalid ]"))?;
                }
                _ => {
                    if prev_paren.len() <= 0 {
                        anyhow::bail!("no previous paren")
                    }
                    input_ptr = prev_paren[prev_paren.len() - 1];
                }
            },
            _ => {}
        }
        input_ptr += 1;
    }
    Ok(())
}
$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/brainfuck`
++++++++++[>++++++++++<-]>++.+++++++++..
foo

ぱっと見だと意味が分からないですがascii文字でf,o,oを出力しています.最初に10個バッファに加算しているのはループ用の変数です.1つ右にポインタをずらしてf用の値をループしながらひたすら加算して作成します.

+[>,.<]
hitsuji
hitsuji

これはエコーサーバーです.コンパクトですね.バッファを行ったり来たりしながら文字を出力しています.

おわりに

brainf*ckbrainf*ckインタプリタの実装をする猛者もいるようです.

http://esoteric.sange.fi/brainfuck/bf-source/prog/BFI.BF

世の中は広いですね.