Tail Calls

Tail Calls

This has been talked about before on my blog, and let me just state that right now, When Dealing With Recursive code in a Language of choice CONSIDER using tail calls if possible. I wanted to write some on Prolog this time and the tail calls there but i feel that it could be out of context so I will write about tail calls in general

So what is a tail call? or rather what is a recursive tail call?

Basically it is a call to the function (subroutine) that returns the value immediately thus eliminating storing returning addresses on the stack. This is possible when the recursive call is the last instruction in the sub routine, it doesn't have to be lexically though, sometimes the compiler can optimize the code to be aligned that way, then we don't access the stack register and store data there but we generate jump instruction instead of that.

For our guinea pig i'm going to chose the Fibonacci sequence, as I like those numbers, they have lot's of interesting properties and patterns, and it shows that the function can be re written on a hundreds of (non standard) ways.

Tail Calls in C# 

Generally the VM does support tail calls, by using the ".tail" instruction, but in C# it is not enforced even when possible (true for NET 3.5) it is however enforced in F# when dealing with the release flag or at least it should be, last time I checked it wasn't, but it is more then possible, however upon not being enforced it's kinda hard to use it unless you write some script that will decompile the assemblies and add this parameter.

Let's write a fib function in C# that should be tail call compatible:

public long FibA(int n)
{
    return Fibx(n, 0, 1);
}

private long Fibx(int n, int a, int b)
{
    if (n == 0) return a;
    else return Fibx(n - 1, a + b, a);
}

but this code however isn't generated with a tail instruction so sadly the compiler isn't smart enough and we have to optimize on our own, but it is very possible that the future versions will enforce the ".tail" instruction.

The same code in F#:

let fibA(n) =
    let rec fibx (n, a, b) =
        match (n, a, b) with
          | (0, a, b) -> a
          | _ -> fibx (n - 1, a + b, a)
    fibx (n, 0I, 1I)

Note that this code is taken form my earlier post : http://badamczewski.blogspot.com/2010/02/f-learning-tests.html

Tail Calls In Java

As far as I know so far tail calls aren't optimized, but this is somewhat planned in the Da Vinci machine, so maybe it will go to Java 7, so in the fib example this will only benefit the performance of the recursive call as we eliminate one recursive call, but it will go on the stack, and the iterative version will be probably faster.

Tail Calls In Prolog

Recently I started to use prolog to solve puzzles, and to use as a fast prototyping language for certain algorithms (some problems take prolog 4 lines of code instead of 30 like in C# or even F#). So writing down some basic functions and knowing that prolog uses quite a lot of recursion I asked myself a question, is this optimized?

Before reading ahead it is advised that you at least know logic programming languages a bit, if not then I recommend a short tutorial.

Having said that let's look at some prolog code and how to convert it to tail recursive call:

fib(0, 1).
fib(1, 1).
fib(X, Y):-
        X > 1, X1 is X - 1, 
        X2 is X - 2, fib(X1, Z),
        fib(X2, W), Y is W + Z.

Normally prolog builds a solution tree and traverses it, when we deal with recursion the evaluator first goes down the tree consuming the stack and then doing some actual calculation it goes back up. This is not so good in therms of memory usage and performance and besides we can run out of stack space fast when dealing with a complex problem.


Calling the function with fib(30,X). will cause a stack overflow.

ERROR: Out of local stack

So this is no good especially that prolog is cool to solve tree structure problems, like language design, data access optimization etc, so now let's look at a better implementation where the function call is the last instruction and addition is done before the call.

fibTail(X,Y) :- fibTail(X,1,0,Y).
fibTail(0,_,C,C).
fibTail(N,A,B,C) :-
        N > 0,
        N1 is N - 1,
        A1 is A + B,
        fibTail(N1,B,A1,C).

A short description of the code, the first fib function is just to reduce the arguments to only the meaningful to the user which are the X input argument and Y the output argument, this basically defines a rule that calls another function that sets the startup parameters for the sequence generator.

Next up is the "fibTail(0,_,C,C)." This tells that if the bottom function will be false at some point we want this to be true to get the value, and how this works it's kinda cool, prolog find the next matching function when the current one if false. So if at some point the the execution of the third function in the code will be evaluated as false (N will be 0) we will skip to this one and evaluate it. So the N will be 0 and that's true, the "_" symbol means "any" value so there will be some value there so again true, then in place of A1 we got C that is a uninitialized variable at this point so the variable C will be initialized with the value of A1, again this is true and the last line uninitialized variable that was passed is now initialized and assigned to our Y so this is true, hence the execution stops and we have a result.

Now when we call the function with the following fibTail(30,X). we will get the actual value.

X = 832040

So that means that prolog supports tail recursive calls, cool so the stack size is not an issue anymore when designing complex recursive functions or tree depth evals.

This concludes tail call article, the bottom line is that problems that require or favor recurrence should be optimized that way if there is a language or VM support for it.