/* What is "polymorphism?"  Technically, we can call a piece of code
polymorphic if it can be applicable to multiple data types.  But the issue
isn't quite so simple.

Consider the following scheme program, which returns the length of a
linked list:

(define (length M) (if (null? m) 0 (+ 1 (length (cdr M)))))

This function is "polymorphic" because it would work on lists of
numbers, strings, or even lists of lists.  It is completely insensitive to
the type of element stored inside the list.

But now consider the following function, which returns the product of all
the values in a list

(define (product M) (if (null? M) 1 (* (car M) (product (cdr M)))))

This function would work on lists of integers as well as a list of floating
point numbers:

(product '(2 3 4))   ; returns 24
(product '(2.3 2.0)) ; returns 4.6

So is it polymorphic? Well, it would only work on datatypes for which
the symbol '*' represents a valid operation.  Clearly this function is
"polymorphic" in a very different sense from the length function
above.  Here the '*' symbol DISPATCHES to different procedures
depending on the type of values its applied to.  The underlining
procedure for two's complement integer multiplication is very
different from floating point multiplication.  It is polymorhpic only
if somebody DOES THE WORK of providing and implementing different algorithms
for the different data types.  This is very different from the kind of
polymorphism achieved with the length function.

In order to fully understand polymorphism and how to best implement it,
we must be clear about something first: 

  "Polymorphism" is first and foremost a characteristic of the *algorithm*,
  not of the program or programming language.  

The potential to write polymorphic code must be inherent in the nature of
the algorithm being implemented. Both length and product has the potential
to be meaningful in a variety of contexts.  But their implementation 
requires different techniques.  We can distinguish between two kinds of
polymorphic code:

  1. Natural polymorphism (aka parametrically polymorphic): this is
     examplified by the length function.  Such functions only examine the
     structure of data, and not its content.  The data "type" is therefore
     entirely parametric to the code.

  2. Constructed polymorphism (aka ad-hoc polymorphic): this is examplified
     by the product function.  In order to have the code applicable to
     different types, distinct algorithms must be provided and the programming
     language must provide a mechanism to dispatch to the correct procedure.

Another example of a naturally polymorphic function would be a function to
compute the depth of a binary search tree: it is ONE ALGORITHM that is
naturally applicable to trees containing any type of data.

On the other hand, the "+" operator of most porgramming languages is
only polymorphic in the second sense: it is ONE SYMBOL that dispatches
to different procedures.  In Java/C# for example, it can represent
integer or floating point addition, or string concactenation.  In
C#/C++, it can be further overloaded to have a user-defined meaning.
But the point is that somewhere somebody has to provide different
algorithms before the apparent polymorphism is realized.

-----------------------------------------------------------------------

The next question is, how do we implement either kind of 
polymorphism in a typed oop language such as C#.

In an untyped language such as Scheme/Perl, implementing functions
that are naturally polymorphic is simple, since we don't specify type
information anyway.  It may appear at first that a type system actually
gets in the way of writing such functions easily.  In C#/Java, we appear
to have the following options (neither of which are as simple).
*/
using System;

// first version: use the 'object' supertype to represent   ********
// arbitrarily typed elements

class olist
{
   public object car;
   public olist cdr;
   public olist(object a, olist d) {car=a; cdr=d;}
   public void print() 
   { for(olist i=this; i!=null; i=i.cdr)
      { Console.Write(i.car+" "); }
     Console.WriteLine("");
   }

   public int length()
   { 
     if (cdr==null) return 1; 
     else return 1 + cdr.length();
   }

   public int intsum()  // only works with list of integers
   {
     int ax = 0;
     for (olist i=this;i!=null;i=i.cdr) 
	ax += (int)i.car;
     return ax;
   }

   // how do I write a polymorphic version of sum?
}// olist

// 'object' is the top of the inheritance tree.  But to 
// use 'object' to implment functions that are naturally
// polymorphic is not the right use of inheritance.  Until a
// few years ago, however, the above approach was the
// only one available.  You'll still find a lot of Java code that
// are like the above.  There are two problems with this style of
// programming. 
//   1. run-time type casting is needed to cast object to Integer or
//      other useful types.  This is time-consuming, both for the programmer
//      and at runtime, since type casting involves looking up tags, etc...
//   2. FAR more importantly, the above program loses all static type
//      information.  It becomes like scheme/perl or C with the void* type.
//      There cannot be static type checking with type "object".
//
//   Try the following with the above class:
//   olist M = new olist(1,new olist(2,new olist(3,null)));
//   int x = (int)M.car % (int)M.cdr.car; // type casting needed.
//   olist L = new olist("ab",new olist("cd",new olist("yz",null)));
//   int y = (int)L.car / (int)L.cdr.car; //it compiles! run for your lifes!

/* The type-casting from a superclass is clearly a characteristic
   of modern OOP languages.  Along with interfaces, abstract classes,
   inheritance and most significantly dynamic dispatch, these mechanisms
   are used to *construct* polymorphic code.  But is the superclass 'object'
   being used in the right way here?
*/

// Second version: parametric types ("Generics")  *****************
// But now we can also write the following (not C++ templates)
class plist<T>
{
   public T car;
   public plist<T> cdr;
   public plist(T a, plist<T> d) {car=a; cdr=d;}

   public void print() 
   { for(plist<T> i=this; i!=null; i=i.cdr) 
      { Console.Write(i.car+" "); }
     Console.WriteLine("");
   }
   // null is bult-in polymorphic

   public int length()
   { 
     if (cdr==null) return 1; 
     else return 1 + cdr.length();
   }

   // dispatch to different procedures, determined by subtype.
   public virtual T sum() { return default(T); } // should really use interface
  // default(T) is the identity of the T datatype ("", 0, or null);
  // problem: can't just write one generic procedure.

  // not-completely-natural polymorphic function:

  public delegate T addfun(T a, T b);

  public T polysum(addfun f)  // take function to "add"
  {
     if (cdr==null) return car;
     else return f(car, cdr.polysum(f));
  }
  // The above approach can also be adopted in Scheme/Perl/C

} // plist<T>

class ilist : plist<int>
{
   public ilist(int a, ilist d): base(a,d) {} // constructor
   public override int sum()
   { if (cdr==null) return car; else return car+cdr.sum(); }
}// ilist


public class polymorph
{
   public static void Main()
   {
      plist<int> A = new plist<int>(2,new plist<int>(4,null));
      ilist B = new ilist(1,new ilist(3,new ilist(5,null)));
      int x = B.car + B.cdr.car; // no need to type cast
    
      A.print();  B.print();
//      Console.WriteLine(default(ilist)==null);

      plist<string> S;
      S = new plist<string>("hello ",new plist<string>("world",null));
      //int y = S.car - S.cdr.car;  // compiler error, we're safe!
  
      string sum = S.polysum(delegate (string a,string b) {return a+b;});

      Console.WriteLine(sum);
   }//main
}

/* alternatively, I can also CONSTRAIN the type parameter T as follows:

class plist<T> where T:IComparable<T>
{
}

The built-in IComparable interface (Comparable in Java) is as follows:

interface IComparable<in T>
{
   int CompareTo(T x);
}

Any class that implements this interface must implement a CompareTo
method that returns 0 for equality, negative integer for "<" and positive
integer for ">".  For example:

class student : IComparable<student>
{
   int id;
   // boring stuff omitted.
   public int CompareTo(student x) { return id - x.id; }
}

The word "in" in <in T> means that T is "contravariant" - a recent
refinement of generics in C#.  It means that T can be instantiated by
a more general type (supertype) - more about that later, but let's say I
have

class undergrad : student, IComparable<undergrad>
{
 // I can inherit CompareTo from the student superclass, even though that
 // function expects a student, not an undergrad as a parameter: that is,
 // IComparable<undergrad> can be instantiated by an instance of 
 // IComparable<student>.  
}

*/

/* What is "polymorphism"?  When all is said and done, polymorphism is
   nothing but another word for "abstraction".  A polymorphic piece of
   code abstracts away specifics of particular types.  Just as
   "protocol" gives us abstraction in networking, the mechanisms that
   support polymorphism give us abstraction in programming languages.
   This can be achieved, for example, using higher order functions, or
   by using inheritance and dynamic dispatch.  The new C#/Java feature
   of "Generics" or parametric types simplifies the writing of
   functions that are naturally polymorphic, and returns static-type
   checking to polymorphic code.  But inheritance or some other
   mechanism is still needed to implement the different versions of
   algorithms needed to support polymorphism.  
*/