Chapter 5. Higher-Order Functions

In ATS, an anonymous function can be defined as a lambda-abstraction. For instance, the square function on integers can be defined as follows:

where the keyword lam is for constructing a lambda-abstraction. For defining a recursive anonymous function, the keyword fix is needed. For instance, the factorial function can also be implemented as follows: A function value can be passed as a function argument just like any other values, and a higher-order function refers to one that takes a function value as its argument. As far as terminology is concerned, a first-order function takes no function arguments; a second-order function takes a first-order function as its argument; a third-order function takes a second-order function as its argument; etc. In practice, higher-order functions are overwhelmingly second-order ones.

At this point, I want to digress a bit by advocating a so-called build-your-own-library approach to learning programming. Often a limitation faced by someone learning programming is that one does not have many opportunities to actually use the code written by oneself. For instance, we rarely see a case where someone makes extensive use of a data structure (such as hash table and associative map) implemented by his or her own. Most likely, one implements some data structure for the purpose of learning about it and then throws the code away afterwards. My own experience strongly indicates that one can learn a great deal more about programming if one insists on calling library functions implemented by oneself. From this point on, I will gradually build a library for this book and I encourage everyone reading the book to study the source code for the library on-line.

As an example of higher-order function, let us implement a commonly used library function of the name int_foreach:

Note that the type cfun(int, void) is just a shorthand for (int) -<cloref1> void, which is assigned to a closure-function that takes an integer argument and returns void. There are two kinds of functions in ATS: envless function and closure-function; the former is just a function in the sense of C: a function pointer to some memory location where a sequence of instructions is stored; the latter is essentially a function pointer paired with an environment (represented as a tuple of values) for certain paramemters. For an envless function from int to void, its type is written as (int) -> void or (int) -<fun1> void. While turning an envless function into a closure-function is straightforward, there is no generic method for turning a closure-function into an envless function. Note that each function argument of a higher-order function is usually chosen to be a closure-function so as to make the higher-order function more applicable.

A standard implementation of int_foreach is given as follows:

For testing fact (that implements the factorial function), we can simply make a call to int_foreach as follows:

As another example, let us implement a higher-order function of the name int_foldleft as follows:

Note that int_foldleft is declared as a function template. For someone who knows the standard left-folding function on a list (for folding the list from left to right), int_foldleft does essentially the same as left-folding a list consisting of integers from 0 to n-1, where n is the first argument passed to int_foldleft. For instance, we can implement the factorial function as follows: If we want a function sqsum to sum up the squares of the first n positive integers for any given natural number n, we can implement it with a call to int_foldleft as well:

Higher-order functions like int_foreach and int_foldleft are often referred to as combinators. By making use of combinators, one can often shorten the code needed for solving a particular problem. Much more importantly, combinators can help one formulate high-level solutions that tend to significantly reduce the need for directly handling minute programming details. As we all know too well, handling such details is a very rich source for programming errors.

As the last example in this chapter, let us see a combinator-based implementation of matrix multiplication. In imperative programming, the following style of code is common:

where one for-loop is embedded in the body of another for-loop. A combinator int_cross_foreach is given as follows for doing the same: The following function matrix_mulby takes six arguments p, q, r, A, B, and C, where it is assumed that A, B, and C are matrices of dimensions p by q, q by r, and p by r, respectively: Note that the function templates gadd_val_val and gmul_val_val are for addition and multiplication operations on generic numbers of type a, respectively. What matrix_mulby does is simply updating C with C plus the product of A and B.

In ATS code, dot-notation is often seen for calling combinators. For instance, we can introduce the following curried version of int_foreach and int_foldleft plus some overload declarations:

We can then implement the functions fact and testfact as follows: Note that TYPE{int} is a form of type-annotation; it indicates to the typechecker of ATS that the template parameter for the involved instance of int_foldleft_method is int.

Please find on-line the entirety of the code used in this chapter. The multable example mentioned previously is modified a bit so as to make use of the int_foreach_method combinator.