<option>-XPostfixOperators</option>,
<option>-XPatternGuards</option>,
<option>-XLiberalTypeSynonyms</option>,
+ <option>-XExplicitForAll</option>,
<option>-XRankNTypes</option>,
<option>-XImpredicativeTypes</option>,
<option>-XTypeOperators</option>,
- <option>-XRecursiveDo</option>,
+ <option>-XDoRec</option>,
<option>-XParallelListComp</option>,
<option>-XEmptyDataDecls</option>,
<option>-XKindSignatures</option>,
<entry>Name</entry>
</row>
</thead>
+
+<!--
+ to find the DocBook entities for these characters, find
+ the Unicode code point (e.g. 0x2237), and grep for it in
+ /usr/share/sgml/docbook/xml-dtd-*/ent/* (or equivalent on
+ your system. Some of these Unicode code points don't have
+ equivalent DocBook entities.
+ -->
+
<tbody>
<row>
<entry><literal>::</literal></entry>
<entry>MIDLINE HORIZONTAL ELLIPSIS</entry>
</row>
</tbody>
+
+ <tbody>
+ <row>
+ <entry>-<</entry>
+ <entry>↢</entry>
+ <entry>0x2919</entry>
+ <entry>LEFTWARDS ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>>-</entry>
+ <entry>↣</entry>
+ <entry>0x291A</entry>
+ <entry>RIGHTWARDS ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>-<<</entry>
+ <entry></entry>
+ <entry>0x291B</entry>
+ <entry>LEFTWARDS DOUBLE ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>>>-</entry>
+ <entry></entry>
+ <entry>0x291C</entry>
+ <entry>RIGHTWARDS DOUBLE ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>*</entry>
+ <entry>★</entry>
+ <entry>0x2605</entry>
+ <entry>BLACK STAR</entry>
+ </row>
+ </tbody>
+
</tgroup>
</informaltable>
</sect2>
<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>-XRecursiveDo</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>
<indexterm><primary><literal>forall</literal></primary></indexterm>
</term>
<listitem><para>
- Stolen (in types) by: <option>-XScopedTypeVariables</option>,
+ Stolen (in types) by: <option>-XExplicitForAll</option>, and hence by
+ <option>-XScopedTypeVariables</option>,
<option>-XLiberalTypeSynonyms</option>,
<option>-XRank2Types</option>,
<option>-XRankNTypes</option>,
<sect3>
<title>Multi-parameter type classes</title>
<para>
-Multi-parameter type classes are permitted. For example:
+Multi-parameter type classes are permitted, with flag <option>-XMultiParamTypeClasses</option>.
+For example:
<programlisting>
</para>
</sect3>
-<sect3>
+<sect3 id="superclass-rules">
<title>The superclasses of a class declaration</title>
<para>
-There are no restrictions on the context in a class declaration
-(which introduces superclasses), except that the class hierarchy must
-be acyclic. So these class declarations are OK:
+In Haskell 98 the context of a class declaration (which introduces superclasses)
+must be simple; that is, each predicate must consist of a class applied to
+type variables. The flag <option>-XFlexibleContexts</option>
+(<xref linkend="flexible-contexts"/>)
+lifts this restriction,
+so that the only restriction on the context in a class declaration is
+that the class hierarchy must be acyclic. So these class declarations are OK:
<programlisting>
<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:
(You need <link linkend="instance-rules"><option>-XFlexibleInstances</option></link> to do this.)
</para>
<para>
+Warning: overlapping instances must be used with care. They
+can give rise to incoherence (ie different instance choices are made
+in different parts of the program) even without <option>-XIncoherentInstances</option>. Consider:
+<programlisting>
+{-# LANGUAGE OverlappingInstances #-}
+module Help where
+
+ class MyShow a where
+ myshow :: a -> String
+
+ instance MyShow a => MyShow [a] where
+ myshow xs = concatMap myshow xs
+
+ showHelp :: MyShow a => [a] -> String
+ showHelp xs = myshow xs
+
+{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}
+module Main where
+ import Help
+
+ data T = MkT
+
+ instance MyShow T where
+ myshow x = "Used generic instance"
+
+ instance MyShow [T] where
+ myshow xs = "Used more specific instance"
+
+ main = do { print (myshow [MkT]); print (showHelp [MkT]) }
+</programlisting>
+In function <literal>showHelp</literal> GHC sees no overlapping
+instances, and so uses the <literal>MyShow [a]</literal> instance
+without complaint. In the call to <literal>myshow</literal> in <literal>main</literal>,
+GHC resolves the <literal>MyShow [T]</literal> constraint using the overlapping
+instance declaration in module <literal>Main</literal>. As a result,
+the program prints
+<programlisting>
+ "Used more specific instance"
+ "Used generic instance"
+</programlisting>
+(An alternative possible behaviour, not currently implemented,
+would be to reject module <literal>Help</literal>
+on the grounds that a later instance declaration might overlap the local one.)
+</para>
+<para>
The willingness to be overlapped or incoherent is a property of
the <emphasis>instance declaration</emphasis> itself, controlled by the
presence or otherwise of the <option>-XOverlappingInstances</option>
<sect1 id="other-type-extensions">
<title>Other type system extensions</title>
-<sect2 id="type-restrictions">
-<title>Type signatures</title>
+<sect2 id="explicit-foralls"><title>Explicit universal quantification (forall)</title>
+<para>
+Haskell type signatures are implicitly quantified. When the language option <option>-XExplicitForAll</option>
+is used, the keyword <literal>forall</literal>
+allows us to say exactly what this means. For example:
+</para>
+<para>
+<programlisting>
+ g :: b -> b
+</programlisting>
+means this:
+<programlisting>
+ g :: forall b. (b -> b)
+</programlisting>
+The two are treated identically.
+</para>
+<para>
+Of course <literal>forall</literal> becomes a keyword; you can't use <literal>forall</literal> as
+a type variable any more!
+</para>
+</sect2>
+
-<sect3 id="flexible-contexts"><title>The context of a type signature</title>
+<sect2 id="flexible-contexts"><title>The context of a type signature</title>
<para>
The <option>-XFlexibleContexts</option> flag lifts the Haskell 98 restriction
that the type-class constraints in a type signature must have the
g :: Eq [a] => ...
g :: Ord (T a ()) => ...
</programlisting>
+The flag <option>-XFlexibleContexts</option> also lifts the corresponding
+restriction on class declarations (<xref linkend="superclass-rules"/>) and instance declarations
+(<xref linkend="instance-rules"/>).
</para>
+
<para>
GHC imposes the following restrictions on the constraints in a type signature.
Consider the type:
language omits them; in Haskell 98, all the free type variables of an
explicit source-language type signature are universally quantified,
except for the class type variables in a class declaration. However,
-in GHC, you can give the foralls if you want. See <xref linkend="universal-quantification"/>).
+in GHC, you can give the foralls if you want. See <xref linkend="explicit-foralls"/>).
</para>
<para>
</orderedlist>
</para>
-</sect3>
-
-
</sect2>
</title>
<para>
-Haskell type signatures are implicitly quantified. The new keyword <literal>forall</literal>
-allows us to say exactly what this means. For example:
-</para>
-<para>
-<programlisting>
- g :: b -> b
-</programlisting>
-means this:
-<programlisting>
- g :: forall b. (b -> b)
-</programlisting>
-The two are treated identically.
-</para>
-
-<para>
-However, GHC's type system supports <emphasis>arbitrary-rank</emphasis>
+GHC's type system supports <emphasis>arbitrary-rank</emphasis>
explicit universal quantification in
types.
For example, all the following types are legal:
</itemizedlist>
</para></listitem>
</itemizedlist>
-Of course <literal>forall</literal> becomes a keyword; you can't use <literal>forall</literal> as
-a type variable any more!
</para>
<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
</para>
</sect2>
+<sect2 id="mono-local-binds">
+<title>Monomorphic local bindings</title>
+<para>
+We are actively thinking of simplifying GHC's type system, by <emphasis>not generalising local bindings</emphasis>.
+The rationale is described in the paper
+<ulink url="http://research.microsoft.com/~simonpj/papers/constraints/index.htm">Let should not be generalised</ulink>.
+</para>
+<para>
+The experimental new behaviour is enabled by the flag <option>-XMonoLocalBinds</option>. The effect is
+that local (that is, non-top-level) bindings without a type signature are not generalised at all. You can
+think of it as an extreme (but much more predictable) version of the Monomorphism Restriction.
+If you supply a type signature, then the flag has no effect.
+</para>
+</sect2>
+
</sect1>
<!-- ==================== End of type system extensions ================= -->
have type <literal>Q Exp</literal></para></listitem>
<listitem><para> an type; the spliced expression must
have type <literal>Q Typ</literal></para></listitem>
- <listitem><para> a list of top-level declarations; the spliced expression must have type <literal>Q [Dec]</literal></para></listitem>
+ <listitem><para> a list of top-level declarations; the spliced expression
+ must have type <literal>Q [Dec]</literal></para></listitem>
</itemizedlist>
- </para>
Inside a splice you can can only call functions defined in imported modules,
- not functions defined elsewhere in the same module.</listitem>
-
+ not functions defined elsewhere in the same module.</para></listitem>
<listitem><para>
A expression quotation is written in Oxford brackets, thus:
A quasi-quotation can appear in either a pattern context or an
expression context and is also written in Oxford brackets:
<itemizedlist>
- <listitem><para> <literal>[:<replaceable>varid</replaceable>| ... |]</literal>,
+ <listitem><para> <literal>[$<replaceable>varid</replaceable>| ... |]</literal>,
where the "..." is an arbitrary string; a full description of the
quasi-quotation facility is given in <xref linkend="th-quasiquotation"/>.</para></listitem>
</itemizedlist></para></listitem>
</para>
</listitem>
+ <listitem><para> You may omit the <literal>$(...)</literal> in a top-level declaration splice.
+ Simply writing an expression (rather than a declaration) implies a splice. For example, you can write
+<programlisting>
+module Foo where
+import Bar
+
+f x = x
+
+$(deriveStuff 'f) -- Uses the $(...) notation
+
+g y = y+1
+
+deriveStuff 'g -- Omits the $(...)
+
+h z = z-1
+</programlisting>
+ This abbreviation makes top-level declaration slices quieter and less intimidating.
+ </para></listitem>
+
</itemizedlist>
(Compared to the original paper, there are many differences of detail.
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:
projects / ghc-hetmet.git / blobdiff