back2roots/padua

home *** CD-ROM | disk | FTP | other *** search

/ back2roots/padua / padua.7z / padua / lang / gofer223.lha / doc / ch14 < prev next >

Wrap

Text File | 1992-11-10 | 74.8 KB | 2,113 lines

Introduction to Gofer 14. OVERLOADING IN GOFER 14. OVERLOADING IN GOFER One of the biggest differences between Gofer and most other programming languages (with the exception of Haskell) is the approach to overloading; enabling the definition and use of functions in which the meaning of a function symbol may depend on the types of its arguments. Like Haskell, overloading in Gofer is based around a system of type classes which allow overloaded functions to be grouped together into related groups of functions. Whilst the precise details of the approach to type classes used by Gofer are quite different to those of Haskell, both rely on the same basic ideas and use a similar syntax for defining and using type classes. It would therefore seem possible that experience gained with the overloading system in one language can readily by applied to the other. The differences embodied in the Gofer system of classes stem from my own, theoretically based investigations into `qualified types' some of which is detailed in references [8-12]. In my personal opinion, the Gofer system has some significant advantages over the Haskell approach (see [12] for details) and one of the principal motivations behind the implementation to Gofer was to provide a way of testing such claims. One fact which I believe has already been established using Gofer is that the use and implementation of overloaded functions need not have the significant effect on performance that was anticipated with early implementations of Haskell. This section outlines the system of type classes used in Gofer, indicating briefly how they can be used and how they are implemented. 14.1 Type classes and predicates -------------------------------- A type class can be thought of as a family of types (or more generally as a family of tuples of types) whose elements are called instances of the class. If C is the name of an n-parameter type class then an expression of the form C t1 t2 ... tn where t1, t2, ..., tn are type expressions is called a predicate and represents the assertion that the specified tuple of types is an instance of the class C. Given a polymorphic function (e.g. map::(a->b)->[a]->[b]), we are free to use the function at any type which can be obtained by substituting arbitrary types for each of the type variables in its type. In Gofer, a type expression may be qualified by one or more predicates which restrict the range of types at which a value can be used: e.g. a function of type C a => a -> a -> a can be treated as a function of type t -> t -> t for any instance t of the class C. The predicate C a in the type expression in the previous example is called the context of the type. Contexts may contain more than one predicate in which case the predicates involved must be separated by commas and the context enclosed in parentheses as in (C a, D b). The empty context is written () and any type expression t is equivalent to the qualified type () => t. For uniformity, a context with only one element may also be enclosed by parentheses. 61 Introduction to Gofer 14.1 Type classes and predicates For technical reasons, type synonyms are not currently permitted in predicates. This is consistent with the use of predicates in Haskell, but may be relaxed, at least in certain cases, in later versions of Gofer. 14.2 The type class Eq ---------------------- The type class Eq is a simple and useful example, whose instances are precisely those types whose elements can be tested for equality. The declaration of this class given in the standard prelude is as follows: class Eq a where (==), (/=) :: a -> a -> Bool x /= y = not (x == y) There are three parts in any class declaration. For this particular example we have: o The first line (called the `header') of the declaration introduces a name Eq for the class and indicates that it has a single parameter, represented by the type variable a. o The second line of the declaration (the `signature part') indicates that there are functions denoted by the operator symbols (==) and (/=) of type a -> a -> Bool for each instance a of class Eq. Using the notation introduced in the previous section, both of these operators have type: Eq a => a -> a -> Bool These functions are called the `members' (or `member functions') of the class. [This terminology, taken from Haskell, is rather unfortunate; thinking of a type class as a set of types, the elements of the class are called `instances', whilst the `members' of the class correspond more closely to the instance variables that are used in the terminology of object-oriented programming.] The intention is that the (==) function will be used to implement an equality test for each instance of the class, with the (/=) operator providing the corresponding inequality function. The ability to include related groups of functions within a single type class in this way is a useful tool in program design. o The third line of the class declaration (the `default definitions') provides a default definition of the (/=) operator in terms of the (==) operator. Thus it is only necessary to give a definition for the (==) operator in order to define all of the member functions for the class Eq. It is possible to override default member definitions by giving an alternative definition as appropriate for specific instances of the class. 62 Introduction to Gofer 14.2.1 Implicit overloading 14.2.1 Implicit overloading --------------------------- Member functions are clearly marked as overloaded functions by their definition as part of a class declaration, but this is not the only way in which overloaded functions occur in Gofer; the restriction to particular instances of a type class is also carried over into the type of any function defined either directly or indirectly in terms of the member functions of that class. For example, the types inferred for the following two functions: x `elem` xs = any (x==) xs xs `subset` ys = all (`elem` ys) xs are: elem :: Eq a => a -> [a] -> Bool subset :: Eq a => [a] -> [a] -> Bool [ASIDE: On the other hand, if none of the functions used in a particular expression or definition are overloaded then there will not be any overloading in the corresponding value. Gofer does not support the concept of implicit overloading used in some languages where a value of a particular type might automatically be coerced to a value of some supertype. An example of this would be the automatic translation of a badly typed expression "1.0 == 1" to a well-typed expression of the form "1.0 == float 1" for some (potentially overloaded) coercion function "float" mapping numeric values to elements of type Float.] Note also that the types appearing in the context of a qualified type reflect the types at which overloaded functions are used. Thus: f x ys = [x] == ys has type Eq [a] => a -> [a] -> Bool, and not Eq a => a -> [a] -> Bool, which is the type that would be assigned to "f" in a Haskell system. 14.2.2 Instances of class Eq ---------------------------- Instances of a type class are defined using declarations similar to those used to define the corresponding type class. The following examples, taken from the standard prelude, give the definitions for a number of simple instances of the class Eq: instance Eq Int where (==) = primEqInt instance Eq Bool where True == True = True False == False = True _ == _ = False instance Eq Char where c == d = ord c == ord d instance (Eq a, Eq b) => Eq (a,b) where (x,y) == (u,v) = x==u && y==v 63 Introduction to Gofer 14.2.2 Instances of class Eq instance Eq a => Eq [a] where [] == [] = True [] == (y:ys) = False (x:xs) == [] = False (x:xs) == (y:ys) = x==y && xs==ys The interpretation of these declarations is as follows: o The first declaration makes Int an instance of class Eq. The function "primEqInt" is a primitive Gofer function which tests the equality of two integer values and has type Int -> Int -> Bool which tests the equality of two integer values. o The second declaration makes Bool an instance of class Eq with a simple definition involving pattern matching. o The third declaration makes Char an instance of class Eq. This definition indicates that a pair of characters are equal if they have the same ASCII value, which is obtained using the "ord" function. Note that the two occurrences of the symbol (==) in the equation: c == d = ord c == ord d have different meanings; the first denotes equality between characters (elements of type Char), whilst the second denotes equality between integers (elements of type Int). o The fourth declaration provides an equality operation on pairs. Given two elements (x,y) and (u,v) of type (a,b) for some a, b, it must be possible to check that both x==u and y==v before we can be sure that the two pairs are indeed equal. In other words, both a and b must also be instances of Eq in order to make (a,b) an instance of Eq. This requirement is described by the first line in the instance declaration using the expression: (Eq a, Eq b) => Eq (a,b) o The fifth declaration makes [a] an instance of Eq, whenever a is itself an instance of Eq in a similar way to the previous example. The context Eq a is used in the last equation in the declaration: (x:xs) == (y:ys) = x==y && xs==ys which contains three occurrences of the (==) operator; the first and third are used to compare lists of type [a], whilst the second is used to compare elements of type a, using the instance Eq a. Combining these five declarations, we obtain definitions for (==) on an infinite family of types including Int, Char, Bool, (Int,Bool), (Char,Int), [Char], (Bool,[Int]), [(Bool,Int)], etc...: ? 2 == 3 -- using Eq Int False (2 reductions, 10 cells) 64 Introduction to Gofer 14.2.2 Instances of class Eq ? (["Hello"],3) == (["Hello"],3) -- using Eq ([[Char]],Int) True (31 reductions, 65 cells) ? On the other hand, any attempt to use (==) to compare elements of some type not covered by a suitable instance declaration will result in an error. For example, the standard prelude does not define the equality operation on triples of values: ? (1,2,3) == (1,2,3) ERROR: Cannot derive instance in expression *** Expression : (==) d125 (1,2,3) (1,2,3) *** Required instance : Eq (Int,Int,Int) ? This can be solved by including an instance declaration of the form into a file of definitions loaded into Gofer: instance (Eq a, Eq b, Eq c) => Eq (a,b,c) where (x,y,z) == (u,v,w) = x==u && y==v && z==w Giving: ? (1,2,3) == (1,2,3) True (6 reductions, 20 cells) ? In general, an instance declaration has the form: instance context => predicate where definitions of member functions The context part of the declaration gives a list of predicates which must be satisfied for the predicate on the right hand side of the `=>' sign to be valid. Constant predicates (i.e. predicates not involving any type variables) required by an instance declaration (such as the predicate Eq Int required by the third declaration) need not be included in the context. If the resulting context is empty (as in the first three declarations above) then it may be omitted, together with the corresponding `=>' symbol. 14.2.3 Testing equality of represented values --------------------------------------------- Instances of Eq can also be defined for other types, including user-defined datatypes, and unlike the instances described above, the definition of (==) need not be used to determine whether the values being compared have the same structure; it is often more useful to check that they represent the same value. As an example, suppose that we introduce a type constructor Set for representing sets of values, using a list to store the values held in the set: data Set a = Set [a] 65 Introduction to Gofer 14.2.3 Testing equality of represented values As usual, we say that two sets are equal if they have the same members, ignoring any repetitions or differences in the ordering of the elements in the lists representing the sets. This is achieved using the following instance declaration: instance Eq a => Eq (Set a) where Set xs == Set ys = xs `subset` ys && ys `subset` xs where xs `subset` ys = all (`elem` ys) xs A couple of examples illustrate the use of this definition: ? Set [1,2,3] == Set [3,4,1] False (49 reductions, 89 cells) ? Set [1,2,3] == Set [1,2,2,2,1,3] True (157 reductions, 240 cells) ? 14.2.4 Instance declarations without members -------------------------------------------- It is possible to give an instance declaration without specifying any definitions for the member functions of the class. For example: instance Eq () In this case, the definition of (==) for the instance Eq () is left completely undefined, and hence so is the definition of (/=), which is defined in terms of (==): ? () == () {undefined_member (==)} (3 reductions, 34 cells) ? () /= () {undefined_member (==)} (4 reductions, 36 cells) ? 14.2.5 Equality on function types --------------------------------- If an expression requires an instance of a class which cannot be obtained using the rules in the given instance declarations, then an error message will be produced when the expression is type-checked. For example, in general there is no sensible way to determine when a pair of functions are equal, and the standard prelude does not include a definition for an instance of the form Eq (a -> b) for any types a and b: ? (1==) == (\x->1==x) ERROR: Cannot derive instance in expression *** Expression : (==) d148 ((==) {dict} 1) (\x->(==) {dict} 1 x) *** Required instance : Eq (Int -> Bool) ? 66 Introduction to Gofer 14.2.5 Equality on function types If for some reason, you would prefer this kind of error to produce an error message when an expression is evaluated, rather than when it is type-checked, you can use an instance declaration to specify the required behaviour. For example: instance Eq (a -> b) where (==) = error "Equality not defined between functions" Evaluating the previous expression once this instance declaration has been included now produces the following result: ? (1==) == (\x->1==x) {error "Equality not defined between functions"} (42 reductions, 173 cells) ? A limited form of equality can be defined for functions of type (a->b) if a has only finitely many elements, such as the boolean type Bool: instance Eq a => Eq (Bool -> a) where f == g = f False == g False && f True == g True [ASIDE: This instance declaration would not be accepted in a Haskell program which insists that the predicate on the right of the `=>' symbol contains precisely one type constructor symbol.] Using this instance declaration once for each argument, we can now test two functions taking boolean arguments for equality (assuming of course that their result type is also an instance of Eq). ? (&&) == (||) False (9 reductions, 21 cells) ? not == (\x -> if x then False else True) True (8 reductions, 16 cells) ? (&&) == (\x y-> if x then y else False) True (16 reductions, 30 cells) ? 14.2.6 Non-overlapping instances -------------------------------- Other instance declarations for types of the form a -> b can be used at the same time, so long as no pair of declarations overlap. For example, adding the following instance declaration instance Eq a => Eq (() -> a) where f == g = f () == g () enables us to evaluate expressions such as: ? (\()->"Hello") == const "Hello" True (30 reductions, 55 cells) ? 67 Introduction to Gofer 14.2.6 Non-overlapping instances If however, we try and use instance declarations for types of the form (a -> b) and (Bool -> a) at the same time, then Gofer produces an error message similar to the following: ERROR "file" (line 37): Overlapping instances for class "Eq" *** This instance : Eq (a -> b) *** Overlaps with : Eq (Bool -> a) *** Common instance : Eq (Bool -> a) ? indicating that, given the task of testing two values of type (Bool->a) for equality, there are (at least) two definitions of (==) that could be used, with potentially different results being obtained in each case. Here is a further example of the use of non-overlapping instances of a class to define a function "cat" (inspired by the unix (tm) command of the same name) which uses the I/O facilities of Gofer to print the contents of one or more files on the terminal: class Cat a where cat :: a -> Dialogue instance Cat [Char] where cat n = showFile n done instance Cat [[Char]] where cat = foldr showFile done showFile name cont = readFile name abort (\s->appendChan stdout s abort cont) Given these declarations, an expression of the form: cat "file" can be used to display the contents of the named file, whilst a list of files can be printed one after the other using an expression of the form: cat ["file1", "file2", ..., "filen"]. 14.3 Dictionaries ----------------- In order to understand some of the messages produced by Gofer, as well as some of the more subtle problems associated with overloaded functions, it is useful to have a rough idea of the way in which overloaded functions are implemented. The basic idea is that a function with a qualified type context => type where context is a non-empty list of predicates is implemented by a function which takes an extra argument for each predicate in the context. When the function is used, each of these parameters is filled by a `dictionary' which gives the values of each of the member functions in the appropriate class. None of these extra parameters is entered by the programmer. Instead, they are inserted automatically during type-checking. For the class Eq, each dictionary has at least two elements containing 68 Introduction to Gofer 14.3 Dictionaries definitions for each of the functions (==) and (/=). A dictionary for an instance of Eq can be depicted by a diagram of the form: +--------+--------+--------- | | | | (==) | (/=) | ..... | | | +--------+--------+--------- In order to produce useful error messages and indicate the way in which dictionary expressions are being used, Gofer uses a number of special notations for printing expressions involving dictionaries: (#1 d) selects the first element of the dictionary d (#2 d) selects the second element of the dictionary d (#n d) selects the nth element of the dictionary d (note that (#0 d) is equivalent to the dictionary d). {dict} denotes a specific dictionary (the contents are not displayed). dnnn a dictionary variable representing an unknown dictionary is printed as a lower case letter `d' followed by an integer; e.g. d231. Note that, whilst these notations are used in output produced by Gofer and in the following explanations, they cannot be entered directly into Gofer expressions or programs -- even if you use a variable such as "d1" in an expression, Gofer will not confuse this with a dictionary variable with the same name (although Gofer might confuse you by using the same name in two different contexts!). Using these notations, the member functions (==) and (/=) of the class Eq behave as if they were defined by the expressions: (==) d1 = (#1 d1) (/=) d1 = (#2 d1) To understand how these definitions work, we need to take a look at a specific dictionary. Following the original instance declaration used for Eq Int, the corresponding dictionary is: d :: Eq Int +------------+------------+ | | | | primEqInt | defNeq d | | | | +------------+------------+ Note that the dictionary variable d is used as a name for the dictionary in this diagram, indicating how values within a dictionary can include references to the same dictionary. [ASIDE: It turns out that predicates play a very similar role for 69 Introduction to Gofer 14.3 Dictionaries dictionaries as types play for normal values. This motivates our use of the notation d :: Eq Int to indicate that d is a dictionary for the instance Eq Int. One difference between these, particularly important for theoretical work, is that dictionary values are uniquely determined by predicates; if d1::p and d2::p for some predicate p, then d1 = d2.] The value held in the first element of the dictionary is the primitive equality function on integers, "primEqInt". The following diagram shows how the dictionary is used to evaluate the expression "2 == 3". Note that this expression will first be translated to "(==) d 2 3" by the type checker. The evaluation then proceeds as follows: (==) d 2 3 ==> (#1 d) 2 3 ==> primEqInt 2 3 ==> False The second element of the dictionary is a little more interesting because it uses the default definition for (/=) given in the original class definition which, after translation, is represented by the function "defNeq" defined by: defNeq d1 x y = not ((==) d1 x y) Notice the way in which the extra dictionary parameter is used to obtain the appropriate overloading. For example, evaluation of the expression "2 /= 3", which becomes "(/=) d 2 3" after translation, proceeds as follows: (/=) d 2 3 ==> (#2 d) 2 3 ==> defNeq d 2 3 ==> not ((==) d 2 3) ==> not ((#1 d) 2 3) ==> not (primEqInt 2 3) ==> not False ==> True [Clearly there is some scope for optimisation here; whilst the actual reduction sequences used by Gofer are equivalent to those illustrated above, the precise details are a little different.] If an instance is obtained from an instance declaration with a non-empty context, then the basic two element dictionary used in the examples above is extended with an extra dictionary value for each predicate in the context. As an example, the diagram below shows the dictionaries that will be created from the instance definitions in section 14.2.2 for the instance Eq (Int, [Int]). The functions "eqPair" and "eqList" which are used in these dictionaries are obtained from the definitions of (==) given in the instance declarations for Eq (a,b) and Eq [a] respectively: eqPair d (x,y) (u,v) = (==) (#3 d) x u && (==) (#4 d) y v eqList d [] [] = True eqList d [] (y:ys) = False eqList d (x:xs) [] = False eqList d (x:xs) (y:ys) = (==) (#3 d) x y && (==) d xs ys 70 Introduction to Gofer 14.3 Dictionaries The dictionary structure for Eq (Int, [Int]) is as follows. Note that the Gofer system ensures that there is at most one dictionary for a particular instance of a class, and that the dictionary d1 :: Eq Int in this system is automatically shared between d2 and d3: d3 :: Eq (Int, [Int]) +------------+------------+------------+------------+ | | | | | | eqPair d3 | defNeq d3 | d1::Eq Int |d2::Eq [Int]| | | | | | +------------+------------+-----+------+-----+------+ | | +--------------+ | | | | d2 :: Eq [Int] V | +------------+------------+------------+ | | | | | | | eqList d2 | defNeq d2 | d1::Eq Int | | | | | | | +------------+------------+-----+------+ | | d1 :: Eq Int V | +------------+------------+ | | | | | | primEqInt | defNeq d1 |<--------------------------+ | | | +------------+------------+ Once again, it may be useful to see how these definitions are used to evaluate the expression "(2,[1]) == (2,[1,3])" which, after translation, becomes "(==) d3 (2,[1]) (2,[1,3])": (==) d3 (2,[1]) (2,[1,3]) ==> (#1 d3) (2,[1]) (2,[1,3]) ==> eqPair d3 (2,[1]) (2,[1,3]) ==> (==) (#3 d3) 2 2 && (==) (#4 d3) [1] [1,3] ==> (==) d1 2 2 && (==) (#4 d3) [1] [1,3] ==> (#1 d1) 2 2 && (==) (#4 d3) [1] [1,3] ==> primEqInt 2 2 && (==) (#4 d3) [1] [1,3] ==> True && (==) (#4 d3) [1] [1,3] ==> (==) (#4 d3) [1] [1,3] ==> (==) d2 [1] [1,3] ==> (#1 d2) [1] [1,3] ==> eqList d2 [1] [1,3] ==> (==) (#3 d2) 1 1 && (==) d2 [] [3] ==> (==) d1 1 1 && (==) d2 [] [3] ==> (#1 d1) 1 1 && (==) d2 [] [3] ==> primEqInt 1 1 && (==) d2 [] [3] ==> True && (==) d2 [] [3] ==> (==) d2 [] [3] ==> False 71 Introduction to Gofer 14.3.1 Superclasses 14.3.1 Superclasses ------------------- In general, a type class declaration has the form: class context => Class a1 ... an where type declarations for member functions default definitions of member functions where Class is the name of the new type class which takes n arguments, represented by distinct type variables a1, ..., an. As in the case of instance declarations, the context that appears on the left hand side of the `=>' symbol specifies a list of predicates that must be satisfied in order to construct any instance of "Class". The predicates in the context part of a class declaration are called the superclasses of Class. This terminology is taken from Haskell where all classes have a single parameter and each of the predicates in the context part of a class declaration has the form C a1; in this situation, any instance of Class must also be an instance of each class C named in the context. In other words, each such C contains a superset of the types in Class. As an example of a class declaration with a non-empty context, consider the following declaration from the standard prelude which introduces a class Ord whose instances are types with both strict (<), (>) and non-strict (<=), (>=) versions of an ordering defined on their elements: class Eq a => Ord a where (<), (<=), (>), (>=) :: a -> a -> Bool max, min :: a -> a -> a x < y = x <= y && x /= y x >= y = y <= x x > y = y < x max x y | x >= y = x | y >= x = y min x y | x <= y = x | y <= x = y Notice that this definition provides default definitions for all of the member functions except (<=), so that in general only this single function needs to be defined to construct an instance of class Ord. There are two reasons for defining Eq as a superclass of Ord: o The default definition for (<) relies on the use of (/=) taken from class Eq. In order to guarantee that this is always valid we must ensure that every instance of Ord must also be an instance of Eq. o Given the definition of a non-strict ordering (<=) on the elements of a type, it is always possible to construct a definition for the (==) operator (and hence for (/=)) using the equation: 72 Introduction to Gofer 14.3.1 Superclasses x==y = x<=y && y<=x There will therefore be no loss in generality by requiring Eq to be a superclass of Ord, and conversely, no difficulty in defining an instance of Eq to accompany any instance of Ord for which an instance of Eq has not already be provided. As an example, the following definitions provide an alternative way to implement the equality operation on elements of the Set datatype described in section 14.2.3, in terms of the subset ordering defined in class Ord: instance Ord (Set a) => Eq (Set a) where x == y = x <= y && y <= x instance Eq a => Ord (Set a) where Set xs <= Set ys = all (`elem` ys) xs This definition is in fact no less efficient or effective than the original version. Dictionaries for superclasses are dealt with in much the same way as the instance specific dictionaries described above. For example, the general layout of a dictionary for an instance of Ord is illustrated in the following diagram: +--------+--------+--------+--------+--------+--------+--------+----- | | | | | | | | | (<) | (<=) | (>) | (>=) | max | min | Eq a | ..... | | | | | | | | +--------+--------+--------+--------+--------+--------+--------+----- Note the use of the seventh element of this dictionary which points to the dictionary for the appropriate instance of Eq. This is used in the translation of the default definition for (<) which is equivalent to: defLessThan d x y = (<=) d x y && (/=) (#7 d) x y 14.3.2 Combining classes ------------------------ In general, a dictionary is made up of three separate parts: +-------------------+-------------------+-------------------+ | Implementation | Superclass | Instance specific | | of class members | Dictionaries | Dictionaries | | | | | +-------------------+-------------------+-------------------+ Each of these may be empty. We have already seen examples in which there are no superclass dictionaries (e.g. instances of Eq) and in which there are no instance specific dictionaries (e.g. Eq Int). Classes with no member functions (corresponding to dictionaries with no member functions) are sometimes useful as a convenient abbreviation for a list of predicates. For example: 73 Introduction to Gofer 14.3.2 Combining classes class C a where cee :: a -> a class D a where dee :: a -> a class (C a, D a) => CandD a makes CandD a an abbreviation for the context (C a, D a). Thinking of single parameter type classes as sets of types, the type class CandD corresponds to the intersection of classes C and D. Just as the type inferred for a particular function definition or expression do not involve type synonyms unless explicit type signatures are used, the Gofer type system will not use a single predicate of the form CandD a instead of the two predicates C a and D a unless explicit signatures are used: ? :t dee . cee \d129 d130 -> dee d130 . cee d129 :: (C a, D a) => a -> a ? :t dee . cee :: CandD a => a -> a \d129 -> dee (#2 d129) . cee (#1 d129) :: CandD a => a -> a ? In Haskell, all instances of a class such as CandD must be have explicit declarations, in addition to the corresponding declarations for instances for C and D. This problem can be avoided by using the more general form of instance declaration permitted in Gofer; a single instance declaration: instance CandD a is all that is required to ensure that any instance of CandD can be obtained, so long as corresponding instances for C and D can be found. 14.3.3 Simplified contexts -------------------------- Consider the function defined by the following equation: eg1 x = [x] == [x] || x == x This definition does not restrict the type of x in any way except that, if x :: a, then there must be instances Eq [a] and Eq a which are used for the two occurrences of the (==) operator in the equation. We might therefore expect the type of eg1 to be: (Eq [a], Eq a) => a -> Bool with translation: eg1 d1 d2 x = (==) d1 [x] [x] || (==) d2 x x However, as can be seen from the case where a=Int illustrated in section 14.3, given d1::Eq [a] we can always find a dictionary for Eq a by taking the third element of d1 i.e. (#3 d1)::Eq a. Since it is more efficient to select an element from a dictionary than to complicate both type and translation with extra parameters, the type assigned to "eg1" by default is: 74 Introduction to Gofer 14.3.3 Simplified contexts Eq [a] => a -> Bool with translation: eg1 d1 x = (==) d1 [x] [x] || (==) (#3 d1) x x In general, given a set of predicates corresponding to the instances required by an expression, Gofer will always attempt to find the smallest possible subset of these predicates such that all of the required dictionaries can still be obtained, whilst minimising the number of dictionary parameters that are used. The original type and translation for eg1 given above can be produced by including an explicit type signature in the file containing the definition of eg1: eg1 :: (Eq [a], Eq a) => a -> Bool eg1 x = [x] == [x] || x == x But even with this definition, Gofer will still always try to minimise the number of dictionaries used in any particular expression: ? :t eg1 \d153 -> eg1 d153 (#3 d153) :: Eq [a] => a -> Bool ? As another example, consider the expression "(\x y-> x==x || y==y)". The type and translation assigned to this term can be found directly using Gofer: ? :t (\x y-> x==x || y==y) \d121 d122 x y -> (==) d122 x x || (==) d121 y y :: (Eq b, Eq a) => a -> b -> Bool ? Note that the translation has two dictionary parameters d121 and d122 corresponding to the two predicates Eq a and Eq b respectively. Since both of these dictionaries can be obtained from a dictionary for the predicate Eq (a,b), we can use an explicit type signature to produce a translation which needs only one dictionary parameter: ? :t (\x y-> x==x || y==y) :: Eq (a,b) => a -> b -> Bool \d121 x y -> (==) (#3 d121) x x || (==) (#4 d121) y y :: Eq (a,b) => a -> b -> Bool ? 75 Introduction to Gofer 14.4 Other issues 14.4 Other issues ----------------- 14.4.1 Unresolved overloading ----------------------------- Consider the use of the (==) operator in the following three situations: o In the expression "2 == 3", it is clear that the appropriate value for the equality operator in this case is primIntEq as defined by the instance declaration for Eq Int. The expression can therefore be translated to "primEqInt 2 3". o In the function definition "f x = x==x", we cannot completely determine the appropriate value for (==) because it depends on the type assigned to the variable "x", which may itself vary with different uses of the function "f". It is however possible to add an extra parameter to the definition, giving "f d x = (==) d x x" and taking the type of "f" to be Eq a => a -> Bool. In this way, the problem of finding the appropriate definition for the (==) operator is deferred until the function is actually used. o In the expression "[]==[]", the appropriate value for (==) must be obtained from the dictionary for some instance of the form Eq [a], but there is not sufficient information in the expression to determine what the value of the type variable a should be. Looking back to the instance declaration for Eq [a], we find that the definition of (==) depends on the value of the dictionary for the instance Eq a. In this particular case, it is clear that the expression will always evaluate to True, regardless of the value of this dictionary. Unfortunately, the only way that this can be detected is by evaluating the expression to see if the calculation can be completed without reference to the dictionary value (see the comments in the aside at the end of this section). Attempting to evaluate this expression in Gofer will therefore result in an error message indicating that the expression does not contain sufficient information to resolve the use of overloading in the expression: ? [] == [] ERROR: Unresolved overloading *** type : Eq [a] => Bool *** translation : \d129 -> (==) d129 [] [] ? Note that the expression has been converted into a lambda expression using the dictionary variable d129 to represent the dictionary for the unknown instance Eq [a]. One simple way to resolve the overloading in an expression of this kind is to use an explicit type signature. For example, if we specify that the second empty list is an empty list of type [Int]: 76 Introduction to Gofer 14.4.1 Unresolved overloading ? [] == ([]::[Int]) True (2 reductions, 9 cells) ? The same problem occurs in Haskell, where it is described using the idea of an `ambiguous type' -- i.e. a type expression of the form context => type where one or more of the type variables appearing in the given context do not appear in the remaining part of the type expression. Further examples of unresolved overloading occur with other classes. As an example consider the class Reader defined by: class Reader a where parse :: String -> a unparse :: a -> String whose member functions provide methods for obtaining the string representation of an element of an instance type, and for converting such representations back into the original values (The standard Haskell Text class contains similar functions). Now consider the expression "parse . unparse" which maps values from some instance of Reader to values of another instance via an intermediate string representation. ? parse . unparse ERROR: Unresolved overloading *** type : (Reader a, Reader b) => a -> b *** translation : \d129 d130 -> parse d130 . unparse d129 ? One of the first things that might surprise the reader here is that the value produced by "parse . unparse" does not have to be of the same type as the argument; for example, we would not usually expect to have any sensible interpretation for a floating point number obtained from the string representation of a boolean value! This can be fixed by using an explicit type declaration, although the expression still produces unresolved overloading: ? (parse . unparse) :: Reader a => a -> a ERROR: Unresolved overloading *** type : Reader a => a -> a *** translation : \d130 -> parse d130 . unparse d130 ? Notice however that the type of this expression is not ambiguous so that the unresolved overloading in this example can be eliminated when the function is actually used: ? ((parse . unparse) :: Reader a => a -> a) 'a' 'a' (4 reductions, 11 cells) ? 77 Introduction to Gofer 14.4.1 Unresolved overloading A more serious problem occurs with the expression "unparse . parse" which maps string values to string values via some intermediate type. Clearly this will lead to a problem with unresolved overloading: ? unparse . parse ERROR: Unresolved overloading *** type : Reader a => String -> String *** translation : \d130 -> unparse d130 . parse (#0 d130) ? Notice that the type obtained in this case is ambiguous; the type variable a which appears in the predicate Reader a does not appear in the type String -> String. There are a number of ways of resolving this kind of ambiguity: o Using an explicitly typed expression: Assuming for example that Char is an instance of Reader, we can write: ? unparse . (parse :: String -> Char) v113 {dict} . v112 {dict} (5 reductions, 42 cells) ? without any ambiguity. If such type signatures are used in a number of places, it might be better to define an auxiliary function and use that instead: charParse :: String -> Char charParse = parse ? unparse . charParse v113 {dict} . charParse (4 reductions, 37 cells) ? In such situations, it is perhaps worth asking if overloaded functions are in fact the most appropriate solution for the problem in hand! o Using an extra dummy parameter in a function definition. In a definition such as: f = unparse . parse we can introduce an additional dummy parameter `x' which is not used except to determine the type of the result produced by parse in f: f x = unparse . (parse `asTypeOf` (\""->x)) where the standard prelude operator `asTypeOf` defined by: asTypeOf :: a -> a -> a x `asTypeOf` _ = x is used to ensure that the type of parse in the definition of f is 78 Introduction to Gofer 14.4.1 Unresolved overloading the same as that of the function (\""->x) -- in other words, the type must be String -> a where a is the type of the variable x. The resulting type for f is: f :: Reader a => a -> String -> String Notice how the addition of the dummy parameter has been used to eliminate the ambiguity present in the original type. This kind of `coding trick' is rather messy and is not recommended for anything but the simplest examples. [ASIDE: The idea of evaluating an expression with an ambiguous type to see if it does actually need the unspecified dictionaries could have been implemented quite rather easily in Gofer using an otherwise unused datatype Unresolved and generating instance declarations such as: instance Eq Unresolved where (==) = error "unresolved overloading for (==)" (/=) = error "unresolved overloading for (/=)" for each class. Given a particular expression, we can then use the type Unused in place of any ambiguous type variables in its type. The evaluation of the expression could then be attempted, either completing successfully if the dictionaries are not required, but otherwise resulting in a run-time error. This approach is not used in Gofer; instead, the programmer is notified of any unresolved polymorphism when the program is type checked, avoiding the possibility that a program might contain an undetected ambiguity.] 14.4.2 `Recursive' dictionaries ------------------------------- Unlike Haskell, there are no restrictions on the form of the predicates that may appear in the context part of a Gofer class or instance declaration. This has a number of potentially useful applications because it enables the Gofer programs to use mutually `recursive' systems of dictionaries. One example of this is the ability to implement a large family of related functions using a group of classes instead of having to use a single class. The following example illustrates the technique with an alternative definition for the class Eq in which the (==) and (/=) operators are placed in different classes: class Neq a => Eq a where (==) :: a -> a -> Bool class Eq a => Neq a where (/=) :: a -> a -> Bool x/=y = not (x == y) [ASIDE: These declarations clash with those in the standard prelude and hence cannot actually be used in Gofer unless a modified version of the 79 Introduction to Gofer 14.4.2 `Recursive' dictionaries standard prelude is used instead.] If we then give instance declarations: instance Eq Int where (==) = primEqInt instance Neq Int and try to evaluate the expression "2==3" then the following system of dictionaries will be generated: d1 :: Eq Int d2 :: Neq Int +-----------+-----------+ +-----------+-----------+ | | | | | | +-->| primEqInt |d2::Neq Int+----->| defNeq d2 |d1::Eq Int +---+ | | | | | | | | | +-----------+-----------+ +-----------+-----------+ | | | +------------------------------<-------------------------------+ where the function "defNeq" is derived from the default definition in the class Neq and is equivalent to: defNeq d x y = not ((==) (#2 d) x y) Incidentally, if the instance declaration for Neq Int above had been replaced by: instance Neq a Then the effect of these declarations would be similar to the standard definition of the class Eq, except that it would not be possible to override the default definition for (/=). In other words, this approach would give the same effect as defining (/=) as a top-level function rather than a member function in the class Eq: class Eq a where (==) :: a -> a -> Bool (/=) :: Eq a => a -> a -> Bool x /= y = not (x == y) There are other situations in which recursive dictionaries of the kind described above can be used. A further example is given in the following section. Unfortunately, the lack of restrictions on the form of class and instance declarations can also lead to problems in some (mostly pathological) cases. As an example, consider the class: class Bad [a] => Bad a where bad :: a -> a Without defining any instances of Bad, it is not possible to construct any dictionaries for instances of Bad: ? bad 2 ERROR: Cannot derive instance in expression *** Expression : bad d126 2 *** Required instance : Bad Int ? 80 Introduction to Gofer 14.4.2 `Recursive' dictionaries If however we add the instance declarations: instance Bad Int where bad = id instance Bad [a] where bad = id then any attempt to construct a dictionary for Bad Int will also require a dictionary for the superclass Bad [Int] and then for the superclass of that instance Bad [[Int]] etc... Since Gofer has only a finite amount of space for storing dictionaries, this process will eventually terminate when that space has been used up: ? bad 2 ERROR: Dictionary storage space exhausted ? [ASIDE: depending on the configuration of your particular version of Gofer and on the nature of the class and instance declarations that are involved, an alternative error message "ERROR: Too many type variables in type checker" may be produced instead of the message shown above.] From a practical point of view, this problem is unlikely to cause too many real difficulties: o Class declarations involving predicates such as those in the declaration of Bad are unlikely to be used in realistic programs. o All dictionaries are constructed before evaluation begins. This process is guaranteed to terminate because each new dictionary that is created uses up part of the space used to hold Gofer dictionaries. The construction process will either terminate successfully once complete, or be aborted as soon as all of the dictionary space has been used. It remains to see what impact (if any) this has on realistic programs, and if later versions of Gofer should be modified to impose some syntactic restrictions (as in Haskell) or perhaps some form of static checking of the contexts appearing in class and instance declarations. 14.4.3 Classes with multiple parameters --------------------------------------- Gofer is the first language to support the use of type classes with multiple parameters. This again is an experimental feature of the language, intended to make it possible to explore the claims from a number of researchers about the use of such classes. Initial experiments suggest that multiple parameter type classes are likely to lead to large numbers of problems with unresolved overloading. Ultimately, this may mean that such classes are only of practical use in explicitly typed languages, or alternatively that a more powerful and general defaulting mechanism (similar to that used in Haskell with numeric classes) is required to support user controlled overloading resolution. The following declaration introduces a class Iso whose elements are pairs of isomorphic types: 81 Introduction to Gofer 14.4.3 Classes with multiple parameters class Iso b a => Iso a b where iso :: a -> b The single member function "iso" represents the isomorphism mapping elements of type a to corresponding elements of type b. Note the `superclass' context in this declaration which formalises the idea that if a is isomorphic to b then b is also isomorphic to a. The class Iso therefore provides further examples of the recursive dictionaries described in the previous section. The fact that any type is isomorphic to itself can be described by the following instance declaration: instance Iso a a where iso x = x For example, the dictionary structure created in order to evaluate the expression "iso 2 = 3" is: d :: Iso Int Int +--------------+--------------+ | | | +-->| id |d::Iso Int Int+--+ | | | | | | +--------------+--------------+ | | | +------------------<-----------------+ ? iso 2 == 3 False (4 reductions, 11 cells) ? Our first taste of the problems to come occurs when we try to evaluate the expression "iso 2 == iso 3": ? iso 2 == iso 3 ERROR: Unresolved overloading *** type : (Eq a, Iso Int a) => Bool *** translation : \d130 d132 -> (==) d130 (iso d132 2) (iso d132 3) ? In this case, the "iso" function is used to map the integers 2 and 3 to elements of some type a, isomorphic to Int, and the values produced are the compared using (==) at the instance Eq a; there is no way of discovering what the value of a should be without using an explicit type signature. Further instances can be defined. The following two declarations are needed to describe the (approximate) isomorphism between lists of pairs and pairs of lists: instance Iso [(a,b)] ([a],[b]) where iso xs = (map fst xs, map snd xs) instance Iso ([a],[b]) [(a,b)] where iso (xs,ys) = zip xs ys 82 Introduction to Gofer 14.4.3 Classes with multiple parameters Unfortunately, even apparently straightforward examples give problems with unresolved overloading, forcing the use of explicit type declarations: ? iso [(1,2),(3,4)] ERROR: Unresolved overloading *** type : Iso [(Int,Int)] a => a *** translation : \d126 -> iso d126 [(1,2),(3,4)] ? (iso [(1,2),(3,4)]) :: ([Int],[Int]) ([1, 3],[2, 4]) (22 reductions, 64 cells) ? A second example of a multiple parameter type class is defined as follows: class Ord a => Collects a b where emptyCollection :: b addToCollection :: a -> b -> b listCollection :: b -> [a] The basic intuition is that the predicate Collects a b indicates that elements of type b can be used to represent collections of elements of type a. A number of people have suggested using type classes in this way to provide features similar to the (similarly named, but otherwise different) classes that occur in object-oriented languages. Obvious implementations involve the use of ordered lists or binary search trees defined by instances of the form: data STree a = Empty | Node a (STree a) (STree a) instance Collects a [a] where .... instance Collects a (STree a) where .... Once again, there are significant problems even with simple examples using these functions. As an example, the standard way of defining a function of type: Collects a b => [a] -> b mapping a list of values to a collection of those values using the higher order function "foldr": listToCollection = foldr addToCollection emptyCollection actually produces a function with ambiguous type: ? :t foldr addToCollection emptyCollection \d139 d140 -> foldr (addToCollection d140) (emptyCollection d139) :: (Collects c b, Collects a b) => [a] -> b ? which cannot be resolved, even with an explicit type declaration. 83 Introduction to Gofer 14.4.4 Overloading and numeric values 14.4.4 Overloading and numeric values ------------------------------------- One of the most common uses of overloading is to allow the use of the standard arithmetic operators such as (+), (*) etc. on the elements of a range of numeric types including integers, floating point values in addition to user defined numeric types such as arbitrary precision integers, complex and rational numbers, vectors and matrices, polynomials etc. In Haskell, these features are supported by a number of built-in types and a complex hierarchy of type classes describing the operations defined on the elements of each numeric type. As an experimental language, intended primarily for the investigation of general purpose overloading, Gofer has only two built-in numeric types; Int and Float (the second of which is not supported in all implementations). Similarly, although the Gofer system could be used to implement the fully hierarchy of Haskell numeric classes, the standard prelude uses a single numeric type class Num defined by: class Eq a => Num a where -- simplified numeric class (+), (-), (*), (/) :: a -> a -> a negate :: a -> a fromInteger :: Int -> a The first four member functions (+), (-), (*), (/) are the standard arithmetic functions on instances of Num, whilst "negate" denotes unary negation. The final member function, fromInteger is used to coerce any integer value to the corresponding value in another instance of Num. An expression such as "fromInteger 3" is called an overloaded numeric constant and has type Num a => a indicating that it can be used as a value of any instance of Num. See below for examples. Both Float and Int are defined as instances of Num using primitive functions for integer and floating point arithmetic: instance Num Int where (+) = primPlusInt (-) = primMinusInt (*) = primMulInt (/) = primDivInt negate = primNegInt fromInteger x = x instance Num Float where (+) = primPlusFloat (-) = primMinusFloat (*) = primMulFloat (/) = primDivFloat negate = primNegFloat fromInteger = primIntToFloat These definitions make it possible to evaluate numeric expressions involving both types: ? 2 + 3 5 (3 reductions, 6 cells) 84 Introduction to Gofer 14.4.4 Overloading and numeric values ? 3.2 + 4.321 7.521 (3 reductions, 13 cells) ? Note however that any attempt to evaluate an expression mixing different arithmetic types is likely to cause a type error: ? 4.2 * 4 ERROR: Type error in application *** expression : 4.2 * 4 *** term : 4.2 *** type : Float *** does not match : Int ? Further problems occur when we try to define functions intended to be used with arbitrary instances of Num rather than specific numeric types. As an example of this, the standard prelude function "sum", roughly equivalent to: sum [] = 0 sum (x:xs) = x + sum xs has type [Int] -> Int, rather than the more general Num a => [a] -> a which could be used to find the sum of a list of numeric values in any instance of Num. The problem in this particular case is caused by the integer constant 0 in the first line of the definition. Replacing this with the expression fromInteger 0 leads to the following definition for a generic sum function of the required type: genericSum :: Num a => [a] -> a genericSum [] = fromInteger 0 genericSum (x:xs) = x + genericSum xs For example: ? genericSum [1,2,3] 6 (10 reductions, 18 cells) ? genericSum [1.0,2.0,3.0] 6.0 (11 reductions, 27 cells) ? The fromInteger function can also be used to solve the previous problem: ? 4.2 * fromInteger 4 16.8 (3 reductions, 13 cells) ? In Haskell, any integer constant k appearing in an expression is treated as if the programmer had actually written "fromInteger k" so that both of the preceding problems are automatically resolved. 85 Introduction to Gofer 14.4.4 Overloading and numeric values Unfortunately, this also creates some new problems; applying the function fromInteger to each integer constant in previous examples causes problems with unresolved overloading: ? fromInteger 2 + fromInteger 3 ERROR: Unresolved overloading *** type : Num a => a *** translation : \d143 -> (+) d143 (fromInteger d143 2) (fromInteger d143 3) ? Once again, Haskell provides a solution to this problem in the form of a `default mechanism' for numeric types which, once the following problem has been detected, will typically `default' the unknown type represented by the type variable a above to be Int, so that the result is actually equivalent to the following: ? (fromInteger 2 + fromInteger 3) :: Int 5 (4 reductions, 8 cells) ? There are a number of problems with the Haskell default mechanism; both theoretical and practical. In addition, if a default mechanism of some form is used then it should also be capable of dealing with arbitrary user-defined type classes, rather than a small group of `standard' classes, in order to provide solutions to the unresolved overloading problems described in previous sections. Therefore, for the time being, Gofer does not support any form of default mechanism and overloaded numeric constants can only be obtained by explicit use of the fromInteger function. 14.4.5 Constants in dictionaries -------------------------------- The Gofer system constructs new dictionaries as necessary, and deletes them when they are no longer required. At any one time, there is at most one dictionary for each instance of a class. Coupled with lazy evaluation, this has a number of advantages for classes in which member functions are defined by variable declarations as in section 9.10. As an example, consider the class Finite defined by: class Finite a where members :: [a] The only member in this class is a list enumerating the elements of the type. For example: instance Finite Bool where members = [False, True] instance (Finite a, Finite b) => Finite (a,b) where members = [ (x,y) | x<-members, y<-members ] In order to overcome any problems with unresolved overloading, explicit type signatures are often needed to resolve overloading: ? members :: [Bool] 86 Introduction to Gofer 14.4.5 Constants in dictionaries [False, True] (6 reductions, 26 cells) ? length (members :: [((Bool,Bool),(Bool,Bool))]) 16 (103 reductions, 195 cells) ? In some cases, the required overloading is implicit from the context and no additional type information is required, as in the following example: ? [ x && y | (x,y) <- members ] [False, False, False, True] (29 reductions, 90 cells) ? We can also use the technique of passing a `dummy' parameter to resolve overloading problems in a function definition: size :: Finite a => a -> Int size x = length (members `asTypeOf` [x]) which calculates the number of elements of a finite type, given an arbitrary element of that type: ? size (True,False) 4 (31 reductions, 60 cells) ? Now consider the expression "size (True,False) + size (True,False)". At first glance, we expect this to repeat the calculation in the previous example two times, requiring approximately twice as many reductions and cells as before. However, before this expression is evaluated, Gofer constructs a dictionary for Finite (Bool,Bool). The evaluation of the first summand forces Gofer to evaluate the value for "members" in this dictionary. Since precisely the same dictionary is used to calculate the value of the second summand, the evaluation of "members" is not repeated and the complete calculation actually uses rather fewer reductions and cells: ? size (True,False) + size (True,False) 8 (51 reductions, 90 cells) ? On the other hand, repeating the original calculation gives exactly the same number of reductions and cells as before, because the dictionaries constructed at the beginning of each calculation are not retained for use in subsequent calculations. We can force Gofer to construct specific dictionaries whilst reading from a file of definitions, so that they are not deleted at the end of each calculation, using an explicitly typed variable definition such as: 87 Introduction to Gofer 14.4.5 Constants in dictionaries boolBoolMembers = members :: [(Bool,Bool)] This forces Gofer to construct the dictionary Finite (Bool,Bool) when the file of definitions is loaded and prevents it from being deleted at the end of each calculation. Having loaded a file containing this definition, the first two attempts to evaluate "size (True,False)" give: ? size (True,False) 4 (31 reductions, 60 cells) ? size (True,False) 4 (20 reductions, 32 cells) ? 14.4.6 The monomorphism restriction ----------------------------------- This section describes a technique used to limit the amount of overloading used in the definition of certain values to avoid a number of technical problems. This particular topic has attracted quite a lot of attention within the Haskell community where it is affectionately known as the `dreaded monomorphism restriction'. Although the initial formulation of the rule was rather cumbersome and limiting, the current version used in both Gofer and Haskell is unlikely to cause any problems in practice. In addition, many of the examples used to motivate the need for the monomorphism restriction in Haskell occur as a result of the use of implicitly overloaded numeric constants, described in section 14.4.4, and hence do not occur in Gofer. The monomorphism restriction takes its name from the way in which it limits the amount of polymorphism that can be used in particular kinds of declaration. Although we touch on this point in the following discussion, the description given here uses an equivalent, but less abstract approach, based on observations about the implementation of overloaded functions. Basic ideas: ------------ As we have seen, the implementation of overloading used by Gofer depends on being able to add extra arguments to a function definition to supply the required dictionary parameters. For example, given a function definition such as: isElement x [] = False isElement x (y:ys) = x==y || isElement x ys we first add a dictionary parameter for the use of the overloaded (==) operator on the right hand side, obtaining: isElement x [] = False isElement x (y:ys) = (==) d x y || isElement x ys Finally, we have to add the variable d as a new parameter for the function isElement, on both the left and right hand sides of the 88 Introduction to Gofer 14.4.6 The monomorphism restriction definition: isElement d x [] = False isElement d x (y:ys) = (==) d x y || isElement d x ys The monomorphism restriction imposes conditions which prevent this last step from being used for certain kinds of value binding. Declaration groups: ------------------- Before giving the full details, it is worth pointing out that, in general, the monomorphism restriction affects groups of value declarations rather than just individual definitions. To illustrate this point, consider the function definitions: f x y = x==y || g x y g x y = not (f x y) Adding an appropriate dictionary parameter for the (==) operator gives: f x y = (==) d x y || g x y g x y = not (f x y) The next stage is to make this dictionary variable into an extra parameter to the function f wherever it appears, giving: f d x y = (==) d x y || g x y g x y = not (f d x y) But now the right hand side of the second definition mentions the dictionary variable d which must therefore be added as an extra parameter to g: f d x y = (==) d x y || g d x y g d x y = not (f d x y) In other words, if dictionary parameters are added to any particular function definition, then each use of that function in another definition will also be require extra dictionary parameters. As a result, the monomorphism restriction has to be applied to the smallest groups of declarations such that any pair of mutually recursive bindings are in the same group. As the example above shows, if one (or more) of the bindings in a given declaration group is affected by the monomorphism restriction so that the appropriate dictionary parameters cannot be added as parameters for that definition, then the same condition must also be imposed on all of the other bindings in the group. [Adding the extra parameter to f in the example forces us to add an extra parameter for g; if extra parameters were not permitted for g then they could not be added to f.] 89 Introduction to Gofer 14.4.6 The monomorphism restriction Restricted bindings: -------------------- There are three main reasons for avoiding adding dictionary parameters to a particular value binding: o Dictionary parameters unnecessary. If the dictionary values are completely determined by context then it is not necessary to pass the appropriate values as dictionary parameters. For example, the function definition: f x = x == 0 || x == 2 can be translated as: f x = (==) {dict} x 0 || (==) {dict} x 2 where, in both cases, the symbol {dict} denotes the dictionary for Eq Int. As a further optimisation, once the dictionary is fully determined, this can be simplified to: f x = primEqInt x 0 || primEqInt x 2 o Dictionary parameters cannot be added in a pattern binding. One potential solution to this problem would be to replace the pattern binding by an equivalent set of function bindings. In practice, we do not use this technique because it typically causes ambiguity problems, as illustrated by the pattern binding: (plus,times) = ((+), (*)) Translating this into a group of function bindings gives: newVariable = ((+), (*)) plus = fst newVariable -- fst (x,_) = x times = snd newVariable -- snd (_,y) = y The type of newVariable is (Num a, Num b) => (a->a->a, b->b->b) so that the correct translation of these bindings using two dictionary variables gives: newVariable da db = ((+) da, (*) db) plus da db = fst (newVariable da db) times da db = snd (newVariable da db) and hence the correct types for plus and times are: plus :: (Num a, Num b) => a -> a -> a times :: (Num a, Num b) => b -> b -> b both of which are ambiguous. o Adding dictionary parameters may translate a variable definition into a function definition, loosing the benefits of shared evaluation. As an example, consider the following definition using the function "size" and the class Finite described in the previous section: 90 Introduction to Gofer 14.4.6 The monomorphism restriction twiceSize x = n + n where n = size x Since the variable n is defined using a local definition, we would not expect to have to evaluate size x more than once to determine the value of twiceSize. However, adding extra dictionary parameters without restriction gives: twiceSize d x = n d + n d where n d = size d x Now that n has been replaced by a function, the evaluation will be repeated, once for each occurrence of the expression "n d". In order to avoid this kind of problem, the monomorphism restriction does not usually allow extra parameters to be added to a variable definition. Thus the original definition above will be translated to give: twiceSize d x = n + n where n = size d x Note that the same rule is applied to variable definitions at the top-level of a file of definitions, resulting in an error if any dictionary parameters are required for the right hand side of the definition. As an example of this: twiceMembers = members ++ members which produces an error message of the form: ERROR "ex" (line 157): Unresolved top-level overloading *** Binding : twiceMembers *** Inferred type : [_7] *** Outstanding context : Finite _7 ? [COMMENT: A type expression of the form _n (such as _7 in this particular example) represents a fixed (i.e. monomorphic) type variable.] In the case of a variable declaration, the monomorphism restriction can be overcome by giving an explicit type signature including an appropriate context, to indicate that the variable defined is intended to be used as an overloaded value. In this case, we need only include the declaration: twiceMembers :: Finite a => [a] in the file containing the definition for twiceMembers to suppress the previous error message and allow the function to be used as a fully overloaded variable. Note that the monomorphism restriction interferes with the use of polymorphism. For example, the definition: aNumber = length (twiceMembers::[Bool]) + length (twiceMembers::[(Bool,Bool)]) where twiceMembers = members ++ members 91 Introduction to Gofer 14.4.6 The monomorphism restriction will not be accepted because the monomorphism restriction forces the local definition of "twiceMembers" to be restricted to a single overloading (the dictionary parameter supplied to each use of members must be constant throughout the local definition): ERROR "ex" (line 12): Type error in type signature expression *** term : twiceMembers *** type : [(Bool,Bool)] *** does not match : [Bool] ? Once again, this problem can be fixed using an explicit type declaration: aNumber = length (twiceMembers::[Bool]) + length (twiceMembers::[(Bool,Bool)]) where twiceMembers :: Finite a => [a] twiceMembers = members ++ members Formal definition: ------------------ The examples above describe the motivation for the monomorphism restriction, captured by the following definition: Dictionary variables will not be used as extra parameters in the definition of a value in a given declaration group G if: either: G includes a pattern binding or: G includes a variable declaration, but does not include an explicit type signature for any of the variables in the group. If neither of these conditions hold, then equivalent sets of dictionary parameters will be added to each declaration in the group. 92