Previous    Next

Polymorphic Types

poly-mor-phic: able to assume different forms

Webster's Dictionary


Some functions execute in a way that's independent of the data type on which they operate. Some data structures are structured in the same way regardless of the types of their elements. As an example, consider a function to concatenate linked lists in Java. We define a List class, subclasses for empty and nonempty lists, and a (nondestructive) append method:

abstract class IntList {
 IntList append(IntList more);
class IntCons extends IntList {
 Integer head; IntList tail;
 IntCons (Integer head, IntList tail) {
 this.head=head; this.tail=tail;
 IntList append(IntList more) {
 return new IntCons(head, tail.append(more));
class IntNull extends IntList {
 IntNull () {}
 IntList append(IntList more) {
 return more;

There's nothing about the code for the IntList data type or the append method that would be any different if the element type were String or Tree instead of Integer. We might like append to be able to work on any kind of list. We could, of course, use the word Object instead of Integer to declare head, but then if we unintentionally mixed Integers and Strings as elements of the same List, the compiler's type-checker wouldn't be able to give us useful feedback: we'd get a runtime exception at a downcast somewhere. A function is polymorphic (from the Greek many+shape) if it can operate on arguments of different types. There are two main kinds of polymorphism Parametric polymorphism A function is parametrically polymorphic if it follows the same algorithm regardless of the type of its argument. The Ada or Modula-3 generic mechanism, C++ templates, or ML type schemes are examples of parametric polymorphism. Overloading A function identifier is overloaded if it stands for different algorithms depending on the type of its argument. For example, in most languages + is overloaded, meaning integer addition on integer arguments and floating-point addition (which is quite a different algorithm) on floating-point arguments. In many languages, including Ada, C++, and Java, programmers can make overloaded functions of their own.

These two kinds of polymorphism are quite different - almost unrelated - and require different implementation techniques.

JaVaScreenshot Previous    Next