2 % $Id: glasgow_exts.vsgml,v 1.10 1999/05/04 08:31:52 sof Exp $
4 % GHC Language Extensions.
7 As with all known Haskell systems, GHC implements some extensions to
8 the language. To use them, you'll need to give a @-fglasgow-exts@%
9 <nidx>-fglasgow-exts option</nidx> option.
11 Virtually all of the Glasgow extensions serve to give you access to
12 the underlying facilities with which we implement Haskell. Thus, you
13 can get at the Raw Iron, if you are willing to write some non-standard
14 code at a more primitive level. You need not be ``stuck'' on
15 performance because of the implementation costs of Haskell's
16 ``high-level'' features---you can always code ``under'' them. In an
17 extreme case, you can write all your time-critical code in C, and then
18 just glue it together with Haskell!
20 Executive summary of our extensions:
24 <tag>Unboxed types and primitive operations:</tag>
26 You can get right down to the raw machine types and operations;
27 included in this are ``primitive arrays'' (direct access to Big Wads
28 of Bytes). Please see Section <ref name="Unboxed types"
29 id="glasgow-unboxed"> and following.
31 <tag>Multi-parameter type classes:</tag>
33 GHC's type system supports extended type classes with multiple
34 parameters. Please see Section <ref name="Mult-parameter type
35 classes" id="multi-param-type-classes">.
37 <tag>Local universal quantification:</tag>
39 GHC's type system supports explicit unversal quantification in
40 constructor fields and function arguments. This is useful for things
41 like defining @runST@ from the state-thread world. See Section <ref
42 name="Local universal quantification" id="universal-quantification">.
44 <tag>Extistentially quantification in data types:</tag>
46 Some or all of the type variables in a datatype declaration may be
47 <em>existentially quantified</em>. More details in Section <ref
48 name="Existential Quantification" id="existential-quantification">.
50 <tag>Scoped type variables:</tag>
52 Scoped type variables enable the programmer to supply type signatures
53 for some nested declarations, where this would not be legal in Haskell
54 98. Details in Section <ref name="Scoped Type Variables"
55 id="scoped-type-variables">.
57 <tag>Calling out to C:</tag>
59 Just what it sounds like. We provide <em>lots</em> of rope that you
60 can dangle around your neck. Please see Section <ref name="Calling~C
61 directly from Haskell" id="glasgow-ccalls">.
65 Pragmas are special instructions to the compiler placed in the source
66 file. The pragmas GHC supports are described in Section <ref
67 name="Pragmas" id="pragmas">.
71 Before you get too carried away working at the lowest level (e.g.,
72 sloshing @MutableByteArray#@s around your program), you may wish to
73 check if there are system libraries that provide a ``Haskellised
74 veneer'' over the features you want. See Section <ref name="GHC
75 Prelude and libraries" id="ghc-prelude">.
77 %************************************************************************
80 <label id="glasgow-unboxed">
82 <nidx>Unboxed types (Glasgow extension)</nidx>
84 %************************************************************************
86 These types correspond to the ``raw machine'' types you would use in
87 C: @Int#@ (long int), @Double#@ (double), @Addr#@ (void *), etc. The
88 <em>primitive operations</em> (PrimOps) on these types are what you
89 might expect; e.g., @(+#)@ is addition on @Int#@s, and is the
90 machine-addition that we all know and love---usually one instruction.
92 There are some restrictions on the use of unboxed types, the main one
93 being that you can't pass an unboxed value to a polymorphic function
94 or store one in a polymorphic data type. This rules out things like
95 @[Int#]@ (ie. lists of unboxed integers). The reason for this
96 restriction is that polymorphic arguments and constructor fields are
97 assumed to be pointers: if an unboxed integer is stored in one of
98 these, the garbage collector would attempt to follow it, leading to
99 unpredictable space leaks. Or a @seq@ operation on the polymorphic
100 component may attempt to dereference the pointer, with disastrous
101 results. Even worse, the unboxed value might be larger than a pointer
102 (@Double#@ for instance).
104 Nevertheless, A numerically-intensive program using unboxed types can
105 go a <em>lot</em> faster than its ``standard'' counterpart---we saw a
106 threefold speedup on one example.
108 Please see Section <ref name="The module PrelGHC: really primitive
109 stuff" id="ghc-libs-ghc"> for the details of unboxed types and the
112 %************************************************************************
114 <sect1>Primitive state-transformer monad
115 <label id="glasgow-ST-monad">
117 <nidx>state transformers (Glasgow extensions)</nidx>
118 <nidx>ST monad (Glasgow extension)</nidx>
120 %************************************************************************
122 This monad underlies our implementation of arrays, mutable and
123 immutable, and our implementation of I/O, including ``C calls''.
125 The @ST@ library, which provides access to the @ST@ monad, is a
126 GHC/Hugs extension library and is described in the separate <htmlurl
127 name="GHC/Hugs Extension Libraries" url="libs.html"> document.
129 %************************************************************************
131 <sect1>Primitive arrays, mutable and otherwise
132 <label id="glasgow-prim-arrays">
134 <nidx>primitive arrays (Glasgow extension)</nidx>
135 <nidx>arrays, primitive (Glasgow extension)</nidx>
137 %************************************************************************
139 GHC knows about quite a few flavours of Large Swathes of Bytes.
141 First, GHC distinguishes between primitive arrays of (boxed) Haskell
142 objects (type @Array# obj@) and primitive arrays of bytes (type
145 Second, it distinguishes between...
147 <tag>Immutable:</tag>
148 Arrays that do not change (as with ``standard'' Haskell arrays); you
149 can only read from them. Obviously, they do not need the care and
150 attention of the state-transformer monad.
153 Arrays that may be changed or ``mutated.'' All the operations on them
154 live within the state-transformer monad and the updates happen
157 <tag>``Static'' (in C land):</tag>
158 A C routine may pass an @Addr#@ pointer back into Haskell land. There
159 are then primitive operations with which you may merrily grab values
160 over in C land, by indexing off the ``static'' pointer.
162 <tag>``Stable'' pointers:</tag>
163 If, for some reason, you wish to hand a Haskell pointer (i.e.,
164 <em>not</em> an unboxed value) to a C routine, you first make the
165 pointer ``stable,'' so that the garbage collector won't forget that it
166 exists. That is, GHC provides a safe way to pass Haskell pointers to
169 Please see Section <ref name="Subverting automatic unboxing with
170 ``stable pointers''" id="glasgow-stablePtrs"> for more details.
172 <tag>``Foreign objects'':</tag>
173 A ``foreign object'' is a safe way to pass an external object (a
174 C-allocated pointer, say) to Haskell and have Haskell do the Right
175 Thing when it no longer references the object. So, for example, C
176 could pass a large bitmap over to Haskell and say ``please free this
177 memory when you're done with it.''
179 Please see Section <ref name="Pointing outside the Haskell heap"
180 id="glasgow-foreignObjs"> for more details.
184 The libraries section gives more details on all these ``primitive
185 array'' types and the operations on them, Section <ref name="The GHC
186 Prelude and Libraries" id="ghc-prelude">. Some of these extensions
187 are also supported by Hugs, and the supporting libraries are described
188 in the <htmlurl name="GHC/Hugs Extension Libraries" url="libs.html">
191 %************************************************************************
193 <sect1>Calling~C directly from Haskell
194 <label id="glasgow-ccalls">
196 <nidx>C calls (Glasgow extension)</nidx>
197 <nidx>_ccall_ (Glasgow extension)</nidx>
198 <nidx>_casm_ (Glasgow extension)</nidx>
200 %************************************************************************
202 GOOD ADVICE: Because this stuff is not Entirely Stable as far as names
203 and things go, you would be well-advised to keep your C-callery
204 corraled in a few modules, rather than sprinkled all over your code.
205 It will then be quite easy to update later on.
207 %************************************************************************
209 <sect2>@_ccall_@ and @_casm_@: an introduction
210 <label id="ccall-intro">
213 %************************************************************************
215 The simplest way to use a simple C function
218 double fooC( FILE *in, char c, int i, double d, unsigned int u )
221 is to provide a Haskell wrapper:
224 fooH :: Char -> Int -> Double -> Word -> IO Double
225 fooH c i d w = _ccall_ fooC (``stdin''::Addr) c i d w
228 The function @fooH@ will unbox all of its arguments, call the C
229 function @fooC@ and box the corresponding arguments.
231 One of the annoyances about @_ccall_@s is when the C types don't quite
232 match the Haskell compiler's ideas. For this, the @_casm_@ variant
233 may be just the ticket (NB: <em>no chance</em> of such code going
234 through a native-code generator):
241 = _casm_ ``%r = getenv((char *) %0);'' name >>= \ litstring ->
243 if (litstring == nullAddr) then
244 Left ("Fail:oldGetEnv:"++name)
246 Right (unpackCString litstring)
250 The first literal-literal argument to a @_casm_@ is like a @printf@
251 format: @%r@ is replaced with the ``result,'' @%0@--@%n-1@ are
252 replaced with the 1st--nth arguments. As you can see above, it is an
253 easy way to do simple C~casting. Everything said about @_ccall_@ goes
254 for @_casm_@ as well.
256 The use of @_casm_@ in your code does pose a problem to the compiler
257 when it comes to generating an interface file for a freshly compiled
258 module. Included in an interface file is the unfolding (if any) of a
259 declaration. However, if a declaration's unfolding happens to contain
260 a @_casm_@, its unfolding will <em/not/ be emitted into the interface
261 file even if it qualifies by all the other criteria. The reason why
262 the compiler prevents this from happening is that unfolding @_casm_@s
263 into an interface file unduly constrains how code that import your
264 module have to be compiled. If an imported declaration is unfolded and
265 it contains a @_casm_@, you now have to be using a compiler backend
266 capable of dealing with it (i.e., the C compiler backend). If you are
267 using the C compiler backend, the unfolded @_casm_@ may still cause you
268 problems since the C code snippet it contains may mention CPP symbols
269 that were in scope when compiling the original module are not when
270 compiling the importing module.
272 If you're willing to put up with the drawbacks of doing cross-module
273 inlining of C code (GHC - A Better C Compiler :-), the option
274 @-funfold-casms-in-hi-file@ will turn off the default behaviour.
275 <nidx>-funfold-casms-in-hi-file option</nidx>
277 %************************************************************************
279 <sect2>Literal-literals
280 <label id="glasgow-literal-literals">
282 <nidx>Literal-literals</nidx>
284 %************************************************************************
286 The literal-literal argument to @_casm_@ can be made use of separately
287 from the @_casm_@ construct itself. Indeed, we've already used it:
290 fooH :: Char -> Int -> Double -> Word -> IO Double
291 fooH c i d w = _ccall_ fooC (``stdin''::Addr) c i d w
294 The first argument that's passed to @fooC@ is given as a literal-literal,
295 that is, a literal chunk of C code that will be inserted into the generated
296 @.hc@ code at the right place.
298 A literal-literal is restricted to having a type that's an instance of
299 the @CCallable@ class, see <ref name="CCallable" id="ccall-gotchas">
300 for more information.
302 Notice that literal-literals are by their very nature unfriendly to
303 native code generators, so exercise judgement about whether or not to
304 make use of them in your code.
306 %************************************************************************
308 <sect2>Using function headers
309 <label id="glasgow-foreign-headers">
311 <nidx>C calls, function headers</nidx>
313 %************************************************************************
315 When generating C (using the @-fvia-C@ directive), one can assist the
316 C compiler in detecting type errors by using the @-#include@ directive
317 to provide @.h@ files containing function headers.
322 typedef unsigned long *StgForeignObj;
325 void initialiseEFS (StgInt size);
326 StgInt terminateEFS (void);
327 StgForeignObj emptyEFS(void);
328 StgForeignObj updateEFS (StgForeignObj a, StgInt i, StgInt x);
329 StgInt lookupEFS (StgForeignObj a, StgInt i);
332 You can find appropriate definitions for @StgInt@, @StgForeignObj@,
333 etc using @gcc@ on your architecture by consulting
334 @ghc/includes/StgTypes.h@. The following table summarises the
335 relationship between Haskell types and C types.
338 <bf>C type name</bf> | <bf>Haskell Type</bf> @@
340 @StgChar@ | @Char#@ @@
342 @StgWord@ | @Word#@ @@
343 @StgAddr@ | @Addr#@ @@
344 @StgFloat@ | @Float#@ @@
345 @StgDouble@ | @Double#@ @@
347 @StgArray@ | @Array#@ @@
348 @StgByteArray@ | @ByteArray#@ @@
349 @StgArray@ | @MutableArray#@ @@
350 @StgByteArray@ | @MutableByteArray#@ @@
352 @StgStablePtr@ | @StablePtr#@ @@
353 @StgForeignObj@ | @ForeignObj#@
356 Note that this approach is only <em>essential</em> for returning
357 @float@s (or if @sizeof(int) != sizeof(int *)@ on your
358 architecture) but is a Good Thing for anyone who cares about writing
359 solid code. You're crazy not to do it.
361 %************************************************************************
363 <sect2>Subverting automatic unboxing with ``stable pointers''
364 <label id="glasgow-stablePtrs">
366 <nidx>stable pointers (Glasgow extension)</nidx>
368 %************************************************************************
370 The arguments of a @_ccall_@ are automatically unboxed before the
371 call. There are two reasons why this is usually the Right Thing to
376 C is a strict language: it would be excessively tedious to pass
377 unevaluated arguments and require the C programmer to force their
378 evaluation before using them.
380 <item> Boxed values are stored on the Haskell heap and may be moved
381 within the heap if a garbage collection occurs---that is, pointers
382 to boxed objects are not <em>stable</em>.
385 It is possible to subvert the unboxing process by creating a ``stable
386 pointer'' to a value and passing the stable pointer instead. For
387 example, to pass/return an integer lazily to C functions @storeC@ and
388 @fetchC@, one might write:
391 storeH :: Int -> IO ()
392 storeH x = makeStablePtr x >>= \ stable_x ->
393 _ccall_ storeC stable_x
396 fetchH x = _ccall_ fetchC >>= \ stable_x ->
397 deRefStablePtr stable_x >>= \ x ->
398 freeStablePtr stable_x >>
402 The garbage collector will refrain from throwing a stable pointer away
403 until you explicitly call one of the following from C or Haskell.
406 void freeStablePointer( StgStablePtr stablePtrToToss )
407 freeStablePtr :: StablePtr a -> IO ()
410 As with the use of @free@ in C programs, GREAT CARE SHOULD BE
411 EXERCISED to ensure these functions are called at the right time: too
412 early and you get dangling references (and, if you're lucky, an error
413 message from the runtime system); too late and you get space leaks.
415 And to force evaluation of the argument within @fooC@, one would
416 call one of the following C functions (according to type of argument).
419 void performIO ( StgStablePtr stableIndex /* StablePtr s (IO ()) */ );
420 StgInt enterInt ( StgStablePtr stableIndex /* StablePtr s Int */ );
421 StgFloat enterFloat ( StgStablePtr stableIndex /* StablePtr s Float */ );
424 <nidx>performIO</nidx>
425 <nidx>enterInt</nidx>
426 <nidx>enterFloat</nidx>
428 Note Bene: @_ccall_GC_@<nidx>_ccall_GC_</nidx> must be used if any of
429 these functions are used.
431 %************************************************************************
433 <sect2>Foreign objects: pointing outside the Haskell heap
434 <label id="glasgow-foreignObjs">
436 <nidx>foreign objects (Glasgow extension)</nidx>
438 %************************************************************************
440 There are two types that @ghc@ programs can use to reference
441 (heap-allocated) objects outside the Haskell world: @Addr@ and
444 If you use @Addr@, it is up to you to the programmer to arrange
445 allocation and deallocation of the objects.
447 If you use @ForeignObj@, @ghc@'s garbage collector will call upon the
448 user-supplied <em>finaliser</em> function to free the object when the
449 Haskell world no longer can access the object. (An object is
450 associated with a finaliser function when the abstract
451 Haskell type @ForeignObj@ is created). The finaliser function is
452 expressed in C, and is passed as argument the object:
455 void foreignFinaliser ( StgForeignObj fo )
458 when the Haskell world can no longer access the object. Since
459 @ForeignObj@s only get released when a garbage collection occurs, we
460 provide ways of triggering a garbage collection from within C and from
464 void GarbageCollect()
468 More information on the programmers' interface to @ForeignObj@ can be
469 found in the library documentation.
471 %************************************************************************
473 <sect2>Avoiding monads
474 <label id="glasgow-avoiding-monads">
476 <nidx>C calls to `pure C'</nidx>
477 <nidx>unsafePerformIO</nidx>
479 %************************************************************************
481 The @_ccall_@ construct is part of the @IO@ monad because 9 out of 10
482 uses will be to call imperative functions with side effects such as
483 @printf@. Use of the monad ensures that these operations happen in a
484 predictable order in spite of laziness and compiler optimisations.
486 To avoid having to be in the monad to call a C function, it is
487 possible to use @unsafePerformIO@, which is available from the
488 @IOExts@ module. There are three situations where one might like to
489 call a C function from outside the IO world:
493 Calling a function with no side-effects:
495 atan2d :: Double -> Double -> Double
496 atan2d y x = unsafePerformIO (_ccall_ atan2d y x)
498 sincosd :: Double -> (Double, Double)
499 sincosd x = unsafePerformIO $ do
500 da <- newDoubleArray (0, 1)
501 _casm_ ``sincosd( %0, &((double *)%1[0]), &((double *)%1[1]) );'' x da
502 s <- readDoubleArray da 0
503 c <- readDoubleArray da 1
507 <item> Calling a set of functions which have side-effects but which can
508 be used in a purely functional manner.
510 For example, an imperative implementation of a purely functional
511 lookup-table might be accessed using the following functions.
515 update :: EFS x -> Int -> x -> EFS x
516 lookup :: EFS a -> Int -> a
518 empty = unsafePerformIO (_ccall_ emptyEFS)
520 update a i x = unsafePerformIO $
521 makeStablePtr x >>= \ stable_x ->
522 _ccall_ updateEFS a i stable_x
524 lookup a i = unsafePerformIO $
525 _ccall_ lookupEFS a i >>= \ stable_x ->
526 deRefStablePtr stable_x
529 You will almost always want to use @ForeignObj@s with this.
531 <item> Calling a side-effecting function even though the results will
532 be unpredictable. For example the @trace@ function is defined by:
535 trace :: String -> a -> a
538 ((_ccall_ PreTraceHook sTDERR{-msg-}):: IO ()) >>
539 fputs sTDERR string >>
540 ((_ccall_ PostTraceHook sTDERR{-msg-}):: IO ()) >>
543 sTDERR = (``stderr'' :: Addr)
546 (This kind of use is not highly recommended --- it is only really
547 useful in debugging code.)
550 %************************************************************************
552 <sect2>C-calling ``gotchas'' checklist
553 <label id="ccall-gotchas">
555 <nidx>C call dangers</nidx>
556 <nidx>CCallable</nidx>
557 <nidx>CReturnable</nidx>
559 %************************************************************************
561 And some advice, too.
564 <item> For modules that use @_ccall_@s, etc., compile with
565 @-fvia-C@.<nidx>-fvia-C option</nidx> You don't have to, but you should.
567 Also, use the @-#include "prototypes.h"@ flag (hack) to inform the C
568 compiler of the fully-prototyped types of all the C functions you
569 call. (Section <ref name="Using function headers"
570 id="glasgow-foreign-headers"> says more about this...)
572 This scheme is the <em>only</em> way that you will get <em>any</em>
573 typechecking of your @_ccall_@s. (It shouldn't be that way, but...).
574 GHC will pass the flag @-Wimplicit@ to gcc so that you'll get warnings
575 if any @_ccall_@ed functions have no prototypes.
578 Try to avoid @_ccall_@s to C~functions that take @float@
579 arguments or return @float@ results. Reason: if you do, you will
580 become entangled in (ANSI?) C's rules for when arguments/results are
581 promoted to @doubles@. It's a nightmare and just not worth it.
582 Use @doubles@ if possible.
584 If you do use @floats@, check and re-check that the right thing is
585 happening. Perhaps compile with @-keep-hc-file-too@ and look at
586 the intermediate C (@.hc@ file).
588 <item> The compiler uses two non-standard type-classes when
589 type-checking the arguments and results of @_ccall_@: the arguments
590 (respectively result) of @_ccall_@ must be instances of the class
591 @CCallable@ (respectively @CReturnable@). Both classes may be
592 imported from the module @CCall@, but this should only be
593 necessary if you want to define a new instance. (Neither class
594 defines any methods --- their only function is to keep the
597 The type checker must be able to figure out just which of the
598 C-callable/returnable types is being used. If it can't, you have to
599 add type signatures. For example,
605 is not good enough, because the compiler can't work out what type @x@
606 is, nor what type the @_ccall_@ returns. You have to write, say:
609 f :: Int -> IO Double
613 This table summarises the standard instances of these classes.
615 % ToDo: check this table against implementation!
618 <bf>Type</bf> |<bf>CCallable</bf>|<bf>CReturnable</bf> | <bf>Which is probably...</bf> @@
620 @Char@ | Yes | Yes | @unsigned char@ @@
621 @Int@ | Yes | Yes | @long int@ @@
622 @Word@ | Yes | Yes | @unsigned long int@ @@
623 @Addr@ | Yes | Yes | @void *@ @@
624 @Float@ | Yes | Yes | @float@ @@
625 @Double@ | Yes | Yes | @double@ @@
626 @()@ | No | Yes | @void@ @@
627 @[Char]@ | Yes | No | @char *@ (null-terminated) @@
629 @Array@ | Yes | No | @unsigned long *@ @@
630 @ByteArray@ | Yes | No | @unsigned long *@ @@
631 @MutableArray@ | Yes | No | @unsigned long *@ @@
632 @MutableByteArray@ | Yes | No | @unsigned long *@ @@
634 @State@ | Yes | Yes | nothing!@@
636 @StablePtr@ | Yes | Yes | @unsigned long *@ @@
637 @ForeignObjs@ | Yes | Yes | see later @@
640 Actually, the @Word@ type is defined as being the same size as a
641 pointer on the target architecture, which is <em>probably</em>
644 The brave and careful programmer can add their own instances of these
645 classes for the following types:
649 A <em>boxed-primitive</em> type may be made an instance of both
650 @CCallable@ and @CReturnable@.
652 A boxed primitive type is any data type with a
653 single unary constructor with a single primitive argument. For
654 example, the following are all boxed primitive types:
659 data XDisplay = XDisplay Addr#
660 data EFS a = EFS# ForeignObj#
664 instance CCallable (EFS a)
665 instance CReturnable (EFS a)
668 <item> Any datatype with a single nullary constructor may be made an
669 instance of @CReturnable@. For example:
673 instance CReturnable MyVoid
676 <item> As at version 2.09, @String@ (i.e., @[Char]@) is still
677 not a @CReturnable@ type.
679 Also, the now-builtin type @PackedString@ is neither
680 @CCallable@ nor @CReturnable@. (But there are functions in
681 the PackedString interface to let you get at the necessary bits...)
684 <item> The code-generator will complain if you attempt to use @%r@ in
685 a @_casm_@ whose result type is @IO ()@; or if you don't use @%r@
686 <em>precisely</em> once for any other result type. These messages are
687 supposed to be helpful and catch bugs---please tell us if they wreck
690 <item> If you call out to C code which may trigger the Haskell garbage
691 collector or create new threads (examples of this later...), then you
692 must use the @_ccall_GC_@<nidx>_ccall_GC_ primitive</nidx> or
693 @_casm_GC_@<nidx>_casm_GC_ primitive</nidx> variant of C-calls. (This
694 does not work with the native code generator - use @\fvia-C@.) This
695 stuff is hairy with a capital H! </itemize>
697 <sect1> Multi-parameter type classes
698 <label id="multi-param-type-classes">
701 This section documents GHC's implementation of multi-paramter type
702 classes. There's lots of background in the paper <url name="Type
703 classes: exploring the design space"
704 url="http://www.dcs.gla.ac.uk/~simonpj/multi.ps.gz"> (Simon Peyton
705 Jones, Mark Jones, Erik Meijer).
707 I'd like to thank people who reported shorcomings in the GHC 3.02
708 implementation. Our default decisions were all conservative ones, and
709 the experience of these heroic pioneers has given useful concrete
710 examples to support several generalisations. (These appear below as
711 design choices not implemented in 3.02.)
713 I've discussed these notes with Mark Jones, and I believe that Hugs
714 will migrate towards the same design choices as I outline here.
715 Thanks to him, and to many others who have offered very useful
721 There are the following restrictions on the form of a qualified
725 forall tv1..tvn (c1, ...,cn) => type
728 (Here, I write the "foralls" explicitly, although the Haskell source
729 language omits them; in Haskell 1.4, all the free type variables of an
730 explicit source-language type signature are universally quantified,
731 except for the class type variables in a class declaration. However,
732 in GHC, you can give the foralls if you want. See Section <ref
733 name="Explicit universal quantification"
734 id="universal-quantification">).
738 <item> <bf>Each universally quantified type variable
739 @tvi@ must be mentioned (i.e. appear free) in @type@</bf>.
741 The reason for this is that a value with a type that does not obey
742 this restriction could not be used without introducing
743 ambiguity. Here, for example, is an illegal type:
746 forall a. Eq a => Int
749 When a value with this type was used, the constraint <tt>Eq tv</tt>
750 would be introduced where <tt>tv</tt> is a fresh type variable, and
751 (in the dictionary-translation implementation) the value would be
752 applied to a dictionary for <tt>Eq tv</tt>. The difficulty is that we
753 can never know which instance of <tt>Eq</tt> to use because we never
754 get any more information about <tt>tv</tt>.
756 <item> <bf>Every constraint @ci@ must mention at least one of the
757 universally quantified type variables @tvi@</bf>.
759 For example, this type is OK because <tt>C a b</tt> mentions the
760 universally quantified type variable <tt>b</tt>:
763 forall a. C a b => burble
766 The next type is illegal because the constraint <tt>Eq b</tt> does not
770 forall a. Eq b => burble
773 The reason for this restriction is milder than the other one. The
774 excluded types are never useful or necessary (because the offending
775 context doesn't need to be witnessed at this point; it can be floated
776 out). Furthermore, floating them out increases sharing. Lastly,
777 excluding them is a conservative choice; it leaves a patch of
778 territory free in case we need it later.
782 These restrictions apply to all types, whether declared in a type signature
785 Unlike Haskell 1.4, constraints in types do <bf>not</bf> have to be of
786 the form <em>(class type-variables)</em>. Thus, these type signatures
790 f :: Eq (m a) => [m a] -> [m a]
794 This choice recovers principal types, a property that Haskell 1.4 does not have.
796 <sect2>Class declarations
801 <item> <bf>Multi-parameter type classes are permitted</bf>. For example:
804 class Collection c a where
805 union :: c a -> c a -> c a
810 <item> <bf>The class hierarchy must be acyclic</bf>. However, the definition
811 of "acyclic" involves only the superclass relationships. For example,
816 op :: D b => a -> b -> b
819 class C a => D a where { ... }
822 Here, <tt>C</tt> is a superclass of <tt>D</tt>, but it's OK for a
823 class operation <tt>op</tt> of <tt>C</tt> to mention <tt>D</tt>. (It
824 would not be OK for <tt>D</tt> to be a superclass of <tt>C</tt>.)
826 <item> <bf>There are no restrictions on the context in a class declaration
827 (which introduces superclasses), except that the class hierarchy must
828 be acyclic</bf>. So these class declarations are OK:
831 class Functor (m k) => FiniteMap m k where
834 class (Monad m, Monad (t m)) => Transform t m where
835 lift :: m a -> (t m) a
838 <item> <bf>In the signature of a class operation, every constraint
839 must mention at least one type variable that is not a class type
845 class Collection c a where
846 mapC :: Collection c b => (a->b) -> c a -> c b
849 is OK because the constraint <tt>(Collection a b)</tt> mentions
850 <tt>b</tt>, even though it also mentions the class variable
851 <tt>a</tt>. On the other hand:
855 op :: Eq a => (a,b) -> (a,b)
858 is not OK because the constraint <tt>(Eq a)</tt> mentions on the class
859 type variable <tt>a</tt>, but not <tt>b</tt>. However, any such
860 example is easily fixed by moving the offending context up to the
864 class Eq a => C a where
868 A yet more relaxed rule would allow the context of a class-op signature
869 to mention only class type variables. However, that conflicts with
870 Rule 1(b) for types above.
872 <item> <bf>The type of each class operation must mention <em/all/ of
873 the class type variables</bf>. For example:
878 insert :: s -> a -> s
881 is not OK, because the type of <tt>empty</tt> doesn't mention
882 <tt>a</tt>. This rule is a consequence of Rule 1(a), above, for
883 types, and has the same motivation.
885 Sometimes, offending class declarations exhibit misunderstandings. For
886 example, <tt>Coll</tt> might be rewritten
891 insert :: s a -> a -> s a
894 which makes the connection between the type of a collection of
895 <tt>a</tt>'s (namely <tt>(s a)</tt>) and the element type <tt>a</tt>.
896 Occasionally this really doesn't work, in which case you can split the
903 class CollE s => Coll s a where
904 insert :: s -> a -> s
909 <sect2>Instance declarations
914 <item> <bf>Instance declarations may not overlap</bf>. The two instance
918 instance context1 => C type1 where ...
919 instance context2 => C type2 where ...
922 "overlap" if @type1@ and @type2@ unify
924 However, if you give the command line option
925 @-fallow-overlapping-instances@<nidx>-fallow-overlapping-instances
926 option</nidx> then two overlapping instance declarations are permitted
930 <item> EITHER @type1@ and @type2@ do not unify
931 <item> OR @type2@ is a substitution instance of @type1@
932 (but not identical to @type1@)
936 Notice that these rules
939 <item> make it clear which instance decl to use
940 (pick the most specific one that matches)
942 <item> do not mention the contexts @context1@, @context2@
943 Reason: you can pick which instance decl
944 "matches" based on the type.
947 Regrettably, GHC doesn't guarantee to detect overlapping instance
948 declarations if they appear in different modules. GHC can "see" the
949 instance declarations in the transitive closure of all the modules
950 imported by the one being compiled, so it can "see" all instance decls
951 when it is compiling <tt>Main</tt>. However, it currently chooses not
952 to look at ones that can't possibly be of use in the module currently
953 being compiled, in the interests of efficiency. (Perhaps we should
954 change that decision, at least for <tt>Main</tt>.)
956 <item> <bf>There are no restrictions on the type in an instance
957 <em/head/, except that at least one must not be a type variable</bf>.
958 The instance "head" is the bit after the "=>" in an instance decl. For
959 example, these are OK:
962 instance C Int a where ...
964 instance D (Int, Int) where ...
966 instance E [[a]] where ...
969 Note that instance heads <bf>may</bf> contain repeated type variables.
970 For example, this is OK:
973 instance Stateful (ST s) (MutVar s) where ...
976 The "at least one not a type variable" restriction is to ensure that
977 context reduction terminates: each reduction step removes one type
978 constructor. For example, the following would make the type checker
979 loop if it wasn't excluded:
982 instance C a => C a where ...
985 There are two situations in which the rule is a bit of a pain. First,
986 if one allows overlapping instance declarations then it's quite
987 convenient to have a "default instance" declaration that applies if
988 something more specific does not:
995 Second, sometimes you might want to use the following to get the
996 effect of a "class synonym":
999 class (C1 a, C2 a, C3 a) => C a where { }
1001 instance (C1 a, C2 a, C3 a) => C a where { }
1004 This allows you to write shorter signatures:
1013 f :: (C1 a, C2 a, C3 a) => ...
1016 I'm on the lookout for a simple rule that preserves decidability while
1017 allowing these idioms. The experimental flag
1018 @-fallow-undecidable-instances@<nidx>-fallow-undecidable-instances
1019 option</nidx> lifts this restriction, allowing all the types in an
1020 instance head to be type variables.
1022 <item> <bf>Unlike Haskell 1.4, instance heads may use type
1023 synonyms</bf>. As always, using a type synonym is just shorthand for
1024 writing the RHS of the type synonym definition. For example:
1027 type Point = (Int,Int)
1028 instance C Point where ...
1029 instance C [Point] where ...
1032 is legal. However, if you added
1035 instance C (Int,Int) where ...
1038 as well, then the compiler will complain about the overlapping
1039 (actually, identical) instance declarations. As always, type synonyms
1040 must be fully applied. You cannot, for example, write:
1044 instance Monad P where ...
1047 This design decision is independent of all the others, and easily
1048 reversed, but it makes sense to me.
1050 <item><bf>The types in an instance-declaration <em/context/ must all
1051 be type variables</bf>. Thus
1054 instance C a b => Eq (a,b) where ...
1060 instance C Int b => Foo b where ...
1063 is not OK. Again, the intent here is to make sure that context
1064 reduction terminates.
1066 Voluminous correspondence on the Haskell mailing list has convinced me
1067 that it's worth experimenting with a more liberal rule. If you use
1068 the flag <tt>-fallow-undecidable-instances</tt> you can use arbitrary
1069 types in an instance context. Termination is ensured by having a
1070 fixed-depth recursion stack. If you exceed the stack depth you get a
1071 sort of backtrace, and the opportunity to increase the stack depth
1072 with <tt>-fcontext-stack</tt><em/N/.
1076 % -----------------------------------------------------------------------------
1077 <sect1>Explicit universal quantification
1078 <label id="universal-quantification">
1081 GHC now allows you to write explicitly quantified types. GHC's
1082 syntax for this now agrees with Hugs's, namely:
1085 forall a b. (Ord a, Eq b) => a -> b -> a
1088 The context is, of course, optional. You can't use <tt>forall</tt> as
1089 a type variable any more!
1091 Haskell type signatures are implicitly quantified. The <tt>forall</tt>
1092 allows us to say exactly what this means. For example:
1101 g :: forall b. (b -> b)
1104 The two are treated identically.
1106 <sect2>Universally-quantified data type fields
1110 In a <tt>data</tt> or <tt>newtype</tt> declaration one can quantify
1111 the types of the constructor arguments. Here are several examples:
1114 data T a = T1 (forall b. b -> b -> b) a
1116 data MonadT m = MkMonad { return :: forall a. a -> m a,
1117 bind :: forall a b. m a -> (a -> m b) -> m b
1120 newtype Swizzle = MkSwizzle (Ord a => [a] -> [a])
1123 The constructors now have so-called <em/rank 2/ polymorphic
1124 types, in which there is a for-all in the argument types.:
1127 T1 :: forall a. (forall b. b -> b -> b) -> a -> T1 a
1128 MkMonad :: forall m. (forall a. a -> m a)
1129 -> (forall a b. m a -> (a -> m b) -> m b)
1131 MkSwizzle :: (Ord a => [a] -> [a]) -> Swizzle
1134 Notice that you don't need to use a <tt>forall</tt> if there's an
1135 explicit context. For example in the first argument of the
1136 constructor <tt>MkSwizzle</tt>, an implicit "<tt>forall a.</tt>" is
1137 prefixed to the argument type. The implicit <tt>forall</tt>
1138 quantifies all type variables that are not already in scope, and are
1139 mentioned in the type quantified over.
1141 As for type signatures, implicit quantification happens for non-overloaded
1142 types too. So if you write this:
1144 data T a = MkT (Either a b) (b -> b)
1146 it's just as if you had written this:
1148 data T a = MkT (forall b. Either a b) (forall b. b -> b)
1150 That is, since the type variable <tt>b</tt> isn't in scope, it's
1151 implicitly universally quantified. (Arguably, it would be better
1152 to <em>require</em> explicit quantification on constructor arguments
1153 where that is what is wanted. Feedback welcomed.)
1155 <sect2> Construction
1158 You construct values of types <tt>T1, MonadT, Swizzle</tt> by applying
1159 the constructor to suitable values, just as usual. For example,
1162 (T1 (\xy->x) 3) :: T Int
1164 (MkSwizzle sort) :: Swizzle
1165 (MkSwizzle reverse) :: Swizzle
1172 MkMonad r b) :: MonadT Maybe
1175 The type of the argument can, as usual, be more general than the type
1176 required, as <tt>(MkSwizzle reverse)</tt> shows. (<tt>reverse</tt>
1177 does not need the <tt>Ord</tt> constraint.)
1179 <sect2>Pattern matching
1182 When you use pattern matching, the bound variables may now have
1183 polymorphic types. For example:
1186 f :: T a -> a -> (a, Char)
1187 f (T1 f k) x = (f k x, f 'c' 'd')
1189 g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b]
1190 g (MkSwizzle s) xs f = s (map f (s xs))
1192 h :: MonadT m -> [m a] -> m [a]
1193 h m [] = return m []
1194 h m (x:xs) = bind m x $ \y ->
1195 bind m (h m xs) $ \ys ->
1199 In the function <tt>h</tt> we use the record selectors <tt>return</tt>
1200 and <tt>bind</tt> to extract the polymorphic bind and return functions
1201 from the <tt>MonadT</tt> data structure, rather than using pattern
1204 You cannot pattern-match against an argument that is polymorphic.
1207 newtype TIM s a = TIM (ST s (Maybe a))
1209 runTIM :: (forall s. TIM s a) -> Maybe a
1210 runTIM (TIM m) = runST m
1213 Here the pattern-match fails, because you can't pattern-match against
1214 an argument of type <tt>(forall s. TIM s a)</tt>. Instead you
1215 must bind the variable and pattern match in the right hand side:
1217 runTIM :: (forall s. TIM s a) -> Maybe a
1218 runTIM tm = case tm of { TIM m -> runST m }
1220 The <tt>tm</tt> on the right hand side is (invisibly) instantiated, like
1221 any polymorphic value at its occurrence site, and now you can pattern-match
1224 <sect2>The partial-application restriction
1227 There is really only one way in which data structures with polymorphic
1228 components might surprise you: you must not partially apply them.
1229 For example, this is illegal:
1232 map MkSwizzle [sort, reverse]
1235 The restriction is this: <em>every subexpression of the program must
1236 have a type that has no for-alls, except that in a function
1237 application (f e1 ... en) the partial applications are not subject to
1238 this rule</em>. The restriction makes type inference feasible.
1240 In the illegal example, the sub-expression <tt>MkSwizzle</tt> has the
1241 polymorphic type <tt>(Ord b => [b] -> [b]) -> Swizzle</tt> and is not
1242 a sub-expression of an enclosing application. On the other hand, this
1246 map (T1 (\a b -> a)) [1,2,3]
1249 even though it involves a partial application of <tt>T1</tt>, because
1250 the sub-expression <tt>T1 (\a b -> a)</tt> has type <tt>Int -> T
1253 <sect2>Type signatures
1257 Once you have data constructors with universally-quantified fields, or
1258 constants such as <tt>runST</tt> that have rank-2 types, it isn't long
1259 before you discover that you need more! Consider:
1262 mkTs f x y = [T1 f x, T1 f y]
1265 <tt>mkTs</tt> is a fuction that constructs some values of type
1266 <tt>T</tt>, using some pieces passed to it. The trouble is that since
1267 <tt>f</tt> is a function argument, Haskell assumes that it is
1268 monomorphic, so we'll get a type error when applying <tt>T1</tt> to
1269 it. This is a rather silly example, but the problem really bites in
1270 practice. Lots of people trip over the fact that you can't make
1271 "wrappers functions" for <tt>runST</tt> for exactly the same reason.
1272 In short, it is impossible to build abstractions around functions with
1275 The solution is fairly clear. We provide the ability to give a rank-2
1276 type signature for <em>ordinary</em> functions (not only data
1277 constructors), thus:
1280 mkTs :: (forall b. b -> b -> b) -> a -> [T a]
1281 mkTs f x y = [T1 f x, T1 f y]
1284 This type signature tells the compiler to attribute <tt>f</tt> with
1285 the polymorphic type <tt>(forall b. b -> b -> b)</tt> when type
1286 checking the body of <tt>mkTs</tt>, so now the application of
1287 <tt>T1</tt> is fine.
1289 There are two restrictions:
1292 <item> You can only define a rank 2 type, specified by the following
1296 rank2type ::= [forall tyvars .] [context =>] funty
1297 funty ::= ([forall tyvars .] [context =>] ty) -> funty
1299 ty ::= ...current Haskell monotype syntax...
1302 Informally, the universal quantification must all be right at the beginning,
1303 or at the top level of a function argument.
1305 <item> There is a restriction on the definition of a function whose
1306 type signature is a rank-2 type: the polymorphic arguments must be
1307 matched on the left hand side of the "<tt>=</tt>" sign. You can't
1308 define <tt>mkTs</tt> like this:
1311 mkTs :: (forall b. b -> b -> b) -> a -> [T a]
1312 mkTs = \ f x y -> [T1 f x, T1 f y]
1316 The same partial-application rule applies to ordinary functions with
1317 rank-2 types as applied to data constructors.
1321 % -----------------------------------------------------------------------------
1322 <sect1>Existentially quantified data constructors
1323 <label id="existential-quantification">
1326 The idea of using existential quantification in data type declarations
1327 was suggested by Laufer (I believe, thought doubtless someone will
1328 correct me), and implemented in Hope+. It's been in Lennart
1329 Augustsson's <tt>hbc</tt> Haskell compiler for several years, and
1330 proved very useful. Here's the idea. Consider the declaration:
1333 data Foo = forall a. MkFoo a (a -> Bool)
1337 The data type <tt>Foo</tt> has two constructors with types:
1340 MkFoo :: forall a. a -> (a -> Bool) -> Foo
1344 Notice that the type variable <tt>a</tt> in the type of <tt>MkFoo</tt>
1345 does not appear in the data type itself, which is plain <tt>Foo</tt>.
1346 For example, the following expression is fine:
1349 [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
1352 Here, <tt>(MkFoo 3 even)</tt> packages an integer with a function
1353 <tt>even</tt> that maps an integer to <tt>Bool</tt>; and <tt>MkFoo 'c'
1354 isUpper</tt> packages a character with a compatible function. These
1355 two things are each of type <tt>Foo</tt> and can be put in a list.
1357 What can we do with a value of type <tt>Foo</tt>?. In particular,
1358 what happens when we pattern-match on <tt>MkFoo</tt>?
1361 f (MkFoo val fn) = ???
1364 Since all we know about <tt>val</tt> and <tt>fn</tt> is that they
1365 are compatible, the only (useful) thing we can do with them is to
1366 apply <tt>fn</tt> to <tt>val</tt> to get a boolean. For example:
1370 f (MkFoo val fn) = fn val
1373 What this allows us to do is to package heterogenous values
1374 together with a bunch of functions that manipulate them, and then treat
1375 that collection of packages in a uniform manner. You can express
1376 quite a bit of object-oriented-like programming this way.
1378 <sect2>Why existential?
1379 <label id="existential">
1382 What has this to do with <em>existential</em> quantification?
1383 Simply that <tt>MkFoo</tt> has the (nearly) isomorphic type
1386 MkFoo :: (exists a . (a, a -> Bool)) -> Foo
1389 But Haskell programmers can safely think of the ordinary
1390 <em>universally</em> quantified type given above, thereby avoiding
1391 adding a new existential quantification construct.
1396 An easy extension (implemented in <tt>hbc</tt>) is to allow
1397 arbitrary contexts before the constructor. For example:
1400 data Baz = forall a. Eq a => Baz1 a a
1401 | forall b. Show b => Baz2 b (b -> b)
1404 The two constructors have the types you'd expect:
1407 Baz1 :: forall a. Eq a => a -> a -> Baz
1408 Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
1411 But when pattern matching on <tt>Baz1</tt> the matched values can be compared
1412 for equality, and when pattern matching on <tt>Baz2</tt> the first matched
1413 value can be converted to a string (as well as applying the function to it).
1414 So this program is legal:
1418 f (Baz1 p q) | p == q = "Yes"
1420 f (Baz1 v fn) = show (fn v)
1423 Operationally, in a dictionary-passing implementation, the
1424 constructors <tt>Baz1</tt> and <tt>Baz2</tt> must store the
1425 dictionaries for <tt>Eq</tt> and <tt>Show</tt> respectively, and
1426 extract it on pattern matching.
1428 Notice the way that the syntax fits smoothly with that used for
1429 universal quantification earlier.
1434 There are several restrictions on the ways in which existentially-quantified
1435 constructors can be use.
1439 <item> When pattern matching, each pattern match introduces a new,
1440 distinct, type for each existential type variable. These types cannot
1441 be unified with any other type, nor can they escape from the scope of
1442 the pattern match. For example, these fragments are incorrect:
1448 Here, the type bound by <tt>MkFoo</tt> "escapes", because <tt>a</tt>
1449 is the result of <tt>f1</tt>. One way to see why this is wrong is to
1450 ask what type <tt>f1</tt> has:
1453 f1 :: Foo -> a -- Weird!
1456 What is this "<tt>a</tt>" in the result type? Clearly we don't mean
1460 f1 :: forall a. Foo -> a -- Wrong!
1463 The original program is just plain wrong. Here's another sort of error
1466 f2 (Baz1 a b) (Baz1 p q) = a==q
1469 It's ok to say <tt>a==b</tt> or <tt>p==q</tt>, but
1470 <tt>a==q</tt> is wrong because it equates the two distinct types arising
1471 from the two <tt>Baz1</tt> constructors.
1474 <item>You can't pattern-match on an existentially quantified
1475 constructor in a <tt>let</tt> or <tt>where</tt> group of
1476 bindings. So this is illegal:
1479 f3 x = a==b where { Baz1 a b = x }
1482 You can only pattern-match
1483 on an existentially-quantified constructor in a <tt>case</tt> expression or
1484 in the patterns of a function definition.
1486 The reason for this restriction is really an implementation one.
1487 Type-checking binding groups is already a nightmare without
1488 existentials complicating the picture. Also an existential pattern
1489 binding at the top level of a module doesn't make sense, because it's
1490 not clear how to prevent the existentially-quantified type "escaping".
1491 So for now, there's a simple-to-state restriction. We'll see how
1494 <item>You can't use existential quantification for <tt>newtype</tt>
1495 declarations. So this is illegal:
1498 newtype T = forall a. Ord a => MkT a
1501 Reason: a value of type <tt>T</tt> must be represented as a pair
1502 of a dictionary for <tt>Ord t</tt> and a value of type <tt>t</tt>.
1503 That contradicts the idea that <tt>newtype</tt> should have no
1504 concrete representation. You can get just the same efficiency and effect
1505 by using <tt>data</tt> instead of <tt>newtype</tt>. If there is no
1506 overloading involved, then there is more of a case for allowing
1507 an existentially-quantified <tt>newtype</tt>, because the <tt>data</tt>
1508 because the <tt>data</tt> version does carry an implementation cost,
1509 but single-field existentially quantified constructors aren't much
1510 use. So the simple restriction (no existential stuff on <tt>newtype</tt>)
1511 stands, unless there are convincing reasons to change it.
1515 <sect1> <idx/Assertions/
1516 <label id="sec:assertions">
1519 If you want to make use of assertions in your standard Haskell code, you
1520 could define a function like the following:
1523 assert :: Bool -> a -> a
1524 assert False x = error "assertion failed!"
1528 which works, but gives you back a less than useful error message --
1529 an assertion failed, but which and where?
1531 One way out is to define an extended <tt/assert/ function which also
1532 takes a descriptive string to include in the error message and
1533 perhaps combine this with the use of a pre-processor which inserts
1534 the source location where <tt/assert/ was used.
1536 Ghc offers a helping hand here, doing all of this for you. For every
1537 use of <tt/assert/ in the user's source:
1540 kelvinToC :: Double -> Double
1541 kelvinToC k = assert (k >= 0.0) (k+273.15)
1544 Ghc will rewrite this to also include the source location where the
1548 assert pred val ==> assertError "Main.hs|15" pred val
1551 The rewrite is only performed by the compiler when it spots
1552 applications of <tt>Exception.assert</tt>, so you can still define and
1553 use your own versions of <tt/assert/, should you so wish. If not,
1554 import <tt/Exception/ to make use <tt/assert/ in your code.
1556 To have the compiler ignore uses of assert, use the compiler option
1557 @-fignore-asserts@. <nidx>-fignore-asserts option</nidx> That is,
1558 expressions of the form @assert pred e@ will be rewritten to @e@.
1560 Assertion failures can be caught, see the documentation for the
1561 Hugs/GHC Exception library for information of how.
1563 % -----------------------------------------------------------------------------
1564 <sect1>Scoped Type Variables
1565 <label id="scoped-type-variables">
1568 A <em/pattern type signature/ can introduce a <em/scoped type
1569 variable/. For example
1572 f (xs::[a]) = ys ++ ys
1578 The pattern @(xs::[a])@ includes a type signature for @xs@.
1579 This brings the type variable @a@ into scope; it scopes over
1580 all the patterns and right hand sides for this equation for @f@.
1581 In particular, it is in scope at the type signature for @y@.
1583 At ordinary type signatures, such as that for @ys@, any type variables
1584 mentioned in the type signature <em/that are not in scope/ are
1585 implicitly universally quantified. (If there are no type variables in
1586 scope, all type variables mentioned in the signature are universally
1587 quantified, which is just as in Haskell 98.) In this case, since @a@
1588 is in scope, it is not universally quantified, so the type of @ys@ is
1589 the same as that of @xs@. In Haskell 98 it is not possible to declare
1590 a type for @ys@; a major benefit of scoped type variables is that
1591 it becomes possible to do so.
1593 Scoped type variables are implemented in both GHC and Hugs. Where the
1594 implementations differ from the specification below, those differences
1597 So much for the basic idea. Here are the details.
1599 <sect2>Scope and implicit quantification
1603 <item> All the type variables mentioned in the patterns for a single
1604 function definition equation, that are not already in scope,
1605 are brought into scope by the patterns. We describe this set as
1606 the <em/type variables bound by the equation/.
1608 <item> The type variables thus brought into scope may be mentioned
1609 in ordinary type signatures or pattern type signatures anywhere within
1612 <item> In ordinary type signatures, any type variable mentioned in the
1613 signature that is in scope is <em/not/ universally quantified.
1615 <item> Ordinary type signatures do not bring any new type variables
1616 into scope (except in the type signature itself!). So this is illegal:
1623 It's illegal because @a@ is not in scope in the body of @f@,
1624 so the ordinary signature @x::a@ is equivalent to @x::forall a.a@;
1625 and that is an incorrect typing.
1627 <item> There is no implicit universal quantification on pattern type
1628 signatures, nor may one write an explicit @forall@ type in a pattern
1629 type signature. The pattern type signature is a monotype.
1632 The type variables in the head of a @class@ or @instance@ declaration
1633 scope over the methods defined in the @where@ part. For example:
1645 (Not implemented in Hugs yet, Dec 98).
1652 <item> Pattern type signatures are completely orthogonal to ordinary, separate
1653 type signatures. The two can be used independently or together. There is
1654 no scoping associated with the names of the type variables in a separate type signature.
1658 f (xs::[b]) = reverse xs
1661 <item> The function must be polymorphic in the type variables
1662 bound by all its equations. Operationally, the type variables bound
1663 by one equation must not:
1666 <item> Be unified with a type (such as @Int@, or @[a]@).
1667 <item> Be unified with a type variable free in the environment.
1668 <item> Be unified with each other. (They may unify with the type variables
1669 bound by another equation for the same function, of course.)
1672 For example, the following all fail to type check:
1675 f (x::a) (y::b) = [x,y] -- a unifies with b
1677 g (x::a) = x + 1::Int -- a unifies with Int
1679 h x = let k (y::a) = [x,y] -- a is free in the
1680 in k x -- environment
1682 k (x::a) True = ... -- a unifies with Int
1683 k (x::Int) False = ...
1686 w (x::a) = x -- a unifies with [b]
1689 <item> The pattern-bound type variable may, however, be constrained
1690 by the context of the principal type, thus:
1693 f (x::a) (y::a) = x+y*2
1696 gets the inferred type: @forall a. Num a => a -> a -> a@.
1699 <sect2>Result type signatures
1703 <item> The result type of a function can be given a signature,
1707 f (x::a) :: [a] = [x,x,x]
1710 The final @":: [a]"@ after all the patterns gives a signature to the
1711 result type. Sometimes this is the only way of naming the type variable
1715 f :: Int -> [a] -> [a]
1716 f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
1717 in \xs -> map g (reverse xs `zip` xs)
1722 Result type signatures are not yet implemented in Hugs.
1724 <sect2>Pattern signatures on other constructs
1728 <item> A pattern type signature can be on an arbitrary sub-pattern, not
1732 f ((x,y)::(a,b)) = (y,x) :: (b,a)
1735 <item> Pattern type signatures, including the result part, can be used
1736 in lambda abstractions:
1739 (\ (x::a, y) :: a -> x)
1742 Type variables bound by these patterns must be polymorphic in
1743 the sense defined above.
1747 f1 (x::c) = f1 x -- ok
1748 f2 = \(x::c) -> f2 x -- not ok
1751 Here, @f1@ is OK, but @f2@ is not, because @c@ gets unified
1752 with a type variable free in the environment, in this
1753 case, the type of @f2@, which is in the environment when
1754 the lambda abstraction is checked.
1756 <item> Pattern type signatures, including the result part, can be used
1757 in @case@ expressions:
1760 case e of { (x::a, y) :: a -> x }
1763 The pattern-bound type variables must, as usual,
1764 be polymorphic in the following sense: each case alternative,
1765 considered as a lambda abstraction, must be polymorphic.
1769 case (True,False) of { (x::a, y) -> x }
1772 Even though the context is that of a pair of booleans,
1773 the alternative itself is polymorphic. Of course, it is
1777 case (True,False) of { (x::Bool, y) -> x }
1781 To avoid ambiguity, the type after the ``@::@'' in a result
1782 pattern signature on a lambda or @case@ must be atomic (i.e. a single
1783 token or a parenthesised type of some sort). To see why,
1784 consider how one would parse this:
1790 <item> Pattern type signatures that bind new type variables
1791 may not be used in pattern bindings at all.
1795 f x = let (y, z::a) = x in ...
1798 But these are OK, because they do not bind fresh type variables:
1801 f1 x = let (y, z::Int) = x in ...
1802 f2 (x::(Int,a)) = let (y, z::a) = x in ...
1805 However a single variable is considered a degenerate function binding,
1806 rather than a degerate pattern binding, so this is permitted, even
1807 though it binds a type variable:
1810 f :: (b->b) = \(x::b) -> x
1814 Such degnerate function bindings do not fall under the monomorphism
1818 g :: a -> a -> Bool = \x y. x==y
1821 Here @g@ has type @forall a. Eq a => a -> a -> Bool@, just as if
1822 @g@ had a separate type signature. Lacking a type signature, @g@
1823 would get a monomorphic type.
1829 <item> Pattern type signatures can bind existential type variables.
1833 data T = forall a. MkT [a]
1836 f (MkT [t::a]) = MkT t3
1843 %-----------------------------------------------------------------------------
1845 <label id="pragmas">
1848 GHC supports several pragmas, or instructions to the compiler placed
1849 in the source code. Pragmas don't affect the meaning of the program,
1850 but they might affect the efficiency of the generated code.
1852 <sect2>INLINE pragma
1853 <label id="inline-pragma">
1854 <nidx>INLINE pragma</nidx>
1855 <nidx>pragma, INLINE</nidx>
1858 GHC (with @-O@, as always) tries to inline (or ``unfold'')
1859 functions/values that are ``small enough,'' thus avoiding the call
1860 overhead and possibly exposing other more-wonderful optimisations.
1862 You will probably see these unfoldings (in Core syntax) in your
1865 Normally, if GHC decides a function is ``too expensive'' to inline, it
1866 will not do so, nor will it export that unfolding for other modules to
1869 The sledgehammer you can bring to bear is the
1870 @INLINE@<nidx>INLINE pragma</nidx> pragma, used thusly:
1872 key_function :: Int -> String -> (Bool, Double)
1874 #ifdef __GLASGOW_HASKELL__
1875 {-# INLINE key_function #-}
1878 (You don't need to do the C pre-processor carry-on unless you're going
1879 to stick the code through HBC---it doesn't like @INLINE@ pragmas.)
1881 The major effect of an @INLINE@ pragma is to declare a function's
1882 ``cost'' to be very low. The normal unfolding machinery will then be
1883 very keen to inline it.
1885 An @INLINE@ pragma for a function can be put anywhere its type
1886 signature could be put.
1888 @INLINE@ pragmas are a particularly good idea for the
1889 @then@/@return@ (or @bind@/@unit@) functions in a monad.
1890 For example, in GHC's own @UniqueSupply@ monad code, we have:
1892 #ifdef __GLASGOW_HASKELL__
1893 {-# INLINE thenUs #-}
1894 {-# INLINE returnUs #-}
1898 <sect2>NOINLINE pragma
1899 <label id="noinline-pragma">
1901 <nidx>NOINLINE pragma</nidx>
1902 <nidx>pragma, NOINLINE</nidx>
1904 The @NOINLINE@ pragma does exactly what you'd expect: it stops the
1905 named function from being inlined by the compiler. You shouldn't ever
1906 need to do this, unless you're very cautious about code size.
1908 <sect2>SPECIALIZE pragma
1909 <label id="specialize-pragma">
1911 <nidx>SPECIALIZE pragma</nidx>
1912 <nidx>pragma, SPECIALIZE</nidx>
1913 <nidx>overloading, death to</nidx>
1915 (UK spelling also accepted.) For key overloaded functions, you can
1916 create extra versions (NB: more code space) specialised to particular
1917 types. Thus, if you have an overloaded function:
1920 hammeredLookup :: Ord key => [(key, value)] -> key -> value
1923 If it is heavily used on lists with @Widget@ keys, you could
1924 specialise it as follows:
1926 {-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-}
1929 To get very fancy, you can also specify a named function to use for
1930 the specialised value, by adding @= blah@, as in:
1932 {-# SPECIALIZE hammeredLookup :: ...as before... = blah #-}
1934 It's <em>Your Responsibility</em> to make sure that @blah@ really
1935 behaves as a specialised version of @hammeredLookup@!!!
1937 NOTE: the @=blah@ feature isn't implemented in GHC 4.xx.
1939 An example in which the @= blah@ form will Win Big:
1941 toDouble :: Real a => a -> Double
1942 toDouble = fromRational . toRational
1944 {-# SPECIALIZE toDouble :: Int -> Double = i2d #-}
1945 i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
1947 The @i2d@ function is virtually one machine instruction; the
1948 default conversion---via an intermediate @Rational@---is obscenely
1949 expensive by comparison.
1951 By using the US spelling, your @SPECIALIZE@ pragma will work with
1952 HBC, too. Note that HBC doesn't support the @= blah@ form.
1954 A @SPECIALIZE@ pragma for a function can be put anywhere its type
1955 signature could be put.
1957 <sect2>SPECIALIZE instance pragma
1958 <label id="specialize-instance-pragma">
1960 <nidx>SPECIALIZE pragma</nidx>
1961 <nidx>overloading, death to</nidx>
1962 Same idea, except for instance declarations. For example:
1964 instance (Eq a) => Eq (Foo a) where { ... usual stuff ... }
1966 {-# SPECIALIZE instance Eq (Foo [(Int, Bar)] #-}
1968 Compatible with HBC, by the way.
1971 <label id="line-pragma">
1973 <nidx>LINE pragma</nidx>
1974 <nidx>pragma, LINE</nidx>
1976 This pragma is similar to C's @#line@ pragma, and is mainly for use in
1977 automatically generated Haskell code. It lets you specify the line
1978 number and filename of the original code; for example
1981 {-# LINE 42 "Foo.vhs" #-}
1984 if you'd generated the current file from something called @Foo.vhs@
1985 and this line corresponds to line 42 in the original. GHC will adjust
1986 its error messages to refer to the line/file named in the @LINE@