Changes between Version 4 and Version 5 of SQLLikeComprehensions


Ignore:
Timestamp:
Oct 30, 2007 11:31:32 AM (8 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SQLLikeComprehensions

    v4 v5  
     1= Comprehensive comprehensions =
     2
    13As 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.
    24
    35
    4 == Bracketing Syntax ==
    5 
    6 Due 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 {{{
    9 xs = [1,2]
    10 ys = [3,4]
    11 zs = [5,6]
    12 
    13 p1 =
    14   [ (x,y,z)
    15   | ( x <- xs
    16     | y <- ys )
    17   , z <- zs ]
    18 
    19 p2 =
    20   [ (x,y,z)
    21   | x <- xs
    22   | ( y <- ys
    23     , z <- zs ) ]
    24 }}}
    25 
    26 This results in:
    27 
    28 {{{
    29 p1 = [(1,3,5), (1,3,6), (2,4,5), (2,4,6)]
    30 p2 = [(1,3,5), (2,3,6)]
    31 }}}
    32 
    33 Unfortunately, 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 
    39 When 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 
    41  * Disallow bracketing of qualifiers altogether!
    42   * This keeps the concrete syntax simple and should cover all common use cases
    43   * It does reduce the composability of the qualifier syntax rather drastically however
    44  * Keep bracketing in this manner but use type information to resolve the ambiguity
    45   * I will need to change the parser to consider qualifiers as expressions so that we can parse without any reduce/reduce conflicts
    46   * 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
    47   * Might have negative implications on the readability of some error messages :(
    48   * 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
    49  * Introduce new syntax to allow this idiom to be expressed unambiguously. Some examples of what we could use are below:
    50 
    51 {{{
    52 -- 1) A new keyword
    53 [ foo | x <- e,
    54         nest { y <- ys,
    55                z <- zs },
    56         x > y + 3 ]
    57 
    58 -- 2) Trying to suggest pulling things out of a sublist without having to mention binders
    59 [ foo | x <- e,
    60         <- [ .. | y <- ys,
    61                   z <- zs ],
    62         x > y + 3 ]
    63 
    64 -- 3) New kind of brackets
    65 [ foo | x <- e,
    66         (| y <- ys,
    67            z <- zs |),
    68         x < y + 3 ]
    69 
    70 -- 4) Variation on 2), slightly more concise
    71 [ foo | x <- e,
    72         <- [ y <- ys,
    73              z <- zs ],
    74         x > y + 3 ]
    75 
    76 -- 5) Another variation on 2), moving the ".." into the pattern rather than the comprehension body
    77 [ foo | x <- e,
    78         .. <- [ y <- ys,
    79                 z <- zs ],
    80         x > y + 3 ]
    81 }}}
    826
    837
     
    15680
    15781
     82== Bracketing Syntax ==
     83
     84Due to the generality added to comprehensions by the paper, it now makes sense to allow bracketing of qualifiers. An example from the paper is:
     85
     86{{{
     87xs = [1,2]
     88ys = [3,4]
     89zs = [5,6]
     90
     91p1 =
     92  [ (x,y,z)
     93  | ( x <- xs
     94    | y <- ys )
     95  , z <- zs ]
     96
     97p2 =
     98  [ (x,y,z)
     99  | x <- xs
     100  | ( y <- ys
     101    , z <- zs ) ]
     102}}}
     103
     104This results in:
     105
     106{{{
     107p1 = [(1,3,5), (1,3,6), (2,4,5), (2,4,6)]
     108p2 = [(1,3,5), (2,3,6)]
     109}}}
     110
     111Unfortunately, there is a practical problem with using brackets in this way: doing so causes a reduce/reduce conflict in the grammar. Consider this expression:
     112
     113{{{
     114[foo | (i, e) <- ies]
     115}}}
     116
     117When 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:
     118
     119 * Disallow bracketing of qualifiers altogether!
     120  * This keeps the concrete syntax simple and should cover all common use cases
     121  * It does reduce the composability of the qualifier syntax rather drastically however
     122 * Keep bracketing in this manner but use type information to resolve the ambiguity
     123  * I will need to change the parser to consider qualifiers as expressions so that we can parse without any reduce/reduce conflicts
     124  * 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
     125  * Might have negative implications on the readability of some error messages :(
     126  * 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
     127 * Introduce new syntax to allow this idiom to be expressed unambiguously. Some examples of what we could use are below:
     128
     129{{{
     130-- 1) A new keyword
     131[ foo | x <- e,
     132        nest { y <- ys,
     133               z <- zs },
     134        x > y + 3 ]
     135
     136-- 2) Trying to suggest pulling things out of a sublist
     137--    without having to mention binders
     138[ foo | x <- e,
     139        <- [ .. | y <- ys,
     140                  z <- zs ],
     141        x > y + 3 ]
     142
     143-- 3) New kind of brackets
     144[ foo | x <- e,
     145        (| y <- ys,
     146           z <- zs |),
     147        x < y + 3 ]
     148
     149-- 4) Variation on 2), slightly more concise
     150[ foo | x <- e,
     151        <- [ y <- ys,
     152             z <- zs ],
     153        x > y + 3 ]
     154
     155-- 5) Another variation on 2), moving the ".." into 
     156--    the pattern rather than the comprehension body
     157[ foo | x <- e,
     158        .. <- [ y <- ys,
     159                z <- zs ],
     160        x > y + 3 ]
     161}}}
     162
    158163== Extending To Arbitrary Monads ==
    159164