Grok Parametric polymorphism

This page is a part of the Grokking Nemerle tutorial.

Parametric polymorphism is a wise way to say that function can operate on values of any type. Kind of System.Object and/or void* on steroids. This is very much like Generics in C# 2.0 or Java 5.0 and somewhat less like templates in C++.

Both functions and types can be parameterized over types.

Simple polymorphism

Here we define a list of values of any type (it is also defined in Nemerle standard library but this is not the point here).

variant list [T] {
  | Cons { hd : T; tl : list [T]; }
  | Nil
}

Here we used T as a type parameter to the list type. The ML-lovers would rather write 'a instead and read it alpha (it is a convention to use identifiers starting with an apostrophe for type parameters). They are allowed to do so, as the apostrophe is allowed in identifiers in Nemerle. We will however stick to a C++-like convention.

In the body of the list definition T can be used like any other type name. It is called type variable in this scope.

Next we define the method parameterized on a type (it is reflected by listing [something] after Head). Since the algorithm of taking the head out of the list does not depend on the type of the actual values stored in the list, we can use the same T, but we could have used 'b or foobar42 as well. This method for list[int], list[string] and even list[list[int]] would look exactly the same. Therefore we can use generic T type.

You can see that the type of elements of the list (a parameter in list[T]) is used as return type of this method. This way we can ensure that we take an int out of list[int] and not some generic System.Object.

class List {
  public static Head[T] (l : list[T]) : T
  {
    match (l) {
      | Cons (hd, _) => hd
      | Nil =>
        throw System.ArgumentException ()
    }
  }
}

Constraints on type variables

It is sometimes necessary for types to be substituted for type variables to conform to some specific interface. This concept is known as F-bounded polymorphism. We will address this issue in more detail, as it is probably new for most readers.

For example the elements stored in a tree need to provide a comparison method. Thus, we can define an appropriate interface and then require 'a in Tree['a] to conform to it:

interface IComparable ['a] {
  CompareTo (elem : 'a) : int;
}

variant Tree['a] 
  where 'a : IComparable['a]
{
  | Node {
      left : Tree['a];
      elem : 'a;
      right : Tree['a];
    }
  | Tip
}

In fact the IComparable interface is already defined in the standard library, but that is not the point.

Now, once we ensured that elements in the tree conform to IComparable, we can use the CompareTo method. For example, to insert a thing into the tree we can use the following function:

module TreeOperations {
  public Insert['a] (t : Tree['a], e : 'a) : Tree['a]
    where 'a : IComparable['a]
  {
    match (t) {
      | Node (l, c, r) =>
        if (e.CompareTo (c) < 0)
          Node (Insert (l, e), c, r)
        else if (e.CompareTo (c) > 0)
          Node (l, c, Insert (r, e))
        else
          Node (l, e, r)
      | Tip =>
        Node (Tip (), e, Tip ())
    }
  }
}

The people familiar with C# or Java will ask why not simply use something like:

interface IComparable {
  CompareTo (elem : IComparable) : int;
}

variant Tree
{
  | Node {
      left : Tree;
      elem : IComparable;
      right : Tree;
    }
  | Tip
}

But this is only half good. The most often case for using a tree is to store elements of some specific type, for example strings. We don't want integers and strings to be stored in the same tree, for the very simple reason that we cannot compare integer with string in a reasonable way. Well, even if we could, we plainly cannot predict what other types beside integers and strings implement IComparable and thus can be passed to string's CompareTo.

But the design above makes it impossible to ensure statically whether we're using the tree with correct types. When inserting nodes to the tree we upcast them all to IComparable. We will get runtime exception when string's CompareTo is passed integer argument. The second drawback is that when we extract elements out of the tree, we need to downcast them to a specific type. This is second possibility for runtime errors.

To fully understand this issue please look at the following example:

interface IFrobincatable {
  Frobnicate (x : int) : void;
}

class C1 : IFrobincatable 
{
  public this () {}
  public Frobnicate (_ : int) : void {}
}

class C2 : IFrobincatable 
{
  public this () {}
  public Frobnicate (_ : int) : void {}
}

module M {
  f1['a] (o : 'a) : 'a
    where 'a : IFrobincatable
  {
    o.Frobnicate (3);
    o
  }

  f2 (o : IFrobincatable) : IFrobincatable
  {
    o.Frobnicate (3);
    C1 ()
  }

  Main () : void
  {
    def x1 = f1 (C1 ()); // x1 : C1
    def x2 = f1 (C2 ()); // x2 : C2
    def x3 = f2 (C1 ()); // x3 : IFrobincatable
    def x4 = f2 (C2 ()); // x4 : IFrobincatable

    ()
  }
}

In the Main function you can see what types get the x1, x2 etc values.