Parametric Polymorphism

Parametric polymorphism (or polymorphism for short) offers a flexible and effective approach to supporting code reuse. For instance, given a pair (v1, v2) where v1 and v2 are a boolean a character, respectively, the function swap_bool_char defined below returns a pair (v2, v1):

fun swap_bool_char (xy: (bool, char)): (char, bool) = (xy.1, xy.0)

Suppose that integer values need to be swapped as well. This leads to the implementation of the following function swap_int_int:

fun swap_int_int (xy: (int, int)): (int, int) = (xy.1, xy.0)

The code duplication between swap_bool_char and swap_int_int is obvious, and it can be easily avoided by implementing a function template as follows:

fun{a,b:t@ype} swap (xy: (a, b)): (b, a) = (xy.1, xy.0)

Now the functions swap_bool_char and swap_int_int can simply be replaced with swap<bool,char> and swap<int,int>, respectively. The function template swap cannot be compiled into binary object code directly as the sizes of type variables a and b are unknown: The special sort t@ype is for classifying types whose sizes are unspecified. If swap<T1,T2> is used for some types T1 and T2 of known sizes, then an instantiation of swap is created where type variables a and b are replaced with T1 and T2, respectively, and the instantiation is compiled into binary object code. For those know the feature of templates in C++, this should sound rather familiar.

In contrast to swap, swap_type_type is defined below as a polymorphic function (rather than a function template):

fun swap_type_type {a,b:type} (xy: (a, b)): (b, a) = (xy.1, xy.0)

This function can be compiled into binary object code as the sizes of type variables a and b are known: The special sort type is for classifying types of size equal to exactly one word, that is, the size of a pointer. For example, the size of a string is one word, and the size of any declared datatype is also one word. Given strings str1 and str2, an application of swap_type_type to str1 and str2 can be written as follows:

swap_type_type {string,string} (str1, str2)

where the expression {string,string} is often referred to as a static argument. As in this case, most static arguments do not have to be supplied explicitly since they can be automatically inferred. However, such static arguments, if given, can often greatly enhance the quality and precision of the error messages reported in case of typechecking failure.