10. Stack example

Calling a subroutine

The executing program maintains a stack to help control the flow of instructions.

A program is often divided up into a main loop that calls a number of 'subroutines'. Each subroutine has a specific task. A subroutine often needs some information passed into it in order to carry out its task. This information is called its 'parameters' and typically looks like this.

return_largest_value(list,length)

There can be many parameters passed into a subroutine.

This subroutine, judging by its name, returns the largest value in a list. The first parameter provides the location of the list in memory, the second parameter supplies the length of that list.

The main loop will 'CALL' this subroutine. The 'call' operation will first of all place on to the stack the address of the machine code that is calling the subroutine, then it adds the parameters of the subroutine on to the stack. Finally, the CALL operation jumps to the starting address of the subroutine. The stack looks like this

The first thing the subroutine does is to POP the parameters off the stack. It knows how many parameters to POP. So the stack now looks like this

The subroutine carries out its task.

The end of the task is often marked by a 'RETURN' statement within the subroutine. The return operation will POP the calling address from the stack and if required will PUSH a return value onto the stack. Control now jumps back to the instruction at the calling address. The calling machine code may then POP the result off the stack.

This is how a stack is used to jump from one subroutine to another.

A subroutine can call another subroutine before finishing. So it is possible for a whole chain of subroutine calls to be PUSHed onto the stack and then POPed in reverse order.

Note that the compiler takes care of the CALL and RETURN operations, the software programmer simply writes the call function statement and the return statement according to the grammar of the computer language being used.

Basic Problem with Stacks: Overflow and Underflow

A stack cannot grow indefinitely.

When it comes to its limit and yet another operation tries to PUSH data onto the stack then a 'stack overflow' occurs. When this happens it often causes the program to crash. It is up to the software programmer to ensure that the stack does not overflow.

If the stack is empty and yet a POP operation is attempted, this is called an 'stack underflow' and can cause a program to crash. The software programmer should check that the stack is not empty before attempting a POP operation.