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

<<< Previous | Next >>> |

Tail-recursion is of crucial importance in functional programming as loops in imperative programming are often implemented as tail-recursive functions.

Suppose that a function *bar* calls another function *bar*,
that is, there is a call to *bar* appearing in the body of
*foo*, where *foo* and *bar* may actually be the same
fuction. If the return value of the call to *bar* also happens to be
the return value of *foo*, then this call is often referred to as a
*tail-call*. If *foo* and *bar* are the same, then
this call is a (recursive) self tail-call. For instanace, there are two
recursive calls in the body of the following defined function f91,
where the outer call to f91 is a tail-call while the inner one is
not:

It is arguably that the single most important optimization performed by the ATS compiler is the translation of every self tail-call into a direct (local) jump. This optimization effectively turns every tail-recursive function into the equivalent of a loop, guaranteeing that a fixed amount of stack space is adequate for executing each call to the function.

Let us now see some examples that can help further illustrate the notion of tail-recursive call optimization. The following recursive function sum1 sums up all the natural numbers less than or equal to n, where n is the given parameter:

Clearly, sum1 is not recursive as the only self call in its body is not a tail-call. The counterpart of sum1 in C can essentially be given as follows: When applied to an integer n, the following defined function sum2 also sums up all the natural numbers less than or equal to n:fn sum2 (n: int): int = let fun loop (n: int, res: int): int = if n > 0 then loop (n-1, res + n) else res // end of [loop] in loop (n, 0) end // end of [sum2] |

int sum2_loop (int n, int res) { loop: if (n > 0) { res = res + n ; n = n - 1; goto loop; } else { // do nothing } return res ; } int sum2 (int n) { return sum2_loop (n, 0) ; } |

Translating sum1 into sum2 is a fairly straightforward process. However, it can be highly involved, sometimes, to turn a non-tail-recursive implementation into an equivalent one that is tail-recurisve.

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

The Program Entry Point: mainats | Up | Mutual Tail-Recursion |