Dissecting Guix, Part 2: The Store Monad

( — 2023-02-20

Hello again!

In the last post, we briefly mentioned the with-store and run-with-store macros. Today, we'll be looking at those in further detail, along with the related monad library and the %store-monad!

Typically, we use monads to chain operations together, and the %store-monad is no different; it's used to combine operations that work on the Guix store (for instance, creating derivations, building derivations, or adding data files to the store).

However, monads are a little hard to explain, and from a distance, they seem to be quite incomprehensible. So, I want you to erase them from your mind for now. We'll come back to them later. And be aware that if you can't seem to get your head around them, it's okay; you can understand most of the architecture of Guix without understanding monads.

Yes, No, Maybe So

Let's instead implement another M of functional programming, maybe values, representing a value that may or may not exist. For instance, there could be a procedure that attempts to pop a stack, returning the result if there is one, or nothing if the stack has no elements.

maybe is a very common feature of statically-typed functional languages, and you'll see it all over the place in Haskell and OCaml code. However, Guile is dynamically typed, so we usually use ad-hoc #f values as the "null value" instead of a proper "nothing" or "none".

Just for fun, though, we'll implement a proper maybe in Guile. Fire up that REPL once again, and let's import a bunch of modules that we'll need:

(use-modules (ice-9 match)
             (srfi srfi-9))

We'll implement maybe as a record with two fields, is? and value. If the value contains something, is? will be #t and value will contain the thing in question, and if it's empty, is?'ll be #f.

(define-record-type <maybe>
  (make-maybe is? value)
  maybe?
  (is? maybe-is?)
  (value maybe-value))

Now we'll define constructors for the two possible states:

(define (something value)
  (make-maybe #t value))

(define (nothing)
  (make-maybe #f #f)) ;the value here doesn't matter; we'll just use #f

And make some silly functions that return optional values:

(define (remove-a str)
  (if (eq? (string-ref str 0) #\a)
      (something (substring str 1))
      (nothing)))

(define (remove-b str)
  (if (eq? (string-ref str 0) #\b)
      (something (substring str 1))
      (nothing)))

(remove-a "ahh")
⇒ #<<maybe> is?: #t value: "hh">

(remove-a "ooh")
⇒ #<<maybe> is?: #f value: #f>

(remove-b "bad")
⇒ #<<maybe> is?: #t value: "ad">

But what if we want to compose the results of these functions?

Keeping Your Composure

As you might have guessed, this is not fun. Cosplaying as a compiler backend typically isn't.

(let ((t1 (remove-a "abcd")))
  (if (maybe-is? t1)
      (remove-b (maybe-value t1))
      (nothing)))
⇒ #<<maybe> is?: #t value: "cd">

(let ((t1 (remove-a "bbcd")))
  (if (maybe-is? t1)
      (remove-b (maybe-value t1))
      (nothing)))
⇒ #<<maybe> is?: #f value: #f>

I can almost hear the heckling. Even worse, composing three:

(let* ((t1 (remove-a "abad"))
       (t2 (if (maybe-is? t1)
               (remove-b (maybe-value t1))
               (nothing))))
  (if (maybe-is? t2)
      (remove-a (maybe-value t2))
      (nothing)))
⇒ #<<maybe> is?: #t value: "d">

So, how do we go about making this more bearable? Well, one way could be to make remove-a and remove-b accept maybes:

(define (remove-a ?str)
  (match ?str
    (($ <maybe> #t str)
     (if (eq? (string-ref str 0) #\a)
         (something (substring str 1))
         (nothing)))
    (_ (nothing))))

(define (remove-b ?str)
  (match ?str
    (($ <maybe> #t str)
     (if (eq? (string-ref str 0) #\b)
         (something (substring str 1))
         (nothing)))
    (_ (nothing))))

Not at all pretty, but it works!

(remove-b (remove-a (something "abc")))
⇒ #<<maybe> is?: #t value: "c">

Still, our procedures now require quite a bit of boilerplate. Might there be a better way?

The Ties That >>= Us

First of all, we'll revert to our original definitions of remove-a and remove-b, that is to say, the ones that take a regular value and return a maybe.

(define (remove-a str)
  (if (eq? (string-ref str 0) #\a)
      (something (substring str 1))
      (nothing)))

(define (remove-b str)
  (if (eq? (string-ref str 0) #\b)
      (something (substring str 1))
      (nothing)))

What if we tried introducing higher-order procedures (procedures that accept other procedures as arguments) into the equation? Because we're functional programmers and we have an unhealthy obsession with that sort of thing.

(define (maybe-chain maybe proc)
  (if (maybe-is? maybe)
      (proc (maybe-value maybe))
      (nothing)))

(maybe-chain (something "abc")
             remove-a)
⇒ #<<maybe> is?: #t value: "bc">

(maybe-chain (nothing)
             remove-a)
⇒ #<<maybe> is?: #f value: #f>

It lives! To make it easier to compose procedures like this, we'll define a macro that allows us to perform any number of sequenced operations with only one composition form:

(define-syntax maybe-chain*
  (syntax-rules ()
    ((_ maybe proc)
     (maybe-chain maybe proc))
    ((_ maybe proc rest ...)
     (maybe-chain* (maybe-chain maybe proc)
                   rest ...))))

(maybe-chain* (something "abad")
              remove-a
              remove-b
              remove-a)
⇒ #<<maybe> is?: #t value: "d">

Congratulations, you've just implemented the bind operation, commonly written as >>=, for our maybe type. And it turns out that a monad is just any container-like value for which >>= (along with another procedure called return, which wraps a given value in the simplest possible form of a monad) has been implemented.

A more formal definition would be that a monad is a mathematical object composed of three parts: a type, a bind function, and a return function. So, how do monads relate to Guix?

New Wheel, Old Wheel

Now that we've reinvented the wheel, we'd better learn to use the original wheel. Guix provides a generic, high-level monads library, along with the two generic monads %identity-monad and %state-monad, and the Guix-specific %store-monad. Since maybe is not one of them, let's integrate our version into the Guix monad system!

First we'll import the module that provides the aforementioned library:

(use-modules (guix monads))

To define a monad's behaviour in Guix, we simply use the define-monad macro, and provide two procedures: bind, and return.

(define-monad %maybe-monad
  (bind maybe-chain)
  (return something))

bind is just the procedure that we use to compose monadic procedure calls together, and return is the procedure that wraps values in the most basic form of the monad. A properly implemented bind and return must follow the so-called monad laws:

1. (bind (return x) proc) must be equivalent to (proc x).
2. (bind monad return) must be equivalent to just monad.
3. (bind (bind monad proc-1) proc-2) must be equivalent to (bind monad (lambda (x) (bind (proc-1 x) proc-2))).

Let's verify that our maybe-chain and something procedures adhere to the monad laws:

(define (mlaws-proc-1 x)
  (something (+ x 1)))

(define (mlaws-proc-2 x)
  (something (+ x 2)))

;; First law: the left identity.
(equal? (maybe-chain (something 0)
                     mlaws-proc-1)
        (mlaws-proc-1 0))
⇒ #t

;; Second law: the right identity.
(equal? (maybe-chain (something 0)
                     something)
        (something 0))
⇒ #t

;; Third law: associativity.
(equal? (maybe-chain (maybe-chain (something 0)
                                  mlaws-proc-1)
                     mlaws-proc-2)
        (maybe-chain (something 0)
                     (lambda (x)
                       (maybe-chain (mlaws-proc-1 x)
                                    mlaws-proc-2))))
⇒ #t

Now that we know they're valid, we can use the with-monad macro to tell Guix to use these specific implementations of bind and return, and the >>= macro to thread monads through procedure calls!

(with-monad %maybe-monad
  (>>= (something "aabbc")
       remove-a
       remove-a
       remove-b
       remove-b))
⇒ #<<maybe> is?: #t value: "c">

We can also now use return:

(with-monad %maybe-monad
  (return 32))
⇒ #<<maybe> is?: #t value: 32>

But Guix provides many higher-level interfaces than >>= and return, as we will see. There's mbegin, which evaluates monadic expressions without binding them to symbols, returning the last one. This, however, isn't particularly useful with our %maybe-monad, as it's only really usable if the monadic operations within have side effects, just like the non-monadic begin.

There's also mlet and mlet*, which do bind the results of monadic expressions to symbols, and are essentially equivalent to a chain of (>>= MEXPR (lambda (BINDING) ...)):

;; This is equivalent...
(mlet* %maybe-monad ((str -> "abad") ;non-monadic binding uses the -> symbol
                     (str1 (remove-a str))
                     (str2 (remove-b str1)))
  (remove-a str2))
⇒ #<<maybe> is?: #t value: "d">

;; ...to this:
(with-monad %maybe-monad
  (>>= (return "abad")
       (lambda (str)
         (remove-a str))
       (lambda (str1)
         (remove-b str1))
       (lambda (str2)
         (remove-a str2))))

Various abstractions over these two exist too, such as mwhen (a when plus an mbegin), munless (an unless plus an mbegin), and mparameterize (dynamically-scoped value rebinding, like parameterize, in a monadic context). lift takes a procedure and a monad and creates a new procedure that returns a monadic value.

There are also interfaces for manipulating lists wrapped in monads; listm creates such a list, sequence turns a list of monads into a list wrapped in a monad, and the anym, mapm, and foldm procedures are like their non-monadic equivalents, except that they return lists wrapped in monads.

This is all well and good, you may be thinking, but why does Guix need a monad library, anyway? The answer is technically that it doesn't. But building on the monad API makes a lot of things much easier, and to learn why, we're going to look at one of Guix's built-in monads.

In a State

Guix implements a monad called %state-monad, and it works with single-argument procedures returning two values. Behold:

(with-monad %state-monad
  (return 33))
⇒ #<procedure 21dc9a0 at <unknown port>:1106:22 (state)>

The run-with-state value turns this procedure into an actually useful value, or, rather, two values:

(run-with-state (with-monad %state-monad (return 33))
  (list "foo" "bar" "baz"))
⇒ 33
⇒ ("foo" "bar" "baz")

What can this actually do for us, though? Well, it gets interesting if we do some >>=ing:

(define state-seq
  (mlet* %state-monad ((number (return 33)))
    (state-push number)))
result
⇒ #<procedure 7fcb6f466960 at <unknown port>:1484:24 (state)>

(run-with-state state-seq (list 32))
⇒ (32)
⇒ (33 32)

(run-with-state state-seq (list 30 99))
⇒ (30 99)
⇒ (33 30 99)

What is state-push? It's a monadic procedure for %state-monad that takes whatever's currently in the first value (the primary value) and pushes it onto the second value (the state value), which is assumed to be a list, returning the old state value as the primary value and the new list as the state value.

So, when we do (run-with-state result (list 32)), we're passing (list 32) as the initial state value, and then the >>= form passes that and 33 to state-push. What %state-monad allows us to do is thread together some procedures that require some kind of state, while essentially pretending the state value is stored globally, like you might do in, say, C, and then retrieve both the final state and the result at the end!

If you're a bit confused, don't worry. We'll write some of our own %state-monad-based monadic procedures and hopefully all will become clear. Consider, for instance, the Fibonacci sequence, in which each value is computed by adding the previous two. We could use the %state-monad to compute Fibonacci numbers by storing the previous number as the primary value and the number before that as the state value:

(define (fibonacci-thing value)
  (lambda (state)
    (values (+ value state)
            value)))

Now we can feed our Fibonacci-generating procedure the first value using run-with-state and the second using return:

(run-with-state
    (mlet* %state-monad ((starting (return 1))
                         (n1 (fibonacci-thing starting))
                         (n2 (fibonacci-thing n1)))
      (fibonacci-thing n2))
  0)
⇒ 3
⇒ 2

(run-with-state
    (mlet* %state-monad ((starting (return 1))
                         (n1 (fibonacci-thing starting))
                         (n2 (fibonacci-thing n1))
                         (n3 (fibonacci-thing n2))
                         (n4 (fibonacci-thing n3))
                         (n5 (fibonacci-thing n4)))
      (fibonacci-thing n5))
  0)
⇒ 13
⇒ 8

This is all very nifty, and possibly useful in general, but what does this have to do with Guix? Well, many Guix store-based operations are meant to be used in concert with yet another monad, called the %store-monad. But if we look at (guix store), where %store-monad is defined...

(define-alias %store-monad %state-monad)
(define-alias store-return state-return)
(define-alias store-bind state-bind)

It was all a shallow façade! All the "store monad" is is a special case of the state monad, where a value representing the store is passed as the state value.

Lies, Damned Lies, and Abstractions

We mentioned that, technically, we didn't need monads for Guix. Indeed, many (now deprecated) procedures take a store value as the argument, such as build-expression->derivation. However, monads are far more elegant and simplify store code by quite a bit.

build-expression->derivation, being deprecated, should never of course be used. For one thing, it uses the "quoted build expression" style, rather than G-expressions (we'll discuss gexps another time). The best way to create a derivation from some basic build code is to use the new-fangled gexp->derivation procedure:

(use-modules (guix gexp)
             (gnu packages irc))

(define symlink-irssi
  (gexp->derivation "link-to-irssi"
    #~(symlink #$(file-append irssi "/bin/irssi") #$output)))
⇒ #<procedure 7fddcc7b81e0 at guix/gexp.scm:1180:2 (state)>

You don't have to understand the #~(...) form yet, only everything surrounding it. We can see that this gexp->derivation returns a procedure taking the initial state (store), just like our %state-monad procedures did, and like we used run-with-state to pass the initial state to a %state-monad monadic value, we use our old friend run-with-store when we have a %store-monad monadic value!

(define symlink-irssi-drv
  (with-store store
    (run-with-store store
      symlink-irssi)))
⇒ #<derivation /gnu/store/q7kwwl4z6psifnv4di1p1kpvlx06fmyq-link-to-irssi.drv => /gnu/store/6a94niigx4ii0ldjdy33wx9anhifr25x-link-to-irssi 7fddb7ef52d0>

Let's just check this derivation is as expected by reading the code from the builder script.

(define symlink-irssi-builder
  (list-ref (derivation-builder-arguments symlink-irssi-drv) 1))

(call-with-input-file symlink-irssi-builder
  (lambda (port)
    (read port)))

⇒ (symlink
   "/gnu/store/hrlmypx1lrdjlxpkqy88bfrzg5p0bn6d-irssi-1.4.3/bin/irssi"
   ((@ (guile) getenv) "out"))

And indeed, it symlinks the irssi binary to the output path. Some other, higher-level, monadic procedures include interned-file, which copies a file from outside the store into it, and text-file, which copies some text into it. Generally, these procedures aren't used, as there are higher-level procedures that perform similar functions (which we will discuss later), but for the sake of this blog post, here's an example:

(with-store store
  (run-with-store store
    (text-file "unmatched-paren"
      "( <paren@disroot.org>")))
⇒ "/gnu/store/v6smacxvdk4yvaa3s3wmd54lixn1dp3y-unmatched-paren"

Conclusion

What have we learned about monads? The key points we can take away are:

1. Monads are a way of composing together procedures and values that are wrapped in containers that give them extra context, like maybe values.
2. Guix provides a high-level monad library that compensates for Guile's lack of static typing or an interface-like system.
3. The (guix monads) module provides the state monad, which allows you to thread state through procedures, allowing you to essentially pretend it's a global variable that's modified by each procedure.
4. Guix uses the store monad frequently to thread a store connection through procedures that need it.
5. The store monad is really just the state monad in disguise, where the state value is used to thread the store object through monadic procedures.

If you've read this post in its entirety but still don't yet quite get it, don't worry. Try to modify and tinker about with the examples, and ask any questions on the IRC channel #guix:libera.chat and mailing list at help-guix@gnu.org, and hopefully it will all click eventually!

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, AArch64 and POWER9 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.