An Alternate Understanding of Nix's lib.fix

06 July 2023
nix

I came across an article on Understanding Nix's lib.fix, which took me a while to understand. So I played around a bit, and the below is a slightly different interpretation that splits the "binding" and "evaluating" (names are invented) which I think is clearer.

The definition of lib.fix is deceivingly simple:

fix = f: let x = f x; in x;

As nix is lazily evaluated, note that the let statement is not immediately run, but is only evaluated when x is accessed. Let us consider the function

recursive = self: self,

which does not work as it creates infinite recursion — that nix detects!

nix-repl> fix recursive
error: infinite recursion encountered

Why?

Nix looks at fix and sees that it wants to return x (the return value is that following the let ... in).
x is defined as part of the let ... in statement, so x = f x.
What is f x? Naught but x itself. (f here is the recursive function)
Oh. Evaluating x got us x. This is infinite recursion. *errors*

A more complex example is

f2 = self: { a = 5; b = self.a + 5; },

which evaluates to

nix-repl> fix f2
{ a = 5; b = 10; }.

Let us step through again.

Nix looks at fix and sees that it wants to return x (the return value is that following the let ... in).
What is x? let x = f x. Ok. Let me evaluate that.
x is now { a = 5; b = x.a + 5; }. This can be returned. The x inside the expression for x is essentially a reference to the concept of x, but not evaluated — this is Nix's lazy evaluation at work.

Nix however, is very lazy. Our REPL session earlier is misleading, as it implies that we get a "nice" pre-evaluated object storing 10 — we don't.

Let us introspect what is happening. Consider the function

f3 = self: {
    a = trace "evaluating a..." 5;
    b = trace "evaluating b..." (self.a + 5);
},

noting the trace is a nix builtin that prints its first argument and returns the second. If we fix f3, the same steps happen as before, but we can see when a or b gets evaluated:

nix-repl> (fix f3).a
trace: evaluating a...
5

nix-repl> (fix f3).b
trace: evaluating b...
trace: evaluating a...
10

b is never evaluated if we only ask for a! This is laziness. The explanation for the evaluation of (fix f3).b is as follows:

fix f3 returns our conceptual x = { a = 5; b = x.a + 5; } self-recursive object from f2 above.
We access the element b, which tells us to evaluate x.a + 5. This also triggers our trace for evaluating b....
We know what 5 is, so we access the element a of x, then evaluate it. This triggers the trace for evaluating a..., and we get 5.
We add 5 + 5 and return 10.

If you print out the entirety of fix f3, it looks a little weird, but you can see that a and b are only evaluated when necessary (and in fact, here a gets re-used and not re-evaluated!)

{ a = trace: evaluating a...
5; b = trace: evaluating b...
10; }

The same logic would apply if we had say

f4 = self: { a = 5; b = self.a + 5; c = self.b + 5; },

giving us a "conceptual"

{ a = 5; b = x.a + 5; c = x.b + 5; },

where evaluating c evaluates b which evaluates a and so forth.

As an aside, the description in the original blogpost indicates that nix would reevaluate x as f x and do the "finding out" of what x is every time, which is probably plausible, but is conceptually the same thing.