# Changes between Version 4 and Version 5 of SQLLikeComprehensions

Show
Ignore:
Timestamp:
10/30/07 04:31:32 (6 years ago)
Comment:

--

Unmodified
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