What is parametric polymorphism?

I keep talking about this so i want to give a "rough not very technical" idea what it is.

A polymorphic data structure is basically data structure abstracted over one or more types. For example array and list are candidates. The requirement is that these work for any type. The definition of these things usually involves using a type parameter, which is universally quantified over all types .. hence "parametric".

You can have an array of int, an array of string, .. an array of absolutely any type at all!

A parametrically polymorphic function is similar. But this comes with very heavy constraints. For example, consider the function which reverses the elements of an array. You need to be able to swap and or copy elements of ANY type, that's generally considered a universal operation on all types. Given a purely functional singly linked list, you can produce a new list with the elements reversed easily.

How about sorting an array?

NO. You can NOT sort an array with a just a function that accepts an array, because you need an ordering on the elements and not all types have such an ordering!

That's a bit restrictive, isn't it?

NO. It's not. It's completely general. What? You say? Aren't I contradicting myself?

Nope. I said "just a function that accepts an array". If you pass in to the function a comparison operator that works for ANY type, you can do it. I'm going to show a simpler example: "add up everything in an array":

fun addem[T] (a: varray[T], add: T * T -> T, var init:T) {
  for v in a perform init = add(init, v);
  return init;

See? if you pass in the add function that works on the values stored in the array you can do it, no problem. You can type check this function so that ANY instantiation for ANY type and addition operator must work without further type checking which in particular means to call this function you ONLY need to know the interface, not the implementation. In particular the interface is just the name of the function and its type .. this is why types are so important:

fun addem[T] : varray[T] * (T * T -> T) * T -> T

Now, parametric polymorphism has a problem. In complex algorithms, you may need to pass in a LOT of functions to do the work. On way to simplify this is to put all the functions into a record and just pass in the record.

Another way to simplify it is to pass in the record statically (at compile time). Which is what you do with type classes (Haskell) or interfaces (Chapel). Typically you have a type class and specify using it like:

fun default_addem[T where Addable[T]] (a: varray[T]) {
  var init = zero();
  for v in a perform init = Addable[T]::add(init, v)
  return v;

This is the same function body, but we find the add function in Addable[T]. This again can be type checked AND every call is guaranteed to be type correct BUT later, the compiler may fail to find Addable for a particular T. This is not a type error. It's constraint failure, or, if you like an instantiation error, or, "the programmer forgot to define that instance".

There is more than one way to make parametric polymorphism easier to use, by systematically packaging up commonly needed sets of operations, based on ALGEBRA.

The point is you HAVE to start first with parametric polymorphism as an extension to a core non-polymorphic language. Generics, where you just grab the methods from the point of instantiation ARE TOTALLY AND UTTERLY UNACCEPTABLE.

This form of construction CANNOT be type checked. Static typing REQUIRES all constructions be type checked before use. The ONLY question is how to get rid of them. Probably the best way is to deprecate them and add a new syntax for parametric polymorphism. That avoids breaking any code and gives users plenty of time to learn the new system and migrate over to using it. Maybe in 10 years you can actually disable generics with a `--legacy-generics' flag to turn them back on.

When you have something so completely wrong as generics in Chapel and C++, it's probably best not to fix it but simply add something new. It is tempting to say "well some Chapel generics are already parametrically polymorphic" so why not just keep the existing machinery? Again, you cannot do this, because without some positive indication you intended to be parametrically polymorphic, there's no way to report a definitive type error except at instantiation time, which is the actual problem.