Changes between Version 1 and Version 2 of SQLLikeComprehensions


Ignore:
Timestamp:
Oct 28, 2007 8:03:47 PM (6 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}}}