Polymorphism

Some motivation for polymorphism
- Monomorphism and type checking

Polymorphism is the simplification and generality of having one name to operate safely on values of more than one type. For example ``+'',``*'',``-'' apply to REALs, INTEGERs, CARDINALs and subranges in Modula-2, a function to find the length of a list in Haskell can be applied to any list. In 1967 Christopher Strachey identified two principal forms of polymorphism in programming languages:

ad-hoc polymorphism: under one name different operations can be applied to different types. This is more commonly called overloading.
parametric polymorphism: one operation can be applied to different types of value. The generics of Ada are an example of a form of parametric polymorphism.

Both these forms of polymorphism are important. They are applicable in different situations.

Some motivation for polymorphism

Before a fuller description of polymorphism it might help to provide a justification. Polymorphism can be seen as an attempt to overcome the inflexibility of type monomorphism and still retain the advantages of static type checking.

Monomorphism and type checking

A monomorphic type system is one where procedures or functions can be applied to only one type. So the Modula2 procedure:

  TYPE  list = POINTER TO cell;
        cell = RECORD
                 val : INTEGER;
                 nxt : list
               END;
  ....
  PROCEDURE last(il: list): INTEGER;
  BEGIN
    IF il = NIL THEN RETURN NIL
    ELSIF il^.nxt = NIL THEN RETURN il^.val
    ELSE  RETURN last(il^.nxt) END
  END last;

will only find the last element of lists containing integers. If the program needs lists of other types the code and definitions will be identical except that INTEGER will be replaced by REAL or whatever.

Such an inflexible type discipline has two immediate consequences, firstly, nearly identical code must be replicated, and secondly, each version of the type and the function must have distinct names. Both of these make program development, reuse and maintenance harder.

As was seen in sub-section the dynamically type checked languages allow structures and code to be used for any type. The function:

   (defun length (l)
      (cond ((null l) 0)
            (t (+ 1 (length (cdr l))))
   ))

can be applied to any sort of list:

   (length '(1 2 3 4))
   (length '(apple orange pear))
   (length '(1 red "hello"(10 20) 4))

However this also allows runtime type errors. How is it possible to get re-use and simplicity with some compile time checking?

Next: Parametric polymorphism Up: Types, type checking and Previous: Static and dynamic type

Page generated: 2002-11-04 by Bob Dickerson

Disclaimer