From: gb@cs.purdue.EDU (Gerald Baumgartner)
Newsgroups: comp.object
Subject: Re: Polymorphism (was: Re: comparing object-oriented platforms)
Date: 15 Oct 92 18:24:37 GMT
Organization: Department of Computer Science, Purdue University

In article <1992Oct14.200408.17846@dec254.uucp> hall@dec254.uucp (Phil Hall) writes:
> In hopes of helping clear up some terminology issues I have a question 
> concerning parametric polymorphism.

Quote of previous poster deleted.

> I am not familiar with "ML-style polymorphism" but I expect it is the
> same as "generic procedures" above.

It's not quite the same.  For example, let's have a look at the identity
function in ML:

	fun id (x) = x;

The type of this function is, in ML syntax,

	'a -> 'a

that means `for every type a: the function takes an element of type
a as argument and returns an element of type a as return value.'
The ML compiler compiles one version of the function that can deal
with any type of argument.

With generic functions you can come close to parameteric polymorphism
but it's not that powerful.  The above function could be written in
Ada:

	generic
	    type T is private;
	function Id (X : in T) return T is
	begin
	    return X;
	end;

Now this is just a template, it is not executable.  To create an
executable version we have to instantiate with a particular type,
as in:

	function IntId is new Id (INTEGER);

We end up having one compiled version per parameter type.


> The way I understand [CARD85]'s parametric polymorphism is that 
> the same *implementation* accepts a parameter of any type or some set
> of types.  I've heard the "any type" version refered to as "pure" 
> polymorphism.  This assessment would label "parameterized
> types/generics/ML-style polymorphic functions" as overloading
> rather the parametric polymorphism.

BTW, the `some set of types' still refers to parameteric polymorphism.
For example, the function to compute the length of a list in ML

	fun length (x) = if null (x) then 0 else length (tl (x)) + 1;

is still polymorphic, although it doesn't operate on all types, but
only on lists.  The ML compiler tells us, that `length' has the type

	'a list -> int

Overloading is different.  For overloading, you have several different
functions (e.g., addition for integers and for reals, set union) which
are denoted by the same name in the programming language (e.g, the
symbol `+').  The compiler picks one of them based on the argument
(and return) types.

The main difference between parameteric polymorphism/generic functions
and overloading is that in the case of overloading the functions
involved are completely unrelated, except that they happen to have the
same name.

For both, parameteric polymorphism and generic functions, you have
only one function that describes the behavior for any type of
argument.  In the case of parameteric polymorphism, this function is
compiled into only one assembly function which can operate on any type
(and there are infinitely many types).  A generic function is compiled
into several different assembly functions (finitely many), each of
which operates on only one type.

Hope that helps,

Gerald

--
Gerald Baumgartner
Dept. of Computer Sciences, Purdue University,  W. Lafayette, IN 47907
Internet: gb@cs.purdue.edu, UUCP: ...!{decwrl,gatech,ucbvax}!purdue!gb
Newsgroups: comp.object