Super Mario Derivations

One of the most surprising features of the Nix language is its laziness, which is particularly noticeable to those unfamiliar with lazy languages. This characteristic allows for the creation of bottomless attribute sets within Nixpkgs, where the same store path is repeated throughout. The complexity arises from understanding that only the attributes accessed are evaluated, enabling endless recursion in an attribute set. Nixpkgs showcases this with the `pkgs` containing itself and every package set inside it.

An intriguing aspect of this laziness is its application to Super Mario Bros. 3. By treating the attribute path as a sequence of button presses, each node in the recursive tree represents a frame of the game, and each child button press generates a new frame. The output frames can be viewed as separate derivations in a Nix store. The code for this concept is available at fzakaria/nes-nix, allowing for the emulation of any game by inputting a ROM as a flake input.

The process involves the Nix flake computing a derivation based on the attribute path, where each button press is its own derivation. The derivations do not re-emulate their ancestors' frames. Each frame is accompanied by a screenshot, which is used for stitching a video sequence together. This setup makes the Nix store act as the emulator's savestate history, allowing for branching and appending to the middle or end of a long run of button presses.

The dependency graph of this sequence represents the input, enabling inquiries into which buttons produced a specific frame. The evaluation of the Nix expression itself results in a directory of symlinks to the frames, which can then be processed by ffmpeg to create a video sequence. The maximum number of presses allowed by Nix is capped at 21,845, as per Linux's argument list size limit.

While Nix can build derivations in parallel, the recursion in this case is tail-recursive and therefore serial. Benchmarking the build time shows a linear cost per press, with roughly 1.27 seconds with substituters enabled and 0.28 seconds without. The round-trip cost for checking derivation cache is significantly higher than the emulation of the frames.

This concept demonstrates that the Nix package manager can be effectively used for playing Mario, leveraging its laziness and ability to handle complex sequences of button presses.