guix/monads.scm

   1 ;;; GNU Guix --- Functional package management for GNU
   2 ;;; Copyright © 2013, 2014, 2015 Ludovic Courtès <ludo@gnu.org>
   3 ;;;
   4 ;;; This file is part of GNU Guix.
   5 ;;;
   6 ;;; GNU Guix is free software; you can redistribute it and/or modify it
   7 ;;; under the terms of the GNU General Public License as published by
   8 ;;; the Free Software Foundation; either version 3 of the License, or (at
   9 ;;; your option) any later version.
  10 ;;;
  11 ;;; GNU Guix is distributed in the hope that it will be useful, but
  12 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 ;;; GNU General Public License for more details.
  15 ;;;
  16 ;;; You should have received a copy of the GNU General Public License
  17 ;;; along with GNU Guix.  If not, see <http://www.gnu.org/licenses/>.
  18
  19 (define-module (guix monads)
  20   #:use-module ((system syntax)
  21                 #:select (syntax-local-binding))
  22   #:use-module (ice-9 match)
  23   #:use-module (srfi srfi-1)
  24   #:use-module (srfi srfi-9)
  25   #:use-module (srfi srfi-26)
  26   #:export (;; Monads.
  27             define-monad
  28             monad?
  29             monad-bind
  30             monad-return
  31
  32             ;; Syntax.
  33             >>=
  34             return
  35             with-monad
  36             mlet
  37             mlet*
  38             mbegin
  39             mwhen
  40             munless
  41             lift0 lift1 lift2 lift3 lift4 lift5 lift6 lift7 lift
  42             listm
  43             foldm
  44             mapm
  45             sequence
  46             anym
  47
  48             ;; Concrete monads.
  49             %identity-monad
  50
  51             %state-monad
  52             state-return
  53             state-bind
  54             current-state
  55             set-current-state
  56             state-push
  57             state-pop
  58             run-with-state))
  59
  60 ;;; Commentary:
  61 ;;;
  62 ;;; This module implements the general mechanism of monads, and provides in
  63 ;;; particular an instance of the "store" monad.  The API was inspired by that
  64 ;;; of Racket's "better-monads" module (see
  65 ;;; <http://planet.racket-lang.org/package-source/toups/functional.plt/1/1/planet-docs/better-monads-guide/index.html>).
  66 ;;; The implementation and use case were influenced by Oleg Kysielov's
  67 ;;; "Monadic Programming in Scheme" (see
  68 ;;; <http://okmij.org/ftp/Scheme/monad-in-Scheme.html>).
  69 ;;;
  70 ;;; The store monad allows us to (1) build sequences of operations in the
  71 ;;; store, and (2) make the store an implicit part of the execution context,
  72 ;;; rather than a parameter of every single function.
  73 ;;;
  74 ;;; Code:
  75
  76 ;; Record type for monads manipulated at run time.
  77 (define-record-type <monad>
  78   (make-monad bind return)
  79   monad?
  80   (bind   monad-bind)
  81   (return monad-return))                         ; TODO: Add 'plus' and 'zero'
  82
  83 (define-syntax define-monad
  84   (lambda (s)
  85     "Define the monad under NAME, with the given bind and return methods."
  86     (define prefix (string->symbol "% "))
  87     (define (make-rtd-name name)
  88       (datum->syntax name
  89                      (symbol-append prefix (syntax->datum name) '-rtd)))
  90
  91     (syntax-case s (bind return)
  92       ((_ name (bind b) (return r))
  93        (with-syntax ((rtd (make-rtd-name #'name)))
  94          #`(begin
  95              (define rtd
  96                ;; The record type, for use at run time.
  97                (make-monad b r))
  98
  99              (define-syntax name
 100                ;; An "inlined record", for use at expansion time.  The goal is
 101                ;; to allow 'bind' and 'return' to be resolved at expansion
 102                ;; time, in the common case where the monad is accessed
 103                ;; directly as NAME.
 104                (lambda (s)
 105                  (syntax-case s (%bind %return)
 106                    ((_ %bind)   #'b)
 107                    ((_ %return) #'r)
 108                    (_           #'rtd))))))))))
 109
 110 (define-syntax-parameter >>=
 111   ;; The name 'bind' is already taken, so we choose this (obscure) symbol.
 112   (lambda (s)
 113     (syntax-violation '>>= ">>= (bind) used outside of 'with-monad'" s)))
 114
 115 (define-syntax-parameter return
 116   (lambda (s)
 117     (syntax-violation 'return "return used outside of 'with-monad'" s)))
 118
 119 (define-syntax with-monad
 120   (lambda (s)
 121     "Evaluate BODY in the context of MONAD, and return its result."
 122     (syntax-case s ()
 123       ((_ monad body ...)
 124        (eq? 'macro (syntax-local-binding #'monad))
 125        ;; MONAD is a syntax transformer, so we can obtain the bind and return
 126        ;; methods by directly querying it.
 127        #'(syntax-parameterize ((>>=    (identifier-syntax (monad %bind)))
 128                                (return (identifier-syntax (monad %return))))
 129            body ...))
 130       ((_ monad body ...)
 131        ;; MONAD refers to the <monad> record that represents the monad at run
 132        ;; time, so use the slow method.
 133        #'(syntax-parameterize ((>>=    (identifier-syntax
 134                                         (monad-bind monad)))
 135                                (return (identifier-syntax
 136                                         (monad-return monad))))
 137            body ...)))))
 138
 139 (define-syntax mlet*
 140   (syntax-rules (->)
 141     "Bind the given monadic values MVAL to the given variables VAR.  When the
 142 form is (VAR -> VAL), bind VAR to the non-monadic value VAL in the same way as
 143 'let'."
 144     ;; Note: the '->' symbol corresponds to 'is:' in 'better-monads.rkt'.
 145     ((_ monad () body ...)
 146      (with-monad monad body ...))
 147     ((_ monad ((var mval) rest ...) body ...)
 148      (with-monad monad
 149        (>>= mval
 150             (lambda (var)
 151               (mlet* monad (rest ...)
 152                 body ...)))))
 153     ((_ monad ((var -> val) rest ...) body ...)
 154      (let ((var val))
 155        (mlet* monad (rest ...)
 156          body ...)))))
 157
 158 (define-syntax mlet
 159   (lambda (s)
 160     (syntax-case s ()
 161       ((_ monad ((var mval ...) ...) body ...)
 162        (with-syntax (((temp ...) (generate-temporaries #'(var ...))))
 163          #'(mlet* monad ((temp mval ...) ...)
 164              (let ((var temp) ...)
 165                body ...)))))))
 166
 167 (define-syntax mbegin
 168   (syntax-rules (%current-monad)
 169     "Bind the given monadic expressions in sequence, returning the result of
 170 the last one."
 171     ((_ %current-monad mexp)
 172      mexp)
 173     ((_ %current-monad mexp rest ...)
 174      (>>= mexp
 175           (lambda (unused-value)
 176             (mbegin %current-monad rest ...))))
 177     ((_ monad mexp)
 178      (with-monad monad
 179        mexp))
 180     ((_ monad mexp rest ...)
 181      (with-monad monad
 182        (>>= mexp
 183             (lambda (unused-value)
 184               (mbegin monad rest ...)))))))
 185
 186 (define-syntax mwhen
 187   (syntax-rules ()
 188     "When CONDITION is true, evaluate EXP0..EXP* as in an 'mbegin'.  When
 189 CONDITION is false, return *unspecified* in the current monad."
 190     ((_ condition exp0 exp* ...)
 191      (if condition
 192          (mbegin %current-monad
 193            exp0 exp* ...)
 194          (return *unspecified*)))))
 195
 196 (define-syntax munless
 197   (syntax-rules ()
 198     "When CONDITION is false, evaluate EXP0..EXP* as in an 'mbegin'.  When
 199 CONDITION is true, return *unspecified* in the current monad."
 200     ((_ condition exp0 exp* ...)
 201      (if condition
 202          (return *unspecified*)
 203          (mbegin %current-monad
 204            exp0 exp* ...)))))
 205
 206 (define-syntax define-lift
 207   (syntax-rules ()
 208     ((_ liftn (args ...))
 209      (define (liftn proc monad)
 210        "Lift PROC to MONAD---i.e., return a monadic function in MONAD."
 211        (lambda (args ...)
 212          (with-monad monad
 213            (return (proc args ...))))))))
 214
 215 (define-lift lift0 ())
 216 (define-lift lift1 (a))
 217 (define-lift lift2 (a b))
 218 (define-lift lift3 (a b c))
 219 (define-lift lift4 (a b c d))
 220 (define-lift lift5 (a b c d e))
 221 (define-lift lift6 (a b c d e f))
 222 (define-lift lift7 (a b c d e f g))
 223
 224 (define (lift proc monad)
 225   "Lift PROC, a procedure that accepts an arbitrary number of arguments, to
 226 MONAD---i.e., return a monadic function in MONAD."
 227   (lambda args
 228     (with-monad monad
 229       (return (apply proc args)))))
 230
 231 (define (foldm monad mproc init lst)
 232   "Fold MPROC over LST, a list of monadic values in MONAD, and return a
 233 monadic value seeded by INIT."
 234   (with-monad monad
 235     (let loop ((lst    lst)
 236                (result init))
 237       (match lst
 238         (()
 239          (return result))
 240         ((head tail ...)
 241          (mlet* monad ((item   head)
 242                        (result (mproc item result)))
 243            (loop tail result)))))))
 244
 245 (define (mapm monad mproc lst)
 246   "Map MPROC over LST, a list of monadic values in MONAD, and return a monadic
 247 list.  LST items are bound from left to right, so effects in MONAD are known
 248 to happen in that order."
 249   (mlet monad ((result (foldm monad
 250                               (lambda (item result)
 251                                 (mlet monad ((item (mproc item)))
 252                                   (return (cons item result))))
 253                               '()
 254                               lst)))
 255     (return (reverse result))))
 256
 257 (define-inlinable (sequence monad lst)
 258   "Turn the list of monadic values LST into a monadic list of values, by
 259 evaluating each item of LST in sequence."
 260   (with-monad monad
 261     (mapm monad return lst)))
 262
 263 (define (anym monad proc lst)
 264   "Apply PROC to the list of monadic values LST; return the first value,
 265 lifted in MONAD, for which PROC returns true."
 266   (with-monad monad
 267     (let loop ((lst lst))
 268       (match lst
 269         (()
 270          (return #f))
 271         ((head tail ...)
 272          (mlet* monad ((value  head)
 273                        (result -> (proc value)))
 274            (if result
 275                (return result)
 276                (loop tail))))))))
 277
 278 (define-syntax listm
 279   (lambda (s)
 280     "Return a monadic list in MONAD from the monadic values MVAL."
 281     (syntax-case s ()
 282       ((_ monad mval ...)
 283        (with-syntax (((val ...) (generate-temporaries #'(mval ...))))
 284          #'(mlet monad ((val mval) ...)
 285              (return (list val ...))))))))
 286
 287
 288 \f
 289 ;;;
 290 ;;; Identity monad.
 291 ;;;
 292
 293 (define-inlinable (identity-return value)
 294   value)
 295
 296 (define-inlinable (identity-bind mvalue mproc)
 297   (mproc mvalue))
 298
 299 (define-monad %identity-monad
 300   (bind   identity-bind)
 301   (return identity-return))
 302
 303 \f
 304 ;;;
 305 ;;; State monad.
 306 ;;;
 307
 308 (define-inlinable (state-return value)
 309   (lambda (state)
 310     (values value state)))
 311
 312 (define-inlinable (state-bind mvalue mproc)
 313   "Bind MVALUE, a value in the state monad, and pass it to MPROC."
 314   (lambda (state)
 315     (call-with-values
 316         (lambda ()
 317           (mvalue state))
 318       (lambda (value state)
 319         ;; Note: as of Guile 2.0.11, declaring a variable to hold the result
 320         ;; of (mproc value) prevents a bit of unfolding/inlining.
 321         ((mproc value) state)))))
 322
 323 (define-monad %state-monad
 324   (bind state-bind)
 325   (return state-return))
 326
 327 (define* (run-with-state mval #:optional (state '()))
 328   "Run monadic value MVAL starting with STATE as the initial state.  Return
 329 two values: the resulting value, and the resulting state."
 330   (mval state))
 331
 332 (define-inlinable (current-state)
 333   "Return the current state as a monadic value."
 334   (lambda (state)
 335     (values state state)))
 336
 337 (define-inlinable (set-current-state value)
 338   "Set the current state to VALUE and return the previous state as a monadic
 339 value."
 340   (lambda (state)
 341     (values state value)))
 342
 343 (define (state-pop)
 344   "Pop a value from the current state and return it as a monadic value.  The
 345 state is assumed to be a list."
 346   (lambda (state)
 347     (match state
 348       ((head . tail)
 349        (values head tail)))))
 350
 351 (define (state-push value)
 352   "Push VALUE to the current state, which is assumed to be a list, and return
 353 the previous state as a monadic value."
 354   (lambda (state)
 355     (values state (cons value state))))
 356
 357 ;;; monads.scm end here