Trying to understand `lib.fix`

[a12l]

I’m in the process trying to understand how Nix’s module system and overlays work. I found @Infinisil’s video The Nix Hour #19 [module system recursion, config vs config, common infinite recursion causes] [0]. When watching the video I quickly understood that lib.fix [1] is fundamental to how nixpkgs works. so I set out to learn and understand how it works.

I found @akavel’s blog post Understanding Nix’s lib.fix [2], but several steps in that evaluation confuses me. The steps that confuse me is

Step 2 → 3: Why does (f: let x = f x; in x) f evaluate to x?

Steps 3 → 4, 4 → 5, 8 → 9, 9 → 10: How does Nix know to concatenate let x = ...; in and let x = f x; in to the expressions? My (obviously wrong) feeling is that “information” about the functions fix and f is removed when (f: let x = f x; in x) f is evaluated to x in step 2 -> 3.

My mental model of how evaluation works is similar to how you would show how two different expressions is equal by rewriting each expression step by step using different definitions.

Step 11 → 12: How can the evaluator go directly from foobar = (f x).foo + (f x).bar to foobar = { foo = "foo"; ... }.foo + { ...; bar = "bar"; ...; }.bar;, without needing to evaluate foobar = ((self: { foo = "foo"; ...; } x).foo + ((self: { ...; bar = "bar"; ...; }) x).bar? A friend suggested that maybe the steps shown in @akavel’s post wasn’t actual evaluation steps, but manually crafted steps trying to pedagogically explain how it works. If so, it didn’t help me.

I think that my fundamental problem is that I don’t understand lazy evaluation. I’ve written Haskell programs in university courses, but I’ve never needed to take lazy evaluation into consideration while writing my programs. I know that lazy evaluation can be shortly explained as “don’t evaluate expressions before you absolutely need to”, but I don’t know how evaluation works when it actually evaluates expressions. And after some searching on the web it seems that something called “memoization” is part of the answers to my questions?

I found a discussion about the article in the Matrix chat from some time ago [3], there @ElvishJerricco tried to explain

It’s a laziness thing. Procedurally you can think of it like this:

• Allocate unevaluated thunk x.
• Stuff it with code that says “call f with a pointer to that thunk”.
• When someone evaluates x, run that code.
• f will return something. If evaluating that something requires evaluating the x thunk at the pointer passed to f, then we bail with an infinite recursion error. Otherwise, we just return that thing.
• Laziness means that we can evaluate what’s returned by f without evaluating x as long as f only uses x in a lazy way.
• e.g. fix (x: { a = x.b + 1; b = 0; }). You don’t have to evaluate x to evaluate the attrset because the values inside are lazy (i.e. not necessarily evaluated by evaluating the attrset itself). We know x.b is 0, so a = x.b + 1 means that x.a will first evaluate the attrset, then evaluate b = 0, then evaluate a = 0 + 1

A neat consequence of this is that if builtins.seq (f (throw "foo")) null doesn’t error, then fix f won’t go infinite on its own

Conceptually, it’s like time travel. fix (x: <expr>) is equivalent to <expr> but with x substituted for the premonition of what <expr> evaluates to. If you use this future sight to make <expr> eagerly depend on <expr>, then you’ve created a time travel paradox and the universe blows up

I wrote about this for fix and MonadFix in Haskell: MonadFix is Time Travel

[…]

It’s similar to something called open recursion (I’m not sure what it’s called when it’s the same idea but not recursive :P). Like fac = f: x: if x == 1 then 1 else x * (f (x - 1)) is an openly recursive implementation of factorial. fix fac returns a function Int -> Int that calculates the factorial. We call it open recursion because you can compose it with other functions so that it’s not just fac being passed in as f; it can be something that modfies the behavior in some odd way, like returning a nested data structure that contains both the the result and all the previous steps

Similarly, overlays represent open recursion by altering what any given package might actually evaluate to

Actually, I don’t think that nested data structure example works, but you get the idea

Sadly @ElvishJerricco’s explanation didn’t help me much, neither the one in Matrix nor the one on his blog. I also looked at the blog post @ElvishJerricco refers to inside his blog post for explaining how the fix point combinator works [4], but it didn’t help .

[0] The Nix Hour #19 [module system recursion, config vs config, common infinite recursion causes] - YouTube

[1] nixpkgs/lib/fixed-points.nix at 96e46251e3346261c153c0543d9c5118c1f0fe6c · NixOS/nixpkgs · GitHub

[2] Understanding Nix's lib.fix - akavel

[3] You're invited to talk on Matrix

[4] Grokking Fix

[akavel]

I don’t visit here often, but thanks to your mention, now that I visited, I saw your post Not sure if you’re still interested in this, and whether I will be notified on email when you answer here… but I’ll try at least to start…

So: for now, let’s focus on “Step 2->3”, and see if we can get somewhere with it.

First of all, looking at it after so many years, I sadly see that it might not be obvious what’s going on in that area of the article But I’m also afraid it was already hard for me to try and explain it at all, so not sure I’d be able to find a better way… but maybe some day… Still, with that disclaimer out of the way:

The “Step 2->3” is not really what Nix does in reality. It’s more like my attempt at an explanation of an imaginary step it could in theory do. But does not really do. In a way, those “steps” are a kind of “reverse engineering” of coming from the laziest thing ever, back to a laziest thing permitted.

In yet another words, between each step, you could try inserting mentally a sentence of: “Ahh; but if I did this, they would say I’m too lazy, and I didn’t really do any work and give them any useful result. What could I do instead if I were just a tiny, teeny bit less lazy, and a tiny, teeny bit more useful?”

So, for example: “Step 1” is just repeating what the user asked for. This is the laziest possible thing a really lazy evaluator could do after seeing fix f, right?

But then, remember our mantra of the “reverese engineering” mentioned above: “it’s too lazy! what slighly more useful thing could be done instead?”

So, next slightly less lazy thing it could do, is substitute fix with fix’s definition, i.e. (f: let x...) etc. That results in Step 2. But… “it’s still too lazy and not useful”.

So, the next slightly less lazy approach is to look into the parentheses of fix. In the parentheses, a function is defined: (f: ...). This function is then called with some parameter named (also) f (sorry for the confusingly identical naming ). But let’s not get distracted by the parameter: let’s first see - in a laziest possible way - what does the function return? Parsing the function definition we see it returns the result of a let ... in x expression. Now, remember we’re really, really lazy. So, if someone asks us: “what does the (f: ...) function return?” — the laziest thing to do in this situation would be to reply: “Oh, it returns some stupid x, I don’t care, go away!” So, in this way of thinking, it would be valid (if not very useful) to say that fix f evaluates to x (where we mean this x that is defined inside (f: ...) through some boring expression that even reading looks very much like having to do some work instead of just being wonderfully lazy). But… “it’s still too lazy and not useful.”

So, again, for “Step 4-6”, what can we expand the original fix f to, that would be just a tiny bit less lazy than expanding it to x? We could explain what the x really is — and from the (f: ...) defintion we see that x is, actually, defined by the let x = ... expression as f x. So that’s the next less lazy thing we can do instead.

Etc. etc.

Does it make at least slightly more sense now? Or not really? I do like trying to explain things, but it’s totally not easy sometimes, and it’s equally not easy to know if the explanation was actually understandable, so I’d love to hear at this point whether it’s worth anything for us if I go this direction, or I should think of some another way of painting it, before I go too far in a funny but useless direction