IchigoJamでBefungeインタプリタ

# 何をするか

[Befunge](https://ja.wikipedia.org/wiki/Befunge)のインタプリタを作る。
(Brainf*ckのインタプリタを作ろうかと思ったら[既にあった](https://fukuno.jig.jp/1773)ので…)

# Befungeとは

命令を表す文字を2次元平面上に並べるのが特徴のプログラミング言語。

[Befunge - Esolang](https://esolangs.org/wiki/Befunge)

## 仕様

* [Befunge-93.markdown | Cat's Eye Technologies](https://catseye.tc/view/Befunge-93/doc/Befunge-93.markdown)
* [Funge-98/funge98.markdown at master · catseye/Funge-98 · GitHub](https://github.com/catseye/Funge-98/blob/master/doc/funge98.markdown)

## インタプリタ (ブラウザ上で動くもの)

* [The BedroomLAN Befunge Interpreter | BedroomLAN](https://www.bedroomlan.org/tools/befunge-playground/#prog=hello,mode=edit)
* [Befunge-93 Interpreter in JavaScript](https://www.quirkster.com/iano/js/befunge.html)
* [HTML5 Befunge93 Interpreter](http://qiao.github.io/javascript-playground/visual-befunge93-interpreter/) (`p`命令や`g`命令のx座標とy座標が逆になるバグがあるようである)

# 今回の仕様

* Befunge-93の命令に対応する。
* プログラムの最大サイズはIchigoJamの画面に合わせた32×24。(Befunge-93の仕様の80×25より小さい)
* 画面はプログラムの格納に用い、シリアルポートで入出力を行う。
* 整数はIchigoJamで普通に扱える範囲(-32768～32767)に対応する。
* 画面上の文字がナル文字(文字コード0)の場合、命令の取得時には空白(文字コード32)とみなす。
  * `g`命令でのデータの取得時には、この補正は行わない。

# 実装

```
1 'Befunge
2 X=0:Y=0:U=1:V=0:S=0:Q=0:LC0,-1
3 C=SCR(X,Y):C=C+32*!C:GOSUB9:GOTO3
4 GOSUB5:B=A
5 T=S>0:S=S-T:A=[S]*T:RETURN
6 [S]=A:S=S+1
7 X=(X+U+32)%32:Y=(Y+V+24)%24:RETURN
8 A=INKEY():IF!AGOTO8ELSEA=A&255:RETURN
9 IFC=34:Q=!QELSEIFQA=C:GOTO6
10 IFC=43GOSUB4:A=A+B:GOTO6
11 IFC=45GOSUB4:A=A-B:GOTO6
12 IFC=42GOSUB4:A=A*B:GOTO6
13 IFC=47GOSUB4:A=A/B:GOTO6
14 IFC=37GOSUB4:A=A%B:GOTO6
15 IFC=33GOSUB5:A=!A:GOTO6
16 IFC=96GOSUB4:A=A>B:GOTO6
17 IFC=62U=1:V=0
18 IFC=60U=-1:V=0
19 IFC=94U=0:V=-1
20 IFC=118U=0:V=1
21 IFC=63V=RND(4):U=!V-(V=1):V=(V=2)-(V=3)
22 IFC=95GOSUB5:U=2*!A-1:V=0
23 IFC=124GOSUB5:U=0:V=2*!A-1
24 IFC=58GOSUB5:[S]=A:S=S+1:GOTO6
25 IFC=92GOSUB4:[S]=B:S=S+1:GOTO6
26 IFC=36GOSUB5
27 IFC=46GOSUB5:?A;" ";
28 IFC=44GOSUB5:?CHR$(A);
29 IFC=35GOSUB7
30 IFC=103GOSUB4:A=SCR(A,B):GOTO6
31 IFC=112GOSUB5:D=A:GOSUB4:POKE#900+D*32+B,A
32 IFC=126GOSUB8:GOTO6
33 IFC=64END
34 IF47<CANDC<58A=C-48:GOTO6
35 B=0:M=1:IFC-38GOTO7
36 GOSUB8:IFA=45M=-1ELSEIFA<48OR57<AA=B*M:GOTO6ELSEB=B*10+A-48
37 GOTO36
```

# 解説

今回は、以下の変数を用いた。

* `X`：プログラムカウンタのx座標。
* `Y`：プログラムカウンタのy座標。
* `U`：プログラムカウンタのx座標の増分。
* `V`：プログラムカウンタのy座標の増分。
* `S`：スタックに入っている要素数。
* `Q`：文字列モードフラグ。
* `C`：実行中の命令。
* `T`：スタックからポップする際に要素があるかを表すフラグ。
* `A`：スタックからポップした値、読み込んだ文字、1番目のパラメータ。
* `B`：2番目のパラメータ、読み込み中の整数。
* `D`：3番目のパラメータ。
* `M`：読込中の整数の符号。

`GOTO`や`GOSUB`命令で消費する文字数を減らすため、行番号を10ずつではなく1ずつ増やすようにした。

それぞれの行の役割は、以下のようになっている。

* 1行目：タイトル
* 2行目：変数の初期化
* 3行目：プログラムカウンタが指す位置の文字を取得し、命令を実行する
* 4行目：スタックから値を2個popする
  * まず`GOSUB5`で値を1個popし、それを変数`B`に入れた後、5行目に実行が移ってもう1個の値をpopする
* 5行目：スタックから値を1個popする
  * 「スタックが空の状態でpopすると0が返る」という仕様を実装している
* 6行目：変数`A`の値をスタックにpushし、次の命令に移る
  * 「次の命令に移る」は、7行目に実行が移ることで実現する
* 7行目：スタックポインタの値を更新し、次の命令に移る
  * 29行目(`#`命令)では、ここを`GOSUB`で呼び出し、スタックポインタの値を合計2回分進める
* 8行目：シリアルポートから1文字入力されるまで待ち、入力された文字を取得する
* 9行目～35行目：各命令の処理を行う
  * スタックに値をpushする命令では、`GOTO6`を実行する
  * スタックに値をpushしない命令では、文字数を削減するため`GOTO7`を省略した
* 35行目～37行目：シリアルポートから整数を読み込み、スタックにpushする (`&`命令)
  * 符号は簡易対応のため、`+`には対応せず、`1-2-3`のような入力も`-123`として扱う

# 実行例

実行するために画面にBefungeのプログラムを置く際、誤って改行を送信してしまうと、
行頭にある数字を行番号と認識してインタプリタのプログラムが破壊されることがあるので注意する。
行の区切りは、[IchigoJamの特殊キーコード表](https://fukuno.jig.jp/1092)にある「行分割」(0x10)を使うとよい。
IJUtilitiesでは「Hex送信」から送信できる。
以下のRecipeを用いることで、プログラム中の改行を行分割に変換し、さらに16進数に変換できる。

[Find / Replace, To Hex - CyberChef](https://gchq.github.io/CyberChef/#recipe=Find_/_Replace%28%7B%27option%27:%27Regex%27,%27string%27:%27%5C%5Cn%27%7D,%27%5C%5Cx10%27,true,false,true,false%29To_Hex%28%27None%27,0%29)

[Sieve of Eratosthenes](https://esolangs.org/wiki/Befunge#Sieve_of_Eratosthenes) のプログラムを32列に縮め、
さらに最後に改行の出力を追加した以下のプログラムを実行した。

```
2>:3g  " "-!v\  g30            <
 |!`-9*85:+1_:.:03p>03g+:58*9-`|
 >73+,@            ^  p3\" ":  <
2 234567890123456789012345678901
```

以下のようにプログラムを画面に置き、実行した。

![Befungeインタプリタ 実行開始](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1bd4e967-12a2-cfd5-17ca-7446f1f3a05e.png)

IchigoJam BASIC 1.0.0 で実行した結果、約5分で実行が完了した。

![Befungeインタプリタ 実行完了](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/28150688-240f-d925-d190-49e4fa6cbb0a.png)

以下は実行中の動画(ノーカット)である。

<iframe width="560" height="315" src="https://www.youtube.com/embed/u48yNYzvCmo" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

# おわりに

IchigoJamはjig.jpの登録商標です。