The store monad

The store monad

[Ludovic Courtès]

Hi!

I just pushed the ‘wip-monad’ branch for review (like we do in Guile,
‘wip-’ means that I may rebase it until it’s complete.)

So far in Guix we had two things: store primitives from (guix store)
that explicitly manipulate the store via effectful RPCs, and package
definitions, which are abstract, inert, and never see a store object.

Package objects are great, but they’re not necessarily suitable for
small derivations like the many we have in (gnu system …) modules.  Yet,
it would be nicer if functions in those modules did not have to
explicitly carry a ‘store’ parameter, and if the sequence of store
operations could be built and hidden under the carpet.

This is where monads come in.  In addition to being fashionable in FP
circles ;-), they offer a nice way to do exactly that: to add context to
values (here, the context is the store), and to build sequences of
computations.

So now, instead of writing procedures that explicitly manipulate the
store:

  (define (foo store)
    (let* ((drv (package-derivation store bash))
           (out (derivation->output-path drv)))
      (add-text-to-store store "foo.sh" (format #f "#!~a/bin/sh
echo hello world" out))))

  ;; Call the function:
  (foo (open-connection))

we can now write a monadic function:

  (define (foo)
    (mlet the-store-monad ((sh (package-file bash "bin/sh")))
      (text-file "foo.sh"
                 (string-append "#!" sh "\necho hello world"))))

  ;; Call the monadic function, and “run” its monadic result:
  ((foo) (open-connection))

Notice how ‘store’ completely disappeared.  Here we use ‘mlet’, not
‘let’, because ‘package-file’ returns a “monadic value” instead of a
normal value.

Monadic values in the store monad are currently just (lambda (store) …).

That’s the first time I use monads after just reading about it.  This
was mostly inspired by
<http://okmij.org/ftp/Scheme/monad-in-Scheme.html> and
<http://planet.racket-lang.org/package-source/toups/functional.plt/1/1/planet-docs/better-monads-guide/index.html>.
A good introduction is at <http://learnyouahaskell.com/a-fistful-of-monads>.

Actually, values in the Nix programming language essentially live in the
store monad, even if that’s not what it’s called.

I plan to polish it, add tests, and merge it in the coming days or so.

Comments welcome!

Thanks,
Ludo’.

Re: The store monad

[Nikita Karetnikov]

[-- Attachment #1: Type: text/plain, Size: 341 bytes --]

Thanks, this is definitely a step in the right direction.

> That’s the first time I use monads after just reading about it.

I hope that you checked the monad laws.

> <http://okmij.org/ftp/Scheme/monad-in-Scheme.html>

Thanks for sharing, I haven’t seen this one.  I’ll check your
implementation when I finish the article.

[-- Attachment #2: Type: application/pgp-signature, Size: 835 bytes --]

Re: The store monad

[Ludovic Courtès]

Nikita Karetnikov <nikita@karetnikov.org> skribis:

> Thanks, this is definitely a step in the right direction.
>
>> That’s the first time I use monads after just reading about it.
>
> I hope that you checked the monad laws.

Left identity:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> ,use(guix monads)
scheme@(guile-user)> (store-bind (store-return 2) (lambda (x) (store-return (pk 'x x))))
$1 = #<procedure 272e600 at guix/monads.scm:209:2 (store)>
scheme@(guile-user)> ($1 #f)

;;; (x 2)
$2 = 2
--8<---------------cut here---------------end--------------->8---

Right identity:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> (store-bind (store-return 2) store-return)
$3 = #<procedure 26d8960 at guix/monads.scm:209:2 (store)>
scheme@(guile-user)> ($3 #f)
$4 = 2
--8<---------------cut here---------------end--------------->8---

Associativity:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> (define (f x) (store-return (+ 1 x)))
scheme@(guile-user)> (define (g x) (store-return (* 2 x)))
scheme@(guile-user)> (store-bind (store-bind (store-return 0) f) g)
$5 = #<procedure 2766210 at guix/monads.scm:209:2 (store)>
scheme@(guile-user)> ($5 #f)
$6 = 2
scheme@(guile-user)> (store-bind (store-return 0) (lambda (x) (store-bind (f x) g)))
$7 = #<procedure 283a9c0 at guix/monads.scm:209:2 (store)>
scheme@(guile-user)> ($7 #t)
$8 = 2
--8<---------------cut here---------------end--------------->8---

Seems to be lawful and everything.  ;-)

I’ll add that to the tests.

Thanks,
Ludo’.

Re: The store monad

[Ludovic Courtès]

Today’s monadic news is that monads are “inlined”.  Before, something like:

  (mlet %store-monad ((x y))
    (return (+ 1 y)))

would expand to:

  ((struct-ref %store-monad 0) y
    (lambda (x)
      ((struct-ref %store-monad 1) x)))

With inlining, the above doesn’t expand to references to the
‘%store-monad’ record, and instead directly expands to:

  (store-bind y (lambda (x) (store-return (+ 1 x))))

If in addition ‘store-bind’ and ‘store-return’ are defined with
‘define-inlinable’, then the whole shebang is inlined, allowing for
better optimizations:

--8<---------------cut here---------------start------------->8---
scheme@(guix monads)> ,expand (with-monad %identity-monad (>>= (return 2) (lambda (x) (return (1+ x)))))
$17 = (let ((mvalue (let ((value 2)) value))
      (mproc (lambda (x) (let ((value (#{1+}# x))) value))))
  (mproc mvalue))
scheme@(guix monads)> ,optimize (with-monad %identity-monad (>>= (return 2) (lambda (x) (return (1+ x)))))
$18 = 3
scheme@(guix monads)> ,optimize (mlet* %identity-monad ((x (return 1))(y (return 2))(z (return (+ x y)))) z)
$19 = 3

[...]

scheme@(guix monads)> ,optimize (mlet* %store-monad ((x (return 1))(y (return 2))(z (return (+ x y)))) (return z))
$22 = (lambda (store) (let mresult ((store store)) 3))
--8<---------------cut here---------------end--------------->8---

This significantly reduces the cost of using bind/return all over the
place.

Ludo’.

Re: The store monad

[Ludovic Courtès]

ludo@gnu.org (Ludovic Courtès) skribis:

> I just pushed the ‘wip-monad’ branch for review (like we do in Guile,
> ‘wip-’ means that I may rebase it until it’s complete.)

Merged and pushed, along with some doc.

Ludo’.