Why are primitive types stored in a stack in systems level software?

Question

Firstly 2 disclaimers, I am very new to the concept of a stack at a low level. I've only encountered it because I'm learning rust and the docs mention it. Secondly, I am aware of another similar question on this site, but it doesn't address a very specific concern.

My understanding of a stack is that it follows First In Last Off and cannot be searched, this confuses me if I do this.

variable a = 22;
variable b = 33;
variable c = 44;

Then my understanding is that c will be on top of the stack. So if I want to do something with a and b, will the system have to pop c and dig deeper for a and b? This seems inefficient. And an indexed array seems better.

Answer 1

You've probably encountered the simplest definition of a stack, which is a data structure with two operations push and pop, and some basic properties:

• If you call push on a value and then pop, the value you get from the pop is the value passed to push, and the stack is returned to its original state.
• pop is invalid on a stack where there has never been a push (empty stack).
• These properties also apply if the stack is modified in the middle, as long as these modifications return the stack to its state before the modifications.

There are many equivalent formulations of these axioms. The point here is that with this definition, push and pop are the only things you're allowed to do on a stack.

With the metaphor of a stack as being like a stack of plates, you can't “peek” at a value that isn't at the top of the stack (the most recently pushed value). (Note that I'm describing a stack that grows upwards. Unfortunately there's no standard for that: some stacks are described as growing down. But even with downward-growing stacks, the word “top” usually means the most recently pushed value.) But when a stack is a data structure, it's often possible to access values anywhere in the stack.

The same word “stack” can mean any variant of the basic data structure, supporting other operations apart from push and pop. There's no completely universal limit for what can be called “stack”, but generally, if a data structure is called a “stack”, it means that it's a collection of values where the only way to add an item is push and the only way to remove an item is pop. Other operations may be supported, such as:

• Reading the stack size.
• Peeking, i.e. reading any of the values on the stack (not just the top one).
• Modifying a value on the stack.

---

Let's look at programming languages now. Almost every programming language has a concept of function (or procedure, subroutine, method, etc. — the distinction is not relevant here). Function calls have certain properties:

• If the code in function f calls a function g and then g returns, you're back to f, in the same context as before (“context” here means the values of local variables).
• You can't return from the top level of the program that's not inside a function. (Depending on the programming language, this may not even be a thing: the program may start directly by calling a certain function, so that there's no way to have code outside of any function. Or a ”return“ statement outside of any function may exit the program instead.)
• These properties also apply if there are additional sequences of function calls involved that return back to the original function.

Looks familiar? Yep, the function calls form a stack. (Many programming languages have ways to break the stack structure, such as exceptions which can pop many values from the function call stack in a single statement, or even more complex things that I won't go into.)

The way the function call stack is implemented on a processor is usually through a stack of return addresses. Each function call does a push of the current value of the instruction pointer before jumping to the code of the called function, and returning from a function is a pop in that stack and a jump to the popped address.

Each time a function is called, its local variables come into existence. So the variables, in turn, form a stack. Calling a function pushes a new entry on the variable stack for this function's variables, and returning from a function pops an entry from the variable stack. (You can model this either with a single entry for all of a function's variables and a single push/pop per call/return, or with one entry per variable and as many push/pop per call/return as the function has variables.)

Note that variables are associated with a function call, not just with a function. When a function is called recursively, or more generally as part of a chain of calls of mutually recursive functions, each function call has its own variables, even if they happen to be calls to the same function. Conversely, local variables of a function don't “exist” while the function isn't being called. (Some of the very first programming languages had one storage area per routine, which existed all the time. These languages did not permit recursive calls. No modern programming language works that way, but some hardware description languages do.)

In a language with dynamic scoping, if a function f calls a function g, the code of g can access the variables of f by name. This is an example of a stack with extra operations: the code of g can read and modify the variables of f. The code of g can't create new variables of f or destroy variables of f, so this is still a stack. In a language with [lexical scoping]9https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping), the code of g can't access the variables of f by name, but it may nonetheless be able to access and modify their value if it can see a pointer or reference to a variable of f.

---

So far I've described how almost every programming language works. The specifics of what “the variables of a function call” means depends on the programming language. There's the association between the variable name and its value, and there's the value itself. Most programming languages have three classes of storage: global (exists for the whole lifetime of the program), stack (lasts as long as a function call), and heap (can be created and destroyed arbitrarily). But how apparent this is depends heavily on the language. In most higher-level languages, these classes of storage are a detail of how the compiler or runtime environment works, because storage allocation and destruction is automatic. Variables have a scope (the parts of the program where a certain name refers to that variable). Storage usually doesn't have an explicit scope in higher-level languages, but it does in lower-level languages.

In Rust, the scope of storage is explicit. A variable's storage lives as long as the variable lives, i.e. until the function returns. It lives longer if the value is returned from the function. Heap storage requires explicitly boxed values.

---

Now that I've described what a stack is as an abstract data structure, and how it arises when describing the theory of programming languages, I'm finally read to discuss how it works in the implementation of a programming language. Here, I'm going to describe how most implementations of most programming languages work when compiled to native code. (Languages compiled to byte code are typically fairly similar, but may be a bit further from this simplified description.) It's possible to do things differently, but unusual. I'm also going to keep things simple and not go into details that aren't important to understand the basic concept, such as registers, function parameters, return values, block scope, etc.

The typical way to implement a function call stack is to store the return addresses and the local (unboxed) storage for its variables in a single memory area. This specific method of implementing the stack abstract data structure is also called a “stack”. The stack of memory management for function calls works this way:

• There's an array of memory which is reserved for the stack.
• Pushing means copying a value to the top of the stack and incrementing the stack pointer, which is an index into the array of memory.
• Popping means reading the value at the top of the stack, then decrementing the stack pointer.
• To call a function, push the current value of the instruction pointer, then push enough storage for the function's local variables. The set of things pushed at this stage constitute a stack frame.
• To return from a function, pop the stack frame and jump to the return address.

As long as a function call is in progress, its variables are in its stack frame. To access them, you need to know their address. To access a variable of the current function, all you need to know is its position in the stack frame. And the address of the stack frame of the current function is the top of the stack minus the frame size. So for example, let's imagine a simple (unoptimized) compiler for a simple programming language and the following program fragment in a function:

variable a = 22;
variable b = 33;
variable c = 2 * a;

This is compiled as: * Allocate a frame with room for three variables. * Write 22 to the address sp - 3 where sp is the stack pointer. (For simplicity, in this example, I assume that all variables have the size 1. Having differently-sized variables just requires keeping track of their sizes and doing additions at compile time.) * Write 33 to the address sp - 2. * Read a value from the address sp - 3, multiply the value by 2, and write the result to the address sp - 1.

As you can see, accessing a variable doesn't require popping to it. This is because computer memory itself is not a stack, but random-access memory. The stack that contains the local variables is a stack only because it grows and shrinks according to a stack pattern, not because it's impossible to access elements that are not at the top.

Accessing a variable of a function which isn't the current one doesn't require popping to it either. It does require knowing the address of that variable. If a variable has access to another function's variable, this can be either because the variable was passed as a parameter, or because the current function has access to a reference (pointer) to that variable. In either case, what happens under the hood is that the address of the variable is stored somewhere where the called function can access it.

Answer 2

What you looked at was the simplest form of a stack, where you can put one item on the top of the stack, remove one item from the top of the stack, and access the item on the top of the stack.

You can instead use a slightly more complex version of the stack, where you can add k items on the top of the stack, remove those same k items, and access the k items on the top of the stack.

In your example, you needed space for three variables, so you add space for three variables on the stack when the function is entered, you remove space for three variables when the function is removed, and can access all three variables on the top of the stack. Each function has a different number of variables it needs to make space for on the stack. And in most languages, there is indeed no way to access variables higher up in the stack (nested functions in Pascal are a rare exception).