Brainf**kセルフインタプリタ作ってみた

はじめに

Brainf**kでセルフインタプリタ書いてみました。折角なので ( というか放っておくと何やったか分からなくなるので )、一応記事にしてみます。

セルフインタプリタとは

セルフインタプリタというのは、あるプログラム言語の処理系を、その言語自身で書いたものです。Lispなんかが良くネタにされる印象がありますが…。まあ今回は、Brainf**kプログラムを解釈して実行する処理系をBrainf**kで書いた、ということになります。

なんでわざわざ??

発端は次のtweetを見たからです。

Brainfuckって[]の最大ネスト数を有限にしたらチューリング完全じゃなくなるのかな？チューリング完全と不完全の境界は何重なんだろう？

— TokusiN (@toku51n) 2016年1月25日

Brainf**kはコンパクトでありながら、( メモリ量の制限がなければ ) チューリング完全であることが知られています。しかしそこに、条件分岐 [ ] のネスト段数の条件は出てきません。果たしてネスト段数を有限にすると、チューリング完全でなくなるのでしょうか。

しかし、そこで考えました。任意のBrainf**kプログラムを処理できる実行エンジンをBrainf**kで書いてしまえば。プログラムデータをメモリに配置した上でエンジンを実行するようなBrainf**kプログラムで同等の処理ができるわけですから、エンジン部分の実装に必要な「有限」のネスト段数で済むはずではないかと。

…まあいつかは書こうと思ってもいましたから、丁度ネタとしてもいいなということで。

実装

仕様

いつも使っているのがideoneのbffなので、それに準拠したものにしました。

• bffと同じところ
  • セルサイズ：4byte
  • wrapping ( 0からのマイナス、あるいはセル最大値からのプラス ): 可
  • 負のアドレスへの移動: 可
  • EOFの値: -1
• 違うかもしれないところ
  • セル数: 無限 ( メモリの許す限り…のはずですが、bff自身に上限がある気がします )
  • カッコのネスト段数: 無限 ( セル数の許す限り )
• その他
  • 入力データのうち、パイプ記号 ( | ) までをソース、それ以降をプログラム用のデータとして扱う。
    ※Brainf**kは入力が1チャンネルしかないので、こういう風に分けざるを得ないという…。
    ※なお、パイプ記号がない場合は全てソース ( データなし ) とします。
  • 文法チェック ( [ ] の対応の妥当性チェック ) を行わない。
  • ソース部分で、8種類の文字以外はコメントとして扱う。ただし、ASCIIコード ( 文字コード127以下 ) に限る。
    ※別に128以上も対処はできるのですが、面倒だったので。無理に入れると多分暴走します。

メモリレイアウト

さて。まずはメモリレイアウトです。下の図は,+[-<,+]>[.>]|abcdという入力 ( コードとしては入力を逆順にして出力するもの ) を食わせ、2番目の [ まで制御を進めたところです。

コードはロードが終わった後それ以上増えることはありませんが、セル数を無限としている以上、またネスト段数の上限は事前に予測できないことから、コードの左右にネストカウンタ・データ領域を配置し、無限に延ばせるようにしています。

ネストカウンターをわざわざ可変長にしなくとも、4byteセルのbffであれば十分なネスト段数は実現できるのですが…。一応ほらその、無限段数を強調するために、可変長2進数にしています。( 2進数なのは操作が簡単だからですね )

コード部分は、8種の命令を数値 0～7 として ( 1セル置きに ) メモリに配置します。
データの実行エンジン部分としては、順番にこのコードを辿り、命令内容に応じてデータ部分へ飛んで操作を行い次のコードに戻る、というのが基本です。コードとデータの区切り ( -1のセル ) に達すれば実行終了です。

データ部分

続いてデータ部分です。先ほどのメモリレイアウトからデータ部分を抜粋したのが次の図です。

マイナスのアドレスにも対応できるよう、非負・負のセルを合わせて1組のデータセルとし、それを繋げていきます。現在操作中のセルが分かるように、データセルの先頭にデータポインタ ( マーカーという方が適切?? ) を設定します。

非負・負どちらのアドレスかは、「裏面フラグ」によって制御します。同じデータセルにデータポインタがセットされているとしても、裏面フラグが立っていれば負のアドレス ( オレンジのセル )、立っていなければ非負のアドレス ( 緑のセル ) のデータを扱うということになります。

セルの操作

実際にどのように目的のデータにアクセスするかを次の図に示します。

if-else の制御の要領で脱出場所を調整します。これにより、目的のセルに到達できますから、+-,.はそこで該当する操作を行うだけで済みます。

セルの移動

続いては、<>によるセルの移動の実現についてです。

次の図は>で正の方向へ移動する際の制御を表すものです。

裏面フラグが立っているかどうか、端 ( アドレス -1 ) のセルかどうか、計3通りの場合分けになりますが、基本的にはデータポインタの移動で済みます。

なお、<は移動方向等が逆になるだけで、やることは同じです。

対応するカッコへのスキップ

実行制御として一番複雑なのが、対応するカッコへのスキップです。以下では例として、閉じカッコ ] での制御を説明していきます。

まずは、カレントセルが 0 かどうかの判断が入ります。閉じカッコ ] の場合、カレントセルのデータが 0 であれば何も行いませんから、単純な if 文の制御になります。そこで、スキップを行うべきかどうか、フラグを f に立てておきます。

なお、カッコ に限らず、データ操作後に戻ってこれるよう、IP ( インストラクションポインタ ) をセットしてますので、フラグ f が立っていればまずこのIPを辿り、そこからコード領域を逆方向に対応する開きカッコ [ を探します。

探索中、各コードを見て制御するのですが、大きく4通りに分かれます。

• カッコ に無関係なコード
• 閉じカッコ ] ( ネストカウンターをインクリメント )
• 開きカッコ [ だが対応するカッコではない ( ネストカウンターをデクリメント )
• 対応する開きカッコ [

まずは一番単純な、無関係なコードのパターンです。図中 X が判定対象のコードを表します。

操作する場所が足りませんので、隣のコード Y を一旦移動させています。で、全ての判定が終わった後、Y を元に戻し、IPの場所へ移ります。IPが探索継続フラグを兼ねていますので、そのまま次に移れるようになっています。

続いては閉じカッコ ] のパターンです。先ほどの処理と似ていますが、1点違うのは、ネストカウンタの場所まで行ってインクリメントしてから戻ってくる点です。

最後が開きカッコ [ のパターンです。このパターンでは、ネストカウンタが 0 でない場合のみ、X の脇にフラグ f をセットした上でデクリメントを行います。コードまで戻った後、フラグ f が立っていれば IP を再セットしますが、立ってなければ IP をクリアしたままですので、探索が終了することになります。
※なお、開きカッコ [ 処理時の閉じカッコ ] 探索も、IPの位置が逆になる等の違いはありますが、似たような処理になります。

コード

以下が、ideone の bff 1.0.5 での実装です。こちらは "a childish number translator"(適当) のコードを食わせた例です。

終わりに

ということで、半ば備忘録も兼ねて解説を書いてみました。

一応、自分自身を食わせてダブルインタプリタとして動かすこともできると思いますが、劇的に遅くなるのでまあ…。コード領域とデータ領域を毎回行ったり来たりする関係上、このインタプリタ、どうしても速くはならないのですね。恐らく実行時間がネイティブ実行に比べて3桁位変わるんじゃないでしょうか。なので、実用的とは言えません。

…ん?? 誰ですか、Brainf**kがそもそも実用じゃねえだろとか言う人は。

まあ、予想以上にバグなく組めたので結構満足しています。