What is a trampoline function?

Question

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?

Answer 1

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