Introduction to Programming in ATS:
PrevNext

Chapter 17. From Genericity to Late-Binding

Table of Contents
Genericity of Template Implementations
Example: Generic Operations on Numbers
Templates as a Special Form of Functors
Example: Templates for Loop Construction
Template-Based Support for Late-Binding

The support for function templates in ATS is deeply ingrained in the design and implementation of ATS. Primarily, function templates are meant to provide a general approach to code reuse in ATS that is highly flexible (in terms of applicability) while incurring minimal run-time overhead if any. Both ATSPRE (that is, ATSLIB/prelude) and ATSLIB/libats are nearly entirely template-based, and the templates in these libraries are for use by atsopt to generate C code that implements template instances in the ATS source being compiled. The library files of ATS for linking (libatslib.a and libatslib.so) are minimal, and they are not even necessary for compiling ATS source into executable binaries.

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

Genericity of Template Implementations

As is briefly explained in Part I of the book, function templates can be seen as a natural solution to the problem of supporting parametric polymorphism in the presence of native unboxed data. However, function templates can do much more than just supporting parametric polymorphism. Let myprint be a function template of the following interface: 

fun{a:t@ype} myprint (x: a): void

Given a value, myprint is supposed to print out some kind of representation for this value. For example, we can implement myprint as follows: 

implement{a} myprint (x) = print_string "?"

This implementation of myprint is often referred to as a (fully) generic template implementation due to no restriction being imposed on the template parameter. Following is another way to code the same implementation: 

implement(a) myprint<a> (x) = print_string "?"

Clearly, the above generic implementation of myprint is unsatisfactory as it outputs no specific information on a given value. We may want to implement myprint as follows for only values of the type int: 

implement myprint<int> (x) = print_int (x)

where print_int is called to print out a given integer. This implementation of myprint is often referred to as a specific template implementation due to the template parameter being bound to a specific type (that is, int in this case). The following code implements myprint for list-values (that is, values of type List(T) for some type T): 

implement(a)
myprint<List(a)> (xs) =
case+ xs of
| list_nil () => ()
| list_cons (x, xs) =>
    (myprint<a> (x); myprint<List(a)> (xs))

This implementation of myprint is often referred to as a partially generic template implementation. In order for an instance of myprint to use this implementation, the template parameter for the instance must be of the form List(T) for some type T. As an example, the following code calls an instance of myprint to print out a list of two integer lists: 

(*
** The output is "0123401234"
*)
val ys = $list{int}(0,1,2,3,4)
val yss = $list{List(int)}(ys, ys)
val ((*void*)) = myprint<List(List(int))> (yss)
val ((*void*)) = print_newline((*void*))

Implementations of a function template can be ordered according to an obvious partial ordering referred to as genericity ordering: The genericity of one implementation is less than or equal to that of another one if the former implementation is an instance of the latter one. Please note that the first-fit (instead of best-fit) strategy is employed to locate the template implementation needed for compiling a given template instance. More specifically, locating the template implementation for a particular template instance follows the standard principle of lexical scoping to search for the first one that is available for use.

In practice, there is quite a bit of subtlety in locating a template implementation for a template instance. Let myprint2 be a function template of the following interface: 

fun{a:t@ype} myprint2 (x: a): int

Following is a partially generic implementation of myprint2: 

//
implement(a)
myprint2<List(a)> (xs) =
case+ xs of
| list_nil () => ()
| list_cons (x, xs) =>
    (myprint<a> (x); 1 + myprint2 (xs))
//

This template implementation actually behaves very differently from what one might have expected. Note that the template parameter of the called instance of myprint2 in the body of the implementation is synthesized to be a type of the form list(a, N) for some static term N (of the sort int). As this form can never match List(T) for any type T, the called instance of the template myprint2 cannot be compiled according to the given template implementation of myprint2. This issue can be readily fixed by passing explicity the type List(a) (as a template parameter) to the called instance of myprint2: 

//
implement(a)
myprint2<List(a)> (xs) =
case+ xs of
| list_nil () => ()
| list_cons (x, xs) =>
    (myprint<a> (x); 1 + myprint2<List(a)> (xs))
//

The instance myprint2<List(a)> in this example is often referred to as a recursive instance. In general, it is a good programming practice to avoid using recursive instances. For example, the following equivalent implementation of myprint2 makes no use of recursive instances: 

//
implement(a)
myprint2<List(a)>
  (xs) = let
//
fun
aux
(xs: List(a)): int =
//
case+ xs of
| list_nil () => 0
| list_cons (x, xs) => (myprint<a>(x); 1 + aux(xs))
//
in
  aux (xs)
end // end of [myprint2<List(a)>]
//

Please find on-line the file myprint.dats containing the entirety of the code presented in this section plus some testing code.

PrevHomeNext
Programming with Function TemplatesUpExample: Generic Operations on Numbers