Department of Computer Science



next up previous
Next: Review of sub-typing and Up: Types, type checking and Previous: Parametric polymorphism


Overloading (or ad-hoc polymorphism)


Subsections

Ad-hoc polymorphism is different operations on different types known by the same name. This is also called overloading. It exists in most languages where the simple arithmetic operators ``+'', ``*'', ``-'' etc. are applicable to more than one type. The operator: ``+'', if applied between 2 integers generates an integer add instruction whereas when applied between 2 real numbers uses a floating point add and the bit-manipulation of floating point and integer adds is different.

The problem is simple: how is the appropriate operation determined? In the case of explicitly programmer-typed languages like Ada and Modula-2 it is simple: the compiler easily determines which instruction to use by the declared or inferred types of its operands.

This simple overloading extends to overloading procedure names in Ada and C++. Suppose there are two procedures to compute the sum of squares of 2 numbers, one for reals and one for integers, they can be given the same name:

   int sumsq(int a,int b) {  return a*a + b*b; }

   double sumsq(double a, double b) {  return a*a + b*b; }
The solution is still simple: the compiler can infer which piece of code to use by the context:
   double x;
   ...
   ...sumsq(x,3.0) + 2.1..
obviously use the double sumsq function.

Resolving overloading with sub-types: inheritance polymorphism

Determining which operation to use for a given name with overloading and subtyping is not so easy. In languages with inheritance that allow redefinition of operators and permit subtyping a parent variable can contain derived or subclass values. If an operation is invoked on this variable which version of the operation is used? Consider the C++ fragment:

  class P {
     protected:
        int i;
     public:
        P(void) { i=0; }
        virtual void show(void){printf("P's i=%d\n",i);}
  };
  class C: public P {
     protected:
        int j;
     public:
        C(void):P() { j=1; }
        void show(void){printf("C's i=%d j=%d\n",i,j); }
  };
this defines 2 classes with a subtype relationship because of the public derivation. The operation show is defined on both but is different, it is also declared virtual which means that that the operation appropriate to the type should be used. If the operation is invoked:
   
   main()
   {  P p;
      C c;
      P *pp;
      ...
      pp->show();
which code is invoked? This cannot be resolved by static typing, the type of pp is a pointer to P values but if the code between the declarations and the call dynamically assigns a C value eg:
   
   pp = &c;
then the required call should get C's code. The solution to this is to compile the call of the operation indirectly and have indirection information in each object, then at runtime the call will dynamically select the correct code. This works, there are different ways of implementing it and the small cost is more than outweighed by the advantages. This is called dynamic binding.


Problems with overloading and type inference

In the functional language SML which supports parametric polymorphism and type inference there is also overloading of ``+'' etc. on reals and integers this creates another resolution problem.

SML infers the type of names but if an overloaded operator is applied to a name which of the possible types should be assigned? Eg:

   fun square n = n * n;
is this of type:
   
   square: int -> int
or:
   square: real -> real ?
The operator ``*'' is overloaded on integers and reals and there is no information to help. SML will fail to determine the type of square:
   Type checking error in: (syntactic context unknown)
   Unresolvable overloaded identifier:  *
   Definition cannot be found for the type: 'a -> 'a
The programmer must provide some explicit information about the type of the argument or result of square:
   fun sumsq (n:int) = n * n;
Miranda, which also uses type inference, resolves the problem another way, it avoids overloading the arithmetic operators. There is only one type for integers and reals in Miranda it is num, this is the only type on which arithmetic operators are defined. This is not a very desirable solution as the 2 numeric types really should be treated differently: a ``counting'' value should not be fractional.

The problem also occurs with comparsion operators. Are equality ``='' or ordering ``<'' overloaded operators or are they polymorphic? If they are completely polymorphic it means they can be used with any types at all just like being parameters or being the elements of lists. Or are they overloaded because they are not applicable to all possible types? Comparisons, particularly equality, are used on nearly all types but strictly they are only overloaded because function values and abstract data types cannot (and should not) be compared. However this then produces a problem, any function using equality is not polymorphic and multiple explicitly typed versions must be written (or the equality check must be provided as an additional argument).

Once again SML and Miranda have different solutions. Miranda pretends there is no problem, comparisons (``='', ``<'' etc.) are treated as polymorphic but an attempt to compare 2 functions produces a runtime error. An earlier version of SML made them overloaded and not polymorphic so the function:

   fun member [] e = false
     | member (h::t) e = (e=h) orelse member t e
produced a compiler error and could not be given a type. This is also obviously inconvenient and silly so the current version has introduced the solution of partial polymorphism. There is a new type parameter instead of 'a there is a doubly primed letter ''a this stands for any type admitting equality. So the above function has type:
   val member = fn : ''a list -> ''a -> bool
This is not an entirely satisfactory solution as other type parameters can be used in any context, they mean: ``any type''. These more or less overloaded operators need a better solution.

Type classes

To overcome the problems of more-or-less-overloaded operators Wadler and Blott suggest a new approach in their paper ``How to make ad-hoc polymorphism less ad-hoc'', published in the Proceedings of the 16th Symposium on The Principles of Programming Languages, in 1989. They suggest a systematic way for languages to overload operators in classes (not the same as OO language classes) and define which types belong to which classes and therefore which operators are defined on them. Their solution has been implemented in the language Haskell which is freely based on Miranda. For example, to define arithmetic operator overloading:

   class Num a where
      (+), (*) :: a -> a -> a
      negate   :: a -> a

   instance Num Int where
      (+)    = addInt
      (*)    = mulInt
      negate = negInt

   instance Num Float where
      (+)    = addFloat
      (*)    = mulFloat
      negate = negFloat
The class declaration defines the class Num parameterised with ``a'' of types (the parameter is a place holder for types) which have ``+'', ``*'' and negate defined on them. The first instance declaration states that the type Int is a member of Num and it will use the actual operation (or code) addInt for ``+'' etc. Now when a functions type is given explicitly or inferred and it uses an overloaded operator the type can be constrained to be any type that is an instance of Num:
   square x = x * x
will have type:
   square   :: Num a => a -> a
which means square can be applied to any type ``a'' and will produce a result of type ``a'' so long as the type is an instance of Num. ``Num a =>'' is a sort or predicate, condition or constraint on which types can be substituted for ``a''.

This gives a simple, uniform, fully checked solution to the problem of overloading with type inference. It can be applied to equality aswell:

   class Eq a where
      (==) :: a -> a -> Bool
   instance Eq Int where
      (==) = eqInt
   instance Eq Char where
      (==) = eqChar
where the operator ``=='' is overloaded for as many types as are declared instances of Eq. Then the member function can be defined on any type that is in class Eq:
   member [] y     = False
   member (x:xs) y = (x==y) \\/ member xs y
this has type:
   member     :: Eq a => [a] -> a -> Bool
Now it might be necessary to define equality between lists, there must be an instance of Eq for list types but what should the list implementation of the ``=='' operator be? To do this each element of the list must be compared in turn which will require that the element type of the list is of Eq class:
   instance Eq a => Eq [a] where
      [] == []       = True
      [] == (y:ys)   = False
      (x:xs) == []   = False
      (x:xs)==(y:ys) = (x==y) & (xs==ys)
this defines list types ``[a]'' to be instances of Eq if the type ``a'' is an instance of Eq. It then defines the implementation of ``=='' on list types.

The equality types can be defined over user defined types aswell by making the new types instances of the Eq family and defining the correct code for ``=='':

 Set a ::= MkSet [a]

 instance Eq a => Eq (Set a) where
   (MkSet xs) == (MkSet ys) =
       and (map (member xs) ys) & and (map (member ys) xs)
The type ``Set a'' is an instance of Eq if its elements are, and equality is if both sets are subsets of each other.

For all the standard types and their structures in Haskell all the classes and instance declarations are given in a standard prelude so they don't need to be given by programmers but programmers can add their own new types to these classes if they wish.

There is a runtime implication for this. Just as with subtyping and overloading in object oriented languages there is a need for some form of dynamic binding. Applications of overloaded operators must resolve the actual function to apply when they applied since, for example in the case of lists, the actual value of the arguments could be anything. The overhead is not necessarily high as in many cases the compiler could optimise the code by using any information it has to resolve the actual functions.

Haskell classes and classes in object oriented languages

A class in an objected oriented language can act as a type, in as much as it can be used to ``generate'' new object values. (It is not obvious exactly what a type is, but being a collection of values is probably part of it). Obviously a Haskell type class is not a type, types are separate, they ``join'' classes.

The nearest thing in an object oriented language to a Haskell type class is probably the abstract class (pure virtual in C++, completely deferred class in Eiffel, or interface in Java). For example the class Ordered_Collection:

  template<class T> class Ordered_Collection {
    public:
      virtual int empty(void)=0;
      virtual void add(T e)=0;
      virtual T first(void)=0;
      virtual void remove(T e)=0;
  };
Which is a generalised form of any container that can have elements added, removed and have a ``first'' element. However there is no code for the functions because it will depend on whether it is a queue, a priority queue or a list.

These sorts of class can only be used as ``parents''. They only contain the signatures of functions, when any class is derived from an abstract class it must provide concrete versions of all the functions named in the abstract class. The reason for the use of such classes is for defining the ``top'' of a type hierarchy, any variable or parameter of the abstract class type can hold any object of a derived type.

It is like a Haskell class in that it can be used for type checking, it just defines some properties (operators) that all derived classes (``instances types'') must have. Similarly its use implies dynamic binding to the concrete methods provided in the derived classes.

Constrained type parameters to generics in Eiffel

Eiffel also has a good way of solving the problem of resolving overloaded operators with parametric polymorphism, ie. how to have functions, classes, abstypes or packages with parameterised types that need to apply some operation to the parameterised values.

In Eiffel the problem is operations on class values as arguments to generic classes. The solution is in some ways analagous to the Wadler and Blott solution. The type parameters can be constrained to be subclasses of some class. For example suppose it is required to have a class representing some ordered queue so that the highest priority element is always the next one retrieved no matter what the order of arrivals is. Further suppose that this ordered queue is to be parameterised by the type of enqueued element. Now one operation the class will certainly need to perform on the elements is comparison for order. How can it be guaranteed that this operation will be available on all types that instantiate the generic parameter? Once again it could be assumed that ordering, ``<'', is available on all types and produce a runtime error if it is not, like Miranda does; but this is not a very good solution. Instead, because all types can be classes that are subclasses, define a class with an ordering operation and insist that all instantiating types are subclasses of this class; in other words state that all the allowed arguments are types that overload ``<''. Eg:

   class ordered_collection[T->comparable]

   feature
      q: array[T];
      maxsize: integer is 100;
      num_elems: integer;
   
      first: T is  require not empty
      do  result := q.item(num_elems)
      end; -- first
      ...   

      insert(e:T) is  require not full
      local
         i,j: integer
      do  
         ...
         if e < q.item(i) ....
This declares that ordered_collection can contain elements of any T type as long as T is a direct or indirect subclass of comparable which will include the operator ``<'', defined appropriately for the value to be ordered.

Clearly this is not exactly the same as Haskell ``classes'' (which are not!) but it is attempting to extend overloading safely in the context where a type parameter cannot be completely general.


next up previous
Next: Review of sub-typing and Up: Types, type checking and Previous: Parametric polymorphism


Page generated: 2002-11-04 by Bob Dickerson

© University of Hertfordshire Higher Education Corporation (1998)

Disclaimer