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.

Recursion

Basically, a function calling itself could be called a recursion. But that’s not the point of recursion. What lies in its core is the idea of decomposing a computational problem into several problems of smaller scale. Those sub-problems can be solved using the exact same method, whose results will be composed back into the result of the original problem. The limit of the decomposing process is what we call the base case.

When designing a recursive algorithm, make sure the problem is getting smaller in every recursive call, and that there should be proper base cases, when the base problem’s anwser is immediately known.

Tail Recursion

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

Tail Call Optimization by Example

This is a tail call example,

extern fun foo (int): int
extern fun bar (int): int

implement foo (n) =
    if n > 0
    then foo (n-1)
    else bar (n)

implement bar (n) = 
    n - 1

Here, both calls to foo and bar are tail calls because both of them are the final calls. First, it can be transformed into loop for efficiency. Second, it may cause problems in some cases.

Problems

Suppose we have a very limited stack space, and we call foo(100000000000), then 100000000000 stack frames are going to be allocated. It is highly likely that the program will crash with a stack overflow error before it reachs 100000000000. This is especially important in functional languages because most of them don’t have language constructs for loop. Instead, they use tail call as loop.

Examples and Solutions

For a non-optimized compiler, it will generate the following code (pseudo-code) for foo. Suppose n is on the stack, and we use loc() to denote the location of something.

``` {.sourceCode .assembly} mov reg loc(n) ; load the value n from stack into register cmp reg 0 ; compare n and 0 jg 1 ; jump to label 1 if n > 0 push reg ; push n onto stack to pass parameter call bar ; call bar, who uses the parameter pop ; pop n from stack to clear it


A tail call optimized code would look like this:

``` {.sourceCode .assembly}
mov  reg loc(n)  ; load the value n from stack into register
cmp  reg 0       ; compare n and 0
jg   1           ; jump to label 1 if n > 0
jmp  bar         ; jump to bar

Here, we are not pushing parameters onto stack and call functions. Instead, we are adjusting the current parameters and loop. Or we can say, we are not buding new stack frames, we are instead reusing the same stack after we adjust the parameters needed by the code.

You can correspond the optimized machine code to the following demo python code (because there is no loop constructs in ATS and other functional languages alike).

{.sourceCode .python} def foo(n): while n > 0: n = n - 1 return n - 1

And you can examine that this is a semanticlly equivalent program of the original one.

Tail Recursion

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

While Loop and Tail Recursion

Consider this (in ATS)

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

and this (in C)

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.

Exercises

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

  • Implement the 91 function.
  • Implement Eculidean’s greatest common divisior algorithm. (ref)