前置き
Befunge-93が"プログラムコードの長さ制限"という仕様のせいでチューリング完全ではないというのは有名な話 1 2ですが、その「後継の後継の後継」くらいの立ち位置にあるBefunge-98にはその制限が存在せず、加えて色々な機能が追加されています。これはもォ～～～～～チューリング完全じゃない方がおかしいでしょって感じなんですが、時として現実は"おかしい"という表層を打ち破ってきます 3……なので念のために、実際にBefunge-98でBrainf*ckインタプリタを作って確かめてみましょう。
魔法の言葉について
当インタプリタは土曜日の午前、3時間ほどで制作されました。
繰り返します―――土曜日の午前、3時間です。これを覚えておいてください。
この先、この記事には様々なツッコミどころが到来します……しかしそれを見た時にとりあえず椅子から立ち上がるのではなく、まずこの言葉を思い出してください……復唱しましょう、土曜日の午前、3時間です。日曜日の午後でも、金曜日の正午でもありません。土曜日の午前です。2時間でも、4時間でもありません。3時間です。
そのあたり、お願いしますよ。
今回作る物の詳細仕様
- オーバーフロー・アンダーフローは無し
- Brainf*ckのプログラムはソースコード内の12行目に書き込んでおく
- 実行停止が無い（プログラムを端まで読んでも終わらない）
- そのため、プログラムを実行する際はリアルタイムインタプリタで走らせないと死ぬ
- Befunge-98でしか動かない
- バグは多分ある
つくるぞ
設計する
Befungeのプログラムは事前に緻密な設計を行わなければなりません。そこで僕がMSペイントで描いた設計図がこちらです。
伝わったでしょうか。ちなみに小さい四角の赤い方はプログラムカウンタで、青い方はメモリカウンタです。これは別にスタックに保存する変数として取り扱ってもよかったんですが、いちいちアクセスするのがめんどくさいので却下しました。
とりあえず骨組みを作る
>09g'0-bgv
_v#!-+': <
>:'-- #v_
_v#!-[':<
>:'>- #v_
_v#!-]':<
>:'<- #v_
_v#!-.':<
>:',- #v_
00 v
##########################################
##########################################
v > >09g1+09p$
単純な階段状のSwitch文のようなものです。最初にプログラムカウンタをロードしてそのプログラムカウンタでプログラムをロードした後、それぞれの命令文字列と引き算して「0だったら横に行く、そうでなければ続ける」という分岐を繰り返しています。
特筆すべき点があるとすれば向きですね。命令によって「横」が左だったり右だったりするため、適宜命令を反転させて書く必要があります。Switchの順番が若干特殊なのもその関係です。
各種命令の実装
+命令
2行目を次のように書き換えて実装しました。
_v#!-+': <vpd\+1gd:-0'g91
特に特殊なところはありません。要するに
- メモリカウンタをロード
- メモリをロード
- メモリの+1をプッシュ
- ポップしてメモリをセーブ
といった工程を踏んでいるだけです。
-命令
3行目を次のように書き換えて実装しました。
>:'-- #v_ 19g'0-:dg1-\dp v
+命令を適当に書き換えて反転させただけですね。この辺の実装はとても楽でした。下向き矢印が若干ズレているのは後で回収します。
>命令
[]の説明は面倒なので飛ばして、先に><について解説します。
5行目を次のように書き換えて実装しました。
>:'>- #v_ 19g2+ >1-19pv
メモリカウンタに直接+1しています。なぜ2を足してから1を引くなんて面倒な手法を取っているかと言うと、<で呼び出して使うからです。
<命令
7行目を次のように書き換えて実装しました。
>:'<- #v_ 19g:'0->#^_ v <
5行目と並べてみるとこうなります。
>:'>- #v_ 19g2+ >1-19pv
～[の処理～
>:'<- #v_ 19g:'0->#^_ v <
プログラムカウンタが左端にあった場合、それ以上右に行かれると困るので「プログラムカウンタが0ならば何もしない、そうでなければ-1してプッシュ」という風に組みました。それに当たって>のスペースが空いていたのでちょっと借りた、という形になります。「2を足してから1を引く」の「1を引く」部分を再利用しているわけですね。
.命令
8行目を次のように書き換えて実装しました。
_v#!-.':< v,- 'gd-0'g91
ロードしたメモリをそのまま出力してるだけです。
敢えて言うなら （スペース）をメモリ値から引いたうえで出力している点でしょうか。このプログラムではメモリにおける「0」をスペースと定義しているため、引いておく必要性がある訳です。
,命令
9行目を次のように書き換えて実装しました。
>:',- #v_ ~19g'0-dp v
Befungeの入力には二種類（&と~）あるんですが、今回は後者を使用しています……Brainf*ckの仕様がちょうどそんな感じなので。
[]命令
"来"てしまいましたよ、コイツを説明するトキがァ……ッ！！！結構大規模に書いたので、ここまで書いたプログラムの後ろに[]関係の処理が書かれる、みたいなこともザラです。
4～10行目を次のように書き換えて実装しました。
_v#!-[':< v _ v#- 'gd-0'g91
>:'>- #v_ 19g2+ >1-19pv>10 v
_v#!-]':< v _ v#!- 'gd-0'g91
>:'<- #v_ 19g:'0->#^_ v <>01-0> v
_v#!-.':< v,- 'gd-0'g91 $k9"^p90+g90<0"
>:',- #v_ ~19g'0-dp v>'0-bg-!-:!#v_\:^9
00 v <^g90]'+!-['gb-0'g<
解説すると、まず[ ]それぞれの命令を受け取った後にベクトルとカウンタをスタックにプッシュしています。これはBefunge側のdelta値やメモリカウンタとはまた別で、[ ]を探すにあたってのベクトルと、出現回数を数えるためのカウンタです。それらをプッシュしたら個別的なループに入ります。ループ内でやっていることは、
-
メモリカウンタに
[]が無いか調べる- この際、もし
[があればカウンタに1を足し、]があればカウンタから1を引いている
- この際、もし
-
カウンタが0（=発見した
[と]が同数）ならば、ループから抜ける -
プログラムカウンタをベクトルに動かす
と言ったことです。
特筆点としては8行目ですね。.の処理とループが重なってめんどくさかったので、.側でループを文字列としてプッシュしたうえで$k9で全部捨てるというアグレッシブな方法で回避しました。
あとついでに16行目にカウンタをキャッチする用の行を追加しました。
^ <
全体像
こうなりました。
>09g'0-bgv
_v#!-+': <vpd\+1gd:-0'g91
>:'-- #v_ 19g'0-:dg1-\dp v
_v#!-[':< v _ v#- 'gd-0'g91
>:'>- #v_ 19g2+ >1-19pv>10 v
_v#!-]':< v _ v#!- 'gd-0'g91
>:'<- #v_ 19g:'0->#^_ v <>01-0> v
_v#!-.':< v,- 'gd-0'g91 $k9"^p90+g90<0"
>:',- #v_ ~19g'0-dp v>'0-bg-!-:!#v_\:^9
00 v <^g90]'+!-['gb-0'g<
##########################################
##########################################
v > >09g1+09p$
^ <
何せ土曜日の午前に作られたものですから、かなり改善の余地がありますが……とりあえずは、これでいいでしょう。
動かしてみる
早速Brainf*ckのプログラムを12行目に書き込んで、インタプリタで動かしてみましょう。
今回は、「Befunge-98開発ツールで一番敷居が低い」と評判 4のBefungeSharpを使って動かしていきます。
適当にググったら出てきた記事に書いてあったHello,world!プログラムから改行を除去して12行目に書き込み……
ザ・Befungeって感じの挙動を挟んで……
最終的にこうなりました。
御覧の通り、O（アウトプット）欄にちゃんと文字列が出力されています。
まとめ
Befunge-98はチューリング完全