1. Introduction
In this tutorial, we’re going to look at the call stack mechanism. We’re going to find out how it works, what it is intended to do and how does the famous stack overflow error occurs.
Nowadays the most popular programming languages are high-level and a lot of things are away from the programmers using them. Most of the time, however, a lot of work is happening under the hood. While the actual details of program execution may vary by the type of compiler, operating system, and instructions themselves, most of them manipulate a chunk of memory commonly referred to as “call stack” or simply “the stack”. This is why it’s worth having at least a high-level view of it.
2. Stack Definition
A stack, in general, is an abstract data type that is used to add and remove data elements in a last-in-first-out (LIFO) manner. As an analogy, we might think of the stack as a stack of books in which we can only take out or add books from the top. In computer science terminology, adding an element to the stack is also referred to as ‘push’, and removing an element from the top is known as a ‘pop’.
Initially, having a restriction for adding and removing elements might sound like a handicap but it is what makes the stack a very handy tool in programming and computer science in general when dealing with nested sequences.
3. The Call Stack
The call stack, in particular, is a stack mainly purposed to organize multiple instructions and keep track of their execution. When our program calls a function the first thing the program compiler, interpreter, or system(depending on implementation) does is to set aside some chunk of memory for the function to do its necessary work. The chunks are also often called stack frames and they usually contain at least a few things:
- the called function’s arguments that were passed to it
- some space reserved for local variables
- a return memory address used to point where to return the function’s result
Since the function needs its stack frame to work, it’s important to think about how to provide its necessary access during execution. But how can we organize the memory in such a way that we can handle sequential instructions?
4. Simple Example
Let’s consider for example a simple program with the function main which contains another function called greet which in itself will call a print(“Hello”) function:
function Greet():
print 'Hello'
function Main():
Greet()
The system will reserve memory for each of them, but we can have only one running at a time, so one might wonder, how does the computer know which function to run first?
The system will reserve memory for each of them, but we can have only one running at a time, so one might wonder, how does the computer know which function to run first?
We cannot run main without running greet and can’t run greet if we don’t run print. And this is where the stack data structure comes in handy. When a function is called it becomes active and we push its frame on top of the call stack. Additionally, each time a new function is invoked we immediately push its frame on top of the stack and it becomes the active frame. This way we ensure that there is only one active function at a time, making the process threadsafe.
When a function finishes its execution we pop its frame. And since the stack frame contains a return address pointing to the stack frame of the function that is called it, we can easily go switch back to the parent function. That is the beauty of the stack structure.
Here is a diagram displaying the call stack frames in memory during the simple program that greets us:
5. Stack Overflow
In our simple example, we had just three functions nested inside each other, but sometimes in programming, there is a lot more nesting because we tend to abstract the logic of our programs. And sometimes during runtime, the call stack runs out of reserved memory resulting in an error. We call this type of error stack overflow. Generally, this type of error signals a problem in resource provisioning and since it occurs during runtime can be hard to figure out.
The most common cause of stack overflow is excessively deep or infinite recursion. In such cases, a function calls itself so many times that the space needed to store its individual stack frames becomes more than the size of the stack.
Here is an example of infinite recursion that, if run, is sure to fail:
function Foo():
return Foo()6. Conclusion
In this article, we looked at the call stack, explained the terminology related to it, explored how it is used in programming in general.