unofficial mirror of guix-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Templates for monadic procedures
@ 2017-05-02 22:03 Ludovic Courtès
  2017-05-03  6:25 ` Ricardo Wurmus
  0 siblings, 1 reply; 3+ messages in thread
From: Ludovic Courtès @ 2017-05-02 22:03 UTC (permalink / raw)
  To: guix-devel

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

^ permalink raw reply	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2017-05-03 10:16 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-05-02 22:03 Templates for monadic procedures Ludovic Courtès
2017-05-03  6:25 ` Ricardo Wurmus
2017-05-03 10:16   ` Ludovic Courtès

Code repositories for project(s) associated with this public inbox

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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).