X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fdocs%2Fusers_guide%2Fglasgow_exts.sgml;h=9306e085d6b630677bae8e6f20a29958716c18ba;hb=72f5cd2fbc56c266e92f974a4561fbe878628b63;hp=0fbb00bb717d18a07994059a8ddafabcced03182;hpb=af9d318397bf714df23da54b0b955868fede3778;p=ghc-hetmet.git
diff --git a/ghc/docs/users_guide/glasgow_exts.sgml b/ghc/docs/users_guide/glasgow_exts.sgml
index 0fbb00b..9306e08 100644
--- a/ghc/docs/users_guide/glasgow_exts.sgml
+++ b/ghc/docs/users_guide/glasgow_exts.sgml
@@ -16,160 +16,15 @@ performance because of the implementation costs of Haskell's
-Executive summary of our extensions:
-
-
-
-
-
- Unboxed types and primitive operations:
-
- You can get right down to the raw machine types and
- operations; included in this are “primitive
- arrays” (direct access to Big Wads of Bytes). Please
- see and following.
-
-
-
-
- Type system extensions:
-
- GHC supports a large number of extensions to Haskell's
- type system. Specifically:
-
-
-
- Multi-parameter type classes:
-
-
-
-
-
-
- Functional dependencies:
-
-
-
-
-
-
- Implicit parameters:
-
-
-
-
-
-
- Linear implicit parameters:
-
-
-
-
-
-
- Local universal quantification:
-
-
-
-
-
-
- Extistentially quantification in data types:
-
-
-
-
-
-
- Scoped type variables:
-
- Scoped type variables enable the programmer to
- supply type signatures for some nested declarations,
- where this would not be legal in Haskell 98. Details in
- .
-
-
-
-
-
-
-
- Pattern guards
-
- Instead of being a boolean expression, a guard is a list
- of qualifiers, exactly as in a list comprehension. See .
-
-
-
-
- Data types with no constructors
-
- See .
-
-
-
-
- Parallel list comprehensions
-
- An extension to the list comprehension syntax to support
- zipWith-like functionality. See .
-
-
-
-
- Foreign calling:
-
- Just what it sounds like. We provide
- lots of rope that you can dangle around
- your neck. Please see .
-
-
-
-
- Pragmas
-
- Pragmas are special instructions to the compiler placed
- in the source file. The pragmas GHC supports are described in
- .
-
-
-
-
- Rewrite rules:
-
- The programmer can specify rewrite rules as part of the
- source program (in a pragma). GHC applies these rewrite rules
- wherever it can. Details in .
-
-
-
-
- Generic classes:
-
- (Note: support for generic classes is currently broken
- in GHC 5.02).
-
- Generic class declarations allow you to define a class
- whose methods say how to work over an arbitrary data type.
- Then it's really easy to make any new type into an instance of
- the class. This generalises the rather ad-hoc "deriving"
- feature of Haskell 98. Details in .
-
-
-
-
-
Before you get too carried away working at the lowest level (e.g.,
sloshing MutableByteArray#s around your
program), you may wish to check if there are libraries that provide a
-“Haskellised veneer” over the features you want. See
-.
+“Haskellised veneer” over the features you want. The
+separate libraries documentation describes all the libraries that come
+with GHC.
+
Language options
@@ -198,6 +53,30 @@ program), you may wish to check if there are libraries that provide a
+ and :
+
+
+
+ This option enables the language extension defined in the
+ Haskell 98 Foreign Function Interface Addendum plus deprecated
+ syntax of previous versions of the FFI for backwards
+ compatibility.
+
+
+
+
+ :
+
+
+ This option enables the deprecated with
+ keyword for implicit parameters; it is merely provided for backwards
+ compatibility.
+ It is independent of the
+ flag.
+
+
+
+ :
@@ -231,6 +110,15 @@ program), you may wish to check if there are libraries that provide a
+
+
+
+ See . Independent of
+ .
+
+
+
+
@@ -252,7 +140,7 @@ program), you may wish to check if there are libraries that provide a
module namespace is flat, and you must not conflict with
any Prelude module.)
- Even though you have not imported the Prelude, all
+ 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 [Int]
@@ -261,51 +149,9 @@ program), you may wish to check if there are libraries that provide a
translation for list comprehensions continues to use
Prelude.map etc.
- With one group of exceptions! You may want to
- define your own numeric class hierarchy. It completely
- defeats that purpose if the literal "1" means
- "Prelude.fromInteger 1", which is what
- the Haskell Report specifies. So the
- flag causes the
- following pieces of built-in syntax to refer to whatever
- is in scope, not the Prelude versions:
-
-
-
- Integer and fractional literals mean
- "fromInteger 1" and
- "fromRational 3.2", not the
- Prelude-qualified versions; both in expressions and in
- patterns.
-
-
-
- Negation (e.g. "- (f x)")
- means "negate (f x)" (not
- Prelude.negate).
-
-
-
- In an n+k pattern, the standard Prelude
- Ord class is still used for comparison,
- but the necessary subtraction uses whatever
- "(-)" is in scope (not
- "Prelude.(-)").
-
-
-
- Note: Negative literals, such as -3, are
- specified by (a careful reading of) the Haskell Report as
- meaning Prelude.negate (Prelude.fromInteger 3).
- However, GHC deviates from this slightly, and treats them as meaning
- fromInteger (-3). One particular effect of this
- slightly-non-standard reading is that there is no difficulty with
- the literal -2147483648 at type Int;
- it means fromInteger (-2147483648). The strict interpretation
- would be negate (fromInteger 2147483648),
- and the call to fromInteger would overflow
- (at type Int, remember).
-
+ However, does
+ change the handling of certain built-in syntax: see
+ .
@@ -314,144 +160,279 @@ program), you may wish to check if there are libraries that provide a
-&primitives;
+
+
+
+ Unboxed types and primitive operations
+
+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.
+
+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.
+
+The Real Truth about what primitive types there are, and what operations
+work over those types, is held in the file
+fptools/ghc/compiler/prelude/primops.txt.
+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.
+
+ Indeed,
+the result of such processing is part of the description of the
+ External
+ Core language.
+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 primops.txt so that
+we could include the results here in the User Guide.
+
+What follows here is a brief summary of some main points.
+
+
+Unboxed types
+
+
+
+Unboxed types (Glasgow extension)
+
-
-Primitive state-transformer monad
+Most types in GHC are boxed, which means
+that values of that type are represented by a pointer to a heap
+object. The representation of a Haskell Int, for
+example, is a two-word heap object. An unboxed
+type, however, is represented by the value itself, no pointers or heap
+allocation are involved.
+
-state transformers (Glasgow extensions)
-ST monad (Glasgow extension)
+Unboxed types correspond to the “raw machine” types you
+would use in C: Int# (long int),
+Double# (double), Addr#
+(void *), etc. The primitive operations
+(PrimOps) on these types are what you might expect; e.g.,
+(+#) is addition on
+Int#s, and is the machine-addition that we all
+know and love—usually one instruction.
-This monad underlies our implementation of arrays, mutable and
-immutable, and our implementation of I/O, including “C calls”.
+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 # suffix.
-The ST library, which provides access to the
-ST monad, is described in .
+Primitive values are often represented by a simple bit-pattern, such
+as Int#, Float#,
+Double#. But this is not necessarily the case:
+a primitive value might be represented by a pointer to a
+heap-allocated object. Examples include
+Array#, 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.
-
+
+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 [Int#] (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
+seq 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
+(Double# for instance).
+
+
+
+Nevertheless, A numerically-intensive program using unboxed types can
+go a lot faster than its “standard”
+counterpart—we saw a threefold speedup on one example.
+
+
+
-
-Primitive arrays, mutable and otherwise
+
+Unboxed Tuples
-primitive arrays (Glasgow extension)
-arrays, primitive (Glasgow extension)
+Unboxed tuples aren't really exported by GHC.Exts,
+they're available by default with . An
+unboxed tuple looks like this:
-GHC knows about quite a few flavours of Large Swathes of Bytes.
+
+
+(# e_1, ..., e_n #)
+
+
-First, GHC distinguishes between primitive arrays of (boxed) Haskell
-objects (type Array# obj) and primitive arrays of bytes (type
-ByteArray#).
+where e_1..e_n are expressions of any
+type (primitive or non-primitive). The type of an unboxed tuple looks
+the same.
-Second, it distinguishes between…
-
+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.
+
-
-Immutable:
-
-Arrays that do not change (as with “standard” Haskell arrays); you
-can only read from them. Obviously, they do not need the care and
-attention of the state-transformer monad.
+There are some pretty stringent restrictions on the use of unboxed tuples:
-
-
-
-Mutable:
+
+
+
+
+
-Arrays that may be changed or “mutated.” All the operations on them
-live within the state-transformer monad and the updates happen
-in-place.
+ 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.
+
-
-
-“Static” (in C land):
+
-A C routine may pass an Addr# pointer back into Haskell land. There
-are then primitive operations with which you may merrily grab values
-over in C land, by indexing off the “static” pointer.
+ Unboxed tuples may only be constructed as the direct result of
+a function, and may only be deconstructed with a case expression.
+eg. the following are valid:
+
+
+
+f x y = (# x+1, y-1 #)
+g x = case f x x of { (# a, b #) -> a + b }
+
+
+
+but the following are invalid:
+
+
+
+f x y = g (# x, y #)
+g (# x, y #) = x + y
+
+
+
-
-
-“Stable” pointers:
-
-If, for some reason, you wish to hand a Haskell pointer (i.e.,
-not an unboxed value) to a C routine, you first make the
-pointer “stable,” so that the garbage collector won't forget that it
-exists. That is, GHC provides a safe way to pass Haskell pointers to
-C.
-
-Please see for more details.
+ No variable can have an unboxed tuple type. This is illegal:
+
+
+
+f :: (# Int, Int #) -> (# Int, Int #)
+f x = x
+
+
+
+because x has an unboxed tuple type.
+
-
-
-“Foreign objects”:
-
-
-A “foreign object” is a safe way to pass an external object (a
-C-allocated pointer, say) to Haskell and have Haskell do the Right
-Thing when it no longer references the object. So, for example, C
-could pass a large bitmap over to Haskell and say “please free this
-memory when you're done with it.”
+
+
+
-Please see for more details.
-
-
-
-
+Note: we may relax some of these restrictions in the future.
-The libraries documentatation gives more details on all these
-“primitive array” types and the operations on them.
+The IO and ST monads use unboxed
+tuples to avoid unnecessary allocation during sequences of operations.
+
-
-Data types with no constructors
+
+
+
+Syntactic extensions
+
+
+
+
+ Hierarchical Modules
+
+ GHC supports a small extension to the syntax of module
+ names: a module name is allowed to contain a dot
+ ‘.’. This is also known as the
+ “hierarchical module namespace” extension, because
+ it extends the normally flat Haskell module namespace into a
+ more flexible hierarchy of modules.
+
+ This extension has very little impact on the language
+ itself; modules names are always fully
+ qualified, so you can just think of the fully qualified module
+ name as the module name. In particular, this
+ means that the full module name must be given after the
+ module keyword at the beginning of the
+ module; for example, the module A.B.C must
+ begin
+
+module A.B.C
+
+
+ It is a common strategy to use the as
+ keyword to save some typing when using qualified names with
+ hierarchical modules. For example:
-With the flag, GHC lets you declare
-a data type with no constructors. For example:
- data S -- S :: *
- data T a -- T :: * -> *
+import qualified Control.Monad.ST.Strict as ST
-Syntactically, the declaration lacks the "= constrs" part. The
-type can be parameterised, but only over ordinary types, of kind *; since
-Haskell does not have kind signatures, you cannot parameterise over higher-kinded
-types.
-Such data types have only one value, namely bottom.
-Nevertheless, they can be useful when defining "phantom types".
-
+ For details on how GHC searches for source and interface
+ files in the presence of hierarchical modules, see .
+
+ GHC comes with a large collection of libraries arranged
+ hierarchically; see the accompanying library documentation.
+ There is an ongoing project to create and maintain a stable set
+ of core libraries used by several Haskell
+ compilers, and the libraries that GHC comes with represent the
+ current status of that project. For more details, see Haskell
+ Libraries.
+
+
+
+
-
+Pattern guards
@@ -576,9 +557,96 @@ f x | [y] <- x
Haskell's current guards therefore emerge as a special case, in which the
qualifier list has just one element, a boolean expression.
-
+
+
+
+
+
+The recursive do-notation
+
+
+ The recursive do-notation (also known as mdo-notation) is implemented as described in
+"A recursive do for Haskell",
+Levent Erkok, John Launchbury",
+Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
+
+
+The do-notation of Haskell does not allow recursive bindings,
+that is, the variables bound in a do-expression are visible only in the textually following
+code block. Compare this to a let-expression, where bound variables are visible in the entire binding
+group. It turns out that several applications can benefit from recursive bindings in
+the do-notation, and this extension provides the necessary syntactic support.
+
+
+Here is a simple (yet contrived) example:
+
+
+import Control.Monad.Fix
+
+justOnes = mdo xs <- Just (1:xs)
+ return xs
+
+
+As you can guess justOnes will evaluate to Just [1,1,1,....
+
+
+
+The Control.Monad.Fix library introduces the MonadFix class. It's definition is:
+
+
+class Monad m => MonadFix m where
+ mfix :: (a -> m a) -> m a
+
+
+The function mfix
+dictates how the required recursion operation should be performed. If recursive bindings are required for a monad,
+then that monad must be declared an instance of the MonadFix class.
+For details, see the above mentioned reference.
+
+
+The following instances of MonadFix 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).
+
+
+There are three important points in using the recursive-do notation:
+
+
+The recursive version of the do-notation uses the keyword mdo (rather
+than do).
+
+
+
+You should import Control.Monad.Fix.
+(Note: Strictly speaking, this import is required only when you need to refer to the name
+MonadFix in your program, but the import is always safe, and the programmers
+are encouraged to always import this module when using the mdo-notation.)
+
+
+
+As with other extensions, ghc should be given the flag -fglasgow-exts
+
+
+
+
+
+The web page: http://www.cse.ogi.edu/PacSoft/projects/rmb
+contains up to date information on recursive monadic bindings.
+
-
+
+Historical note: The old implementation of the mdo-notation (and most
+of the existing documents) used the name
+MonadRec for the class and the corresponding library.
+This name is not supported by GHC.
+
+
+
+
+
+
+
+ Parallel List Comprehensionslist comprehensionsparallel
@@ -626,99 +694,318 @@ qualifier list has just one element, a boolean expression.
where `zipN' is the appropriate zip for the given number of
branches.
-
-
-
-Multi-parameter type classes
-
+
-
-This section documents GHC's implementation of multi-parameter type
-classes. There's lots of background in the paper Type
-classes: exploring the design space (Simon Peyton Jones, Mark
-Jones, Erik Meijer).
-
+
+Rebindable syntax
-
-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.)
-
-
-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.
-
+ GHC allows most kinds of built-in syntax to be rebound by
+ the user, to facilitate replacing the Prelude
+ with a home-grown version, for example.
-
-Types
+ You may want to define your own numeric class
+ hierarchy. It completely defeats that purpose if the
+ literal "1" means "Prelude.fromInteger
+ 1", which is what the Haskell Report specifies.
+ So the flag causes
+ the following pieces of built-in syntax to refer to
+ whatever is in scope, not the Prelude
+ versions:
-
-There are the following restrictions on the form of a qualified
-type:
-
+
+
+ Integer and fractional literals mean
+ "fromInteger 1" and
+ "fromRational 3.2", not the
+ Prelude-qualified versions; both in expressions and in
+ patterns.
+ However, the standard Prelude Eq class
+ is still used for the equality test necessary for literal patterns.
+
-
+
+ Negation (e.g. "- (f x)")
+ means "negate (f x)" (not
+ Prelude.negate).
+
-
- forall tv1..tvn (c1, ...,cn) => type
-
+
+ In an n+k pattern, the standard Prelude
+ Ord class is still used for comparison,
+ but the necessary subtraction uses whatever
+ "(-)" is in scope (not
+ "Prelude.(-)").
+
-
+
+ "Do" notation is translated using whatever
+ functions (>>=),
+ (>>), fail, and
+ return, are in scope (not the Prelude
+ versions). List comprehensions, and parallel array
+ comprehensions, are unaffected.
+
-
-(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 ).
-
+ Be warned: this is an experimental facility, with fewer checks than
+ usual. In particular, it is essential that the functions GHC finds in scope
+ must have the appropriate types, namely:
+
+ fromInteger :: forall a. (...) => Integer -> a
+ fromRational :: forall a. (...) => Rational -> a
+ negate :: forall a. (...) => a -> a
+ (-) :: forall a. (...) => a -> a -> a
+ (>>=) :: forall m a. (...) => m a -> (a -> m b) -> m b
+ (>>) :: forall m a. (...) => m a -> m b -> m b
+ return :: forall m a. (...) => a -> m a
+ fail :: forall m a. (...) => String -> m a
+
+ (The (...) part can be any context including the empty context; that part
+ is up to you.)
+ If the functions don't have the right type, very peculiar things may
+ happen. Use -dcore-lint to
+ typecheck the desugared program. If Core Lint is happy you should be all right.
-
+
+
-
-
-
- Each universally quantified type variable
-tvi must be mentioned (i.e. appear free) in type.
+
+
+Type system extensions
-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:
+
+Data types with no constructors
+With the flag, GHC lets you declare
+a data type with no constructors. For example:
- forall a. Eq a => Int
+ data S -- S :: *
+ data T a -- T :: * -> *
+Syntactically, the declaration lacks the "= constrs" part. The
+type can be parameterised over types of any kind, but if the kind is
+not * then an explicit kind annotation must be used
+(see ).
-When a value with this type was used, the constraint Eq tv
-would be introduced where tv is a fresh type variable, and
-(in the dictionary-translation implementation) the value would be
-applied to a dictionary for Eq tv. The difficulty is that we
-can never know which instance of Eq to use because we never
-get any more information about tv.
+Such data types have only one value, namely bottom.
+Nevertheless, they can be useful when defining "phantom types".
+
-
-
-
+
+Infix type constructors
- Every constraint ci must mention at least one of the
-universally quantified type variables tvi.
-
-For example, this type is OK because C a b mentions the
-universally quantified type variable b:
-
-
-
- forall a. C a b => burble
+GHC allows type constructors to be operators, and to be written infix, very much
+like expressions. More specifically:
+
+
+ A type constructor can be an operator, beginning with a colon; e.g. :*:.
+ The lexical syntax is the same as that for data constructors.
+
+
+ Types can be written infix. For example Int :*: Bool.
+
+
+ Back-quotes work
+ as for expressions, both for type constructors and type variables; e.g. Int `Either` Bool, or
+ Int `a` Bool. Similarly, parentheses work the same; e.g. (:*:) Int Bool.
+
+
+ Fixities may be declared for type constructors just as for data constructors. However,
+ one cannot distinguish between the two in a fixity declaration; a fixity declaration
+ sets the fixity for a data constructor and the corresponding type constructor. For example:
+
+ infixl 7 T, :*:
+
+ sets the fixity for both type constructor T and data constructor T,
+ and similarly for :*:.
+ Int `a` Bool.
+
+
+ Function arrow is infixr with fixity 0. (This might change; I'm not sure what it should be.)
+
+
+ Data type and type-synonym declarations can be written infix. E.g.
+
+ data a :*: b = Foo a b
+ type a :+: b = Either a b
+
+
+
+ The only thing that differs between operators in types and operators in expressions is that
+ ordinary non-constructor operators, such as + and *
+ are not allowed in types. Reason: the uniform thing to do would be to make them type
+ variables, but that's not very useful. A less uniform but more useful thing would be to
+ allow them to be type constructors. But that gives trouble in export
+ lists. So for now we just exclude them.
+
+
+
+
+
+
+
+Explicitly-kinded quantification
+
+
+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:
+
+ data Set cxt a = Set [a]
+ | Unused (cxt a -> ())
+
+The only use for the Unused constructor was to force the correct
+kind for the type variable cxt.
+
+
+GHC now instead allows you to specify the kind of a type variable directly, wherever
+a type variable is explicitly bound. Namely:
+
+data declarations:
+
+ data Set (cxt :: * -> *) a = Set [a]
+
+type declarations:
+
+ type T (f :: * -> *) = f Int
+
+class declarations:
+
+ class (Eq a) => C (f :: * -> *) a where ...
+
+forall's in type signatures:
+
+ f :: forall (cxt :: * -> *). Set cxt Int
+
+
+
+
+
+The parentheses are required. Some of the spaces are required too, to
+separate the lexemes. If you write (f::*->*) you
+will get a parse error, because "::*->*" is a
+single lexeme in Haskell.
+
+
+
+As part of the same extension, you can put kind annotations in types
+as well. Thus:
+
+ f :: (Int :: *) -> Int
+ g :: forall a. a -> (a :: *)
+
+The syntax is
+
+ atype ::= '(' ctype '::' kind ')
+
+The parentheses are required.
+
+
+
+
+
+Class method types
+
+
+Haskell 98 prohibits class method types to mention constraints on the
+class type variable, thus:
+
+ class Seq s a where
+ fromList :: [a] -> s a
+ elem :: Eq a => a -> s a -> Bool
+
+The type of elem is illegal in Haskell 98, because it
+contains the constraint Eq a, constrains only the
+class type variable (in this case a).
+
+
+With the GHC lifts this restriction.
+
+
+
+
+
+Multi-parameter type classes
+
+
+
+This section documents GHC's implementation of multi-parameter type
+classes. There's lots of background in the paper Type
+classes: exploring the design space (Simon Peyton Jones, Mark
+Jones, Erik Meijer).
+
+
+
+
+Types
+
+
+GHC imposes the following restrictions on the form of a qualified
+type, whether declared in a type signature
+or inferred. Consider the type:
+
+
+ forall tv1..tvn (c1, ...,cn) => type
+
+
+(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 ).
+
+
+
+
+
+
+
+
+ Each universally quantified type variable
+tvi must be reachable from type.
+
+A type variable is "reachable" if it it is functionally dependent
+(see )
+on the type variables free in type.
+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:
+
+
+
+ forall a. Eq a => Int
+
+
+
+When a value with this type was used, the constraint Eq tv
+would be introduced where tv is a fresh type variable, and
+(in the dictionary-translation implementation) the value would be
+applied to a dictionary for Eq tv. The difficulty is that we
+can never know which instance of Eq to use because we never
+get any more information about tv.
+
+
+
+
+
+
+ Every constraint ci must mention at least one of the
+universally quantified type variables tvi.
+
+For example, this type is OK because C a b mentions the
+universally quantified type variable b:
+
+
+
+ forall a. C a b => burble
@@ -745,10 +1032,6 @@ territory free in case we need it later.
-
-These restrictions apply to all types, whether declared in a type signature
-or inferred.
-
Unlike Haskell 1.4, constraints in types do not have to be of
@@ -769,9 +1052,9 @@ are perfectly OK
This choice recovers principal types, a property that Haskell 1.4 does not have.
-
+
-
+Class declarations
@@ -835,56 +1118,14 @@ be acyclic. So these class declarations are OK:
-
-
-
- In the signature of a class operation, every constraint
-must mention at least one type variable that is not a class type
-variable.
-
-Thus:
-
-
-
- class Collection c a where
- mapC :: Collection c b => (a->b) -> c a -> c b
-
-
-
-is OK because the constraint (Collection a b) mentions
-b, even though it also mentions the class variable
-a. On the other hand:
-
-
-
- class C a where
- op :: Eq a => (a,b) -> (a,b)
-
-
-
-is not OK because the constraint (Eq a) mentions on the class
-type variable a, but not b. However, any such
-example is easily fixed by moving the offending context up to the
-superclass context:
-
-
-
- class Eq a => C a where
- op ::(a,b) -> (a,b)
-
-
-
-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.
-
-
- The type of each class operation must mention all of
-the class type variables. For example:
+ All of the class type variables must be reachable (in the sense
+mentioned in )
+from the free varibles of each method type
+. For example:
@@ -931,9 +1172,9 @@ class like this:
-
+
-
+Instance declarations
@@ -1060,63 +1301,8 @@ For example, this is OK:
instance Stateful (ST s) (MutVar s) where ...
-
-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:
-
-
-
- instance C a => C a where ...
-
-
-
-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:
-
-
-
- instance C a where
- op = ... -- Default
-
-
-
-Second, sometimes you might want to use the following to get the
-effect of a "class synonym":
-
-
-
- class (C1 a, C2 a, C3 a) => C a where { }
-
- instance (C1 a, C2 a, C3 a) => C a where { }
-
-
-
-This allows you to write shorter signatures:
-
-
-
- f :: C a => ...
-
-
-
-instead of
-
-
-
- f :: (C1 a, C2 a, C3 a) => ...
-
-
-
-I'm on the lookout for a simple rule that preserves decidability while
-allowing these idioms. The experimental flag
--fallow-undecidable-instances
-option lifts this restriction, allowing all the types in an
-instance head to be type variables.
-
+See for an experimental
+extension to lift this restriction.
@@ -1178,16 +1364,10 @@ instance C Int b => Foo b where ...
-is not OK. Again, the intent here is to make sure that context
-reduction terminates.
+is not OK. See 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 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 N.
@@ -1196,11 +1376,85 @@ with N.
+
+
-
+
+Undecidable instances
+
+The rules for instance declarations state that:
+
+At least one of the types in the head of
+an instance declaration must not be a type variable.
+
+All of the types in the context of
+an instance declaration must be type variables.
+
+
+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:
+
+ instance C a => C a where ...
+
+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:
+
+
+
+ instance C a where
+ op = ... -- Default
+
+
+
+Second, sometimes you might want to use the following to get the
+effect of a "class synonym":
+
+
+
+ class (C1 a, C2 a, C3 a) => C a where { }
+
+ instance (C1 a, C2 a, C3 a) => C a where { }
+
+
+
+This allows you to write shorter signatures:
+
+
+
+ f :: C a => ...
+
+
+
+instead of
+
+
+
+ f :: (C1 a, C2 a, C3 a) => ...
+
+
+
+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
+-fallow-undecidable-instances
+option, 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 N.
+
+
+I'm on the lookout for a less brutal solution: a simple rule that preserves decidability while
+allowing these idioms interesting idioms.
+
+
-
+Implicit parameters
@@ -1210,13 +1464,76 @@ J Lewis, MB Shields, E Meijer, J Launchbury,
27th ACM Symposium on Principles of Programming Languages (POPL'00),
Boston, Jan 2000.
-
+(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.)
-There should be more documentation, but there isn't (yet). Yell if you need it.
+A variable is called dynamically bound when it is bound by the calling
+context of a function and statically bound when bound by the callee's
+context. In Haskell, all variables are statically bound. Dynamic
+binding of variables is a notion that goes back to Lisp, but was later
+discarded in more modern incarnations, such as Scheme. Dynamic binding
+can be very confusing in an untyped language, and unfortunately, typed
+languages, in particular Hindley-Milner typed languages like Haskell,
+only support static scoping of variables.
-
-
- You can't have an implicit parameter in the context of a class or instance
+
+However, by a simple extension to the type class system of Haskell, we
+can support dynamic binding. Basically, we express the use of a
+dynamically bound variable as a constraint on the type. These
+constraints lead to types of the form (?x::t') => t, which says "this
+function uses a dynamically-bound variable ?x
+of type t'". For
+example, the following expresses the type of a sort function,
+implicitly parameterized by a comparison function named cmp.
+
+ sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
+
+The dynamic binding constraints are just a new form of predicate in the type class system.
+
+
+An implicit parameter occurs in an expression using the special form ?x,
+where x is
+any valid identifier (e.g. ord ?x 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 sortBy function:
+
+ sortBy :: (a -> a -> Bool) -> [a] -> [a]
+
+ sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
+ sort = sortBy ?cmp
+
+
+
+
+Implicit-parameter type constraints
+
+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
+function that called it. For example, our sort function might be used
+to pick out the least value in a list:
+
+ least :: (?cmp :: a -> a -> Bool) => [a] -> a
+ least xs = fst (sort xs)
+
+Without lifting a finger, the ?cmp parameter is
+propagated to become a parameter of least as well. With explicit
+parameters, the default is that parameters must always be explicit
+propagated. With implicit parameters, the default is to always
+propagate them.
+
+
+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 (?x, ?x)
+is (?x::a) => (a,a), and not
+(?x::a, ?x::b) => (a, b), as would be the case for type
+class constraints.
+
+
+ You can't have an implicit parameter in the context of a class or instance
declaration. For example, both these declarations are illegal:
class (?x::Int) => C a where ...
@@ -1226,13 +1543,78 @@ 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.
-
+
+Implicit-parameter constraints do not cause ambiguity. For example, consider:
+
+ f :: (?x :: [a]) => Int -> Int
+ f n = n + length ?x
+
+ g :: (Read a, Show a) => String -> String
+ g s = show (read s)
+
+Here, g has an ambiguous type, and is rejected, but f
+is fine. The binding for ?x at f's call site is
+quite unambiguous, and fixes the type a.
+
+
+
+
+Implicit-parameter bindings
+
+
+An implicit parameter is bound using the standard
+let or where binding forms.
+For example, we define the min function by binding
+cmp.
+
+ min :: [a] -> a
+ min = let ?cmp = (<=) in least
+
+
+
+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 let
+(including in a list comprehension, or do-notation, or pattern guards),
+or a where clause.
+Note the following points:
+
+
+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.
+
+
+You may not mix implicit-parameter bindings with ordinary bindings in a
+single let
+expression; use two nested lets instead.
+(In the case of where you are stuck, since you can't nest where clauses.)
+
+
+You may put multiple implicit-parameter bindings in a
+single binding group; but they are not treated
+as a mutually recursive group (as ordinary let bindings are).
+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:
+
+ f t = let { ?x = t; ?y = ?x+(1::Int) } in ?x + ?y
+
+The use of ?x in the binding for ?y does not "see"
+the binding for ?x, so the type of f is
+
+ f :: (?x::Int) => Int -> Int
+
+
+
-
+
+
-
+Linear implicit parameters
@@ -1256,12 +1638,14 @@ written '%x' instead of '?x'.
For example:
+ import GHC.Exts( Splittable )
+
data NameSupply = ...
splitNS :: NameSupply -> (NameSupply, NameSupply)
newName :: NameSupply -> Name
- instance PrelSplit.Splittable NameSupply where
+ instance Splittable NameSupply where
split = splitNS
@@ -1292,7 +1676,7 @@ the parameter explicit:
Notice the call to 'split' introduced by the type checker.
How did it know to use 'splitNS'? Because what it really did
was to introduce a call to the overloaded function 'split',
-defined by
+defined by the class Splittable:
class Splittable a where
split :: a -> (a,a)
@@ -1306,8 +1690,8 @@ and GHC will infer
g :: (Splittable a, %ns :: a) => b -> (b,a,a)
-The Splittable class is built into GHC. It's defined in PrelSplit,
-and exported by GlaExts.
+The Splittable class is built into GHC. It's exported by module
+GHC.Exts.
Other points:
@@ -1324,7 +1708,7 @@ are entirely distinct implicit parameters: you
-Warnings
+Warnings
The monomorphism restriction is even more important than usual.
@@ -1356,28 +1740,76 @@ parameters we have already lost beta reduction anyway, and
Haskell programs without knowing their typing.
-
+
-
+Recursive functions
+Linear implicit parameters can be particularly tricky when you have a recursive function
+Consider
+
+ foo :: %x::T => Int -> [Int]
+ foo 0 = []
+ foo n = %x : foo (n-1)
+
+where T is some type in class Splittable.
+
+Do you get a list of all the same T's or all different T's
+(assuming that split gives two distinct T's back)?
+
+If you supply the type signature, taking advantage of polymorphic
+recursion, you get what you'd probably expect. Here's the
+translated term, where the implicit param is made explicit:
+
+ foo x 0 = []
+ foo x n = let (x1,x2) = split x
+ in x1 : foo x2 (n-1)
+
+But if you don't supply a type signature, GHC uses the Hindley
+Milner trick of using a single monomorphic instance of the function
+for the recursive calls. That is what makes Hindley Milner type inference
+work. So the translation becomes
+
+ foo x = let
+ foom 0 = []
+ foom n = x : foom (n-1)
+ in
+ foom
+
+Result: 'x' is not split, and you get a list of identical T's. So the
+semantics of the program depends on whether or not foo has a type signature.
+Yikes!
+
+You may say that this is a good reason to dislike linear implicit parameters
+and you'd be right. That is why they are an experimental feature.
+
+
+
+
-
+Functional dependencies
Functional dependencies are implemented as described by Mark Jones
-in "Type Classes with Functional Dependencies", Mark P. Jones,
+in “Type Classes with Functional Dependencies”, Mark P. Jones,
In Proceedings of the 9th European Symposium on Programming,
-ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782.
+ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782,
+.
-
+Functional dependencies are introduced by a vertical bar in the syntax of a
+class declaration; e.g.
+
+ class (Monad m) => MonadState s m | m -> s where ...
+
+ class Foo a b c | a b -> c where ...
+
There should be more documentation, but there isn't (yet). Yell if you need it.
-
+
-
-Explicit universal quantification
+
+Arbitrary-rank polymorphism
@@ -1451,7 +1883,7 @@ a type variable any more!
-
+Examples
@@ -1583,9 +2015,9 @@ and bind to extract the polymorphic bind and return functions
from the MonadT data structure, rather than using pattern
matching.
-
+
-
+Type inference
@@ -1629,10 +2061,10 @@ it is an argument of constructor T1 and that tells GHC all
it needs to know.
-
+
-
+Implicit quantification
@@ -1677,16 +2109,17 @@ 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.
+
-
-
-Type synonyms and hoisting
+
+Liberalised type synonyms
-Type synonmys are like macros at the type level, and GHC is much more liberal
-about them than Haskell 98. In particular:
+Type synonmys are like macros at the type level, and
+GHC does validity checking on types only after expanding type synonyms.
+That means that GHC can be very much more liberal about type synonyms than Haskell 98:
You can write a forall (including overloading)
in a type synonym, thus:
@@ -1711,11 +2144,56 @@ You can write an unboxed tuple in a type synonym:
h x = (# x, x #)
+
+
+You can apply a type synonym to a forall type:
+
+ type Foo a = a -> a -> Bool
+
+ f :: Foo (forall b. b->b)
+
+After expanding the synonym, f has the legal (in GHC) type:
+
+ f :: (forall b. b->b) -> (forall b. b->b) -> Bool
+
+
+
+
+You can apply a type synonym to a partially applied type synonym:
+
+ type Generic i o = forall x. i x -> o x
+ type Id x = x
+
+ foo :: Generic Id []
+
+After epxanding the synonym, foo has the legal (in GHC) type:
+
+ foo :: forall x. x -> [x]
+
+
+
+
+
+GHC currently does kind checking before expanding synonyms (though even that
+could be changed.)
+
-GHC does validity checking on types after expanding type synonyms
-so, for example,
+After expanding type synonyms, GHC does validity checking on types, looking for
+the following mal-formedness which isn't detected simply by kind checking:
+
+
+Type constructor applied to a type involving for-alls.
+
+
+Unboxed tuple on left of an arrow.
+
+
+Partially-applied type synonym.
+
+
+So, for example,
this will be rejected:
type Pr = (# Int, Int #)
@@ -1725,9 +2203,12 @@ this will be rejected:
because GHC does not allow unboxed tuples on the left of a function arrow.
+
+
+For-all hoisting
-However, it is often convenient to use these sort of generalised synonyms at the right hand
+It is often convenient to use generalised type synonyms at the right hand
end of an arrow, thus:
type Discard a = forall b. a -> b -> a
@@ -1759,10 +2240,22 @@ valid way to write g's type signature:
g :: Int -> Int -> forall b. b -> Int
-
+
+When doing this hoisting operation, GHC eliminates duplicate constraints. For
+example:
+
+ type Foo a = (?x::Int) => Bool -> a
+ g :: Foo (Foo Int)
+
+means
+
+ g :: (?x::Int) => Bool -> Bool -> Int
+
+
+
-
+Existentially quantified data constructors
@@ -1852,7 +2345,7 @@ that collection of packages in a uniform manner. You can express
quite a bit of object-oriented-like programming this way.
-
+Why existential?
@@ -1875,9 +2368,9 @@ But Haskell programmers can safely think of the ordinary
adding a new existential quantification construct.
-
+
-
+Type classes
@@ -1937,9 +2430,9 @@ Notice the way that the syntax fits smoothly with that used for
universal quantification earlier.
-
+
-
+Restrictions
@@ -2010,8 +2503,13 @@ bindings. So this is illegal:
f3 x = a==b where { Baz1 a b = x }
+Instead, use a case expression:
+
+
+ f3 x = case x of Baz1 a b -> a==b
+
-You can only pattern-match
+In general, you can only pattern-match
on an existentially-quantified constructor in a case expression or
in the patterns of a function definition.
@@ -2083,92 +2581,12 @@ declarations. Define your own instances!
-
-
-
-
-
-Assertions
-Assertions
-
-
-
-If you want to make use of assertions in your standard Haskell code, you
-could define a function like the following:
-
-
-
-
-
-assert :: Bool -> a -> a
-assert False x = error "assertion failed!"
-assert _ x = x
-
-
-
-
-
-which works, but gives you back a less than useful error message --
-an assertion failed, but which and where?
-
-
-
-One way out is to define an extended assert function which also
-takes a descriptive string to include in the error message and
-perhaps combine this with the use of a pre-processor which inserts
-the source location where assert was used.
-
-
-
-Ghc offers a helping hand here, doing all of this for you. For every
-use of assert in the user's source:
-
-
-
-
-
-kelvinToC :: Double -> Double
-kelvinToC k = assert (k >= 0.0) (k+273.15)
-
-
-
-
-
-Ghc will rewrite this to also include the source location where the
-assertion was made,
-
-
-
-
-
-assert pred val ==> assertError "Main.hs|15" pred val
-
-
-
-
-
-The rewrite is only performed by the compiler when it spots
-applications of Exception.assert, so you can still define and
-use your own versions of assert, should you so wish. If not,
-import Exception to make use assert in your code.
-
-
-
-To have the compiler ignore uses of assert, use the compiler option
-. -fignore-asserts option That is,
-expressions of the form assert pred e will be rewritten to e.
-
-
-
-Assertion failures can be caught, see the documentation for the
-Exception library ()
-for the details.
-
+
-
+
-
-Scoped Type Variables
+
+Scoped type variables
@@ -2218,7 +2636,7 @@ are noted.
So much for the basic idea. Here are the details.
-
+What a pattern type signature means
A type variable brought into scope by a pattern type signature is simply
@@ -2256,9 +2674,9 @@ For example, all of these are legal:
w (x::a) = x -- a unifies with [b]
-
+
-
+Scope and implicit quantification
@@ -2390,52 +2808,9 @@ scope over the methods defined in the where part. For exampl
-
-
-
-Result type signatures
-
-
-
-
-
-
-
- The result type of a function can be given a signature,
-thus:
-
-
-
- f (x::a) :: [a] = [x,x,x]
-
-
-
-The final :: [a] after all the patterns gives a signature to the
-result type. Sometimes this is the only way of naming the type variable
-you want:
-
-
-
- f :: Int -> [a] -> [a]
- f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
- in \xs -> map g (reverse xs `zip` xs)
-
-
-
-
-
-
-
-
-
-
-
-Result type signatures are not yet implemented in Hugs.
-
-
-
+
-
+Where a pattern type signature can occur
@@ -2547,123 +2922,1264 @@ in f4's scope.
-
+
+
+Result type signatures
-
+
+The result type of a function can be given a signature, thus:
-
- Pragmas
- pragma
+
+ f (x::a) :: [a] = [x,x,x]
+
- GHC supports several pragmas, or instructions to the
- compiler placed in the source code. Pragmas don't normally affect
- the meaning of the program, but they might affect the efficiency
- of the generated code.
- Pragmas all take the form
+The final :: [a] after all the patterns gives a signature to the
+result type. Sometimes this is the only way of naming the type variable
+you want:
-{-# word ... #-}
- where word indicates the type of
- pragma, and is followed optionally by information specific to that
- type of pragma. Case is ignored in
- word. The various values for
- word that GHC understands are described
- in the following sections; any pragma encountered with an
- unrecognised word is (silently)
- ignored.
+
+ f :: Int -> [a] -> [a]
+ f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
+ in \xs -> map g (reverse xs `zip` xs)
+
-
-INLINE pragma
+
+
+The type variables bound in a result type signature scope over the right hand side
+of the definition. However, consider this corner-case:
+
+ rev1 :: [a] -> [a] = \xs -> reverse xs
-INLINE pragma
-pragma, INLINE
+ foo ys = rev (ys::[a])
+
+The signature on rev1 is considered a pattern type signature, not a result
+type signature, and the type variables it binds have the same scope as rev1
+itself (i.e. the right-hand side of rev1 and the rest of the module too).
+In particular, the expression (ys::[a]) is OK, because the type variable a
+is in scope (otherwise it would mean (ys::forall a.[a]), which would be rejected).
+
+
+As mentioned above, rev1 is made monomorphic by this scoping rule.
+For example, the following program would be rejected, because it claims that rev1
+is polymorphic:
+
+ rev1 :: [b] -> [b]
+ rev1 :: [a] -> [a] = \xs -> reverse xs
+
+
-GHC (with , 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.
+Result type signatures are not yet implemented in Hugs.
+
+
+
+
+
+Deriving clause for classes Typeable and Data
+
-You will probably see these unfoldings (in Core syntax) in your
-interface files.
+Haskell 98 allows the programmer to add "deriving( Eq, Ord )" to a data type
+declaration, to generate a standard instance declaration for classes specified in the deriving clause.
+In Haskell 98, the only classes that may appear in the deriving clause are the standard
+classes Eq, Ord,
+Enum, Ix, Bounded, Read, and Show.
+
+GHC extends this list with two more classes that may be automatically derived
+(provided the flag is specified):
+Typeable, and Data. These classes are defined in the library
+modules Data.Dynamic and Data.Generics respectively, and the
+appropriate class must be in scope before it can be mentioned in the deriving clause.
+
+
+
+
+Generalised derived instances for newtypes
-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.
+When you define an abstract type using newtype, you may want
+the new type to inherit some instances from its representation. In
+Haskell 98, you can inherit instances of Eq, Ord,
+Enum and Bounded by deriving them, but for any
+other classes you have to write an explicit instance declaration. For
+example, if you define
+
+
+ newtype Dollars = Dollars Int
+
+
+and you want to use arithmetic on Dollars, you have to
+explicitly define an instance of Num:
+
+
+ instance Num Dollars where
+ Dollars a + Dollars b = Dollars (a+b)
+ ...
+
+All the instance does is apply and remove the newtype
+constructor. It is particularly galling that, since the constructor
+doesn't appear at run-time, this instance declaration defines a
+dictionary which is wholly equivalent to the Int
+dictionary, only slower!
+
+ Generalising the deriving clause
-The sledgehammer you can bring to bear is the
-INLINEINLINE pragma pragma, used thusly:
+GHC now permits such instances to be derived instead, so one can write
+
+ newtype Dollars = Dollars Int deriving (Eq,Show,Num)
+
-
-key_function :: Int -> String -> (Bool, Double)
+and the implementation uses the sameNum dictionary
+for Dollars as for Int. Notionally, the compiler
+derives an instance declaration of the form
-#ifdef __GLASGOW_HASKELL__
-{-# INLINE key_function #-}
-#endif
+
+ instance Num Int => Num Dollars
+
+
+which just adds or removes the newtype constructor according to the type.
+
+
+
+We can also derive instances of constructor classes in a similar
+way. For example, suppose we have implemented state and failure monad
+transformers, such that
+
+
+ instance Monad m => Monad (State s m)
+ instance Monad m => Monad (Failure m)
+
+In Haskell 98, we can define a parsing monad by
+
+ type Parser tok m a = State [tok] (Failure m) a
+
+
+which is automatically a monad thanks to the instance declarations
+above. With the extension, we can make the parser type abstract,
+without needing to write an instance of class Monad, via
+
+
+ newtype Parser tok m a = Parser (State [tok] (Failure m) a)
+ deriving Monad
+
+In this case the derived instance declaration is of the form
+
+ instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
+
+
+Notice that, since Monad is a constructor class, the
+instance is a partial application of the new type, not the
+entire left hand side. We can imagine that the type declaration is
+``eta-converted'' to generate the context of the instance
+declaration.
+
+
+
+We can even derive instances of multi-parameter classes, provided the
+newtype is the last class parameter. In this case, a ``partial
+application'' of the class appears in the deriving
+clause. For example, given the class
+
+
+ class StateMonad s m | m -> s where ...
+ instance Monad m => StateMonad s (State s m) where ...
+
+then we can derive an instance of StateMonad for Parsers by
+
+ newtype Parser tok m a = Parser (State [tok] (Failure m) a)
+ deriving (Monad, StateMonad [tok])
+
+
+The derived instance is obtained by completing the application of the
+class to the new type:
+
+
+ instance StateMonad [tok] (State [tok] (Failure m)) =>
+ StateMonad [tok] (Parser tok m)
+
+
-(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 INLINE pragmas.)
+As a result of this extension, all derived instances in newtype
+declarations are treated uniformly (and implemented just by reusing
+the dictionary for the representation type), except
+Show and Read, which really behave differently for
+the newtype and its representation.
+
+ A more precise specification
-The major effect of an INLINE pragma is to declare a function's
-“cost” to be very low. The normal unfolding machinery will then be
-very keen to inline it.
+Derived instance declarations are constructed as follows. Consider the
+declaration (after expansion of any type synonyms)
+
+
+ newtype T v1...vn = T' (S t1...tk vk+1...vn) deriving (c1...cm)
+
+
+where
+
+
+ S is a type constructor,
+
+
+ t1...tk are types,
+
+
+ vk+1...vn are type variables which do not occur in any of
+ the ti, and
+
+
+ the ci are partial applications of
+ classes of the form C t1'...tj', where the arity of C
+ is exactly j+1. That is, C lacks exactly one type argument.
+
+
+Then, for each ci, the derived instance
+declaration is:
+
+ instance ci (S t1...tk vk+1...v) => ci (T v1...vp)
+
+where p is chosen so that T v1...vp is of the
+right kind for the last parameter of class Ci.
+
+
+As an example which does not work, consider
+
+ newtype NonMonad m s = NonMonad (State s m s) deriving Monad
+
+Here we cannot derive the instance
+
+ instance Monad (State s m) => Monad (NonMonad m)
+
+because the type variable s occurs in State s m,
+and so cannot be "eta-converted" away. It is a good thing that this
+deriving clause is rejected, because NonMonad m is
+not, in fact, a monad --- for the same reason. Try defining
+>>= with the correct type: you won't be able to.
+
-An INLINE pragma for a function can be put anywhere its type
-signature could be put.
+
+Notice also that the order of class parameters becomes
+important, since we can only derive instances for the last one. If the
+StateMonad class above were instead defined as
+
+
+ class StateMonad m s | m -> s where ...
+
+
+then we would not have been able to derive an instance for the
+Parser type above. We hypothesise that multi-parameter
+classes usually have one "main" parameter for which deriving new
+instances is most interesting.
+
+
+
+
+
+
+
+
+
+
+
+
+Template Haskell
+
+Template Haskell allows you to do compile-time meta-programming in Haskell. There is a "home page" for
+Template Haskell at
+http://www.haskell.org/th/, while
+the background to
+the main technical innovations is discussed in "
+Template Meta-programming for Haskell" (Proc Haskell Workshop 2002).
+
+
+ The first example from that paper is set out below as a worked example to help get you started.
+
+
+
+The documentation here describes the realisation in GHC. (It's rather sketchy just now;
+Tim Sheard is going to expand it.)
+
+
+ Syntax
+
+ Template Haskell has the following new syntactic constructions. You need to use the flag
+ -fglasgow-exts to switch these syntactic extensions on.
+
+
+
+ A splice is written $x, where x is an
+ identifier, or $(...), where the "..." is an arbitrary expression.
+ There must be no space between the "$" and the identifier or parenthesis. This use
+ of "$" overrides its meaning as an infix operator, just as "M.x" overrides the meaning
+ of "." as an infix operator. If you want the infix operator, put spaces around it.
+
+ A splice can occur in place of
+
+ an expression; the spliced expression must have type Expr
+ a list of top-level declarations; ; the spliced expression must have type Q [Dec]
+ a type; the spliced expression must have type Type.
+
+ (Note that the syntax for a declaration splice uses "$" not "splice" as in
+ the paper. Also the type of the enclosed expression must be Q [Dec], not [Q Dec]
+ as in the paper.)
+
+
+
+
+ A expression quotation is written in Oxford brackets, thus:
+
+ [| ... |], where the "..." is an expression;
+ the quotation has type Expr.
+ [d| ... |], where the "..." is a list of top-level declarations;
+ the quotation has type Q [Dec].
+ [t| ... |], where the "..." is a type;
+ the quotation has type Type.
+
+
+
+ Reification is written thus:
+
+ reifyDecl T, where T is a type constructor; this expression
+ has type Dec.
+ reifyDecl C, where C is a class; has type Dec.
+ reifyType f, where f is an identifier; has type Typ.
+ Still to come: fixities
+
+
+
+
+
+
+
+ Using Template Haskell
-INLINE pragmas are a particularly good idea for the
-then/return (or bind/unit) functions in a monad.
-For example, in GHC's own UniqueSupply monad code, we have:
+
+
+ The data types and monadic constructor functions for Template Haskell are in the library
+ Language.Haskell.THSyntax.
+
+
+
+ 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.)
+
+
+
+ The flag -ddump-splices shows the expansion of all top-level splices as they happen.
+
+
+ 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.
+
+
+
+ Template Haskell works in any mode (--make, --interactive,
+ or file-at-a-time). There used to be a restriction to the former two, but that restriction
+ has been lifted.
+
+
+
+ A Template Haskell Worked Example
+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":
-#ifdef __GLASGOW_HASKELL__
-{-# INLINE thenUs #-}
-{-# INLINE returnUs #-}
-#endif
+{- 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") )
+
+{- 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)
+
+
+Now run the compiler (here we are using a "stage three" build of GHC, at a Cygwin prompt on Windows):
+
+ghc/compiler/stage3/ghc-inplace --make -fglasgow-exts -package haskell-src main.hs -o main.exe
+
+
+Run "main.exe" and here is your output:
+
+
+
+$ ./main
+Hello
+
+
+
-
-NOINLINE pragma
+
+
+
+Arrow notation
-NOINLINE pragma
-pragmaNOINLINE
-NOTINLINE pragma
-pragmaNOTINLINE
+Arrows are a generalization of monads introduced by John Hughes.
+For more details, see
+
+
+
+
+“Generalising Monads to Arrows”,
+John Hughes, in Science of Computer Programming 37,
+pp67–111, May 2000.
+
+
+
+
+
+“A New Notation for Arrows”,
+Ross Paterson, in ICFP, Sep 2001.
+
+
+
-The NOINLINE 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.
+“Arrows and Computation”,
+Ross Paterson, in The Fun of Programming,
+Palgrave, 2003.
+
+
+
+
+and the arrows web page at
+http://www.haskell.org/arrows/.
+With the 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
+Control.Arrow
+module.
+
+
+The extension adds a new kind of expression for defining arrows,
+of the form proc pat -> cmd,
+where proc is a new keyword.
+The variables of the pattern are bound in the body of the
+proc-expression,
+which is a new sort of thing called a command.
+The syntax of commands is as follows:
+
+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
+
+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.
+
+
+
+A simple example of the new notation is the expression
+
+proc x -> f -< x+1
+
+We call this a procedure or
+arrow abstraction.
+As with a lambda expression, the variable x
+is a new variable bound within the proc-expression.
+It refers to the input to the arrow.
+In the above example, -< 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
+
+arr (\ x -> x+1) >>> f
+
+That would make no sense if the expression to the left of
+-< involves the bound variable x.
+More generally, the expression to the left of -<
+may not involve any local variable,
+i.e. a variable bound in the current arrow abstraction.
+For such a situation there is a variant -<<, as in
+
+proc x -> f x -<< x+1
+
+which is equivalent to
+
+arr (\ x -> (f, x+1)) >>> app
+
+so in this case the arrow must belong to the ArrowApply
+class.
+Such an arrow is equivalent to a monad, so if you're using this form
+you may find a monadic formulation more convenient.
-NOTINLINE is a synonym for
-NOINLINE (NOTINLINE 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).
+
+do-notation for commands
+
+
+Another form of command is a form of do-notation.
+For example, you can write
+
+proc x -> do
+ y <- f -< x+1
+ g -< 2*y
+ let z = x+y
+ t <- h -< x*z
+ returnA -< t+z
+
+You can read this much like ordinary do-notation,
+but with commands in place of monadic expressions.
+The first line sends the value of x+1 as an input to
+the arrow f, and matches its output against
+y.
+In the next line, the output is discarded.
+The arrow returnA is defined in the
+Control.Arrow
+module as arr id.
+The above example is treated as an abbreviation for
+
+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
+
+Note that variables not used later in the composition are projected out.
+After simplification using rewrite rules (see )
+defined in the
+Control.Arrow
+module, this reduces to
+
+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)
+
+which is what you might have written by hand.
+With arrow notation, GHC keeps track of all those tuples of variables for you.
+
+
+
+Note that although the above translation suggests that
+let-bound variables like z must be
+monomorphic, the actual translation produces Core,
+so polymorphic variables are allowed.
+
+
+
+It's also possible to have mutually recursive bindings,
+using the new rec keyword, as in the following example:
+
+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
+
+The translation of such forms uses the loop combinator,
+so the arrow concerned must belong to the ArrowLoop class.
+
+
+
+
+
+Conditional commands
+
+
+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
+
+proc (x,y) ->
+ if f x y
+ then g -< x+1
+ else h -< y+2
+
+which is translated to
+
+arr (\ (x,y) -> if f x y then Left x else Right y) >>>
+ (arr (\x -> x+1) >>> f) ||| (arr (\y -> y+2) >>> g)
+
+Since the translation uses |||,
+the arrow concerned must belong to the ArrowChoice class.
+
+
+
+There are also case commands, like
+
+case input of
+ [] -> f -< ()
+ [x] -> g -< x+1
+ x1:x2:xs -> do
+ y <- h -< (x1, x2)
+ ys <- k -< xs
+ returnA -< y:ys
+
+The syntax is the same as for case expressions,
+except that the bodies of the alternatives are commands rather than expressions.
+The translation is similar to that of if commands.
+
+
+Defining your own control structures
+
+
+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 ArrowChoice class includes a combinator
+
+ArrowChoice a => (<+>) :: a e c -> a e c -> a e c
+
+so we can use it to build commands:
+
+expr' = proc x ->
+ returnA -< x
+ <+> do
+ symbol Plus -< ()
+ y <- term -< ()
+ expr' -< x + y
+ <+> do
+ symbol Minus -< ()
+ y <- term -< ()
+ expr' -< x - y
+
+This is equivalent to
+
+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)
+
+It is essential that this operator be polymorphic in e
+(representing the environment input to the command
+and thence to its subcommands)
+and satisfy the corresponding naturality property
+
+arr k >>> (f <+> g) = (arr k >>> f) <+> (arr k >>> g)
+
+at least for strict k.
+(This should be automatic if you're not using seq.)
+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.
+
+
+
+We could define our own operator
+
+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
+
+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:
+
+proc x -> do
+ y <- f -< x+1
+ (|untilA (increment -< x+y) (within 0.5 -< x)|)
+
+
+
+
+
+
+Primitive constructs
+
+
+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
+
+handleA :: ... => a e c -> a (e,Ex) c -> a e c
+
+where Ex is the type of exceptions handled.
+You could then use this with arrow notation by writing a command
+
+body `handleA` \ ex -> handler
+
+so that if an exception is raised in the command body,
+the variable ex is bound to the value of the exception
+and the command handler,
+which typically refers to ex, 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 handleA,
+this stack consists of one value, the value of the exception.
+The command form of lambda merely gives this value a name.
+
+
+
+More concretely,
+the values on the stack are paired to the right of the environment.
+So when designing operators like handleA that pass
+extra inputs to their subcommands,
+More precisely, the type of each argument of the operator (and its result)
+should have the form
+
+a (...(e,t1), ... tn) t
+
+where e is a polymorphic variable
+(representing the environment)
+and ti are the types of the values on the stack,
+with t1 being the top.
+The polymorphic variable e must not occur in
+a, ti or
+t.
+However the arrows involved need not be the same.
+Here are some more examples of suitable operators:
+
+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)
+
+We can supply the extra input required by commands built with the last two
+by applying them to ordinary expressions, as in
+
+proc x -> do
+ s <- ...
+ (|runReader (do { ... })|) s
+
+which adds s to the stack of inputs to the command
+built using runReader.
+
+
+
+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 do-notation by defining
+
+bind :: Arrow a => a e b -> a (e,b) c -> a e c
+u `bind` f = returnA &&& u >>> f
+
+bind_ :: Arrow a => a e b -> a e c -> a e c
+u `bind_` f = u `bind` (arr fst >>> f)
+
+We could simulate do by defining
+
+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
+
+
+
+
+
+
+Differences with the paper
+
+
+
+
+Instead of a single form of arrow application (arrow tail) with two
+translations, the implementation provides two forms
+-< (first-order)
+and -<< (higher-order).
+
+
+
+
+User-defined operators are flagged with banana brackets instead of
+a new form keyword.
+
+
+
+
+
+
+
+
+Portability
+
+
+Although only GHC implements arrow notation directly,
+there is also a preprocessor
+(available from the
+arrows web page>)
+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:
+
+
+
+
+The module must import
+Control.Arrow.
+
+
+
+
+
+The preprocessor cannot cope with other Haskell extensions.
+These would have to go in separate modules.
+
+
+
+
+
+Because the preprocessor targets Haskell (rather than Core),
+let-bound variables are monomorphic.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Assertions
+Assertions
+
+
+
+If you want to make use of assertions in your standard Haskell code, you
+could define a function like the following:
+
+
+
+
+
+assert :: Bool -> a -> a
+assert False x = error "assertion failed!"
+assert _ x = x
+
+
+
+
+
+which works, but gives you back a less than useful error message --
+an assertion failed, but which and where?
+
+
+
+One way out is to define an extended assert function which also
+takes a descriptive string to include in the error message and
+perhaps combine this with the use of a pre-processor which inserts
+the source location where assert was used.
+
+
+
+Ghc offers a helping hand here, doing all of this for you. For every
+use of assert in the user's source:
+
+
+
+
+
+kelvinToC :: Double -> Double
+kelvinToC k = assert (k >= 0.0) (k+273.15)
+
+
+
+
+
+Ghc will rewrite this to also include the source location where the
+assertion was made,
+
+
+
+
+
+assert pred val ==> assertError "Main.hs|15" pred val
+
+
+
+
+
+The rewrite is only performed by the compiler when it spots
+applications of Control.Exception.assert, so you
+can still define and use your own versions of
+assert, should you so wish. If not, import
+Control.Exception to make use
+assert in your code.
+
+
+
+To have the compiler ignore uses of assert, use the compiler option
+. -fignore-asserts
+option That is, expressions of the form
+assert pred e will be rewritten to
+e.
+
+
+
+Assertion failures can be caught, see the documentation for the
+Control.Exception library for the details.
+
+
+
+
+
+
+
+
+ Pragmas
+
+ pragma
+
+ GHC supports several pragmas, or instructions to the
+ compiler placed in the source code. Pragmas don't normally affect
+ the meaning of the program, but they might affect the efficiency
+ of the generated code.
+
+ Pragmas all take the form
+
+{-# word ... #-}
+
+ where word indicates the type of
+ pragma, and is followed optionally by information specific to that
+ type of pragma. Case is ignored in
+ word. The various values for
+ word that GHC understands are described
+ in the following sections; any pragma encountered with an
+ unrecognised word is (silently)
+ ignored.
+
+
+ DEPRECATED pragma
+ DEPRECATED
+
+
+ The DEPRECATED pragma lets you specify that a particular
+ function, class, or type, is deprecated. There are two
+ forms.
+
+
+
+ You can deprecate an entire module thus:
+
+ module Wibble {-# DEPRECATED "Use Wobble instead" #-} where
+ ...
+
+ When you compile any module that import
+ Wibble, GHC will print the specified
+ message.
+
+
+
+ You can deprecate a function, class, or type, with the
+ following top-level declaration:
+
+ {-# DEPRECATED f, C, T "Don't use these" #-}
+
+ When you compile any module that imports and uses any
+ of the specifed entities, GHC will print the specified
+ message.
+
+
+
+ You can suppress the warnings with the flag
+ .
+
+
+
+ INLINE and NOINLINE pragmas
+
+ These pragmas control the inlining of function
+ definitions.
+
+
+ INLINE pragma
+ INLINE
+
+ GHC (with , 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.
+
+ The sledgehammer you can bring to bear is the
+ INLINEINLINE
+ pragma pragma, used thusly:
+
+
+key_function :: Int -> String -> (Bool, Double)
+
+#ifdef __GLASGOW_HASKELL__
+{-# INLINE key_function #-}
+#endif
+
+
+ (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 INLINE pragmas.)
+
+ The major effect of an INLINE pragma
+ is to declare a function's “cost” to be very low.
+ The normal unfolding machinery will then be very keen to
+ inline it.
+
+ Syntactially, an INLINE pragma for a
+ function can be put anywhere its type signature could be
+ put.
+
+ INLINE pragmas are a particularly
+ good idea for the
+ then/return (or
+ bind/unit) functions in
+ a monad. For example, in GHC's own
+ UniqueSupply monad code, we have:
+
+
+#ifdef __GLASGOW_HASKELL__
+{-# INLINE thenUs #-}
+{-# INLINE returnUs #-}
+#endif
+
+
+ See also the NOINLINE pragma ().
+
+
+
+ NOINLINE pragma
+
+ NOINLINE
+ NOTINLINE
+
+ The NOINLINE 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.
+
+ NOTINLINE is a synonym for
+ NOINLINE (NOTINLINE 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).
+
+
+
+ Phase control
+
+ Sometimes you want to control exactly when in GHC's
+ pipeline the INLINE pragma is switched on. Inlining happens
+ only during runs of the simplifier. Each
+ run of the simplifier has a different phase
+ number; the phase number decreases towards zero.
+ If you use 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:
+
+
+
+ You can say "inline f in Phase 2
+ and all subsequent phases":
+
+ {-# INLINE [2] f #-}
+
+
+
+
+
+ You can say "inline g in all
+ phases up to, but not including, Phase 3":
+
+ {-# INLINE [~3] g #-}
+
+
+
+
+
+ If you omit the phase indicator, you mean "inline in
+ all phases".
+
+
+
+ You can use a phase number on a NOINLINE pragma too:
+
+
+
+ You can say "do not inline f
+ until Phase 2; in Phase 2 and subsequently behave as if
+ there was no pragma at all":
+
+ {-# NOINLINE [2] f #-}
+
+
+
+
+
+ You can say "do not inline g in
+ Phase 3 or any subsequent phase; before that, behave as if
+ there was no pragma":
+
+ {-# NOINLINE [~3] g #-}
+
+
+
+
+
+ If you omit the phase indicator, you mean "never
+ inline this function".
+
+
+
+ The same phase-numbering control is available for RULES
+ ().
+
+
+
+
+ LINE pragma
+
+ LINEpragma
+ pragmaLINE
+ This pragma is similar to C's #line
+ 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
+
+
+{-# LINE 42 "Foo.vhs" #-}
+
+
+ if you'd generated the current file from something called
+ Foo.vhs 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 LINE
+ pragma.
+
+
+
+ OPTIONS pragma
+ OPTIONS
+
+ pragmaOPTIONS
+
+
+ The OPTIONS pragma is used to specify
+ additional options that are given to the compiler when compiling
+ this source file. See for
+ details.
+
+
+
+ RULES pragma
+
+ The RULES pragma lets you specify rewrite rules. It is
+ described in .
+
+
SPECIALIZE pragma
@@ -2688,35 +4204,37 @@ hammeredLookup :: Ord key => [(key, value)] -> key -> value
{-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-}
- To get very fancy, you can also specify a named function
- to use for the specialised value, as in:
+ A SPECIALIZE pragma for a function can
+ be put anywhere its type signature could be put.
+A SPECIALIZE has the effect of generating (a) a specialised
+version of the function and (b) a rewrite rule (see ) 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:
-{-# RULES hammeredLookup = blah #-}
+ genericLookup :: Ord a => Table a b -> a -> b
+ intLookup :: Table Int b -> Int -> b
-
- where blah is an implementation of
- hammerdLookup written specialy for
- Widget lookups. It's Your
+where intLookup is an implementation of genericLookup
+that works very fast for keys of type Int. Then you can write the rule
+
+ {-# RULES "intLookup" genericLookup = intLookup #-}
+
+(see ). It is Your
Responsibility to make sure that
- blah really behaves as a specialised
- version of hammeredLookup!!!
-
- Note we use the RULE pragma here to
- indicate that hammeredLookup applied at a
- certain type should be replaced by blah. See
- for more information on
- RULES.
+ intLookup really behaves as a specialised
+ version of genericLookup!!!An example in which using RULES for
specialisation will Win Big:
-toDouble :: Real a => a -> Double
-toDouble = fromRational . toRational
+ toDouble :: Real a => a -> Double
+ toDouble = fromRational . toRational
-{-# SPECIALIZE toDouble :: Int -> Double = 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
The i2d function is virtually one machine
@@ -2724,9 +4242,6 @@ i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
Rational—is obscenely expensive by
comparison.
- A SPECIALIZE pragma for a function can
- be put anywhere its type signature could be put.
-
@@ -2754,86 +4269,12 @@ of the pragma.
-
-LINE pragma
-
-
-
-LINE pragma
-pragma, LINE
-
-
-
-This pragma is similar to C's #line 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
-
-
-
-
-
-{-# LINE 42 "Foo.vhs" #-}
-
-
-
-
-
-if you'd generated the current file from something called Foo.vhs
-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 LINE
-pragma.
-
-
-
-
-
-RULES pragma
-
-
-The RULES pragma lets you specify rewrite rules. It is described in
-.
-
-
-
-
-
-DEPRECATED pragma
-
-
-The DEPRECATED pragma lets you specify that a particular function, class, or type, is deprecated.
-There are two forms.
-
-
-
-You can deprecate an entire module thus:
-
- module Wibble {-# DEPRECATED "Use Wobble instead" #-} where
- ...
-
-
-When you compile any module that import Wibble, GHC will print
-the specified message.
-
-
-
-
-You can deprecate a function, class, or type, with the following top-level declaration:
-
-
- {-# DEPRECATED f, C, T "Don't use these" #-}
-
-
-When you compile any module that imports and uses any of the specifed entities,
-GHC will print the specified message.
-
-
-
-You can suppress the warnings with the flag .
-
+
+
Rewrite rules
@@ -2843,7 +4284,10 @@ GHC will print the specified message.
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 flag () is on,
+and (b) the flag
+() is not specified.
@@ -2867,16 +4311,34 @@ From a syntactic point of view:
+ There may be zero or more rules in a RULES pragma.
+
+
+
+
+
+
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.
-
+
- There may be zero or more rules in a RULES pragma.
+A rule may optionally have a phase-control number (see ),
+immediately after the name of the rule. Thus:
+
+ {-# RULES
+ "map/map" [2] forall f g xs. map f (map g xs) = map (f.g) xs
+ #-}
+
+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.
+
+
@@ -2885,6 +4347,7 @@ is set, so you must lay out your rules starting in the same column as the
enclosing definitions.
+
@@ -3272,7 +4735,7 @@ will fuse with one but not the other)
-
+
So, for example, the following should generate no intermediate lists:
@@ -3360,7 +4823,7 @@ If you add you get a more detailed listing.
- The defintion of (say) build in PrelBase.lhs looks llike this:
+ The defintion of (say) build in GHC/Base.lhs looks llike this:
build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
@@ -3378,9 +4841,9 @@ in the RHS of the INLINE thing. I regret the delicacy of thi
- In ghc/lib/std/PrelBase.lhs look at the rules for map to
+ In libraries/base/GHC/Base.lhs look at the rules for map to
see how to write rules that will do fusion and yet give an efficient
-program even if fusion doesn't happen. More rules in PrelList.lhs.
+program even if fusion doesn't happen. More rules in GHC/List.lhs.
@@ -3390,6 +4853,69 @@ program even if fusion doesn't happen. More rules in PrelList.lhs
+
+ CORE pragma
+
+ CORE pragma
+ pragma, CORE
+ core, annotation
+
+
+ The external core format supports Note annotations;
+ the CORE 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:
+
+
+f x = ({-# CORE "foo" #-} show) ({-# CORE "bar" #-} x)
+
+
+ Sematically, this is equivalent to:
+
+
+g x = show x
+
+
+
+
+ However, when external for is generated (via
+ ), there will be Notes attached to the
+ expressions show and x.
+ The core function declaration for f is:
+
+
+
+ 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);
+
+
+
+ Here, we can see that the function show (which
+ has been expanded out to a case expression over the Show dictionary)
+ has a %note attached to it, as does the
+ expression eta (which used to be called
+ x).
+
+
+
+
@@ -3438,7 +4964,7 @@ Now you can make a data type into an instance of Bin like this:
instance (Bin a, Bin b) => Bin (a,b)
instance Bin a => Bin [a]
-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.
@@ -3648,179 +5174,6 @@ Just to finish with, here's another example I rather like:
-
-Generalised derived instances for newtypes
-
-
-When you define an abstract type using newtype, you may want
-the new type to inherit some instances from its representation. In
-Haskell 98, you can inherit instances of Eq, Ord,
-Enum and Bounded by deriving them, but for any
-other classes you have to write an explicit instance declaration. For
-example, if you define
-
-
- newtype Dollars = Dollars Int
-
-
-and you want to use arithmetic on Dollars, you have to
-explicitly define an instance of Num:
-
-
- instance Num Dollars where
- Dollars a + Dollars b = Dollars (a+b)
- ...
-
-All the instance does is apply and remove the newtype
-constructor. It is particularly galling that, since the constructor
-doesn't appear at run-time, this instance declaration defines a
-dictionary which is wholly equivalent to the Int
-dictionary, only slower!
-
-
- Generalising the deriving clause
-
-GHC now permits such instances to be derived instead, so one can write
-
- newtype Dollars = Dollars Int deriving (Eq,Show,Num)
-
-
-and the implementation uses the sameNum dictionary
-for Dollars as for Int. Notionally, the compiler
-derives an instance declaration of the form
-
-
- instance Num Int => Num Dollars
-
-
-which just adds or removes the newtype constructor according to the type.
-
-
-
-We can also derive instances of constructor classes in a similar
-way. For example, suppose we have implemented state and failure monad
-transformers, such that
-
-
- instance Monad m => Monad (State s m)
- instance Monad m => Monad (Failure m)
-
-In Haskell 98, we can define a parsing monad by
-
- type Parser tok m a = State [tok] (Failure m) a
-
-
-which is automatically a monad thanks to the instance declarations
-above. With the extension, we can make the parser type abstract,
-without needing to write an instance of class Monad, via
-
-
- newtype Parser tok m a = Parser (State [tok] (Failure m) a)
- deriving Monad
-
-In this case the derived instance declaration is of the form
-
- instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
-
-
-Notice that, since Monad is a constructor class, the
-instance is a partial application of the new type, not the
-entire left hand side. We can imagine that the type declaration is
-``eta-converted'' to generate the context of the instance
-declaration.
-
-
-
-We can even derive instances of multi-parameter classes, provided the
-newtype is the last class parameter. In this case, a ``partial
-application'' of the class appears in the deriving
-clause. For example, given the class
-
-
- class StateMonad s m | m -> s where ...
- instance Monad m => StateMonad s (State s m) where ...
-
-then we can derive an instance of StateMonad for Parsers by
-
- newtype Parser tok m a = Parser (State [tok] (Failure m) a)
- deriving (Monad, StateMonad [tok])
-
-
-The derived instance is obtained by completing the application of the
-class to the new type:
-
-
- instance StateMonad [tok] (State [tok] (Failure m)) =>
- StateMonad [tok] (Parser tok m)
-
-
-
-
-As a result of this extension, all derived instances in newtype
-declarations are treated uniformly (and implemented just by reusing
-the dictionary for the representation type), except
-Show and Read, which really behave differently for
-the newtype and its representation.
-
-
-
- A more precise specification
-
-Derived instance declarations are constructed as follows. Consider the
-declaration (after expansion of any type synonyms)
-
-
- newtype T v1...vn = T' (S t1...tk vk+1...vn) deriving (c1...cm)
-
-
-where S is a type constructor, t1...tk are
-types,
-vk+1...vn are type variables which do not occur in any of
-the ti, and the ci are partial applications of
-classes of the form C t1'...tj'. The derived instance
-declarations are, for each ci,
-
-
- instance ci (S t1...tk vk+1...v) => ci (T v1...vp)
-
-where p is chosen so that T v1...vp is of the
-right kind for the last parameter of class Ci.
-
-
-
-As an example which does not work, consider
-
- newtype NonMonad m s = NonMonad (State s m s) deriving Monad
-
-Here we cannot derive the instance
-
- instance Monad (State s m) => Monad (NonMonad m)
-
-
-because the type variable s occurs in State s m,
-and so cannot be "eta-converted" away. It is a good thing that this
-deriving clause is rejected, because NonMonad m is
-not, in fact, a monad --- for the same reason. Try defining
->>= with the correct type: you won't be able to.
-
-
-
-Notice also that the order of class parameters becomes
-important, since we can only derive instances for the last one. If the
-StateMonad class above were instead defined as
-
-
- class StateMonad m s | m -> s where ...
-
-
-then we would not have been able to derive an instance for the
-Parser type above. We hypothesise that multi-parameter
-classes usually have one "main" parameter for which deriving new
-instances is most interesting.
-
-
-
-