Tail Call Optimization in Lisp Implementations

Early on in my Lisp education, I learned Scheme and became enamored with using recursion as a primary iteration strategy. It's hard to avoid this in Scheme because it doesn't have any other general recursion mechanisms besides do.

In Common Lisp, iteration via recursion is not an established paradigm. Mostly that's because, unlike Scheme, Common Lisp does not guarantee that tail recursion will be “optimized.” You can always do recursion, of course, but you risk running out of stack frames. With tail call optimization (TCO)1 that doesn't happen.

Even though Common Lisp doesn't guarantee TCO, most implementations do, in fact, provide it. Sadly, it's hard—or at least I find it hard—to determine whether a particular implementation provides it or not. You can peruse the documentation, of course, but it seems harder than it should be to find the information. Happily, Marc Simpson, who had the same problem, has us covered. He's put together a nice post that lays out which CL implementations provide TCO and which don't.

For my part, I'm glad the SBCL does TCO. So does Clozure, the other CL implementation that I sometimes use. If you are a Lisper, you should take a look at this post and bookmark it even if you currently use only a single implementation. It's a great resource.

Footnotes:

1

More accurately tail call elimination, but everyone calls it tail call optimization.

This entry was posted in Programming and tagged , . Bookmark the permalink.