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

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.

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 mod

StackExchange Computer Science Q#123576, answer score: 2