Templates for monadic procedures

[Ludovic Courtès]

Hello Guix!

In a previous episode, (guix monads) was hacked so that we could inline
a monad’s ‘return’ and ‘bind’ operation in forms such as:

  (mlet %state-monad ((x (do-something)))
    (return (+ x 42)))

See <https://lists.gnu.org/archive/html/guix-devel/2013-10/msg00034.html>.

There was still a common case where inlining could not take place, and
that was when defining monadic procedures like:

  (define (mapm monad proc lst)
    …)

Here, when ‘mapm’ is compiled, we know nothing about ‘monad’, and thus
we fall in the worst-case scenario: instead of inling the bind and
return procedures of ‘monad’, we have to assume that monad is a struct
and do a ‘struct-ref’ to get its bind and return.  Not great, especially
since those ‘struct-ref’ occur in the middle of the ‘mapm’ loop.

So, 
<https://git.savannah.gnu.org/cgit/guix.git/commit/?id=dcb95c1fc936d74dfdf84b7e59eff66cb99c5a63>
adds a C++-inspired template mechanism to (guix monads).  Now we can
write:

  (define-template (mapm monad proc lst)
    …)

That automatically leads to the definition of both a generic version
(same one as before, inefficient) as well as one specialized version for
each monad that is defined.  Each specialized version is more efficient
because the monad it is specialized for is known at expansion-time, and
thus we can inline the monad’s bind/return:

--8<---------------cut here---------------start------------->8---
scheme@(guix monads)> ,optimize (template-directory instantiations 
%identity-monad)
$2 = (begin
  (define (#{ mapm %identity-monad instance}# mproc lst)
    "Map MPROC over LST and return a monadic list.\n\n  (mapm %state-monad 
(lift1 1+ %state-monad) '(0 1 2))\n  => (1 2 3)  ;monadic\n"
    (let mapm ((lst lst) (result '()))
      (cond ((null? lst) (reverse result))
            ((pair? lst)
             (let ((w (car lst)) (x (cdr lst)))
               (let ((mvalue (mproc w)))
                 (mapm x (cons mvalue result)))))
            (else
             ((@@ (ice-9 match) error)
              'match
              "no matching pattern"
              lst)
             #f))))
  (register-template-instance!
    #<syntax mapm>
    #<syntax %identity-monad>
    #<syntax #{ mapm %identity-monad instance}#>)
  (define (#{ sequence %identity-monad instance}# lst)

    [...]
--8<---------------cut here---------------end--------------->8---

Here we see the specialization of ‘mapm’ for ‘%identity-monad’.  Its
bind/return operations are properly inlined and there’s no
‘struct-ref’.  For comparison, the generic version of ‘mapm’ looks like
this:

--8<---------------cut here---------------start------------->8---
  (define (#{ %mapm-generic}# monad mproc lst)
    "Map MPROC over LST and return a monadic list.\n\n  (mapm %state-monad 
(lift1 1+ %state-monad) '(0 1 2))\n  => (1 2 3)  ;monadic\n"
    (let mapm ((lst lst) (result '()))
      (cond ((null? lst)
             ((if (eq? (struct-vtable monad) <monad>)
                (struct-ref monad 1)
                (throw 'wrong-type-arg
                       'monad-return
                       "Wrong type argument: ~S"
                       (list monad)
                       (list monad)))
              (reverse result)))
            ((pair? lst)
             (let ((w (car lst)) (x (cdr lst)))
               ((if (eq? (struct-vtable monad) <monad>)
                  (struct-ref monad 0)
                  (throw 'wrong-type-arg
                         'monad-bind
                         "Wrong type argument: ~S"
                         (list monad)
                         (list monad)))
                (mproc w)
                (lambda (head) (mapm x (cons head result))))))
            (else
             ((@@ (ice-9 match) error)
              'match
              "no matching pattern"
              lst)
             #f))))
--8<---------------cut here---------------end--------------->8---

Boooh!

Once we have those template instances, we need to pick the right one at
call sites:

--8<---------------cut here---------------start------------->8---
scheme@(guix monads)> ,optimize (mapm %identity-monad 1+ '(0 1 2))
$4 = (#{ mapm %identity-monad instance}#
  #{1+}#
  '(0 1 2))
scheme@(guix monads)> ,optimize (mapm some-unknown-monad 1+ '(0 1 2))
#f:24:10: warning: no specialization of template 'mapm' for 'some-unknown-monad'
$5 = (#{ %mapm-generic}#
  some-unknown-monad
  #{1+}#
  '(0 1 2))
scheme@(guix monads)> ,optimize (mapm %state-monad 1+ '(0 1 2))
$6 = (#{ mapm %state-monad instance}# #{1+}# '(0 1 2))
--8<---------------cut here---------------end--------------->8---

All this relies on a “stateful macro” that keeps state across the
expansion-time and run-time stages.  I think it’s a pretty fun hack!

Currently it doesn’t have a noticeable performance impact because monads
are used sparsely, but I expect it will help with the
‘wip-build-systems-gexp’ branch, which aims to use gexps (and thus
‘%store-monad’) for packages.

Feedback welcome!  :-)

Ludo’.