/* ****************************************************** */
    /* *** What Mother Never Told You About C++ Templates *** */
    /* ****************************************************** */

using namespace std;
#include<iostream>
#include<string>

// polymorphic linked lists:

template <typename T>
class cell
{
 public:
   T head;
   cell<T> *tail;
  cell(T h, cell<T> *t) { head  =h;  tail = t; }
  ~cell() { if (tail!=NULL) delete(tail); }
};

template <typename T>
int length(cell<T>* l)
{
  int ax = 0;
  while (l!=NULL) { l=l->tail; ax++; }
  return ax;
}


// Templates only let you write "naturally" polymorphic functions
// easier.  They cannot automatically provide the kind of abstraction
// that inheritance provides.

// The following "polymorphic" function tries to subtract one from every
// element in a linked list.  The element can be an integer, or an
// object representing a fraction, for which subtraction is a different 
// algorithm.  Having templates would not help here.  Furthermore,  they
// can lead to the following situation found in main beneath.

template <typename A>
void subone(cell<A>* l)
{
  cell<A>* i = l;
  while (i!=NULL)
    {
      l->head = l->head - 1;
      i = i->tail;
    }
}

int main()
{
  cell<int> *IL = new cell<int>(2, new cell<int>(4, new cell<int>(6,NULL)));
  cell<string> *SL = new cell<string>("abc", new cell<string>("def", NULL));
  cell<double> *DL = new cell<double>(1.5, new cell<double>(2.5,NULL));
  cout << length(IL) << endl;
  cout << length(DL) << endl;
  cout << length(SL) << endl;
  subone(IL);
  subone(DL);
  
  // so far so good, but ...

  
  //subone(SL);   // ooooops!  How do I subtract one from a string?
  return 0;
}

// how to "type check" the template code itself?  Construct a minimal
// class:

class Arbitrary {};
cell<Arbitrary> *a;  // will this compile

/*
   The problem here is that C++ lacks the ability to type check parametrized
types.  No type checking is done until the templates are actually instantiated.


There are two problems here:

1.  You're not supposed to look at the machine code generated, because
it's embarassing.  For each possible instantiation of a type variable,
there is a separate copy of code.  If you have 8 different
instantiations, you get 8 copies.  If you have templates with multiple
type variables, you'll multiply the number of times it generates code.
In contrast, more sophisticated type systems (C# 2.0/Java 1.5) allow
you to specify a naturally polymorphic function (such as length of a
linked list), and really powerful type systems (ML) will even deduce
polymorphism from your code automatically.

2.  The second problem with C++ templates is that, suppose you're
asked to develop a "template library" that has generic code to do all
sorts of neat stuff, like subtracting one from every element of a list
:-).  You wrote it, compiled it, tested it with a few examples, and
announced that it "works".  Then somebody comes along and tries to
instantiate your template with string, and it doesn't compile.  You
get blamed.  In order to prevent this from happening, we must have the
ability to type check the generic code statically.  That is, the
parameterization of the type variable should be constrained so that it
can only be instantiated with certain kinds of types.

----------- ML Polymorphism -------------

The ML language implements the typed lambda calculus just as Scheme
implements the untyped version.  The following code in ML defines a
data type for linked lists and the length function on it.

- datatype 'a seq = nil | cons of ('a*'a seq);

- fun seqlength nil = 0
=   | seqlength (cons(head,tail)) = 1 + seqlength(tail);

ML infers that the type of seqlength is:

val seqlength = fn : 'a seq -> int

That is, it is polymorphic and can be used on lists containing data of
any type.  

Of course, it's also possible to write such functions naturally in untyped
languages such as scheme or perl, but one looses the benefits of a type
system - that is, certain errors can be caught at compile time.

Microsoft is developing its own version of ML, called F#.

*/