adventar.org4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。/-500/さんによるunidentifiedexe.hatenablog.comです。この記事はadventar.org5日目の記事でもあります。空いていたので埋めました。4日目の記事はnakarioさんによるqiita.com6日目の記事はdnek_さんによるwww.dnek.appでした。Brainf*ck処理系同士の非互換性Brainf*ckの処理系(コンパイラおよびインタプリタ)にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。実行したときにEOFに到達していた場合は0または-1が格納されます。これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1。他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。オーバーフローでランタイムエラーになるといった違いがあります。符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。bionicのデフォルト挙動とか。errorにすることもできる。0初期化とムーブ、コピーここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。符号なしの場合はどの仕様でも(最適化がしょぼくて時間がかかるかもしれませんが)[-]で常に0初期化できます。隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。これに対する対策はいくつかあります。0初期化なら符号に応じて[-]と[+]を使い分ける。ムーブなら[>+<-]と[>-<+]を使い分ける。符号なしの場合は[-]と[>+<-]だけでできるのはこれの特殊な場合。aを引くことで非負の値にすることができ、あとは0初期化なら[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます(最小値の絶対値(あるいはそれ以上の値)を足す)。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。問題はこのどちらの仮定も満たさない場合です。Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。特定の範囲内に値があるかを判定するBrainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。0この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。[->]>>+<<<<<[<]>>>]>>>これを実行すると最終的にポインタは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_n,b_nがあればy-anに対して[-]をすれば0初期化できます。b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3。Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。b_nを指数的に変化させる方が良いでしょう。これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。>>>[<<<+>>>-]<<<]1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。yが0になった瞬間にループを抜けられるような作りになっています。ムーブやコピーもこのテクニックを応用することで可能です。非負整数ペアによる整数表現ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。ここでは非負整数のペア(二つ組)によって整数を扱う方法を紹介します。b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、(オーバーフローがなければ)これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに(たとえ真の値a-bの絶対値が小さくても)オーバーフローが起こる可能性があります。b-a)と"標準化"することで回避できます(そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか)。このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。22日目】この記事はKMCアドベントカレンダー22日目の記事です。「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみたLeapMind株式会社に入社しました月別アーカイブはてなブログをはじめよう!PrimeNumberさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。