</varlistentry>
<varlistentry>
+ <term><option>-farrows</option></term>
+ <indexterm><primary><option>-farrows</option></primary></indexterm>
+ <listitem>
+ <para>See <xref LinkEnd="arrow-notation">. Independent of
+ <option>-fglasgow-exts</option>.</para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
<term><option>-fgenerics</option></term>
<indexterm><primary><option>-fgenerics</option></primary></indexterm>
<listitem>
<sect1 id="template-haskell">
<title>Template Haskell</title>
-<para>Template Haskell allows you to do compile-time meta-programming in Haskell. The background
-the main technical innovations are discussed in "<ulink
+<para>Template Haskell allows you to do compile-time meta-programming in Haskell. There is a "home page" for
+Template Haskell at <ulink url="http://www.haskell.org/th/">
+http://www.haskell.org/th/</ulink>, while
+the background to
+the main technical innovations is discussed in "<ulink
url="http://research.microsoft.com/~simonpj/papers/meta-haskell">
-Template Meta-programming for Haskell</ulink>", in
-Proc Haskell Workshop 2002.
+Template Meta-programming for Haskell</ulink>" (Proc Haskell Workshop 2002).
</para>
<para> The first example from that paper is set out below as a worked example to help get you started.
</sect1>
+<!-- ===================== Arrow notation =================== -->
+
+<sect1 id="arrow-notation">
+<title>Arrow notation
+</title>
+
+<para>Arrows are a generalization of monads introduced by John Hughes.
+For more details, see
+<itemizedlist>
+
+<listitem>
+<para>
+“Generalising Monads to Arrows”,
+John Hughes, in <citetitle>Science of Computer Programming</citetitle> 37,
+pp67–111, May 2000.
+</para>
+</listitem>
+
+<listitem>
+<para>
+“<ulink url="http://www.soi.city.ac.uk/~ross/papers/notation.html">A New Notation for Arrows</ulink>”,
+Ross Paterson, in <citetitle>ICFP</citetitle>, Sep 2001.
+</para>
+</listitem>
+
+<listitem>
+<para>
+“<ulink url="http://www.soi.city.ac.uk/~ross/papers/fop.html">Arrows and Computation</ulink>”,
+Ross Paterson, in <citetitle>The Fun of Programming</citetitle>,
+Palgrave, 2003.
+</para>
+</listitem>
+
+</itemizedlist>
+and the arrows web page at
+<ulink url="http://www.haskell.org/arrows/"><literal>http://www.haskell.org/arrows/</literal></ulink>.
+With the <option>-farrows</option> flag, GHC supports the arrow
+notation described in the second of these papers.
+What follows is a brief introduction to the notation;
+it won't make much sense unless you've read Hughes's paper.
+This notation is translated to ordinary Haskell,
+using combinators from the
+<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>
+module.
+</para>
+
+<para>The extension adds a new kind of expression for defining arrows,
+of the form <literal>proc pat -> cmd</literal>,
+where <literal>proc</literal> is a new keyword.
+The variables of the pattern are bound in the body of the
+<literal>proc</literal>-expression,
+which is a new sort of thing called a <firstterm>command</firstterm>.
+The syntax of commands is as follows:
+<screen>
+cmd ::= exp1 -< exp2
+ | exp1 -<< exp2
+ | do { cstmt1 .. cstmtn ; cmd }
+ | let decls in cmd
+ | if exp then cmd1 else cmd2
+ | case exp of { calts }
+ | cmd1 qop cmd2
+ | (| aexp cmd1 .. cmdn |)
+ | \ pat1 .. patn -> cmd
+ | cmd aexp
+ | ( cmd )
+
+cstmt ::= let decls
+ | pat <- cmd
+ | rec { cstmt1 .. cstmtn }
+ | cmd
+</screen>
+Commands produce values, but (like monadic computations)
+may yield more than one value,
+or none, and may do other things as well.
+For the most part, familiarity with monadic notation is a good guide to
+using commands.
+However the values of expressions, even monadic ones,
+are determined by the values of the variables they contain;
+this is not necessarily the case for commands.
+</para>
+
+<para>
+A simple example of the new notation is the expression
+<screen>
+proc x -> f -< x+1
+</screen>
+We call this a <firstterm>procedure</firstterm> or
+<firstterm>arrow abstraction</firstterm>.
+As with a lambda expression, the variable <literal>x</literal>
+is a new variable bound within the <literal>proc</literal>-expression.
+It refers to the input to the arrow.
+In the above example, <literal>-<</literal> is not an identifier but an
+new reserved symbol used for building commands from an expression of arrow
+type and an expression to be fed as input to that arrow.
+(The weird look will make more sense later.)
+It may be read as analogue of application for arrows.
+The above example is equivalent to the Haskell expression
+<screen>
+arr (\ x -> x+1) >>> f
+</screen>
+That would make no sense if the expression to the left of
+<literal>-<</literal> involves the bound variable <literal>x</literal>.
+More generally, the expression to the left of <literal>-<</literal>
+may not involve any <firstterm>local variable</firstterm>,
+i.e. a variable bound in the current arrow abstraction.
+For such a situation there is a variant <literal>-<<</literal>, as in
+<screen>
+proc x -> f x -<< x+1
+</screen>
+which is equivalent to
+<screen>
+arr (\ x -> (f, x+1)) >>> app
+</screen>
+so in this case the arrow must belong to the <literal>ArrowApply</literal>
+class.
+Such an arrow is equivalent to a monad, so if you're using this form
+you may find a monadic formulation more convenient.
+</para>
+
+<sect2>
+<title>do-notation for commands</title>
+
+<para>
+Another form of command is a form of <literal>do</literal>-notation.
+For example, you can write
+<screen>
+proc x -> do
+ y <- f -< x+1
+ g -< 2*y
+ let z = x+y
+ t <- h -< x*z
+ returnA -< t+z
+</screen>
+You can read this much like ordinary <literal>do</literal>-notation,
+but with commands in place of monadic expressions.
+The first line sends the value of <literal>x+1</literal> as an input to
+the arrow <literal>f</literal>, and matches its output against
+<literal>y</literal>.
+In the next line, the output is discarded.
+The arrow <literal>returnA</literal> is defined in the
+<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>
+module as <literal>arr id</literal>.
+The above example is treated as an abbreviation for
+<screen>
+arr (\ x -> (x, x)) >>>
+ first (arr (\ x -> x+1) >>> f) >>>
+ arr (\ (y, x) -> (y, (x, y))) >>>
+ first (arr (\ y -> 2*y) >>> g) >>>
+ arr snd >>>
+ arr (\ (x, y) -> let z = x+y in ((x, z), z)) >>>
+ first (arr (\ (x, z) -> x*z) >>> h) >>>
+ arr (\ (t, z) -> t+z) >>>
+ returnA
+</screen>
+Note that variables not used later in the composition are projected out.
+After simplification using rewrite rules (see <xref linkEnd="rewrite-rules">)
+defined in the
+<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>
+module, this reduces to
+<screen>
+arr (\ x -> (x+1, x)) >>>
+ first f >>>
+ arr (\ (y, x) -> (2*y, (x, y))) >>>
+ first g >>>
+ arr (\ (_, (x, y)) -> let z = x+y in (x*z, z)) >>>
+ first h >>>
+ arr (\ (t, z) -> t+z)
+</screen>
+which is what you might have written by hand.
+With arrow notation, GHC keeps track of all those tuples of variables for you.
+</para>
+
+<para>
+Note that although the above translation suggests that
+<literal>let</literal>-bound variables like <literal>z</literal> must be
+monomorphic, the actual translation produces Core,
+so polymorphic variables are allowed.
+</para>
+
+<para>
+It's also possible to have mutually recursive bindings,
+using the new <literal>rec</literal> keyword, as in the following example:
+<screen>
+counter :: ArrowCircuit a => a Bool Int
+counter = proc reset -> do
+ rec output <- returnA -< if reset then 0 else next
+ next <- delay 0 -< output+1
+ returnA -< output
+</screen>
+The translation of such forms uses the <literal>loop</literal> combinator,
+so the arrow concerned must belong to the <literal>ArrowLoop</literal> class.
+</para>
+
+</sect2>
+
+<sect2>
+<title>Conditional commands</title>
+
+<para>
+In the previous example, we used a conditional expression to construct the
+input for an arrow.
+Sometimes we want to conditionally execute different commands, as in
+<screen>
+proc (x,y) ->
+ if f x y
+ then g -< x+1
+ else h -< y+2
+</screen>
+which is translated to
+<screen>
+arr (\ (x,y) -> if f x y then Left x else Right y) >>>
+ (arr (\x -> x+1) >>> f) ||| (arr (\y -> y+2) >>> g)
+</screen>
+Since the translation uses <literal>|||</literal>,
+the arrow concerned must belong to the <literal>ArrowChoice</literal> class.
+</para>
+
+<para>
+There are also <literal>case</literal> commands, like
+<screen>
+case input of
+ [] -> f -< ()
+ [x] -> g -< x+1
+ x1:x2:xs -> do
+ y <- h -< (x1, x2)
+ ys <- k -< xs
+ returnA -< y:ys
+</screen>
+The syntax is the same as for <literal>case</literal> expressions,
+except that the bodies of the alternatives are commands rather than expressions.
+The translation is similar to that of <literal>if</literal> commands.
+</para>
+
+</sect2>
+
+<sect2>
+<title>Defining your own control structures</title>
+
+<para>
+As we're seen, arrow notation provides constructs,
+modelled on those for expressions,
+for sequencing, value recursion and conditionals.
+But suitable combinators,
+which you can define in ordinary Haskell,
+may also be used to build new commands out of existing ones.
+The basic idea is that a command defines an arrow from environments to values.
+These environments assign values to the free local variables of the command.
+Thus combinators that produce arrows from arrows
+may also be used to build commands from commands.
+For example, the <literal>ArrowChoice</literal> class includes a combinator
+<programlisting>
+ArrowChoice a => (<+>) :: a e c -> a e c -> a e c
+</programlisting>
+so we can use it to build commands:
+<programlisting>
+expr' = proc x ->
+ returnA -< x
+ <+> do
+ symbol Plus -< ()
+ y <- term -< ()
+ expr' -< x + y
+ <+> do
+ symbol Minus -< ()
+ y <- term -< ()
+ expr' -< x - y
+</programlisting>
+This is equivalent to
+<programlisting>
+expr' = (proc x -> returnA -< x)
+ <+> (proc x -> do
+ symbol Plus -< ()
+ y <- term -< ()
+ expr' -< x + y)
+ <+> (proc x -> do
+ symbol Minus -< ()
+ y <- term -< ()
+ expr' -< x - y)
+</programlisting>
+It is essential that this operator be polymorphic in <literal>e</literal>
+(representing the environment input to the command
+and thence to its subcommands)
+and satisfy the corresponding naturality property
+<screen>
+arr k >>> (f <+> g) = (arr k >>> f) <+> (arr k >>> g)
+</screen>
+at least for strict <literal>k</literal>.
+(This should be automatic if you're not using <literal>seq</literal>.)
+This ensures that environments seen by the subcommands are environments
+of the whole command,
+and also allows the translation to safely trim these environments.
+The operator must also not use any variable defined within the current
+arrow abstraction.
+</para>
+
+<para>
+We could define our own operator
+<programlisting>
+untilA :: ArrowChoice a => a e () -> a e Bool -> a e ()
+untilA body cond = proc x ->
+ if cond x then returnA -< ()
+ else do
+ body -< x
+ untilA body cond -< x
+</programlisting>
+and use it in the same way.
+Of course this infix syntax only makes sense for binary operators;
+there is also a more general syntax involving special brackets:
+<screen>
+proc x -> do
+ y <- f -< x+1
+ (|untilA (increment -< x+y) (within 0.5 -< x)|)
+</screen>
+</para>
+
+</sect2>
+
+<sect2>
+<title>Primitive constructs</title>
+
+<para>
+Some operators will need to pass additional inputs to their subcommands.
+For example, in an arrow type supporting exceptions,
+the operator that attaches an exception handler will wish to pass the
+exception that occurred to the handler.
+Such an operator might have a type
+<screen>
+handleA :: ... => a e c -> a (e,Ex) c -> a e c
+</screen>
+where <literal>Ex</literal> is the type of exceptions handled.
+You could then use this with arrow notation by writing a command
+<screen>
+body `handleA` \ ex -> handler
+</screen>
+so that if an exception is raised in the command <literal>body</literal>,
+the variable <literal>ex</literal> is bound to the value of the exception
+and the command <literal>handler</literal>,
+which typically refers to <literal>ex</literal>, is entered.
+Though the syntax here looks like a functional lambda,
+we are talking about commands, and something different is going on.
+The input to the arrow represented by a command consists of values for
+the free local variables in the command, plus a stack of anonymous values.
+In all the prior examples, this stack was empty.
+In the second argument to <literal>handleA</literal>,
+this stack consists of one value, the value of the exception.
+The command form of lambda merely gives this value a name.
+</para>
+
+<para>
+More concretely,
+the values on the stack are paired to the right of the environment.
+So when designing operators like <literal>handleA</literal> that pass
+extra inputs to their subcommands,
+More precisely, the type of each argument of the operator (and its result)
+should have the form
+<screen>
+a (...(e,t1), ... tn) t
+</screen>
+where <replaceable>e</replaceable> is a polymorphic variable
+(representing the environment)
+and <replaceable>ti</replaceable> are the types of the values on the stack,
+with <replaceable>t1</replaceable> being the <quote>top</quote>.
+The polymorphic variable <replaceable>e</replaceable> must not occur in
+<replaceable>a</replaceable>, <replaceable>ti</replaceable> or
+<replaceable>t</replaceable>.
+However the arrows involved need not be the same.
+Here are some more examples of suitable operators:
+<screen>
+bracketA :: ... => a e b -> a (e,b) c -> a (e,c) d -> a e d
+runReader :: ... => a e c -> a' (e,State) c
+runState :: ... => a e c -> a' (e,State) (c,State)
+</screen>
+We can supply the extra input required by commands built with the last two
+by applying them to ordinary expressions, as in
+<screen>
+proc x -> do
+ s <- ...
+ (|runReader (do { ... })|) s
+</screen>
+which adds <literal>s</literal> to the stack of inputs to the command
+built using <literal>runReader</literal>.
+</para>
+
+<para>
+The command versions of lambda abstraction and application are analogous to
+the expression versions.
+In particular, the beta and eta rules describe equivalences of commands.
+These three features (operators, lambda abstraction and application)
+are the core of the notation; everything else can be built using them,
+though the results would be somewhat clumsy.
+For example, we could simulate <literal>do</literal>-notation by defining
+<programlisting>
+bind :: Arrow a => a e b -> a (e,b) c -> a e c
+u `bind` f = returnA &&& u >>> f
+
+bind_ :: Arrow a => a e b -> a e c -> a e c
+u `bind_` f = u `bind` (arr fst >>> f)
+</programlisting>
+We could simulate <literal>do</literal> by defining
+<programlisting>
+cond :: ArrowChoice a => a e b -> a e b -> a (e,Bool) b
+cond f g = arr (\ (e,b) -> if b then Left e else Right e) >>> f ||| g
+</programlisting>
+</para>
+
+</sect2>
+
+<sect2>
+<title>Differences with the paper</title>
+
+<itemizedlist>
+
+<listitem>
+<para>Instead of a single form of arrow application (arrow tail) with two
+translations, the implementation provides two forms
+<quote><literal>-<</literal></quote> (first-order)
+and <quote><literal>-<<</literal></quote> (higher-order).
+</para>
+</listitem>
+
+<listitem>
+<para>User-defined operators are flagged with banana brackets instead of
+a new <literal>form</literal> keyword.
+</para>
+</listitem>
+
+</itemizedlist>
+
+</sect2>
+
+<sect2>
+<title>Portability</title>
+
+<para>
+Although only GHC implements arrow notation directly,
+there is also a preprocessor
+(available from the
+<ulink url="http://www.haskell.org/arrows/">arrows web page></ulink>)
+that translates arrow notation into Haskell 98
+for use with other Haskell systems.
+You would still want to check arrow programs with GHC;
+tracing type errors in the preprocessor output is not easy.
+Modules intended for both GHC and the preprocessor must observe some
+additional restrictions:
+<itemizedlist>
+
+<listitem>
+<para>
+The module must import
+<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>.
+</para>
+</listitem>
+
+<listitem>
+<para>
+The preprocessor cannot cope with other Haskell extensions.
+These would have to go in separate modules.
+</para>
+</listitem>
+
+<listitem>
+<para>
+Because the preprocessor targets Haskell (rather than Core),
+<literal>let</literal>-bound variables are monomorphic.
+</para>
+</listitem>
+
+</itemizedlist>
+</para>
+
+</sect2>
+
+</sect1>
+
<!-- ==================== ASSERTIONS ================= -->
<sect1 id="sec-assertions">
<para>A <literal>SPECIALIZE</literal> pragma for a function can
be put anywhere its type signature could be put.</para>
- <para>To get very fancy, you can also specify a named function
- to use for the specialised value, as in:</para>
-
+<para>A <literal>SPECIALIZE</literal> has the effect of generating (a) a specialised
+version of the function and (b) a rewrite rule (see <xref linkend="rules">) that
+rewrites a call to the un-specialised function into a call to the specialised
+one. You can, instead, provide your own specialised function and your own rewrite rule.
+For example, suppose that:
<programlisting>
-{-# RULES "hammeredLookup" hammeredLookup = blah #-}
+ genericLookup :: Ord a => Table a b -> a -> b
+ intLookup :: Table Int b -> Int -> b
</programlisting>
-
- <para>where <literal>blah</literal> is an implementation of
- <literal>hammerdLookup</literal> written specialy for
- <literal>Widget</literal> lookups. It's <emphasis>Your
+where <literal>intLookup</literal> is an implementation of <literal>genericLookup</literal>
+that works very fast for keys of type <literal>Int</literal>. Then you can write the rule
+<programlisting>
+ {-# RULES "intLookup" genericLookup = intLookup #-}
+</programlisting>
+(see <xref linkend="rule-spec">). It is <emphasis>Your
Responsibility</emphasis> to make sure that
- <function>blah</function> really behaves as a specialised
- version of <function>hammeredLookup</function>!!!</para>
-
- <para>Note we use the <literal>RULE</literal> pragma here to
- indicate that <literal>hammeredLookup</literal> applied at a
- certain type should be replaced by <literal>blah</literal>. See
- <xref linkend="rules"> for more information on
- <literal>RULES</literal>.</para>
+ <function>intLookup</function> really behaves as a specialised
+ version of <function>genericLookup</function>!!!</para>
<para>An example in which using <literal>RULES</literal> for
specialisation will Win Big:
<programlisting>
-toDouble :: Real a => a -> Double
-toDouble = fromRational . toRational
+ toDouble :: Real a => a -> Double
+ toDouble = fromRational . toRational
-{-# RULES "toDouble/Int" toDouble = i2d #-}
-i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
+ {-# RULES "toDouble/Int" toDouble = i2d #-}
+ i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
</programlisting>
The <function>i2d</function> function is virtually one machine
<para>
The programmer can specify rewrite rules as part of the source program
-(in a pragma). GHC applies these rewrite rules wherever it can.
+(in a pragma). GHC applies these rewrite rules wherever it can, provided (a)
+the <option>-O</option> flag (<xref LinkEnd="options-optimise">) is on,
+and (b) the <option>-frules-off</option> flag
+(<xref LinkEnd="options-f">) is not specified.
</para>
<para>
</para>
-<para>
+ <para>
So, for example, the following should generate no intermediate lists:
<programlisting>
projects / ghc-hetmet.git / blobdiff