Tue, 1 Nov 1994 23:54:45 GMT

Related articles |
---|

[25 earlier articles] |

Re: Polymorphism vs. Overloading mmcg@bruce.cs.monash.edu.au (1994-10-29) |

Re: Polymorphism vs. Overloading hbaker@netcom.com (1994-10-29) |

Re: Polymorphism vs. Overloading jhallen@world.std.com (1994-11-01) |

Re: Polymorphism vs. Overloading kanze@lts.sel.alcatel.de (kanze) (1994-11-01) |

Re: Polymorphism vs. Overloading davidm@Rational.COM (1994-10-31) |

Re: Polymorphism vs. Overloading bill@amber.ssd.csd.harris.com (1994-11-01) |

Re: Polymorphism vs. Overloading drichter@pygmy.owlnet.rice.edu (1994-11-01) |

Re: Polymorphism vs. Overloading bevan@cs.man.ac.uk (1994-11-02) |

Re: Polymorphism vs. Overloading bimbart@CS.kuleuven.ac.be (Bart Demoen) (1994-11-02) |

Re: Polymorphism vs. Overloading monnier@di.epfl.ch (1994-11-01) |

Re: Polymorphism vs. Overloading nickb@harlequin.co.uk (1994-11-09) |

Re: Polymorphism vs. Overloading franka@europa.com (1994-11-09) |

Newsgroups: | comp.compilers |

From: | drichter@pygmy.owlnet.rice.edu (David Richter) |

Keywords: | polymorphism |

Organization: | Rice University |

References: | 94-10-144 94-10-182 |

Date: | Tue, 1 Nov 1994 23:54:45 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.