A Tutorial on Programming Features in ATS: | ||
---|---|---|

<<< Previous | Next >>> |

A higher-order function is one that takes another function as its argument. Let us use BT to range over base types such as char, double, int and string. A simple type T is formed according to the following inductive definition:

BT is a simple type.

(T

_{1}, ..., T_{n}) -> T_{0}is a simple type if T_{0}, T_{1}, ... T_{n}are simple types.

*order*(BT) = 0*order*((T_{1}, ..., T_{n}) -> T_{0}) =*max*(*order*(T_{0}), 1 +*order*(T_{1}), ..., 1 +*order*(T_{n}))

Given a function f of some simple type T, we say that f is a
*n*th-order function if *order*(T) = *n*. For
instance, a function of the type (int, int) -> int is 1st-order, and a
function of the type int -> (int -> int) is also 1st-order, and a
function of the type ((int -> int), int) -> int is 2nd-order. In
practice, most higher-order functions are 2nd-order.

As an example, we implement as follows a 2nd-order function find_root that takes as its only argument a function f from integers to integers and searches for a root of f by enumeration:

fn find_root (f: int -<cloref1> int): int = let fun aux ( f: int -<cloref1> int, n: int ) : int = if f (n) = 0 then n else ( if n <= 0 then aux (f, ~n + 1) else aux (f, ~n) ) // end of [if] in aux (f, 0) end // end of [fint_root] |

As another example, we implement as follows the famous Newton-Raphson's method for finding roots of functions on reals:

typedef fdouble = double -<cloref1> double // macdef epsilon = 1E-6 (* precision *) // // [f1] is the derivative of [f] // fn newton_raphson ( f: fdouble, f1: fdouble, x0: double ) : double = let fun loop ( f: fdouble, f1: fdouble, x0: double ) : double = let val y0 = f x0 in if abs (y0 / x0) < epsilon then x0 else let val y1 = f1 x0 in loop (f, f1, x0 - y0 / y1) end // end of [if] end // end of [loop] in loop (f, f1, x0) end // end of [newton_raphson] |

// square root function fn sqrt (c: double): double = newton_raphson (lam x => x * x - c, lam x => 2.0 * x, 1.0) // cubic root function fn cbrt (c: double): double = newton_raphson (lam x => x * x * x - c, lam x => 3.0 * x * x, 1.0) |

Higher-order functions can be of great use in supporting a form of code sharing that is both common and flexible. As function arguments are often represented as heap-allocated closures that can only be reclaimed through garbage collection (GC), higher-order functions are used infrequently, if ever, in a setting where GC is not present. In ATS, linear closures, which can be manually freed if needed, are available to support higher-order functions in the absence of GC, making it possible to employ higher-order functions extensively in systems programming (where GC is unavailable or simply disallowed). The details on linear closures are to be given elsewhere.

<<< Previous | Home | Next >>> |

Metrics for Termination Verification | Up | Parametric Polymorphism |