From 71f504147cda20d448b397b9872c2110bfbb6fbe Mon Sep 17 00:00:00 2001 From: simonpj Date: Thu, 14 Mar 2002 15:49:36 +0000 Subject: [PATCH] [project @ 2002-03-14 15:49:36 by simonpj] Documentation about type system extensions --- ghc/docs/users_guide/glasgow_exts.sgml | 799 ++++++++++++-------------------- ghc/docs/users_guide/primitives.sgml | 95 ++++ 2 files changed, 394 insertions(+), 500 deletions(-) diff --git a/ghc/docs/users_guide/glasgow_exts.sgml b/ghc/docs/users_guide/glasgow_exts.sgml index e5202b8..bc6dd13 100644 --- a/ghc/docs/users_guide/glasgow_exts.sgml +++ b/ghc/docs/users_guide/glasgow_exts.sgml @@ -16,160 +16,6 @@ performance because of the implementation costs of Haskell's -Executive summary of our extensions: - - - - - - Unboxed types and primitive operations: - - You can get right down to the raw machine types and - operations; included in this are “primitive - arrays” (direct access to Big Wads of Bytes). Please - see and following. - - - - - Type system extensions: - - GHC supports a large number of extensions to Haskell's - type system. Specifically: - - - - Class method types: - - - - - - - Multi-parameter type classes: - - - - - - - Functional dependencies: - - - - - - - Implicit parameters: - - - - - - - Linear implicit parameters: - - - - - - - Local universal quantification: - - - - - - - Extistentially quantification in data types: - - - - - - - Scoped type variables: - - Scoped type variables enable the programmer to - supply type signatures for some nested declarations, - where this would not be legal in Haskell 98. Details in - . - - - - - - - - Pattern guards - - Instead of being a boolean expression, a guard is a list - of qualifiers, exactly as in a list comprehension. See . - - - - - Data types with no constructors - - See . - - - - - Parallel list comprehensions - - An extension to the list comprehension syntax to support - zipWith-like functionality. See . - - - - - Foreign calling: - - Just what it sounds like. We provide - lots of rope that you can dangle around - your neck. Please see . - - - - - Pragmas - - Pragmas are special instructions to the compiler placed - in the source file. The pragmas GHC supports are described in - . - - - - - Rewrite rules: - - The programmer can specify rewrite rules as part of the - source program (in a pragma). GHC applies these rewrite rules - wherever it can. Details in . - - - - - Generic classes: - - (Note: support for generic classes is currently broken - in GHC 5.02). - - Generic class declarations allow you to define a class - whose methods say how to work over an arbitrary data type. - Then it's really easy to make any new type into an instance of - the class. This generalises the rather ad-hoc "deriving" - feature of Haskell 98. Details in . - - - - - Before you get too carried away working at the lowest level (e.g., sloshing MutableByteArray#s around your program), you may wish to check if there are libraries that provide a @@ -177,6 +23,7 @@ program), you may wish to check if there are libraries that provide a . + Language options @@ -321,126 +168,15 @@ program), you may wish to check if there are libraries that provide a + &primitives; - -Primitive state-transformer monad - - -state transformers (Glasgow extensions) -ST monad (Glasgow extension) - - - -This monad underlies our implementation of arrays, mutable and -immutable, and our implementation of I/O, including “C calls”. - - - -The ST library, which provides access to the -ST monad, is described in . - - - - - -Primitive arrays, mutable and otherwise - - - -primitive arrays (Glasgow extension) -arrays, primitive (Glasgow extension) - - - -GHC knows about quite a few flavours of Large Swathes of Bytes. - - - -First, GHC distinguishes between primitive arrays of (boxed) Haskell -objects (type Array# obj) and primitive arrays of bytes (type -ByteArray#). - - - -Second, it distinguishes between… - - - -Immutable: - - -Arrays that do not change (as with “standard” Haskell arrays); you -can only read from them. Obviously, they do not need the care and -attention of the state-transformer monad. - - - - -Mutable: - - -Arrays that may be changed or “mutated.” All the operations on them -live within the state-transformer monad and the updates happen -in-place. - - - - -“Static” (in C land): - - -A C routine may pass an Addr# pointer back into Haskell land. There -are then primitive operations with which you may merrily grab values -over in C land, by indexing off the “static” pointer. - - - - -“Stable” pointers: - - -If, for some reason, you wish to hand a Haskell pointer (i.e., -not an unboxed value) to a C routine, you first make the -pointer “stable,” so that the garbage collector won't forget that it -exists. That is, GHC provides a safe way to pass Haskell pointers to -C. - - - -Please see for more details. - - - - -“Foreign objects”: - - -A “foreign object” is a safe way to pass an external object (a -C-allocated pointer, say) to Haskell and have Haskell do the Right -Thing when it no longer references the object. So, for example, C -could pass a large bitmap over to Haskell and say “please free this -memory when you're done with it.” - - -Please see for more details. - - - - - + + +Type system extensions - -The libraries documentatation gives more details on all these -“primitive array” types and the operations on them. - - - - - - + Data types with no constructors With the flag, GHC lets you declare @@ -456,186 +192,9 @@ types. Such data types have only one value, namely bottom. Nevertheless, they can be useful when defining "phantom types". - - - -Pattern guards - - -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.) - - - -Suppose we have an abstract data type of finite maps, with a -lookup operation: - - -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: - - - -clunky env var1 var2 | ok1 && ok2 = val1 + val2 -| otherwise = var1 + var2 -where - m1 = lookup env var1 - m2 = lookup env var2 - ok1 = maybeToBool m1 - ok2 = maybeToBool m2 - val1 = expectJust m1 - val2 = expectJust m2 - - - -The auxiliary functions are - - - -maybeToBool :: Maybe a -> Bool -maybeToBool (Just x) = True -maybeToBool Nothing = False - -expectJust :: Maybe a -> a -expectJust (Just x) = x -expectJust Nothing = error "Unexpected Nothing" - - - -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 -respectively. If either lookup fails, then clunky takes the -otherwise case and returns the sum of its arguments. - - - -This is certainly legal Haskell, but it is a tremendously verbose and -un-obvious way to achieve the desired effect. Arguably, a more direct way -to write clunky would be to use case expressions: - - - -clunky env var1 var1 = case lookup env var1 of - Nothing -> fail - Just val1 -> case lookup env var2 of - Nothing -> fail - Just val2 -> val1 + val2 -where - fail = val1 + val2 - - - -This is a bit shorter, but hardly better. Of course, we can rewrite any set -of pattern-matching, guarded equations as case expressions; that is -precisely what the compiler does when compiling equations! The reason that -Haskell provides guarded equations is because they allow us to write down -the cases we want to consider, one at a time, independently of each other. -This structure is hidden in the case version. Two of the right-hand sides -are really the same (fail), and the whole expression -tends to become more and more indented. - - - -Here is how I would write clunky: - - - -clunky env var1 var1 - | Just val1 <- lookup env var1 - , Just val2 <- lookup env var2 - = val1 + val2 -...other equations for clunky... - - - -The semantics should be clear enough. The qualifers are matched in order. -For a <- qualifier, which I call a pattern guard, the -right hand side is evaluated and matched against the pattern on the left. -If the match fails then the whole guard fails and the next equation is -tried. If it succeeds, then the appropriate binding takes place, and the -next qualifier is matched, in the augmented environment. Unlike list -comprehensions, however, the type of the expression to the right of the -<- is the same as the type of the pattern to its -left. The bindings introduced by pattern guards scope over all the -remaining guard qualifiers, and over the right hand side of the equation. - - - -Just as with list comprehensions, boolean expressions can be freely mixed -with among the pattern guards. For example: - - - -f x | [y] <- x - , y > 3 - , Just z <- h y - = ... - - - -Haskell's current guards therefore emerge as a special case, in which the -qualifier list has just one element, a boolean expression. - - - - - Parallel List Comprehensions - list comprehensionsparallel - - parallel list comprehensions - - - Parallel list comprehensions are a natural extension to list - comprehensions. List comprehensions can be thought of as a nice - syntax for writing maps and filters. Parallel comprehensions - extend this to include the zipWith family. - - A parallel list comprehension has multiple independent - branches of qualifier lists, each separated by a `|' symbol. For - example, the following zips together two lists: - - - [ (x, y) | x <- xs | y <- ys ] - - - The behavior of parallel list comprehensions follows that of - zip, in that the resulting list will have the same length as the - shortest branch. - - We can define parallel list comprehensions by translation to - regular comprehensions. Here's the basic idea: - - Given a parallel comprehension of the form: - - - [ e | p1 <- e11, p2 <- e12, ... - | q1 <- e21, q2 <- e22, ... - ... - ] - - - This will be translated to: - - - [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...] - [(q1,q2) | q1 <- e21, q2 <- e22, ...] - ... - ] - - - where `zipN' is the appropriate zip for the given number of - branches. - - + - + Class method types @@ -654,9 +213,9 @@ class type variable (in this case a). With the GHC lifts this restriction. - + - + Multi-parameter type classes @@ -683,7 +242,7 @@ Thanks to him, and to many others who have offered very useful feedback. - + Types @@ -797,9 +356,9 @@ are perfectly OK This choice recovers principal types, a property that Haskell 1.4 does not have. - + - + Class declarations @@ -959,9 +518,9 @@ class like this: - + - + Instance declarations @@ -1224,11 +783,11 @@ with N. - + - + - + Implicit parameters @@ -1333,9 +892,9 @@ Easiest thing is to outlaw the offending types. - + - + Linear implicit parameters @@ -1427,7 +986,7 @@ are entirely distinct implicit parameters: you -Warnings +Warnings The monomorphism restriction is even more important than usual. @@ -1459,11 +1018,11 @@ parameters we have already lost beta reduction anyway, and Haskell programs without knowing their typing. - + - + - + Functional dependencies @@ -1476,11 +1035,11 @@ ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782. There should be more documentation, but there isn't (yet). Yell if you need it. - + - -Explicit universal quantification +<sect2 id="universal-quantification"> +<title>Arbitrary-rank polymorphism @@ -1554,7 +1113,7 @@ a type variable any more! - + Examples @@ -1686,9 +1245,9 @@ and bind to extract the polymorphic bind and return functions from the MonadT data structure, rather than using pattern matching. - + - + Type inference @@ -1732,10 +1291,10 @@ it is an argument of constructor T1 and that tells GHC all it needs to know. - + - + Implicit quantification @@ -1780,16 +1339,17 @@ but at least the rule is simple. If you want the latter type, you can write your for-alls explicitly. Indeed, doing so is strongly advised for rank-2 types. + - - -Type synonyms and hoisting +<sect2> +<title>Liberalised type synonyms -Type synonmys are like macros at the type level, and GHC is much more liberal -about them than Haskell 98. In particular: +Type synonmys are like macros at the type level, and +GHC does validity checking on types only after expanding type synonyms. +That means that GHC can be very much more liberal about type synonyms than Haskell 98: You can write a forall (including overloading) in a type synonym, thus: @@ -1814,11 +1374,56 @@ You can write an unboxed tuple in a type synonym: h x = (# x, x #) + + +You can apply a type synonym to a forall type: + + type Foo a = a -> a -> Bool + + f :: Foo (forall b. b->b) + +After epxanding 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 does validity checking on types after expanding type synonyms -so, for example, +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 #) @@ -1828,9 +1433,12 @@ this will be rejected: because GHC does not allow unboxed tuples on the left of a function arrow. + + +For-all hoisting -However, it is often convenient to use these sort of generalised synonyms at the right hand +It is often convenient to use generalised type synonyms at the right hand end of an arrow, thus: type Discard a = forall b. a -> b -> a @@ -1862,10 +1470,10 @@ valid way to write g's type signature: g :: Int -> Int -> forall b. b -> Int - + - + Existentially quantified data constructors @@ -1955,7 +1563,7 @@ that collection of packages in a uniform manner. You can express quite a bit of object-oriented-like programming this way. - + Why existential? @@ -1978,9 +1586,9 @@ But Haskell programmers can safely think of the ordinary adding a new existential quantification construct. - + - + Type classes @@ -2040,9 +1648,9 @@ Notice the way that the syntax fits smoothly with that used for universal quantification earlier. - + - + Restrictions @@ -2186,11 +1794,11 @@ declarations. Define your own instances! - + - + - + Scoped Type Variables @@ -2241,7 +1849,7 @@ are noted. So much for the basic idea. Here are the details. - + What a pattern type signature means A type variable brought into scope by a pattern type signature is simply @@ -2279,9 +1887,9 @@ For example, all of these are legal: w (x::a) = x -- a unifies with [b] - + - + Scope and implicit quantification @@ -2413,9 +2021,9 @@ scope over the methods defined in the where part. For exampl - + - + Result type signatures @@ -2456,9 +2064,9 @@ you want: Result type signatures are not yet implemented in Hugs. - + - + Where a pattern type signature can occur @@ -2570,10 +2178,10 @@ in f4's scope. + - - + Explicitly-kinded quantification @@ -2632,8 +2240,14 @@ The syntax is The parentheses are required. + + + + + + Assertions <indexterm><primary>Assertions</primary></indexterm> @@ -2714,6 +2328,189 @@ for the details. </sect1> +<!-- ====================== PATTERN GUARDS ======================= --> + +<sect1 id="pattern-guards"> +<title>Pattern guards + + +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.) + + + +Suppose we have an abstract data type of finite maps, with a +lookup operation: + + +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: + + + +clunky env var1 var2 | ok1 && ok2 = val1 + val2 +| otherwise = var1 + var2 +where + m1 = lookup env var1 + m2 = lookup env var2 + ok1 = maybeToBool m1 + ok2 = maybeToBool m2 + val1 = expectJust m1 + val2 = expectJust m2 + + + +The auxiliary functions are + + + +maybeToBool :: Maybe a -> Bool +maybeToBool (Just x) = True +maybeToBool Nothing = False + +expectJust :: Maybe a -> a +expectJust (Just x) = x +expectJust Nothing = error "Unexpected Nothing" + + + +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 +respectively. If either lookup fails, then clunky takes the +otherwise case and returns the sum of its arguments. + + + +This is certainly legal Haskell, but it is a tremendously verbose and +un-obvious way to achieve the desired effect. Arguably, a more direct way +to write clunky would be to use case expressions: + + + +clunky env var1 var1 = case lookup env var1 of + Nothing -> fail + Just val1 -> case lookup env var2 of + Nothing -> fail + Just val2 -> val1 + val2 +where + fail = val1 + val2 + + + +This is a bit shorter, but hardly better. Of course, we can rewrite any set +of pattern-matching, guarded equations as case expressions; that is +precisely what the compiler does when compiling equations! The reason that +Haskell provides guarded equations is because they allow us to write down +the cases we want to consider, one at a time, independently of each other. +This structure is hidden in the case version. Two of the right-hand sides +are really the same (fail), and the whole expression +tends to become more and more indented. + + + +Here is how I would write clunky: + + + +clunky env var1 var1 + | Just val1 <- lookup env var1 + , Just val2 <- lookup env var2 + = val1 + val2 +...other equations for clunky... + + + +The semantics should be clear enough. The qualifers are matched in order. +For a <- qualifier, which I call a pattern guard, the +right hand side is evaluated and matched against the pattern on the left. +If the match fails then the whole guard fails and the next equation is +tried. If it succeeds, then the appropriate binding takes place, and the +next qualifier is matched, in the augmented environment. Unlike list +comprehensions, however, the type of the expression to the right of the +<- is the same as the type of the pattern to its +left. The bindings introduced by pattern guards scope over all the +remaining guard qualifiers, and over the right hand side of the equation. + + + +Just as with list comprehensions, boolean expressions can be freely mixed +with among the pattern guards. For example: + + + +f x | [y] <- x + , y > 3 + , Just z <- h y + = ... + + + +Haskell's current guards therefore emerge as a special case, in which the +qualifier list has just one element, a boolean expression. + + + + + + + Parallel List Comprehensions + list comprehensionsparallel + + parallel list comprehensions + + + Parallel list comprehensions are a natural extension to list + comprehensions. List comprehensions can be thought of as a nice + syntax for writing maps and filters. Parallel comprehensions + extend this to include the zipWith family. + + A parallel list comprehension has multiple independent + branches of qualifier lists, each separated by a `|' symbol. For + example, the following zips together two lists: + + + [ (x, y) | x <- xs | y <- ys ] + + + The behavior of parallel list comprehensions follows that of + zip, in that the resulting list will have the same length as the + shortest branch. + + We can define parallel list comprehensions by translation to + regular comprehensions. Here's the basic idea: + + Given a parallel comprehension of the form: + + + [ e | p1 <- e11, p2 <- e12, ... + | q1 <- e21, q2 <- e22, ... + ... + ] + + + This will be translated to: + + + [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...] + [(q1,q2) | q1 <- e21, q2 <- e22, ...] + ... + ] + + + where `zipN' is the appropriate zip for the given number of + branches. + + + + + Pragmas @@ -2996,6 +2793,8 @@ GHC will print the specified message. + + Rewrite rules diff --git a/ghc/docs/users_guide/primitives.sgml b/ghc/docs/users_guide/primitives.sgml index 10f4323..a627b21 100644 --- a/ghc/docs/users_guide/primitives.sgml +++ b/ghc/docs/users_guide/primitives.sgml @@ -1107,6 +1107,101 @@ putMVar# :: SynchVar# s elt -> State# s -> State# s </sect2> +<sect2 id="glasgow-prim-arrays"> +<title>Primitive arrays, mutable and otherwise + + + +primitive arrays (Glasgow extension) +arrays, primitive (Glasgow extension) + + + +GHC knows about quite a few flavours of Large Swathes of Bytes. + + + +First, GHC distinguishes between primitive arrays of (boxed) Haskell +objects (type Array# obj) and primitive arrays of bytes (type +ByteArray#). + + + +Second, it distinguishes between… + + + +Immutable: + + +Arrays that do not change (as with “standard” Haskell arrays); you +can only read from them. Obviously, they do not need the care and +attention of the state-transformer monad. + + + + +Mutable: + + +Arrays that may be changed or “mutated.” All the operations on them +live within the state-transformer monad and the updates happen +in-place. + + + + +“Static” (in C land): + + +A C routine may pass an Addr# pointer back into Haskell land. There +are then primitive operations with which you may merrily grab values +over in C land, by indexing off the “static” pointer. + + + + +“Stable” pointers: + + +If, for some reason, you wish to hand a Haskell pointer (i.e., +not an unboxed value) to a C routine, you first make the +pointer “stable,” so that the garbage collector won't forget that it +exists. That is, GHC provides a safe way to pass Haskell pointers to +C. + + + +Please see for more details. + + + + +“Foreign objects”: + + +A “foreign object” is a safe way to pass an external object (a +C-allocated pointer, say) to Haskell and have Haskell do the Right +Thing when it no longer references the object. So, for example, C +could pass a large bitmap over to Haskell and say “please free this +memory when you're done with it.” + + + +Please see for more details. + + + + + + + +The libraries documentatation gives more details on all these +“primitive array” types and the operations on them. + + + +