Templates for monadic procedures

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’.

Re: Templates for monadic procedures

[Ricardo Wurmus]

Ludovic Courtès <ludo@gnu.org> writes:

> 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:
[…]
> 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!

Wow!  That’s very cool!  I previously played with my own monads in Guile
for a toy project and it bothered me that too many lookup happened at
runtime.  Having a lookup directory at expansion time is really neat,
though I must say that this higher level macrology would be very hard
for me to come up with from scratch!

I wonder if we could also do monad type checking at expansion or compile
time.  That’s the last thing that’s missing here.

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

Yay, super cool!  I’m looking forward to seeing that branch merged!

--
Ricardo

GPG: BCA6 89B6 3655 3801 C3C6  2150 197A 5888 235F ACAC
https://elephly.net

Re: Templates for monadic procedures

[Ludovic Courtès]

Ricardo Wurmus <rekado@elephly.net> skribis:

> Ludovic Courtès <ludo@gnu.org> writes:
>
>> 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:
> […]
>> 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!
>
> Wow!  That’s very cool!  I previously played with my own monads in Guile
> for a toy project and it bothered me that too many lookup happened at
> runtime.  Having a lookup directory at expansion time is really neat,
> though I must say that this higher level macrology would be very hard
> for me to come up with from scratch!
>
> I wonder if we could also do monad type checking at expansion or compile
> time.  That’s the last thing that’s missing here.

At this point we can distinguish between “definitely a monad” and “don’t
know” for the first argument of ‘mlet’ and the templated procedures.
That’s a start.  ;-)

I really want to look at Turnstile, which uses macrology to introduce
some typing:

  https://docs.racket-lang.org/turnstile/The_Turnstile_Guide.html

Ludo’.