X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fdocs%2Fusers_guide%2Fglasgow_exts.sgml;h=1c42f5d1c6945dd331f8d1c1dacf2e72cfccd7fa;hb=2dfd507259664e6f28df4a9467a8de34d01d70a0;hp=b43f6d4abbcd6e4165bca70aef3ef9d5ccdf7200;hpb=5d86a0c4dae6b6c04f03316ffe8a4c10ada38662;p=ghc-hetmet.git diff --git a/ghc/docs/users_guide/glasgow_exts.sgml b/ghc/docs/users_guide/glasgow_exts.sgml index b43f6d4..1c42f5d 100644 --- a/ghc/docs/users_guide/glasgow_exts.sgml +++ b/ghc/docs/users_guide/glasgow_exts.sgml @@ -2,17 +2,19 @@ language, GHC extensions, GHC As with all known Haskell systems, GHC implements some extensions to -the language. To use them, you'll need to give a --fglasgow-exts option option. +the language. They are all enabled by options; by default GHC +understands only plain Haskell 98. -Virtually all of the Glasgow extensions serve to give you access to -the underlying facilities with which we implement Haskell. Thus, you -can get at the Raw Iron, if you are willing to write some non-standard -code at a more primitive level. You need not be “stuck” on -performance because of the implementation costs of Haskell's -“high-level” features—you can always code “under” them. In an extreme case, you can write all your time-critical code in C, and then just glue it together with Haskell! +Some of the Glasgow extensions serve to give you access to the +underlying facilities with which we implement Haskell. Thus, you can +get at the Raw Iron, if you are willing to write some non-portable +code at a more primitive level. You need not be “stuck” +on performance because of the implementation costs of Haskell's +“high-level” features—you can always code +“under” them. In an extreme case, you can write all your +time-critical code in C, and then just glue it together with Haskell! @@ -20,8 +22,8 @@ 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. The -separate libraries documentation describes all the libraries that come -with GHC. +separate libraries +documentation describes all the libraries that come with GHC. @@ -35,10 +37,38 @@ with GHC. extensionsoptions controlling - These flags control what variation of the language are + These flags control what variation of the language are permitted. Leaving out all of them gives you standard Haskell 98. + NB. turning on an option that enables special syntax + might cause working Haskell 98 code to fail + to compile, perhaps because it uses a variable name which has + become a reserved word. So, together with each option below, we + list the special syntax which is enabled by this option. We use + notation and nonterminal names from the Haskell 98 lexical syntax + (see the Haskell 98 Report). There are two classes of special + syntax: + + + + New reserved words and symbols: character sequences + which are no longer available for use as identifiers in the + program. + + + Other special syntax: sequences of characters that have + a different meaning when this particular option is turned + on. + + + + We are only listing syntax changes here that might affect + existing working programs (i.e. "stolen" syntax). Many of these + extensions will also enable new context-free syntax, but in all + cases programs written to use the new syntax would not be + compilable without the option enabled. + @@ -47,8 +77,21 @@ with GHC. This simultaneously enables all of the extensions to Haskell 98 described in , except where otherwise + linkend="ghc-language-features"/>, except where otherwise noted. + + New reserved words: forall (only in + types), mdo. + + Other syntax stolen: + varid{#}, + char#, + string#, + integer#, + float#, + float##, + (#, #), + |), {|. @@ -61,18 +104,8 @@ with GHC. 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. + New reserved words: foreign. @@ -95,7 +128,7 @@ with GHC. - See . Only relevant + See . Only relevant if you also use . @@ -104,48 +137,92 @@ with GHC. - See . Only relevant if + See . Only relevant if you also use . + + + + See . Independent of + . + + New reserved words/symbols: rec, + proc, -<, + >-, -<<, + >>-. + + Other syntax stolen: (|, + |). + + + + - See . Independent of + See . Independent of . - - - - -fno-implicit-prelude - option GHC normally imports - Prelude.hi files for you. If you'd - rather it didn't, then give it a - option. The idea - is that you can then import a Prelude of your own. (But - don't call it Prelude; the Haskell - module namespace is flat, and you must not conflict with - any Prelude module.) - - 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] - still means Prelude.[] Int; tuples - continue to refer to the standard Prelude tuples; the - translation for list comprehensions continues to use - Prelude.map etc. - - However, does - change the handling of certain built-in syntax: see - . + + + + -fno-implicit-prelude + option GHC normally imports + Prelude.hi files for you. If you'd + rather it didn't, then give it a + option. The idea is + that you can then import a Prelude of your own. (But don't + call it Prelude; the Haskell module + namespace is flat, and you must not conflict with any + Prelude module.) + + 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] + still means Prelude.[] Int; tuples + continue to refer to the standard Prelude tuples; the + translation for list comprehensions continues to use + Prelude.map etc. + + However, does + change the handling of certain built-in syntax: see . + + - - + + + + Enables Template Haskell (see ). Currently also implied by + . + + Syntax stolen: [|, + [e|, [p|, + [d|, [t|, + $(, + $varid. + + + + + + + Enables implicit parameters (see ). Currently also implied by + . + + Syntax stolen: + ?varid, + %varid. + + @@ -406,9 +483,9 @@ tuples to avoid unnecessary allocation during sequences of operations. import qualified Control.Monad.ST.Strict as ST - Hierarchical modules have an impact on the way that GHC - searches for files. For a description, see . + 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. @@ -428,7 +505,7 @@ import qualified Control.Monad.ST.Strict as ST Pattern guards (Glasgow extension) -The discussion that follows is an abbreviated version of Simon Peyton Jones's original proposal. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.) +The discussion that follows is an abbreviated version of Simon Peyton Jones's original proposal. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.) @@ -440,11 +517,11 @@ lookup :: FiniteMap -> Int -> Maybe Int The lookup returns Nothing if the supplied key is not in the domain of the mapping, and (Just v) otherwise, -where v is the value that the key maps to. Now consider the following definition: +where v is the value that the key maps to. Now consider the following definition: -clunky env var1 var2 | ok1 && ok2 = val1 + val2 +clunky env var1 var2 | ok1 && ok2 = val1 + val2 | otherwise = var1 + var2 where m1 = lookup env var1 @@ -470,12 +547,12 @@ expectJust Nothing = error "Unexpected Nothing" -What is clunky doing? The guard ok1 && +What is clunky doing? The guard ok1 && ok2 checks that both lookups succeed, using maybeToBool to convert the Maybe types to booleans. The (lazily evaluated) expectJust calls extract the values from the results of the lookups, and binds the -returned values to val1 and val2 +returned values to val1 and val2 respectively. If either lookup fails, then clunky takes the otherwise case and returns the sum of its arguments. @@ -538,9 +615,9 @@ with among the pattern guards. For example: -f x | [y] <- x +f x | [y] <- x , y > 3 - , Just z <- h y + , Just z <- h y = ... @@ -574,7 +651,7 @@ Here is a simple (yet contrived) example: import Control.Monad.Fix -justOnes = mdo xs <- Just (1:xs) +justOnes = mdo xs <- Just (1:xs) return xs @@ -654,7 +731,7 @@ This name is not supported by GHC. example, the following zips together two lists: - [ (x, y) | x <- xs | y <- ys ] + [ (x, y) | x <- xs | y <- ys ] The behavior of parallel list comprehensions follows that of @@ -667,8 +744,8 @@ This name is not supported by GHC. Given a parallel comprehension of the form: - [ e | p1 <- e11, p2 <- e12, ... - | q1 <- e21, q2 <- e22, ... + [ e | p1 <- e11, p2 <- e12, ... + | q1 <- e21, q2 <- e22, ... ... ] @@ -676,8 +753,8 @@ This name is not supported by GHC. This will be translated to: - [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...] - [(q1,q2) | q1 <- e21, q2 <- e22, ...] + [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...] + [(q1,q2) | q1 <- e21, q2 <- e22, ...] ... ] @@ -765,7 +842,11 @@ This name is not supported by GHC. Type system extensions - + + +Data types and type synonyms + + Data types with no constructors With the flag, GHC lets you declare @@ -779,13 +860,13 @@ a data type with no constructors. For example: 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 ). +(see ). Such data types have only one value, namely bottom. Nevertheless, they can be useful when defining "phantom types". - + - + Infix type constructors @@ -836,221 +917,449 @@ like expressions. More specifically: - + - -Explicitly-kinded quantification + +Liberalised type synonyms -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: +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: -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 - - - + You can write a forall (including overloading) +in a type synonym, thus: + + type Discard a = forall b. Show b => a -> b -> (a, String) - -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. - + f :: Discard a + f x y = (x, show y) - -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. + g :: Discard Int -> (Int,Bool) -- A rank-2 type + g f = f Int True + - + + +You can write an unboxed tuple in a type synonym: + + type Pr = (# Int, Int #) - -Class method types - - -Haskell 98 prohibits class method types to mention constraints on the -class type variable, thus: + h :: Int -> Pr + h x = (# x, x #) + + + + +You can apply a type synonym to a forall type: - class Seq s a where - fromList :: [a] -> s a - elem :: Eq a => a -> s a -> Bool + type Foo a = a -> a -> Bool + + f :: Foo (forall b. b->b) -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). +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] + + + + + -With the GHC lifts this restriction. +GHC currently does kind checking before expanding synonyms (though even that +could be changed.) + +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 #) - + h :: Pr -> Int + h x = ... + +because GHC does not allow unboxed tuples on the left of a function arrow. + + - -Multi-parameter type classes + +<sect3 id="existential-quantification"> +<title>Existentially quantified data constructors -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). +The idea of using existential quantification in data type declarations +was suggested by Laufer (I believe, thought doubtless someone will +correct me), and implemented in Hope+. It's been in Lennart +Augustsson's hbc Haskell compiler for several years, and +proved very useful. Here's the idea. Consider the declaration: - - -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 + data Foo = forall a. MkFoo a (a -> Bool) + | Nil -(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 ). - - - +The data type Foo has two constructors with types: + - 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 + MkFoo :: forall a. a -> (a -> Bool) -> Foo + Nil :: Foo - -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: +Notice that the type variable a in the type of MkFoo +does not appear in the data type itself, which is plain Foo. +For example, the following expression is fine: + + - forall a. C a b => burble + [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo] + -The next type is illegal because the constraint Eq b does not -mention a: + +Here, (MkFoo 3 even) packages an integer with a function +even that maps an integer to Bool; and MkFoo 'c' +isUpper packages a character with a compatible function. These +two things are each of type Foo and can be put in a list. + + + +What can we do with a value of type Foo?. In particular, +what happens when we pattern-match on MkFoo? + + - forall a. Eq b => burble + f (MkFoo val fn) = ??? - -The reason for this restriction is milder than the other one. The -excluded types are never useful or necessary (because the offending -context doesn't need to be witnessed at this point; it can be floated -out). Furthermore, floating them out increases sharing. Lastly, -excluding them is a conservative choice; it leaves a patch of -territory free in case we need it later. - - - - - - - -Unlike Haskell 1.4, constraints in types do not have to be of -the form (class type-variables). Thus, these type signatures -are perfectly OK +Since all we know about val and fn is that they +are compatible, the only (useful) thing we can do with them is to +apply fn to val to get a boolean. For example: - f :: Eq (m a) => [m a] -> [m a] - g :: Eq [a] => ... + f :: Foo -> Bool + f (MkFoo val fn) = fn val -This choice recovers principal types, a property that Haskell 1.4 does not have. +What this allows us to do is to package heterogenous values +together with a bunch of functions that manipulate them, and then treat +that collection of packages in a uniform manner. You can express +quite a bit of object-oriented-like programming this way. + +Why existential? + + + +What has this to do with existential quantification? +Simply that MkFoo has the (nearly) isomorphic type + + + + + + MkFoo :: (exists a . (a, a -> Bool)) -> Foo + + + + + +But Haskell programmers can safely think of the ordinary +universally quantified type given above, thereby avoiding +adding a new existential quantification construct. + + + + + +Type classes + + +An easy extension (implemented in hbc) is to allow +arbitrary contexts before the constructor. For example: + + + + + +data Baz = forall a. Eq a => Baz1 a a + | forall b. Show b => Baz2 b (b -> b) + + + + + +The two constructors have the types you'd expect: + + + + + +Baz1 :: forall a. Eq a => a -> a -> Baz +Baz2 :: forall b. Show b => b -> (b -> b) -> Baz + + + + + +But when pattern matching on Baz1 the matched values can be compared +for equality, and when pattern matching on Baz2 the first matched +value can be converted to a string (as well as applying the function to it). +So this program is legal: + + + + + + f :: Baz -> String + f (Baz1 p q) | p == q = "Yes" + | otherwise = "No" + f (Baz2 v fn) = show (fn v) + + + + + +Operationally, in a dictionary-passing implementation, the +constructors Baz1 and Baz2 must store the +dictionaries for Eq and Show respectively, and +extract it on pattern matching. + + + +Notice the way that the syntax fits smoothly with that used for +universal quantification earlier. + + + + + +Restrictions + + +There are several restrictions on the ways in which existentially-quantified +constructors can be use. + + + + + + + + + When pattern matching, each pattern match introduces a new, +distinct, type for each existential type variable. These types cannot +be unified with any other type, nor can they escape from the scope of +the pattern match. For example, these fragments are incorrect: + + + +f1 (MkFoo a f) = a + + + +Here, the type bound by MkFoo "escapes", because a +is the result of f1. One way to see why this is wrong is to +ask what type f1 has: + + + + f1 :: Foo -> a -- Weird! + + + +What is this "a" in the result type? Clearly we don't mean +this: + + + + f1 :: forall a. Foo -> a -- Wrong! + + + +The original program is just plain wrong. Here's another sort of error + + + + f2 (Baz1 a b) (Baz1 p q) = a==q + + + +It's ok to say a==b or p==q, but +a==q is wrong because it equates the two distinct types arising +from the two Baz1 constructors. + + + + + + + +You can't pattern-match on an existentially quantified +constructor in a let or where group of +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 + + +In general, you can only pattern-match +on an existentially-quantified constructor in a case expression or +in the patterns of a function definition. + +The reason for this restriction is really an implementation one. +Type-checking binding groups is already a nightmare without +existentials complicating the picture. Also an existential pattern +binding at the top level of a module doesn't make sense, because it's +not clear how to prevent the existentially-quantified type "escaping". +So for now, there's a simple-to-state restriction. We'll see how +annoying it is. + + + + + + +You can't use existential quantification for newtype +declarations. So this is illegal: + + + + newtype T = forall a. Ord a => MkT a + + + +Reason: a value of type T must be represented as a +pair of a dictionary for Ord t and a value of type +t. That contradicts the idea that +newtype should have no concrete representation. +You can get just the same efficiency and effect by using +data instead of newtype. If +there is no overloading involved, then there is more of a case for +allowing an existentially-quantified newtype, +because the data version does carry an +implementation cost, but single-field existentially quantified +constructors aren't much use. So the simple restriction (no +existential stuff on newtype) stands, unless there +are convincing reasons to change it. + + + + + + + + You can't use deriving to define instances of a +data type with existentially quantified data constructors. + +Reason: in most cases it would not make sense. For example:# + + +data T = forall a. MkT [a] deriving( Eq ) + + +To derive Eq in the standard way we would need to have equality +between the single component of two MkT constructors: + + +instance Eq T where + (MkT a) == (MkT b) = ??? + + +But a and b have distinct types, and so can't be compared. +It's just about possible to imagine examples in which the derived instance +would make sense, but it seems altogether simpler simply to prohibit such +declarations. Define your own instances! + + + + + + + + - + + + + + Class declarations - - +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). + + +There are the following constraints on class declarations: + @@ -1114,7 +1423,7 @@ be acyclic. So these class declarations are OK: All of the class type variables must be reachable (in the sense -mentioned in ) +mentioned in ) from the free varibles of each method type . For example: @@ -1159,33 +1468,217 @@ class like this: - + + + +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. - -Instance declarations - - + - - + +Type signatures +The context of a type signature - Instance declarations may not overlap. The two instance -declarations - - +Unlike Haskell 98, constraints in types do not have to be of +the form (class type-variable) or +(class (type-variable type-variable ...)). Thus, +these type signatures are perfectly OK - instance context1 => C type1 where ... - instance context2 => C type2 where ... + g :: Eq [a] => ... + g :: Ord (T a ()) => ... + + +GHC imposes the following restrictions on the constraints in a type signature. +Consider the type: + + + forall tv1..tvn (c1, ...,cn) => type + + +(Here, we write the "foralls" explicitly, although the Haskell source +language omits them; in Haskell 98, all the free type variables of an +explicit source-language type signature are universally quantified, +except for the class type variables in a class declaration. However, +in GHC, you can give the foralls if you want. See ). + + + + + + + + + Each universally quantified type variable +tvi must be reachable from type. + +A type variable a is "reachable" if it it appears +in the same constraint as either a type variable free in in +type, or another reachable type variable. +A value with a type that does not obey +this reachability restriction cannot be used without introducing +ambiguity; that is why the type is rejected. +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. + + +Note +that the reachability condition is weaker than saying that a is +functionally dependendent on a type variable free in +type (see ). The reason for this is there +might be a "hidden" dependency, in a superclass perhaps. So +"reachable" is a conservative approximation to "functionally dependent". +For example, consider: + + class C a b | a -> b where ... + class C a b => D a b where ... + f :: forall a b. D a b => a -> a + +This is fine, because in fact a does functionally determine b +but that is not immediately apparent from f's type. + + + + + + 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 + + + +The next type is illegal because the constraint Eq b does not +mention a: + + + + forall a. Eq b => burble + + + +The reason for this restriction is milder than the other one. The +excluded types are never useful or necessary (because the offending +context doesn't need to be witnessed at this point; it can be floated +out). Furthermore, floating them out increases sharing. Lastly, +excluding them is a conservative choice; it leaves a patch of +territory free in case we need it later. + + + + + + + + + + +For-all hoisting + +It is often convenient to use generalised type synonyms (see ) at the right hand +end of an arrow, thus: + + type Discard a = forall b. a -> b -> a + + g :: Int -> Discard Int + g x y z = x+y + +Simply expanding the type synonym would give + + g :: Int -> (forall b. Int -> b -> Int) + +but GHC "hoists" the forall to give the isomorphic type + + g :: forall b. Int -> Int -> b -> Int + +In general, the rule is this: to determine the type specified by any explicit +user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly +performs the transformation: + + type1 -> forall a1..an. context2 => type2 +==> + forall a1..an. context2 => type1 -> type2 + +(In fact, GHC tries to retain as much synonym information as possible for use in +error messages, but that is a usability issue.) This rule applies, of course, whether +or not the forall comes from a synonym. For example, here is another +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 + + + + + + + + +Instance declarations + + +Overlapping instances + +In general, instance declarations may not overlap. The two instance +declarations -"overlap" if type1 and type2 unify + + instance context1 => C type1 where ... + instance context2 => C type2 where ... + +"overlap" if type1 and type2 unify. + + However, if you give the command line option -fallow-overlapping-instances option then overlapping instance declarations are permitted. @@ -1263,44 +1756,16 @@ when it is compiling Main. However, it currently chooses not to look at ones that can't possibly be of use in the module currently being compiled, in the interests of efficiency. (Perhaps we should change that decision, at least for Main.) - - - - - - There are no restrictions on the type in an instance -head, except that at least one must not be a type variable. -The instance "head" is the bit after the "=>" in an instance decl. For -example, these are OK: - - - - instance C Int a where ... - - instance D (Int, Int) where ... - - instance E [[a]] where ... - - - -Note that instance heads may contain repeated type variables. -For example, this is OK: - - - - instance Stateful (ST s) (MutVar s) where ... - + -See for an experimental -extension to lift this restriction. - - - + +Type synonyms in the instance head - Unlike Haskell 1.4, instance heads may use type -synonyms. As always, using a type synonym is just shorthand for +Unlike Haskell 98, instance heads may use type +synonyms. (The instance "head" is the bit after the "=>" in an instance decl.) +As always, using a type synonym is just shorthand for writing the RHS of the type synonym definition. For example: @@ -1334,55 +1799,52 @@ This design decision is independent of all the others, and easily reversed, but it makes sense to me. - - + - -The types in an instance-declaration context must all -be type variables. Thus + +Undecidable instances +An instance declaration must normally obey the following rules: + +At least one of the types in the head of +an instance declaration must not be a type variable. +For example, these are OK: -instance C a b => Eq (a,b) where ... - - - -is OK, but + instance C Int a where ... + instance D (Int, Int) where ... + instance E [[a]] where ... + +but this is not: -instance C Int b => Foo b where ... + instance F a where ... + +Note that instance heads may contain repeated type variables. +For example, this is OK: + + instance Stateful (ST s) (MutVar s) where ... - - -is not OK. See for an experimental -extension to lift this restriction. - - - - - - - - - - - - -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 + +All of the types in the context of an instance declaration must be type variables. - - +Thus + +instance C a b => Eq (a,b) where ... + +is OK, but + +instance C Int b => Foo b where ... + +is not OK. + + + These restrictions ensure that context reduction terminates: each reduction step removes one type constructor. For example, the following would make the type checker @@ -1443,11 +1905,13 @@ 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 - +Implicit parameters Implicit paramters are implemented as described in "Implicit parameters: dynamic scoping with static types", @@ -1455,7 +1919,13 @@ 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.) + +(Most of the following, stil rather incomplete, documentation is +due to Jeff Lewis.) + +Implicit parameter support is enabled with the option +. + 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 @@ -1559,7 +2029,7 @@ For example, we define the min function by binding cmp. min :: [a] -> a - min = let ?cmp = (<=) in least + min = let ?cmp = (<=) in least @@ -1606,8 +2076,7 @@ the binding for ?x, so the type of f is -Linear implicit parameters - +Linear implicit parameters Linear implicit parameters are an idea developed by Koen Claessen, Mark Shields, and Simon PJ. They address the long-standing @@ -1799,25 +2268,88 @@ There should be more documentation, but there isn't (yet). Yell if you need it. - -Arbitrary-rank polymorphism - + + +Explicitly-kinded quantification -Haskell type signatures are implicitly quantified. The new keyword forall -allows us to say exactly what this means. For example: - - - - g :: b -> b - -means this: - - g :: forall b. (b -> b) - -The two are treated identically. +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. + + + + + +Arbitrary-rank polymorphism + + + +Haskell type signatures are implicitly quantified. The new keyword forall +allows us to say exactly what this means. For example: + + + + g :: b -> b + +means this: + + g :: forall b. (b -> b) + +The two are treated identically. + + However, GHC's type system supports arbitrary-rank explicit universal quantification in @@ -1843,8 +2375,8 @@ the forall is on the left of a function arrrow. As shows, the polymorphic type on the left of the function arrow can be overloaded. -The functions f3 and g3 have rank-3 types; -they have rank-2 types on the left of a function arrow. +The function f3 has a rank-3 type; +it has rank-2 types on the left of a function arrow. GHC allows types of arbitrary rank; you can nest foralls @@ -1854,12 +2386,12 @@ In particular, a forall-type (also called a "type scheme"), including an operational type class context, is legal: On the left of a function arrow - On the right of a function arrow (see ) + On the right of a function arrow (see ) As the argument of a constructor, or type of a field, in a data type declaration. For -example, any of the f1,f2,f3,g1,g2,g3 above would be valid +example, any of the f1,f2,f3,g1,g2 above would be valid field type signatures. As the type of an implicit parameter - In a pattern type signature (see ) + In a pattern type signature (see ) There is one place you cannot put a forall: you cannot instantiate a type variable with a forall-type. So you cannot @@ -2025,7 +2557,7 @@ that x's type has no foralls in it. What does it mean to "provide" an explicit type for x? You can do that by giving a type signature for x directly, using a pattern type signature -(), thus: +(), thus: \ f :: (forall a. a->a) -> (f True, f 'c') @@ -2084,497 +2616,27 @@ point. For example: f :: (a -> a) -> Int -- MEANS - f :: forall a. (a -> a) -> Int - -- NOT - f :: (forall a. a -> a) -> Int - - - g :: (Ord a => a -> a) -> Int - -- MEANS the illegal type - g :: forall a. (Ord a => a -> a) -> Int - -- NOT - g :: (forall a. Ord a => a -> a) -> Int - -The latter produces an illegal type, which you might think is silly, -but at least the rule is simple. If you want the latter type, you -can write your for-alls explicitly. Indeed, doing so is strongly advised -for rank-2 types. - - - - - -Liberalised type synonyms - - - -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: - - type Discard a = forall b. Show b => a -> b -> (a, String) - - f :: Discard a - f x y = (x, show y) - - g :: Discard Int -> (Int,Bool) -- A rank-2 type - g f = f Int True - - - - - -You can write an unboxed tuple in a type synonym: - - type Pr = (# Int, Int #) - - h :: Int -> Pr - 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.) - - -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 #) - - h :: Pr -> Int - h x = ... - -because GHC does not allow unboxed tuples on the left of a function arrow. - - - - -For-all hoisting - -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 - - g :: Int -> Discard Int - g x y z = x+y - -Simply expanding the type synonym would give - - g :: Int -> (forall b. Int -> b -> Int) - -but GHC "hoists" the forall to give the isomorphic type - - g :: forall b. Int -> Int -> b -> Int - -In general, the rule is this: to determine the type specified by any explicit -user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly -performs the transformation: - - type1 -> forall a1..an. context2 => type2 -==> - forall a1..an. context2 => type1 -> type2 - -(In fact, GHC tries to retain as much synonym information as possible for use in -error messages, but that is a usability issue.) This rule applies, of course, whether -or not the forall comes from a synonym. For example, here is another -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 - - - -The idea of using existential quantification in data type declarations -was suggested by Laufer (I believe, thought doubtless someone will -correct me), and implemented in Hope+. It's been in Lennart -Augustsson's hbc Haskell compiler for several years, and -proved very useful. Here's the idea. Consider the declaration: - - - - - - data Foo = forall a. MkFoo a (a -> Bool) - | Nil - - - - - -The data type Foo has two constructors with types: - - - - - - MkFoo :: forall a. a -> (a -> Bool) -> Foo - Nil :: Foo - - - - - -Notice that the type variable a in the type of MkFoo -does not appear in the data type itself, which is plain Foo. -For example, the following expression is fine: - - - - - - [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo] - - - - - -Here, (MkFoo 3 even) packages an integer with a function -even that maps an integer to Bool; and MkFoo 'c' -isUpper packages a character with a compatible function. These -two things are each of type Foo and can be put in a list. - - - -What can we do with a value of type Foo?. In particular, -what happens when we pattern-match on MkFoo? - - - - - - f (MkFoo val fn) = ??? - - - - - -Since all we know about val and fn is that they -are compatible, the only (useful) thing we can do with them is to -apply fn to val to get a boolean. For example: - - - - - - f :: Foo -> Bool - f (MkFoo val fn) = fn val - - - - - -What this allows us to do is to package heterogenous values -together with a bunch of functions that manipulate them, and then treat -that collection of packages in a uniform manner. You can express -quite a bit of object-oriented-like programming this way. - - - -Why existential? - - - -What has this to do with existential quantification? -Simply that MkFoo has the (nearly) isomorphic type - - - - - - MkFoo :: (exists a . (a, a -> Bool)) -> Foo - - - - - -But Haskell programmers can safely think of the ordinary -universally quantified type given above, thereby avoiding -adding a new existential quantification construct. - - - - - -Type classes - - -An easy extension (implemented in hbc) is to allow -arbitrary contexts before the constructor. For example: - - - - - -data Baz = forall a. Eq a => Baz1 a a - | forall b. Show b => Baz2 b (b -> b) - - - - - -The two constructors have the types you'd expect: - - - - - -Baz1 :: forall a. Eq a => a -> a -> Baz -Baz2 :: forall b. Show b => b -> (b -> b) -> Baz - - - - - -But when pattern matching on Baz1 the matched values can be compared -for equality, and when pattern matching on Baz2 the first matched -value can be converted to a string (as well as applying the function to it). -So this program is legal: - - - - - - f :: Baz -> String - f (Baz1 p q) | p == q = "Yes" - | otherwise = "No" - f (Baz2 v fn) = show (fn v) - - - - - -Operationally, in a dictionary-passing implementation, the -constructors Baz1 and Baz2 must store the -dictionaries for Eq and Show respectively, and -extract it on pattern matching. - - - -Notice the way that the syntax fits smoothly with that used for -universal quantification earlier. - - - - - -Restrictions - - -There are several restrictions on the ways in which existentially-quantified -constructors can be use. - - - - - - - - - When pattern matching, each pattern match introduces a new, -distinct, type for each existential type variable. These types cannot -be unified with any other type, nor can they escape from the scope of -the pattern match. For example, these fragments are incorrect: - - - -f1 (MkFoo a f) = a - - - -Here, the type bound by MkFoo "escapes", because a -is the result of f1. One way to see why this is wrong is to -ask what type f1 has: - - - - f1 :: Foo -> a -- Weird! - - - -What is this "a" in the result type? Clearly we don't mean -this: - - - - f1 :: forall a. Foo -> a -- Wrong! - - - -The original program is just plain wrong. Here's another sort of error - - - - f2 (Baz1 a b) (Baz1 p q) = a==q - - - -It's ok to say a==b or p==q, but -a==q is wrong because it equates the two distinct types arising -from the two Baz1 constructors. - - - - - - - -You can't pattern-match on an existentially quantified -constructor in a let or where group of -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 - - -In general, you can only pattern-match -on an existentially-quantified constructor in a case expression or -in the patterns of a function definition. - -The reason for this restriction is really an implementation one. -Type-checking binding groups is already a nightmare without -existentials complicating the picture. Also an existential pattern -binding at the top level of a module doesn't make sense, because it's -not clear how to prevent the existentially-quantified type "escaping". -So for now, there's a simple-to-state restriction. We'll see how -annoying it is. - - - - - - -You can't use existential quantification for newtype -declarations. So this is illegal: - - - - newtype T = forall a. Ord a => MkT a - - - -Reason: a value of type T must be represented as a pair -of a dictionary for Ord t and a value of type t. -That contradicts the idea that newtype should have no -concrete representation. You can get just the same efficiency and effect -by using data instead of newtype. If there is no -overloading involved, then there is more of a case for allowing -an existentially-quantified newtype, because the data -because the data version does carry an implementation cost, -but single-field existentially quantified constructors aren't much -use. So the simple restriction (no existential stuff on newtype) -stands, unless there are convincing reasons to change it. - - - - - - - - You can't use deriving to define instances of a -data type with existentially quantified data constructors. - -Reason: in most cases it would not make sense. For example:# - - -data T = forall a. MkT [a] deriving( Eq ) - + f :: forall a. (a -> a) -> Int + -- NOT + f :: (forall a. a -> a) -> Int -To derive Eq in the standard way we would need to have equality -between the single component of two MkT constructors: - -instance Eq T where - (MkT a) == (MkT b) = ??? + g :: (Ord a => a -> a) -> Int + -- MEANS the illegal type + g :: forall a. (Ord a => a -> a) -> Int + -- NOT + g :: (forall a. Ord a => a -> a) -> Int - -But a and b have distinct types, and so can't be compared. -It's just about possible to imagine examples in which the derived instance -would make sense, but it seems altogether simpler simply to prohibit such -declarations. Define your own instances! +The latter produces an illegal type, which you might think is silly, +but at least the rule is simple. If you want the latter type, you +can write your for-alls explicitly. Indeed, doing so is strongly advised +for rank-2 types. - - - + + - - - Scoped type variables @@ -2597,23 +2659,23 @@ f (xs::[a]) = ys ++ ys </para> <para> -The pattern <literal>(xs::[a])</literal> includes a type signature for <VarName>xs</VarName>. +The pattern <literal>(xs::[a])</literal> includes a type signature for <varname>xs</varname>. This brings the type variable <literal>a</literal> into scope; it scopes over all the patterns and right hand sides for this equation for <function>f</function>. -In particular, it is in scope at the type signature for <VarName>y</VarName>. +In particular, it is in scope at the type signature for <varname>y</varname>. </para> <para> Pattern type signatures are completely orthogonal to ordinary, separate type signatures. The two can be used independently or together. -At ordinary type signatures, such as that for <VarName>ys</VarName>, any type variables +At ordinary type signatures, such as that for <varname>ys</varname>, any type variables mentioned in the type signature <emphasis>that are not in scope</emphasis> are implicitly universally quantified. (If there are no type variables in scope, all type variables mentioned in the signature are universally -quantified, which is just as in Haskell 98.) In this case, since <VarName>a</VarName> -is in scope, it is not universally quantified, so the type of <VarName>ys</VarName> is -the same as that of <VarName>xs</VarName>. In Haskell 98 it is not possible to declare -a type for <VarName>ys</VarName>; a major benefit of scoped type variables is that +quantified, which is just as in Haskell 98.) In this case, since <varname>a</varname> +is in scope, it is not universally quantified, so the type of <varname>ys</varname> is +the same as that of <varname>xs</varname>. In Haskell 98 it is not possible to declare +a type for <varname>ys</varname>; a major benefit of scoped type variables is that it becomes possible to do so. </para> @@ -2700,9 +2762,9 @@ The type variable(s) bound by the pattern have the same scope as the term variable(s) bound by the pattern. For example: <programlisting> let - f (x::a) = <...rhs of f...> + f (x::a) = <...rhs of f...> (p::b, q::b) = (1,2) - in <...body of let...> + in <...body of let...> </programlisting> Here, the type variable <literal>a</literal> scopes over the right hand side of <literal>f</literal>, just like <literal>x</literal> does; while the type variable <literal>b</literal> scopes over the @@ -2742,7 +2804,7 @@ into scope (except in the type signature itself!). So this is illegal: f x = x::a </programlisting> -It's illegal because <VarName>a</VarName> is not in scope in the body of <function>f</function>, +It's illegal because <varname>a</varname> is not in scope in the body of <function>f</function>, so the ordinary signature <literal>x::a</literal> is equivalent to <literal>x::forall a.a</literal>; and that is an incorrect typing. @@ -2971,6 +3033,25 @@ Result type signatures are not yet implemented in Hugs. </sect2> +<sect2 id="deriving-typeable"> +<title>Deriving clause for classes <literal>Typeable</literal> and <literal>Data</literal> + + +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 @@ -3103,17 +3184,24 @@ where S is a type constructor, - t1...tk are types, + The t1...tk are types, - vk+1...vn are type variables which do not occur in any of + The vk+1...vn are type variables which do not occur in any of the ti, and - the ci are partial applications of + 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. + + None of the ci is Read, Show, + Typeable, or Data. These classes + should not "look through" the type or its constructor. You can still + derive these classes for a newtype, but it happens in the usual way, not + via this new mechanism. + Then, for each ci, the derived instance declaration is: @@ -3168,11 +3256,19 @@ instances is most interesting. Template Haskell -Template Haskell allows you to do compile-time meta-programming in Haskell. The background -the main technical innovations are discussed in "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", in -Proc Haskell Workshop 2002. +Template Meta-programming for Haskell" (Proc Haskell Workshop 2002). +The details of the Template Haskell design are still in flux. Make sure you +consult the online library reference material +(search for the type ExpQ). +[Temporary: many changes to the original design are described in + "http://research.microsoft.com/~simonpj/tmp/notes2.ps". +Not all of these changes are in GHC 6.2.] The first example from that paper is set out below as a worked example to help get you started. @@ -3183,10 +3279,16 @@ The documentation here describes the realisation in GHC. (It's rather sketchy j 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. + + Syntax + + Template Haskell has the following new syntactic + constructions. You need to use the flag + + to switch these syntactic extensions on + ( is currently implied by + , but you are encouraged to + specify it explicitly). @@ -3233,7 +3335,6 @@ Tim Sheard is going to expand it.) - Using Template Haskell @@ -3273,6 +3374,7 @@ Tim Sheard is going to expand it.) First cut and paste the two modules below into "Main.hs" and "Printf.hs": + {- Main.hs -} module Main where @@ -3283,9 +3385,8 @@ import Printf ( pr ) -- generated at compile time by "pr" and splices it into -- the argument of "putStrLn". main = putStrLn ( $(pr "Hello") ) - - + {- Printf.hs -} module Printf where @@ -3294,7 +3395,7 @@ module Printf where -- you intend to use it. -- Import some Template Haskell syntax -import Language.Haskell.THSyntax +import Language.Haskell.TH.Syntax -- Describe a format string data Format = D | S | L String @@ -3308,25 +3409,24 @@ 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 :: [Format] -> ExpQ gen [D] = [| \n -> show n |] gen [S] = [| \s -> s |] -gen [L s] = string s +gen [L s] = stringE s -- Here we generate the Haskell code for the splice -- from an input format string. -pr :: String -> Expr +pr :: String -> ExpQ 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): +Now run the compiler (here we are a Cygwin prompt on Windows): -ghc/compiler/stage3/ghc-inplace --make -fglasgow-exts -package haskell-src main.hs -o main.exe +$ ghc --make -fth main.hs -o main.exe -Run "main.exe" and here is your output: - +Run "main.exe" and here is your output: $ ./main @@ -3337,6 +3437,497 @@ Hello + + + +Arrow notation + + +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. + + + + + +“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: + +exp10 ::= ... + | proc apat -> 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 ::= exp10 -< exp + | exp10 -<< exp + | cmd0 + +with cmd0 up to +cmd9 defined using +infix operators as for expressions, and + +cmd10 ::= \ apat ... apat -> cmd + | let decls in cmd + | if exp then cmd else cmd + | case exp of { calts } + | do { cstmt ; ... cstmt ; cmd } + | fcmd + +fcmd ::= fcmd aexp + | ( cmd ) + | (| aexp cmd ... cmd |) + +cstmt ::= let decls + | pat <- cmd + | rec { cstmt ; ... cstmt [;] } + | cmd + +where calts are like alts +except that the bodies are commands instead of expressions. + + + +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. + + + +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 -> do + returnA -< x + <+> do + symbol Plus -< () + y <- term -< () + expr' -< x + y + <+> do + symbol Minus -< () + y <- term -< () + expr' -< x - y + +(The do on the first line is needed to prevent the first +<+> ... from being interpreted as part of the +expression on the previous line.) +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. + + + + + + + + + + @@ -3455,7 +4046,7 @@ Assertion failures can be caught, see the documentation for the The DEPRECATED pragma lets you specify that a particular function, class, or type, is deprecated. There are two - forms. + forms. @@ -3480,7 +4071,15 @@ Assertion failures can be caught, see the documentation for the message. - + Any use of the deprecated item, or of anything from a deprecated + module, will be flagged with an appropriate message. However, + deprecations are not reported for + (a) uses of a deprecated function within its defining module, and + (b) uses of a deprecated function in an export list. + The latter reduces spurious complaints within a library + in which one module gathers together and re-exports + the exports of several others. + You can suppress the warnings with the flag . @@ -3543,7 +4142,7 @@ key_function :: Int -> String -> (Bool, Double) See also the NOINLINE pragma (). + linkend="noinline-pragma"/>). @@ -3632,7 +4231,7 @@ key_function :: Int -> String -> (Bool, Double) The same phase-numbering control is available for RULES - (). + (). @@ -3666,7 +4265,7 @@ key_function :: Int -> String -> (Bool, Double) The OPTIONS pragma is used to specify additional options that are given to the compiler when compiling - this source file. See for + this source file. See for details. @@ -3674,7 +4273,7 @@ key_function :: Int -> String -> (Bool, Double) RULES pragma The RULES pragma lets you specify rewrite rules. It is - described in . + described in . @@ -3704,41 +4303,20 @@ hammeredLookup :: Ord key => [(key, value)] -> key -> value A SPECIALIZE pragma for a function can be put anywhere its type signature could be put. - To get very fancy, you can also specify a named function - to use for the specialised value, as in: + 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. - -{-# RULES "hammeredLookup" hammeredLookup = blah #-} - - - where blah is an implementation of - hammerdLookup written specialy for - Widget lookups. It's 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. - - An example in which using RULES for - specialisation will Win Big: + In earlier versions of GHC, it was possible to provide your own + specialised function for a given type: -toDouble :: Real a => a -> Double -toDouble = fromRational . toRational - -{-# RULES "toDouble/Int" toDouble = i2d #-} -i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly +{-# SPECIALIZE hammeredLookup :: [(Int, value)] -> Int -> value = intLookup #-} - The i2d function is virtually one machine - instruction; the default conversion—via an intermediate - Rational—is obscenely expensive by - comparison. + This feature has been removed, as it is now subsumed by the + RULES pragma (see ). @@ -3767,7 +4345,71 @@ of the pragma. + + UNPACK pragma + + UNPACK + + The UNPACK indicates to the compiler + that it should unpack the contents of a constructor field into + the constructor itself, removing a level of indirection. For + example: + + +data T = T {-# UNPACK #-} !Float + {-# UNPACK #-} !Float + + + will create a constructor T containing + two unboxed floats. This may not always be an optimisation: if + the T constructor is scrutinised and the + floats passed to a non-strict function for example, they will + have to be reboxed (this is done automatically by the + compiler). + + Unpacking constructor fields should only be used in + conjunction with , in order to expose + unfoldings to the compiler so the reboxing can be removed as + often as possible. For example: + +f :: T -> Float +f (T f1 f2) = f1 + f2 + + + The compiler will avoid reboxing f1 + and f2 by inlining + + on floats, but only when is on. + + Any single-constructor data is eligible for unpacking; for + example + + +data T = T {-# UNPACK #-} !(Int,Int) + + + will store the two Ints directly in the + T constructor, by flattening the pair. + Multi-level unpacking is also supported: + + +data T = T {-# UNPACK #-} !S +data S = S {-# UNPACK #-} !Int {-# UNPACK #-} !Int + + + will store two unboxed Int#s + directly in the T constructor. The + unpacker can see through newtypes, too. + + If a field cannot be unpacked, you will not get a warning, + so it might be an idea to check the generated code with + . + + See also the flag, + which essentially has the effect of adding + {-# UNPACK #-} to every strict + constructor field. + @@ -3782,7 +4424,10 @@ of the pragma. 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. @@ -3820,7 +4465,7 @@ no significance at all. It is only used when reporting how many times the rule -A rule may optionally have a phase-control number (see ), +A rule may optionally have a phase-control number (see ), immediately after the name of the rule. Thus: {-# RULES @@ -3978,7 +4623,7 @@ But not beta conversion (that's called higher-order matching). Matching is carried out on GHC's intermediate language, which includes type abstractions and applications. So a rule only matches if the -types match too. See below. +types match too. See below. @@ -3995,8 +4640,8 @@ For example, consider: The expression s (t xs) does not match the rule "map/map", but GHC -will substitute for s and t, giving an expression which does match. -If s or t was (a) used more than once, and (b) large or a redex, then it would +will substitute for s and t, giving an expression which does match. +If s or t was (a) used more than once, and (b) large or a redex, then it would not be substituted, and the rule would not fire. @@ -4230,7 +4875,7 @@ will fuse with one but not the other) - + So, for example, the following should generate no intermediate lists: @@ -4257,43 +4902,62 @@ Prelude definitions of the above functions to see how to do so. Rewrite rules can be used to get the same effect as a feature -present in earlier version of GHC: +present in earlier versions of GHC. +For example, suppose that: - {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-} +genericLookup :: Ord a => Table a b -> a -> b +intLookup :: Table Int b -> Int -> b -This told GHC to use int8ToInt16 instead of fromIntegral whenever -the latter was called with type Int8 -> Int16. That is, rather than -specialising the original definition of fromIntegral the programmer is -promising that it is safe to use int8ToInt16 instead. - - - -This feature is no longer in GHC. But rewrite rules let you do the -same thing: +where intLookup is an implementation of +genericLookup that works very fast for +keys of type Int. You might wish +to tell GHC to use intLookup instead of +genericLookup whenever the latter was called with +type Table Int b -> Int -> b. +It used to be possible to write -{-# RULES - "fromIntegral/Int8/Int16" fromIntegral = int8ToInt16 -#-} +{-# SPECIALIZE genericLookup :: Table Int b -> Int -> b = intLookup #-} -This slightly odd-looking rule instructs GHC to replace fromIntegral -by int8ToInt16 whenever the types match. Speaking more operationally, -GHC adds the type and dictionary applications to get the typed rule +This feature is no longer in GHC, but rewrite rules let you do the same thing: -forall (d1::Integral Int8) (d2::Num Int16) . - fromIntegral Int8 Int16 d1 d2 = int8ToInt16 +{-# RULES "genericLookup/Int" genericLookup = intLookup #-} -What is more, -this rule does not need to be in the same file as fromIntegral, -unlike the SPECIALISE pragmas which currently do (so that they +This slightly odd-looking rule instructs GHC to replace +genericLookup by intLookup +whenever the types match. +What is more, this rule does not need to be in the same +file as genericLookup, unlike the +SPECIALIZE pragmas which currently do (so that they have an original definition available to specialise). +It is Your Responsibility to make sure that +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 + +{-# RULES "toDouble/Int" toDouble = i2d #-} +i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly + + +The i2d function is virtually one machine +instruction; the default conversion—via an intermediate +Rational—is obscenely expensive by +comparison. + + @@ -4318,7 +4982,7 @@ If you add you get a more detailed listing. - The defintion of (say) build in GHC/Base.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] @@ -4377,7 +5041,7 @@ g x = show x However, when external for is generated (via ), there will be Notes attached to the - expressions show and x. + expressions show and x. The core function declaration for f is: @@ -4405,8 +5069,8 @@ r) -> 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). + expression eta (which used to be called + x). @@ -4677,3 +5341,4 @@ Just to finish with, here's another example I rather like: ;;; sgml-parent-document: ("users_guide.sgml" "book" "chapter" "sect1") *** ;;; End: *** --> +