10

A stack is something that piles bottom-up.

Hence a call stack adds new items on the stack when functions are called with items being removed from the stack as each function ends until the stack is empty and then the program ends.

If the above is correct, why do people refer to control moving "up" the call stack? Surely control moves down the call stack until it reaches the bottom.

  • When a function is called, an item is added to the top of the stack, and the control is passed to that function. Hence the control moves from the underlying item in the stack to the top item of it -- upward. – treecoder May 1 '12 at 8:08
  • 1
    @greengit: the expression "up the call stack" is used with exceptions, where control actually moves in the opposite way. – Michael Borgwardt May 1 '12 at 8:11
  • @MichaelBorgwardt: You are correct. – treecoder May 1 '12 at 8:13
  • 1
    @MichaelBorgwardt: I have seen the expression "errors move up the call stack". Surely that is incorrect. – CJ7 May 1 '12 at 8:16
  • 3
    The enemy's gate is down. – Jon May 1 '12 at 10:40
8

There are two possible reasons for this usage:

  • In the context of exceptions, the control moves to the calling function/method, and this call hierarchy is typically visualized with the main method on top and method calls forming a hierarchy downwards, with a decreasing level of abstractions. In this hierarchy, an exception moves upwards.

  • The actual program stack in a normal x86 application is inverted, i.e. it grows downwards. The PUSH / PUSHW / PUSHD machine code instructions decrease the stack pointer. Other architectures may share this model.

  • Isn't the top-down idea contrary to the everyday concept of a "stack" being a pile of items starting at the bottom? – CJ7 May 1 '12 at 9:21
  • @CraigJ: so is the fact that the bits of each byte of the stack's contents will be physically stored in separate chips. Who cares? – Michael Borgwardt May 1 '12 at 10:01
1

It all depends on the definition of words; what exactly do you mean with the words "top" and "bottom" in this context, and also on the implementation of the operating system or computer architecture.

I remember the following from long ago, when I was programming on the Commodore 64. The memory between address $0800 (2048) and $9FFF (40959) was reserved for BASIC programs. The code of your BASIC program was stored starting at the lower address ($0800, growing upwards from there). The stack, for storing variables and return addresses of subroutines, started at the top ($9FFF) of that range and grew towards lower addresses. So in this context it was logical to see the stack as growing downward, and when you return from a subroutine the stack frame of the subroutine was discarded by incrementing the stack pointer, so that you could say you were "moving up the stack" when returning from a subroutine.

I don't know how it works on modern versions of for example Windows or Intel x86 processors. Maybe the stack works the other way around, i.e. it grows from lower to higher addresses. If that would be the case then you'd probably use the words "top", "bottom" and "up", "down" exactly the other way around.

0

To call a function such as foo(6, x+1)...

  1. Evaluate the actual parameter expressions, such as the x+1, in the caller's context.
  2. Allocate memory for foo()'s locals by pushing a suitable "local block" of memory onto a runtime "call stack" dedicated to this purpose. For parameters but not local variables, store the values from step (1) into the appropriate slot in foo()'s local block.
  3. Store the caller's current address of execution (its "return address") and switch execution to foo().
  4. foo() executes with its local block conveniently available at the end of the call stack.
  5. When foo() is finished, it exits by popping its locals off the stack and "returns" to the caller using the previously stored return address. Now the caller's locals are on the end of the stack and it can resume executing.

Reference:

http://cslibrary.stanford.edu/102/PointersAndMemory.pdf (p15)

  • Note that this is highly specific to the calling convention. There are calling conventions that let the caller clean up, most use at least some registers, etc. – user7043 May 1 '12 at 10:47
0

If you conceptualize a stack as a bottom up thing, like a cylinder with tennis balls in it under normal gravitational reality the then control moves up the stack as functions are called. As functions complete, the control moves down the stack.

If you conceptualize a stack as a top down thing, like the same cylinder of tennis balls but with inverted gravity, then control moves down up the stack as functions are called and up the stack as functions complete.

These are both just models in your head and are essentially totally arbitrary. You can conceptualize it as a side to side thing if you prefer, but might have trouble communicating with people. I personally think that if A calls B and B calls C that C is the bottom of the stack (inverted gravitational reality) and if an exception occurs in C you want to bubble that exception "up" to A. I think this may be the more common language usage because the feeling is that C is deep down and A is the top. The first function is more intuitively the top to me and functions get deeper on each call.

Not the answer you're looking for? Browse other questions tagged or ask your own question.