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 thex
thunk at the pointer passed tof
, 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 evaluatingx
as long asf
only usesx
in a lazy way.- e.g.
fix (x: { a = x.b + 1; b = 0; })
. You don’t have to evaluatex
to evaluate the attrset because the values inside are lazy (i.e. not necessarily evaluated by evaluating the attrset itself). We knowx.b
is0
, soa = x.b + 1
means thatx.a
will first evaluate the attrset, then evaluateb = 0
, then evaluatea = 0 + 1
A neat consequence of this is that if
builtins.seq (f (throw "foo")) null
doesn’t error, thenfix f
won’t go infinite on its ownConceptually, it’s like time travel.
fix (x: <expr>)
is equivalent to<expr>
but withx
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 an openly recursive implementation of factorial.fix fac
returns a functionInt -> Int
that calculates the factorial. We call it open recursion because you can compose it with other functions so that it’s not justfac
being passed in asf
; 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