Opened 3 years ago

Last modified 20 months ago

#5429 new feature request

Docase notation as GHC extension

Reported by: tomasp Owned by: tomasp
Priority: normal Milestone: 7.6.2
Component: Compiler Version:
Keywords: monad, syntactic sugar, mzip, comprehensions Cc: fischer@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty:
Test Case: Blocked By:
Blocking: Related Tickets:

Description (last modified by simonpj)

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)
    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
    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)
    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?

Change History (8)

comment:1 Changed 3 years ago by tomasp

  • Owner set to tomasp

The prototype implementation of the extension (started at Cambridge Hackathon 2 weeks ago) can be found in my forked GitHub? repository:

I believe that the implementation is reasonably modular and does not affect the rest of GHC in any unexpected ways. It adds a single new case HsDocase to the expression syntax. It is implemented as an extension (can be turned on using :set -XDocaseNotation). The syntax in parser duplicates parts of the syntax for case (to allow additional ? pseudo-pattern without affecting the rest of the language). More complex routines are implemented in two additional modules (TcDocase and DsDocase).

The patch is not yet complete. At the moment, I'm aware of the following limitations:

  • The documentation for docase in the docs folder is missing.
  • The tests for the docase notation are missing.
  • I need to review the code to make sure everything is well documented.

If anybody can review the code and give some additional feedback, that would be highly appreciated. I published the patch on GitHub?, because I wasn't sure what is the best practice (the wiki page that describes working with Git is a bit incomplete http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions/Git)

comment:2 Changed 3 years ago by sebf

  • Cc fischer@… added

comment:3 Changed 3 years ago by igloo

  • Status changed from new to patch

comment:4 Changed 3 years ago by simonpj

  • Owner tomasp deleted
  • Status changed from patch to new

Simon PJ and Tomas had a brief chat. Summary

  • It's not a huge patch, but there's always a cost in adding a feature. It's not clear whether docase is sufficiently persuasive to go into GHC permanently. Tomas will talk to people using it, refine design etc, and make an active case for inclusion in due course if it seems like a Very Useful Thing.
  • Meanwhile Simon M and Simon PJ will go to Tomas's talk in Tokyo

comment:5 Changed 3 years ago by simonpj

  • Owner set to tomasp

comment:6 Changed 3 years ago by simonpj

  • Description modified (diff)

comment:7 Changed 2 years ago by igloo

  • Milestone set to 7.6.1

comment:8 Changed 20 months ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2
Note: See TracTickets for help on using tickets.