(This is a post for CS320 at Boston University.)

In most functional programming languages, including ATS, there is no explicit language construct for loops. Instead, they use tail recursion to do this.

Tail Call

A tail call is a subroutine call that happens inside another procedure as its final action. (ref)

Consider the following pesudo code. (Examples are taken from Wikipedia)

function foo(data) {
    a(data);
    return b(data);
}

Here, only b(data) is tail call.

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

Here, both b and c are in tail position.

Now consider this code:

function foo1(data) {
    return a(data) + 1;
}

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var ret = a(data);
    return (ret === 0) ? 1 : ret;
}

Only a in foo2 is a tail call.

Tail Recursion

If a recursive call happens to be a tail call, then it is tail recursion.

function bar(data) {
    if (data > 0)
        return bar(data - 1)
    else
        return 0
}

While Loop and Tail Recursion

Consider this

fun loop(a: int, sum: int): int = 
    if a = 0 then 
        sum 
    else 
        loop(a - 1, sum + a)
    
        

and this

int sum;
int loop(int a) {
    while (a > 0) {
        sum += a;
        a--;
    }
    return sum;
}

For Loop and Tail Recursion

You can easily turn a for loop into while loop, thus turn it into tail recursion.

Optimization

There are differences between while loop and tail recursion. While loop is more machine friendly. It generates machine code that will jump around the loop body, and reuse the same stack frame. However, tail recursion is essentially recursive function calls, and it will generate new stack frames.

However, most modern compilers, especially compilers for functional languages, will do optimizations that turn tail recursions into loops internally to save stack space and make functional languages possible.

Exercises

Finish the following tasks using recursions. They may or may not be tail recursions.

  • Find the minimum one in an integer list.
extern fun min(xs: List (int)): int

implement min(xs) = do_min(xs, 9999) where {
    fun do_min(xs: List (int), init: int): int = 
        case+ xs of
        | cons (x, xs) => 
            if x < init then do_min(xs, x) 
            else do_min(xs, init)
        | nil  () => 
            init
    }

#define :: list_cons

implement main0 () = () where {
    val m = min(1::9::23::0::8::nil)
}
  • Implement the 91 function.
  • Implement Eculidean's greatest common divisior algorithm. (ref)