**Table of Contents**- Functions as a Simple Form of Abstraction
- Function Arity
- Function Interface
- Evaluation of Function Calls
- Recursive Functions
- Evaluation of Recursive Function Calls
- Example: Coin Changes for Fun
- Tail-Call and Tail-Recursion
- Example: The Eight-Queens Puzzle
- Mutually Recursive Functions
- Mutually Defined Tail-Recursion
- Envless Functions and Closure-Functions
- Higher-Order Functions
- Example: Binary Search for Fun
- Example: A Higher-Order Fun Puzzle
- Currying and Uncurrying

Functions play a foundational role in programming. While it may be theoretically possible to program without functions (but with loops), such a programming style is of little practical value. ATS does provide some language constructs for implementing for-loops and while-loops directly. I, however, strongly recommend that the programmer implement loops as recursive functions or more precisely, as tail-recursive functions. This is a programming style that matches well with more advanced programming features in ATS, which will be presented in this book later.

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

Given an expression exp of the type double, we can multiply exp by itself to compute its square. If exp is a complex expression, we may introduce a binding between a name and exp so that exp is only evaluated once. This idea is shown in the following example:

Now suppose that we have found a more efficient way to do squaring. In order to take full advantage of it, we need to modify each occurrence of squaring in the current program accordingly. This style of programming is clearly not modular, and it is of little chance to scale. To address this problem, we can implement a function as follows to compute the square of a given floating point number: The keyword fn initiates the definition of a non-recursive function, and the name following it is for the function to be defined. In the above example, the function square takes one argument of the name x, which is assumed to have the type double, and returns a value of the type double. The expression on the right-hand side (RHS) of the symbol = is the body of the function, which is x * x in this case. If we have a more efficient way to do squaring, we can just re-implement the body of the function square accordingly to take advantage of it, and there is no other changes needed (assuming that squaring is solely done by calling square).If square is a name, what is the expression it refers to? It turns out that the above function definition can also be written as follows:

where the RHS of the symbol = is a lambda-expression representing an anonymous function that takes one argument of the type double and returns a value of the type double, and the expression following the symbol => is the body of the function. If we wish, we can change the name of the function argument as follows: This is called alpha-renaming (of function arguments), and the new lambda-expression is said to be alpha-equivalent to the original one.
A lambda-expression is a (function) value. Suppose we have a
lambda-expression representing a binary function, that is, a function
taking two arguments. In order to assign a type of the form (T1, T2) -> T
to the lambda-expression, we need to verify that the body of the function
can be given the type T if the two arguments of the function are assumed to
have the types T1 and T2.
What is stated also applies, *mutatis mutandis*, to
lambda-expressions representing functions of fewer or more arguments. For
instance, the lambda-expression lam (x: double): double => x *
x can be assigned the function type (double) -> double, which
may also be written as double -> double.

Assume that exp is an expression of some function type (T1, T2) -> T. Note
that exp is not necessarily a name or a lambda-expression. If expressions
exp_{1} and exp_{2} can be assigned
the types T1 and T2, then the function application
exp(exp_{1}, exp_{2}), which may
also be referred to as a function call, can be assigned the type T. Typing
a function application of fewer or more arguments is handled similarly.

Let us now see an example that builds on the previously defined function square. The boundary of a ring consists of two circles centered at the same point. If the radii of the outer and inner circles are R and r, respectively, then the area of the ring can be computed by the following function area_of_ring:

Note that the subtraction and multiplication functions are of the type (double, double) -> double and square is of the type (double) -> double. It is thus a simple routine to verify that the body of area_of_ring can be assigned the type double.