[bug#61214,guix-artwork] website: posts: Add Dissecting Guix, Part 2: The Store Monad.

* website/posts/dissecting-guix-2-store-monad.md: New blog post.
---
Heya Guix!

At long last, the second Dissecting Guix is complete :)

This one is about monads, the Guix monad API, and the %STORE-MONAD.  Hopefully
it's not too confusing, but if you find it hard to follow, please let me know!

  -- (

 .../posts/dissecting-guix-2-store-monad.md    | 498 ++++++++++++++++++
 1 file changed, 498 insertions(+)
 create mode 100644 website/posts/dissecting-guix-2-store-monad.md


base-commit: fe113595b6f7d8a1e1a0b814521f02783f9209c3

Hi,

Nice!  Some minor comments which can be trashed if they are not
helpful. :-)


On Wed, 01 Feb 2023 at 17:28, "\( via Guix-patches" via <guix-patches@gnu.org> wrote:

> +Let's instead implement another M of functional programming, _`maybe`_ values,
> +representing a value that may or may not exist.  `maybe` is a very common
> +feature of strongly-typed functional languages, and you'll see it all over the
> +place in Haskell and OCaml code. However, Guile is not strongly typed, so we

I would say “Guile is dynamically typed“ or “is not statically typed”
instead of “is not strongly typed”.  Because the terminology “strongly
typed” is probably confusing, for instance, quoting Wikipedia [1]:

        Smalltalk, Ruby, Python, and Self are all "strongly typed" in
        the sense that …

        The Lisp family of languages are all "strongly typed" in the
        sense that …

        Standard ML, F#, OCaml, Haskell, Go and Rust are statically
        type-checked, …

1: <https://en.wikipedia.org/wiki/Strong_and_weak_typing>

> +(define (nothing)
> +  (make-maybe #f #f))
> +```

Here, I would mention that the value ‘#f‘ is picked but anything else
would also work as 'nothing.  Well, to make the distinction with the
previous part about #f or () for null values, I would use the symbol
'no-value or something like that.  In all cases, I would mention that
this #f is just useless.


> +(define (remove-a ?str)
> +  (if (maybe-is? ?str)
> +      (let ((str (maybe-value ?str)))
> +        (if (eq? (string-ref str 0) #\a)
> +            (something (substring str 1))
> +            (nothing)))
> +      (nothing)))

Well, my personal preference would be a ’match’ instead of ’let’. :-)

Maybe, it is for smoothly introducing mlet? :-)


> +Congratulations, you've reinvented `bind`, commonly written as the `>>=`
> +operator.  And it turns out that a monadic type is just a container type that
> +can be used with `>>=`!

From my experience, what is often confusing for newcomer with “monadic
notation“ is that ’bind’ (>>=) appears magic since it is the same symbol
for all the types.  When it is attached to one type; here ‘maybe‘.

Well, for what it is worth, it is the same kind of issue when one
presents well-known arithmetic operators.  At first, it is confusing
that the symbol + in 1+2 and 1.2+3.4 does not have the same meaning and
e.g. 1+2.3 is a third meaning.

Well, I would write: ”Congratulations, you've implemented `bind` for the
record `maybe`.  It is commonly denoted as the `>>=` operator.  And it
turns out that a monadic type is just a container type that can be used
with this `>>=` operator defined for such type!“


> +# 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 API, along with three monads,
> +though `maybe` is not one of them, so let's integrate it into the Guix monad
> +system!

I think it is confusing because from my point of view, a piece is
missing.  Well, for what it is worth, I would end the previous section
with a rough definition of monad:

 1. one type constructor
 2. one ‘bind‘ operator
 3. one ’return’ function

and that ’bind’ and ’return’ must satisfy the 3 laws of monad.  Using
’maybe’ as example, all is explicit and more or less concrete.  Maybe,
the type constructor could be omitted; without loss in generality.

Therefore, “along with three monads” means that the API already provides
a type constructor, ’bind’ and ’return’ for each.  I would write “along
with the three monads commonly named identity and state monads”.

What is the third? :-)


> +First we'll make the API available:
> +
> +```scheme
> +(use-modules (guix monads))
> +```
> +
> +To define a monad's API in Guix, we simply use the `define-monad` macro, and
> +provide two procedures: `bind`, and `return`.
> +
> +```scheme
> +(define-monad %maybe-monad
> +  (bind maybe-chain)
> +  (return something))
> +```

IMHO, ending the previous section with a short paragraph explaining that
a monad is a mathematical object defined with three/two components
(type, bind and return) makes this define-monad API more meaningful;
again IMHO.

> +`bind` is just the procedure that we use to chain monadic procedure calls

Instead of chain, I would write compose.  Elsewhere too.

> +There are also APIs for manipulating lists wrapped in monads; `mlist` creates

Do you mean ’listm’?

> +such a list, `anym` is a monadic `any`, `sequence` turns a list of monads into a
> +monadic list, `mapm` is a monadic `map`, and `foldm` is a monadic `fold`.

Well, here we are touching the limit of what Scheme can express. :-)
Because for instance, reading,

    (mapm %state-monad (lift1 1+ %state-monad) '(0 1 2))

it does not appear clear to me what monad provides compared to just pass
arguments around. ;-)



> +# In a State
> +
> +Guix implements a monad called `%state-monad`, and it works with single-argument
> +procedures returning two values.  Behold:
> +
> +```scheme
> +(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:
> +
> +```scheme
> +(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:

What appears to me hard to follow is that >>= is not explicitly used in
the following.  See below.

> +
> +```scheme
> +(define state-seq
> +  (mlet* ((number (return 33)))
> +    (state-push number)))

I guess %state-monad is missing in mlet*.

> +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

Well, maybe instead of mlet*, it would ease the reading if state-seq
explicitly uses >>= and mention again that instead it could be written
using mlet*.  It appears to me clearer with the text to have:

        (define state-seq*
         (with-monad %state-monad
           (>>= (return 33)
                state-push)))

Or instead, maybe earlier, something like:

--8<---------------cut here---------------start------------->8---
And there's `mlet` and `mlet*`, which can bind them, and is essentially
equivalent to a chain of `(>>= MEXPR (lambda (BINDING) ...))`.  Other
said,

(with-monad %maybe-monad
 (>>= (return "abad")
      remove-a
      remove-b
      remove-a))

is equivalent to:

(mlet* %maybe-monad ((str -> "abad") ;non-monadic binding uses the -> symbol
                     (str1 (remove-a str))
                     (str2 (remove-b str)))
  (remove-a str))
--8<---------------cut here---------------end--------------->8---

Maybe instead of some unrelated example earlier, I would write:

--8<---------------cut here---------------start------------->8---
Now we can use the `with-monad` macro to tell Guix to use this specific `bind`
and `return`, and the `>>=` macro to thread monads through procedure calls!

```scheme
(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`:

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

But Guix provides many higher-level APIs than `>>=` and `return`, as we will
see.  There's `mbegin`, which evaluates monadic expressions without binding them
to symbols, returning the last one:

```scheme
(mbegin %maybe-monad
  (remove-a "abc"))
;; #<<maybe> is?: #t value: "bc">
```

And there's `mlet` and `mlet*`, which can bind them, and is essentially
equivalent to a chain of `(>>= MEXPR (lambda (BINDING) ...))`,
rewriting the previous example using the operator `>>=`:

```scheme
(mlet* %maybe-monad ((str -> "aabbc") ;non-monadic binding uses the -> symbol
                     (str1 (remove-a str))
                     (str2 (remove-a str1))
                     (str3 (remove-b str2)))                     
  (remove-b str3))
;; #<<maybe> is?: #t value: "c">
```
--8<---------------cut here---------------end--------------->8---


> +`state-push`.  What `%state-monad` allows us to do is thread together some
> +procedures that require some kind of state, while pretending the state isn't
> +there, 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.

I would add something along these lines for some context:

--8<---------------cut here---------------start------------->8---
Consider the (Fibonacci
sequence)[https://en.wikipedia.org/wiki/Fibonacci_number] where the
next value is computed using the previous values.  Let consider one
`state` that stores the previous computed value, for instance,

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

Now, let’s evaluate the three first values of the sequence, starting
with 1 and 0.

(run-with-state
  (with-monad %state-monad
    (>>= (return 1)
         fibonacci-thing
         fibonacci-thing
         fibonacci-thing))
   0)
;; 3
;; 2

Similarly, it is possible to compute the 6th and 7th term of the
sequence (remind the 0th and first are given by 0 and 1), using
equivalently mlet*.

(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
```

The `fibonacci-thing` monadic procedure takes the number passed, makes it the
current state, and outputs the sum of the state and the number passed.  This
gives us a sort of Fibonacci-sequence-like behaviour, where the next number in
the sequence is given by the sum of the two before.
--8<---------------cut here---------------end--------------->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...
> +
> +```scheme
> +(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:

I think it is worth to mention that monad provides the correct framework
to compose in a pure world some impure functions.  The pure world is an
isolated environment but that alone is useless.  What make things useful
is to have inputs from the outside impure world.  All the question is
thus to keep the control of impurity when composing.

Well, this short video [1] is about Haskell but all the arguments apply,
IMHO.  I mean the kind of diagram seems to also make sense here.

1: <https://youtu.be/iSmkqocn0oQ>

> +```scheme
> +(use-modules (guix derivations)
> +             (guix store))
> +
> +(with-store store ;remember this?
> +  (build-expression->derivation store NAME EXPRESSION ...))
> +```
> +
> +This procedure, being deprecated, should never of course be used.  For one
> +thing, it uses the "quoted build expression" style, rather than gexps, which we
> +will discuss another time.  The best way to create a derivation from some basic
> +build code is to use the new-fangled `gexp->derivation` procedure, which happens
> +to be monadic!

This paragraph appears to me confusing because it is not clear what is
deprecated; with-store or build-expression->derivation?

Well, I would drop build-expression->derivation.

Instead, I would use this pattern:

--8<---------------cut here---------------start------------->8---
Consider that we would like to build something and have it in the
store, for instance some text file.  Well, the procedure `text-file`,

(define* (text-file name
                    text ;string
                    #:optional (references '()))
  "Return as a monadic value the absolute file name in the store of the file
containing TEXT, a string.

seems what we want.  Therefore, we want to evaluate this monadic value
in the context of the store, similarly as the previous run-with-state.
`guix repl` provides a nice interface with the command `,run-in-store`:

scheme@(guix-user)> ,run-in-store
   (text-file "unmatched-paren"
      "( <paren@disroot.org>")
$1 = "/gnu/store/v6smacxvdk4yvaa3s3wmd54lixn1dp3y-unmatched-paren"

Unwrapping the machinery, it would reads,

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

where `with-store` acts similarly as `with-monad` and `run-with-store`
similarly as `run-with-state`.  Note the order is reversed because the
store is somehow unique.

Now, consider we want to build a derivation.  Let define one:

```scheme
(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)>
```

Remember that store and state are related.

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 to pass
this initial state, we used `run-with-state`.  The equivalent for working with
the store is our old friend `run-with-store`!

  (with-store store
    (run-with-store store
      symlink-irssi)))
;; #<derivation /gnu/store/q7kwwl4z6psifnv4di1p1kpvlx06fmyq-link-to-irssi.drv => /gnu/store/6a94niigx4ii0ldjdy33wx9anhifr25x-link-to-irssi 7fddb7ef52d0>
--8<---------------cut here---------------end--------------->8---

My 2 cents.

Nice read of an hard topic.  Well done! :-)

Cheers,
simon

Heya,

On Thu Feb 2, 2023 at 8:17 AM GMT, Simon Tournier wrote:
> Nice!  Some minor comments which can be trashed if they are not
> helpful. :-)

You raise some good points; I'll send a v2 in a moment.

> Nice read of an hard topic.  Well done! :-)

Thank you! :)

    -- (

> And to pass this initial state, we used `run-with-state`.  The equivalent for working with
> the store is our old friend `run-with-store`!

For my poor English, I do not understand this well, does this mean
"run-with-store will call run-with-state, we just use run-with-store
generally." or "run-with-store is similer with run-with-state, they can
replace each other"?



--

Feng Shu <tumashu@163.com> writes:

>> And to pass this initial state, we used `run-with-state`.  The equivalent for working with
>> the store is our old friend `run-with-store`!
>
> For my poor English, I do not understand this well, does this mean
> "run-with-store will call run-with-state, we just use run-with-store
> generally." or "run-with-store is similer with run-with-state, they can
> replace each other"?

Well, "The equivalent for working with the store ..." should read as
"And to pass this initial store, we should use `run-with-store`".

> We can see that this `gexp->derivation` returns a procedure taking the
> initial state (store), just like our `%state-monad` procedures did.
> And to pass this initial state, we used `run-with-state`.

Maybe "And to pass the initial state for `%state-monad`, we used
`run-with-state`.  So to pass the initial for `%store-monad`, we will
use `run-with-store`!" is better?

Heya,

On Fri Feb 3, 2023 at 1:55 AM GMT, Feng Shu wrote:
> For my poor English, I do not understand this well, does this mean
> "run-with-store will call run-with-state, we just use run-with-store
> generally." or "run-with-store is similer with run-with-state, they can
> replace each other"?

Oops :) It's supposed to mean something like:

> Just like we use `run-with-state` to pass an initial state to a monadic
> value that uses `%state-monad`, we use our old friend `run-with-store`
> when the value uses the `%store-monad`.

Since it's unclear at present, I'll change it in a moment.

    -- (