Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!ncar!elroy.jpl.nasa.gov!jarthur!ucivax!orion.oac.uci.edu!cerritos.edu!arizona.edu!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Runtime Polymorphism -- To Have and Have Not
Message-ID: <562@coatimundi.cs.arizona.edu>
Date: 1 Mar 91 21:57:28 GMT
Sender: news@cs.arizona.edu
Lines: 76

It is a simple matter to define a language that has the advantages of
runtime polymorphism without the disadvantages.  More specifically, it
is possible to allow runtime polymorphism in some places and not in
others, and you only pay the penalties for the feature when you are
actually making use of it.

Start with a strongly typed language with automatic type conversion.
Add a new type called "top".  A value of this type contains two parts,
(1) a value of some other type, and (2) a tag to tell what the type of
the value is.  Expressions of type top can occur anywhere.  For
example

  top x, y; double z; int arr[20];
  x = 3;
  y = 4.2;
  z = x;
  z = x + y;
  x = arr[y];
  y = x;
  ...

The rule is that in a dereferencing context, a value of type top can
be automatically converted to any other type, but the conversion
involves a test to make sure that the type actually is correct.  For
example, in the above code fragment all statements are legal except
for "x = arr[y]", since during the conversion of y to an integer, it
is discovered that y is in fact a float.  (Of course this assumes that
floats are not converted automatically into ints.  If floats are
converted automatically into ints then all the above expressions are
legal.)

On the left hand side of an assignment, a variable of type top gets
the value of the right hand side plus the type of the right hand side.
In "x = 3", x gets the type int.  In "y = 4.2", y gets the type float.
In "y = x", y gets the current type of x.

One caveat is that type information must be propogated down the parse
tree as well as up.  For example, in "z = x + y", there has to be some
information passed down the parse tree to x and y to generate code
that will convert them to floats.  By extension, type information must
also be propogated from the left side of assignments to the right
side.

In the above, I slid past another potential problem: what to do for
polymorphic operators (and function).  In "z = x + y", you want the
expression to behave at runtime just like it would have behaved if you
had known the types of x and y at compile time.  That means that if x
and y are both integers, then you want integer addition performed, and
the result coerced to a float for assignment.  In general, the
decision of what version of a polymorphic operator to apply must be
made at runtime using the same algorithms that would be used at
compile time if the types were known.  However, this usually is a
simple case-by-case analysis of the types of the parameters.

Declarations in a language with top are a superset of the language
without top.  Using C-with-top as an example, you might declare a tree
struct as follows:

  struct tree {data;left;right}

where names given without types are assumed to have type top.  Thus,
the data is fully polymorphic, and so are the branches.  Or you might
want a little more type security so you could define

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

which does type checking on the branches, but leaves the data in the
trees fully polymorphic.

Program development then becomes a process of starting with skeleton
declarations and adding type details as required for debugging or
performance needs.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman