Stack Theory
Posted on 06-14-2006, by Adrian
Stacks are extremely important in programming. Every high-level language has the concept of the stack, and uses a stack to control function execution. Heres how stacks work.

Say you have 2 functions, main and recurse, a recursive function that will print out a message n times, where n is the integer argument passed to it. Written in c++, this might look like:

Code:
void recurse(int n)
{
  if (n > 0)
  {
    cout << "This is a recursive function!\n";
    recurse(n - 1);
    //return point 2
  }
}

void main()
{
  recurse(2);
  //return point 1
}



This code will print "This is a recursive function!\n" 2 times to the screen. While seemingly simple, this code has a lot of subtle interactions, especially in dealing with the stack. First, lets just go over how the function calls look on the stack.

First, main will call recurse with its argument being 2. The stack is pushed down far enough to accomidate for two peices of information; the argument and the address of the next line, which will be '2' and 'return point 1', respectively.

Stack, before setting up call to recurse
[ ] <- stack top
[ ]
[ ]
[ ]
[ ]
[ ]
Stack, after setting up call to recurse
[ 2 ]
[return point 1 address]
[ ] <- stack top
[ ]
[ ]
[ ]

Recure will be called, and it will begin execution. Recurse checks the stack for its arguments; it knows where it is because it knows the current stack top and knows that its argument will be in the memory 2 less than the top. So it goes ahead and outputs its message, etc, until it gets to the call to recurse. Again, the stack is pushed down and the information is loaded into memory - on top of the previous information. See how it looks below.

Stack, before setting up call #2
[ 2 ]
[return point 1 address]
[ ] <- stack top
[ ]
[ ]
[ ]
Stack, after setting up call #2
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[ ] <- stack top
[ ]
[ ]

Notice that the return address is different; this is because the calling function is no longer main, its recurse, and so needs to return to recurse when its done executing.

Ok, so recurse will again look at the info passed to it by checking out the value 2 less than the stack top; it will retrieve the value '1'. Note that this is different than the first call, even though the first call is still waiting to finish; it is "on hold" till this version of recurse finishes. Ok, so recurse again calls itself, making the stack look like:

Stack, before setting up call #3
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[ ] <- stack top
[ ]
[ ]
Stack, after setting up call #3
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[0]
[return point 2 address]
[ ] <- stack top

Now you can see that recurse will be called, it will check the value 2 less than the stack top, see its 0, and not print out a message. Instead, it will stop executing, and want to return. How does it know where to return to?

The answer is that other piece of information we pushed onto the stack: the return point address. Recurse knows where to return to, because it knows that the return address was pushed onto the stack, and is accesable at 1 less than the stack top. So recurse checks the return address, and gets ready to return. But it doesnt just return; it also decrements the stack pointer, to make sure that the stack pointer isnt pointing to its data anymore, but instead to the calling functions data. This is very important. Without it, the calling function would have its values on the stack be completely unaccesable.

Stack, before return
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[0]
[return point 2 address]
[ ] <- stack top
Stack, after return
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[ ] <- stack top
[ ]
[ ]

Now the stack is pointing to the 2nd call's data, and the 2nd call continues executing. It returns too, making the stack look like

Stack, before return
[ 2 ]
[return point 1 address]
[ 1 ]
[return point 2 address]
[0] <- stack top
[ ]
[ ]
Stack, after return
[ 2 ]
[return point 1 address]
[ ] <- stack top
[ ]
[ ]
[ ]
[ ]

And then the final function call returns back to main, and the stack looks as it did before:

Stack, before return
[ 2 ]
[return point 1 address]
[ ] <- stack top
[ ]
[ ]
[ ]
[ ]
Stack, after return
[ ] <- stack top
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]

There, easy right? Thankfully, C++ takes care of the stack for us; unfortunately, we arent using C++. LC-3 has no inate concept of the stack; if we want to use it, we need to program it into our code.
Difficulty: Advanced - Views: 10984

User Comments

Copyright 2006 © LC3Help.com v1.4.7