Brainfuckでレイトレーサーを書いた

C++のシステムプログラミングコンペティションの準備をしていたとき、CMakeのチュートリアルで興味深い主張を目にしました。多くの場合、問題解決のためのツールを汎用プログラミング言語で書き、ビルドプロセスの一部としてそのツールを呼び出すようにCMakeに教えるのが正しいアプローチです。CMake言語でコード生成、暗号署名ユーティリティ、さらにはレイトレーサーさえも書かれていますが、これは推奨される方法ではありません。 以前にレイトレーサーを書き、それをGPU向けに書き直した経験から、この記述は私の目を引き、さらに優れたレイトレーサーを書くための言語は何だろうかと考えさせられました。前回の書き直しでは、第一原理に基づいたアプローチがほとんどなく、比較的高度なAPIセットに大きく依存するコードを書きました。そのため、私が知っている最もシンプルな言語であるBFを選びました。なぜなら、シンプルな言語は明らかに非常にシンプルなコードベースにつながるからです。実際、BFのコードベースは通常、数行程度にしかなりません。さらに、Muller氏のREADMEでのコメント[1]は、私がカウンター例を示したいという気持ちにさせました。 コードはmTvare6/rayfuck[2]で入手可能です。 PrimerBFは、わずか8つの操作と1つの「データ構造」（各セルがu8を格納できる片側無限のテープ）からなる、明らかにシンプルな言語です。 文字>を見ると、テープ上のセルを指すデータポインタが右に移動し、<では逆に左に移動します。 I/Oは、および.で管理されます。最初の,はデータポインタが指すセルに入力バイトを格納し、後者の.はそれを表示します。 I/O以外の値を変更できる唯一のプリミティブは、データポインタでのインクリメントとデクリメントで、それぞれ+と-で行われます。 その制限は明白でしょう。他のマシンが持つようなn > 1レジスタはなく、複数のセルを操作する命令もなく、加算や乗算のための命令もありません。 BFをチューリング完全にするために必要な最後の要素は、[と]で書かれるループです。トークン[に遭遇すると、ランタイムはデータポインタのセルをチェックします。ゼロであれば、対応する]の後にジャンプし、そうでなければループに入ります。]では、セルがゼロでない場合は対応する[に戻り、そうでなければループを終了します。 直感を得るために、5文字だけでcatプログラムを書く簡単な演習を試してみてください。 事前検討 始める前にそれについて読んでいたので、結果や実装の詳細を調べるのを避け、第一原理からできるだけ多くを書き留めることにしました。スコープを最小限に抑え、プログラムを明らかにレイトレーサーにするために、RIW[3]のMetalセクションでレンダリングされたものと全く同じ画像をレンダリングすることにしました。 Cコードはそれでも少し複雑すぎたため、Cパーサーを書くことは明らかにスコープ外でした。メンテナンスされていないCパーサーを書くことは、AnthropicのCコンパイラ[4]でより良く処理されることです。 すべてのdouble型はセルを組み合わせて表現することにしました。半分のビットを小数部、もう半分のビットを整数部として使用し、実質的にそれらの間に固定小数点（バイナリポイント）を配置します。 [1][1] この同じアプローチは、double型だけでなく、私が必要とする他のデータ型（ブール型など）もカバーします。後にこれはQフォーマットと呼ばれることを知りました。より安価な符号付きQ8.8を使用すると、解像度は1/256、範囲は約[-128, 128)になります。しかし、明らかにそれは十分ではありません。シーンの地面に使用された球体が平らに見えるためには半径r=1000が必要だったため、より高価な符号付きQ16.16フォーマットを選択しました。これは、解像度が1/2^16、範囲が[-2^15, 2^15)で、十分です。 すべてのdouble型はセルを組み合わせて表現することにしました。半分のビットを小数部、もう半分のビットを整数部として使用し、実質的にそれらの間に固定小数点（バイナリポイント）を配置します。 [1][1] この同じアプローチは、double型だけでなく、私が必要とする他のデータ型（ブール型など）もカバーします。後にこれはQフォーマットと呼ばれることを知りました。より安価な符号付きQ8.8を使用すると、解像度は1/256、範囲は約[-128, 128)になります。しかし、明らかにそれは十分ではありません。シーンの地面に使用された球体が平らに見えるためには半径r=1000が必要だったため、より高価な符号付きQ16.16フォーマットを選択しました。これは、解像度が1/2^16、範囲が[-2^15, 2^15)で、十分です。 再帰的なコードを反復処理にし、関数で定義された変数をハンガリアン記法のようにプレフィックスを付けて、名前ルックアップ時の名前の衝突を避けるように、コードをSSAライクな形式に変換することにしました。 [2][2] この変換はLLMの唯一の仕事とし、残りはプロジェクトに設定した第一原理の制約に従うことにしました。 同様に、解析とコード生成を分離することが必要だと判断し、複雑さを2つのコード領域に分割し、中間的な「DSL」をIRとして使用しました。DSLには、abs、add、and、call、copy、div、else、end、eq、func、ge、gt、if、int、le、lt、mul、neg、not、or、print2、print3、set、sqrt、sub、text、var、whileといったシンプルな操作が含まれていました。 次の難しい部分は、いくつかのライブラリ呼び出しでした。使用されたのはsqrt、rand、absです。当初は次のような2状態ソリューションを使用する予定でした。 A = (A-B) % 256 B = (B+1) % 256 または B = (B+A+p) % 256 # ある素数pに対して しかし、これらのバリアントのほとんどは周期が短いです。よりシンプルな A = (5*A + 1) % 256 を選択しました。これは256個の値の完全なシーケンスの後でのみ繰り返すことが保証されており、このユースケースではそれほど悪くありません。 [5][5] ここでのユースケースはスーパーサンプリングアンチエイリアシングであり、暗号学的に強力なランダム性よりも、わずかに異なるサンプル位置のストリームを必要とします。 sqrtには、ヘロンの公式という明白な候補があります。 [3][3] 前述のCMakeチュートリアルでヘロンの公式を思い出しました。しかし、除算を含むことを考えると、それが悪い結果になることは明らかでした。繰り返し減算は、生成されるコードは小さくなりますが、それでも実行するには比較的コストがかかりました。 [4][4] 生成されるコードが小さい方が望ましいです。なぜなら、インタープリタが移動するコードが少なくなるからです。他の候補としては、テイラー級数と「学校方式」（筆算を伴う）がありました。 sqrt(1 + x) = 1 + x/2 - x^2/8 y = 2^16*x sqrt(2^16 + y) / 2^8 = (1 + y/2^17 - y^2/2^35 ) sqrt(y) / 2^8 = (1 + (y - 2^16)/2^17 - (y - 2^16)^2/2^35 ) Desmosでこれをプロットすると、エンコードされた値が20k未満、つまり約0.305未満ではフィットが悪く、これは非常に重要な領域でした。そのため、筆算による方法が残りました。これはかなりシンプルでした。実数値がxの場合、表現される値は次のようになります。 N = x * 2^16 sqrt(x)を表現するには、次のものが必要です。 N_0 = sqrt(x) * 2^16 isqrt(N) = sqrt(x) * 2^8 isqrt(2^16 * N) = sqrt(x) * 2^16 = N_0 isqrtはここで正当化されます。エンコードされた結果の1の違いは、デコードされた平方根を1/2^16未満、つまり約0.00001526だけ変化させるからです。 そして最後に、変数マップと対応するBFアドレス全体は、辞書で維持されます。 実装 理論的なビットが設定されたので、明らかにシンプルな実装の詳細だけが残りました。2つの重要なプリミティブは移動とコピーでした。 [a, 0] 移動は、初期データポインタのセルがゼロになるまで値を継続的に減らし、毎回等しく別のセルをインクリメントすることで機能します。 [ # ループ開始 - # デクリメント >+ # 右に移動してインクリメント < # 戻る、このセルはループ制御に使用 ] ワンライナーとして [->+<] そしてコピーは以下のように機能します。この配列から開始します。 [a, 0, 0] コードを使用して。 [->+>+<<] これを次のように変換します。 [0, a, a] そして今、必要であれば、末尾のaを内側に移動できます。 加算、そして後には除算が一時値の繰り返し使用を伴うため、データポインタの移動をあまり避けるために値が近くにある必要があるため、マップ内の各値には一時変数スロットも近くにあります。これらはキャリーセルやその他の便利なスクラッチスペースも提供し、コピーをコンテインします。 乗算も同様に単純で、各セルを乗算し、結果を格納し、後でそれらを合計します。乗算ステップは、繰り返し加算によって処理されます。2つのセルを乗算するには、一方を一時的な場所にコピーして外側のループとして使用し、もう一方を内側のループとして機能させるために各イテレーションでコピーします。内側のループの各イテレーションは、結果を1回インクリメントします。 [a, b, a->0, b->0, a + ... + a] ここでaは毎回なくなり、aがゼロになるとbがデクリメントされ、b個のaのコピーが生成されます。 4セル値の場合、一方の各セルともう一方の各セルがペアになります。i番目のセルとj番目のセルの乗算は、8セル結果のi+jに加算されます。 [a0, a1, a2, a3] * [b0, b1, b