The call stack does not say "where you came from", but "where you are going next"?

Question

In a previous question (Get object call hierarchy), I got this interesting answer:

The call stack is not there to tell you where you came from. It is to tell you where you are going next.

As far as I know, when arriving at a function call, a program generally does the following:

1. In calling code:

   • store return address (on the call stack)
   • save registers' states (on the call stack)
   • write parameters that will be passed to function (on the call stack or in registers)
   • jump to target function
     
     

2. In called target code:

   • Retrieve stored variables (if needed)
     
     

3. Return process: Undo what we did when we called the function, i.e. unroll/pop the call stack:

   • remove local variables from the call stack
   • remove function variables from the call stack
   • restore registers state (the one we stored before)
   • jump to return address (the one we stored before)
     
     

Question:

How can this be viewed as something that "tells you where you are going next" rather than "tell you where you came from"?

Is there something in C#'s JIT or C#'s runtime environment that makes that call stack work differently?

Thanks for any pointers to documentation about this description of a call stack — there's plenty of documentation about how a traditional call stack works.

Answer 1

You've explained it yourself. The "return address" by definition tells you where you are going next.

There is no requirement whatsoever that the return address that is put on the stack is an address inside the method that called the method you're in now. It typically is, which sure makes it easier to debug. But there is not a requirement that the return address be an address inside the caller. The optimizer is permitted to -- and sometimes does -- muck with the return address if doing so makes the program faster (or smaller, or whatever it is optimizing for) without changing its meaning.

The purpose of the stack is to make sure that when this subroutine finishes, it's continuation -- what happens next -- is correct. The purpose of the stack is not to tell you where you came from. That it usually does so is a happy accident.

Moreover: the stack is just an implementation detail of the concepts of continuation and activation. There is no requirement that both concepts be implemented by the same stack; there could be two stacks, one for activations (local variables) and one for continuation (return addresses). Such architectures are obviously much more resistant to stack smashing attacks by malware because the return address is nowhere near the data.

More interestingly, there is no requirement that there be any stack at all! We use call stacks to implement continuation because they are convenient for the kind of programming we typically do: subroutine-based synchronous calls. We could choose to implement C# as a "Continuation Passing Style" language, where the continuation is actually reified as an object on the heap, not as a bunch of bytes pushed on a million byte system stack. That object is then passed around from method to method, none of which use any stack. (Activations are then reified by breaking each method up into possibly many delegates, each of which is associated with an activation object.)

In continuation passing style there simply is no stack, and no way at all to tell where you came from; the continuation object does not have that information. It only knows where you are going next.

This might seem to be a highfalutin theoretical mumbo jumbo, but we essentially are making C# and VB into continuation passing style languages in the next version; the coming "async" feature is just continuation passing style in a thin disguise. In the next version, if you use the async feature you will essentially be giving up stack-based programming; there will be no way to look at the call stack and know how you got here, because the stack will frequently be empty.

Continuations reified as something other than a call stack is a hard idea for a lot of people to get their minds around; it certainly was for me. But once you get it, it just clicks and makes perfect sense. For a gentle introduction, here are a number of articles I've written on the subject:

An introduction to CPS, with examples in JScript:

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/11/recursion-part-five-more-on-cps.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/15/recursion-part-six-making-cps-work.aspx

Here are a dozen articles that start by doing a deeper dive into CPS, and then explain how this all works with the coming "async" feature. Start from the bottom:

http://blogs.msdn.com/b/ericlippert/archive/tags/async/

Languages that support continuation passing style often have a magic control flow primitive called "call with current continuation", or "call/cc" for short. In this stackoverflow question, I explain the trivial difference between "await" and "call/cc":

How could the new async feature in c# 5.0 be implemented with call/cc?

To get your hands on the official "documentation" (a bunch of white papers), and a preview release of C# and VB's new "async await" feature, plus a forum for support Q&A, go to:

http://msdn.com/vstudio/async