Polymorphism: Ability of a function to take arguments of multiple types.
-------------
The primary use of polymorphism is code reuse. Functions that call polymorphic
functions can use the same piece of code to operate on different types of
data. 

Overloading (aka adhoc polymorphism):
Same function NAME is used to represent different functions, each of which
may take arguments of a specific type. 
e.g., operator '+' is overloaded in most languages so that
they can be used to add integers or reals. But the integer addition
operation is very different from the addition operation on reals.

Arbitrary function names can be overloaded in C++, but not in C.

All virtual functions are in fact overloaded functions.

Parametric polymorphism: 
The same function works for arugments of different types, same code is
reused for arguments of different types. With overloading, you get resue
of "client" code, i.e., code that calls an overloaded function.

template <class C> 
Type min(const Type* a, int size, Type minval) {
   for (int i = 0; i < size; i++)
       if (a[i] < minval)
          minval = a[i];

   return minval;
}

The above example shows how the same code can be used for
computing the minimum value from arrays of any type. The only 
requirement is that the type support the comparison operator "<"
and the assignment operator "=". 

The above function definition is parameterized wrt to the type "class C",
and hence the term "parametric polymorphism". The constraint regarding
this type, namely that it support the operations "<" and "=", is implicit
from the body of the template function.

Unlike C++, C and Java do not support templates. (There is a
proposal for adding template types to Java.)

Code reuse with parametric polymorphism and overloading:
It is clear that with parametric ploymorphism, the  same function body is
reused to deal with different datatypes. The basic property of a parametrically
polymorphic function is that it does not need to "look below" a certain
level of some data structure. For instance, the "min" function above
did not need to look inside of each array element. Similarly, one
can think of "length" and "append" functions that can operate on linked
lists of all types, without looking at the specific element type. 

With oveloading, there is no reuse of the overloaded function, since there is
in fact a different function body corresponding to each argument type.
However, client code that calls a overloaded function can be reused.
For instance, let C be a class, with subclasses C1,...,Cn. Also let
"f" be a virtual method of class C (and hence its subclasses). We can now
write client code that can apply the function uniformly to elements of
an array, each of which is a pointer to an object of type C1,...,Cn.

void
g(int size, C *a[]) {
   for (int i = 0; i < size; i++)
      a[i]->f(...);
}

Now, the body of function g (which is a client of the function f) can
be reused for arrays that contain objects of type C1 or C2 or ... or Cn,
or even a mixture of these types. 

Type equivalence
-------------------

1. Structural equivalence: two types are equivalent if they 
        are defined by identical type expressions.
   -- Issues: what components are counted? array range? record labels?
      Typically: array ranges are not considered as part of the type,
                 but record labels are considered part of the type.

2. Name equivalence: two types are equal if they have the same name.

3. Declaration equivalence: two types are equivalent if their 
     declarations lead back to the same original type expression
     by a series of redeclarations. 

Structural equivalence is the lest restrictive notion of type equivalence
among the above three, while name equivalence is the most restrictive.
Declaration equivalence is in between these two notions.

Pure name equivalence is not very useful:
    TYPE t1 = ARRAY [1..10] of INTEGER;
    TYPE t2 = t1;

  t1 and t2 are not equivalent. In
     v1: ARRAY [1..10] OF INTEGER;
     v2: ARRAY [1..10] OF INTEGER;  
  v1 and v2 have different types!

Using the notion of structural equivalence, t1 and t2 are equivalent;
v1 and v2 have equivalent types.

Using declaration equivalence, t1 and t2 are equivalent, but the
types of v1 and v2 are treated to be distinct.

Declaration equivalence:
   types whose declarations lead back to the same original type expression
     by a series of redeclarations (of the form type t1 = t2, or typedef
        TE tn).

        Pascal, Modula use decl equivalence
        In C, decl equiv used for structs and unions, structual
           equivalence for other types such as pointers and arrays.

   struct {
        int a ;
        float b ;
    } x ;
    struct {
        int a ;
        float b ;
    } y ;

   then x and y are structure equivalent but not declaration
   equivalent.

   typedef int* intp ;
   typedef int** intpp ;
   intpp v1 ;
   intp *v2 ;

   then v1 and v2 are structure equivalent.

Type compatibility : Weaker notion than type equivalence. Type
compatibility rules are different for different operators. 
We give an example here, corresponding to the assignment operator.

   v = expr
   is meaningful if type of <expr> is compatible with type of v.

   Compatibility in this case is based on a subtype relationship, i.e.,
   if the type of expr is a subtype of the type of v, then there is 
   compatibility.
   Example:
     in most languages, assigning integer value to a real variable
     is permitted, since integer is a subtype of real.

     in OO-languages, an object of a derived type can be assigned to 
     an object of the base type.

  Procedure parameter passing uses the same notion of comptibility
  as assignment. (There may be exceptions to this in some languages.)
  This is because a procedure call can be though of as proceding in
  two steps:
    -- assignment of actual parameter expressions to the formal
       parameters of the procedure
    -- execution of the procedure body

   Note: formal parameters are the parameter names that appear in the
         function declaration. The actual parameters are the expressions
         that appear at the point of function call.



Type checking
--------------

 Static (compile time) :
   Benefits
    - no run-time overhead
    - programs safer/more robust
  Dynamic (run-time) :
   Disadvantages
    -- runtime overhead
      -- maintaining type info at runtime
      -- performing type checks at runtime
   Benefits
    - more flexible / more expressible
      e.g., C++ allows casting of subclass to superclass (always type-safe).
                        superclass to subclass (not necessarily type-safe).
            Since C++ is statically typed, there is no way to check if the
            second form of casting is safe at runtime. In contrast, Java
            uses a combination of static and dynamic type-checking. This
            enables Java to check the potentially unsafe casts at runtime
            to see if they are OK.

Strongly typed language: programs in such languages will execute
  without producing uncaught type errors at runtime
  e.g., no invalid memory access
           -- no seg fault
           -- array index out of range
           -- access of null pointer

Type checking relies on type compatibility and type inference
     rules. Type inference rules are used to infer types of
     expressions. e.g., type of (a+b)+c is inferred from type of a, b
     and c and the inference rule for operator +
   Type inference rules typically operate on a bottom-up
     fashion. Given type of e1 and w2, the fule specifies the type of
      e1 op e2
     for each operator op.
   e.g.,
             +:real
             /\
            /  \
           /    \
          /      \
         +:real   c:real
        /\
       /  \
      /    \
     /      \
    a:int   b:real

  In SML, type inference rules cature bottom-up as well as top-down
    flow of type info.
   Top-down:
      fun f x y = (x+y): real
                 f:real
                 /\
                /  \
               /    \
              /      \
             x:real   y:real
         Here types of x and y are inferred from return type of f
         (real).

   Most of the time SML programs don't require type declaration.

Type conversion
   EXPLICIT: Functions are used to perform conversion.
                      strtol, atoi, itoa in C; real and int etc.
   IMPLICIT conversion (coercion)
     e.g., if a is real and b is int then type of a+b is real
           Before doing the addition, b must be converted to a real value.
           This conversion is done automatically.
   Casting (as in C)
   Invisible conversion: in unions
             If you store a value in the integer field of a union, but
             then access a float field, then you will get unpredictable
             results: it would be the hardware representation of an integer 
             interpreted as a floating point number.