all messages for Guix-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: "\( via Guix-patches" via <guix-patches@gnu.org>
To: 61214@debbugs.gnu.org
Cc: "\(" <paren@disroot.org>
Subject: [bug#61214] [PATCH guix-artwork v3] website: posts: Add Dissecting Guix, Part 2: The Store Monad.
Date: Fri,  3 Feb 2023 07:36:24 +0000	[thread overview]
Message-ID: <20230203073624.2338-1-paren@disroot.org> (raw)
In-Reply-To: <20230201172821.3072-1-paren@disroot.org>

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

Here's a v3.

* Make purpose of `run-with-store` versus `run-with-state` clearer.

  -- (

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

diff --git a/website/posts/dissecting-guix-2-store-monad.md b/website/posts/dissecting-guix-2-store-monad.md
new file mode 100644
index 0000000..a27a28b
--- /dev/null
+++ b/website/posts/dissecting-guix-2-store-monad.md
@@ -0,0 +1,557 @@
+title: Dissecting Guix, Part 2: The Store Monad
+date: TBC
+author: (
+tags: Dissecting Guix, Functional package management, Programming interfaces, Scheme API
+---
+Hello again!
+
+In [the last post](https://guix.gnu.org/en/blog/2023/dissecting-guix-part-1-derivations/),
+we briefly mentioned the `with-store` and `run-with-store` APIs.  Today, we'll
+be looking at those in further detail, along with the related monad API and the
+`%store-monad`!
+
+Monads are a little hard to explain, and from a distance, they seem more than a
+bit confusing.  So, I want you to erase monads from your mind for now.  We'll
+come back to them later.
+
+# Yes, No, Maybe So
+
+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 dynamically typed, so we
+usually use ad-hoc `#f`s and `'()`s for null values instead of a proper
+"optional" value.
+
+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:
+
+```scheme
+(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`.
+
+```scheme
+(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:
+
+```scheme
+(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:
+
+```scheme
+(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.
+
+```scheme
+(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:
+
+```scheme
+(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 `maybe`s:
+
+```scheme
+(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`.
+
+```scheme
+(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 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.
+
+```scheme
+(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:
+
+```scheme
+(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 API, 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 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))
+```
+
+`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 these
+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:
+
+```scheme
+(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!
+
+```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 are essentially
+equivalent to a chain of `(>>= MEXPR (lambda (BINDING) ...))`:
+
+```scheme
+;; This is equivalent...
+(mlet* %maybe-monad ((str -> "abad") ;non-monadic binding uses the -> symbol
+                     (str1 (remove-a str))
+                     (str2 (remove-b str)))
+  (remove-a str))
+;; #<<maybe> is?: #t value: "d">
+
+;; ...to this:
+(with-monad %maybe-monad
+  (>>= (return "abad")
+       (lambda (str)
+         (remove-a str))
+       (lambda (str1)
+         (remove-b str))
+       (lambda (str2)
+         (remove-a str))))
+```
+
+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 APIs 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
+API?  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:
+
+```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:
+
+```scheme
+(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 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.
+Consider, for instance, the
+[Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number), 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:
+
+```scheme
+(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`:
+
+```scheme
+(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...
+
+```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, such as
+`build-expression->derivation`.  However, using monads both helps ensure purity
+and simply looks nicer.
+
+`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:
+
+```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)>
+```
+
+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!
+
+```scheme
+(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.
+
+```scheme
+(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:
+
+```scheme
+(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 API that compensates for Guile's lack of
+   strong types or an interface-like system.
+3. This API provides the state monad, which allows you to thread state through
+   procedures such that you can pretend it doesn't exist.
+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 hopefully it will
+all click eventually!
+
+#### About GNU Guix
+
+[GNU Guix](https://guix.gnu.org) is a transactional package manager and
+an advanced distribution of the GNU system that [respects user
+freedom](https://www.gnu.org/distros/free-system-distribution-guidelines.html).
+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](https://www.gnu.org/software/guile)
+programming interfaces and extensions to the
+[Scheme](http://schemers.org) language.

base-commit: fe113595b6f7d8a1e1a0b814521f02783f9209c3
-- 
2.39.1





  parent reply	other threads:[~2023-02-03  7:37 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-02-01 17:28 [bug#61214] [PATCH guix-artwork] website: posts: Add Dissecting Guix, Part 2: The Store Monad ( via Guix-patches via
2023-02-02  8:17 ` Simon Tournier
2023-02-02 13:06   ` ( via Guix-patches via
2023-02-02 15:00 ` [bug#61214] [PATCH guix-artwork v2] " ( via Guix-patches via
2023-02-02 15:04   ` ( via Guix-patches via
2023-02-06 15:38   ` Simon Tournier
2023-02-03  1:55 ` [bug#61214] run-with-state and run-with-store Feng Shu
2023-02-03  5:31   ` [bug#61214] [PATCH guix-artwork] website: posts: Add Dissecting Guix, Part 2: The Store Monad 宋文武 via Guix-patches via
2023-02-03  6:35   ` [bug#61214] run-with-state and run-with-store ( via Guix-patches via
2023-02-03  7:36 ` ( via Guix-patches via [this message]
2023-02-12 10:47   ` [bug#61214] [PATCH guix-artwork v3] website: posts: Add Dissecting Guix, Part 2: The Store Monad Christopher Baines
2023-02-12 14:17     ` ( via Guix-patches via
2023-02-13 12:08     ` zimoun
2023-02-12 18:05   ` [bug#61214] [PATCH guix-artwork] " Ludovic Courtès
2023-02-12 20:38     ` ( via Guix-patches via
2023-02-14  7:30 ` [bug#61214] [PATCH guix-artwork v4] " ( via Guix-patches via
2023-02-14  7:33 ` [bug#61214] [PATCH guix-artwork v5] " ( via Guix-patches via
2023-02-14 18:01   ` Simon Tournier
2023-02-14 19:26     ` ( via Guix-patches via
2023-02-16 17:00 ` [bug#61214] [PATCH guix-artwork v6] " ( via Guix-patches via
2023-02-20 21:23   ` Tobias Geerinckx-Rice via Guix-patches via
2023-02-20 22:04     ` ( via Guix-patches via

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20230203073624.2338-1-paren@disroot.org \
    --to=guix-patches@gnu.org \
    --cc=61214@debbugs.gnu.org \
    --cc=paren@disroot.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/guix.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.