Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!elroy.jpl.nasa.gov!sdd.hp.com!caen!news.cs.indiana.edu!arizona.edu!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Runtime Polymorphism -- To Have and Have Not (Par
Message-ID: <559@coatimundi.cs.arizona.edu>
Date: 1 Mar 91 07:37:27 GMT
Sender: news@cs.arizona.edu
Lines: 80

Runtime polymorphism (or runtime typing, or dynamic typing) means that
identifiers in a language do not have types that are fixed at compile
time, they can reference values of different types at different times
in the program.  Languages with runtime polymorphism include Lisp,
Smalltalk, Icon, and Prolog.

There are several advantages to this.  First, it makes program
prototyping and developement much faster because declarations are
minimized.  For example a structure to represent a binary tree of
integers might be declared as

  record tree(data,left,right)

rather than

  struct tree {
    some_type data;
    struct tree left,right;
  }

I've saved maybe half of the work for an extremely simple structure.
I'd guess that for complex structures, the declarations for a language
with runtime polymorphism run 10% or so of the size of declarations in
a strongly typed language.  This can save a lot of time when you first
start writing the program and can save even more time later when you
change the representations (since most of the polymorphic declarations
needn't be changed).  In fact all of the languages named above have
powerful enough built-in data types that you can get by with almost no
declarations at all.  And such powerful built-in data types can only
be defined in languages that have runtime polymorphism.

Another advantage of runtime polymorphism is code generality.  You can
write generic procedures that work on many data types (as long as it
only makes use of operations that have definitions for all the data
types).  For example you can write a procedure to insert something in
a tree without knowing the type of the object: (Icon code)

  # insert x into tree t and return the new tree
  procedure tree_insert(t,x)
    if t === &null return tree(x)
    if x <<< t.data then 
      t.left := tree_insert(t.left,x)
    else
      t.right := tree_insert(t.right,x)
    return t
  end

The only operations on x are object comparison (<<<) and inserting
into a record, so the procedure is entirely generic.  (As an aside,
does anyone really want to claim that the lack of semi-colons is
confusing here?  I don't know of anyone who has actually programmed in
Icon who found the semi-colon rule to be any problem at all.)

There are two problems with runtime typing (or I should say, one
problem and one complaint of questionable importance)  First, it is
very hard to make these programs run fast.  In practice, most programs
use most variables in a type-consistent way, but the user pays the
performance penalty of having runtime type checks everywhere.  These
type checks can be largely eliminated by type inference, but not
entirely.  And there still must be some mechanism for cleanly
combining values of unknown type with values of known type.

The questionable complaint about runtime typing is that it leads to
hard-to-find errors that are not caught until runtime.  It is true
that type errors in such languages cannot be found until runtime, and
that the place where a runtime error actually occurs is not always
near where the error originated.  On rare occasions these errors
require some serious debugging.  But in my experience this is a minor
problem, and the time spent looking for these errors is quite small
compared to the time that would have been spent writing strongly typed
declarations.

Even so, I believe that there is a solution to both of these problems
that still leaves the advantages of runtime polymorphism intact.  I'll
discuss the solution in a later posting (and maybe answer some of the
flames that this article may generate :-).
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman