<option>-XRankNTypes</option>,
<option>-XImpredicativeTypes</option>,
<option>-XTypeOperators</option>,
- <option>-XRecursiveDo</option>,
+ <option>-XDoRec</option>,
<option>-XParallelListComp</option>,
<option>-XEmptyDataDecls</option>,
<option>-XKindSignatures</option>,
<title>The recursive do-notation
</title>
-<para> The recursive do-notation (also known as mdo-notation) is implemented as described in
-<ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>,
-by Levent Erkok, John Launchbury,
-Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
-This paper is essential reading for anyone making non-trivial use of mdo-notation,
-and we do not repeat it here.
-</para>
<para>
-The do-notation of Haskell does not allow <emphasis>recursive bindings</emphasis>,
+The do-notation of Haskell 98 does not allow <emphasis>recursive bindings</emphasis>,
that is, the variables bound in a do-expression are visible only in the textually following
code block. Compare this to a let-expression, where bound variables are visible in the entire binding
group. It turns out that several applications can benefit from recursive bindings in
-the do-notation, and this extension provides the necessary syntactic support.
+the do-notation. The <option>-XDoRec</option> flag provides the necessary syntactic support.
</para>
<para>
-Here is a simple (yet contrived) example:
-</para>
+Here is a simple (albeit contrived) example:
<programlisting>
-import Control.Monad.Fix
-
-justOnes = mdo xs <- Just (1:xs)
- return xs
+{-# LANGUAGE DoRec #-}
+justOnes = do { rec { xs <- Just (1:xs) }
+ ; return (map negate xs) }
</programlisting>
+As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [-1,-1,-1,...</literal>.
+</para>
<para>
-As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [1,1,1,...</literal>.
+The background and motivation for recusrive do-notation is described in
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
+by Levent Erkok, John Launchbury,
+Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
+The theory behind monadic value recursion is explained further in Erkok's thesis
+<ulink url="http://sites.google.com/site/leventerkok/erkok-thesis.pdf">Value Recursion in Monadic Computations</ulink>.
+However, note that GHC uses a different syntax than the one described in these documents.
</para>
+<sect3>
+<title>Details of recursive do-notation</title>
<para>
-The Control.Monad.Fix library introduces the <literal>MonadFix</literal> class. Its definition is:
+The recursive do-notation is enabled with the flag <option>-XDoRec</option> or, equivalently,
+the LANGUAGE pragma <option>DoRec</option>. It introduces the single new keyword "<literal>rec</literal>",
+which wraps a mutually-recursive group of monadic statements,
+producing a single statement.
</para>
+<para>Similar to a <literal>let</literal>
+statement, the variables bound in the <literal>rec</literal> are
+visible throughout the <literal>rec</literal> group, and below it.
+For example, compare
<programlisting>
-class Monad m => MonadFix m where
- mfix :: (a -> m a) -> m a
+do { a <- getChar do { a <- getChar
+ ; let { r1 = f a r2 ; rec { r1 <- f a r2
+ ; r2 = g r1 } ; r2 <- g r1 }
+ ; return (r1 ++ r2) } ; return (r1 ++ r2) }
</programlisting>
+In both cases, <literal>r1</literal> and <literal>r2</literal> are
+available both throughout the <literal>let</literal> or <literal>rec</literal> block, and
+in the statements that follow it. The difference is that <literal>let</literal> is non-monadic,
+while <literal>rec</literal> is monadic. (In Haskell <literal>let</literal> is
+really <literal>letrec</literal>, of course.)
+</para>
<para>
-The function <literal>mfix</literal>
-dictates how the required recursion operation should be performed. For example,
-<literal>justOnes</literal> desugars as follows:
+The static and dynamic semantics of <literal>rec</literal> can be described as follows:
+<itemizedlist>
+<listitem><para>
+First,
+similar to let-bindings, the <literal>rec</literal> is broken into
+minimal recursive groups, a process known as <emphasis>segmentation</emphasis>.
+For example:
+<programlisting>
+rec { a <- getChar ===> a <- getChar
+ ; b <- f a c rec { b <- f a c
+ ; c <- f b a ; c <- f b a }
+ ; putChar c } putChar c
+</programlisting>
+The details of segmentation are described in Section 3.2 of
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>.
+Segmentation improves polymorphism, reduces the size of the recursive "knot", and, as the paper
+describes, also has a semantic effect (unless the monad satisfies the right-shrinking law).
+</para></listitem>
+<listitem><para>
+Then each resulting <literal>rec</literal> is desugared, using a call to <literal>Control.Monad.Fix.mfix</literal>.
+For example, the <literal>rec</literal> group in the preceding example is desugared like this:
+<programlisting>
+rec { b <- f a c ===> (b,c) <- mfix (\~(b,c) -> do { b <- f a c
+ ; c <- f b a } ; c <- f b a
+ ; return (b,c) })
+</programlisting>
+In general, the statment <literal>rec <replaceable>ss</replaceable></literal>
+is desugared to the statement
<programlisting>
-justOnes = mfix (\xs' -> do { xs <- Just (1:xs'); return xs }
+<replaceable>vs</replaceable> <- mfix (\~<replaceable>vs</replaceable> -> do { <replaceable>ss</replaceable>; return <replaceable>vs</replaceable> })
</programlisting>
-For full details of the way in which mdo is typechecked and desugared, see
-the paper <ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>.
-In particular, GHC implements the segmentation technique described in Section 3.2 of the paper.
+where <replaceable>vs</replaceable> is a tuple of the variables bound by <replaceable>ss</replaceable>.
+</para><para>
+The original <literal>rec</literal> typechecks exactly
+when the above desugared version would do so. For example, this means that
+the variables <replaceable>vs</replaceable> are all monomorphic in the statements
+following the <literal>rec</literal>, because they are bound by a lambda.
</para>
<para>
-If recursive bindings are required for a monad,
-then that monad must be declared an instance of the <literal>MonadFix</literal> class.
-The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO.
-Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class
-for Haskell's internal state monad (strict and lazy, respectively).
+The <literal>mfix</literal> function is defined in the <literal>MonadFix</literal>
+class, in <literal>Control.Monad.Fix</literal>, thus:
+<programlisting>
+class Monad m => MonadFix m where
+ mfix :: (a -> m a) -> m a
+</programlisting>
+</para>
+</listitem>
+</itemizedlist>
</para>
<para>
-Here are some important points in using the recursive-do notation:
+Here are some other important points in using the recursive-do notation:
<itemizedlist>
<listitem><para>
-The recursive version of the do-notation uses the keyword <literal>mdo</literal> (rather
-than <literal>do</literal>).
+It is enabled with the flag <literal>-XDoRec</literal>, which is in turn implied by
+<literal>-fglasgow-exts</literal>.
</para></listitem>
<listitem><para>
-It is enabled with the flag <literal>-XRecursiveDo</literal>, which is in turn implied by
-<literal>-fglasgow-exts</literal>.
+If recursive bindings are required for a monad,
+then that monad must be declared an instance of the <literal>MonadFix</literal> class.
</para></listitem>
<listitem><para>
-Unlike ordinary do-notation, but like <literal>let</literal> and <literal>where</literal> bindings,
-name shadowing is not allowed; that is, all the names bound in a single <literal>mdo</literal> must
-be distinct (Section 3.3 of the paper).
+The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO.
+Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class
+for Haskell's internal state monad (strict and lazy, respectively).
</para></listitem>
<listitem><para>
-Variables bound by a <literal>let</literal> statement in an <literal>mdo</literal>
-are monomorphic in the <literal>mdo</literal> (Section 3.1 of the paper). However
-GHC breaks the <literal>mdo</literal> into segments to enhance polymorphism,
-and improve termination (Section 3.2 of the paper).
+Like <literal>let</literal> and <literal>where</literal> bindings,
+name shadowing is not allowed within a <literal>rec</literal>;
+that is, all the names bound in a single <literal>rec</literal> must
+be distinct (Section 3.3 of the paper).
+</para></listitem>
+<listitem><para>
+It supports rebindable syntax (see <xref linkend="rebindable-syntax"/>).
</para></listitem>
</itemizedlist>
</para>
+</sect3>
+
+<sect3> <title> Mdo-notation (deprecated) </title>
+<para> GHC used to support the flag <option>-XREecursiveDo</option>,
+which enabled the keyword <literal>mdo</literal>, precisely as described in
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
+but this is now deprecated. Instead of <literal>mdo { Q; e }</literal>, write
+<literal>do { rec Q; e }</literal>.
+</para>
<para>
Historical note: The old implementation of the mdo-notation (and most
of the existing documents) used the name
<literal>MonadRec</literal> for the class and the corresponding library.
This name is not supported by GHC.
</para>
+</sect3>
</sect2>
<sect3><title>Rules for functional dependencies </title>
<para>
In a class declaration, all of the class type variables must be reachable (in the sense
-mentioned in <xref linkend="type-restrictions"/>)
+mentioned in <xref linkend="flexible-contexts"/>)
from the free variables of each method type.
For example:
<sect2 id="impredicative-polymorphism">
<title>Impredicative polymorphism
</title>
+<para><emphasis>NOTE: the impredicative-polymorphism feature is deprecated in GHC 6.12, and
+will be removed or replaced in GHC 6.14.</emphasis></para>
+
<para>GHC supports <emphasis>impredicative polymorphism</emphasis>,
enabled with <option>-XImpredicativeTypes</option>.
This means
portable).</para>
</sect3>
+ <sect3 id="conlike-pragma">
+ <title>CONLIKE modifier</title>
+ <indexterm><primary>CONLIKE</primary></indexterm>
+ <para>An INLINE or NOINLINE pragma may have a CONLIKE modifier,
+ which affects matching in RULEs (only). See <xref linkend="conlike"/>.
+ </para>
+ </sect3>
+
<sect3 id="phase-control">
<title>Phase control</title>
</para>
</listitem>
-<listitem>
+</itemizedlist>
+
+</para>
+
+</sect2>
+
+<sect2 id="conlike">
+<title>How rules interact with INLINE/NOINLINE and CONLIKE pragmas</title>
<para>
Ordinary inlining happens at the same time as rule rewriting, which may lead to unexpected
results. Consider this (artificial) example
<programlisting>
f x = x
-{-# RULES "f" f True = False #-}
-
g y = f y
-
h z = g True
+
+{-# RULES "f" f True = False #-}
</programlisting>
Since <literal>f</literal>'s right-hand side is small, it is inlined into <literal>g</literal>,
to give
</para>
<para>
The way to get predictable behaviour is to use a NOINLINE
-pragma on <literal>f</literal>, to ensure
+pragma, or an INLINE[<replaceable>phase</replaceable>] pragma, on <literal>f</literal>, to ensure
that it is not inlined until its RULEs have had a chance to fire.
</para>
-</listitem>
-</itemizedlist>
-
+<para>
+GHC is very cautious about duplicating work. For example, consider
+<programlisting>
+f k z xs = let xs = build g
+ in ...(foldr k z xs)...sum xs...
+{-# RULES "foldr/build" forall k z g. foldr k z (build g) = g k z #-}
+</programlisting>
+Since <literal>xs</literal> is used twice, GHC does not fire the foldr/build rule. Rightly
+so, because it might take a lot of work to compute <literal>xs</literal>, which would be
+duplicated if the rule fired.
+</para>
+<para>
+Sometimes, however, this approach is over-cautious, and we <emphasis>do</emphasis> want the
+rule to fire, even though doing so would duplicate redex. There is no way that GHC can work out
+when this is a good idea, so we provide the CONLIKE pragma to declare it, thus:
+<programlisting>
+{-# INLINE[1] CONLIKE f #-}
+f x = <replaceable>blah</replaceable>
+</programlisting>
+CONLIKE is a modifier to an INLINE or NOINLINE pragam. It specifies that an application
+of f to one argument (in general, the number of arguments to the left of the '=' sign)
+should be considered cheap enough to duplicate, if such a duplication would make rule
+fire. (The name "CONLIKE" is short for "constructor-like", because constructors certainly
+have such a property.)
+The CONLIKE pragam is a modifier to INLINE/NOINLINE because it really only makes sense to match
+<literal>f</literal> on the LHS of a rule if you are sure that <literal>f</literal> is
+not going to be inlined before the rule has a chance to fire.
</para>
-
</sect2>
<sect2>
Use <option>-ddump-rules</option> to see what transformation rules GHC is using.
</para>
</listitem>
-<listitem>
+<listitem>
<para>
Use <option>-ddump-simpl-stats</option> to see what rules are being fired.
If you add <option>-dppr-debug</option> you get a more detailed listing.
</para>
</listitem>
+
<listitem>
+<para>
+ Use <option>-ddump-rule-firings</option> to see in great detail what rules are being fired.
+If you add <option>-dppr-debug</option> you get a still more detailed listing.
+</para>
+</listitem>
+<listitem>
<para>
The definition of (say) <function>build</function> in <filename>GHC/Base.lhs</filename> looks like this: