trampoline
The trampoline
function is used to optimize a mutually recursive function relation.
This function is effective when a recursive call does not use explicit tail recursion.
The syntax is: (trampoline f) (trampoline f & args)
Advice to coaches
The example below prints out to standard output. If the attendees are using LightTable, they need to open the console to see the result. Be careful. After trying this example on Instarepl, a response of the Instarepl may become very slow.
If we don’t use trampoline, the example below will raise “java.lang.StackOverflowError: null”.
user=> (incrementor 500)
500, 591, 518, 566, 505, .... (bunch of numbers) ....
-1191,
StackOverflowError java.lang.ReflectiveOperationException.<init> (ReflectiveOperationException.java:89)
The incrementor and decrementor functions call each other.
declare
is used to define this sort of mutual call functions.
Since Clojure interprets from top to bottom, the decrementor function in incrementor function can’t be found without declare
.
To avoid StackOverflowError, we can use the trampoline
function.
This function takes a function and the given function’s argument(s).
While the given function returns a function, trampoline
keeps calling the given function without an argument.
To use trampoline
, we need to change incrementor and decrementor so that those will return a function. Changing it to anonymous function
does the job.
Below is a trampoline-able functions.
user=> (incrementor2 500)
500, #<user$incrementor2$fn__664 user$incrementor2$fn__664@2f5731c7>
user=> ; incrementor2 function returns function
user=> ; incrementor2 is a higher-order function since it returns function
user=> (trampoline incrementor2 500)
500, 535, 523, 539, 523, ... (bunch of numbers) ....
9995, 9955, 9970, 9959, 10048, nil
In the first example, we wrote functions to call each other. We can use Clojure’s core functions or macros wrapped in an anonymous function. Let’s look at the second example below. Both the right-and-left and right-and-left functions move a cursor right and left. For example:
size 3: right, right, left, done
size 4: right, right, right, left, left, right, done
size 5: right, right, right, right, left, left, left, right, right, left, done
As we saw in the first example, right-and-left function raises StackOverflowError when the size gets bigger. The right-and-left2 function that uses trampoline doesn’t.
In addition, the second example doesn’t use declare
.
Instead, it defines a local function within the letfn
scope.
user=> (right-and-left 1000)
StackOverflowError clojure.lang.PersistentVector.nth (PersistentVector.java:111)
user=> (right-and-left2 1000)
done
nil