🧠

PythonでBrainfuckインタプリタを作る

2024/09/15に公開

Python

インタプリタ

Brainfuck

tech

ある程度プログラミングに詳しくなってくると、視界が開けて世の中にはいろんなプログラミング言語があることに気づきます。難解プログラミング言語も例外ではありません。その中でも特にBrainfuckについては基本系はもちろん姿や形を変えて、ことあるごとに話題にあがる一種のプログラミングジョークとしての地位を確立しているように見えます。

このところは本業とゲームに忙しく、なかなかこういった面白い技術に触れる時間がなかったのですが、最近某所でBrainfuckの投稿を見かけたことがきっかけで、そういえばBrainfuckのインタプリタを作った記憶がないと気づいたことと、過去に私が技術書展で頒布した同人誌の中でPython VMを使って自作言語を作ったことを思い出し、ふたつを組み合わせてなにか興味深いものが書けないかと思い立ってコネコネし始めて作られたものがこの記事です。

ここでは改めてBrainfuckの仕様を確認し、まずはC言語によるインタプリタの実装、そしてその問題点を説明したのち、AST(抽象構文木)による解消方法を提案し、Pythonでパーサとインタプリタを作成して、インタプリタによるプログラムの実行方法について理解を深めていきます。

言語仕様

言語仕様はWikipediaで確認することができるように、基本的な命令については解釈が一致しているように感じます。提唱したUrban Müller氏が実際に公演で説明している内容(文字起こし)とも一致しています。

ですが、そのほか部分の仕様については実装によって仕様が異なることがあるようです。実際に筆者はメモリアドレスがマイナスになっても正常に動作する処理系を見たことがあります(私の記憶が正しければですが)。

このたび本当の仕様あるいはデファクト実装はどうなっているのか？が気になって調べてみた結果、brainfuck.orgに実装者への書簡という仕様について言及している文書を発見したので、それを引用します。内容は重要なところだけを抜き出して意訳してあります。

Brainfuckはシンプルだが、それゆえに実装者を過信させる。Urban Müllerも言及していない仕様の曖昧さがある。
環境によって改行と認識されるバイト列は異なる。一般的には \n (0x0A), \r (0x0D), \r\n (0x0D, 0x0A) があるが、Brainfuckの処理系は改行文字が入力されたときに、\n だけを受け取るようにして、逆に \n だけを改行として出力するべきである(筆者注: 文脈からしてコンソールの場合を想定している)。
, 命令によってEOF(ファイルの終端)を検知した場合、0 または -1 (あるいはunsigned charにおける255) を受け取るか、あるいは値を変更しないことが考えられる。どれを選ぶかはオプションとして指定できることが望ましい。
伝統的に # (デバッグ出力) と ! (入力バイト列指定用の区切り文字) のふたつの拡張命令が認められている。
メモリの配列要素は少なくとも30,000個あるべきで、プログラムの実行開始時にポインタはその左端を指すべきである。

インタプリタを実装する

今回はまず勘違いしやすいBrainfuckの仕様を整理し、C言語による実装をします。「表題にPythonと書いているじゃないか嘘つきめ」と毒づきたくなるかもしれませんが、長いコードというのは大抵著者は満足する一方で読者はウンザリするので、本質的な部分がわかるように、あえてBrainfuckを少ないコード量で書けるC言語を選んでいます。

C言語による実装

理解のしやすさのために実装者への書簡をある程度無視すると、C言語での実装は以下のようになります。普通であればちゃんと改行するところも行数を稼ぐためにまとめています。普段からこういうコードを書いているわけではありません。

#include <stdio.h>

const char *_bf_loop_seek(const char *ip, int d) {
    for (int lc = 0; *ip; ip += d) {
        if (*ip == '[') lc++;
        else if (*ip == ']') lc--;
        if (!lc) break;
    }
    return ip;
}

void bf_exec(const char *source, FILE *in, FILE *out) {
    unsigned char mem[30000] = {0};
    unsigned char *mp = mem;
    for (const char *ip = source; *ip; ip++) {
        if (*ip == '>') mp++;
        else if (*ip == '<') mp--;
        else if (*ip == '+') (*mp)++;
        else if (*ip == '-') (*mp)--;
        else if (*ip == '.') fputc(*mp, out);
        else if (*ip == ',') *mp = fgetc(in);
        else if (*ip == '[') !*mp && (ip = _bf_loop_seek(ip, 1));
        else if (*ip == ']') ip = _bf_loop_seek(ip, -1) - 1;
    }
}

[ と ] 以外の命令はメモリやポインタの概念を理解していれば実装することは容易いでしょう。ポインタを理解していなくても、ポインタを使うことは必須ではないので、添字による配列アクセスでも実現できます。

注意が必要なのは [ と ] によるループです。これらは入れ子になりえるので、正しく処理されるように工夫が要ります。入れ子になったデータや処理を制御するにはスタックを使うのが定石ですが、もっと簡単な方法としてはカウンタ変数を用意して [ と ] が出現するたびにインクリメントとデクリメントをすると、0になったところで入れ子が解消したと判断できます。

C言語で作ったインタプリタの問題点

このインタプリタは一部の仕様に目を瞑ればちゃんと動作しますし、なによりシンプルでわかりやすいですが、このコードには問題点があります。それは、[ と ] によってループが発生するときに、ループの始まりと終わりを検知するために、その間にあるソースコードを1バイトずつ走査しないといけないことです。

もし [ と ] の間にコードがあればあるほどポインタを動かす時間が長くなり、ループ性能が悪くなることになります。もし走査途中の文字が基本8命令のどれかであればまだ許せますが、コメントであった場合には意味のない文字列をただ読み取っているということが起きてしまいます。

コメントに限った話であればソースコードの実行前にコメントを取り除いた新しいソースコードを生成してそれを実行するようにすればこの問題は解消できます。ですが、意味のある命令しかなかった場合はこの問題にどう対処すればいいでしょうか？

ひとつめは [ が実行されるときにそのポインタの値をスタックに退避しておいて、] の実行時にポインタに復元することです。これでソースコード上でポインタを無駄に動かすことはなくなりましたが、スタックを管理する責任が生まれます。さらにこの方法はループの実行効率は低下しませんが、 [ の中に入らない場合に、対応する ] を探索する仕事はなくならないので片手落ちです。

AST (抽象構文木)を作る

実行効率を高めるためのふたつめの方法は、今回の主題となるAST(抽象構文木)を作る方法です。生成するコストは高いものの、ソースコードから空白文字やコメント、文法上必要なキーワードなど、プログラムを実行するにあたって本質的に必要のない要素を取り除いた再帰的な制御構造を構築するものです。

例えば、++[>++<-]というコードが与えられたら、

[Incr, Incr, Loop([Next, Incr, Incr, Prev, Decr])]

といったASTを生成することを期待しています。

人間が見れば [>++<-] の部分はループ処理が実行されるとわかりますが、コンピュータはそうではありません。C言語版のソースコードを直接実行する形式のインタプリタでは、[ が出たら対応する ]まで走査する必要がありましたが、ASTに変換したあとの形式ではループ内で実行する命令が構造的に表現されているので、処理しやすい形式になっていると言えます。

ASTは言ってしまえば、ソースコードをコンピュータが処理しやすい形式に変換したに過ぎませんが、直接ソースコードを解釈して実行するインタプリタに比べて問題を単純化(≠コード量が削減)できます。また、本質的な部分だけを抽出しているので、最適化もしやすくなります。一度に複雑なことをせずに、段階ごとに分業することで、それぞれの仕事の難易度を下げることができます。

しかしASTを作るコストがかかるじゃないか、と指摘する人もいるとは思います。それは事実正しく、それなりのコストが必要なので、1度しか実行しないプログラムに対しては効果が薄いと言えます。ですがよくよく考えてみると、実際一回しか実行されない書き捨てのプログラムは少なく、どんなプログラムでも複数回実行されることがほとんどなので、ASTを作らないよりも作ったときに得られる恩恵のほうが大きくなると捉えることができます。

Brainfuckはとても単純な言語構造を持っていて、ソースコードレベルのインタプリタを簡単に作ってしまえるので、ASTを作ることにあまり意義を感じないかもしれませんが、これがどういうことかを理解するために、Pythonで簡単なASTを作ってみたいと思います。

各命令に対応するASTを定義する

まずはASTクラスを作ってみます。すべての命令は抽象クラスのAst(これ自体が使われることはありません)から派生していて、各命令を表現しています。[ と ] はあわせてLoopとして表現します。

import abc

class Ast(metaclass=abc.ABCMeta):
    def __repr__(self) -> str:
        # デバッグ用に出力した際に読みやすくする
        return self.__class__.__name__

class Prev(Ast): pass
class Next(Ast): pass
class Incr(Ast): pass
class Decr(Ast): pass
class Input(Ast): pass
class Output(Ast): pass

class Loop(Ast):
    def __init__(self, ops: list[Ast]) -> None:
        # ループはその中身としてAstの配列を持つ
        self.ops = ops

    def __repr__(self) -> str:
        return f'{super().__repr__()}{repr(self.ops)}'

<, >, +, -, ,, . についてはクラスの中に定義する内容はありません。命令がほかの要素に依存しておらず、単体で完結しているからです。

しかし、Loopクラスだけはプロパティとしてその中に含まれる命令を持ちます。ここではAstの配列を持つように定義していますが、Astは抽象クラスなので実体はPrev, Next, Incr, Decr, Input, OutputそしてLoopのどれかになります。Loopの中にLoopを含めることもできるので、入れ子になったループも表現できます。

ASTクラスの定義がこれだけのことにびっくりするかもしれませんが、AST自体は命令を表現するデータ構造なので、メモリの位置をずらしたり、メモリの値を足し引きしたりといった振る舞いを持ちません。実際にASTを解釈して実行するのはインタプリタの仕事になります。

ASTに変換するためのパーサを作る

次にソースコードからASTを生成するパーサを作ります。少し長めのコードにはなっていますが、やっていることは与えられたソースコードを1文字ずつ読み取って対応するASTに変換しているだけです。ただ [ が出現したときだけは、Loopの中で実行する内容を決定するために再帰的な処理が必要です。

class ParserStream:
    def __init__(self, code: str, index: int = 0) -> None:
        self.code = code
        self.index = index

    def eof(self) -> bool:
        return self.index >= len(self.code)

    def next(self) -> str:
        c = self.code[self.index]
        self.index += 1
        return c

class AstParser:
    def parse(self, s: str) -> list[Ast]:
        stream = ParserStream(s)
        return self._parse(stream)

    def _parse(self, stream: ParserStream) -> list[Ast]:
        # このメソッドは再帰的に実行される
        ops = []
        while not stream.eof():
            match stream.next():
                case '<': ops.append(Prev())
                case '>': ops.append(Next())
                case '+': ops.append(Incr())
                case '-': ops.append(Decr())
                case ',': ops.append(Input())
                case '.': ops.append(Output())
                case '[':
                    ops.append(Loop(self._parse(stream)))
                case ']': break
        return ops

ASTのインタプリタを作る

さて、ASTが作れたのでこれを解釈して実行するインタプリタを作ってみましょう。おそらくここでの仕事はソースコードをそのまま解読しながら処理をするよりも格段に簡単になっているはずです。

やることはふたつです。Brainfuckの動作に必要なデータを用意することと、ASTをひとつずつ読み取って命令を実行することです。

import sys
from typing import BinaryIO

class AstInterpreter:
    def __init__(self,
        mem: int = 30000,
        input: BinaryIO | None = None,
        output: BinaryIO | None = None
    ) -> None:
        # Brainfuckは最低でもメモリとして30000セルの領域を持ち、
        # 最初はその先頭を指している
        self.mem = bytearray([0 for _ in range(mem)])
        self.pos = 0
        # 入力ストリームと出力ストリーム。指定しないと標準入力と標準出力を使う
        self.input = input or sys.stdin.buffer
        self.output = output or sys.stdout.buffer

    def execute(self, ops: list[Ast]) -> None:
        while ops:
            match ops[0]:
                case Prev(): self.pos -= 1
                case Next(): self.pos += 1
                case Incr(): self.mem[self.pos] = (self.mem[self.pos] + 1) & 0xff
                case Decr(): self.mem[self.pos] = (self.mem[self.pos] - 1) & 0xff
                case Input(): self.mem[self.pos] = self.input.read(1)
                case Output(): self.output.write(self.mem[self.pos].to_bytes())
                case Loop():
                    while self.mem[self.pos]:
                        self.execute(ops[0].ops)
                case _: raise Exception(ops)
            ops = ops[1:]

BrainfuckのASTを構築することにあまり意義を感じないと述べたように、Loop()以外の部分では、C言語版のインタプリタと変わり映えがしません。しかしLoop()はアドレスをなにやら怪しい条件でインクリメントやデクリメントするといった処理がなくなっていて、単純なwhileループとメソッドの再起呼び出しに置き換わっていて見通しが良くなっています。

さて、ここまでに作ったパーサとインタプリタを組み合わせてBrainfuckのコードを実行してみましょう。こんな感じで簡単に動かせるはずです…

# https://en.wikipedia.org/wiki/Brainfuck のコードを利用
a = AstParser().parse('''
    ++++++++[>++++[>++>+++>+++>+<<<<-]>+
    >+>->>+[<]<-]>>.>---.+++++++..+++.>>
    .<-.<.+++.------.--------.>>+.>++.
''')
AstInterpreter().execute(a)  # Hello World!

ASTを実行する形式ではコメントを完全に無視することができるようになり、ループの処理効率も改善しました。本来処理したい部分だけに着目できるようになるのがASTの強みであることを理解できたと思います。

またここでは触れませんが、さらなる最適化も考えられます。例えば[Incr, Incr, Incr, Incr]といったまとまりがあれば [Add(4)] に変換するなど、生成されたASTを解析して命令を入れ替えることで実行効率を高めることができます。興味があれば取り組んでみてください。

PythonのASTにトランスパイルする

ここまででC言語でソースコードを直接実行するインタプリタとASTに変換して実行するインタプリタを作ってきましたが、せっかくPythonで実装しているので、最後におまけでPythonのASTに変換するトランスパイラも作ってみましょう。

Pythonの標準モジュールの中にはastがあり、Python自体のASTを作成してコードオブジェクトに変換し、実行することができます。なので、BrainfuckのASTをPythonのASTに変換することができれば、Brainfuckのソースコードで表現していることをそのままPython上で動作させることができるようになります。つまり、BrainfuckがPythonの速さで動作するということです。

PythonのASTを作るにはソースコードから変換するか、リファレンスに沿って直接構築する方法がありますが、astモジュールの最初の方で「抽象文法は、現在次のように定義されています」と将来変更されうることが示唆されているので、ここではソースコードから変換する方法を執ります。

ASTからPythonのソースコードを生成することは簡単なので、ASTインタプリタを参考にして次のように書けます。

import ast
import io

class PyAstTranspiler:
    def __init__(self) -> None:
        self.sio = io.StringIO()
        self.indent = 0

    def _block(self, f: callable) -> None:
        self.indent += 1
        f()
        self.indent -= 1

    def _write(self, s: str) -> None:
        print(f'{'    ' * self.indent}{s}', file=self.sio)

    def transpile(self, ops: list[Ast]) -> ast.AST:
        self._write('import sys')
        self._write('mem = bytearray([0 for _ in range(30000)])')
        self._write('pos = 0')
        self._transpile(ops)
        return compile(self.sio.getvalue(), '<string>', 'exec', ast.PyCF_ONLY_AST)

    def _transpile(self, ops: list[Ast]) -> ast.AST:
        while ops:
            match ops[0]:
                case Prev(): self._write('pos -= 1')
                case Next(): self._write('pos += 1')
                case Incr(): self._write('mem[pos] = (mem[pos] + 1) & 0xff')
                case Decr(): self._write('mem[pos] = (mem[pos] - 1) & 0xff')
                case Input(): self._write('mem[pos] = sys.stdin.buffer.read(1)')
                case Output(): self._write('sys.stdout.buffer.write(mem[pos].to_bytes())')
                case Loop():
                    self._write('while mem[pos]:')
                    self._block(lambda: self._transpile(ops[0].ops))
                case _: raise Exception(ops)
            ops = ops[1:]

このトランスパイラはBrainfuckのASTをPythonのソースコードに変換し、その結果を組み込み関数のcompile()に与えることでPythonのASTを生成しています。少々強引な方法ではありますが、BrainfuckをPythonに変換することに成功しました。あとはASTをコードオブジェクトに変換して実行するだけです。

ASTを実行するには組み込み関数compile()とexec()を使います。

# BrainfuckのソースコードをBrainfuck ASTに変換
a = AstParser().parse('''
    ++++++++[>++++[>++>+++>+++>+<<<<-]>+
    >+>->>+[<]<-]>>.>---.+++++++..+++.>>
    .<-.<.+++.------.--------.>>+.>++.
''')

# Brainfuck ASTをPython ASTに変換
b = PyAstTranspiler().transpile(a)

# PythonのASTを出力する。とにかく長い
print(ast.dump(b))

# PythonのASTをコードオブジェクトにコンパイルする
# <code object <module> at 0x13387be00, file "<string>", line 1>
# のようにオブジェクトのアドレスだけ表示される
print(compile(b, '<string>', 'exec'))

# PythonのASTをコードオブジェクトにコンパイルして実行する
exec(compile(b, '<string>', 'exec')) # Hello World!

おわりに

今回は言わずと知れたBrainfuckのインタプリタの実装を説明してきました。言語としては単純な仕組みでありながら、いざ実装してみるとなると意外と考えることがあり、複雑に感じるのではないでしょうか。

Brainfuckに限らず、簡単な言語を定義して実装してみるとプログラミング言語の動作に詳しくなれるので、ぜひ一度は試してみてください。もし単純なトークンの域を越えてそこそこ複雑な文法が必要になるようであれば、PLYのような字句解析器や構文解析器の力を借りることで、汎用プログラミング相当の表現力を得ることもできます。

おわり🌱