Next: Algorithmic Skeletons Up: Explicit Parallelism Previous: Control Languages

Commutative Monads

Monads have proved popular in encapsulating state problems in sequential functional programming [115]. The idea is derived from category theory, and allows type-based control of certain kinds of state.

Because monads are generally used to program state, their implementations are usually deliberately single-threaded. This is not necessary, however. If the monad is commutative, then the operations captured within it can be computed in parallel. This has been exploited to produce a parallel type inference algorithm [48], and to formulate a general framework for parallelism [70]. In the latter system, for some monad Par, with operations


  unit :: a -> Par a
  bind :: Par a -> (a -> Par b) -> Par b
  fork :: Par a -> Par b -> Par (a,b)
Par is commutative if the following two definitions of fork are equivalent.

fork1 p q = p `bind` \ x -> q `bind` \ y ->
            unit (x,y)

fork2 p q = q `bind` \ y -> p `bind` \ x ->
            unit (x,y)
It is simple to reformulate nfib in terms of these operations

nfib n :: Par Int
nfib n = (nfib (n-1)  `fork` 
          nfib (n-2)) `bind` \ (n1,n2) ->
         unit(n1+n2+1)
Unfortunately, the type of nfib now precludes its use in non-monadic functions without some special trickery.


Kevin Hammond <kh@dcs.st-and.ac.uk>
Thu Jan 4 21:31:10 GMT 1996