Changes between Version 4 and Version 5 of SQLLikeComprehensions


Ignore:
Timestamp:
Oct 30, 2007 11:31:32 AM (7 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