スーパーマリオのデリベーション

Nix言語で最も驚くべき側面の一つは、特に遅延評価言語を初めて使う場合、その遅延性です。この遅延性こそが、Nixpkgsの多くの可能性と複雑さを生み出しています。遅延性を理解する最も簡単な方法の一つは、アクセスされた属性のみが評価されるということです。 ``` $ nix eval --expr 'let pkgs = { hello = "hi"; broken = throw "never forced"; }; in pkgs.hello' "hi" ``` これのより奇妙なバージョンとして、属性セット内で無限の再帰を持つことができます。Nixpkgsはこのような底なしの属性セットで満たされています。 ``` $ nix eval -f '<nixpkgs>' 'pkgs.hello' --raw /nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2 $ nix eval -f '<nixpkgs>' 'pkgs.pkgs.pkgs.hello' --raw /nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2 $ nix eval -f '<nixpkgs>' 'pkgs.python3Packages.pkgs.hello' --raw /nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2 ``` 毎回同じストアパスです。pkgsはそれ自体を含み、その中のすべてのパッケージセットも同様です。 🤯 遅延性が再帰的な属性セットを終了させることを可能にするなら、再帰はまったく底に達する必要はありません。 ``` $ nix eval --expr \ 'let countdown = n: { value = n; next = countdown (n + 1); }; in (countdown 0).next.next.next.value' 3 ``` その属性セットは無限に深いです。3レベル深くインデックスを付けると、ちょうど3レベルの評価が必要になるだけで、無限の木の残りの部分は誰も要求しないため、決して構築されません。したがって、属性パスは遅延生成されたツリーを歩くことになります。これは、属性パスが何かの入力になったらどうなるだろうか、と考えさせられました。 🤔 そのアイデアを取り入れて、属性パスをスーパーマリオブラザーズ3のボタン入力シーケンスにすることにしました。ツリーの各ノードはゲームのフレームであり、各子ノードは新しいフレームを生成するボタン入力です。ゲームの状態は本質的に再帰的です。 ``` $ nix build '.#level1.rightb.rightb.rightab.rightb' $ file -L result result: PNG image data, 256 x 240, 8-bit/color RGB, non-interlaced ``` .rightb は右＋Bで、スーパーマリオブラザーズ3では「右に走る」という意味です。.rightab は走ってジャンプです。出力は、実際のハードウェアでそのゲームでその順序でボタンを押した場合に表示されるフレームです。 11スクリーンショットも生成され、ビデオシーケンスをまとめる際に使用されます。プレフィックス .#level1 は、レベル1-1の開始地点に到達するための、あらかじめ用意されたボタン入力シーケンスです。パスのどこかに .play を追加すると、実行全体が録画にまとめられます。 しかし、最もクールなのは、それらのフレームのすべてが私のストアにある個別のデリベーションであるということです。コードは fzakaria/nes-nix にあります。これは汎用化されており、ROMは任意のゲームに合わせて好きな場所にポイントできるflake入力です。flakeは属性パスに基づいたデリベーションを計算し、各プレスはその独自のデリベーションとなり、前のプレスのセーブステートを入力として取ります。各デリベーションは、祖先のフレームを再エミュレートすることはありません。 22スクリーンショットはフレームごとに生成され、ビデオシーケンスをまとめる際に使用されます。 ``` trunk1 level1 2y1qjbk7…-nes-wait16 trunk2 .rightb gdbgfpdk…-nes-rightb trunk1->trunk2 run .rightb kpjlw529…-nes-rightb trunk2->run jump .rightab iv6asl0i…-nes-rightab trunk2->jump a .a q02kp71k…-nes-a run->a righta .righta nb87m9ss…-nes-righta run->righta ``` 実際的な結果として、ストアはエミュレータのセーブステート履歴になります。 ``` # 3つのデリベーション、コールドスタート $ nix build '.#game.start4.wait2.right' # 1つのデリベーション、プレフィックス再利用 $ nix build '.#game.start4.wait2.left' # 1つのデリベーション、すべて再利用 $ nix build '.#game.start4.wait2.right.right' ``` 100回のプレスの途中で分岐することは、末尾に追加することと同じように、1回のプレスで済みます。逆に考えることもできます。依存関係グラフは入力シーケンスなので、Nixにどのボタンがフレームを生成したかを尋ねることができます。 ``` $ nix-store --query --tree $(nix eval --raw '.#game.start.wait4.start.drvPath') /nix/store/32n4ni0zg01b9c9v64x67am37rdmmr9y-nes-start.drv └───/nix/store/j5vy3385pgs9dzw0y7sdrdmn7xnrxgji-nes-wait4.drv └───/nix/store/w4zz5aqj5zxqhnialabdc7p3sy80v6dc-nes-start.drv └───/nix/store/k9wfz8w5157d0xdwaw1vvhf019dvw5s0-nes-boot.drv ``` .play は実際にはほとんど何もしていません。パス上のすべてのフレームは、それ自体のプレスの出力としてすでにストアに存在するため、録画は何もエミュレートしません。ffmpegで処理するためのフレームへのシンボリックリンクのディレクトリです。 ``` $ nix build '.#level1.rightb.rightb.rightab.play' $ ls -l result/frames | head -4 0000.png -> /nix/store/3p2fxwngh…-nes-boot 0001.png -> /nix/store/4ha88l0dk…-nes-start 0002.png -> /nix/store/nh4zfsq6x…-nes-wait4 0003.png -> /nix/store/ghbgn28f1…-nes-start ``` ``` cluster_play result/frames : playデリベーション cluster_store /nix/store : プレスごとの1つのデリベーション f0 0000.png p0 3p2fxwngh…-nes-boot f0->p0 シンボリックリンク f1 0001.png p1 4ha88l0dk…-nes-start f1->p1 f2 0002.png p2 nh4zfsq6x…-nes-wait4 f2->p2 f3 0003.png p3 ghbgn28f1…-nes-start f3->p3 ``` この入力シーケンスゲーム入力のアイデアをどこまで推し進めることができるでしょうか？Nixはデフォルトで約2,400回のプレスで限界に達します。 ``` $ nix eval --raw ".#game.right.right.right…drvPath" error: stack overflow; max-call-depth exceeded ``` max-call-depthはデフォルトで10,000であり、各プレスを評価するには約4つのネストされた呼び出しが必要です。これは暴走する再帰に対するガードであり、構造的な制限ではありません。これを1000万に引き上げると、20,000回のプレスが可能になります。 ``` $ ulimit -s unlimited $ nix eval --raw --option max-call-depth 10000000 \ ".#game.$( python3 -c 'print(".".join(["right"]*20000))') .drvPath" /nix/store/p4nm0a4p4k9bdjqsag1jj0baah9mj6hb-nes-right.drv ``` 20,000回のプレスは、私のラップトップで評価するのに約14秒かかります。コストはプレスの数に線形であり、プレスあたり約0.7ミリ秒です。 1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ しかし、次のボトルネックは、カーネルが私のマシンで21,845回のプレスで限界に達することです。属性パスは単一のargv要素であり、Linuxは引数リストの合計サイズと個々の引数のサイズを制限します。引数あたりの制限は131,072バイト（MAX_ARG_STRLEN）であり、各プレスは6バイト（right.）なので、21,845回のプレスがnix evalに単一の引数として渡せる最大数です。回避策は、実行を引数として渡すのをやめることです。 そして、入力シーケンスをファイルから読み込むことができます。 ``` $ nix build --impure --expr \ "(builtins.getFlake (toString ./.)) .packages.x86_64-linux.game.sequenceFile ./runs/world1-1.txt" ``` これは同等の属性パスとバイト単位で同一のデリベーションを生成するため、ファイルに保存された実行も同じストアパスを共有します。これらすべては、単にNix式を評価するためでした。次に、それをビルドする必要があります。Nixはデリベーションを並列でビルドするのは得意ですが、ここでの再帰はテイル再帰であるため、逐次的です。ボタンプレスのリストを増やしながらビルド時間をベンチマークしたところ、コストも線形であり、予想通り、プレスの数に比例します。プレスあたりのコストは、サブリューザーが有効な場合は約1.27秒、無効な場合は0.28秒です。キャッシュにデリベーションが存在するかどうかを確認するための往復コストは、フレームのエミュレーションコストよりも顕著に高くなります。 33ローカルビルドを優先するか、サブリューザーを許可することで、このコストを回避できます。1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 属性パスが単なる名前、つまり存在するカタログへの座標であることに慣れています。遅延評価は、それが実際にプログラムであることを意味します。評価者が歩む一連のステップであり、必要に応じて生成されます。Nixpkgsはその仕組みをソフトウェアを記述するために使用しますが、ツリーがカタログである必要はまったくありません。ストアが再現可能なステートマシンのためのまともな永続レイヤーであることが判明したことと相まって、私たちの「パッケージマネージャー」はマリオをプレイするために合理的に使用できます。 🍄