HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Super Mario Derivations (fzakaria.com)

105 pointsby domenkozar14 コメント

要約

Nix言語の遅延評価(Laziness)の特性を、スーパーマリオブラザーズ3のゲームプレイと結びつけて解説した記事です。Nixの属性パスをボタン入力シーケンスと見なし、各ゲームフレームをNixのストアにおける個別のデリベーション(派生物)として生成する仕組みを紹介しています。これにより、ゲームの進行状態をNixのキャッシュとして効率的に管理・再利用することが可能になります。

全文翻訳

スーパーマリオの導出

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は走ってジャンプです。出力は、実際のハードウェアでそのゲームで、それらのボタンをその順序で押した場合に表示されるフレームです。¹ プレフィックス.#level1は、レベル1-1の開始地点に到達するための、事前に準備されたボタン操作のシーケンスです。

パスのどこかに.playを追加すると、実行全体が録画としてまとめられます。

[画像: スーパーマリオブラザーズ3がエミュレータで実行されている様子:タイトル画面、1/2プレイヤーメニュー、ワールド1マップ、そしてマリオがレベル1-1で右に走りジャンプしている様子]

しかし、最もクールなのは、それらのフレームのすべてが私のストア内の個別の導出であるということです。

コードはfzakaria/nes-nixにあります。これは汎用化されており、ROMは任意のゲームに対して好きな場所にポイントできるflake入力です。

flakeは属性パスに基づいて導出を計算し、各プレスが独自の導出となり、前のプレスのセーブステートを入力として取ります。各導出は、祖先のフレームを再エミュレートしません。² スクリーンショットも生成され、ビデオシーケンスをまとめたい場合に使用されます。

cluster_play result/frames : the play derivation cluster_store /nix/store : one derivation per press f0 0000.png p0 3p2fxwngh…-nes-boot f0->p0 symlink 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

実用的な結果として、ストアはエミュレータのセーブステート履歴になります。

# 3 derivations, cold
$ nix build '.#game.start4.wait2.right'
# 1 derivation, prefix reused
$ nix build '.#game.start4.wait2.left'
# 1 derivation, all of it reused
$ 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

この入力シーケンスゲーム入力というアイデアをどこまで推し進めることができるでしょうか?

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.7msです。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 0 5,000 10,000 15,000 20,000 5 10 15 default max-call-depth stops you here (~2,400) kernel argv limit 21,845 presses presses in the attribute path nix eval (seconds)

次のボトルネックは、カーネルが私のマシンで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は導出を並列でビルドするのが得意ですが、ここの再帰はテイル再帰であるため、シリアルになります。

ボタン操作のリストが増えるにつれてビルド時間をベンチマークしたところ、コストも線形であり、予想通り操作回数に比例します。操作あたりのコストは、サブラスト(substituters)を有効にした場合は約1.27秒、無効にした場合は0.28秒です。キャッシュに導出が存在するかどうかを確認するための往復コストは、フレームをエミュレートするコストよりも顕著に高くなります。³ preferLocalBuildまたはallowSubstitutesを設定することで、このコストを回避できます。

1980-01-01T00:00:00+00:00 image/svg+xml Matplotlib v3.10.5, https://matplotlib.org/ 50 100 150 200 0 100 200 50 100 150 200 0.0 0.5 1.0 1.5 2.0 presses built total wall clock (s) seconds per press --option substitute false default (queries binary caches)

私たちは、属性パスが名前であり、単に存在するもののカタログへの座標であることに慣れています。遅延評価は、それが実際にはプログラムであることを意味します。評価者が歩き、必要に応じて生成するステップのシーケンスです。

Nixpkgsはソフトウェアを記述するためにその仕組みを使用していますが、ツリーがカタログである必要は全くありません。ストアが再現可能なステートマシン用のまともな永続レイヤーであることが判明したことと組み合わせると、私たちの「パッケージマネージャー」はマリオをプレイするのに適しています。🍄