Recursion Using Trampoline Functions
Trampoline function is a general term used to describe an additional level of indirection between the calling code and the called code. For example, a trampoline can be used to intercept calls to a function and supply additional functionality that was not present on the original function (see this Microsoft research project [2] to understand what is possible).
To illustrate the idea, here is a simple example of trampoline function that can be used effectivelly to eliminate recusive calls. It is important to do this in languages like C because the compiler is usually unable to optimize tail calls, unlike languages such as Scheme.
The usual recursive way of calculating a factorial would be something like this:
int fact(int x, int total) {
if (x <= 1) return total;
return fact(x-1, total*x);
}
int main() {
printf("result is %d\n", fact(10, 1));
return 0;
}
|
The problem with this version is that you are using the function stack to maintain the intermediate results. While this is not really a problem here (because the size of the integer is more of a limitation than the size of the stack), it can be a real concern in other recursive implementations.
Let us see what we can do using a trampoline function. That is, instead of calling the function itself, we call a pointer to a function that is supposed to do what it needs to do, and then return a pointer to a place where we need to go next:
#include <stdlib.h>
#include <stdio.h>
typedef void * (*Func)(int *x, int *total);
void *fact0(int *x, int *total) { return NULL; }
void *fact(int *x, int *total) {
if (*x <= 1) return fact0;
*total *= *x;
*x = *x-1;
printf("total %d, x: %d\n", *total, *x);
return fact;
}
int main() {
int res=1, n = 10;
Func f = fact;
while (f != NULL) {
f = (Func)f(&n, &res);
}
printf("result is %d\n", res);
return 0;
}
|
This also works, and now there is no problem with the stack size: at each time, the stack holds only the context for the function that is being called. It is always possible to do something like this in a tail recursive function, because we don’t need to store return information for the last call.
In fact, as mentioned by Knuth [1], the method described above can be used to implement any algorithm. This is exactly the direction taken when implementing some interpreters to scheme. The basic idea is to use continuations to store control structure information, so that one never needs to return from a function. However, as stack size is limited in languages such as C, the tactic explained above is used, so one can work with trampoline functions instead of continuations. Tricky but useful when implementing functional languages.
For a similar example in Python, see [3].
[1] Structured Programming With Goto Statements, D.E. Knuth, A.C.M. Computing Surveys, Vol. 6, pp. 261-301.
[2] http://research.microsoft.com/apps/pubs/default.aspx?id=68568
[3] http://mail.python.org/pipermail/tutor/2004-August/031553.html
