Jan 15, 2018
I spent the past week doing a programming retreat at the Recurse Center in New York City. One project I worked on was writing a simple Lisp interpreter in Ruby, following the excellent make-a-lisp tutorial.
One of the more educational steps was adding support for tail call optimization. I had used tail call optimization before and had a vague sense of how it worked, but it always sounded complicated. Implementing it in a toy interpreter was a great way to understand it better, and it turns out that the core idea is actually very simple!
In this post, I’ll show you why we need tail call optimization, and exactly how I implemented it in an interpreter with a surprisingly small set of changes to the code.