... | ... | @@ -3,6 +3,9 @@ |
|
|
|
|
|
This is a proposal to add support to GHC for desugaring do-notation into Applicative expressions where possible.
|
|
|
|
|
|
|
|
|
To jump to the code, see [ https://phabricator.haskell.org/D729](https://phabricator.haskell.org/D729).
|
|
|
|
|
|
## Related proposals
|
|
|
|
|
|
- [ Max's proposal on haskell-cafe](http://www.haskell.org/pipermail/haskell-cafe/2011-September/095153.html)
|
... | ... | @@ -13,7 +16,7 @@ This is a proposal to add support to GHC for desugaring do-notation into Applica |
|
|
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. Haxl). For
|
|
|
concurrent whereas the Monad bind is sequential (c.f. [ Haxl](https://github.com/facebook/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.
|
... | ... | @@ -48,15 +51,10 @@ Since in general Applicative composition might behave differently from monadic b |
|
|
{-# LANGUAGE ApplicativeDo #-}
|
|
|
```
|
|
|
|
|
|
## Stage 1
|
|
|
## Example 1
|
|
|
|
|
|
|
|
|
This section describes a transformation that could be performed during
|
|
|
desugaring. It covers use case (1), but not (2). I'm describing this
|
|
|
first because it is easy to understand by itself, and extends to a
|
|
|
solution for (2). We might consider implementing this first.
|
|
|
|
|
|
### Examples
|
|
|
We'll cover a few examples first, and then describe the transformation in general.
|
|
|
|
|
|
```wiki
|
|
|
do
|
... | ... | @@ -69,163 +67,137 @@ solution for (2). We might consider implementing this first. |
|
|
desugars to
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
(x,y) <- (,) <$> A <*> B
|
|
|
return (f x y)
|
|
|
(\x y -> f x y) <$> A <*> B
|
|
|
```
|
|
|
|
|
|
|
|
|
Note that the tuples introduces like this will probably be optimised
|
|
|
away when the Monad type is known and its bind can be inlined, but for
|
|
|
overloaded Monad code they will not be. In Stage 2 (below) we'll get
|
|
|
rid of the tuples in some cases.
|
|
|
|
|
|
|
|
|
In general we might have
|
|
|
which simplifies further to
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
.. stmts1 ..
|
|
|
x <- A
|
|
|
y <- B
|
|
|
z <- E[y]
|
|
|
.. stmts2 ..
|
|
|
f <$> A <*> B
|
|
|
```
|
|
|
|
|
|
|
|
|
which we desugar to
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
.. stmts1 ..
|
|
|
(x,y) <- (,) <$> A <*> B
|
|
|
z <- E[y]
|
|
|
.. stmts2 ..
|
|
|
```
|
|
|
Since this doesn't refer to any of the `Monad` operations, the typechecker will infer that it only requires `Applicative`.
|
|
|
|
|
|
## Example 1a
|
|
|
|
|
|
this is the best we can do: the rest of the do expression might refer
|
|
|
to x or y.
|
|
|
|
|
|
|
|
|
So in general we want to take the largest consecutive sequence of
|
|
|
statements where none of the rhs's refer to any of the bound
|
|
|
variables, and lift them into an Applicative expression.
|
|
|
|
|
|
|
|
|
A non-binding statement can be considered to be a binding statement
|
|
|
with a wildcard pattern.
|
|
|
We might not have a `return`, e.g.:
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
x <- A
|
|
|
y <- B -- B does not refer to x
|
|
|
C -- C does not refer to x or y
|
|
|
return (f x y)
|
|
|
f x y
|
|
|
```
|
|
|
|
|
|
|
|
|
desugars to
|
|
|
In which case the result is similar, but we need to add a `join`:
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
(x,y,_) <- (,,) <$> A <*> B <*> C
|
|
|
return (f x y)
|
|
|
join ((\x y -> f x y) <$> A <*> B)
|
|
|
```
|
|
|
|
|
|
|
|
|
or we can be slightly more clever:
|
|
|
Of course this requires a `Monad`, since `join` is a `Monad` operation.
|
|
|
|
|
|
## Example 2
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
(x,y) <- (,) <$> A <*> (B <* C)
|
|
|
return (f x y)
|
|
|
x <- A
|
|
|
y <- B x
|
|
|
z <- C
|
|
|
return (f x y z)
|
|
|
```
|
|
|
|
|
|
|
|
|
What if there are more than 63(?) statements, and we don't have a
|
|
|
tuple big enough? We have to desugar to nested tuples in this case.
|
|
|
Not a huge problem, this is exactly what we do for pattern bindings.
|
|
|
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:
|
|
|
|
|
|
```wiki
|
|
|
(\(x,y) z -> f x y z) <$> (do x <- A; y <- B x; return (x,y)) <*> C
|
|
|
```
|
|
|
|
|
|
### No unique grouping
|
|
|
|
|
|
Note that we had to introduce a tuple to return both the values of `x` and `y` from the inner `do` expression
|
|
|
|
|
|
There isn't a guaranteed unique way of doing the grouping. Eg
|
|
|
|
|
|
It's important that we keep the original ordering. For example, we don't want this:
|
|
|
|
|
|
```wiki
|
|
|
do { x <- A
|
|
|
; y <- B -- no x
|
|
|
; z <- C x }
|
|
|
do
|
|
|
(x,z) <- (,) <$> A <*> C
|
|
|
y <- B
|
|
|
return (f x y z)
|
|
|
```
|
|
|
|
|
|
|
|
|
could be grouped with the first two in an applicative, or the second two, but not all three. Which one "wins"?
|
|
|
because now evaluating the expression in a monad that cares about ordering will give a different result.
|
|
|
|
|
|
## Stage 2
|
|
|
|
|
|
Another wrong result would be:
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
x <- A
|
|
|
(\y z -> f x y z) <$> B <*> C
|
|
|
```
|
|
|
|
|
|
This covers a more comprehensive transformation that would also enable
|
|
|
us to drop a Monad constraint to an Applicative constraint in the
|
|
|
typing of do expressions for a certain well-defined subset of the do
|
|
|
syntax.
|
|
|
|
|
|
Because this version has less parallelism than the first result, in which `A` and `B` could be performed at the same time as `C`.
|
|
|
|
|
|
Back to our first example:
|
|
|
## Example 3
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
x <- A
|
|
|
y <- B -- B does not refer to x
|
|
|
return (f x y)
|
|
|
do
|
|
|
x1 <- A
|
|
|
x2 <- B
|
|
|
x3 <- C x1
|
|
|
x4 <- D x2
|
|
|
return (x1,x2,x3,x4)
|
|
|
```
|
|
|
|
|
|
|
|
|
we can go further in desugaring this:
|
|
|
Here we can do `A` and `B` in parallel, and `C` and `D` in parallel. We could do it like this:
|
|
|
|
|
|
```wiki
|
|
|
(\x y -> f x y) <$> A <*> B
|
|
|
do
|
|
|
(x1,x2) <- (,) <$> A <*> B
|
|
|
(\x3 x4 -> (x1,x2,x3,x4)) <$> C x1 <*> D x2
|
|
|
```
|
|
|
|
|
|
|
|
|
(obviously the lambda expression can be eta-reduced in this example,
|
|
|
but that's not the case in general).
|
|
|
But it is slightly more elegant like this:
|
|
|
|
|
|
```wiki
|
|
|
join ((\x1 x2 -> (\x3 x4 -> (x1,x2,x3,x4)) <$> C x1 <*> D x2)) <$> A <*> B)
|
|
|
```
|
|
|
|
|
|
For this to work we have to recognise "return". Or perhaps "pure".
|
|
|
|
|
|
because we avoid the intermediate tuple.
|
|
|
|
|
|
There are two advantages here:
|
|
|
## In general
|
|
|
|
|
|
- This code could be typed with an Applicative constraint rather than
|
|
|
Monad.
|
|
|
|
|
|
- It leads to more efficient code when the Monad type is not known,
|
|
|
because we have eliminated the intermediate pair.
|
|
|
Let's use a more concise syntax to talk about the structure of these expressions. We'll use ; to mean bind, and \| to mean an `Applicative` composition of two expressions. So the solution to Example 3 would be written `(A | B) ; (C | D)`, making it clear that we want `A` and `B` in parallel, then a bind, followed by `C` and `D` in parallel.
|
|
|
|
|
|
|
|
|
What if the final expression is not a "return"?
|
|
|
The general problem can be stated like this:
|
|
|
|
|
|
```wiki
|
|
|
do
|
|
|
x <- A
|
|
|
y <- B -- B does not refer to x
|
|
|
f x y
|
|
|
```
|
|
|
|
|
|
Given a sequence of statements S1...Sn, find a way to express the list as a nested application of the operators `|` and `;`, such that
|
|
|
|
|
|
this is
|
|
|
- in every `A | B`, `B` does not depend on anything in `A`, and
|
|
|
- we get the maximum available parallelism.
|
|
|
|
|
|
```wiki
|
|
|
join ((\x y -> f x y) <$> A <*> B)
|
|
|
```
|
|
|
|
|
|
To define parallelism, we could replace each statement with the value 1, `;` with `+`, and `|` with `max`, and evaluate the expression. A lower result indicates more parallelism.
|
|
|
|
|
|
## Implementation
|
|
|
|
|
|
Note: \*not\* an Applicative, because "join" is a Monad operation.
|
|
|
However we have eliminated the pair.
|
|
|
|
|
|
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.
|
|
|
|
|
|
Problems:
|
|
|
|
|
|
- desugaring comes after typechecking, so the type checker would need
|
|
|
its own version of the desugaring rules to be able to tell when a
|
|
|
do expression can be fully desugared to Applicative syntax. |
|
|
See comments in [ https://phabricator.haskell.org/D729](https://phabricator.haskell.org/D729) for more details. |