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]});
}