Help understanding lib.extends?

I’m trying to understand what lib.extends does. I have run little test-cases in the nix repl, and there’s one that is confusing me. Why does this:

h = self: {a = 1000; b = self.a / 2; c = self.b / 2;d = self.c / 2;}
lib.fix (lib.extends (final: prev: { a = -10 ;b = prev.a ; c = prev.b ;d= prev.c ;e = prev.d ;}) h)

Output this:
{
a = -10;
b = 1000;
c = -5;
d = 500;
e = -2;
}

You can think of extends like applying an overlay - which is not too far off as ultimately when we talk about overlays, the resulting nixpkgs is a fixpoint obtained via lib.fix. final is the fixpoint, prev is the previous value before applying this “overlay”, and the final values will be taken from the first argument to lib.extends.

So a == -10 is pretty much expected. Similarly, b == 1000 should be expected as well.
(If those cases confuse you, please ask about it.)

c == -5 is probably the surprising bit for you, and that comes from the fact that the arg passed to h (the second arg of lib.extends) is also referring to the final value, though you happen to call the final value self here.

Before the overlay is applied, the value of b would have been final.a / 2 which is (-10) / 2 which is -5. So c is now prev.b which is -5. It’s not relevant that the final value of b is now 1000, because you specified in your overlay that you want prev.b. So after the overlay is applied, c is -5.

Then for d, again, before the overlay is applied, the value of c would have been final.b / 2 which is 1000 / 2 i.e. 500. So the final value of d becomes 500 after the overlay is applied.

Same goes for e.

Apologies if that explanation was more confusing or misleading than helpful, I’m not sure how to make it more accessible, nor would I call myself an expert in lambda calculus.

EDIT: or maybe this explanation will be clearer:

{ a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; }
== { a = -10; b = 1000; c = final.a / 2; d = final.b / 2; e = final.c / 2; }
== { a = -10; b = 1000; c = (-10) / 2; d = (1000) / 2; e = ((-10)/2) / 2; }
== { a = -10; b = 1000; c = -5; d = 500; e = -2; }

Let’s expand out the definitions of fix and extends and see.

extends = overlay: f: final:
  let prev = f final; in prev // overlay final prev;
fix = f: let x = f x; in x;

So your expression can be reduced as follows:

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
fix
  (extends
    (final: prev: { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; })
    h
  )

(inlining fix)

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
(f: let x = f x; in x)
  (extends
    (final: prev: { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; })
    h
  )

(beta reduction)

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
let x =
  extends
    (final: prev: { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; })
    h
    x;
in x

(inlining extends)

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
let x =
  (overlay: f: final: let prev = f final; in prev // overlay final prev)
    (final: prev: { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; })
    h
    x;
in x

(beta reduction)

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
let x =
  let prev = h x;
  in
  prev // (final: prev: { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; }) x prev);
in x

(another beta reduction)

let h = self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; };
in
let x =
  let prev = h x;
  in
  prev // { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; };
in x

(inlining h)

let x =
  let prev = (self: { a = 1000; b = self.a / 2; c = self.b / 2; d = self.c / 2; }) x;
  in
  prev // { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; };
in x

(beta reduction)

let x =
  let prev = { a = 1000; b = x.a / 2; c = x.b / 2; d = x.c / 2; };
  in
  prev // { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; };
in x

(consolidate the lets so this is easier to look at)

let
  prev = { a = 1000; b = x.a / 2; c = x.b / 2; d = x.c / 2; };
  x = prev // { a = -10; b = prev.a; c = prev.b; d = prev.c; e = prev.d; };
in x

If you look at that expression, it should be easier to see without having to do a bunch more reduction steps why the final result is what it is. You have to bounce back and forth between prev and x several times to see what the values of the later attributes are, and that’s the value that overlays provide: they let you consume the final result of some attributes (as when prev references x here) alongside an intermediate result of others (as when x references prev).

2 Likes

Thanks for the replies. These both seem like very helpful explanations - I was interested in help with both the verbal/conceptual explanation and also understanding more programmatically how the recursion worked. It may take me a while to digest these responses. I’m replying now, rather than after I’ve worked through it, because I am only ~90% confident in my ability to remember to thank you after working through this.

2 Likes