Super Mario Derivations

One of the most surprising aspects of the Nix language is that it is lazy, especially if you have never used a lazy language before. This laziness is what makes much of Nixpkgs possible, and its complexity. One of the simplest ways to observe the laziness is by understanding that only the attributes you access are evaluated. Nix 语言最令人惊讶的特性之一就是它的惰性（lazy），特别是如果你之前从未接触过惰性语言的话。正是这种惰性使得 Nixpkgs 的大部分功能及其复杂性成为可能。观察这种惰性最简单的方法之一，就是理解只有当你访问某个属性时，它才会被求值。

$ nix eval --expr 'let pkgs = { hello = "hi"; broken = throw "never forced"; }; in pkgs.hello'
"hi"

The more whackier version of this is you can have endless recursion in an attribute set. Nixpkgs is filled with these bottomless attribute sets: 更疯狂的版本是，你可以在属性集中进行无限递归。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

The same store path every time. pkgs contains itself, and so does every package set inside it. 🤯 If laziness is what lets a recursive attribute set terminate, then the recursion doesn’t have to bottom out at all: 每次得到的存储路径都相同。pkgs 包含它自身，其中的每个包集合也是如此。🤯 如果说惰性是让递归属性集能够终止的原因，那么递归本身甚至根本不需要有终点：

$ nix eval --expr \
  'let countdown = n: { value = n; next = countdown (n + 1); }; in (countdown 0).next.next.next.value'
3

That attribute set is infinitely deep. Indexing three levels into it costs exactly three levels of evaluation, and the rest of the infinite tree is never built because nobody asked. So an attribute path is a walk through a lazily-generated tree. Which made me wonder: what if the attribute path were input to something? 🤔 那个属性集是无限深度的。索引到它的第三层级仅消耗三个层级的求值，而无限树的其余部分因为无人访问而永远不会被构建。因此，属性路径实际上是在一棵惰性生成的树中漫步。这让我不禁思考：如果将属性路径作为某种东西的输入会怎样？🤔

I decided to take that idea and make the attribute path a sequence of button presses in Super Mario Bros. 3. Each node in the tree is a frame of the game, and each child is a button press that produces a new frame. Game states are recursive by nature. 我决定采纳这个想法，将属性路径转化为《超级马力欧兄弟 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 is right + B, which in Super Mario Bros. 3 is “run right”. .rightab is run and jump. The output is the frame you’d be looking at if you’d pressed those buttons in that order, on real hardware, in that game. The prefix .#level1 is a precanned sequence of button presses that gets you to the start of level 1-1. Append .play anywhere along the path and you get the whole run stitched into a recording: .rightb 代表右键 + B 键，在《超级马力欧兄弟 3》中即为“向右奔跑”。.rightab 则是奔跑加跳跃。输出的结果就是你在真实硬件上按顺序按下这些按键后所看到的画面。前缀 .#level1 是一段预设的按键序列，可以将你带到 1-1 关卡的起点。在路径的任何位置附加 .play，你就能得到将整个过程拼接而成的录像：

The coolest thing though is that every one of those frames is a separate derivation in my store. The code is at fzakaria/nes-nix. It is generalized and the ROM is a flake input you point wherever you like for any other game. The flake computes a derivation based on the attribute path such that each press is its own derivation, and it takes the previous press’s savestate as an input. Each derivation never re-emulates its ancestors’ frames. 最酷的地方在于，每一帧在我的存储中都是一个独立的派生（derivation）。代码位于 fzakaria/nes-nix。它是通用的，ROM 是一个 flake 输入，你可以将其指向任何其他游戏。该 flake 根据属性路径计算派生，使得每一次按键都成为其自身的派生，并将上一次按键的存档状态作为输入。每个派生都不会重新模拟其祖先帧。

The practical consequence is that the store becomes the emulator’s savestate history: 实际的结果是，存储空间变成了模拟器的存档历史记录：

# 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'

Branching off the middle of a hundred-press run costs one press as does appending to the end of it. We can look at it the other way. The dependency graph is the input sequence, so we can ask Nix what buttons produced a frame: 从一百次按键过程的中间分支出去，其成本与在末尾追加一次按键相同。我们也可以反过来思考。依赖图就是输入序列，因此我们可以询问 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

So what is .play actually doing? Almost nothing. Every frame along the path is already sitting in the store as the output of its own press, so the recording never emulates anything. It is a directory of symlinks to the frames for ffmpeg to process. 那么 .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

How far can we take this input-sequence game input idea? Nix by default gives out at around 2,400 presses… 我们能把这种“输入序列作为游戏输入”的想法推向多远？Nix 默认在约 2,400 次按键后就会崩溃：

$ nix eval --raw ".#game.right.right.right…drvPath"
error: stack overflow; max-call-depth exceeded

max-call-depth defaults to 10,000 and evaluating each press costs roughly four nested calls. It’s a guard against runaway recursion, not a structural limit, and we can raise it to 10 million and get 20,000 presses: max-call-depth 默认为 10,000，而评估每次按键大约需要四次嵌套调用。这是一种防止失控递归的保护机制，而非结构性限制。我们可以将其提高到 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 presses, takes roughly fourteen seconds to evaluate on my laptop. The cost is linear in the number of presses, and it is roughly 0.7ms “per press”. The next bottleneck though is that the kernel gives out at 21,845 presses on my machine. An attribute path is a single argv element, and Linux caps the size of the argument list in total and individual arguments. The per-argument limit is 131,072 bytes (MAX_ARG_STRLEN), and each press is six bytes long (right.), so 21,845 presses is the maximum that can be passed to nix eval as a single argument. 20,000 次按键在我的笔记本电脑上大约需要 14 秒来求值。成本与按键次数呈线性关系，大约是“每次按键”0.7 毫秒。然而，下一个瓶颈是内核在我的机器上限制为 21,845 次按键。属性路径是一个单一的 argv 元素，而 Linux 对参数列表的总大小和单个参数的大小都有限制。单个参数的限制是 131,072 字节（MAX_ARG_STRLEN），而每次按键长度为 6 字节（right.），因此 21,845 次按键是作为单个参数传递给 nix eval 的上限。

The escape hatch is to stop passing the run as an argument, and we can feed in the input-sequence as from a file: 解决办法是停止将运行过程作为参数传递，我们可以从文件中输入序列：

$ nix build --impure --expr \
  '(builtins.getFlake (toString ./.)) .packages.x86_64-linux.game.sequenceFile ./runs/world1-1.txt'

This produces the byte-identical derivation to the equivalent attribute path, so a run kept in a file still shares the same store paths. All of this was to simply evaluate the Nix expression. Now we have to build it. Although Nix is great at building derivations in parallel, the recursion here is tail-recursive… 这会产生与等效属性路径字节完全相同的派生，因此保存在文件中的运行过程仍然共享相同的存储路径。所有这些仅仅是为了求值 Nix 表达式。现在我们必须构建它。虽然 Nix 在并行构建派生方面非常出色，但这里的递归是尾递归的……