この記事はBrainf*ck Advent Calendar 2019 5日目の記事です。
4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか？」の予定です。 6日目の記事はあんでぃ@量産型テ徒???? /-500/さんによる
unidentifiedexe.hatenablog.com
です。
この記事は
5日目の記事でもあります。空いていたので埋めました。 4日目の記事はnakarioさんによる
6日目の記事はdnek_さんによる
でした。
Brainf*ck処理系同士の非互換性
Brainf*ckの処理系（コンパイラおよびインタプリタ）にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。
例えば、EOFの扱いで、多くの処理系では、 . を実行したときにEOFに到達していた場合は0または-1が格納されます。
これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1。
他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。
しかし、最も対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。
値の範囲とオーバーフローの扱いについてざっと上げられるだけでも、
- セルサイズ: 1bit、8bit、16bit、32bit、多倍長など
- 値は符号付きか符号なしか、符号付きの場合の表現方法
- オーバーフロー時にwrap-aroundするか、saturateするか、多倍長整数によりオーバーフローが起こらないか、はたまた実行時エラーになるか
- wrap-around: オーバーフロー時に反対側（最大値に1を足してでオーバーフローしたなら最小値、最小値から1を引いてオーバーフローしたなら最大値になる）
- saturate: オーバーフロー時の結果を表現できる値に切り詰める（最大値に1足しても最大値のまま、最小値から1引いても最小値のまま）
- bignum: 多倍長整数を使って値を格納するので、原理上オーバーフローは起こらず、（メモリの許す限り）任意の大きさの数を格納できる
- runtime error: オーバーフローでランタイムエラーになる
といった違いがあります。 符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。
| 符号 | あり | なし |
|---|---|---|
| wrap-around | 1 | 2 |
| saturate | 3 | 4 |
| bignum | 5 | 6 |
| runtime error | 7 | 8 |
wrap-aroundの場合は符号の有無はあまり関係ない（符号付きで2の補数じゃないBrainf*ck処理系、ある…？）
wrap-aroundが一番多く、例としてはUbuntuのaptで入るbfUbuntu – Details of package bf in bionicのデフォルト挙動とか。
bfはオプションでwrap-aroundではなくruntime errorにすることもできる。
0初期化とムーブ、コピー
ここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。
ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。はたまた コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。
brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。
これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。
また、符号なしの場合はどの仕様でも（最適化がしょぼくて時間がかかるかもしれませんが）[-]で常に0初期化できます。
隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。
問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。
これに対する対策はいくつかあります。まず簡単なものとして2つあり、
- セルに入っている値の符号がわかっている場合: 0初期化なら符号に応じて
[-]と[+]を使い分ける。ムーブなら[>+<-]と[>-<+]を使い分ける。符号なしの場合は[-]と[>+<-]だけでできるのはこれの特殊な場合。 - セルに入っている値の範囲(a<=x<=b)がわかっている場合（runtime error環境の場合は、さらにb-aがオーバーフローしないこと）: aを引くことで非負の値にすることができ、あとは0初期化なら
[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます（最小値の絶対値（あるいはそれ以上の値）を足す）。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。
さて、問題はこのどちらの仮定も満たさない場合です。 Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。一方、bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。
ちなみにruntime error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。
3. 単調減少/増大列と大小比較による方法
特定の範囲内に値があるかを判定する
Brainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。 いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | x(>0) | y | 0 | 0 | 0 |
この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。 上の表のように値がセットされており、いまポインタが0番地にあるとすると、
>>> [ [->]>>+<<<<<[<]>>> ] >>>
これを実行すると最終的にポインタは6番地に移動し、もし0<=y<xであるならば6番地の値が正(x-y)になり、そうでなければ0になります。
本質は[->]で、「ポインタの指す先が0でないなら1を引き、ポインタを1進める」という処理になります。このループの開始直前はポインタは3番地にあり、その値は正(0<x'<=x)です（0になっていれば外側のループを抜けるため）。
そのため、まずx'から1を引き、ポインタは4番地に移動します。4番地の値y'が0ならそこでループが終了し、そうでないなら1を引いて5番地に進みます。
ここで、ループ終了時のアドレスがずれているのがポイントで、その後の+の足す先がずれます。これによりループ中で4番地の値y'が0になったかどうかを検出することが可能になります。
単純なBrainf*ckプログラミングでは、ループ内でポインタが徐々に移動させるとループ終了時にポインタの指す先がずれて、この後のプログラムの実行が大変になるので、そのようなコーディングは避けられがちですが、こういう場面では非常に役に立ちます。
その後、[<]の直前ではポインタは1番地または2番地を指しており、1,2番地が1で0番地が0なので[<]の直後ではポインタはどちらの場合でも0番地になり、分岐していたアドレスが統一されます。
これにより外側のループの中身の終了時に3番地にいることが保証され、0<x'<=xの間ループを回すことが可能になります。
ということで、任意の値yが範囲0<=y<xにあるかどうかを判定することができました。これを任意の範囲a<=y<bにしたいときは、式変形をして0<=(y-a)<(b-a)、つまりyからaをひき、かつx=b-aとすればよいです。
bignum環境における0初期化
もし仮にyがa<=y<bを満たすなら、2番目の方法の通り、y-aは非負なので、[-]によって0初期化できます。しかし、bignum環境では値の範囲がわからないので予めa,bを決めてしまうと、もし範囲内になかったときにどうしようもなくなってしまいます。
そこで、次のように考えます。a,bを決め打つのではなく、a_0<=y<b_0, a_1<=y<b_1, a_2<=y<b_2, ...のような条件式を無限に作り、もしこれを満たすa_n,b_nがあればy-anに対して[-]をすれば0初期化できます。
このようなnが常にするためには、a_0>a_1>a_2>..., b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3。
Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。1回の比較にO(b-a)かかることを考えると、毎回定数倍してa_n, b_nを指数的に変化させる方が良いでしょう。
これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。
>+>+>+[ [>++>++<<-]>>[<<++>>-]<< [ [->]>+<<<<[<]>>>>>[<<[-]<-<->>>>>[-]<-]<< ] >>>[<<<+>>>-]<<< ]
1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。また、yが0になった瞬間にループを抜けられるような作りになっています。
ムーブやコピーもこのテクニックを応用することで可能です。ぜひ考えてみてください。
非負整数ペアによる整数表現
ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。 ここでは非負整数のペア（二つ組）によって整数を扱う方法を紹介します。
具体的には、非負整数のペア(a, b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。
- 足し算: (a, b) + (c, d) = (a+c, b+d)
- 引き算: (a, b) - (c, d) = (a+d, b+c)
- 掛け算: (a, b) * (c, d) = (ac+bd, ad+bc)
- 等号比較: (a, b) = (c, d) ⇔ a+d = b+c
- 大小比較: (a, b) < (c, d) ⇔ a+d < b+c
- 割り算: 上5つの演算を組みあわせることによって実現可能 ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、（オーバーフローがなければ）これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。 非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。
この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。
ただし、足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに（たとえ真の値a-bの絶対値が小さくても）オーバーフローが起こる可能性があります。これは、オーバーフローする前にaとbの大小比較を行い、a>=bなら(a-b, 0)、a<bなら(0, b-a)と"標準化"することで回避できます（そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか）。
このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。
Q: bignum環境って見たことないんだけど
A: 私がさっき作った
まとめ
- Brainf*ckの処理系には非互換性がある
- 特にオーバーフローまわりはいろいろある
- それにより0初期化・ムーブ・コピーといった基本操作に困難が発生する場合がある
- ちょっとしたテクニックで対策は可能
- 整数を直接扱わず、非負整数操作に帰着することも可能
- bignum環境を作ったので遊んでみてね！
