Department of Computer Science
Department of Computer Science
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.
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.
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 -> intor:
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 -> 'aThe 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 -> boolThis 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.
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 * xwill have type:
square :: Num a => a -> awhich 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 ythis has type:
member :: Eq a => [a] -> a -> BoolNow 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.
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.
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.
© University of Hertfordshire Higher Education Corporation (1998)