Proper usage of up / down the stack

Question

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).

Answer 1

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

• http://www.studytonight.com/data-structures/stack-data-structure
• https://en.m.wikipedia.org/wiki/Stack_(abstract_data_type)

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:

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").

Answer 2

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.