From patchwork Tue Feb 14 07:33:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "\\(" X-Patchwork-Id: 46943 Return-Path: X-Original-To: patchwork@mira.cbaines.net Delivered-To: patchwork@mira.cbaines.net Received: by mira.cbaines.net (Postfix, from userid 113) id 47F4A167F4; Tue, 14 Feb 2023 07:34:21 +0000 (GMT) X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on mira.cbaines.net X-Spam-Level: X-Spam-Status: No, score=-3.7 required=5.0 tests=BAYES_00,DKIM_INVALID, DKIM_SIGNED,MAILING_LIST_MULTI,RCVD_IN_MSPIKE_H2,SPF_HELO_PASS, URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.6 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mira.cbaines.net (Postfix) with ESMTPS id 2D56E167D0 for ; Tue, 14 Feb 2023 07:34:19 +0000 (GMT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pRppE-0006lv-K9; Tue, 14 Feb 2023 02:34:04 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pRppD-0006lm-0N for guix-patches@gnu.org; Tue, 14 Feb 2023 02:34:03 -0500 Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pRppC-0002DB-LG for guix-patches@gnu.org; Tue, 14 Feb 2023 02:34:02 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1pRppC-00059C-7b for guix-patches@gnu.org; Tue, 14 Feb 2023 02:34:02 -0500 X-Loop: help-debbugs@gnu.org Subject: [bug#61214] [PATCH guix-artwork v5] website: posts: Add Dissecting Guix, Part 2: The Store Monad. References: <20230201172821.3072-1-paren@disroot.org> In-Reply-To: <20230201172821.3072-1-paren@disroot.org> Resent-From: "(" Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Tue, 14 Feb 2023 07:34:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 61214 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: 61214@debbugs.gnu.org Cc: "\(" , ludo@gnu.org, mail@cbaines.net, zimoun.toutoune@gmail.com Received: via spool by 61214-submit@debbugs.gnu.org id=B61214.167636000219731 (code B ref 61214); Tue, 14 Feb 2023 07:34:02 +0000 Received: (at 61214) by debbugs.gnu.org; 14 Feb 2023 07:33:22 +0000 Received: from localhost ([127.0.0.1]:52383 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pRpoX-000587-DW for submit@debbugs.gnu.org; Tue, 14 Feb 2023 02:33:22 -0500 Received: from knopi.disroot.org ([178.21.23.139]:41894) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pRpoU-00057y-Lg for 61214@debbugs.gnu.org; Tue, 14 Feb 2023 02:33:20 -0500 Received: from localhost (localhost [127.0.0.1]) by disroot.org (Postfix) with ESMTP id 07C6241418; Tue, 14 Feb 2023 08:33:18 +0100 (CET) X-Virus-Scanned: SPAM Filter at disroot.org Received: from knopi.disroot.org ([127.0.0.1]) by localhost (disroot.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id fCGDs_iP1WQp; Tue, 14 Feb 2023 08:33:15 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1676359995; bh=UuvrXN6TQHN26F0BxgbM5Kng7G/8TEItJb8hCtw2cu8=; h=From:To:Cc:Subject:Date; b=KPEmLXz81sQEz+kBqG3vASKetmimefbufkbpsoNF+UY4kn8QYIBXUwD9Yu8uUGiH+ YDoZXdVBualQE/hbSwxYtBX67Q0GlXTBTnklbEHXDeyLutseKOwE9y30JjEzBL10Ql +de/qsP9pvXtswvxLfYMEcLjj6IZ5LHcg+tFPENt5tZ/gdkziKK2YUfKk3u/8xf3o4 89AjgTDzNK/xiwRUg6MqMINgJsc7nuEvyLVJaIaOGe9zmP+VBAX6HrSnB8Mi4bxYDQ 8UMsJIp8kkZkcfwLcAVUdMwhsZMbvFacRlHS22OV19hSOMnpEQ6JC7YnemnuZm4elD 6eNeAXg2Lc4yw== Date: Tue, 14 Feb 2023 07:33:14 +0000 Message-Id: <20230214073314.2651-1-paren@disroot.org> MIME-Version: 1.0 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-to: "\(" X-ACL-Warn: , "\( via Guix-patches" X-Patchwork-Original-From: "\( via Guix-patches" via From: "\\(" Errors-To: guix-patches-bounces+patchwork=mira.cbaines.net@gnu.org Sender: guix-patches-bounces+patchwork=mira.cbaines.net@gnu.org X-getmail-retrieved-from-mailbox: Patches * website/posts/dissecting-guix-2-store-monad.md: New blog post. --- Oops, forgot to ``git commit -a''... :/ See v4 for the changelog. .../posts/dissecting-guix-2-store-monad.md | 567 ++++++++++++++++++ 1 file changed, 567 insertions(+) create mode 100644 website/posts/dissecting-guix-2-store-monad.md base-commit: fe113595b6f7d8a1e1a0b814521f02783f9209c3 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..13b9cbb --- /dev/null +++ b/website/posts/dissecting-guix-2-store-monad.md @@ -0,0 +1,567 @@ +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` macros. Today, we'll +be looking at those in further detail, along with the related monad library and +the [`%store-monad`](https://guix.gnu.org/manual/devel/en/html_node/The-Store-Monad.html)! + +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, returing 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: + +```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 + (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") +⇒ #< is?: #t value: "hh"> + +(remove-a "ooh") +⇒ #< is?: #f value: #f> + +(remove-b "bad") +⇒ #< 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))) +⇒ #< is?: #t value: "cd"> + +(let ((t1 (remove-a "bbcd"))) + (if (maybe-is? t1) + (remove-b (maybe-value t1)) + (nothing))) +⇒ #< 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))) +⇒ #< 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 + (($ #t str) + (if (eq? (string-ref str 0) #\a) + (something (substring str 1)) + (nothing))) + (_ (nothing)))) + +(define (remove-b ?str) + (match ?str + (($ #t str) + (if (eq? (string-ref str 0) #\b) + (something (substring str 1)) + (nothing))) + (_ (nothing)))) +``` + +Not at all pretty, but it works! + +```scheme +(remove-b (remove-a (something "abc"))) +⇒ #< 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) +⇒ #< is?: #t value: "bc"> + +(maybe-chain (nothing) + remove-a) +⇒ #< 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) +⇒ #< 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: + +```scheme +(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`. + +```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 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: + +```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)) +⇒ #< is?: #t value: "c"> +``` + +We can also now use `return`: + +```scheme +(with-monad %maybe-monad + (return 32)) +⇒ #< 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) ...))`: + +```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)) +⇒ #< 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 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: + +```scheme +(with-monad %state-monad + (return 33)) +⇒ #: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 +⇒ #: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](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, 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: + +```scheme +(use-modules (guix gexp) + (gnu packages irc)) + +(define symlink-irssi + (gexp->derivation "link-to-irssi" + #~(symlink #$(file-append irssi "/bin/irssi") #$output))) +⇒ # +``` + +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))) +⇒ # /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" + "( "))) +⇒ "/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](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.