Introduction to Programming in ATS:
PrevChapter 17. From Genericity to Late-BindingNext

Templates as a Special Form of Functors

Many uses of higher-order functions can be readily replaced with function templates in ATS. In particular, higher-order functions are often implemented in ATS based on the corresponding function templates. Let us start with a concrete example. Following is a standard implementation of list mapping as a higher-order function (template): 

//
extern
fun
{a:t@ype}
{b:t@ype}
list_map_fun{n:nat}
  (xs: list(a, n), fopr: a -> b): list_vt(b, n)
//
implement
{a}{b}
list_map_fun (xs, fopr) = let
//
fun
aux{n:nat}
  (xs: list(a, n)): list_vt(b, n) =
(
case+ xs of
| list_nil() => list_vt_nil()
| list_cons(x, xs) => list_vt_cons(fopr(x), aux(xs))
)
//
in
  aux(xs)
end // end of [list_map_fun]
//

Given a list of cerntain length and a function (which is envless), list_map_fun returns a linear list of the same length. Unfortunately, list_map_fun cannot be called on a list and a closure-function. We certainly can implement a variant of list_map_fun of the following interface by essentially duplicating the implementation of list_map_fun: 

//
extern
fun
{a:t@ype}
{b:t@ype}
list_map_cloref{n:nat}
  (xs: list(a, n), fopr: a -<cloref1> b): list_vt(b, n)
//

While list_map_cloref can be called on a list and a closure-function, the closure-function that is formed at run-time to be passed to a call to list_map_cloref most likely becomes garbage immediately after the call returns. Without garbage collection (GC), the memory for storing the closure is leaked. We surely have many good reasons for avoiding using a higher-order function like list_map_cloref when doing embedded programming in ATS.

A proper way to implement list mapping (as I see it) is given as follows: 

//
extern
fun
{a:t@ype}
{b:t@ype}
list_map{n:nat}
  (xs: list(a, n)): list_vt(b, n)
//
extern
fun
{a:t@ype}{b:t@ype} list_map$fopr(x: a): b
//
implement
{a}{b}
list_map (xs) = let
//
fun
aux{n:nat}
  (xs: list(a, n)): list_vt(b, n) =
(
case+ xs of
| list_nil() => list_vt_nil()
| list_cons(x, xs) => list_vt_cons(list_map$fopr<a><b>(x), aux(xs))
) (* end of [aux] *)
//
in
  aux(xs)
end // end of [list_map]
//

The function template list_map is given in a style that is often referred to as being functorial: list_map can be thought of as a functor in Standard ML that applies to a module consisting of a single function list_map$fopr. In SML, each argument of a functor, which itself is a module, needs to be constructed and then passed to the functor explcitly. In ATS, the template implementation needed for compiling a particular template instance is located through a search procedure (that follows the standard principle of lexical scoping).

With list_map, we can implement list_map_fun as follows in a straightforward manner: 

implement
{a}{b}
list_map_fun(xs, fopr) = let
//
implement list_map$fopr<a><b> (x) = fopr(x)
//
in
  list_map<a><b> (xs)
end // end of [list_map_fun]

Please note that list_map$fopr being implemented inside the body of list_map_fun allows the implementation to gain direct access to the argument fopr of list_map_fun. It is in this sense that templates in ATS are often referred to as embeddable templates as they can be directly implemented in the bodies of functions. We can implement list_map_cloref similarly as follows: 

implement
{a}{b}
list_map_cloref(xs, fopr) = let
//
implement list_map$fopr<a><b> (x) = fopr(x)
//
in
  list_map<a><b> (xs)
end // end of [list_map_cloref]

For those who are familiar with functors in SML, the implementation of list_map_fun and list_map_cloref should clearly remind them of functor application.

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

PrevHomeNext
Example: Generic Operations on NumbersUpExample: Templates for Loop Construction