2

What is the convention about describing the direction of the stack, i.e., about what the words up, down, top, and bottom mean?

I noticed that with stack data structure API, top usually to refer to the most recently added item. I never saw high level language or library documentation refer to the newly added item in the stack as anything other than "top".

On the other hand, discussions about the program call stack often use the opposite convention, referring for example to the exceptions propagating up the stack (from the currently executing function towards the main function). Does the convention vary depending on the language, or some other factor?

To clarify: my question is only about the usage in the context of high-level language programming - not the direction in which the CPU/OS grows stack in physical memory (which varies by platform).

  • I believe that the way the stack is actually laid out in the address space is exactly the reason for this terminological confusion. I doubt that there is an “official” terminology to use. At least, a single document should use the words consistently, of course. – 5gon12eder Oct 1 '16 at 16:35
  • Possible duplicate of Which way are downstream and upstream services? – gnat Oct 1 '16 at 16:44
  • @gnat, I don't think this question is anywhere close to a dupe of the one you linked. – user22815 Oct 1 '16 at 17:01
  • I guess it's the same reason why trees grow into the bottom and the root is on top. ;) – Eiko Oct 1 '16 at 17:12
  • @Snowman agree, it's not a duplicate (retracted my vote). Probably last sentence in the question confused me – gnat Oct 2 '16 at 15:06
2

You push items onto and pop them off of the top of the stack, regardless of how it is laid out in memory.

The stack terminology is intended to mirror a physical stack (of plates, in particular):

Stacks are often described by analogy to a spring-loaded stack of plates in a cafeteria. Clean plates are placed on top of the stack, pushing down any already there. When a plate is removed from the stack, the one below it pops up to become the new top (Wikipedia, Stack History)


As it pertains to exceptions, strictly speaking, an exception propagates down the stack, from the most recently called function to the least recently called function. Google "exception propagation," and one of the first few results shows it like this:

enter image description here

However, when someone says "propagates up the stack," we understand what they mean. So, we don't fuss over it. Whether it's up or down in their heads isn't as relevant as whether they ultimately mean "most recent" to "least recent" (or "in opposite order of invocation").

  • Then why do exceptions propagate "up the stack"? The top of the stack according to your definition is the currently executing function, so exceptions should propagate "down".. – max Oct 1 '16 at 17:05
  • Because people who say that are careless with their words, ignorant, or understand that the precise wording isn't as important as just understanding the underlying point. – svidgen Oct 1 '16 at 17:20
  • Hopefully my edits help to clarify. – svidgen Oct 1 '16 at 17:31
  • That makes sense, just wanted to make sure it's not some convention I didn't know about. – max Oct 1 '16 at 21:50
3

There are four ways to look at this:

1) As simply a meaningless metaphor. Calling the newest element the top, bottom, or front of the stack is simply an idiomatic choice. I know for a fact some people think of it that way. And there top is the popular answer. And because of them you can't rely on the next way to look at this unless you check it yourself.

2) As an implementation detail. Stacks must change their address as they grow. A stack that grows must change its address in a particular way. A stack that grows up or down tells you if the address gets bigger or smaller as they grow.

3) As an implementation detail clouded by an idiomatic choice. Who the hell decides that the zeroth address is at the top or bottom of memory? Your computer certainly doesn't care. Go ahead, turn it upside down. Your memory bits don't fall out. Motherboards can be installed with any orientation so up really has no objective meaning here. I've seen instructors write it on the board either way. I seen books lay it out either way. I've seen specs lay it out either way. After over 20 years the only thing I know for sure is that I don't trust it.

4) Bigger numbers always go up. What are you stupid? Just like in graphics where they grow left to right, top to bottom... hey wait a second...

This interview question is a good example of how this can seem objective yet be arbirary. With local1 allocated in the first frame and local2 allocated in the second it's output code is:

if(local1 < &local2)
{
printf("\nStack is growing downwards.\n");
}
else
{
printf("\nStack is growing upwards.\n");
}

Yet in the first comment insists the inequality is pointing the wrong way. The second insists on dropping up/down and referring to higher/lower addresses.

My advice, if you're writing something that cares about this and you can't avoid it, carefully determine the popular assumptions and use those consistently. Try to make your assumptions clear.

If you're reading something that cares about this, regardless of context, don't trust assumptions until they are clear.

Stack depicted with 0th memory address at the top:
https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/stack.html

Stack depicted with 0th memory address at the bottom:
https://stackoverflow.com/questions/4560720/why-does-the-stack-address-grow-towards-decreasing-memory-addresses

Note how they give you the ability to check what their assumptions are.

It sucks but this ambiguity is what we've been left with. Anyone who says different is simply stuck in a small context.

If you want to sidestep all this confusion you can say exceptions unwind the stack.

  • The last linked question has the answer regarding the call stack: the stack starts at the highest address, and grows downwards towards smaller addresses. Then, “upwards” is older data with the call stack frames of calling functions. – amon Oct 1 '16 at 18:49
  • @amon yes, in that context it is. But tell me your grows down and I won't assume I know what you mean until you define down. – candied_orange Oct 1 '16 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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