Befunge-98でBrainf*ckインタプリタを実装する

#前置き
Befunge-93が"プログラムコードの長さ制限"という仕様のせいで**チューリング完全ではない**というのは有名な話 [^1] [^2]ですが、その「**後継の後継の後継**」くらいの立ち位置にあるBefunge-98にはその制限が存在せず、加えて色々な機能が追加されています。これはもォ～～～～～チューリング完全じゃない方がおかしいでしょって感じなんですが、時として現実は"おかしい"という表層を打ち破ってきます [^3]……なので念のために、実際にBefunge-98でBrainf*ckインタプリタを作って確かめてみましょう。

#魔法の言葉について
当インタプリタは土曜日の午前、3時間ほどで制作されました。
繰り返します―――**土曜日の午前**、**3時間**です。これを覚えておいてください。
この先、この記事には様々なツッコミどころが到来します……しかしそれを見た時にとりあえず椅子から立ち上がるのではなく、まずこの言葉を思い出してください……復唱しましょう、**土曜日の午前**、**3時間**です。日曜日の午後でも、金曜日の正午でもありません。**土曜日の午前**です。2時間でも、4時間でもありません。**3時間**です。
そのあたり、お願いしますよ。

#今回作る物の詳細仕様

* オーバーフロー・アンダーフローは無し
* Brainf*ckのプログラムはソースコード内の**12行目**に書き込んでおく
* 実行停止が無い（プログラムを端まで読んでも終わらない）
* そのため、プログラムを実行する際はリアルタイムインタプリタで走らせないと死ぬ
* Befunge-98でしか動かない
* **バグは多分ある**

#つくるぞ
##設計する
Befungeのプログラムは事前に緻密な設計を行わなければなりません。そこで僕がMSペイントで描いた設計図がこちらです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/603574/11ec3a45-55bb-3645-9a58-745e042f6175.png)
伝わったでしょうか。ちなみに小さい四角の<font color="red">赤い方</font>はプログラムカウンタで、<font color="blue">青い方</font>はメモリカウンタです。これは別にスタックに保存する変数として取り扱ってもよかったんですが、いちいちアクセスするのがめんどくさいので却下しました。
##とりあえず骨組みを作る
```
>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. メモリカウンタをロード
2. メモリをロード
3. メモリの+1をプッシュ
4. ポップしてメモリをセーブ

といった工程を踏んでいるだけです。

###`-`命令
**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. この際、もし`[`があればカウンタに1を足し、`]`があればカウンタから1を引いている
    
2. カウンタが0（=発見した`[`と`]`が同数）ならば、ループから抜ける
3. プログラムカウンタをベクトルに動かす

と言ったことです。
特筆点としては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](https://github.com/tngreene/BefungeSharp)を使って動かしていきます。
[適当にググったら出てきた記事](http://www.kmonos.net/alang/etc/brainfuck.php)に書いてあったHello,world!プログラムから改行を除去して12行目に書き込み……

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/603574/13067833-e347-1ecb-2f15-4fb78d2a7754.png)

ザ・Befungeって感じの挙動を挟んで……

![オイオイオイ (1).gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/603574/c8f45967-df90-30f6-d6fa-838dcbdf1239.gif)



最終的にこうなりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/603574/b8cd40b6-e8db-29c2-6c66-32d66e968e71.png)
御覧の通り、`O`（アウトプット）欄にちゃんと文字列が出力されています。

#まとめ
Befunge-98はチューリング完全


[^1]: n=3
[^2]: これ前から思ってたですが本当なんですかね？確かにコード長には制限がありますけどFunge文字の仕様を考えれば"データ"自体は無限に収納できるはずだし、自己変更性も無限inputも備えてるんだから一概にそうとも言えない気がする
[^3]: 「『チューリング完全』という概念自体が既に**机上の空論に片足突っ込んでねーか**」というツッコミは、無しでお願いします。
[^4]: n=1