#5429: Docase notation as GHC extension -------------------------------------+------------------------------------- Reporter: tomasp | Owner: tomasp Type: feature request | Status: new Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: Resolution: | Keywords: monad, | syntactic sugar, mzip, | comprehensions Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by bgamari: Old description:
Many monads provide additional combinators for ''parallel composition'', ''choice'' and ''aliasing''. In our Haskell Symposium 2011 paper (http://www.cl.cam.ac.uk/~tp322/papers/docase.html) we call a monad with these 3 additional combinators a '''joinad'''.
The monads that implement (some of) these three operations include:
* '''Par monad''' for parallel programming implements ''parallel composition'' (run two computations in parallel) and ''aliasing'' (start computation and access the result in multiple other computations) and can be extended to support (non-deterministic) ''choice'' * '''Parsers''' can implement ''parallel composition'' as an intersection of languages (parse the same input using multiple parsers), which is useful for encoding validation rules and ''choice'' (use the result of a first parser that succeeds). * '''Other monads''' that can be considered include the `Orc` monad (for concurrent orchestration) and the encoding of CHP (Communicating Haskell Processes).
The proposal is to implement the a GHC extension that allows the `docase` notation for working with ''joinads''. Using the `Par` monad as an example, the following snippet implements a function `all` which tests whether a predicate holds for all leaves of a tree:
{{{ all :: (a -> Bool) -> Tree a -> Par Bool
all p (Leaf v) = return (p v) all p (Node left right) = docase all p left, all p right of False, ? -> return False ?, False -> return False allL, allR -> return (allL && allR) }}}
The left and right sub-trees are processed in parallel (using ''parllel composition''). The special pattern `?` denotes that the corresponding computation does not have to complete in order for the clause to match. This means that the first two clauses implement short-circuiting behavior (and can match even if the other branch is still being processed).
The operations used by the desugaring are expected to have the following types:
* `mzip :: m a -> m b -> m (a, b)`[[br]]This operation has been added by the recent patch that re-implements ''monad comprehensions'', so we can reuse it. * `morelse :: m a -> m a -> m a`[[br]]The operation has the same type as `mplus` from `MonadPlus`, but we require an operation that is left- biased. One possible option is to add `MonadOr` type class as suggested in http://www.haskell.org/haskellwiki/MonadPlus_reform_proposal. * `malias :: m a -> m (m a)`[[br]]The operation "starts" a computation and returns a handle for accessing the result. It has been used e.g. by the authors of the `Orc` monad. For many simpler monads, this can be implemented as monadic `return`.
===Feedback=== I would appreciate any feedback from GHC users and developers! In particular, here are some general, as well as more specific questions that I've heard in the past:
* What existing monads can implement the interface? (I believe there are quite a few of them including `Par`, Parsers, `Orc`, CPH, but I'd love to know about more.)
* What to do about monads that implement only some operations? Currently, the `malias` operation has default implementation. If a `docase` notation has just a single clause, then `morelse` is not required. If it has multiple clauses, each having just a single ''binding pattern'' (non `?`) then `mzip` is not required.
* The laws - the paper includes detailed discussion about laws (e.g. why `mzip` should be symmetric and why `morelse` should have left-biase). Does the community agree with the laws, or do you suggest some changes?
* Syntax seems to be a tricky question - the notation intentionally resembles `case`, but it takes a list of arguments (of type `m a1`, ..., `m an`), so it is not using ''tuple syntax''. Is there any better alternative?
* Correspondence with ''monad comprehensions'' - the `docase` notation can express parallel composition in a similar way as ''monad comprehensions''. I think this parity is a good thing. However, it allows more expressivity in one direction (by adding choice) and less in another (no group/order by comprehensions). Do you think this is a good ballance?
New description: Many monads provide additional combinators for ''parallel composition'', ''choice'' and ''aliasing''. In our Haskell Symposium 2011 paper (http://www.cl.cam.ac.uk/~tp322/papers/docase.html) we call a monad with these 3 additional combinators a '''joinad'''. The monads that implement (some of) these three operations include: * '''Par monad''' for parallel programming implements ''parallel composition'' (run two computations in parallel) and ''aliasing'' (start computation and access the result in multiple other computations) and can be extended to support (non-deterministic) ''choice'' * '''Parsers''' can implement ''parallel composition'' as an intersection of languages (parse the same input using multiple parsers), which is useful for encoding validation rules and ''choice'' (use the result of a first parser that succeeds). * '''Other monads''' that can be considered include the `Orc` monad (for concurrent orchestration) and the encoding of CHP (Communicating Haskell Processes). The proposal is to implement the a GHC extension that allows the `docase` notation for working with ''joinads''. Using the `Par` monad as an example, the following snippet implements a function `all` which tests whether a predicate holds for all leaves of a tree: {{{ all :: (a -> Bool) -> Tree a -> Par Bool all p (Leaf v) = return (p v) all p (Node left right) = docase all p left, all p right of False, ? -> return False ?, False -> return False allL, allR -> return (allL && allR) }}} The left and right sub-trees are processed in parallel (using ''parllel composition''). The special pattern `?` denotes that the corresponding computation does not have to complete in order for the clause to match. This means that the first two clauses implement short-circuiting behavior (and can match even if the other branch is still being processed). The operations used by the desugaring are expected to have the following types: * `mzip :: m a -> m b -> m (a, b)`[[br]]This operation has been added by the recent patch that re-implements ''monad comprehensions'', so we can reuse it. * `morelse :: m a -> m a -> m a`[[br]]The operation has the same type as `mplus` from `MonadPlus`, but we require an operation that is left-biased. One possible option is to add `MonadOr` type class as suggested in http://www.haskell.org/haskellwiki/MonadPlus_reform_proposal. * `malias :: m a -> m (m a)`[[br]]The operation "starts" a computation and returns a handle for accessing the result. It has been used e.g. by the authors of the `Orc` monad. For many simpler monads, this can be implemented as monadic `return`. ==Feedback== I would appreciate any feedback from GHC users and developers! In particular, here are some general, as well as more specific questions that I've heard in the past: * What existing monads can implement the interface? (I believe there are quite a few of them including `Par`, Parsers, `Orc`, CPH, but I'd love to know about more.) * What to do about monads that implement only some operations? Currently, the `malias` operation has default implementation. If a `docase` notation has just a single clause, then `morelse` is not required. If it has multiple clauses, each having just a single ''binding pattern'' (non `?`) then `mzip` is not required. * The laws - the paper includes detailed discussion about laws (e.g. why `mzip` should be symmetric and why `morelse` should have left-biase). Does the community agree with the laws, or do you suggest some changes? * Syntax seems to be a tricky question - the notation intentionally resembles `case`, but it takes a list of arguments (of type `m a1`, ..., `m an`), so it is not using ''tuple syntax''. Is there any better alternative? * Correspondence with ''monad comprehensions'' - the `docase` notation can express parallel composition in a similar way as ''monad comprehensions''. I think this parity is a good thing. However, it allows more expressivity in one direction (by adding choice) and less in another (no group/order by comprehensions). Do you think this is a good ballance? -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/5429#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler