<!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
<!-- included from primitives.sgml -->
-&primitives;
+<!-- &primitives; -->
+<sect1 id="primitives">
+ <title>Unboxed types and primitive operations</title>
+
+<para>GHC is built on a raft of primitive data types and operations.
+While you really can use this stuff to write fast code,
+ we generally find it a lot less painful, and more satisfying in the
+ long run, to use higher-level language features and libraries. With
+ any luck, the code you write will be optimised to the efficient
+ unboxed version in any case. And if it isn't, we'd like to know
+ about it.</para>
+
+<para>We do not currently have good, up-to-date documentation about the
+primitives, perhaps because they are mainly intended for internal use.
+There used to be a long section about them here in the User Guide, but it
+became out of date, and wrong information is worse than none.</para>
+
+<para>The Real Truth about what primitive types there are, and what operations
+work over those types, is held in the file
+<filename>fptools/ghc/compiler/prelude/primops.txt</filename>.
+This file is used directly to generate GHC's primitive-operation definitions, so
+it is always correct! It is also intended for processing into text.</para>
+
+<para> Indeed,
+the result of such processing is part of the description of the
+ <ulink
+ url="http://haskell.cs.yale.edu/ghc/docs/papers/core.ps.gz">External
+ Core language</ulink>.
+So that document is a good place to look for a type-set version.
+We would be very happy if someone wanted to volunteer to produce an SGML
+back end to the program that processes <filename>primops.txt</filename> so that
+we could include the results here in the User Guide.</para>
+
+<para>What follows here is a brief summary of some main points.</para>
+
+<sect2 id="glasgow-unboxed">
+<title>Unboxed types
+</title>
+
+<para>
+<indexterm><primary>Unboxed types (Glasgow extension)</primary></indexterm>
+</para>
+
+<para>Most types in GHC are <firstterm>boxed</firstterm>, which means
+that values of that type are represented by a pointer to a heap
+object. The representation of a Haskell <literal>Int</literal>, for
+example, is a two-word heap object. An <firstterm>unboxed</firstterm>
+type, however, is represented by the value itself, no pointers or heap
+allocation are involved.
+</para>
+
+<para>
+Unboxed types correspond to the “raw machine” types you
+would use in C: <literal>Int#</literal> (long int),
+<literal>Double#</literal> (double), <literal>Addr#</literal>
+(void *), etc. The <emphasis>primitive operations</emphasis>
+(PrimOps) on these types are what you might expect; e.g.,
+<literal>(+#)</literal> is addition on
+<literal>Int#</literal>s, and is the machine-addition that we all
+know and love—usually one instruction.
+</para>
+
+<para>
+Primitive (unboxed) types cannot be defined in Haskell, and are
+therefore built into the language and compiler. Primitive types are
+always unlifted; that is, a value of a primitive type cannot be
+bottom. We use the convention that primitive types, values, and
+operations have a <literal>#</literal> suffix.
+</para>
+
+<para>
+Primitive values are often represented by a simple bit-pattern, such
+as <literal>Int#</literal>, <literal>Float#</literal>,
+<literal>Double#</literal>. But this is not necessarily the case:
+a primitive value might be represented by a pointer to a
+heap-allocated object. Examples include
+<literal>Array#</literal>, the type of primitive arrays. A
+primitive array is heap-allocated because it is too big a value to fit
+in a register, and would be too expensive to copy around; in a sense,
+it is accidental that it is represented by a pointer. If a pointer
+represents a primitive value, then it really does point to that value:
+no unevaluated thunks, no indirections…nothing can be at the
+other end of the pointer than the primitive value.
+</para>
+
+<para>
+There are some restrictions on the use of primitive types, the main
+one being that you can't pass a primitive value to a polymorphic
+function or store one in a polymorphic data type. This rules out
+things like <literal>[Int#]</literal> (i.e. lists of primitive
+integers). The reason for this restriction is that polymorphic
+arguments and constructor fields are assumed to be pointers: if an
+unboxed integer is stored in one of these, the garbage collector would
+attempt to follow it, leading to unpredictable space leaks. Or a
+<function>seq</function> operation on the polymorphic component may
+attempt to dereference the pointer, with disastrous results. Even
+worse, the unboxed value might be larger than a pointer
+(<literal>Double#</literal> for instance).
+</para>
+
+<para>
+Nevertheless, A numerically-intensive program using unboxed types can
+go a <emphasis>lot</emphasis> faster than its “standard”
+counterpart—we saw a threefold speedup on one example.
+</para>
+
+</sect2>
+
+<sect2 id="unboxed-tuples">
+<title>Unboxed Tuples
+</title>
+
+<para>
+Unboxed tuples aren't really exported by <literal>GHC.Exts</literal>,
+they're available by default with <option>-fglasgow-exts</option>. An
+unboxed tuple looks like this:
+</para>
+
+<para>
+
+<programlisting>
+(# e_1, ..., e_n #)
+</programlisting>
+
+</para>
+
+<para>
+where <literal>e_1..e_n</literal> are expressions of any
+type (primitive or non-primitive). The type of an unboxed tuple looks
+the same.
+</para>
+
+<para>
+Unboxed tuples are used for functions that need to return multiple
+values, but they avoid the heap allocation normally associated with
+using fully-fledged tuples. When an unboxed tuple is returned, the
+components are put directly into registers or on the stack; the
+unboxed tuple itself does not have a composite representation. Many
+of the primitive operations listed in this section return unboxed
+tuples.
+</para>
+
+<para>
+There are some pretty stringent restrictions on the use of unboxed tuples:
+</para>
+
+<para>
+
+<itemizedlist>
+<listitem>
+
+<para>
+ Unboxed tuple types are subject to the same restrictions as
+other unboxed types; i.e. they may not be stored in polymorphic data
+structures or passed to polymorphic functions.
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+ Unboxed tuples may only be constructed as the direct result of
+a function, and may only be deconstructed with a <literal>case</literal> expression.
+eg. the following are valid:
+
+
+<programlisting>
+f x y = (# x+1, y-1 #)
+g x = case f x x of { (# a, b #) -> a + b }
+</programlisting>
+
+
+but the following are invalid:
+
+
+<programlisting>
+f x y = g (# x, y #)
+g (# x, y #) = x + y
+</programlisting>
+
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+ No variable can have an unboxed tuple type. This is illegal:
+
+
+<programlisting>
+f :: (# Int, Int #) -> (# Int, Int #)
+f x = x
+</programlisting>
+
+
+because <literal>x</literal> has an unboxed tuple type.
+
+</para>
+</listitem>
+
+</itemizedlist>
+
+</para>
+
+<para>
+Note: we may relax some of these restrictions in the future.
+</para>
+
+<para>
+The <literal>IO</literal> and <literal>ST</literal> monads use unboxed
+tuples to avoid unnecessary allocation during sequences of operations.
+</para>
+
+</sect2>
+</sect1>
+
<!-- ====================== SYNTACTIC EXTENSIONS ======================= -->
Here is a simple (yet contrived) example:
</para>
<programlisting>
+import Control.Monad.Fix
+
justOnes = mdo xs <- Just (1:xs)
return xs
</programlisting>
For details, see the above mentioned reference.
</para>
<para>
-The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO, and
-state monads (both lazy and strict).
+The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO.
+Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class
+for Haskell's internal state monad (strict and lazy, respectively).
</para>
<para>
There are three important points in using the recursive-do notation:
</para></listitem>
<listitem><para>
-If you want to declare an instance of the <literal>MonadFix</literal> class for one of
-your own monads, or you need to refer to the class name <literal>MonadFix</literal> in any other way (for
-instance when writing a type constraint), then your program should
-<literal>import Control.Monad.MonadFix</literal>.
-Otherwise, you don't need to import any special libraries to use the mdo-notation. That is,
-as long as you only use the predefined instances mentioned above, the mdo-notation will
-be automatically available.
-To be on the safe side, of course, you can simply import it in all cases.
+You should <literal>import Control.Monad.Fix</literal>.
+(Note: Strictly speaking, this import is required only when you need to refer to the name
+<literal>MonadFix</literal> in your program, but the import is always safe, and the programmers
+are encouraged to always import this module when using the mdo-notation.)
</para></listitem>
<listitem><para>
</para>
<para>
+The web page: <ulink url="http://www.cse.ogi.edu/PacSoft/projects/rmb">http://www.cse.ogi.edu/PacSoft/projects/rmb</ulink>
+contains up to date information on recursive monadic bindings.
+</para>
+
+<para>
Historical note: The old implementation of the mdo-notation (and most
of the existing documents) used the name
<literal>MonadRec</literal> for the class and the corresponding library.
-This name is no longer supported.
+This name is not supported by GHC.
</para>
+</sect2>
+
+
+<sect2> <title> Infix type constructors </title>
+
+<para>GHC supports infix type constructors, much as it supports infix data constructors. For example:
+<programlisting>
+ infixl 5 :+:
+
+ data a :+: b = Inl a | Inr b
+
+ f :: a `Either` b -> a :+: b
+ f (Left x) = Inl x
+</programlisting>
+</para>
+<para>The lexical
+syntax of an infix type constructor is just like that of an infix data constructor: either
+it's an operator beginning with ":", or it is an ordinary (alphabetic) type constructor enclosed in
+back-quotes.</para>
+
<para>
-The web page: <ulink url="http://www.cse.ogi.edu/PacSoft/projects/rmb">http://www.cse.ogi.edu/PacSoft/projects/rmb</ulink>
-contains up to date information on recursive monadic bindings.
+When you give a fixity declaration, the fixity applies to both the data constructor and the
+type constructor with the specified name. You cannot give different fixities to the type constructor T
+and the data constructor T.
</para>
+
</sect2>
<!-- ===================== PARALLEL LIST COMPREHENSIONS =================== -->
Jones, Erik Meijer).
</para>
-<para>
-I'd like to thank people who reported shorcomings in the GHC 3.02
-implementation. Our default decisions were all conservative ones, and
-the experience of these heroic pioneers has given useful concrete
-examples to support several generalisations. (These appear below as
-design choices not implemented in 3.02.)
-</para>
-
-<para>
-I've discussed these notes with Mark Jones, and I believe that Hugs
-will migrate towards the same design choices as I outline here.
-Thanks to him, and to many others who have offered very useful
-feedback.
-</para>
-<sect3>
+<sect3 id="type-restrictions">
<title>Types</title>
<para>
-There are the following restrictions on the form of a qualified
-type:
-</para>
-
-<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
</programlisting>
-</para>
-
-<para>
(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,
<para>
<emphasis>Each universally quantified type variable
-<literal>tvi</literal> must be mentioned (i.e. appear free) in <literal>type</literal></emphasis>.
+<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:
+ambiguity.
+Here, for example, is an illegal type:
<programlisting>
</para>
-<para>
-These restrictions apply to all types, whether declared in a type signature
-or inferred.
-</para>
<para>
Unlike Haskell 1.4, constraints in types do <emphasis>not</emphasis> have to be of
</para>
</listitem>
-<listitem>
-
-<para>
- <emphasis>In the signature of a class operation, every constraint
-must mention at least one type variable that is not a class type
-variable</emphasis>.
-
-Thus:
-
-
-<programlisting>
- class Collection c a where
- mapC :: Collection c b => (a->b) -> c a -> c b
-</programlisting>
-
-
-is OK because the constraint <literal>(Collection a b)</literal> mentions
-<literal>b</literal>, even though it also mentions the class variable
-<literal>a</literal>. On the other hand:
-
-
-<programlisting>
- class C a where
- op :: Eq a => (a,b) -> (a,b)
-</programlisting>
-
-
-is not OK because the constraint <literal>(Eq a)</literal> mentions on the class
-type variable <literal>a</literal>, but not <literal>b</literal>. However, any such
-example is easily fixed by moving the offending context up to the
-superclass context:
-
-<programlisting>
- class Eq a => C a where
- op ::(a,b) -> (a,b)
-</programlisting>
-
-
-A yet more relaxed rule would allow the context of a class-op signature
-to mention only class type variables. However, that conflicts with
-Rule 1(b) for types above.
-
-</para>
-</listitem>
<listitem>
<para>
- <emphasis>The type of each class operation must mention <emphasis>all</emphasis> of
-the class type variables</emphasis>. For example:
+ <emphasis>All of the class type variables must be reachable (in the sense
+mentioned in <xref linkend="type-restrictions">)
+from the free varibles of each method type
+</emphasis>. For example:
<programlisting>
instance Stateful (ST s) (MutVar s) where ...
</programlisting>
-
-The "at least one not a type variable" restriction is to ensure that
-context reduction terminates: each reduction step removes one type
-constructor. For example, the following would make the type checker
-loop if it wasn't excluded:
-
-
-<programlisting>
- instance C a => C a where ...
-</programlisting>
-
-
-There are two situations in which the rule is a bit of a pain. First,
-if one allows overlapping instance declarations then it's quite
-convenient to have a "default instance" declaration that applies if
-something more specific does not:
-
-
-<programlisting>
- instance C a where
- op = ... -- Default
-</programlisting>
-
-
-Second, sometimes you might want to use the following to get the
-effect of a "class synonym":
-
-
-<programlisting>
- class (C1 a, C2 a, C3 a) => C a where { }
-
- instance (C1 a, C2 a, C3 a) => C a where { }
-</programlisting>
-
-
-This allows you to write shorter signatures:
-
-
-<programlisting>
- f :: C a => ...
-</programlisting>
-
-
-instead of
-
-
-<programlisting>
- f :: (C1 a, C2 a, C3 a) => ...
-</programlisting>
-
-
-I'm on the lookout for a simple rule that preserves decidability while
-allowing these idioms. The experimental flag
-<option>-fallow-undecidable-instances</option><indexterm><primary>-fallow-undecidable-instances
-option</primary></indexterm> lifts this restriction, allowing all the types in an
-instance head to be type variables.
-
+See <xref linkend="undecidable-instances"> for an experimental
+extension to lift this restriction.
</para>
</listitem>
<listitem>
</programlisting>
-is not OK. Again, the intent here is to make sure that context
-reduction terminates.
+is not OK. See <xref linkend="undecidable-instances"> for an experimental
+extension to lift this restriction.
+
-Voluminous correspondence on the Haskell mailing list has convinced me
-that it's worth experimenting with a more liberal rule. If you use
-the flag <option>-fallow-undecidable-instances</option> can use arbitrary
-types in an instance context. Termination is ensured by having a
-fixed-depth recursion stack. If you exceed the stack depth you get a
-sort of backtrace, and the opportunity to increase the stack depth
-with <option>-fcontext-stack</option><emphasis>N</emphasis>.
</para>
</listitem>
</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
+loop if it wasn't excluded:
+<programlisting>
+ instance C a => C a where ...
+</programlisting>
+There are two situations in which the rule is a bit of a pain. First,
+if one allows overlapping instance declarations then it's quite
+convenient to have a "default instance" declaration that applies if
+something more specific does not:
+
+
+<programlisting>
+ instance C a where
+ op = ... -- Default
+</programlisting>
+
+
+Second, sometimes you might want to use the following to get the
+effect of a "class synonym":
+
+
+<programlisting>
+ class (C1 a, C2 a, C3 a) => C a where { }
+
+ instance (C1 a, C2 a, C3 a) => C a where { }
+</programlisting>
+
+
+This allows you to write shorter signatures:
+
+
+<programlisting>
+ f :: C a => ...
+</programlisting>
+
+
+instead of
+
+
+<programlisting>
+ f :: (C1 a, C2 a, C3 a) => ...
+</programlisting>
+
+
+Voluminous correspondence on the Haskell mailing list has convinced me
+that it's worth experimenting with more liberal rules. If you use
+the experimental flag <option>-fallow-undecidable-instances</option>
+<indexterm><primary>-fallow-undecidable-instances
+option</primary></indexterm>, you can use arbitrary
+types in both an instance context and instance head. Termination is ensured by having a
+fixed-depth recursion stack. If you exceed the stack depth you get a
+sort of backtrace, and the opportunity to increase the stack depth
+with <option>-fcontext-stack</option><emphasis>N</emphasis>.
+</para>
+<para>
+I'm on the lookout for a less brutal solution: a simple rule that preserves decidability while
+allowing these idioms interesting idioms.
+</para>
+</sect2>
+
<sect2 id="implicit-parameters">
<title>Implicit parameters
</title>
The dynamic binding constraints are just a new form of predicate in the type class system.
</para>
<para>
-An implicit parameter is introduced by the special form <literal>?x</literal>,
+An implicit parameter occurs in an expression using the special form <literal>?x</literal>,
where <literal>x</literal> is
-any valid identifier. Use if this construct also introduces new
-dynamic binding constraints. For example, the following definition
+any valid identifier (e.g. <literal>ord ?x</literal> is a valid expression).
+Use of this construct also introduces a new
+dynamic-binding constraint in the type of the expression.
+For example, the following definition
shows how we can define an implicitly parameterized sort function in
terms of an explicitly parameterized <literal>sortBy</literal> function:
<programlisting>
sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
sort = sortBy ?cmp
</programlisting>
+</para>
+
+<sect3>
+<title>Implicit-parameter type constraints</title>
+<para>
Dynamic binding constraints behave just like other type class
constraints in that they are automatically propagated. Thus, when a
function is used, its implicit parameters are inherited by the
propagate them.
</para>
<para>
-An implicit parameter differs from other type class constraints in the
+An implicit-parameter type constraint differs from other type class constraints in the
following way: All uses of a particular implicit parameter must have
the same type. This means that the type of <literal>(?x, ?x)</literal>
is <literal>(?x::a) => (a,a)</literal>, and not
<literal>(?x::a, ?x::b) => (a, b)</literal>, as would be the case for type
class constraints.
</para>
+
+<para> You can't have an implicit parameter in the context of a class or instance
+declaration. For example, both these declarations are illegal:
+<programlisting>
+ class (?x::Int) => C a where ...
+ instance (?x::a) => Foo [a] where ...
+</programlisting>
+Reason: exactly which implicit parameter you pick up depends on exactly where
+you invoke a function. But the ``invocation'' of instance declarations is done
+behind the scenes by the compiler, so it's hard to figure out exactly where it is done.
+Easiest thing is to outlaw the offending types.</para>
<para>
-An implicit parameter is bound using the standard
-<literal>let</literal> binding form, where the bindings must be a
-collection of simple bindings to implicit-style variables (no
-function-style bindings, and no type signatures); these bindings are
-neither polymorphic or recursive. This form binds the implicit
-parameters arising in the body, not the free variables as a
-<literal>let</literal> or <literal>where</literal> would do. For
-example, we define the <literal>min</literal> function by binding
-<literal>cmp</literal>.</para>
+Implicit-parameter constraints do not cause ambiguity. For example, consider:
+<programlisting>
+ f :: (?x :: [a]) => Int -> Int
+ f n = n + length ?x
+
+ g :: (Read a, Show a) => String -> String
+ g s = show (read s)
+</programlisting>
+Here, <literal>g</literal> has an ambiguous type, and is rejected, but <literal>f</literal>
+is fine. The binding for <literal>?x</literal> at <literal>f</literal>'s call site is
+quite unambiguous, and fixes the type <literal>a</literal>.
+</para>
+</sect3>
+
+<sect3>
+<title>Implicit-parameter bindings</title>
+
+<para>
+An implicit parameter is <emphasis>bound</emphasis> using the standard
+<literal>let</literal> or <literal>where</literal> binding forms.
+For example, we define the <literal>min</literal> function by binding
+<literal>cmp</literal>.
<programlisting>
min :: [a] -> a
min = let ?cmp = (<=) in least
</programlisting>
+</para>
<para>
+A group of implicit-parameter bindings may occur anywhere a normal group of Haskell
+bindings can occur, except at top level. That is, they can occur in a <literal>let</literal>
+(including in a list comprehension, or do-notation, or pattern guards),
+or a <literal>where</literal> clause.
Note the following points:
<itemizedlist>
<listitem><para>
+An implicit-parameter binding group must be a
+collection of simple bindings to implicit-style variables (no
+function-style bindings, and no type signatures); these bindings are
+neither polymorphic or recursive.
+</para></listitem>
+<listitem><para>
You may not mix implicit-parameter bindings with ordinary bindings in a
single <literal>let</literal>
expression; use two nested <literal>let</literal>s instead.
+(In the case of <literal>where</literal> you are stuck, since you can't nest <literal>where</literal> clauses.)
</para></listitem>
<listitem><para>
You may put multiple implicit-parameter bindings in a
-single <literal>let</literal> expression; they are <emphasis>not</emphasis> treated
+single binding group; but they are <emphasis>not</emphasis> treated
as a mutually recursive group (as ordinary <literal>let</literal> bindings are).
-Instead they are treated as a non-recursive group, each scoping over the bindings that
-follow. For example, consider:
+Instead they are treated as a non-recursive group, simultaneously binding all the implicit
+parameter. The bindings are not nested, and may be re-ordered without changing
+the meaning of the program.
+For example, consider:
<programlisting>
- f y = let { ?x = y; ?x = ?x+1 } in ?x
+ f t = let { ?x = t; ?y = ?x+(1::Int) } in ?x + ?y
</programlisting>
-This function adds one to its argument.
-</para></listitem>
-
-<listitem><para>
-You may not have an implicit-parameter binding in a <literal>where</literal> clause,
-only in a <literal>let</literal> binding.
-</para></listitem>
-
-<listitem>
-<para> You can't have an implicit parameter in the context of a class or instance
-declaration. For example, both these declarations are illegal:
+The use of <literal>?x</literal> in the binding for <literal>?y</literal> does not "see"
+the binding for <literal>?x</literal>, so the type of <literal>f</literal> is
<programlisting>
- class (?x::Int) => C a where ...
- instance (?x::a) => Foo [a] where ...
+ f :: (?x::Int) => Int -> Int
</programlisting>
-Reason: exactly which implicit parameter you pick up depends on exactly where
-you invoke a function. But the ``invocation'' of instance declarations is done
-behind the scenes by the compiler, so it's hard to figure out exactly where it is done.
-Easiest thing is to outlaw the offending types.</para>
-</listitem>
+</para></listitem>
</itemizedlist>
</para>
+</sect3>
</sect2>
<sect2 id="linear-implicit-parameters">
</sect3>
<sect3>
-<title>Result type signatures</title>
-
-<para>
-
-<itemizedlist>
-<listitem>
-
-<para>
- The result type of a function can be given a signature,
-thus:
-
-
-<programlisting>
- f (x::a) :: [a] = [x,x,x]
-</programlisting>
-
-
-The final <literal>:: [a]</literal> after all the patterns gives a signature to the
-result type. Sometimes this is the only way of naming the type variable
-you want:
-
-
-<programlisting>
- f :: Int -> [a] -> [a]
- f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
- in \xs -> map g (reverse xs `zip` xs)
-</programlisting>
-
-
-</para>
-</listitem>
-
-</itemizedlist>
-
-</para>
-
-<para>
-Result type signatures are not yet implemented in Hugs.
-</para>
-
-</sect3>
-
-<sect3>
<title>Where a pattern type signature can occur</title>
<para>
</para>
</sect3>
+
+<sect3>
+<title>Result type signatures</title>
+
+<para>
+The result type of a function can be given a signature, thus:
+
+
+<programlisting>
+ f (x::a) :: [a] = [x,x,x]
+</programlisting>
+
+
+The final <literal>:: [a]</literal> after all the patterns gives a signature to the
+result type. Sometimes this is the only way of naming the type variable
+you want:
+
+
+<programlisting>
+ f :: Int -> [a] -> [a]
+ f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
+ in \xs -> map g (reverse xs `zip` xs)
+</programlisting>
+
+</para>
+<para>
+The type variables bound in a result type signature scope over the right hand side
+of the definition. However, consider this corner-case:
+<programlisting>
+ rev1 :: [a] -> [a] = \xs -> reverse xs
+
+ foo ys = rev (ys::[a])
+</programlisting>
+The signature on <literal>rev1</literal> is considered a pattern type signature, not a result
+type signature, and the type variables it binds have the same scope as <literal>rev1</literal>
+itself (i.e. the right-hand side of <literal>rev1</literal> and the rest of the module too).
+In particular, the expression <literal>(ys::[a])</literal> is OK, because the type variable <literal>a</literal>
+is in scope (otherwise it would mean <literal>(ys::forall a.[a])</literal>, which would be rejected).
+</para>
+<para>
+As mentioned above, <literal>rev1</literal> is made monomorphic by this scoping rule.
+For example, the following program would be rejected, because it claims that <literal>rev1</literal>
+is polymorphic:
+<programlisting>
+ rev1 :: [b] -> [b]
+ rev1 :: [a] -> [a] = \xs -> reverse xs
+</programlisting>
+</para>
+
+<para>
+Result type signatures are not yet implemented in Hugs.
+</para>
+
+</sect3>
+
</sect2>
<sect2 id="newtype-deriving">
newtype T v1...vn = T' (S t1...tk vk+1...vn) deriving (c1...cm)
</programlisting>
-where <literal>S</literal> is a type constructor, <literal>t1...tk</literal> are
-types,
-<literal>vk+1...vn</literal> are type variables which do not occur in any of
-the <literal>ti</literal>, and the <literal>ci</literal> are partial applications of
-classes of the form <literal>C t1'...tj'</literal>. The derived instance
-declarations are, for each <literal>ci</literal>,
-
+where
+ <itemizedlist>
+<listitem><para>
+ <literal>S</literal> is a type constructor,
+</para></listitem>
+<listitem><para>
+ <literal>t1...tk</literal> are types,
+</para></listitem>
+<listitem><para>
+ <literal>vk+1...vn</literal> are type variables which do not occur in any of
+ the <literal>ti</literal>, and
+</para></listitem>
+<listitem><para>
+ the <literal>ci</literal> are partial applications of
+ classes of the form <literal>C t1'...tj'</literal>, where the arity of <literal>C</literal>
+ is exactly <literal>j+1</literal>. That is, <literal>C</literal> lacks exactly one type argument.
+</para></listitem>
+</itemizedlist>
+Then, for each <literal>ci</literal>, the derived instance
+declaration is:
<programlisting>
instance ci (S t1...tk vk+1...v) => ci (T v1...vp)
</programlisting>
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.
+</para>
+
<para>
The documentation here describes the realisation in GHC. (It's rather sketchy just now;
Tim Sheard is going to expand it.)
</para>
-<sect2> <title> Using Template Haskell </title>
+<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.
</para>
<para> A splice can occur in place of
<itemizedlist>
- <listitem><para> an expression;</para></listitem>
- <listitem><para> a list of top-level declarations;</para></listitem>
- <listitem><para> a pattern;</para></listitem>
- <listitem><para> a type;</para></listitem>
+ <listitem><para> an expression; the spliced expression must have type <literal>Expr</literal></para></listitem>
+ <listitem><para> a list of top-level declarations; ; the spliced expression must have type <literal>Q [Dec]</literal></para></listitem>
+ <listitem><para> a type; the spliced expression must have type <literal>Type</literal>.</para></listitem>
</itemizedlist>
+ (Note that the syntax for a declaration splice uses "<literal>$</literal>" not "<literal>splice</literal>" as in
+ the paper. Also the type of the enclosed expression must be <literal>Q [Dec]</literal>, not <literal>[Q Dec]</literal>
+ as in the paper.)
</para></listitem>
<listitem><para>
A expression quotation is written in Oxford brackets, thus:
<itemizedlist>
- <listitem><para> <literal>[| ... |]</literal>, where the "..." is an expression;</para></listitem>
- <listitem><para> <literal>[d| ... |]</literal>, where the "..." is a list of top-level declarations;</para></listitem>
- <listitem><para> <literal>[p| ... |]</literal>, where the "..." is a pattern;</para></listitem>
- <listitem><para> <literal>[t| ... |]</literal>, where the "..." is a type;</para></listitem>
+ <listitem><para> <literal>[| ... |]</literal>, where the "..." is an expression;
+ the quotation has type <literal>Expr</literal>.</para></listitem>
+ <listitem><para> <literal>[d| ... |]</literal>, where the "..." is a list of top-level declarations;
+ the quotation has type <literal>Q [Dec]</literal>.</para></listitem>
+ <listitem><para> <literal>[t| ... |]</literal>, where the "..." is a type;
+ the quotation has type <literal>Type</literal>.</para></listitem>
</itemizedlist></para></listitem>
<listitem><para>
</para></listitem>
<listitem><para>
- If the module contains any top-level splices that must be run, you must use GHC with
- <literal>--make</literal> or <literal>--interactive</literal> flags. (Reason: that
- means it walks the dependency tree and knows what modules must be linked etc.)
- </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.)
<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 using a "stage three" build of GHC, at a Cygwin prompt on Windows):
+</para>
+<programlisting>
+ghc/compiler/stage3/ghc-inplace --make -fglasgow-exts -package haskell-src main.hs -o main.exe
+</programlisting>
+
+<para>Run "main.exe" and here is your output:
+</para>
+
+<programlisting>
+$ ./main
+Hello
+</programlisting>
+
</sect2>
</sect1>
<sect2 id="inline-pragma">
<title>INLINE pragma
-<indexterm><primary>INLINE pragma</primary></indexterm>
+<indexterm><primary>INLINE and NOINLINE pragmas</primary></indexterm>
<indexterm><primary>pragma, INLINE</primary></indexterm></title>
<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.
-</para>
-
-<para>
-You will probably see these unfoldings (in Core syntax) in your
-interface files.
-</para>
-
-<para>
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.
{-# 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>
<para>
-An <literal>INLINE</literal> pragma for a function can be put anywhere its type
+Syntactially, an <literal>INLINE</literal> pragma for a function can be put anywhere its type
signature could be put.
</para>
</para>
-</sect2>
-
-<sect2 id="noinline-pragma">
-<title>NOINLINE pragma
-</title>
+<sect3 id="noinline-pragma">
+<title>The NOINLINE pragma </title>
<indexterm><primary>NOINLINE pragma</primary></indexterm>
<indexterm><primary>pragma</primary><secondary>NOINLINE</secondary></indexterm>
<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:
+<itemizedlist>
+<listitem> <para>You can say "inline <literal>f</literal> in Phase 2 and all subsequent
+phases":
+<programlisting>
+ {-# INLINE [2] f #-}
+</programlisting>
+</para></listitem>
+
+<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>
+
+<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":
+<programlisting>
+ {-# NOINLINE [2] f #-}
+</programlisting>
+</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":
+<programlisting>
+ {-# NOINLINE [~3] g #-}
+</programlisting>
+</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>
+
+
+
+</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>
{-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-}
</programlisting>
+ <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>
<programlisting>
-{-# RULES hammeredLookup = blah #-}
+{-# RULES "hammeredLookup" hammeredLookup = blah #-}
</programlisting>
<para>where <literal>blah</literal> is an implementation of
toDouble :: Real a => a -> Double
toDouble = fromRational . toRational
-{-# SPECIALIZE toDouble :: Int -> Double = i2d #-}
+{-# RULES "toDouble/Int" toDouble = i2d #-}
i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
</programlisting>
<literal>Rational</literal>—is obscenely expensive by
comparison.</para>
- <para>A <literal>SPECIALIZE</literal> pragma for a function can
- be put anywhere its type signature could be put.</para>
-
</sect2>
<sect2 id="specialize-instance-pragma">
</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="deprecated-pragma">
<title>DEPRECATED pragma</title>
<listitem>
<para>
+ There may be zero or more rules in a <literal>RULES</literal> pragma.
+</para>
+</listitem>
+
+<listitem>
+
+<para>
Each rule has a name, enclosed in double quotes. The name itself has
no significance at all. It is only used when reporting how many times the rule fired.
</para>
</listitem>
-<listitem>
+<listitem>
<para>
- There may be zero or more rules in a <literal>RULES</literal> pragma.
+A rule may optionally have a phase-control number (see <xref LinkEnd="phase-control">),
+immediately after the name of the rule. Thus:
+<programlisting>
+ {-# RULES
+ "map/map" [2] forall f g xs. map f (map g xs) = map (f.g) xs
+ #-}
+</programlisting>
+The "[2]" means that the rule is active in Phase 2 and subsequent phases. The inverse
+notation "[~2]" is also accepted, meaning that the rule is active up to, but not including,
+Phase 2.
</para>
</listitem>
+
+
<listitem>
<para>
enclosing definitions.
</para>
</listitem>
+
<listitem>
<para>
</sect2>
+<sect2 id="core-pragma">
+ <title>CORE pragma</title>
+
+ <indexterm><primary>CORE pragma</primary></indexterm>
+ <indexterm><primary>pragma, CORE</primary></indexterm>
+ <indexterm><primary>core, annotation</primary></indexterm>
+
+<para>
+ The external core format supports <quote>Note</quote> annotations;
+ the <literal>CORE</literal> pragma gives a way to specify what these
+ should be in your Haskell source code. Syntactically, core
+ annotations are attached to expressions and take a Haskell string
+ literal as an argument. The following function definition shows an
+ example:
+
+<programlisting>
+f x = ({-# CORE "foo" #-} show) ({-# CORE "bar" #-} x)
+</programlisting>
+
+ Sematically, this is equivalent to:
+
+<programlisting>
+g x = show x
+</programlisting>
+</para>
+
+<para>
+ However, when external for is generated (via
+ <option>-fext-core</option>), there will be Notes attached to the
+ expressions <function>show</function> and <VarName>x</VarName>.
+ The core function declaration for <function>f</function> is:
+</para>
+
+<programlisting>
+ f :: %forall a . GHCziShow.ZCTShow a ->
+ a -> GHCziBase.ZMZN GHCziBase.Char =
+ \ @ a (zddShow::GHCziShow.ZCTShow a) (eta::a) ->
+ (%note "foo"
+ %case zddShow %of (tpl::GHCziShow.ZCTShow a)
+ {GHCziShow.ZCDShow
+ (tpl1::GHCziBase.Int ->
+ a ->
+ GHCziBase.ZMZN GHCziBase.Char -> GHCziBase.ZMZN GHCziBase.Cha
+r)
+ (tpl2::a -> GHCziBase.ZMZN GHCziBase.Char)
+ (tpl3::GHCziBase.ZMZN a ->
+ GHCziBase.ZMZN GHCziBase.Char -> GHCziBase.ZMZN GHCziBase.Cha
+r) ->
+ tpl2})
+ (%note "foo"
+ eta);
+</programlisting>
+
+<para>
+ Here, we can see that the function <function>show</function> (which
+ has been expanded out to a case expression over the Show dictionary)
+ has a <literal>%note</literal> attached to it, as does the
+ expression <VarName>eta</VarName> (which used to be called
+ <VarName>x</VarName>).
+</para>
+
+</sect2>
+
</sect1>
<sect1 id="generic-classes">
instance (Bin a, Bin b) => Bin (a,b)
instance Bin a => Bin [a]
</programlisting>
-That is, just leave off the "where" clasuse. Of course, you can put in the
+That is, just leave off the "where" clause. Of course, you can put in the
where clause and over-ride whichever methods you please.
</para>
projects / ghc-hetmet.git / blobdiff