Understanding the Clojure `trampoline'
May 8, 2010
Let's define two mutually recursive functions:
(declare funa funb) (defn funa [n] (if (= n 0) 0 (funb (dec n)))) (defn funb [n] (if (= n 0) 0 (funa (dec n))))
Calling `funa' with a parameter of say 4 results in the following sequence of calls:
(funa 4) --> (funb 3) --> (funa 2) --> (funb 1) --> (funa 0)
If you try invoking `funa' with a parameter of say 10000, your code will crash because of a stack overflow. Each function call requires some space on the stack which gets reclaimed only when the function returns - because we have a very long call sequence (of length 10000) with no `return' anywhere in between, all the space which the JVM has allocated for the stack gets consumed.
There is a very clever solution to this problem - in the form of a magical function called `trampoline'. In order to use `trampoline', we will have to restructure our code a bit:
(declare funa funb) (defn funa [n] (if (= n 0) 0 #(funb (dec n)))) (defn funb [n] (if (= n 0) 0 #(funa (dec n))))
The only change we have made is that instead of `funa' calling `funb', it returns an anonymous function which when called will invoke `funb'. Similar is the case with `funb'. (The Clojure `#' notation results in the creation of an anonymous function). The crucial thing to note is that recursion has now vanished from our code - `funa' no longer calls `funb' and `funb' no longer calls `funa'.
We don't want our program to crash - but we still have to get the effect of the mutually recursive invocations. It's here that `trampoline' works its magic:
(trampoline funa 100000)
Instead of calling `funa' directly, we are passing it (together with its parameter) as arguments to `trampoline'. What does `trampoline' do? It simply calls `funa' with parameter 100000 and looks at the return value - if it is a function, `trampoline' calls that function and once again looks at the return value - if it is not a function, the action stops, but if it is once again a function, trampoline calls that function and the whole process repeats.
In our case, the first time `trampoline' calls `funa', it returns an anonymous function which when called will invoke `funb'. Trampoline invokes that function with the result that `funb' gets called. Now, `funb' returns a function which when called will invoke `funa' ... the process repeats until one of `funa' or `funb' returns 0 at which point the process terminates.
Here is the clojure.core implementation of `trampoline':
(defn trampoline ([f] (let [ret (f)] (if (fn? ret) (recur ret) ret))) ([f & args] (trampoline #(apply f args))))
You can either call trampoline with a single function as parameter or you can call it with a function and its parameters as arguments; the second case gets converted to the first through the combination of a `#' and an `apply'. Note that `trampoline' uses `recur' and doesn't create a stack overflow.
`trampoline' is yet another simple function which demonstrates the power you gain by being able to treat functions as first class objects! clojure.core has many more such simple (and nifty) functions for us to read and enjoy!