PurelyFunctional.tv Newsletter 361: Tip: trampoline your tail recursion
Issue 361 - January 20, 2020 · Archives · Subscribe
Clojure Tip 💡
trampoline your tail recursion
A few issues ago, I made the big distinction in Clojure between non-tail
recursion and tail recursion. Non-tail-recursion uses a stackframe per
recursion, so you risk blowing the stack. You can replace tail recursion
with the recur form, which will optimize your recursion into a
loop---and hence no stack explosion.
However, there are some things that look like tail calls but aren't
really. For example, you can't do a recur inside of a try. And
recur only works with self-recursion (a function calling itself) and
not tail calls in general. Those add to the stack, too. Is there a way
to avoid a stack explosion where we can't use recur?
Yes! It's called
trampoline.
Trampolining is a general technique of simulating a loop with return
values. You run a function, it returns the next function to run, and the
trampoline runs it. It keeps bouncing until you stop returning the next
function to run. In the case of trampoline in Clojure, it keeps
bouncing until you return a value that is not a function.
Let's take a look at a function that will continue to retry something in case of an error.
(defn retry-forever [f]
(try
(f)
(catch Exception e
(println "Got an error, retrying.")
(recur f))))
This won't work. The recur looks like it's in tail position, but the
try/catch needs to clean up before you return. You can't use recur
inside of a try to call the enclosing function. We could switch it out
to do regular recursion, but then this would eventually blow the stack.
(defn retry-forever [f]
(try
(f)
(catch Exception e
(println "Got an error, retrying.")
(retry-forever f)))) ;; may blow the stack
Things seem dire, but they're not! A trampoline can help. Recall from
above that a trampoline expects to be passed a function that is the next
iteration of the loop. It will call that function. If it returns a
function, it will call that, etc. Instant loop! All we have to do it
make retry-forever return a function instead of recursing itself. In
Clojure, this is a one-character change. See if you can spot the
character.
(defn retry-forever [f]
(try
(f)
(catch Exception e
(println "Got an error, retrying.")
#(retry-forever f)))) ;; return a function for the next
iteration
Notice that we are now returning a function, which tells the trampoline
what the next iteration of the loop is. retry-forever is not
technically recursive now. It is not calling itself. All branches (the
success and the catch branches) return. That means the stack frame will
be popped before retry-forever is called again.
To use this, we just have to call it like this:
(trampoline (retry-forever f))
That's great, but not terribly convenient. The caller shouldn't really
care how this is implemented. Let's move the trampoline inside the
function. We'll do the important work in a helper.
(defn retry-forever* [f] ;; helper
(try
(f)
(catch Exception e
(println "Got an error, retrying.")
#(retry-forever* f))))
(defn retry-forever [f]
(trampoline (retry-forever* f)))
Now the caller doesn't even know it's a trampoline.
But there's another problem. What if f returns a function?
trampoline is not smart enough to know that it is a special return
value, not the next loop iteration. trampoline will call the returned
function, like all the others.
The solution is to wrap it up in a non-function. Here's one solution:
(defn retry-forever* [f] ;; helper
(try
{:value (f)}
(catch Exception e
(println "Got an error, retrying.")
#(retry-forever* f))))
(defn retry-forever [f]
(:value (trampoline (retry-forever* f))))
Now the helper is either returning a map or a function, regardless of
the return value of f. We can unwrap it when trampoline returns from
its bouncing. Wrap and unwrap.
That will work, but there's a built-in that is a better fit for
indicating the end of a loop. It's called reduced. It's made for
signaling to reduce that it can stop and return a value instead of
continuing to the end of the sequence. We can use it here with its
opposite, unreduced.
(defn retry-forever* [f] ;; helper
(try
(reduced (f))
(catch Exception e
(println "Got an error, retrying.")
#(retry-forever* f))))
(defn retry-forever [f]
(unreduced (trampoline (retry-forever* f))))
You can use trampoline for optimizing mutual tail recursion as well.
Mutual recursion is where a calls b and b calls a. They can't be
optimized by the JVM (yet!), so they too can blow the stack. But
trampolining can help. Mutual recursion comes up a lot in things like
recursive descent parsers. That's a bit too much to go into now, but you
can learn more about that parsing technique in this
lesson.
One quick note about tradeoffs: trampolining is more expensive than tail call optimization. The function has to unroll the stack, the trampoline has to check the type, and then do another function call. Tail call optimization can be as quick as a jump instruction (GOTO). But on our platform, sometimes tail call optimizations are not possible.
Relevant courses 📚
If you like recursion, laziness, and reduce, check out these courses.
Book update 📖
Chapter 6 is out! Buy it now: Grokking Simplicity.
Chapter 6 is all about immutable disciplines you can apply to your code. The two disciplines are copy-on-read and copy-on-write. They let you have immutable data when your language doesn't provide it.
Chapter 7 is finally coming along. Design is a very intuitive, feeling-led endeavor. It is not 10 0% objective or quantifiable. I'm focused now on showing how the reader can develop their intuition along the lines of stratified design.
I'm not sure anyone has written as deeply as I am about it---I haven't found anything. There are articles written about it, but they are descriptive, not prescriptive. They characterize it, but don't tell you how to do it yourself. This will be an important chapter to differentiate the book. Finally, a book teaching FP design!
You can buy the book and use the coupon code TSSIMPLICITY for 50% off.
Podcast episode🎙
I've revamped the format of my podcast. If you like reading old computer science papers to really understand how we got here (and sometimes uncover old gems), this podcast is for you.
In the first episode of the season, we read a paper from 1987 by Abelson and Sussman, the authors of SICP, called * Lisp: A language for stratified design*. The paper asks the question: "What is Lisp good for?" Read the paper, then follow along on the podcast.
And speaking of podcasts, I was a guest on Functional Geekery and Defn.
State of Clojure Community Survey 📋
Please support the ongoing development of Clojure by filling out the annual survey. There are still a few days left.
This survey has been going on for years and it collects very important statistics on the Clojure community. I find the information valuable myself. I can only imagine how important it would be for the folks in Clojure's core team to know this stuff.
Please fill it out, regardless of how you use Clojure. It's all great information.
Cognit e ct analyzes the data and produces a summary. Here is the one from last year. They also release all of the data. Daniel Compton also analyzes the free-text responses and writes a summary. Here is his from last year.
Clojure Challenge 🤔
Last week's challenge
The challenge in Issue 360 was a function to find the coordinates of a particular value in a nested vector. You can see the submissions.
Peter Strömberg asks for comments on his implementation. You can leave comments on this or any gist in the gist itself. Please leave comments! We're all here to learn.
This week's challenge
Gapful numbers
Some numbers are gapful, some aren't. 100 is gapful because it has at
least three digits and 100 is divisible by 10 ((str 1 0), the
concatenation of the first and last digit). That's the definition of
gapful: it has at least three digits and is divisible by the number
formed by concatenating the first and last digits.
Create a function that takes a number and finds the closest gapful number. The function should return its argument if the argument itself is gapful. And if there are two gapful numbers equidistant to the argument, return the lower one.
Thanks to to this site for the challenge idea!
As usual, please reply to this email and let me know what you tried. I'll collect them up and share them in the next issue. If you don't want me to share your submission, let me know.
Rock on!
Eric Normand
