Changes between Version 1 and Version 2 of SQLLikeComprehensions


Ignore:
Timestamp:
Oct 28, 2007 8:03:47 PM (8 years ago)
Author:
guest
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SQLLikeComprehensions

    v1 v2  
    11As part of his final year work at Cambridge, Max Bolingbroke is working on implementing the "Comprehensive Comprehensions" described in a paper [http://research.microsoft.com/~simonpj/papers/list-comp/index.htm available here] in GHC. This page will contain notes on the implementation as it unfolds.
     2
     3
     4== Bracketing Syntax ==
     5
     6Due to the generality added to comprehensions by the paper, it now makes sense to allow bracketing of qualifiers. An example from the paper is:
     7
     8{{{
     9xs = [1,2]
     10ys = [3,4]
     11zs = [5,6]
     12
     13p1 =
     14  [ (x,y,z)
     15  | ( x <- xs
     16    | y <- ys )
     17  , z <- zs ]
     18
     19p2 =
     20  [ (x,y,z)
     21  | x <- xs
     22  | ( y <- ys
     23    , z <- zs ) ]
     24}}}
     25
     26This results in:
     27
     28{{{
     29p1 = [(1,3,5), (1,3,6), (2,4,5), (2,4,6)]
     30p2 = [(1,3,5), (2,3,6)]
     31}}}
     32
     33Unfortunately, there is a practical problem with using brackets in this way: doing so causes a reduce/reduce conflict in the grammar. Consider this expression:
     34
     35{{{
     36[foo | (i, e) <- ies]
     37}}}
     38
     39When the parser reaches the bracket after "e" it is valid to either reduce "(i, e)" to a pair of qualifiers (i.e. i and e are treated as guard expressions), OR to reduce it to the tuple expression (i, e) which will be later converted to a pattern. There are a number of alternative ways we could solve this:
     40* Disallow bracketing of qualifiers altogether!
     41 * This keeps the concrete syntax simple and should cover all common use cases
     42 * It does reduce the composability of the qualifier syntax rather drastically however
     43* Keep bracketing in this manner but use type information to resolve the ambiguity
     44 * I will need to change the parser to consider qualifiers as expressions so that we can parse without any reduce/reduce conflicts
     45 * We can then always use type information to determine which reading is correct, because guards are always boolean, and so can be distinguished from tuples as required
     46 * Might have negative implications on the readability of some error messages :(
     47 * If the parser finds it hard to understand this syntax, you can argue that any human reader would too and hence we should look for something less ambiguous
     48* Introduce new syntax to allow this idiom to be expressed unambiguously. Some examples of what we could use are below:
     49
     50{{{
     51-- 1) A new keyword
     52[ foo | x <- e,
     53        nest { y <- ys,
     54               z <- zs },
     55        x > y + 3 ]
     56
     57-- 2) Trying to suggest pulling things out of a sublist without having to mention binders
     58[ foo | x <- e,
     59        <- [ .. | y <- ys,
     60                  z <- zs ],
     61        x > y + 3 ]
     62
     63-- 3) New kind of brackets
     64[ foo | x <- e,
     65        (| y <- ys,
     66           z <- zs |),
     67        x < y + 3 ]
     68
     69-- 4) Variation on 2), slightly more concise
     70[ foo | x <- e,
     71        <- [ y <- ys,
     72             z <- zs ],
     73        x > y + 3 ]
     74
     75-- 5) Another variation on 2), moving the ".." into the pattern rather than the comprehension body
     76[ foo | x <- e,
     77        .. <- [ y <- ys,
     78                z <- zs ],
     79        x > y + 3 ]
     80}}}
     81
     82
     83== Ordering Syntax ==
     84
     85TODO
     86
     87
     88== Extending To Arbitrary Monads ==
     89
     90On the [http://haskell.org/haskellwiki/Simonpj/Talk:ListComp paper talk page], Michael Adams has outlined how the new idioms could be extended to arbitrary monads. It looks very nice theoretically, but before we consider actually implementing this we need to know if anyone has a use case for the syntax. To demonstrate the kind of thing that this would make possible, consider the following example from Michael:
     91
     92{{{
     93do a <- ma
     94   ...
     95   b <- mb
     96   c <- mc
     97   sort by (b, c) using foo
     98   d <- md
     99   ...
     100   return (a, b, c, d)
     101}}}
     102
     103It would de-sugar to:
     104
     105{{{
     106((do a <- ma
     107   ...
     108   b <- mb
     109   c <- mc
     110   return ((b, c), (a, b, c))
     111) `foo` fst) >>= \result ->
     112do let (a, _, _) = result
     113       (_, b, _) = result
     114       (_, _, c) = result
     115   d <- md
     116   ...
     117   return (a, b, c, d)
     118}}}
     119
     120Where we have:
     121
     122{{{
     123foo :: forall a. (a -> t) -> m a -> m a
     124}}}