[pwm]

I would love to read more about all this, especially how overlays came from "object-oriented" programming. To me, the interesting part is their self-referential nature, for which lazy eval is indeed a great fit!

For anyone interested, this is how I'd illustrate Nix's overlays in Haskell (I know I know, I'm using one obscure lang to explain another...):

  data Attr a = Leaf a | Node (AttrSet a)
    deriving stock (Show, Functor)

  newtype AttrSet a = AttrSet (HashMap Text (Attr a))
    deriving stock (Show, Functor)
    deriving newtype (Semigroup, Monoid)

  type Overlay a = AttrSet a -> AttrSet a -> AttrSet a

  apply :: forall a. [Overlay a] -> AttrSet a -> AttrSet a
  apply overlays attrSet = fix go
    where
      go :: AttrSet a -> AttrSet a
      go final =
        let fs = map (\overlay -> overlay final) overlays
        in foldr (\f as -> f as <> as) attrSet fs

Which uses fix to tie the knot, so that each overlay has access to the final result of applying all overlays. To illustrate, if we do:

  find :: AttrSet a -> Text -> Maybe (Attr a)
  find (AttrSet m) k = HMap.lookup k m

  set :: AttrSet a -> Text -> Attr a -> AttrSet a
  set (AttrSet m) k v = AttrSet $ HMap.insert k v m

  overlayed =
    apply
      [ \final prev -> set prev "a" $ maybe (Leaf 0) (fmap (* 2)) (find final "b"),
        \_final prev -> set prev "b" $ Leaf 2
      ]
      (AttrSet $ HMap.fromList [("a", Leaf 1), ("b", Leaf 1)])

we get:

  λ overlayed
  AttrSet (fromList [("a",Leaf 4),("b",Leaf 2)])

Note that "a" is 4, not 2. Even though the "a = 2 * b" overlay was applied before the "b = 2" overlay, it had access to the final value of "b." The order of overlays still matters (it's right-to-left in my example tnx for foldr). For example, if I were to add another "b = 3" overlay in the middle, then "a" would be 6, not 4 (and if I add it to the end instead then "a" would stay 4).

[rssoconnor]

I have the following file called oop.nix dated from that time.

    # Object Oriented Programming library for Nix
    # By Russell O'Connor in collaboration with David Cunningham.
    #
    # This library provides support for object oriented programming in Nix.
    # The library uses the following concepts.
    #
    # A *class* is an open recursive set.  An open recursive set is a function from
    # self to a set.  For example:
    #
    #     self : { x = 4; y = self.x + 1 }
    #
    # Technically an open recursive set is not recursive at all, however the function
    # is intended to be used to form a fixed point where self will be the resulting
    # set.
    #
    # An *object* is a value which is the fixed point of a class.  For example:
    #
    #    let class = self : { x = 4; y = self.x + 1; };
    #        object = class object; in
    #    object
    #
    # The value of this object is '{ x = 4; y = 5; }'.  The 'new' function in this
    # library takes a class and returns an object.
    #
    #     new (self : { x = 4; y = self. x + 1; });
    #
    # The 'new' function also adds an attribute called 'nixClass' that returns the
    # class that was originally used to define the object.
    #
    # The attributes of an object are sometimes called *methods*.
    #
    # Classes can be extended using the 'extend' function in this library.
    # the extend function takes a class and extension, and returns a new class.
    # An *extension* is a function from self and super to a set containing method
    # overrides.  The super argument provides access to methods prior to being
    # overloaded.  For example:
    #
    #    let class = self : { x = 4; y = self.x + 1; };
    #        subclass = extend class (self : super : { x = 5; y = super.y * self.x; });
    #    in new subclass
    #
    # denotes '{ x = 5; y = 30; nixClass = <LAMBDA>; }'.  30 equals (5 + 1) * 5).
    #
    # An extension can also omit the 'super' argument.
    #
    #    let class = self : { x = 4; y = self.x + 1; };
    #        subclass = extend class (self : { y = self.x + 5; });
    #    in new subclass
    #
    # denotes '{ x = 4; y = 9; nixClass = <LAMBDA>; }'.
    #
    # An extension can also omit both the 'self' and 'super' arguments.
    #
    #    let class = self : { x = 4; y = self.x + 1; };
    #        subclass = extend class { x = 3; };
    #    in new subclass
    #
    # denotes '{ x = 3; y = 4; nixClass = <LAMBDA>; }'.
    #
    # The 'newExtend' function is a composition of new and extend.  It takes a
    # class and and extension and returns an object which is an instance of the
    # class extended by the extension.
    
    rec {
      new = class :
        let instance = class instance // { nixClass = class; }; in instance;
    
      extend = class : extension : self :
        let super = class self; in super //
         (if builtins.isFunction extension
          then let extensionSelf = extension self; in
               if builtins.isFunction extensionSelf
               then extensionSelf super
               else extensionSelf
          else extension
         );
    
      newExtend = class : extension : new (extend class extension);
    }

In nix overlays, the names "final" and "prev" used to be called "self" and "super", owing to this OOP heritage, but people seemed to find those names confusing. Maybe you can still find old instances of the names "self" and "super" in places.

[pwm]

Thanks for this! It's always nice to learn about the origins of things. I was around when they were called "self"/"super", but I never made the connection to OOP.

[rssoconnor]

These slides from Ralf Hinze were instrumental to my understanding of how to use late-binding to define objects in a functional language: https://www.cs.ox.ac.uk/people/ralf.hinze/talks/Open.pdf