Scalisp - now with tail-call optimization

The last few days, I worked a bit more on Scalisp. Most importantly, I added tail-call optimization. If you don't know what this is all about, think what a normal function call does: It grows the stack, one frame for each call. Normally, that's what you want, but not when you try to implement loops with recursive functions. (as you usually do in functional languages)

Take this simple example, summing all numbers from 1 to n (nevermind that there's a simple formula to do that):

1
2
3
4

(defun sum_to (n)
  (if (<= n 1)
    1
    (+ n (sum_to (- n 1)))))

In this form, each recursive call to sum_to will add another stack frame. For small n, that's fine, but it leads to stack overflows very quickly. Luckily, you don't always need to create a new stack frame - if you throw away the context of the calling function, then you don't need the frame. This won't work in our example, since + needs the result of the recursive call to add it to n, but we can do better:

1
2
3
4

(defun sum_to (n acc)
  (if (<= n 0)
    acc
    (sum_to (- n 1) (+ n acc))))

Now, our sum_to either returns the value of acc or the result of recursively calling itself. Therefore, we don't need to store the original stack frame - we can throw it away. That's all tail-call optimization is about - if the recursive call is in the tail position (as in our second example, ie the result of the call is not further processed but immediately returned), then we don't have to grow the stack.

I've implemented this for both interpreted and compiled code, so now you are not restricted to small lists anymore in map and the like.

To present Scalip in class at my university, I've also created a small presentation - you might want to look at it if you want to get a quick overview of the project.

Tags: programming, university