# Stack Memory and Local Variables

In todays languages, every call to a function adds new data to ‘the stack’ in the form of the local data for the function, and the value of where to return to in the program when the function completes.  To understand the stack, it can be useful to understand the problem the stack solves.

• Subroutines
• The problem:  PDP-8
• The stack solves the problem
• Parameters on the Stack
• Local Variables on the Stack
• Stack Overflow
• Tracing the stack
• conclusion

## Subroutines

Before functions, there were subroutines.  A program was considered as a ‘routines’ and subroutines were effectively sub-programs.  Blocks of code that could be considered logically as a single instruction by the overall program.  Subroutines quickly evolved by the addition of parameters, local variables and then return values to be what we today generally call functions.  Some languages still have both subroutines (functions with no return value) and functions (with a return value), but many languages now simply think of all as functions.

## The problem: PDP-8

The PDP-8 computer was designed with an instruction set that enabled ‘subroutines’ without using a stack.  The memory location immediately prior to the first instruction of the subroutine holds the return address, which means there can only be one return address.  The problem with only being able to hold one return address is, what if the subroutine has been call from two or more different places?  The second call will overwrite the return address for the first call.  Consider a routine such as factorial when implemented recursively.  For recursion to be possible, each call of the function must have its own return address.  Factorial 3 requires three calls, each with its own return address.

## The stack Solves the problem.

So the stack was introduced as a concept to provide a new set of data for each call.  With a stack, three call allows three return addresses stacked on top of each other on a stack.

The PDP-8 call instruction does the following:

• calculate return address as  the instruction following the current instruction
• save the return address at the location called
• set the program counter to the location following the location called (the location after where the return address was stored)
• To return, the code jumps to value stored at the call location

A new stack based call would be as follows:

• calculate return address as  the instruction following the current instruction
• save the return address at the location of the stack pointer and subtract one from the stack pointer
• set the program counter to the location called
• to return, add one to the stack pointer and jump to the location stored at the location pointed to by the stack pointer.

The stack approach, requires the following:

• An area of memory allocated as ‘the stack’
• A different ‘call subroutine’ instruction performing the call steps above
• A stack pointer (which is normally a register of the CPU), set to the base of the stack before any subroutine calls
• A return instruction performing as described above

## Parameters on the Stack

In the real world of modern programs, subroutines also accept parameters.  Consider the factorial equation, and the call requires the number for the factorial as a parameter. Again, it should be considered that there may be more than one call to the subroutine active, so separate storage is required for each call.   The stack again provides the solution. Simply push the parameter onto the stack prior to calling the routine, and within the routine the parameter can be accessed using an offset from the stack pointer.

## Local Variables on the Stack.

The next concept was to add ‘local variables’.  From the beginning a subroutine could have a variable in global storage that only that subroutine made use of as a type of ‘local’ variable,  but again the problem of multiple copies of the subroutine would occur with several calls to the function all using the same memory locations for local variables. The solution it to allocate a block of ‘local variable storage’ when the subroutine is called.  At the start of the subroutine, the stack pointer is adjusted by the number of bytes required to reserve memory for local variables, and a reverse adjustment is required at the end of the subroutine.  The diagram here on Wikipedia illustrates a stack where there has been a subroutines call, and then that subroutines has also made a call.

## Stack Overflow.

The amount of information on the stack has grown from the original return address.  With the return address, parameters and space for local variables, the amount of stack space used by any given routine can be significant.  Nesting, or the process of one routine calling another, grows the space required for the stack.  Too many levels of nesting, particularly with routines making use of a lot of local storage, and the stack can run out of room or ‘overflow’.  In reality most stack overflows occur as a result of infinite recursion.

## Tracing the stack.

During debugging, tracing back through the stack can be the only way to understand complex problems, and a ‘stack trace’ or listing of the stack contents the only way to determine the exact state of a program.

## Conclusion

The stack or ‘call stack’, has become an integral part of how functions and subroutines actually operate.  Understanding the call stack is critical to fully understanding how programs work.