What is a trampoline function?

During recent discussions at work, someone referred to a trampoline function.

I have read the description at Wikipedia. It is enough to give a general idea of the functionality, but I would like something a bit more concrete.

Do you have a simple snippet of code that would illustrate a trampoline?

There is also the LISP sense of 'trampoline' as described on Wikipedia:

> Used in some LISP implementations, a > trampoline is a loop that iteratively > invokes thunk-returning functions. A > single trampoline is sufficient to > express all control transfers of a > program; a program so expressed is > trampolined or in "trampolined style"; > converting a program to trampolined > style is trampolining. Trampolined > functions can be used to implement > tail recursive function calls in > stack-oriented languages

Let us say we are using Javascript and want to write the naive Fibonacci function in continuation-passing-style. The reason we would do this is not relevant - to port Scheme to JS for instance, or to play with CPS which we have to use anyway to call server-side functions.

So, the first attempt is

function fibcps(n, c) {
    if (n <= 1) {
        c(n);
    } else {
        fibcps(n - 1, function (x) {
            fibcps(n - 2, function (y) {
                c(x + y)
            })
        });
    }
}

But, running this with n = 25 in Firefox gives an error 'Too much recursion!'. Now this is exactly the problem (missing tail-call optimization in Javascript) that trampolining solves. Instead of making a (recursive) call to a function, let us return an instruction (thunk) to call that function, to be interpreted in a loop.

function fibt(n, c) {
    function trampoline(x) {
        while (x && x.func) {
            x = x.func.apply(null, x.args);
        }
    }

    function fibtramp(n, c) {
        if (n <= 1) {
            return {func: c, args: [n]};
        } else {
            return {
                func: fibtramp,
                args: [n - 1,
                    function (x) {
                        return {
                            func: fibtramp,
                            args: [n - 2, function (y) {
                                return {func: c, args: [x + y]}
                            }]
                        }
                    }
                ]
            }
        }
    }

    trampoline({func: fibtramp, args: [n, c]});
}

Let me add few examples for factorial function implemented with trampolines, in different languages:

Scala:

sealed trait Bounce[A]
case class Done[A](result: A) extends Bounce[A]
case class Call[A](thunk: () => Bounce[A]) extends Bounce[A]

def trampoline[A](bounce: Bounce[A]): A = bounce match {
  case Call(thunk) => trampoline(thunk())
  case Done(x) => x
}

def factorial(n: Int, product: BigInt): Bounce[BigInt] = {
	if (n <= 2) Done(product)
	else Call(() => factorial(n - 1, n * product))
}

object Factorial extends Application {
	println(trampoline(factorial(100000, 1)))
}

Java:

import java.math.BigInteger;

class Trampoline<T> 
{
    public T get() { return null; }
    public Trampoline<T>  run() { return null; }

    T execute() {
        Trampoline<T>  trampoline = this;

        while (trampoline.get() == null) {
            trampoline = trampoline.run();
        }

        return trampoline.get();
    }
}

public class Factorial
{
    public static Trampoline<BigInteger> factorial(final int n, final BigInteger product)
    {
        if(n <= 1) {
            return new Trampoline<BigInteger>() { public BigInteger get() { return product; } };
        }   
        else {
            return new Trampoline<BigInteger>() { 
                public Trampoline<BigInteger> run() { 
                    return factorial(n - 1, product.multiply(BigInteger.valueOf(n)));
                } 
            };
        }
    }

    public static void main( String [ ] args )
    {
        System.out.println(factorial(100000, BigInteger.ONE).execute());
    }
}

C (unlucky without big numbers implementation):

#include <stdio.h>

typedef struct _trampoline_data {
  void(*callback)(struct _trampoline_data*);
  void* parameters;
} trampoline_data;

void trampoline(trampoline_data* data) {
  while(data->callback != NULL)
    data->callback(data);
}

//-----------------------------------------

typedef struct _factorialParameters {
  int n;
  int product;
} factorialParameters;

void factorial(trampoline_data* data) {
  factorialParameters* parameters = (factorialParameters*) data->parameters;

  if (parameters->n <= 1) {
    data->callback = NULL;
  }
  else {
    parameters->product *= parameters->n;
    parameters->n--;
  }
}

int main() {
  factorialParameters params = {5, 1};
  trampoline_data t = {&factorial, &params};

  trampoline(&t);
  printf("\n%d\n", params.product);

  return 0;
}

I'll give you an example that I used in an anti-cheat patch for an online game.

I needed to be able to scan all files that were being loaded by the game for modification. So the most robust way I found to do this was to use a trampoline for CreateFileA. So when the game was launched I would find the address for CreateFileA using GetProcAddress, then I would modify the first few bytes of the function and insert assembly code that would jump to my own "trampoline" function, where I would do some things, and then I would jump back to the next location in CreateFile after my jmp code. To be able to do it reliably is a little trickier than that, but the basic concept is just to hook one function, force it to redirect to another function, and then jump back to the original function.

Edit: Microsoft has a framework for this type of thing that you can look at. Called Detours

I am currently experimenting with ways to implement tail call optimization for a Scheme interpreter, and so at the moment I am trying to figure out whether the trampoline would be feasible for me.

As I understand it, it is basically just a series of function calls performed by a trampoline function. Each function is called a thunk and returns the next step in the computation until the program terminates (empty continuation).

Here is the first piece of code that I wrote to improve my understanding of the trampoline:

#include <stdio.h>

typedef void *(*CONTINUATION)(int);

void trampoline(CONTINUATION cont)
{
  int counter = 0;
  CONTINUATION currentCont = cont;
  while (currentCont != NULL) {
    currentCont = (CONTINUATION) currentCont(counter);
    counter++;
  }
  printf("got off the trampoline - happy happy joy joy !\n");
}

void *thunk3(int param)
{
  printf("*boing* last thunk\n");
  return NULL;
}

void *thunk2(int param)
{
  printf("*boing* thunk 2\n");
  return thunk3;
}

void *thunk1(int param)
{
  printf("*boing* thunk 1\n");
  return thunk2;
}

int main(int argc, char **argv)
{
  trampoline(thunk1);
}

results in:

meincompi $ ./trampoline 
*boing* thunk 1
*boing* thunk 2
*boing* last thunk
got off the trampoline - happy happy joy joy !

Here's an example of nested functions:

#include <stdlib.h>
#include <string.h>
/* sort an array, starting at address `base`,
 * containing `nmemb` members, separated by `size`,
 * comparing on the first `nbytes` only. */
void sort_bytes(void *base,  size_t nmemb, size_t size, size_t nbytes) {
    int compar(const void *a, const void *b) {
        return memcmp(a, b, nbytes);
    }
    qsort(base, nmemb, size, compar);
}

compar can't be an external function, because it uses nbytes, which only exists during the sort_bytes call. On some architectures, a small stub function -- the trampoline -- is generated at runtime, and contains the stack location of the current invocation of sort_bytes. When called, it jumps to the compar code, passing that address.

This mess isn't required on architectures like PowerPC, where the ABI specifies that a function pointer is actually a "fat pointer", a structure containing both a pointer to the executable code and another pointer to data. However, on x86, a function pointer is just a pointer.

For C, a trampoline would be a function pointer:

size_t (*trampoline_example)(const char *, const char *);
trampoline_example= strcspn;
size_t result_1= trampoline_example("xyzbxz", "abc");

trampoline_example= strspn;
size_t result_2= trampoline_example("xyzbxz", "abc");

Edit: More esoteric trampolines would be implicitly generated by the compiler. One such use would be a jump table. (Although there are clearly more complicated ones the farther down you start attempting to generate complicated code.)

Now that C# has Local Functions, the Bowling Game coding kata can be elegantly solved with a trampoline:

using System.Collections.Generic;
using System.Linq;

class Game
{
    internal static int RollMany(params int[] rs) 
    {
        return Trampoline(1, 0, rs.ToList());

        int Trampoline(int frame, int rsf, IEnumerable<int> rs) =>
              frame == 11             ? rsf
            : rs.Count() == 0         ? rsf
            : rs.First() == 10        ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(1))
            : rs.Take(2).Sum() == 10  ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(2))
            :                           Trampoline(frame + 1, rsf + rs.Take(2).Sum(), rs.Skip(2));
    }
}

The method Game.RollMany is called with a number of rolls: typically 20 rolls if there are no spares or strikes.

The first line immediately calls the trampoline function: return Trampoline(1, 0, rs.ToList());. This local function recursively traverses the rolls array. The local function (the trampoline) allows the traversal to start with two additional values: start with frame 1 and the rsf (result so far) 0.

Within the local function there is ternary operator that handles five cases:

• Game ends at frame 11: return the result so far
• Game ends if there are no more rolls: return the result so far
• Strike: calculate the frame score and continue traversal
• Spare: calculate the frame score and continue traversal
• Normal score: calculate the frame score and continue traversal

Continuing the traversal is done by calling the trampoline again, but now with updated values.

For more information, search for: "tail recursion accumulator". Keep in mind that the compiler does not optimize tail recursion. So as elegant as this solution may be, it will likely not be the fasted.

typedef void* (*state_type)(void);
void* state1();
void* state2();
void* state1() {
  return state2;
}
void* state2() {
  return state1;
}
// ...
state_type state = state1;
while (1) {
  state = state();
}
// ...