Introduction to Programming in ATS:
<<< PreviousNext >>>

Parametric Polymorphism

Code sharing is of paramount importance in programming language design. In a typed programming language, we often encounter a situation where the same functionality is needed for values of different types. For instance, we need a function to compute the length of a list while the elements in the list may be characters, integers, strings, etc. Evidently, we want to avoid implementing such a function for each element type as it would probably be the worst form of code duplication otherwise. We want to implement a single function that can be applied to any list to compute the length of the list. The length-computing function parameterizes over the element type of a list it is applied to, and it behaves uniformly regardless what the element type is. This is a form of code sharing that is given the name: 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. 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 for 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))
// end of [compose]

val plus1 = lam (x:int): int =<cloref1> x+1
val times2 = lam (x:int): int =<cloref1> x*2

val f_2x_1: cfun (int, int) = compose (times2, plus1)
val f_2x_2: cfun (int, int) = compose (plus1, times2)

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 it. Similarly, the value f_2x_2 represents the function that adds 1 to its integer argument and then multiplies it by 2.

In ATS, function templates are typechecked but not compiled. Only instances of a function template can be compiled. 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 share one function in C. In particular, if both T1 and T2 are boxed types, which are always given the same name, only one function in C is generated for them.

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

<<< PreviousHomeNext >>>
Example: Evaluating Integer ExpressionsUpPolymorphic Functions