</varlistentry>
<varlistentry>
- <term><option>-fwith</option>:</term>
- <indexterm><primary><option>-fwith</option></primary></indexterm>
- <listitem>
- <para>This option enables the deprecated <literal>with</literal>
- keyword for implicit parameters; it is merely provided for backwards
- compatibility.
- It is independent of the <option>-fglasgow-exts</option>
- flag. </para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
<term><option>-fno-monomorphism-restriction</option>:</term>
<indexterm><primary><option>-fno-monomorphism-restriction</option></primary></indexterm>
<listitem>
</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>
</listitem>
</varlistentry>
- <varlistentry>
- <term><option>-fno-implicit-prelude</option></term>
- <listitem>
- <para><indexterm><primary>-fno-implicit-prelude
- option</primary></indexterm> GHC normally imports
- <filename>Prelude.hi</filename> files for you. If you'd
- rather it didn't, then give it a
- <option>-fno-implicit-prelude</option> option. The idea
- is that you can then import a Prelude of your own. (But
- don't call it <literal>Prelude</literal>; the Haskell
- module namespace is flat, and you must not conflict with
- any Prelude module.)</para>
-
- <para>Even though you have not imported the Prelude, most of
- the built-in syntax still refers to the built-in Haskell
- Prelude types and values, as specified by the Haskell
- Report. For example, the type <literal>[Int]</literal>
- still means <literal>Prelude.[] Int</literal>; tuples
- continue to refer to the standard Prelude tuples; the
- translation for list comprehensions continues to use
- <literal>Prelude.map</literal> etc.</para>
-
- <para>However, <option>-fno-implicit-prelude</option> does
- change the handling of certain built-in syntax: see
- <xref LinkEnd="rebindable-syntax">.</para>
+ <varlistentry>
+ <term><option>-fno-implicit-prelude</option></term>
+ <listitem>
+ <para><indexterm><primary>-fno-implicit-prelude
+ option</primary></indexterm> GHC normally imports
+ <filename>Prelude.hi</filename> files for you. If you'd
+ rather it didn't, then give it a
+ <option>-fno-implicit-prelude</option> option. The idea is
+ that you can then import a Prelude of your own. (But don't
+ call it <literal>Prelude</literal>; the Haskell module
+ namespace is flat, and you must not conflict with any
+ Prelude module.)</para>
+
+ <para>Even though you have not imported the Prelude, most of
+ the built-in syntax still refers to the built-in Haskell
+ Prelude types and values, as specified by the Haskell
+ Report. For example, the type <literal>[Int]</literal>
+ still means <literal>Prelude.[] Int</literal>; tuples
+ continue to refer to the standard Prelude tuples; the
+ translation for list comprehensions continues to use
+ <literal>Prelude.map</literal> etc.</para>
+
+ <para>However, <option>-fno-implicit-prelude</option> does
+ change the handling of certain built-in syntax: see <xref
+ LinkEnd="rebindable-syntax">.</para>
+ </listitem>
+ </varlistentry>
- </listitem>
- </varlistentry>
+ <varlistentry>
+ <term><option>-fth</option></term>
+ <listitem>
+ <para>Enables Template Haskell (see <xref
+ linkend="template-haskell">). Currently also implied by
+ <option>-fglasgow-exts</option>.</para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term><option>-fimplicit-params</option></term>
+ <listitem>
+ <para>Enables implicit parameters (see <xref
+ linkend="implicit-parameters">). Currently also implied by
+ <option>-fglasgow-exts</option>.</para>
+ </listitem>
+ </varlistentry>
</variablelist>
</sect1>
import qualified Control.Monad.ST.Strict as ST
</programlisting>
- <para>Hierarchical modules have an impact on the way that GHC
- searches for files. For a description, see <xref
- linkend="finding-hierarchical-modules">.</para>
+ <para>For details on how GHC searches for source and interface
+ files in the presence of hierarchical modules, see <xref
+ linkend="search-path">.</para>
<para>GHC comes with a large collection of libraries arranged
hierarchically; see the accompanying library documentation.
<sect1 id="type-extensions">
<title>Type system extensions</title>
-<sect2 id="nullary-types">
+
+<sect2>
+<title>Data types and type synonyms</title>
+
+<sect3 id="nullary-types">
<title>Data types with no constructors</title>
<para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
<para>Such data types have only one value, namely bottom.
Nevertheless, they can be useful when defining "phantom types".</para>
-</sect2>
+</sect3>
-<sect2 id="infix-tycons">
+<sect3 id="infix-tycons">
<title>Infix type constructors</title>
<para>
</itemizedlist>
</para>
-</sect2>
+</sect3>
-<sect2 id="sec-kinding">
-<title>Explicitly-kinded quantification</title>
+<sect3 id="type-synonyms">
+<title>Liberalised type synonyms</title>
<para>
-Haskell infers the kind of each type variable. Sometimes it is nice to be able
-to give the kind explicitly as (machine-checked) documentation,
-just as it is nice to give a type signature for a function. On some occasions,
-it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
-John Hughes had to define the data type:
-<Screen>
- data Set cxt a = Set [a]
- | Unused (cxt a -> ())
-</Screen>
-The only use for the <literal>Unused</literal> constructor was to force the correct
-kind for the type variable <literal>cxt</literal>.
-</para>
-<para>
-GHC now instead allows you to specify the kind of a type variable directly, wherever
-a type variable is explicitly bound. Namely:
+Type synonmys are like macros at the type level, and
+GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
+That means that GHC can be very much more liberal about type synonyms than Haskell 98:
<itemizedlist>
-<listitem><para><literal>data</literal> declarations:
-<Screen>
- data Set (cxt :: * -> *) a = Set [a]
-</Screen></para></listitem>
-<listitem><para><literal>type</literal> declarations:
-<Screen>
- type T (f :: * -> *) = f Int
-</Screen></para></listitem>
-<listitem><para><literal>class</literal> declarations:
-<Screen>
- class (Eq a) => C (f :: * -> *) a where ...
-</Screen></para></listitem>
-<listitem><para><literal>forall</literal>'s in type signatures:
-<Screen>
- f :: forall (cxt :: * -> *). Set cxt Int
-</Screen></para></listitem>
-</itemizedlist>
-</para>
+<listitem> <para>You can write a <literal>forall</literal> (including overloading)
+in a type synonym, thus:
+<programlisting>
+ type Discard a = forall b. Show b => a -> b -> (a, String)
-<para>
-The parentheses are required. Some of the spaces are required too, to
-separate the lexemes. If you write <literal>(f::*->*)</literal> you
-will get a parse error, because "<literal>::*->*</literal>" is a
-single lexeme in Haskell.
-</para>
+ f :: Discard a
+ f x y = (x, show y)
-<para>
-As part of the same extension, you can put kind annotations in types
-as well. Thus:
-<Screen>
- f :: (Int :: *) -> Int
- g :: forall a. a -> (a :: *)
-</Screen>
-The syntax is
-<Screen>
- atype ::= '(' ctype '::' kind ')
-</Screen>
-The parentheses are required.
+ g :: Discard Int -> (Int,Bool) -- A rank-2 type
+ g f = f Int True
+</programlisting>
</para>
-</sect2>
+</listitem>
+<listitem><para>
+You can write an unboxed tuple in a type synonym:
+<programlisting>
+ type Pr = (# Int, Int #)
-<sect2 id="class-method-types">
-<title>Class method types
-</title>
-<para>
-Haskell 98 prohibits class method types to mention constraints on the
-class type variable, thus:
+ h :: Int -> Pr
+ h x = (# x, x #)
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a forall type:
<programlisting>
- class Seq s a where
- fromList :: [a] -> s a
- elem :: Eq a => a -> s a -> Bool
+ type Foo a = a -> a -> Bool
+
+ f :: Foo (forall b. b->b)
</programlisting>
-The type of <literal>elem</literal> is illegal in Haskell 98, because it
-contains the constraint <literal>Eq a</literal>, constrains only the
-class type variable (in this case <literal>a</literal>).
+After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
+<programlisting>
+ f :: (forall b. b->b) -> (forall b. b->b) -> Bool
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a partially applied type synonym:
+<programlisting>
+ type Generic i o = forall x. i x -> o x
+ type Id x = x
+
+ foo :: Generic Id []
+</programlisting>
+After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
+<programlisting>
+ foo :: forall x. x -> [x]
+</programlisting>
+</para></listitem>
+
+</itemizedlist>
</para>
+
<para>
-With the <option>-fglasgow-exts</option> GHC lifts this restriction.
+GHC currently does kind checking before expanding synonyms (though even that
+could be changed.)
+</para>
+<para>
+After expanding type synonyms, GHC does validity checking on types, looking for
+the following mal-formedness which isn't detected simply by kind checking:
+<itemizedlist>
+<listitem><para>
+Type constructor applied to a type involving for-alls.
+</para></listitem>
+<listitem><para>
+Unboxed tuple on left of an arrow.
+</para></listitem>
+<listitem><para>
+Partially-applied type synonym.
+</para></listitem>
+</itemizedlist>
+So, for example,
+this will be rejected:
+<programlisting>
+ type Pr = (# Int, Int #)
+
+ h :: Pr -> Int
+ h x = ...
+</programlisting>
+because GHC does not allow unboxed tuples on the left of a function arrow.
</para>
+</sect3>
-</sect2>
-<sect2 id="multi-param-type-classes">
-<title>Multi-parameter type classes
+<sect3 id="existential-quantification">
+<title>Existentially quantified data constructors
</title>
<para>
-This section documents GHC's implementation of multi-parameter type
-classes. There's lots of background in the paper <ULink
-URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
-classes: exploring the design space</ULink > (Simon Peyton Jones, Mark
-Jones, Erik Meijer).
+The idea of using existential quantification in data type declarations
+was suggested by Laufer (I believe, thought doubtless someone will
+correct me), and implemented in Hope+. It's been in Lennart
+Augustsson's <Command>hbc</Command> Haskell compiler for several years, and
+proved very useful. Here's the idea. Consider the declaration:
</para>
-
-<sect3 id="type-restrictions">
-<title>Types</title>
-
<para>
-GHC imposes the following restrictions on the form of a qualified
-type, whether declared in a type signature
-or inferred. Consider the type:
<programlisting>
- forall tv1..tvn (c1, ...,cn) => type
+ data Foo = forall a. MkFoo a (a -> Bool)
+ | Nil
</programlisting>
-(Here, I write the "foralls" explicitly, although the Haskell source
-language omits them; in Haskell 1.4, 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">).
</para>
<para>
-
-<OrderedList>
-<listitem>
+The data type <literal>Foo</literal> has two constructors with types:
+</para>
<para>
- <emphasis>Each universally quantified type variable
-<literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
-
-A type variable is "reachable" if it it is functionally dependent
-(see <xref linkend="functional-dependencies">)
-on the type variables free in <literal>type</literal>.
-The reason for this is that a value with a type that does not obey
-this restriction could not be used without introducing
-ambiguity.
-Here, for example, is an illegal type:
-
<programlisting>
- forall a. Eq a => Int
+ MkFoo :: forall a. a -> (a -> Bool) -> Foo
+ Nil :: Foo
</programlisting>
-
-When a value with this type was used, the constraint <literal>Eq tv</literal>
-would be introduced where <literal>tv</literal> is a fresh type variable, and
-(in the dictionary-translation implementation) the value would be
-applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
-can never know which instance of <literal>Eq</literal> to use because we never
-get any more information about <literal>tv</literal>.
-
</para>
-</listitem>
-<listitem>
<para>
- <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
-universally quantified type variables <literal>tvi</literal></emphasis>.
-
-For example, this type is OK because <literal>C a b</literal> mentions the
-universally quantified type variable <literal>b</literal>:
+Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
+does not appear in the data type itself, which is plain <literal>Foo</literal>.
+For example, the following expression is fine:
+</para>
+<para>
<programlisting>
- forall a. C a b => burble
+ [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
</programlisting>
+</para>
-The next type is illegal because the constraint <literal>Eq b</literal> does not
-mention <literal>a</literal>:
+<para>
+Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
+<function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
+isUpper</function> packages a character with a compatible function. These
+two things are each of type <literal>Foo</literal> and can be put in a list.
+</para>
+
+<para>
+What can we do with a value of type <literal>Foo</literal>?. In particular,
+what happens when we pattern-match on <function>MkFoo</function>?
+</para>
+<para>
<programlisting>
- forall a. Eq b => burble
+ f (MkFoo val fn) = ???
</programlisting>
+</para>
-The reason for this restriction is milder than the other one. The
-excluded types are never useful or necessary (because the offending
-context doesn't need to be witnessed at this point; it can be floated
-out). Furthermore, floating them out increases sharing. Lastly,
-excluding them is a conservative choice; it leaves a patch of
-territory free in case we need it later.
+<para>
+Since all we know about <literal>val</literal> and <function>fn</function> is that they
+are compatible, the only (useful) thing we can do with them is to
+apply <function>fn</function> to <literal>val</literal> to get a boolean. For example:
+</para>
+
+<para>
+
+<programlisting>
+ f :: Foo -> Bool
+ f (MkFoo val fn) = fn val
+</programlisting>
</para>
-</listitem>
-</OrderedList>
+<para>
+What this allows us to do is to package heterogenous values
+together with a bunch of functions that manipulate them, and then treat
+that collection of packages in a uniform manner. You can express
+quite a bit of object-oriented-like programming this way.
+</para>
+
+<sect4 id="existential">
+<title>Why existential?
+</title>
+
+<para>
+What has this to do with <emphasis>existential</emphasis> quantification?
+Simply that <function>MkFoo</function> has the (nearly) isomorphic type
+</para>
+
+<para>
+
+<programlisting>
+ MkFoo :: (exists a . (a, a -> Bool)) -> Foo
+</programlisting>
+
+</para>
+
+<para>
+But Haskell programmers can safely think of the ordinary
+<emphasis>universally</emphasis> quantified type given above, thereby avoiding
+adding a new existential quantification construct.
+</para>
+
+</sect4>
+<sect4>
+<title>Type classes</title>
+
+<para>
+An easy extension (implemented in <Command>hbc</Command>) is to allow
+arbitrary contexts before the constructor. For example:
</para>
+<para>
+
+<programlisting>
+data Baz = forall a. Eq a => Baz1 a a
+ | forall b. Show b => Baz2 b (b -> b)
+</programlisting>
+
+</para>
<para>
-Unlike Haskell 1.4, constraints in types do <emphasis>not</emphasis> have to be of
-the form <emphasis>(class type-variables)</emphasis>. Thus, these type signatures
-are perfectly OK
+The two constructors have the types you'd expect:
</para>
<para>
<programlisting>
- f :: Eq (m a) => [m a] -> [m a]
- g :: Eq [a] => ...
+Baz1 :: forall a. Eq a => a -> a -> Baz
+Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
+</programlisting>
+
+</para>
+
+<para>
+But when pattern matching on <function>Baz1</function> the matched values can be compared
+for equality, and when pattern matching on <function>Baz2</function> the first matched
+value can be converted to a string (as well as applying the function to it).
+So this program is legal:
+</para>
+
+<para>
+
+<programlisting>
+ f :: Baz -> String
+ f (Baz1 p q) | p == q = "Yes"
+ | otherwise = "No"
+ f (Baz2 v fn) = show (fn v)
+</programlisting>
+
+</para>
+
+<para>
+Operationally, in a dictionary-passing implementation, the
+constructors <function>Baz1</function> and <function>Baz2</function> must store the
+dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
+extract it on pattern matching.
+</para>
+
+<para>
+Notice the way that the syntax fits smoothly with that used for
+universal quantification earlier.
+</para>
+
+</sect4>
+
+<sect4>
+<title>Restrictions</title>
+
+<para>
+There are several restrictions on the ways in which existentially-quantified
+constructors can be use.
+</para>
+
+<para>
+
+<itemizedlist>
+<listitem>
+
+<para>
+ When pattern matching, each pattern match introduces a new,
+distinct, type for each existential type variable. These types cannot
+be unified with any other type, nor can they escape from the scope of
+the pattern match. For example, these fragments are incorrect:
+
+
+<programlisting>
+f1 (MkFoo a f) = a
+</programlisting>
+
+
+Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
+is the result of <function>f1</function>. One way to see why this is wrong is to
+ask what type <function>f1</function> has:
+
+
+<programlisting>
+ f1 :: Foo -> a -- Weird!
+</programlisting>
+
+
+What is this "<literal>a</literal>" in the result type? Clearly we don't mean
+this:
+
+
+<programlisting>
+ f1 :: forall a. Foo -> a -- Wrong!
+</programlisting>
+
+
+The original program is just plain wrong. Here's another sort of error
+
+
+<programlisting>
+ f2 (Baz1 a b) (Baz1 p q) = a==q
+</programlisting>
+
+
+It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
+<literal>a==q</literal> is wrong because it equates the two distinct types arising
+from the two <function>Baz1</function> constructors.
+
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+You can't pattern-match on an existentially quantified
+constructor in a <literal>let</literal> or <literal>where</literal> group of
+bindings. So this is illegal:
+
+
+<programlisting>
+ f3 x = a==b where { Baz1 a b = x }
+</programlisting>
+
+Instead, use a <literal>case</literal> expression:
+
+<programlisting>
+ f3 x = case x of Baz1 a b -> a==b
+</programlisting>
+
+In general, you can only pattern-match
+on an existentially-quantified constructor in a <literal>case</literal> expression or
+in the patterns of a function definition.
+
+The reason for this restriction is really an implementation one.
+Type-checking binding groups is already a nightmare without
+existentials complicating the picture. Also an existential pattern
+binding at the top level of a module doesn't make sense, because it's
+not clear how to prevent the existentially-quantified type "escaping".
+So for now, there's a simple-to-state restriction. We'll see how
+annoying it is.
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+You can't use existential quantification for <literal>newtype</literal>
+declarations. So this is illegal:
+
+
+<programlisting>
+ newtype T = forall a. Ord a => MkT a
</programlisting>
+
+Reason: a value of type <literal>T</literal> must be represented as a
+pair of a dictionary for <literal>Ord t</literal> and a value of type
+<literal>t</literal>. That contradicts the idea that
+<literal>newtype</literal> should have no concrete representation.
+You can get just the same efficiency and effect by using
+<literal>data</literal> instead of <literal>newtype</literal>. If
+there is no overloading involved, then there is more of a case for
+allowing an existentially-quantified <literal>newtype</literal>,
+because the <literal>data</literal> version does carry an
+implementation cost, but single-field existentially quantified
+constructors aren't much use. So the simple restriction (no
+existential stuff on <literal>newtype</literal>) stands, unless there
+are convincing reasons to change it.
+
+
</para>
+</listitem>
+<listitem>
<para>
-This choice recovers principal types, a property that Haskell 1.4 does not have.
+ You can't use <literal>deriving</literal> to define instances of a
+data type with existentially quantified data constructors.
+
+Reason: in most cases it would not make sense. For example:#
+
+<programlisting>
+data T = forall a. MkT [a] deriving( Eq )
+</programlisting>
+
+To derive <literal>Eq</literal> in the standard way we would need to have equality
+between the single component of two <function>MkT</function> constructors:
+
+<programlisting>
+instance Eq T where
+ (MkT a) == (MkT b) = ???
+</programlisting>
+
+But <VarName>a</VarName> and <VarName>b</VarName> have distinct types, and so can't be compared.
+It's just about possible to imagine examples in which the derived instance
+would make sense, but it seems altogether simpler simply to prohibit such
+declarations. Define your own instances!
+</para>
+</listitem>
+
+</itemizedlist>
+
</para>
+</sect4>
</sect3>
-<sect3>
+</sect2>
+
+
+
+<sect2 id="multi-param-type-classes">
<title>Class declarations</title>
<para>
-
+This section documents GHC's implementation of multi-parameter type
+classes. There's lots of background in the paper <ULink
+URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
+classes: exploring the design space</ULink > (Simon Peyton Jones, Mark
+Jones, Erik Meijer).
+</para>
+<para>
+There are the following constraints on class declarations:
<OrderedList>
<listitem>
</listitem>
</OrderedList>
-
</para>
-</sect3>
-
-<sect3 id="instance-decls">
-<title>Instance declarations</title>
-
-<para>
-
-<OrderedList>
-<listitem>
-
+<sect3 id="class-method-types">
+<title>Class method types</title>
<para>
- <emphasis>Instance declarations may not overlap</emphasis>. The two instance
-declarations
-
+Haskell 98 prohibits class method types to mention constraints on the
+class type variable, thus:
+<programlisting>
+ class Seq s a where
+ fromList :: [a] -> s a
+ elem :: Eq a => a -> s a -> Bool
+</programlisting>
+The type of <literal>elem</literal> is illegal in Haskell 98, because it
+contains the constraint <literal>Eq a</literal>, constrains only the
+class type variable (in this case <literal>a</literal>).
+</para>
+<para>
+With the <option>-fglasgow-exts</option> GHC lifts this restriction.
+</para>
+
+</sect3>
+
+</sect2>
+
+<sect2 id="type-restrictions">
+<title>Type signatures</title>
+
+<sect3><title>The context of a type signature</title>
+<para>
+Unlike Haskell 98, constraints in types do <emphasis>not</emphasis> have to be of
+the form <emphasis>(class type-variable)</emphasis> or
+<emphasis>(class (type-variable type-variable ...))</emphasis>. Thus,
+these type signatures are perfectly OK
+<programlisting>
+ g :: Eq [a] => ...
+ g :: Ord (T a ()) => ...
+</programlisting>
+</para>
+<para>
+GHC imposes the following restrictions on the constraints in a type signature.
+Consider the type:
+
+<programlisting>
+ forall tv1..tvn (c1, ...,cn) => type
+</programlisting>
+
+(Here, we write the "foralls" explicitly, although the Haskell source
+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">).
+</para>
+
+<para>
+
+<OrderedList>
+<listitem>
+
+<para>
+ <emphasis>Each universally quantified type variable
+<literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
+
+A type variable is "reachable" if it it is functionally dependent
+(see <xref linkend="functional-dependencies">)
+on the type variables free in <literal>type</literal>.
+The reason for this is that a value with a type that does not obey
+this restriction could not be used without introducing
+ambiguity.
+Here, for example, is an illegal type:
+
+
+<programlisting>
+ forall a. Eq a => Int
+</programlisting>
+
+
+When a value with this type was used, the constraint <literal>Eq tv</literal>
+would be introduced where <literal>tv</literal> is a fresh type variable, and
+(in the dictionary-translation implementation) the value would be
+applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
+can never know which instance of <literal>Eq</literal> to use because we never
+get any more information about <literal>tv</literal>.
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+ <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
+universally quantified type variables <literal>tvi</literal></emphasis>.
+
+For example, this type is OK because <literal>C a b</literal> mentions the
+universally quantified type variable <literal>b</literal>:
+
+
+<programlisting>
+ forall a. C a b => burble
+</programlisting>
+
+
+The next type is illegal because the constraint <literal>Eq b</literal> does not
+mention <literal>a</literal>:
+
+
+<programlisting>
+ forall a. Eq b => burble
+</programlisting>
+
+
+The reason for this restriction is milder than the other one. The
+excluded types are never useful or necessary (because the offending
+context doesn't need to be witnessed at this point; it can be floated
+out). Furthermore, floating them out increases sharing. Lastly,
+excluding them is a conservative choice; it leaves a patch of
+territory free in case we need it later.
+
+</para>
+</listitem>
+
+</OrderedList>
+
+</para>
+</sect3>
+
+<sect3 id="hoist">
+<title>For-all hoisting</title>
+<para>
+It is often convenient to use generalised type synonyms (see <xref linkend="type-synonyms">) at the right hand
+end of an arrow, thus:
+<programlisting>
+ type Discard a = forall b. a -> b -> a
+
+ g :: Int -> Discard Int
+ g x y z = x+y
+</programlisting>
+Simply expanding the type synonym would give
+<programlisting>
+ g :: Int -> (forall b. Int -> b -> Int)
+</programlisting>
+but GHC "hoists" the <literal>forall</literal> to give the isomorphic type
+<programlisting>
+ g :: forall b. Int -> Int -> b -> Int
+</programlisting>
+In general, the rule is this: <emphasis>to determine the type specified by any explicit
+user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly
+performs the transformation:</emphasis>
+<programlisting>
+ <emphasis>type1</emphasis> -> forall a1..an. <emphasis>context2</emphasis> => <emphasis>type2</emphasis>
+==>
+ forall a1..an. <emphasis>context2</emphasis> => <emphasis>type1</emphasis> -> <emphasis>type2</emphasis>
+</programlisting>
+(In fact, GHC tries to retain as much synonym information as possible for use in
+error messages, but that is a usability issue.) This rule applies, of course, whether
+or not the <literal>forall</literal> comes from a synonym. For example, here is another
+valid way to write <literal>g</literal>'s type signature:
+<programlisting>
+ g :: Int -> Int -> forall b. b -> Int
+</programlisting>
+</para>
+<para>
+When doing this hoisting operation, GHC eliminates duplicate constraints. For
+example:
+<programlisting>
+ type Foo a = (?x::Int) => Bool -> a
+ g :: Foo (Foo Int)
+</programlisting>
+means
+<programlisting>
+ g :: (?x::Int) => Bool -> Bool -> Int
+</programlisting>
+</para>
+</sect3>
+
+
+</sect2>
+
+<sect2 id="instance-decls">
+<title>Instance declarations</title>
+
+<sect3>
+<title>Overlapping instances</title>
+<para>
+In general, <emphasis>instance declarations may not overlap</emphasis>. The two instance
+declarations
+
<programlisting>
instance context1 => C type1 where ...
to look at ones that can't possibly be of use in the module currently
being compiled, in the interests of efficiency. (Perhaps we should
change that decision, at least for <literal>Main</literal>.)
-
</para>
-</listitem>
-<listitem>
-
-<para>
- <emphasis>There are no restrictions on the type in an instance
-<emphasis>head</emphasis>, except that at least one must not be a type variable</emphasis>.
-The instance "head" is the bit after the "=>" in an instance decl. For
-example, these are OK:
-
-
-<programlisting>
- instance C Int a where ...
-
- instance D (Int, Int) where ...
-
- instance E [[a]] where ...
-</programlisting>
-
-
-Note that instance heads <emphasis>may</emphasis> contain repeated type variables.
-For example, this is OK:
-
-
-<programlisting>
- instance Stateful (ST s) (MutVar s) where ...
-</programlisting>
+</sect3>
-See <xref linkend="undecidable-instances"> for an experimental
-extension to lift this restriction.
-</para>
-</listitem>
-<listitem>
+<sect3>
+<title>Type synonyms in the instance head</title>
<para>
- <emphasis>Unlike Haskell 1.4, instance heads may use type
-synonyms</emphasis>. As always, using a type synonym is just shorthand for
+<emphasis>Unlike Haskell 98, instance heads may use type
+synonyms</emphasis>. (The instance "head" is the bit after the "=>" in an instance decl.)
+As always, using a type synonym is just shorthand for
writing the RHS of the type synonym definition. For example:
reversed, but it makes sense to me.
</para>
-</listitem>
-<listitem>
+</sect3>
-<para>
-<emphasis>The types in an instance-declaration <emphasis>context</emphasis> must all
-be type variables</emphasis>. Thus
+<sect3 id="undecidable-instances">
+<title>Undecidable instances</title>
+<para>An instance declaration must normally obey the following rules:
+<orderedlist>
+<listitem><para>At least one of the types in the <emphasis>head</emphasis> of
+an instance declaration <emphasis>must not</emphasis> be a type variable.
+For example, these are OK:
<programlisting>
-instance C a b => Eq (a,b) where ...
-</programlisting>
+ instance C Int a where ...
+ instance D (Int, Int) where ...
-is OK, but
+ instance E [[a]] where ...
+</programlisting>
+but this is not:
+<programlisting>
+ instance F a where ...
+</programlisting>
+Note that instance heads <emphasis>may</emphasis> contain repeated type variables.
+For example, this is OK:
+<programlisting>
+ instance Stateful (ST s) (MutVar s) where ...
+</programlisting>
+</para>
+</listitem>
+<listitem>
+<para>All of the types in the <emphasis>context</emphasis> of
+an instance declaration <emphasis>must</emphasis> be type variables.
+Thus
+<programlisting>
+instance C a b => Eq (a,b) where ...
+</programlisting>
+is OK, but
<programlisting>
instance C Int b => Foo b where ...
</programlisting>
-
-
-is not OK. See <xref linkend="undecidable-instances"> for an experimental
-extension to lift this restriction.
-
-
-
+is not OK.
</para>
</listitem>
-
</OrderedList>
-
-</para>
-
-</sect3>
-
-</sect2>
-
-<sect2 id="undecidable-instances">
-<title>Undecidable instances</title>
-
-<para>The rules for instance declarations state that:
-<itemizedlist>
-<listitem><para>At least one of the types in the <emphasis>head</emphasis> of
-an instance declaration <emphasis>must not</emphasis> be a type variable.
-</para></listitem>
-<listitem><para>All of the types in the <emphasis>context</emphasis> of
-an instance declaration <emphasis>must</emphasis> be type variables.
-</para></listitem>
-</itemizedlist>
These restrictions ensure that
context reduction terminates: each reduction step removes one type
constructor. For example, the following would make the type checker
I'm on the lookout for a less brutal solution: a simple rule that preserves decidability while
allowing these idioms interesting idioms.
</para>
+</sect3>
+
+
</sect2>
<sect2 id="implicit-parameters">
-<title>Implicit parameters
-</title>
+<title>Implicit parameters</title>
<para> Implicit paramters are implemented as described in
"Implicit parameters: dynamic scoping with static types",
27th ACM Symposium on Principles of Programming Languages (POPL'00),
Boston, Jan 2000.
</para>
-<para>(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.)</para>
+
+<para>(Most of the following, stil rather incomplete, documentation is
+due to Jeff Lewis.)</para>
+
+<para>Implicit parameter support is enabled with the option
+<option>-fimplicit-params</option>.</para>
+
<para>
A variable is called <emphasis>dynamically bound</emphasis> when it is bound by the calling
context of a function and <emphasis>statically bound</emphasis> when bound by the callee's
</sect2>
<sect2 id="linear-implicit-parameters">
-<title>Linear implicit parameters
-</title>
+<title>Linear implicit parameters</title>
<para>
Linear implicit parameters are an idea developed by Koen Claessen,
Mark Shields, and Simon PJ. They address the long-standing
</sect2>
-<sect2 id="universal-quantification">
-<title>Arbitrary-rank polymorphism
-</title>
+
+<sect2 id="sec-kinding">
+<title>Explicitly-kinded quantification</title>
+
+<para>
+Haskell infers the kind of each type variable. Sometimes it is nice to be able
+to give the kind explicitly as (machine-checked) documentation,
+just as it is nice to give a type signature for a function. On some occasions,
+it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
+John Hughes had to define the data type:
+<Screen>
+ data Set cxt a = Set [a]
+ | Unused (cxt a -> ())
+</Screen>
+The only use for the <literal>Unused</literal> constructor was to force the correct
+kind for the type variable <literal>cxt</literal>.
+</para>
+<para>
+GHC now instead allows you to specify the kind of a type variable directly, wherever
+a type variable is explicitly bound. Namely:
+<itemizedlist>
+<listitem><para><literal>data</literal> declarations:
+<Screen>
+ data Set (cxt :: * -> *) a = Set [a]
+</Screen></para></listitem>
+<listitem><para><literal>type</literal> declarations:
+<Screen>
+ type T (f :: * -> *) = f Int
+</Screen></para></listitem>
+<listitem><para><literal>class</literal> declarations:
+<Screen>
+ class (Eq a) => C (f :: * -> *) a where ...
+</Screen></para></listitem>
+<listitem><para><literal>forall</literal>'s in type signatures:
+<Screen>
+ f :: forall (cxt :: * -> *). Set cxt Int
+</Screen></para></listitem>
+</itemizedlist>
+</para>
+
+<para>
+The parentheses are required. Some of the spaces are required too, to
+separate the lexemes. If you write <literal>(f::*->*)</literal> you
+will get a parse error, because "<literal>::*->*</literal>" is a
+single lexeme in Haskell.
+</para>
+
+<para>
+As part of the same extension, you can put kind annotations in types
+as well. Thus:
+<Screen>
+ f :: (Int :: *) -> Int
+ g :: forall a. a -> (a :: *)
+</Screen>
+The syntax is
+<Screen>
+ atype ::= '(' ctype '::' kind ')
+</Screen>
+The parentheses are required.
+</para>
+</sect2>
+
+
+<sect2 id="universal-quantification">
+<title>Arbitrary-rank polymorphism
+</title>
<para>
Haskell type signatures are implicitly quantified. The new keyword <literal>forall</literal>
shows, the polymorphic type on the left of the function arrow can be overloaded.
</para>
<para>
-The functions <literal>f3</literal> and <literal>g3</literal> have rank-3 types;
-they have rank-2 types on the left of a function arrow.
+The function <literal>f3</literal> has a rank-3 type;
+it has rank-2 types on the left of a function arrow.
</para>
<para>
GHC allows types of arbitrary rank; you can nest <literal>forall</literal>s
<listitem> <para> On the left of a function arrow </para> </listitem>
<listitem> <para> On the right of a function arrow (see <xref linkend="hoist">) </para> </listitem>
<listitem> <para> As the argument of a constructor, or type of a field, in a data type declaration. For
-example, any of the <literal>f1,f2,f3,g1,g2,g3</literal> above would be valid
+example, any of the <literal>f1,f2,f3,g1,g2</literal> above would be valid
field type signatures.</para> </listitem>
<listitem> <para> As the type of an implicit parameter </para> </listitem>
<listitem> <para> In a pattern type signature (see <xref linkend="scoped-type-variables">) </para> </listitem>
</sect3>
-<sect3 id="implicit-quant">
-<title>Implicit quantification</title>
-
-<para>
-GHC performs implicit quantification as follows. <emphasis>At the top level (only) of
-user-written types, if and only if there is no explicit <literal>forall</literal>,
-GHC finds all the type variables mentioned in the type that are not already
-in scope, and universally quantifies them.</emphasis> For example, the following pairs are
-equivalent:
-<programlisting>
- f :: a -> a
- f :: forall a. a -> a
-
- g (x::a) = let
- h :: a -> b -> b
- h x y = y
- in ...
- g (x::a) = let
- h :: forall b. a -> b -> b
- h x y = y
- in ...
-</programlisting>
-</para>
-<para>
-Notice that GHC does <emphasis>not</emphasis> find the innermost possible quantification
-point. For example:
-<programlisting>
- f :: (a -> a) -> Int
- -- MEANS
- f :: forall a. (a -> a) -> Int
- -- NOT
- f :: (forall a. a -> a) -> Int
-
-
- g :: (Ord a => a -> a) -> Int
- -- MEANS the illegal type
- g :: forall a. (Ord a => a -> a) -> Int
- -- NOT
- g :: (forall a. Ord a => a -> a) -> Int
-</programlisting>
-The latter produces an illegal type, which you might think is silly,
-but at least the rule is simple. If you want the latter type, you
-can write your for-alls explicitly. Indeed, doing so is strongly advised
-for rank-2 types.
-</para>
-</sect3>
-</sect2>
-
-<sect2 id="type-synonyms">
-<title>Liberalised type synonyms
-</title>
-
-<para>
-Type synonmys are like macros at the type level, and
-GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
-That means that GHC can be very much more liberal about type synonyms than Haskell 98:
-<itemizedlist>
-<listitem> <para>You can write a <literal>forall</literal> (including overloading)
-in a type synonym, thus:
-<programlisting>
- type Discard a = forall b. Show b => a -> b -> (a, String)
-
- f :: Discard a
- f x y = (x, show y)
-
- g :: Discard Int -> (Int,Bool) -- A rank-2 type
- g f = f Int True
-</programlisting>
-</para>
-</listitem>
-
-<listitem><para>
-You can write an unboxed tuple in a type synonym:
-<programlisting>
- type Pr = (# Int, Int #)
-
- h :: Int -> Pr
- h x = (# x, x #)
-</programlisting>
-</para></listitem>
-
-<listitem><para>
-You can apply a type synonym to a forall type:
-<programlisting>
- type Foo a = a -> a -> Bool
-
- f :: Foo (forall b. b->b)
-</programlisting>
-After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
-<programlisting>
- f :: (forall b. b->b) -> (forall b. b->b) -> Bool
-</programlisting>
-</para></listitem>
-
-<listitem><para>
-You can apply a type synonym to a partially applied type synonym:
-<programlisting>
- type Generic i o = forall x. i x -> o x
- type Id x = x
-
- foo :: Generic Id []
-</programlisting>
-After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
-<programlisting>
- foo :: forall x. x -> [x]
-</programlisting>
-</para></listitem>
-
-</itemizedlist>
-</para>
-
-<para>
-GHC currently does kind checking before expanding synonyms (though even that
-could be changed.)
-</para>
-<para>
-After expanding type synonyms, GHC does validity checking on types, looking for
-the following mal-formedness which isn't detected simply by kind checking:
-<itemizedlist>
-<listitem><para>
-Type constructor applied to a type involving for-alls.
-</para></listitem>
-<listitem><para>
-Unboxed tuple on left of an arrow.
-</para></listitem>
-<listitem><para>
-Partially-applied type synonym.
-</para></listitem>
-</itemizedlist>
-So, for example,
-this will be rejected:
-<programlisting>
- type Pr = (# Int, Int #)
-
- h :: Pr -> Int
- h x = ...
-</programlisting>
-because GHC does not allow unboxed tuples on the left of a function arrow.
-</para>
-</sect2>
-
-<sect2 id="hoist">
-<title>For-all hoisting</title>
-<para>
-It is often convenient to use generalised type synonyms at the right hand
-end of an arrow, thus:
-<programlisting>
- type Discard a = forall b. a -> b -> a
-
- g :: Int -> Discard Int
- g x y z = x+y
-</programlisting>
-Simply expanding the type synonym would give
-<programlisting>
- g :: Int -> (forall b. Int -> b -> Int)
-</programlisting>
-but GHC "hoists" the <literal>forall</literal> to give the isomorphic type
-<programlisting>
- g :: forall b. Int -> Int -> b -> Int
-</programlisting>
-In general, the rule is this: <emphasis>to determine the type specified by any explicit
-user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly
-performs the transformation:</emphasis>
-<programlisting>
- <emphasis>type1</emphasis> -> forall a1..an. <emphasis>context2</emphasis> => <emphasis>type2</emphasis>
-==>
- forall a1..an. <emphasis>context2</emphasis> => <emphasis>type1</emphasis> -> <emphasis>type2</emphasis>
-</programlisting>
-(In fact, GHC tries to retain as much synonym information as possible for use in
-error messages, but that is a usability issue.) This rule applies, of course, whether
-or not the <literal>forall</literal> comes from a synonym. For example, here is another
-valid way to write <literal>g</literal>'s type signature:
-<programlisting>
- g :: Int -> Int -> forall b. b -> Int
-</programlisting>
-</para>
-<para>
-When doing this hoisting operation, GHC eliminates duplicate constraints. For
-example:
-<programlisting>
- type Foo a = (?x::Int) => Bool -> a
- g :: Foo (Foo Int)
-</programlisting>
-means
-<programlisting>
- g :: (?x::Int) => Bool -> Bool -> Int
-</programlisting>
-</para>
-</sect2>
-
-
-<sect2 id="existential-quantification">
-<title>Existentially quantified data constructors
-</title>
-
-<para>
-The idea of using existential quantification in data type declarations
-was suggested by Laufer (I believe, thought doubtless someone will
-correct me), and implemented in Hope+. It's been in Lennart
-Augustsson's <Command>hbc</Command> Haskell compiler for several years, and
-proved very useful. Here's the idea. Consider the declaration:
-</para>
-
-<para>
-
-<programlisting>
- data Foo = forall a. MkFoo a (a -> Bool)
- | Nil
-</programlisting>
-
-</para>
-
-<para>
-The data type <literal>Foo</literal> has two constructors with types:
-</para>
-
-<para>
-
-<programlisting>
- MkFoo :: forall a. a -> (a -> Bool) -> Foo
- Nil :: Foo
-</programlisting>
-
-</para>
-
-<para>
-Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
-does not appear in the data type itself, which is plain <literal>Foo</literal>.
-For example, the following expression is fine:
-</para>
-
-<para>
-
-<programlisting>
- [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
-</programlisting>
-
-</para>
-
-<para>
-Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
-<function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
-isUpper</function> packages a character with a compatible function. These
-two things are each of type <literal>Foo</literal> and can be put in a list.
-</para>
-
-<para>
-What can we do with a value of type <literal>Foo</literal>?. In particular,
-what happens when we pattern-match on <function>MkFoo</function>?
-</para>
-
-<para>
-
-<programlisting>
- f (MkFoo val fn) = ???
-</programlisting>
-
-</para>
-
-<para>
-Since all we know about <literal>val</literal> and <function>fn</function> is that they
-are compatible, the only (useful) thing we can do with them is to
-apply <function>fn</function> to <literal>val</literal> to get a boolean. For example:
-</para>
-
-<para>
-
-<programlisting>
- f :: Foo -> Bool
- f (MkFoo val fn) = fn val
-</programlisting>
-
-</para>
-
-<para>
-What this allows us to do is to package heterogenous values
-together with a bunch of functions that manipulate them, and then treat
-that collection of packages in a uniform manner. You can express
-quite a bit of object-oriented-like programming this way.
-</para>
-
-<sect3 id="existential">
-<title>Why existential?
-</title>
-
-<para>
-What has this to do with <emphasis>existential</emphasis> quantification?
-Simply that <function>MkFoo</function> has the (nearly) isomorphic type
-</para>
-
-<para>
-
-<programlisting>
- MkFoo :: (exists a . (a, a -> Bool)) -> Foo
-</programlisting>
-
-</para>
-
-<para>
-But Haskell programmers can safely think of the ordinary
-<emphasis>universally</emphasis> quantified type given above, thereby avoiding
-adding a new existential quantification construct.
-</para>
-
-</sect3>
-
-<sect3>
-<title>Type classes</title>
-
-<para>
-An easy extension (implemented in <Command>hbc</Command>) is to allow
-arbitrary contexts before the constructor. For example:
-</para>
-
-<para>
-
-<programlisting>
-data Baz = forall a. Eq a => Baz1 a a
- | forall b. Show b => Baz2 b (b -> b)
-</programlisting>
-
-</para>
-
-<para>
-The two constructors have the types you'd expect:
-</para>
-
-<para>
-
-<programlisting>
-Baz1 :: forall a. Eq a => a -> a -> Baz
-Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
-</programlisting>
-
-</para>
-
-<para>
-But when pattern matching on <function>Baz1</function> the matched values can be compared
-for equality, and when pattern matching on <function>Baz2</function> the first matched
-value can be converted to a string (as well as applying the function to it).
-So this program is legal:
-</para>
-
-<para>
-
-<programlisting>
- f :: Baz -> String
- f (Baz1 p q) | p == q = "Yes"
- | otherwise = "No"
- f (Baz2 v fn) = show (fn v)
-</programlisting>
-
-</para>
-
-<para>
-Operationally, in a dictionary-passing implementation, the
-constructors <function>Baz1</function> and <function>Baz2</function> must store the
-dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
-extract it on pattern matching.
-</para>
-
-<para>
-Notice the way that the syntax fits smoothly with that used for
-universal quantification earlier.
-</para>
-
-</sect3>
-
-<sect3>
-<title>Restrictions</title>
-
-<para>
-There are several restrictions on the ways in which existentially-quantified
-constructors can be use.
-</para>
-
-<para>
-
-<itemizedlist>
-<listitem>
-
-<para>
- When pattern matching, each pattern match introduces a new,
-distinct, type for each existential type variable. These types cannot
-be unified with any other type, nor can they escape from the scope of
-the pattern match. For example, these fragments are incorrect:
-
-
-<programlisting>
-f1 (MkFoo a f) = a
-</programlisting>
-
-
-Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
-is the result of <function>f1</function>. One way to see why this is wrong is to
-ask what type <function>f1</function> has:
-
-
-<programlisting>
- f1 :: Foo -> a -- Weird!
-</programlisting>
-
-
-What is this "<literal>a</literal>" in the result type? Clearly we don't mean
-this:
-
-
-<programlisting>
- f1 :: forall a. Foo -> a -- Wrong!
-</programlisting>
-
-
-The original program is just plain wrong. Here's another sort of error
-
-
-<programlisting>
- f2 (Baz1 a b) (Baz1 p q) = a==q
-</programlisting>
-
-
-It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
-<literal>a==q</literal> is wrong because it equates the two distinct types arising
-from the two <function>Baz1</function> constructors.
-
-
-</para>
-</listitem>
-<listitem>
-
-<para>
-You can't pattern-match on an existentially quantified
-constructor in a <literal>let</literal> or <literal>where</literal> group of
-bindings. So this is illegal:
-
-
-<programlisting>
- f3 x = a==b where { Baz1 a b = x }
-</programlisting>
-
-Instead, use a <literal>case</literal> expression:
-
-<programlisting>
- f3 x = case x of Baz1 a b -> a==b
-</programlisting>
-
-In general, you can only pattern-match
-on an existentially-quantified constructor in a <literal>case</literal> expression or
-in the patterns of a function definition.
-
-The reason for this restriction is really an implementation one.
-Type-checking binding groups is already a nightmare without
-existentials complicating the picture. Also an existential pattern
-binding at the top level of a module doesn't make sense, because it's
-not clear how to prevent the existentially-quantified type "escaping".
-So for now, there's a simple-to-state restriction. We'll see how
-annoying it is.
-
-</para>
-</listitem>
-<listitem>
-
-<para>
-You can't use existential quantification for <literal>newtype</literal>
-declarations. So this is illegal:
-
-
-<programlisting>
- newtype T = forall a. Ord a => MkT a
-</programlisting>
-
-
-Reason: a value of type <literal>T</literal> must be represented as a pair
-of a dictionary for <literal>Ord t</literal> and a value of type <literal>t</literal>.
-That contradicts the idea that <literal>newtype</literal> should have no
-concrete representation. You can get just the same efficiency and effect
-by using <literal>data</literal> instead of <literal>newtype</literal>. If there is no
-overloading involved, then there is more of a case for allowing
-an existentially-quantified <literal>newtype</literal>, because the <literal>data</literal>
-because the <literal>data</literal> version does carry an implementation cost,
-but single-field existentially quantified constructors aren't much
-use. So the simple restriction (no existential stuff on <literal>newtype</literal>)
-stands, unless there are convincing reasons to change it.
+<sect3 id="implicit-quant">
+<title>Implicit quantification</title>
+<para>
+GHC performs implicit quantification as follows. <emphasis>At the top level (only) of
+user-written types, if and only if there is no explicit <literal>forall</literal>,
+GHC finds all the type variables mentioned in the type that are not already
+in scope, and universally quantifies them.</emphasis> For example, the following pairs are
+equivalent:
+<programlisting>
+ f :: a -> a
+ f :: forall a. a -> a
+ g (x::a) = let
+ h :: a -> b -> b
+ h x y = y
+ in ...
+ g (x::a) = let
+ h :: forall b. a -> b -> b
+ h x y = y
+ in ...
+</programlisting>
</para>
-</listitem>
-<listitem>
-
<para>
- You can't use <literal>deriving</literal> to define instances of a
-data type with existentially quantified data constructors.
-
-Reason: in most cases it would not make sense. For example:#
-
+Notice that GHC does <emphasis>not</emphasis> find the innermost possible quantification
+point. For example:
<programlisting>
-data T = forall a. MkT [a] deriving( Eq )
-</programlisting>
+ f :: (a -> a) -> Int
+ -- MEANS
+ f :: forall a. (a -> a) -> Int
+ -- NOT
+ f :: (forall a. a -> a) -> Int
-To derive <literal>Eq</literal> in the standard way we would need to have equality
-between the single component of two <function>MkT</function> constructors:
-<programlisting>
-instance Eq T where
- (MkT a) == (MkT b) = ???
+ g :: (Ord a => a -> a) -> Int
+ -- MEANS the illegal type
+ g :: forall a. (Ord a => a -> a) -> Int
+ -- NOT
+ g :: (forall a. Ord a => a -> a) -> Int
</programlisting>
-
-But <VarName>a</VarName> and <VarName>b</VarName> have distinct types, and so can't be compared.
-It's just about possible to imagine examples in which the derived instance
-would make sense, but it seems altogether simpler simply to prohibit such
-declarations. Define your own instances!
+The latter produces an illegal type, which you might think is silly,
+but at least the rule is simple. If you want the latter type, you
+can write your for-alls explicitly. Indeed, doing so is strongly advised
+for rank-2 types.
</para>
-</listitem>
-
-</itemizedlist>
+</sect3>
+</sect2>
-</para>
-</sect3>
-</sect2>
<sect2 id="scoped-type-variables">
<title>Scoped type variables
</sect2>
+<sect2 id="deriving-typeable">
+<title>Deriving clause for classes <literal>Typeable</literal> and <literal>Data</literal></title>
+
+<para>
+Haskell 98 allows the programmer to add "<literal>deriving( Eq, Ord )</literal>" to a data type
+declaration, to generate a standard instance declaration for classes specified in the <literal>deriving</literal> clause.
+In Haskell 98, the only classes that may appear in the <literal>deriving</literal> clause are the standard
+classes <literal>Eq</literal>, <literal>Ord</literal>,
+<literal>Enum</literal>, <literal>Ix</literal>, <literal>Bounded</literal>, <literal>Read</literal>, and <literal>Show</literal>.
+</para>
+<para>
+GHC extends this list with two more classes that may be automatically derived
+(provided the <option>-fglasgow-exts</option> flag is specified):
+<literal>Typeable</literal>, and <literal>Data</literal>. These classes are defined in the library
+modules <literal>Data.Dynamic</literal> and <literal>Data.Generics</literal> respectively, and the
+appropriate class must be in scope before it can be mentioned in the <literal>deriving</literal> clause.
+</para>
+</sect2>
+
<sect2 id="newtype-deriving">
<title>Generalised derived instances for newtypes</title>
<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.
Tim Sheard is going to expand it.)
</para>
-<sect2> <title> Syntax </title>
-<para>
- Template Haskell has the following new syntactic constructions. You need to use the flag
- <literal>-fglasgow-exts</literal> to switch these syntactic extensions on.
+ <sect2>
+ <title>Syntax</title>
+
+ <para> Template Haskell has the following new syntactic
+ constructions. You need to use the flag
+ <option>-fth</option><indexterm><primary><option>-fth</option></primary>
+ </indexterm>to switch these syntactic extensions on
+ (<option>-fth</option> is currently implied by
+ <option>-fglasgow-exts</option>, but you are encouraged to
+ specify it explicitly).</para>
<itemizedlist>
<listitem><para>
</itemizedlist>
+</sect2>
+
+<sect2> <title> Using Template Haskell </title>
+<para>
+<itemizedlist>
+ <listitem><para>
+ The data types and monadic constructor functions for Template Haskell are in the library
+ <literal>Language.Haskell.THSyntax</literal>.
+ </para></listitem>
+
+ <listitem><para>
+ You can only run a function at compile time if it is imported from another module. That is,
+ you can't define a function in a module, and call it from within a splice in the same module.
+ (It would make sense to do so, but it's hard to implement.)
+ </para></listitem>
+
+ <listitem><para>
+ The flag <literal>-ddump-splices</literal> shows the expansion of all top-level splices as they happen.
+ </para></listitem>
+ <listitem><para>
+ If you are building GHC from source, you need at least a stage-2 bootstrap compiler to
+ run Template Haskell. A stage-1 compiler will reject the TH constructs. Reason: TH
+ compiles and runs a program, and then looks at the result. So it's important that
+ the program it compiles produces results whose representations are identical to
+ those of the compiler itself.
+ </para></listitem>
+</itemizedlist>
+</para>
+<para> Template Haskell works in any mode (<literal>--make</literal>, <literal>--interactive</literal>,
+ or file-at-a-time). There used to be a restriction to the former two, but that restriction
+ has been lifted.
+</para>
+</sect2>
+
+<sect2> <title> A Template Haskell Worked Example </title>
+<para>To help you get over the confidence barrier, try out this skeletal worked example.
+ First cut and paste the two modules below into "Main.hs" and "Printf.hs":</para>
+
+<programlisting>
+{- Main.hs -}
+module Main where
+
+-- Import our template "pr"
+import Printf ( pr )
+
+-- The splice operator $ takes the Haskell source code
+-- generated at compile time by "pr" and splices it into
+-- the argument of "putStrLn".
+main = putStrLn ( $(pr "Hello") )
+</programlisting>
+
+<programlisting>
+{- Printf.hs -}
+module Printf where
+
+-- Skeletal printf from the paper.
+-- It needs to be in a separate module to the one where
+-- you intend to use it.
+
+-- Import some Template Haskell syntax
+import Language.Haskell.THSyntax
+
+-- Describe a format string
+data Format = D | S | L String
+
+-- Parse a format string. This is left largely to you
+-- as we are here interested in building our first ever
+-- Template Haskell program and not in building printf.
+parse :: String -> [Format]
+parse s = [ L s ]
+
+-- Generate Haskell source code from a parsed representation
+-- of the format string. This code will be spliced into
+-- the module which calls "pr", at compile time.
+gen :: [Format] -> Expr
+gen [D] = [| \n -> show n |]
+gen [S] = [| \s -> s |]
+gen [L s] = string s
+
+-- Here we generate the Haskell code for the splice
+-- from an input format string.
+pr :: String -> Expr
+pr s = gen (parse s)
+</programlisting>
+
+<para>Now run the compiler (here we are a Cygwin prompt on Windows):
+</para>
+<programlisting>
+$ ghc --make -fth main.hs -o main.exe
+</programlisting>
+
+<para>Run "main.exe" and here is your output:</para>
+
+<programlisting>
+$ ./main
+Hello
+</programlisting>
+
+</sect2>
+
+</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> Using Template Haskell </title>
-<para>
-<itemizedlist>
- <listitem><para>
- The data types and monadic constructor functions for Template Haskell are in the library
- <literal>Language.Haskell.THSyntax</literal>.
- </para></listitem>
+</sect2>
- <listitem><para>
- You can only run a function at compile time if it is imported from another module. That is,
- you can't define a function in a module, and call it from within a splice in the same module.
- (It would make sense to do so, but it's hard to implement.)
- </para></listitem>
+<sect2>
+<title>Primitive constructs</title>
- <listitem><para>
- The flag <literal>-ddump-splices</literal> shows the expansion of all top-level splices as they happen.
- </para></listitem>
- <listitem><para>
- If you are building GHC from source, you need at least a stage-2 bootstrap compiler to
- run Template Haskell. A stage-1 compiler will reject the TH constructs. Reason: TH
- compiles and runs a program, and then looks at the result. So it's important that
- the program it compiles produces results whose representations are identical to
- those of the compiler itself.
- </para></listitem>
-</itemizedlist>
-</para>
-<para> Template Haskell works in any mode (<literal>--make</literal>, <literal>--interactive</literal>,
- or file-at-a-time). There used to be a restriction to the former two, but that restriction
- has been lifted.
+<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>
-</sect2>
-
-<sect2> <title> A Template Haskell Worked Example </title>
-<para>To help you get over the confidence barrier, try out this skeletal worked example.
- First cut and paste the two modules below into "Main.hs" and "Printf.hs":</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>
-{- Main.hs -}
-module Main where
-
--- Import our template "pr"
-import Printf ( pr )
+bind :: Arrow a => a e b -> a (e,b) c -> a e c
+u `bind` f = returnA &&& u >>> f
--- The splice operator $ takes the Haskell source code
--- generated at compile time by "pr" and splices it into
--- the argument of "putStrLn".
-main = putStrLn ( $(pr "Hello") )
+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>
-{- Printf.hs -}
-module Printf where
+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>
--- Skeletal printf from the paper.
--- It needs to be in a separate module to the one where
--- you intend to use it.
+</sect2>
--- Import some Template Haskell syntax
-import Language.Haskell.THSyntax
+<sect2>
+<title>Differences with the paper</title>
--- Describe a format string
-data Format = D | S | L String
+<itemizedlist>
--- Parse a format string. This is left largely to you
--- as we are here interested in building our first ever
--- Template Haskell program and not in building printf.
-parse :: String -> [Format]
-parse s = [ L s ]
+<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>
--- Generate Haskell source code from a parsed representation
--- of the format string. This code will be spliced into
--- the module which calls "pr", at compile time.
-gen :: [Format] -> Expr
-gen [D] = [| \n -> show n |]
-gen [S] = [| \s -> s |]
-gen [L s] = string s
+<listitem>
+<para>User-defined operators are flagged with banana brackets instead of
+a new <literal>form</literal> keyword.
+</para>
+</listitem>
--- Here we generate the Haskell code for the splice
--- from an input format string.
-pr :: String -> Expr
-pr s = gen (parse s)
-</programlisting>
+</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>
-<para>Now run the compiler (here we are using a "stage three" build of GHC, at a Cygwin prompt on Windows):
+<listitem>
+<para>
+The module must import
+<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>.
</para>
-<programlisting>
-ghc/compiler/stage3/ghc-inplace --make -fglasgow-exts -package haskell-src main.hs -o main.exe
-</programlisting>
+</listitem>
-<para>Run "main.exe" and here is your output:
+<listitem>
+<para>
+The preprocessor cannot cope with other Haskell extensions.
+These would have to go in separate modules.
</para>
+</listitem>
-<programlisting>
-$ ./main
-Hello
-</programlisting>
+<listitem>
+<para>
+Because the preprocessor targets Haskell (rather than Core),
+<literal>let</literal>-bound variables are monomorphic.
+</para>
+</listitem>
+
+</itemizedlist>
+</para>
</sect2>
-
+
</sect1>
<!-- ==================== ASSERTIONS ================= -->
unrecognised <replaceable>word</replaceable> is (silently)
ignored.</para>
-<sect2 id="inline-pragma">
-<title>INLINE pragma
+ <sect2 id="deprecated-pragma">
+ <title>DEPRECATED pragma</title>
+ <indexterm><primary>DEPRECATED</primary>
+ </indexterm>
-<indexterm><primary>INLINE and NOINLINE pragmas</primary></indexterm>
-<indexterm><primary>pragma, INLINE</primary></indexterm></title>
+ <para>The DEPRECATED pragma lets you specify that a particular
+ function, class, or type, is deprecated. There are two
+ forms.</para>
-<para>
-GHC (with <option>-O</option>, as always) tries to inline (or “unfold”)
-functions/values that are “small enough,” thus avoiding the call
-overhead and possibly exposing other more-wonderful optimisations.
-Normally, if GHC decides a function is “too expensive” to inline, it
-will not do so, nor will it export that unfolding for other modules to
-use.
-</para>
+ <itemizedlist>
+ <listitem>
+ <para>You can deprecate an entire module thus:</para>
+<programlisting>
+ module Wibble {-# DEPRECATED "Use Wobble instead" #-} where
+ ...
+</programlisting>
+ <para>When you compile any module that import
+ <literal>Wibble</literal>, GHC will print the specified
+ message.</para>
+ </listitem>
-<para>
-The sledgehammer you can bring to bear is the
-<literal>INLINE</literal><indexterm><primary>INLINE pragma</primary></indexterm> pragma, used thusly:
+ <listitem>
+ <para>You can deprecate a function, class, or type, with the
+ following top-level declaration:</para>
+<programlisting>
+ {-# DEPRECATED f, C, T "Don't use these" #-}
+</programlisting>
+ <para>When you compile any module that imports and uses any
+ of the specifed entities, GHC will print the specified
+ message.</para>
+ </listitem>
+ </itemizedlist>
+
+ <para>You can suppress the warnings with the flag
+ <option>-fno-warn-deprecations</option>.</para>
+ </sect2>
+
+ <sect2 id="inline-noinline-pragma">
+ <title>INLINE and NOINLINE pragmas</title>
+
+ <para>These pragmas control the inlining of function
+ definitions.</para>
+
+ <sect3 id="inline-pragma">
+ <title>INLINE pragma</title>
+ <indexterm><primary>INLINE</primary></indexterm>
+
+ <para>GHC (with <option>-O</option>, as always) tries to
+ inline (or “unfold”) functions/values that are
+ “small enough,” thus avoiding the call overhead
+ and possibly exposing other more-wonderful optimisations.
+ Normally, if GHC decides a function is “too
+ expensive” to inline, it will not do so, nor will it
+ export that unfolding for other modules to use.</para>
+
+ <para>The sledgehammer you can bring to bear is the
+ <literal>INLINE</literal><indexterm><primary>INLINE
+ pragma</primary></indexterm> pragma, used thusly:</para>
<programlisting>
key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}
#endif
</programlisting>
-(You don't need to do the C pre-processor carry-on unless you're going
-to stick the code through HBC—it doesn't like <literal>INLINE</literal> pragmas.)
-</para>
-<para>
-The major effect of an <literal>INLINE</literal> pragma is to declare a function's
-“cost” to be very low. The normal unfolding machinery will then be
-very keen to inline it.
-</para>
+ <para>(You don't need to do the C pre-processor carry-on
+ unless you're going to stick the code through HBC—it
+ doesn't like <literal>INLINE</literal> pragmas.)</para>
-<para>
-Syntactially, an <literal>INLINE</literal> pragma for a function can be put anywhere its type
-signature could be put.
-</para>
+ <para>The major effect of an <literal>INLINE</literal> pragma
+ is to declare a function's “cost” to be very low.
+ The normal unfolding machinery will then be very keen to
+ inline it.</para>
-<para>
-<literal>INLINE</literal> pragmas are a particularly good idea for the
-<literal>then</literal>/<literal>return</literal> (or <literal>bind</literal>/<literal>unit</literal>) functions in a monad.
-For example, in GHC's own <literal>UniqueSupply</literal> monad code, we have:
+ <para>Syntactially, an <literal>INLINE</literal> pragma for a
+ function can be put anywhere its type signature could be
+ put.</para>
+
+ <para><literal>INLINE</literal> pragmas are a particularly
+ good idea for the
+ <literal>then</literal>/<literal>return</literal> (or
+ <literal>bind</literal>/<literal>unit</literal>) functions in
+ a monad. For example, in GHC's own
+ <literal>UniqueSupply</literal> monad code, we have:</para>
<programlisting>
#ifdef __GLASGOW_HASKELL__
#endif
</programlisting>
-</para>
-
-<sect3 id="noinline-pragma">
-<title>The NOINLINE pragma </title>
-
-<indexterm><primary>NOINLINE pragma</primary></indexterm>
-<indexterm><primary>pragma</primary><secondary>NOINLINE</secondary></indexterm>
-<indexterm><primary>NOTINLINE pragma</primary></indexterm>
-<indexterm><primary>pragma</primary><secondary>NOTINLINE</secondary></indexterm>
-
-<para>
-The <literal>NOINLINE</literal> pragma does exactly what you'd expect:
-it stops the named function from being inlined by the compiler. You
-shouldn't ever need to do this, unless you're very cautious about code
-size.
-</para>
-
-<para><literal>NOTINLINE</literal> is a synonym for
-<literal>NOINLINE</literal> (<literal>NOTINLINE</literal> is specified
-by Haskell 98 as the standard way to disable inlining, so it should be
-used if you want your code to be portable).</para>
-</sect3>
-
+ <para>See also the <literal>NOINLINE</literal> pragma (<xref
+ linkend="noinline-pragma">).</para>
+ </sect3>
+
+ <sect3 id="noinline-pragma">
+ <title>NOINLINE pragma</title>
+
+ <indexterm><primary>NOINLINE</primary></indexterm>
+ <indexterm><primary>NOTINLINE</primary></indexterm>
+
+ <para>The <literal>NOINLINE</literal> pragma does exactly what
+ you'd expect: it stops the named function from being inlined
+ by the compiler. You shouldn't ever need to do this, unless
+ you're very cautious about code size.</para>
+
+ <para><literal>NOTINLINE</literal> is a synonym for
+ <literal>NOINLINE</literal> (<literal>NOTINLINE</literal> is
+ specified by Haskell 98 as the standard way to disable
+ inlining, so it should be used if you want your code to be
+ portable).</para>
+ </sect3>
+
+ <sect3 id="phase-control">
+ <title>Phase control</title>
+
+ <para> Sometimes you want to control exactly when in GHC's
+ pipeline the INLINE pragma is switched on. Inlining happens
+ only during runs of the <emphasis>simplifier</emphasis>. Each
+ run of the simplifier has a different <emphasis>phase
+ number</emphasis>; the phase number decreases towards zero.
+ If you use <option>-dverbose-core2core</option> you'll see the
+ sequence of phase numbers for successive runs of the
+ simpifier. In an INLINE pragma you can optionally specify a
+ phase number, thus:</para>
-<sect3 id="phase-control">
-<title>Phase control</title>
-
-<para> Sometimes you want to control exactly when in GHC's pipeline
-the INLINE pragma is switched on. Inlining happens only during runs of
-the <emphasis>simplifier</emphasis>. Each run of the simplifier has a different
-<emphasis>phase number</emphasis>; the phase number decreases towards zero.
-If you use <option>-dverbose-core2core</option>
-you'll see the sequence of phase numbers for successive runs of the simpifier.
-In an INLINE pragma you can optionally specify a phase number, thus:
-<itemizedlist>
-<listitem> <para>You can say "inline <literal>f</literal> in Phase 2 and all subsequent
-phases":
+ <itemizedlist>
+ <listitem>
+ <para>You can say "inline <literal>f</literal> in Phase 2
+ and all subsequent phases":
<programlisting>
{-# INLINE [2] f #-}
</programlisting>
-</para></listitem>
+ </para>
+ </listitem>
-<listitem> <para>You can say "inline <literal>g</literal> in all phases up to, but
-not including, Phase 3":
+ <listitem>
+ <para>You can say "inline <literal>g</literal> in all
+ phases up to, but not including, Phase 3":
<programlisting>
{-# INLINE [~3] g #-}
</programlisting>
-</para></listitem>
+ </para>
+ </listitem>
-<listitem> <para>If you omit the phase indicator, you mean "inline in all phases".
-</para></listitem>
-</itemizedlist>
-You can use a phase number on a NOINLINE pragma too:
-<itemizedlist>
-<listitem> <para>You can say "do not inline <literal>f</literal> until Phase 2; in
-Phase 2 and subsequently behave as if there was no pragma at all":
+ <listitem>
+ <para>If you omit the phase indicator, you mean "inline in
+ all phases".</para>
+ </listitem>
+ </itemizedlist>
+
+ <para>You can use a phase number on a NOINLINE pragma too:</para>
+
+ <itemizedlist>
+ <listitem>
+ <para>You can say "do not inline <literal>f</literal>
+ until Phase 2; in Phase 2 and subsequently behave as if
+ there was no pragma at all":
<programlisting>
{-# NOINLINE [2] f #-}
</programlisting>
-</para></listitem>
+ </para>
+ </listitem>
-<listitem> <para>You can say "do not inline <literal>g</literal> in Phase 3 or any subsequent phase;
-before that, behave as if there was no pragma":
+ <listitem>
+ <para>You can say "do not inline <literal>g</literal> in
+ Phase 3 or any subsequent phase; before that, behave as if
+ there was no pragma":
<programlisting>
{-# NOINLINE [~3] g #-}
</programlisting>
-</para></listitem>
+ </para>
+ </listitem>
-<listitem> <para>If you omit the phase indicator, you mean "never inline this function".
-</para></listitem>
-</itemizedlist>
-</para>
-<para>The same phase-numbering control is available for RULES (<xref LinkEnd="rewrite-rules">).</para>
-</sect3>
+ <listitem>
+ <para>If you omit the phase indicator, you mean "never
+ inline this function".</para>
+ </listitem>
+ </itemizedlist>
+
+ <para>The same phase-numbering control is available for RULES
+ (<xref LinkEnd="rewrite-rules">).</para>
+ </sect3>
+ </sect2>
+ <sect2 id="line-pragma">
+ <title>LINE pragma</title>
+ <indexterm><primary>LINE</primary><secondary>pragma</secondary></indexterm>
+ <indexterm><primary>pragma</primary><secondary>LINE</secondary></indexterm>
+ <para>This pragma is similar to C's <literal>#line</literal>
+ pragma, and is mainly for use in automatically generated Haskell
+ code. It lets you specify the line number and filename of the
+ original code; for example</para>
-</sect2>
+<programlisting>
+{-# LINE 42 "Foo.vhs" #-}
+</programlisting>
-<sect2 id="rules">
-<title>RULES pragma</title>
+ <para>if you'd generated the current file from something called
+ <filename>Foo.vhs</filename> and this line corresponds to line
+ 42 in the original. GHC will adjust its error messages to refer
+ to the line/file named in the <literal>LINE</literal>
+ pragma.</para>
+ </sect2>
-<para>
-The RULES pragma lets you specify rewrite rules. It is described in
-<xref LinkEnd="rewrite-rules">.
-</para>
+ <sect2 id="options-pragma">
+ <title>OPTIONS pragma</title>
+ <indexterm><primary>OPTIONS</primary>
+ </indexterm>
+ <indexterm><primary>pragma</primary><secondary>OPTIONS</secondary>
+ </indexterm>
+
+ <para>The <literal>OPTIONS</literal> pragma is used to specify
+ additional options that are given to the compiler when compiling
+ this source file. See <xref linkend="source-file-options"> for
+ details.</para>
+ </sect2>
-</sect2>
+ <sect2 id="rules">
+ <title>RULES pragma</title>
+ <para>The RULES pragma lets you specify rewrite rules. It is
+ described in <xref LinkEnd="rewrite-rules">.</para>
+ </sect2>
<sect2 id="specialize-pragma">
<title>SPECIALIZE pragma</title>
<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
</sect2>
-<sect2 id="line-pragma">
-<title>LINE pragma
-</title>
-
-<para>
-<indexterm><primary>LINE pragma</primary></indexterm>
-<indexterm><primary>pragma, LINE</primary></indexterm>
-</para>
-
-<para>
-This pragma is similar to C's <literal>#line</literal> pragma, and is mainly for use in
-automatically generated Haskell code. It lets you specify the line
-number and filename of the original code; for example
-</para>
-
-<para>
-
-<programlisting>
-{-# LINE 42 "Foo.vhs" #-}
-</programlisting>
-
-</para>
-
-<para>
-if you'd generated the current file from something called <filename>Foo.vhs</filename>
-and this line corresponds to line 42 in the original. GHC will adjust
-its error messages to refer to the line/file named in the <literal>LINE</literal>
-pragma.
-</para>
-
-</sect2>
-
-<sect2 id="deprecated-pragma">
-<title>DEPRECATED pragma</title>
-
-<para>
-The DEPRECATED pragma lets you specify that a particular function, class, or type, is deprecated.
-There are two forms.
-</para>
-<itemizedlist>
-<listitem><para>
-You can deprecate an entire module thus:</para>
-<programlisting>
- module Wibble {-# DEPRECATED "Use Wobble instead" #-} where
- ...
-</programlisting>
-<para>
-When you compile any module that import <literal>Wibble</literal>, GHC will print
-the specified message.</para>
-</listitem>
-
-<listitem>
-<para>
-You can deprecate a function, class, or type, with the following top-level declaration:
-</para>
-<programlisting>
- {-# DEPRECATED f, C, T "Don't use these" #-}
-</programlisting>
-<para>
-When you compile any module that imports and uses any of the specifed entities,
-GHC will print the specified message.
-</para>
-</listitem>
-</itemizedlist>
-<para>You can suppress the warnings with the flag <option>-fno-warn-deprecations</option>.</para>
-
-</sect2>
+ <sect2 id="unpack-pragma">
+ <title>UNPACK pragma</title>
+
+ <indexterm><primary>UNPACK</primary> </indexterm>
+
+ <para>There is another use for the <literal>UNPACK</literal>
+ pragma: to indicate that the compiler should unpack the contents
+ of a constructor field into the constructor itself, removing a
+ level of indirection. For example:</para>
+
+<ProgramListing>
+data T = T {-# UNPACK #-} !Float
+ {-# UNPACK #-} !Float
+</ProgramListing>
+
+ <para>will create a constructor <literal>T</literal> containing
+ two unboxed floats. This may not always be an optimisation: if
+ the <Function>T</Function> constructor is scrutinised and the
+ floats passed to a non-strict function for example, they will
+ have to be reboxed (this is done automatically by the
+ compiler).</para>
+
+ <para>Unpacking constructor fields should only be used in
+ conjunction with <option>-O</option>, in order to expose
+ unfoldings to the compiler so the reboxing can be removed as
+ often as possible. For example:</para>
+
+<ProgramListing>
+f :: T -> Float
+f (T f1 f2) = f1 + f2
+</ProgramListing>
+
+ <para>The compiler will avoid reboxing <Function>f1</Function>
+ and <Function>f2</Function> by inlining <Function>+</Function>
+ on floats, but only when <option>-O</option> is on.</para>
+
+ <para>Any single-constructor data is eligible for unpacking; for
+ example</para>
+
+<ProgramListing>
+data T = T {-# UNPACK #-} !(Int,Int)
+</ProgramListing>
+
+ <para>will store the two <literal>Int</literal>s directly in the
+ <Function>T</Function> constructor, by flattening the pair.
+ Multi-level unpacking is also supported:</para>
+
+<ProgramListing>
+data T = T {-# UNPACK #-} !S
+data S = S {-# UNPACK #-} !Int {-# UNPACK #-} !Int
+</ProgramListing>
+
+ <para>will store two unboxed <literal>Int#</literal>s
+ directly in the <Function>T</Function> constructor.</para>
+
+ <para>See also the <option>-funbox-strict-fields</option> flag,
+ which essentially has the effect of adding
+ <literal>{-# UNPACK #-}</literal> to every strict
+ constructor field.</para>
+ </sect2>
</sect1>
<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>
;;; sgml-parent-document: ("users_guide.sgml" "book" "chapter" "sect1") ***
;;; End: ***
-->
+
projects / ghc-hetmet.git / blobdiff