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 returnsomething. 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 ownConceptually, 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 upI 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 anopenly recursiveimplementation 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 stepsSimilarly, 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 .

[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