Run-time stack

[pX]

I'm an EE grad student but taking a comparitive languages classes (mainly because I want to learn lisp). Right now we are just dicussing fundamental language stuff like binding, type checking, scope, storage, etc. I am the only non-CS in the class so they throw around a lot of things that I understand in context but not completely. Someone explain to me what the "run-time stack" is? I know what a stack is, as far as assembly programming, but not really sure what it means to higher level programming languages. Thanks!

 

[Gunslinger08]

Think of the stack as a storage place for records of the program at different points. Because programs branch out (loops, conditional statements, recursion, etc.), they must stop what they're doing and perform another task before they can continue. To do this, they save the state of the process (sometimes called an activation record) to the stack and then do whatever they need to. Once they're finished, they read the top record from the stack and finish it's execution. After that, it continues down the stack until nothing is left (branching along the way and creating new records at the top, if necessary).

 

[DaveSimmons]

In other words, the same as the assembly stack

In assembly within a function you create local variables on the stack, and you do exactly the same thing in higher level languages.

C++

int sum ( int a, int b )
{
int sum ; // I go on the stack!
int* pjunk = new int ; // I was created on the heap not the stack

sum = a + b ;
return sum ;
}

(the stack also holds where to return to, just like in assembly)

 

[kamper]

Originally posted by: DaveSimmons
In other words, the same as the assembly stack

In assembly within a function you create local variables on the stack, and you do exactly the same thing in higher level languages.

C++

int sum ( int a, int b ) // <-- we go on the stack too!!
{
int sum ; // I go on the stack!
int* pjunk = new int ; // I was created on the heap not the stack

sum = a + b ;
return sum ;
}

(the stack also holds where to return to, just like in assembly)

Yeah, stacks are pretty much common to all languages (at least procedural ones, can't say I know functional ones too well so maybe lisp has a different paradigm).

 

[xtknight]

void func(int var1, int var2)
{
func(var1, var2);
}

This will eventually cause a stack overflow (too much "recursion"). So yeah, stacks do store arguments passed to functions as well.

Side question: How big is the stack though?

 

[IHateMyJob2004]

I know, I know .... if you are an EE, you probably need not be concerned with stacks and such unless you want an A.

 

[Markbnj]

A little bit of color to add to the previous explanations. Why do they call it a stack? Because somewhere back in the dawn of computing some young researcher was trying to think of a metaphor for the data structure he had in mind, one which would allow him to save the state of each function call as program flow progressed from function to function. He saw a spring-loaded stack of plates in a cafeteria, and the term was coined. I used to know who it was and where it happened, but have forgotten, and couldn't find it. The analogy is now in very widespread use to describe the operation of a stack. It appears in Mark Chasin's 1984 book on Atari assembly language programming, but I'm sure even then he was just repeating it.

Stacks are devilishly interesting structures. They are architecturally simple in the extreme, but can be used to implement all sorts of state machines. To visualize one, you can think of the plate analogy, but to visualize what they are for, I like the bread crumb analogy.

Suppose you walk into an old mine, with tunnels branching every which way into the darkness. As you walk in you choose various branches, and are soon deep into what is essentially a n-ary tree. The stack is like a trail of bread crumbs that you drop on the floor as you walk in. When you want to leave you turn and follow them out. A program is also an n-ary tree of possible paths of control flow. A function A may call functions B or C depending on decision criteria, and then B may call D or F, and C may call E or G, and so on. At some point a function does its work and returns without calling any other function (this function is what we think of as a "primitive"), at which point the flow of control "unwinds" back through all of the previous functions. Each of them has a "frame" of processor state and local variables that was saved ("pushed") onto the stack. When the flow of control reenters that function the processor state and any local variables are "popped" off the stack.

It seems confusing to most people at first, but then you get it in a flash and you're done with it. It really is that simple at heart. Get it, and you'll understand programming .