-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathapplicative-do.trac
354 lines (250 loc) · 10.5 KB
/
applicative-do.trac
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
= Applicative do-notation =
This is a proposal to add support to GHC for desugaring do-notation into Applicative expressions where possible.
It's described in some detail in the paper: [https://www.microsoft.com/en-us/research/publication/desugaring-haskells-do-notation-into-applicative-operations/ Desugaring Haskell’s do-notation Into Applicative Operations] (ICFP'16).
An implementation was merged for GHC8: [https://github.com/ghc/ghc/commit/8ecf6d8f7dfee9e5b1844cd196f83f00f3b6b879].
See also [wiki:RecursiveDo]
== Tickets ==
Use Keyword = `ApplicativeDo` to ensure that a ticket ends up on these lists.
'''Open Tickets:'''
[[TicketQuery(status=new|patch,keywords=~ApplicativeDo)]]
'''Closed Tickets:'''
[[TicketQuery(status=closed,keywords=~ApplicativeDo)]]
== Summary ==
`ApplicativeDo` is a language extension enabled in the usual way via
{{{
{-# LANGUAGE ApplicativeDo #-}
}}}
When `ApplicativeDo` is turned on, GHC will use a different method for desugaring `do`-notation, which attempts to use the `Applicative` operator `<*>` as far as possible, along with `fmap` and `join`.
`ApplicativeDo` makes it possible to use `do`-notation for types that are `Applicative` but not `Monad`. (See examples below).
For a type that is a `Monad`, `ApplicativeDo` implements the same semantics as the standard `do`-notation desugaring, provided `<*>` = `ap` for this type.
`ApplicativeDo` respects `RebindableSyntax`: it will pick up whatever `<*>`, `fmap`, and `join` are in scope when `RebindableSyntax` is on.
== Motivation
1. Some Monads have the property that Applicative bind is more
efficient than Monad bind. Sometimes this is ''really
important'', such as when the Applicative bind is
concurrent whereas the Monad bind is sequential (c.f. [https://github.com/facebook/Haxl Haxl]). For
these monads we would like the do-notation to desugar to
Applicative bind where possible, to take advantage of the improved
behaviour but without forcing the user to explicitly choose.
2. Applicative syntax can be a bit obscure and hard to write.
Do-notation is more natural, so we would like to be able to write
Applicative composition in do-notation where possible. For example:
{{{
(\x y z -> x*y + y*z + z*x) <$> expr1 <*> expr2 <*> expr3
}}}
vs.
{{{
do x <- expr1; y <- expr2; z <- expr3; return (x*y + y*z + z*x)
}}}
== Example 1 ==
{{{
do
x <- a
y <- b
return (f x y)
}}}
This translates to
{{{
(\x y -> f x y) <$> a <*> b
}}}
Here we noticed that the statements `x <- a` and `y <- b` are independent, so we can make an `Applicative` expression. Note that the desugared version uses the operators `<$>` and `<*>`, so its inferred type will mention `Applicative` only rather than `Monad`. Therefore this `do` block will work for a type that is `Applicative` but not `Monad`.
== Example 2 ==
If the final statement does not have a `return`, then we need to use `join`:
{{{
do
x <- a
y <- b
f x y
}}}
Translates to
{{{
join ((\x y -> f x y) <$> a <*> b)
}}}
Since `join` is a `Monad` operation, this expression requires `Monad`.
== Example 3 ==
{{{
do
x1 <- A
x2 <- B
x3 <- C x1
x4 <- D x2
return (x1,x2,x3,x4)
}}}
Here we can do `A` and `B` together, and `C` and `D` together. We could do it like this:
{{{
do
(x1,x2) <- (,) <$> A <*> B
(\x3 x4 -> (x1,x2,x3,x4)) <$> C x1 <*> D x2
}}}
But it is slightly more elegant like this:
{{{
join ((\x1 x2 -> (\x3 x4 -> (x1,x2,x3,x4)) <$> C x1 <*> D x2)) <$> A <*> B)
}}}
because we avoid the intermediate tuple.
== Example 4 ==
{{{
do
x <- A
y <- B x
z <- C
return (f x y z)
}}}
Now we have a dependency: `y` depends on `x`, but there is still an opportunity to use `Applicative` since `z` does not depend on `x` or `y`. In this case we end up with:
{{{
(\(x,y) z -> f x y z) <$> (do x <- A; y <- B x; return (x,y)) <*> C
}}}
Note that we had to introduce a tuple to return both the values of `x` and `y` from the inner `do` expression
It's important that we keep the original ordering. For example, we don't want this:
{{{
do
(x,z) <- (,) <$> A <*> C
y <- B x
return (f x y z)
}}}
because this has a different semantics from the standard 'do' desugaring; a `Monad` that cares about ordering will expose the difference.
Another wrong result would be:
{{{
do
x <- A
(\y z -> f x y z) <$> B x <*> C
}}}
Because this version has less parallelism than the first result, in which `A` and `B` could be performed at the same time as `C`.
== Example 5 ==
In general, `ApplicativeDo` might have to build a complicated nested `Applicative` expression.
{{{
do
x1 <- a
x2 <- b
x3 <- c x1
x4 <- d
return (x2,x3,x4)
}}}
Here we can do `a/b/d` in parallel, but `c` depends on `x1`, which makes things a bit tricky: remember that we have to retain the semantics of standard `do` desugaring, so we can't move the call to `c` after the call to `d`.
This translates to
{{{
(\(x2,x3) x4 -> (x2, x3, x4))
<$> join ((\x1 x2 -> do
x3 <- c x1
return (x2,x3))
<$> a
<*> b)
<*> d)
}}}
We can write this expression in a simpler way using `|` for applicative composition (like parallel composition) and `;` for monadic composition (like sequential composition): `((a | b) ; c) | d`.
Note that this isn't the only good way to translate this expression, this is also possible: `(a ; (b | c)) | d`. It's not possible to know which is better. `ApplicativeDo` makes a best-effort attempt to use parallel composition where possible while retaining the semantics of the standard 'do' desugaring.
== Syntax & spec
There's a toy implementation which includes the syntax, desugaring, transformation and some examples here: https://github.com/simonmar/ado/blob/52ba028cad68af578bcdfb3f1c5b905f5b9c5617/adosim.hs
Syntax:
{{{
expr ::= ... | do {stmt_1; ..; stmt_n} expr | ...
stmt ::= pat <- expr
| (arg_1 | ... | arg_n) -- applicative composition, n>=1
| ... -- other kinds of statement (e.g. let)
arg ::= pat <- expr
| {stmt_1; ..; stmt_n} {var_1..var_n}
}}}
Desugaring for `do stmts`:
{{{
dsDo {} expr = expr
dsDo {pat <- rhs; stmts} expr =
rhs >>= \pat -> dsDo stmts expr
dsDo {(arg_1 | ... | arg_n)} (return expr) =
(\argpat (arg_1) .. argpat(arg_n) -> expr)
<$> argexpr(arg_1)
<*> ...
<*> argexpr(arg_n)
dsDo {(arg_1 | ... | arg_n); stmts} expr =
join (\argpat (arg_1) .. argpat(arg_n) -> dsDo stmts expr)
<$> argexpr(arg_1)
<*> ...
<*> argexpr(arg_n)
}}}
where
{{{
argpat (pat <- expr) = pat
argpat ({stmt_1; ..; stmt_n} {var_1..var_n}) = (var_1, .., var_n)
argexpr (pat <- expr) = expr
argexpr ({stmt_1; ..; stmt_n} {var_1..var_n}) =
dsDo {stmt_1; ..; stmt_n; return (var_1, ..., var_n)}
}}}
== Transformation ==
{{{
ado {} tail = tail
ado {pat <- expr} {return expr'} = (mkArg(pat <- expr)); return expr'
ado {one} tail = one : tail
ado stmts tail
| n == 1 = ado before (ado after tail) where (before,after) = split(stmts_1)
| n > 1 = (mkArg(stmts_1) | ... | mkArg(stmts_n)); tail
where
{stmts_1 .. stmts_n} = segments(stmts)
segments(stmts) =
-- divide stmts into segments with no interdependencies
mkArg({pat <- expr}) = (pat <- expr)
mkArg({stmt_1; ...; stmt_n}) =
{stmt_1; ...; stmt_n} {vars(stmt_1) u .. u vars(stmt_n)}
split({stmt_1; ..; stmt_n) =
({stmt_1; ..; stmt_i}, {stmt_i+1; ..; stmt_n})
-- 1 <= i <= n
-- i is a good place to insert a bind
}}}
== Differences from the actual implementation ==
1. The final expr in a "do" is a LastStmt, instead of being carried around separately.
2. there is no stripping of "return" during desugaring, it is handled earlier in the renamer instead.
3. arg has an optional "return", for the same reason as (2)
(2) and (3) are so that we can typecheck the syntax without having to desugar it first.
The syntax and desugaring rules are:
{{{
expr ::= ... | do {stmt_1; ..; stmt_n} | ...
stmt ::= expr -- last stmt in a "do" must be this
| pat <- expr
| (arg_1 | ... | arg_n)
| join (arg_1 | ... | arg_n)
| ...
arg ::= pat <- expr
| {stmt_1..stmt_n} {var_1..var_n} maybe_return
maybe_return ::= return | ()
}}}
{{{
dsDo {expr} = expr
dsDo {pat <- rhs; stmts} =
rhs >>= \pat -> dsDo stmts
dsDo {(arg_1 | ... | arg_n); stmts} =
(\argpat (arg_1) .. argpat(arg_n) -> dsDo stmts)
<$> argexpr(arg_1)
<*> ...
<*> argexpr(arg_n)
dsDo {join (arg_1 | ... | arg_n); stmts} =
join (\argpat (arg_1) .. argpat(arg_n) -> dsDo stmts)
<$> argexpr(arg_1)
<*> ...
<*> argexpr(arg_n)
}}}
where
{{{
argpat (pat <- expr) = pat
argpat ({stmt_1..stmt_n} {var_1..var_n} _) = (var_1, .., var_n)
argexpr (pat <- expr) = expr
argexpr ({stmt_1..stmt_n} {var_1..var_n} ()) =
dsDo {stmt_1; ..; stmt_n; (var_1, ..., var_n)}
argexpr ({stmt_1..stmt_n} {var_1..var_n} return) =
dsDo {stmt_1; ..; stmt_n; return (var_1, ..., var_n)}
}}}
Note that there's no matching on "return" during desugaring, the
"return" has already been removed.
---------------------------------
== Related proposals
* [http://www.haskell.org/pipermail/haskell-cafe/2011-September/095153.html Max's proposal on haskell-cafe]
* [http://hackage.haskell.org/package/applicative-quoters-0.1.0.7/docs/Control-Applicative-QQ-ADo.html Control.Applicative.QQ.ADo]
== Implementation
The implementation is tricky, because we want to do a transformation that affects type checking (and renaming, because we might be using `RebindableSyntax`), but we still want type errors in terms of the original source code. Therefore we calculate everything necessary to do the transformation during renaming, but leave enough information behind to reconstruct the original source code for the purposes of error messages.
See comments in [https://phabricator.haskell.org/D729] for more details.
=== Tricky case
{{{
do { x <- A
; y <- B
; z <- C x
; return (z+y) }
}}}
Then we could do `A ; (B | C)` or `(A | B) ; C`.
* If `tA + (max( tB, tC )) < max( tA, tB ) + tC`, then first is best, otherwise second.
If A is smaller than B and C, first is best. If C is smaller than A and B then second is best.