Callstacks of the future

I read a blog entry recently (but can’t find the reference now, sorry) which changed my view about callstacks. Now, these are pretty fundamental things and I’ve been aware of them for nearly twenty years. So this was a pretty remarkable change.

In my head, a callstack was a record of history. When I drop into the debugger, I look at the callstack to see “where I’ve been”.

That’s wrong. The callstack isn’t a record of history. It’s a record of the future. It tells you where your computation is going to go next. The “return addresses” on the stack are where computation will continue from in the future.

Now, it’s easy to see why my misconception has continued for so long. There’s usually not much difference between the two views. Most of the time in a C-like language, you get called from some point in a function and then (later) you resume again from just after that point. So is it really worth worrying about such a tiny different?

Yes it is, because it gets your mind ready to understand concepts such as tail-call optimization and continuations much more easily. In the “future” view of callstacks, tailcall optimization becomes obvious. If we don’t need an activation record in the future, we don’t need it on the stack. Similarly, continuations make much more sense.

It’s a pretty small change in metaphor. I haven’t magically learned anything new because of it. But several bits of my knowledge now fit together in a much more satisfying way because of this switch. Whoever wrote that original blog article, thank you! 🙂

UPDATE: Rar, finally found the original blog article. Dave Herman was the man with the wisdom. 🙂