What is a trampoline function?

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