RecursiveDo.md

+
+
+
+# Recursive Do Notation
+
+
+## Brief Explanation
+
+
+
+An extended form of `do` notation allowing value recursion (or feedback) for monads in the [ MonadFix](http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-Fix.html) class.
+
+
+## References
+
+
+- [ papers](http://www.cse.ogi.edu/PacSoft/projects/rmb/)
+- [ GHC documentation](http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#mdo-notation)
+- [Arrows](arrows)
+
+## Tickets
+
+
+
+<table><tr><th>[\#64](https://gitlab.haskell.org//haskell/prime/issues/64)</th>
+<td>add recursive do syntax</td></tr></table>
+
+
+
+## Variations
+
+
+
+Using `mfix` adds a `MonadFix` constraint, and also affects the semantics for some monads, so a key choice is how `mfix` is introduced.
+As an experiment, two syntaxes are implemented in GHC, both for `do`-notation and [arrow notation](arrows).
+It would clearly be preferable if there was only one variant of recursive `do`, even if arrow notation is not adopted.
+
+
+### Implicit recursion
+
+
+
+(as implemented in GHC and Hugs)
+
+
+
+A dependency analysis is performed over the list of statements, and minimal subsequences of interdependent statements are translated using `mfix`.
+That is, a variable used before it is bound is treated as recursively defined, while in a Haskell 98 `do`-statement it would be treated as shadowed.
+
+
+
+To retain backwards compatibility, existing implementations use a different keyword (`mdo`) for expressions treated in this way, and always add a `MonadFix` constraint to these expressions. If the keyword `mdo` is not suggestive enough (see below) a new keyword (`recdo`?) could be chosen.
+An alternative is to extend the ordinary `do`-notation, sacrificing backwards compatibility.
+In that case, the `MonadFix` constraint would be added only if a recursive binding was present.
+
+
+
+**Cons**
+
+
+- either use another keyword for a second kind of `do`-statement, or break backwards compatibility. Opinion is divided on the value of variable shadowing.
+- a dependency analysis is required to determine the semantics, making it significantly more difficult to understand the desugaring.
+
+
+(The same approaches also work for arrow notation, with the same trade-offs.)
+
+
+### Explicit recursion
+
+
+
+(as implemented in the `do` part of [arrow notation](arrows) and also in plain `do` in GHC with `-farrows`)
+
+
+
+Add to the current `do`-notation a new `rec` statement containing a sequence of mutually recursive statements.
+The `rec` keyword is a bit more suggestive of its meaning than `mdo`.
+The extent of the recursion is explicit, though implementations can trim non-recursive variables from the feedback set without changing the semantics.
+
+
+
+**Cons**
+
+
+- contrasts with `let`/`where` bindings, in which recursion is implicit.
+- `rec` is a common identifier.
+
+## Comment
+
+
+
+For the purpose of this discussion, there are two classes of monads/arrows: those that support recursion,
+and those that don't. By contrast, recursion in a `where` or `let` is always a possibility.
+This suggests two different keywords, `do` and e.g. `recdo` to clearly signal the intent.
+`recdo` could most likely be made to work for the arrow syntax as well, even if the "do" in the
+keyword has imperative connotations that wouldn't necessarily be appropriate (e.g. when
+declaratively specifying a network of stream processors or signal functions). Maybe an even better
+keyword would be found.
+
+
+## Pros
+
+
+- makes programs much more readable that the equivalent forms using `mfix`.
+
+## Cons
+
+
+- the candidate syntaxes have different drawbacks (see above)