この記事は，HUITアドベントカレンダー2020の20日目の記事です．一昨年はスクリプト言語「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*ckでbrainf*ckインタプリタの実装をする猛者もいるようです．

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

世の中は広いですね．

電気ひつじ牧場

技術メモ

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

brainf*ckとは

ソースコード

おわりに