System Stack question

[AresSupreme]

Firstly hi all! I am new to these forums.

My professor gave me a question for my final study guide that I don't understand. It is in our "functions" chapter. Here is the question.

6. What role does the system stack play in the execution of functions? What are the two primary operations of the stack and what do they do?

Also there when I completed the study guide I ran into another question I couldn't answer

11. In what sequence are “stack frames” processed in the system stack?

I answered
all of the questions but stack frames are outside of my level of understanding since I don't actually see them in code.

[Smac89]

Basic operations are push and pop.

In basic terms, a function call pushes the address of the function onto the stack. And as soon as execution leaves the scope of the function, the address is popped from the stack.

So in every program you run in c/c++, you can assume that int main is at the bottom of the call stack and as soon as your program has finished executing, main is popped

[AresSupreme]

That explains it better than anything I have googled. Thank you!

[giblit]

Another way to look at not sure the exact positions in ram but generally from 0 - 1/3 is Static memory (staics/globals are here) , 1/3 - 2/3 is heap memory(where you can ask for memory using new) , 2/3 - end is stack for functions/locals.

Basically stack starts at the last part of memory (main function) then each call it pushes 1 before it and then when it is removed it is popped and then the nxt function calls can go there like smac mentioned earlier.

http://stackoverflow.com/questions/408670/stack-static-and-heap-in-c

[i like red pandas]

Think of a stack kinda like... a stack of dishes. To get a dish, you have to take one of the top (if you don't want to risk a giant tower of dishes collapsing on you), and to add one to the stack, you need to put it on top. This is an example of a LIFO (last in, first out) structure.

Then the two primary operations of a stack are called push and pop. Push will add an item onto the top of the stack, and pop will take the item from the top of the stack. Sometimes you also get a peek operation that lets you look at the top the stack.

The system/call stack is essentially what handles the execution of functions. It stores information about function calls and their execution order. As the name implies, it resembles the stack data structure. When you call a function, a stack frame is created and pushed onto the stack. The stack frame contains info on variable and parameter values, as well as a return address. When execution of the current function completes, the frame is popped off the stack and returns whatever value to the return address. If another function is called during the current one, we allocate a new stack frame for the new function, and push that on the stack. We execute that, then pop it off the stack when it completes and return to our current function's stack frame.

Below is an example of stack frames in C/C++:

// this is going to be in pseudo C code

int f() { return g(); }

int g() { return h(3); }

int h(arg) { 
	if arg == 0, { return 1 and print stack; }
	else, h(arg-1)
}

int main() {
	f();
	return 0;
}

So, if we freeze the program at the point where it says print stack, we get:
- call to main starting the C program
- call to f
- call to g
- call to h with argument 3
Since h is recursive, it calls itself with a different argument until it reaches the base case.
- call to h with arg 2
- call to h with arg 1
- call to h with arg 0

Therefore our stack frame will look something like this:

--------
h: 0
return: 
--------
h: 1
return: h
--------
h: 2
return: h
--------
h: 3
return: g
--------
g:
return: f
--------
f:
return: main
--------
main:
 data
return: OS
--------

[AresSupreme]

Ok, I get all of that now though it's a bit foggy, it's better than being completely lost. The plate analogy helped a lot thanks guys.

I am still a little foggy on the order in which stack frames are processed. is that like when i call a function it goes to the frame, and then is popped off with the value returned?

[Smac89]

AresSupreme wrote:

I am still a little foggy on the order in which stack frames are processed

@i like red pandas mentioned in his post that a stack is processed in the order LIFO (last in, first out).

AresSupreme wrote:

is that like when i call a function it goes to the frame, and then is popped off with the value returned?

Yes but the return value of the function is processed just before the function call is popped off the stack.

imaging a simple addition program:

int add(int data[])
{
    if (data == nullptr)
        return 0;
    return *data + add(&data[1])
}

if the function is called with the array {3, 4, 5, 6}, the resulting call stack of just the function is:

[ *add(), {3, 4, 5, 6}, [] ]

return [code]*data + add(&data[1])[/code]

[ *add(), {4, 5, 6}, [] ]
[ *add(), {3, 4, 5, 6}, [] ]

...
[ *add(), {}, [0] ]
[ *add(), {6}, [] ]
[ *add(), {5, 6}, [] ]
[ *add(), {4, 5, 6}, [] ]
[ *add(), {3, 4, 5, 6}, [] ]

Function calls are complete, now return a value

[ *add(), {6}, [6 + 0] ]
[ *add(), {5, 6}, [] ]
[ *add(), {4, 5, 6}, [] ]
[ *add(), {3, 4, 5, 6}, [] ]


[ *add(), {5, 6}, [5 + 6 + 0] ]
[ *add(), {4, 5, 6}, [] ]
[ *add(), {3, 4, 5, 6}, [] ]

...

[ *add(), {3, 4, 5, 6}, [3 + 4 + 5 + 6 + 0] ]

18