Nixpkgs supports overriding sets of packages using overlays and these overrides bear many similarities to object-oriented inheritance.

As a simple example, I can disable tests for the `hello`

package in Nixpkgs using code that superficially resembles a subclass overriding a superclass method:

```
# ./example.nix
let
overlay = self: super: {
hello = super.hello.overrideAttrs (old: {
doCheck = false;
});
};
pkgs = import <nixpkgs> { overlays = [ overlay ]; };
in
pkgs.hello
```

Here the `super`

identifier plays a role similar to an object-oriented superclass: if you squint and view the package set preceding the override as the “superclass” then the above code defines the `hello`

package for my “subclass” as being the same as the `hello`

package from the “superclass” except without tests.

Also, just like in object-oriented programming, your “methods” (i.e. packages) can refer to other “methods” from within the same “class”, using `self`

. For example, I can specify that I want the `hello`

package to gratuitously run `cowsay`

after the installation phase, like this:

```
# ./example.nix
let
overlay = self: super: {
hello = super.hello.overrideAttrs (old: {
postInstall = "${self.cowsay}/bin/cowsay 'Installation complete'";
});
};
pkgs = import <nixpkgs> { overlays = [ overlay ]; };
in
pkgs.hello
```

… and if we build that we’ll see the output from `cowsay`

in the build logs:

```
$ nix-build ./example.nix
…
_______________________
< Installation complete >
-----------------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
@nix { "action": "setPhase", "phase": "fixupPhase" }
post-installation fixup
gzipping man pages under /nix/store/xid1pxd0bccq8592pbjrb5b9k4qv3zzq-hello-2.10/
strip is /nix/store/hm2qzyqh6bh872rwlpjl4kw7a1nk173d-clang-wrapper-11.1.0/bin/st
stripping (with command strip and flags -S) in /nix/store/xid1pxd0bccq8592pbjrb5
patching script interpreter paths in /nix/store/xid1pxd0bccq8592pbjrb5b9k4qv3zzq
/nix/store/xid1pxd0bccq8592pbjrb5b9k4qv3zzq-hello-2.10
```

You can also combine multiple overlays, which lets you spread out these sorts of overrides into separate logical units. For example, we can create one overlay that disable tests for the `hello`

package and a second overlay that adds the `cowsay`

post-install step, like this:

```
let
overlay0 = self: super: {
hello = super.hello.overrideAttrs (old: {
doCheck = false;
});
};
overlay1 = self: super: {
hello = super.hello.overrideAttrs (old: {
postInstall = "${self.cowsay}/bin/cowsay 'Installation complete'";
});
};
pkgs = import <nixpkgs> { overlays = [ overlay0 overlay1 ]; };
in
pkgs.hello
```

Under the hood, when you specify multiple overlays they are combined using the `pkgs.lib.composeExtensions`

function (which will be relevant in just a second).

#### Monoids

Overlays are not only practical, but also theoretically cool, because overlays are monoids!

To see why, we have to first establish the three things that constitute a monoid:

Every monoid has a corresponding type, which we’ll denote as

`M`

Every monoid has an associative binary operator, which we’ll denote as

`×`

This operator has type:

`M -> M -> M`

(using Haskell notation). In other words it is a function of two inputs of type`M`

and returns an output, also of type`M`

.Every monoid has an “identity” of that operator, which we’ll denote as

`1`

This “identity” is a value of type

`M`

.

When we say that `×`

is associative, we mean that for any three values (e.g. `a`

, `b`

, and `c`

) of type `M`

, the following equation is true:

`= a × (b × c) (a × b) × c `

In other words, the way in which we group multiplication does not change the result. In fact, associativity means that we can elide the parentheses and the meaning of the expression is still unambiguous:

` a × b × c`

When we say that `1`

is the “identity” of `×`

, we mean that for any value (e.g. `a`

) of type `M`

, the following equations are true:

```
1 × a = a
1 = a a ×
```

#### Other monoids

Here we use `×`

to denote the binary operator and `1`

to denote the corresponding identity value because we want to reuse our intuition that multiplication is associative and the number `1`

is the identity of multiplication. However, monoids are more general than numbers and multiplication; there might be other binary operators and identity elements that behave in the same way.

For example, Nix attribute sets are also monoids, if we replace `×`

with `//`

and replace `1`

with `{ }`

:

```
# // is an associative binary operator
(a // b) // c = a // (b // c)
# … and { } is the identity of //
{ } // a = a
a // { } = a
```

Also, as the title suggests, overlays from Nixpkgs are yet another example of a monoid! We can illustrate this by defining the three components of the “overlay monoid”:

The type

`M`

(using Haskell notation) is:`-- Nix derivations are not actually text, but this keeps the example simple type Derivation = Text type PackageSet = Map Text Derivation type M = PackageSet -> PackageSet -> PackageSet -- … which we can expand out to the following equivalent type if we prefer: type M = Map Text Derivation -> Map Text Derivation -> Map Text Derivation`

The binary operator is

`pkgs.lib.composeExtensions`

(the same function I mentioned earlier which combines overlays)The

`composeExtensions`

function is defined like this in Nixpkgs (refactored to improve the clarity of upcoming examples):`composeExtensions = f: g: self: super: f self super // g self (super // f self super);`

Using object-oriented terminology, you can read that as saying: “to combine the methods defined in both

`f`

and`g`

, first extend`g`

’s superclass with all of`f`

’s methods, then combine both sets of methods, giving precedence to methods defined in`g`

”.The equivalent Haskell type and implementation would be:

`composeExtensions :: M -> M -> M = composeExtensions f g -> \self super Map.union (g self (Map.union (f self super) super)) (f self super)`

Carefully note that in the above Haskell code:

`f`

has type`M`

`g`

has type`M`

- Everything past the
`=`

sign (i.e.`\self super -> …`

) has type`M`

It might help to expand out the Haskell type since the

`M`

type synonym is hiding a lot of complexity:`-- This larger type is equivalent to the previous type: composeExtensions :: (PackageSet -> PackageSet -> PackageSet) -- ← M -> (PackageSet -> PackageSet -> PackageSet) -- ← M -> (PackageSet -> PackageSet -> PackageSet) -- ← M -- We can expand things out further to this even larger equivalent type: composeExtensions :: (Map Text Derivation -> Map Text Derivation -> Map Text Derivation) -> (Map Text Derivation -> Map Text Derivation -> Map Text Derivation) -> (Map Text Derivation -> Map Text Derivation -> Map Text Derivation)`

The identity value is

`(self: super: { })`

(the empty overlay)The equivalent Haskell type and implementation would be:

`identityExtension :: M = identityExtension -> Map.empty \self super -- The following types are also equivalent: identityExtension :: PackageSet -> PackageSet -> PackageSet identityExtension :: Map Text Derivation -> Map Text Derivation -> Map Text Derivation`

All we’re missing to establish that this is a bona-fide monoid is to prove that `composeExtensions`

is an associative function and that `identityExtension`

is its identity. We’ll do so using equational reasoning, but in Nix rather than Haskell:

It’s easier to prove the identity laws, so we’ll start with those:

```
composeExtensions (self: super: { }) f
# Replace composeExtensions with its definition
= self: super:
(self: super: { }) self super
// f self (super // (self: super: { }) self super)
# (self: super: e) self super = e
= self: super: { } // f self (super // { })
# { } // a = a
= self: super: f self (super // { })
# a // { } = a
= self: super: f self super
# η-reduction
= f
```

The other identity law is equally simple to prove:

```
composeExtensions f (self: super: { })
# Replace composeExtensions with its definition
= self: super: f self super // (self: super: { }) self (super // f self super)
# β-reduction
= self: super: f self super // { }
# a // { } = a
= self: super: f self super
# η-reduction
= f
```

Now, let’s prove that `composeExtensions`

is associative, which means proving that:

```
composeExtensions (composeExtensions f g) h =
composeExtensions f (composeExtensions g h)
```

We’ll begin from the left-hand side of the equation and keep rewriting until we reach the right-hand side of the equation:

```
composeExtensions (composeExtensions f g) h
# Replace the inner composeExtensions with its definition
= composeExtensions
(self: super: f self super // g self (super // f self super))
h
# Replace the outer composeExtensions with its definition
= self: super:
(self: super: f self super // g self (super // f self super))
self
super
// h self
( super
// (self: super:
f self super // g self (super // f self super)
)
self
super
)
# (self: super: e) self super = e
= self: super:
f self super
// g self (super // f self super)
// h self (super // f self super // g self (super // f self super))
# Factor out the three occurrences of `super // f self super` using a lambda
= self: super:
f self super
// (super: g self super // h self (super // g self super))
(super // f self super)
# e = (self: e) self
= self: super:
f self super
// (self: super: g self super // h self (super // g self super)) self
(super // f self super)
# Definition of composeExtensions, but in reverse
= composeExtensions
f
(self: super: g self super // h self (super // g self super))
# Definition of composeExtensions, but in reverse
= composeExtensions f (composeExtensions g h)
```

#### Generalization

In fact, the above implementation and the proofs of associativity/identity still work if you:

- replace
`//`

with any associative operator - replace
`{ }`

with the corresponding identity of the associative operator

In other words, we can generalize our implementation by replace Nix attribute sets with any arbitrary monoid! We can codify this neat property with the following Haskell type and `Monoid`

instance:

```
-- This generalizes our previous overlay type
newtype Overlay m = Overlay { runOverlay :: m -> m -> m }
-- The `(<>)` operator generalizes our previous `composeExtensions` function
instance Semigroup m => Semigroup (Overlay m) where
Overlay f <> Overlay g =
Overlay (\self super -> f self super <> g self (super <> f self super))
-- `mempty` generalizes our previous `identityExtension`
instance Monoid m => Monoid (Overlay m) where
mempty = Overlay (\self super -> mempty)
```

We can prove that this code generalizes the previous code by showing how we can implement the old overlay type and functions in terms of the new ones. The old code becomes a special case of the new code when we replace the type parameter `m`

with `Dual (Map Text Derivation)`

:

```
{-# LANGUAGE TypeApplications #-}
import Data.Coerce (coerce)
import Data.Map (Map)
import Data.Monoid (Dual(..))
import Data.Text (Text)
newtype Overlay m = Overlay { runOverlay :: m -> m -> m }
instance Semigroup m => Semigroup (Overlay m) where
Overlay f <> Overlay g =
Overlay (\self super -> f self super <> g self (super <> f self super))
instance Monoid m => Monoid (Overlay m) where
mempty = Overlay (\self super -> mempty)
type Derivation = Text
type PackageSet = Map Text Derivation
type OldOverlay = PackageSet -> PackageSet -> PackageSet
type NewOverlay = Overlay (Dual PackageSet)
composeExtensions :: OldOverlay -> OldOverlay -> OldOverlay
=
composeExtensions @(NewOverlay -> NewOverlay -> NewOverlay)
coerce @(OldOverlay -> OldOverlay -> OldOverlay)
<>)
(
identityExtension :: OldOverlay
= coerce @NewOverlay @OldOverlay mempty identityExtension
```

#### Conclusion

I’m not sure if there would be any applications of this `Overlay`

type within the Haskell ecosystem, so I didn’t bother packaging up the latter `Overlay`

type and `Monoid`

instance. However, if you think this might be useful in your code then just let me know and I can create a tiny package for this purpose.

Hopefully this post illustrates how Nixpkgs overlays are actually a pretty principled system for overrides. Also, you might be able to formulate object-oriented inheritance in the same way, too, due to the similarities between Nix’s overlay system and object-oriented programming. The main difference is that Nix’s overlay system is weakly-typed, so to really give this a proper OOP treatment, you’d probably have to:

- replace Nix’s attribute sets with more strongly-typed records
- replace the
`Monoid`

with a more strongly-typed`Category`

… but I haven’t taken the time to fully flesh out that idea. Also, I’m not sure if it could be implemented in Haskell, since Haskell does not support anonymous records, but it might work just fine in PureScript.

Nice article! You might be interested in https://well-typed.com/blog/2018/03/oop-in-haskell/, as well as the references mentioned there.

ReplyDelete