Introduction to Programming in ATS:
PrevNext

Chapter 5. Parametric Polymorphism

Table of Contents
Function Templates
Polymorphic Functions
Polymorphic Datatypes
Example: Function Templates on Lists
Example: Mergesort on Lists

Code sharing is of paramount importance in programming. In a typed programming language, we often encounter a situation where the same functionality is needed for values of different types. For instance, we may need to compute the length of a list while the elements in the list can be characters, integers, strings, etc. Evidently, we want to avoid implementing a list-length function for each element type as it would probably be the worst form of code duplication. We want to implement one single function that can be applied to any list to compute the length of the list. This list-length function parameterizes over the element type of a given list, and it behaves uniformly regardless what the element type is. This is a form of code sharing that is often referred to as parametric polymorphism, which should be distinguished from other forms of polymorphism such as inheritance polymorphism in object-oriented programming.

The code employed for illustration in this chapter plus some additional code for testing is available on-line.

Function Templates

A function template is a code template that implements a function. In the following code, two functions are defined to swap values: 

//
typedef charint = (char, int)
typedef intchar = (int, char)
//
fun swap_char_int (xy: charint): intchar = (xy.1, xy.0)
fun swap_int_char (xy: intchar): charint = (xy.1, xy.0)
//

If types are ignored, the bodies of swap_char_int and swap_int_char are identical. In order to avoid this kind of code duplication, we can first implement a function template swap as follows and then implement swap_char_int and swap_int_char based on swap: 

//
fun{
a,b:t@ype
} swap (xy: (a, b)): (b, a) = (xy.1, xy.0)
//
fun swap_char_int (xy: charint): intchar = swap<char,int> (xy)
fun swap_int_char (xy: intchar): charint = swap<int,char> (xy)
//

It should be noted that a function template is not a first-class value in ATS: There is no expression for representing a function template. The syntax {a,b:t@ype} following the keyword fun represents template parameters or arguments. The unusual symbol t@ype is a sort for static terms representing types of unspecified size, where the size of a type is the number of bytes needed for representing a value of the type (under the assumption that all of the values of the type have the same size). There is another sort type in ATS, which is for static terms representing types of size equal to one word exactly, that is, 4 bytes on a 32-bit machine or 8 bytes on a 64-bit machine. The syntax swap<char,int>, where no space is allowed between swap and < , stands for an instance of the function template swap in which the parameters a and b are replaced with char and int, respectively. The syntax swap<int,char> is interpreted similarly.

A different style of implementation of swap is given as follows: 

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

where the template parameters are given sequentially (instead of simultaneously). The following code shows how swap2 can be instantiated to form instances: 

fun swap_char_int (xy: charint): intchar = swap2<char><int> (xy)
fun swap_int_char (xy: intchar): charint = swap2<int><char> (xy)

Note that >< is a special symbol (of the name GTLT) and no space is allowed between > and <.

As another example, a higher-order function template for composing (closure) functions is given as follows: 

//
typedef
cfun (t1:t@ype, t2:t@ype) = t1 -<cloref1> t2
//
fun{
a,b,c:t@ype
} compose (
  f: cfun (a, b), g: cfun (b, c)
) :<cloref1> cfun (a, c) = lam x => g(f(x))
//
val inc_by_1 = lam (x:int): int =<cloref> x+1
val mul_by_2 = lam (x:int): int =<cloref> x*2
//
val f_2x_1 = compose<int,int,int> (mul_by_2, inc_by_1)
val f_2x_2 = compose<int,int,int> (inc_by_1, mul_by_2)
//

It should be clear that the value f_2x_1 represents the function that multiplies its integer argument by 2 and then adds 1 to the result. Similarly, the value f_2x_2 represents the function that adds 1 to its integer argument and then multiplies the result by 2.

In ATS, function templates are typechecked but not compiled to code in C. Instead, they are compiled to an intermediate form. Only instances of function templates are compiled to code in C. Suppose we have a function template foo taking one type parameter and two instances foo<T1> and foo<T2> are used in a program for some types T1 and T2. In general, one function in C is generated for each instance of foo when the program is compiled. However, if T1 and T2 have the same name, then the two instances may share one function in C.

Please note that I may simply use the name function to refer to a function template from now on if no confusion is expected.

PrevHomeNext
Example: Evaluating Integer ExpressionsUpPolymorphic Functions