Trampolines are memory locations holding addresses pointing to interrupt service routines (interrupt handlers), I/O routines, etc. Also referred to as indirect jump vectors. Execution jumps into the trampoline and then immediately jumps out, or bounces, hence the term trampoline.

Trampoline can be used to overcome the limitations imposed by a CPU architecture that expects to always find vectors in fixed locations.

When an operating system is booted on a symmetric multiprocessing (SMP) machine, only one processor, the boot-strap processor, will be active. After the operating system has configured itself, it will instruct the other processors to jump to a piece of trampoline code that will initialize the processors and wait for the operating system to start scheduling threads on them.

A trampoline can be a loop that iteratively invokes thunk-returning functions (continuation-passing style). A thunk is essentially a function that wraps a call to another function, along with any parameters it needs, for later execution. A way to emulate lazy evaluation.

The goal of a trampoline is to prevent recursion in function calls.

The idea is to transform our function, so that its caller can detect when it recurses or when it leaves. If it performs a recursive call to itself, the trampoline will control its stack by becoming its callee. If it returns its result, the trampoline should notice it and stop.

<?php
function trampoline_factorial($n, $acc = 1)
{
    if ($n == 1) {
        return $acc;
    }
    return function() use ($n, $acc) { return trampoline_factorial($n-1, $n * $acc); };
}

You see here that this function doesn’t directly call itself, but it wraps its recursive call into a closure. This is because now we won’t launch our recursive function directly, but using a trampoline.

When the trampoline sees a closure returned, it launches it, when it sees a non-closure, it returns; hence the “trampoline” wording.

<?php
function trampoline(callable $c, ...$args)
{
    while (is_callable($c)) { $c = $c(...$args); } return $c;
}

echo trampoline('trampoline_factorial', 42);

Trampolines & tail-recursive function calls

When you need a tail call optimization like structure in a language that doesn’t (necessarily) provide it, but does provide closures, you can use a trampoline to achieve constant stack space (with a trade off for heap space for closure objects, of course).

The trampoline is a generic solution to recursion. If you can’t refactor your function to eliminate recursive calls, then transform it to a tail-call function that can be launched through a trampoline.

To illustrate the idea, here is a simple example of trampoline function that can be used effectively to eliminate recursive calls. In languages like C this concept is important because the compiler is usually unable to optimize tail recursive calls, unlike languages such as Scheme.

A basic, recursive way of calculating a factorial in C looks 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 above piece of code is that we are using the function stack to maintain the intermediate results. Although, because the size of the integer is more of a limitation than the size of the stack, this is not really a problem here but it can be a real concern in other recursive implementations.

So what can we do using a trampoline function instead? Instead of calling the function itself, we will call a pointer to a function, 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;
}

On this example, at each time, the stack holds only the context for the function that is being called. Since we don’t need to store return information for the last call, this can always be done in a tail recursive function.

Resources