BrainfuckでBrainfuckのインタプリタを作った話。

この記事を読めばBrainfuckのメタサーキュラーインタプリタがかけるというわけではないです。
これは、「Brainfuckはメタサーキュラーインタプリタが書ける」といった以上の内容を保証しません。
メタサーキュラーインタプリタが書きたい方は、以前投稿したBrainfuckに関する幾つかの記事を読み返した上でこのコードを一度完全に理解してください。

コード

bfi.bf

【入力部】
>-
[
    {調整用加算}
    +
    {入力部まで移動}
    >>>>
    {入力}
    ,
    ----------
    {終了命令}
    [<]-[>]<<+[->+<<+>]>
    ---------------------------------
    {加算命令}
    [<]-[>]<<+[->+<<++++>]>
    -
    {入力命令}
    [<]-[>]<<+[->+<<+++++++++>]>
    -
    {減算命令}
    [<]-[>]<<+[->+<<+++++>]>
    -
    {出力命令}
    [<]-[>]<<+[->+<<++++++++>]>
    --------------
    {ポインタ減算命令}
    [<]-[>]<<+[->+<<+++++++>]>
    --
    {ポインタ加算命令}
    [<]-[>]<<+[->+<<++++++>]>
    -----------------------------
    {ループ開始命令}
    [<]-[>]<<+[->+<<+++>]>
    --
    {ループ終了命令}
    [<]-[>]<<+[->+<<++>]>
    {入力文字零化}
    [-]
    {入力命令参照}
    <<
    {命令が不正な場合再入力できる位置へ戻る}
    [<]-[>]<<+[->+<<<]>
    {終了命令でループを抜ける処理}
    -
]
【準備部】
{テープ部の先頭付近へ移動}
>>
{テープ部の始点となる値を入力}
(これは必ずテープが|01|XX|00|となるようにするため、最初が|00|XX|00|だったらダメ)
+
{コード部の末尾に移動}
<<<<
{余分な数字を調整する}
[-<<]
{コード部の先頭に移動}
>>
【実行部】
[
    -
    {ループ終了命令}
    [<]-[>]<<+[
        ->+
        {自分自身の値の復元}
        +>
        {自身が終了カッコなのでカッコに関する条件を1減算}
        -
        [
            {開始カッコでは1加算、終了カッコでは1減算で合計が0になれば終了}
            <<<
            -[<]-[>]<<+[->+>>>-<<<<]>
            -[<]-[>]<<+[->+>>>+<<<<]>
            {値の復元}
            ++
            >>>
            {フラグを追従}
            [+<<->>]<<
        ]
        {終了場所は開始カッコの位置なはずなのでそれに適した形に調整}
        <-<
    ]>
    -
    {ループ終了命令}
    [<]-[>]<<+[
        ->+
        {現在指し示しているポインタへ移動}
        >>[>>]>>[>>]<<
        {計算用スペースを開ける}
        ->
        {ポインタの指し示す値が00なら分岐に入る}
        [<]-[>]<<+
        [
            {もといた場所に戻る}
            [<<]<<[<<]++
            {自身が開始カッコなのでカッコに関する条件を1加算}
            <+
            [
                {開始カッコでは1加算、終了カッコでは1減算で合計が0になれば終了}
                >>>
                -[<]-[>]<<+[->+<<<->>]>
                -[<]-[>]<<+[->+<<<+>>]>
                {値の復元}
                ++
                {フラグを追従}
                <<<[->>+<<]>>
            ]
            {ジャンプが行われたフラグ}
            +>
            {戻ってくるために00に変更}
            ->>
            {ポインタの指し示す位置に戻る}
            [>>]>>[>>]<+<-
        ]
        {計算用スペースのために片付けたフラグを復元する}
        +
        {現在コード中で00となっている位置から実行を再開するのでそこへ移動}
        [<<]<<[<<]<
        {ジャンプしたということは現在終了カッコにいるということなのでそれ用の調整}
        [->-<]
    ]>
    -
    {加算命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]<+<[<<]<<[<<]<]>
    -
    {減算命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]<-<[<<]<<[<<]<]>
    -
    {ポインタ加算命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]+[<<]<<[<<]<]>
    -
    {ポインタ減算命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]<<-<<[<<]<<[<<]<]>
    -
    {出力命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]<.<[<<]<<[<<]<]>
    -
    {入力命令}
    [<]-[>]<<+[->+>>[>>]>>[>>]<,<[<<]<<[<<]<]>
    {減算してた命令の復元}
    ++++++++
    {次の命令へ移動}
    >>
]

このソースコードは、入力部と準備部、実行部に分かれています。

入力部では実行部に渡すために入力を適切な形式に変換し、準備部では細かな準備、実行部では適切な形式に変換されたコードを実行します。

入力部

入力部ではBrainfuckのソースコードの入力を促します。
この入力は改行が入力されるまでソースコードの入力を受け付けます。
また、入力された文字をそのまま保存せず、適当な値に変換します。

入力	数値
]	01
[	02
+	03
-	04
>	05
<	06
.	07
,	08

数値と入力記号との対応が不自然に見えるかもしれませんが、]と[の評価の関係上、この順番になっています。
実行部を見るとその理由がわかるかもしれませんが、]を評価した後に[をさせてます。
そうすることで]と[の評価を同時に行うことができ、評価回数を削減してます。
また、元の文字ではなく、数値に変換するのも評価回数の問題です。
分岐するためにはその値が00となる条件を探す必要があるのですが、普通の文字だとそれが広範囲に散らばってしまいます。
それでは+や-などで数値を調整する回数が増えるのでこのようにしてます。
また、]と[はジャンプに関する命令でもあるため、評価回数が少なくなるように前に持ってきています。

準備部

ここではテープの形式の定義や文字の調整などの細かな動作をしてます。
数値の調整に関しては特にいうことはないが、Brainfuckの配列を司るポインタの準備は地味に重要です。

実行部

実行部ではそれぞれの値から1ずつ減算していき、それぞれが00となったタイミングで命令が実行されます。
つまり、数値の順に評価されるわけです。
ただし、]が行われた場合のみ特殊で]が評価された直後に必ず[が評価されます。
この構造に至ったのは色々な理由がありますが、現在この形なのは「この形が便利だから」です。
2回にわけて評価すると少し複雑になったりもするので、このコードはこれでいいところに落ち着いたって感じです。

さて、入出力と加算減算ポインタ操作は簡単です。
インタプリタのポインタの指し示す位置まで行ってそこで適当な処理を行うだけです。
加算なら+、入力なら,です。
そのため、入出力と加減算はほとんど同じ形をしています。
また、ポインタの操作もポインタに関するフラグを書き換えているだけなのでそこまで難しくはないです。

ループ命令に関しては難しいです。
説明を読むだけなら簡単に見えますが、実際コードを描くとどこを変更するとどこに影響するかを考えないといけません。
気をつけてください。

もしインタプリタをつくるなら

もしインタプリタをつくるなら以下の点に注意してください。

最初は入出力命令のみをサポートする

一気にBrainfuckの全部の機能を入れるとなると現実的ではありません。
そこで最初は比較的簡単でテストも行いやすい入出力のみをサポートさせましょう。
その後は加減算をサポートしましょう。
ここまではおそらく難しくないです。

もし、もう少しいけそうだと感じたらポインタの移動をサポートしてください。
ここまでできれば十分です。
わざわざループのサポートに手を出す必要はないと思います。

それでもBrainfuckの難解な部分を知りたい場合はループをサポートを検討してみてください。
ただし、何度も申し上げる通りこれは難しいので精神的余裕とかとも相談してください。
ループをサポートする場合はとりあえず]からサポートしてみましょう。
これは無限ループしてしまう命令ですが、適切なインタプリタを用いたら動作を確認はできると思います。
その後、[をサポートしてみましょう。

これが全てできればBrainfuckのメタサーキュラーインタプリタは簡単です。

軽微な変更も思わぬ影響を与えうる

軽微な変更でも思わぬバグを引き起こします。
これは昔のゲームやシステムなどである変数バグのようなものです。
これをインタプリタなどは管理してくれません。
あなたが管理する必要があります。
そのためにはソースコードを書く時には必ず、配列の形式に気を使うことです。
配列の形式を保証することで変更をしやすくはなります。
それでもバグるときはバグりますが。。。

補足

インタプリタの限界

Brainfuckのメタサーキュラーインタプリタにも限界はあります。
例えば、配列の長さがメタサーキュラーインタプリタを動かすインタプリタの配列の長さの大体半分です。
また、ループの中に255個(実装によっては65535個)ループを入れ込むと不正な動きをします。
ただ、これらのどちらの限界も普通のインタプリタにもある問題です。
だから、そこまで気にする必要はないでしょう。
255個もループを内側に持つループは使わないでしょう。
使う場合は実装を見直すべきでしょう。

実行後の配列の状態

以下では実行後の配列の状態を示します。

a. ソースコードの先頭
b. ソースコードの末尾
c. 配列の先頭
d. ポインタが現在指し示している値

以下は,>,.<.\nを実行した後の配列です。
この例では配列の先頭とポインタが現在指し示している値が同じ場所です。
これは入力したコードより自明でしょう。

|00|00|00|08|00|05|00|08|00|07|00|06|00|07|00|00|00|01|30|00|31|00|
           ↑a                                  ↑b    ↑cd

以下は+++++[->++++++<]>+++.\nを実行した後の配列です。

|00|00|00|03|00|03|00|03|00|03|00|03|00|02|00|04|00|05|00|03|00|03|00|03|00|03|00|03|00|03|00|06|00|01|00|05|00|03|00|03|00|03|00|07|00|00|00|01|00|01|21|00|
           ↑a                                                                                                                                  ↑b    ↑c    ↑d

配列には00からFFまでの全ての値が入るので場所を示すには「インタプリタのポインタの指し示す値はここより右である」ことを保証するフラグを使ってます。

コメントなし

bfi.bf

>-[+>>>>,----------[<]-[>]<<+[->+<<+>]>---------------------------------[<]-[>]<<+[->+<<++++>]>-[<]-[>]<<+[->+<<+++++++++>]>-[<]-[>]<<+[->+<<+++++>]>-[<]-[>]<<+[->+<<++++++++>]>--------------[<]-[>]<<+[->+<<+++++++>]>--[<]-[>]<<+[->+<<++++++>]>-----------------------------[<]-[>]<<+[->+<<+++>]>--[<]-[>]<<+[->+<<++>]>[-]<<[<]-[>]<<+[->+<<<]>-]>>+<<<<[-<<]>>[-[<]-[>]<<+[->++>-[<<<-[<]-[>]<<+[->+>>>-<<<<]>-[<]-[>]<<+[->+>>>+<<<<]>++>>>[+<<->>]<<]<-<]>-[<]-[>]<<+[->+>>[>>]>>[>>]<<->[<]-[>]<<+[[<<]<<[<<]++<+[>>>-[<]-[>]<<+[->+<<<->>]>-[<]-[>]<<+[->+<<<+>>]>++<<<[->>+<<]>>]+>->>[>>]>>[>>]<+<-]+[<<]<<[<<]<[->-<]]>-[<]-[>]<<+[->+>>[>>]>>[>>]<+<[<<]<<[<<]<]>-[<]-[>]<<+[->+>>[>>]>>[>>]<-<[<<]<<[<<]<]>-[<]-[>]<<+[->+>>[>>]>>[>>]+[<<]<<[<<]<]>-[<]-[>]<<+[->+>>[>>]>>[>>]<<-<<[<<]<<[<<]<]>-[<]-[>]<<+[->+>>[>>]>>[>>]<.<[<<]<<[<<]<]>-[<]-[>]<<+[->+>>[>>]>>[>>]<,<[<<]<<[<<]<]>++++++++>>]

文字の登場回数ランキング

まず初めに、今回のコードの文字数は883文字でした。
以下はその順位です。

順位	文字	回数	割合
1	<	199	0.225
2	>	177	0.200
3	-	167	0.189
4	+	117	0.132
5	[	110	0.124
5	]	110	0.124
7	,	2	0.002
8	.	1	0.001

ただし、割合は小数第4位以降は切り下げ。

7位と8位は明らかに登場頻度が少ないです。
,は最初の入力とインタプリタで,命令が評価された時にしか使われず、.に至ってはインタプリタで.命令が評価された時しか使われません。
そのため、異様に登場頻度は低いです。

5位は[と]ですが、これが常に同じ順位になるのは自明です。
もし同じ順位になってなかったらループが閉じてないのでそのソースコードは誤ってます。

3位と4位ですが-が+を上回っています。
この差は入力部によって生じています。

1位と2位ですが、これは配列ないでの移動が多いことに起因しますが、正直この順位は意外でした。
個人的には加減算の方が多いイメージでした。
さて、なぜ<が>を上回るのかという話ですが、これはメタサーキュラーインタプリタの配列の特性とnot文に起因するでしょう。
not文は[<]-[>]<<+[->+<]>と<の方が多くなっています。
また、配列の特徴として、インタプリタの持つ配列は以下のような構造を持ちます。

...|01|ZZ|00|...
           ^

これは[>>]で動いてたものが止まった時の状態です。
ここから再度[<<]で戻るためには、<<を一度行う必要があります。

...|01|ZZ|00|...
           ^<<

...|01|ZZ|00|...
     ^[<<]

以上がそれぞれの命令の登場頻度でした。