Super Mario Derivations | Farid Zakaria’s Blog
Skip to content
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 eval --expr 'let pkgs =<br>{ hello = "hi"; broken = throw "never forced"; };<br>in pkgs.hello'<br>"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:
$ nix eval -f '' 'pkgs.hello' --raw<br>/nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2
$ nix eval -f '' 'pkgs.pkgs.pkgs.hello' --raw<br>/nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2
$ nix eval -f '' 'pkgs.python3Packages.pkgs.hello' --raw<br>/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 :
$ nix eval --expr \<br>'let countdown = n: { value = n; next = countdown (n + 1); };<br>in (countdown 0).next.next.next.value'
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.
$ nix build '.#level1.rightb.rightb.rightab.rightb'<br>$ file -L result<br>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.11The 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:
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.22A screenshot of the frame is also produced, which is used when we want to stitch a video sequence together.
trunk1
level1<br>2y1qjbk7…-nes-wait16
trunk2
.rightb<br>gdbgfpdk…-nes-rightb
trunk2 -->
trunk1->trunk2
run
.rightb<br>kpjlw529…-nes-rightb
run -->
trunk2->run
jump
.rightab<br>iv6asl0i…-nes-rightab
jump -->
trunk2->jump
.a<br>q02kp71k…-nes-a
a -->
run->a
righta
.righta<br>nb87m9ss…-nes-righta
righta -->
run->righta
The practical consequence is that the store becomes the emulator’s savestate history:
# 3 derivations, cold<br>$ nix build '.#game.start4.wait2.right'<br># 1 derivation, prefix reused<br>$ nix build '.#game.start4.wait2.left'<br># 1 derivation, all of it reused<br>$ 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-store --query --tree<br>$(nix eval --raw '.#game.start.wait4.start.drvPath')<br>/nix/store/32n4ni0zg01b9c9v64x67am37rdmmr9y-nes-start.drv<br>└───/nix/store/j5vy3385pgs9dzw0y7sdrdmn7xnrxgji-nes-wait4.drv<br>└───/nix/store/w4zz5aqj5zxqhnialabdc7p3sy80v6dc-nes-start.drv<br>└───/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.
$ nix build '.#level1.rightb.rightb.rightab.play'<br>$ ls -l result/frames | head -4<br>0000.png -> /nix/store/3p2fxwngh…-nes-boot<br>0001.png -> /nix/store/4ha88l0dk…-nes-start<br>0002.png -> /nix/store/nh4zfsq6x…-nes-wait4<br>0003.png -> /nix/store/ghbgn28f1…-nes-start
cluster_play
result/frames : the play derivation
cluster_store
/nix/store : one derivation per press
f0
0000.png
p0
3p2fxwngh…-nes-boot
p0 -->
f0->p0
symlink
f1
0001.png
p1
4ha88l0dk…-nes-start
p1 -->
f1->p1
f2
0002.png
p2
nh4zfsq6x…-nes-wait4
p2 -->
f2->p2
f3
0003.png
p3
ghbgn28f1…-nes-start
p3 -->
f3->p3
How...