Playing Super Mario Bros. 3 with Nix Derivations

Nix's laziness is a double-edged sword: it powers the recursive attribute sets that make Nixpkgs possible, but it also means only the attributes you touch get evaluated. A developer, fzakaria, took this to its logical extreme by turning an attribute path into a sequence of button presses in Super Mario Bros. 3, with each node in the tree being a frame of the game.

The core trick is that each button press is its own derivation, taking the previous press's savestate as an input. This means the Nix store becomes the emulator's savestate history. Branching off the middle of a hundred-press run costs one press, as does appending to the end. The dependency graph is the input sequence, so you can query Nix to see exactly which buttons produced a frame.

The .play attribute is almost a no-op: every frame along the path is already in the store, so the recording never re-emulates anything. It's just a directory of symlinks to the frames, ready for ffmpeg to stitch together.

How far can this go? Nix's default max-call-depth of 10,000 gives out at around 2,400 presses, but raising it to 10 million (with ulimit -s unlimited) gets you 20,000 presses in about 14 seconds — roughly 0.7ms per press. The next bottleneck is the kernel's argv limit, which caps out at 21,845 presses on the author's machine.

The project, fzakaria/nes-nix, is generalized: the ROM is a flake input, so you can point it at any NES game. It's a delightful demonstration of how laziness and content-addressed storage can model stateful computation in a purely functional way.