Caterpillar

I talked about tail call elimination yesterday, but let's expand on that a bit, to make sure we're on the same page.

Whenever Caterpillar code calls a function, then (in principle) a new stack frame is added to the stack. That stack frame contains the local variables of that function, but also a return address. A function can be called from multiple places, so the compiler can't know where to go once it ends. That's why we need to keep track of a return address at runtime.

And that's where we catch up to yesterday: If a call is last in a function (a "tail call"), then we don't need to return there. If we did, we would immediately return again. That's useless work and wasted stack space. So what we do instead, is to reuse the stack frame of the calling function. Save one stack frame and one return. That is tail call elimination.