Re: Polymorphism vs. Overloading

gdevivo@conicit.ve (Gabriela de Vivo) worte:
|> Last week I was invited to join a Thesis (MsC) presentation.
|> At some point a question raised about the exact difference between
|> Polymorphism and Overloading.


Well, I mailed a reply to Gabriela de Vivo in the foolish hope that
comp.compilers wouldn't get flooded. But since it has anyway, I might
as well add my 2 cents. I've added some material to end as well.


I suppose we have some expression in a language that looks like


f(a1,a2,a3,...,an)


Overloading is having multiple functions with the same 'name';
which--if any--function actually gets invoked on the arguments depends
on the semantics--which may be ambiguous or nondeterministic.
Typically, the dispatch is on the number of arguments and/or the types
of the arguments. Moreover, some semantics (eg: C++ semantics) have
rules for converting the arguments to other types if the original
types have no corresponding function. Thus, the semantics has both
f : t1 x ... x tn -> t and f : t1' x ... x tn' -> t'. Any guarantee
that the two f's have anything to do with each other is made by the
programmer.


Polymorphism has two nice forms: order sorted and parametric. Both
are similar, but the combination is pretty (and I'd hate to do type
inference :-) ).


Order sorted comes from order sorted algebra. A order sorted algebra
has a set S of sorts, an S-sorted carrier set A, and a set of
operators defined on all or part of A. For s1, s2 \in S, s1 <= s2 iff
A_s1 \subset_or_eq A_s2. An operator f may have multiple _consistent_
typings, eg: if f : s1 x ... x sn -> s0 and si' <= si (i \in {0..n}),
then f : s1' x ... x sn' -> s0' is also possible.
Eg: + : Num x Num -> Num, + : Int x Int -> Int, + : Nat x Nat -> Nat, etc.


Parametric polymorphism typically has operators working on a sum of
types in a uniform fashion. For example, one might have type
constructors parameterized over the types of the arguments to the
constructor (eg: Standard ML). A type t might be constructed by t1
through tn, but generally one uses parameterized types such as t(a1,
..., am) and constructors t1(b11, ... b1k1) through tn (bn1, ...,
bnkn) s.t. {a1, ..., am} \superset_or_eq \union (j=1..n, {b11, ...,
b1kj}). Eg: a type Stack(a) with constructors EmptyStack : ->
Stack(a) and Push : a x Stack(a) -> Stack(a). This kind of multiple
constructors on multiple arguments is called a sum of products type,
as in Stack(a) = Sum ( () , a x Stack(a) ) (the recursiveness is
another issue). Using sum of products, one could have a type Num with
constructors I : Int -> Num, N : Nat -> Num, F : Float -> Num and
write a + : Num x Num -> Num, but this is function has both input and
output disjoint from the + : Int x Int -> Int and + : Nat x Nat -> Nat
functions that would presumably also be defined. Thus, parametric
polymorphism imitating order sorted polymorphism has plenty of
injections and projections floating around. (Rather like category
theory in a non-skeletal category.)


The difference should now be obvious. (:-)) Polymorphism defines one
function that is guarranteed to be consistent along all possible types
of parameters, while overloading defines multiple functions that the
programmer claims are sufficiently similar to deserve identical names.
(Eg: + : Float x Float -> Float and + : Int x Int -> Int.)


Which is better? Overloading is in some sense easier to fiddle with,
eg: suppose I'm writting a numerics package, and I need debugging
output from + : MyNums x MyNums -> MyNums only, without futzing with
all the other +'s floating around. On the other hand, polymorphism is
easier on humans reading the code (eg: + is always addition) and so,
easier to write specifications for and check against specs. However,
with order sorted polymorphism, the proof that f : s1 x ... x sn -> s0
specializes to f : s1' x ... x sn' -> s0' may be quite difficult.
Worse, f may use other order sorted polymorphic functions which have
to be checked as well, so if a loop exists in the call graph then a
(least) fixed point may need to be found.


Languages with both tend to be kludgy at best and impossible at worst.
(Not to pick on C++ or any OO language, of course ;-).)






People have been talking about ad hoc polymorphism, and connections
between polymorphism and OOP. Ad hoc polymorphism, eg: Lispy explicit
dispatch on the type of the argument, is close to both overloading and
to order sorted polymorphism (with an appropriate ordering on the
sorts, that is, with a universal type).


As for OOP; OOP tends to be closer to overloading, or at most ad hoc
polymorphism, due to the inherent feature of the object's true (that
is, most specific) type determining which method of a given name is
actually invoked. That is, suppose f: Container -> bool implements
isFull?, that is,
f=(\a : Container . (zero? (- (maxNumberOfObjects a)
(currentNumberOfObject a))))
Which maxNumberOfObjects and currentNumberOfObjects methods get
invoked depends on what kind of Container a is. So in this sense,
OOP is inherently overloaded. But well written OOP code will typically
behave as if it is polymorphic. Great, huh?


David
--

Return to the comp.compilers page.
Search the comp.compilers archives again.