stack and heap confusion!

In the days before the C language existed, computers used a "stack" for calling functions. On some computers, such as Intel x86 (including Pentium) type computers, the stack is managed by some machine instructions and registers, but for many other computers, the stack is managed entirely by software.

So it might help to understand the stack by understanding it's original use. When a function is called, the important data (the registers) are saved, which includes the location of the next machine instruction following the function call. Then when the function returns, that data gets restored. Since this storing and restoring can occur in functions and subfunctions and such, a "stack" is used to preserve the data for each level.

I did not write that very well; if I were writing a book, I would write it much better. In fact, there are many books that are already written that describe these things very well.

I'm puzzled why you want to know this.

new and delete just work, and forget how or why they work.

Similarly with doing

int a[50];

I've never really bothered about the stack or the heap and I've been writing code for the last 10 years in VC++.

True in version 1.0-1.5 you did have to worry about stack and heap sizes, but post 2.0 you didn't and in version 6.0 + you certainly don't.

Just follow standard C++ guidelines and you'll be ok in 99.99999% of instances.

Darwen.

@Sam and MrViggy: Your posts sound as if the stack is an anachronism which was used in former times to save register values. Note that the requirement to maintain a stack (or an equivalent mechanism) has nothing to do with the hardware architecture, but is simply a requirement for any block structured programming language (compiled or interpreted) which allows for recursive function calls. In other words, a LIFO structure is a convenient way to create and store variables which are local to a function or block. Even if that function is called multiple times, each calling instance uses its own instance of the variables. When you mentioned the processor registers, you were probably thinking of function parameters, which can be passed either on the stack or in registers, but this depends on how the compiler implements it. A different subject is the hardware support for maintaining stack frame pointers in registers, as used by multitasking operating systems when switching contexts.

@darwen: I think it is very important that a C/C++ programmer has a basic understanding of what the stack and the heap are. I've seen too many "programmers" which had appearently learned C++ using that "black-box" approach, and had no clue about what the code they wrote did at the machine level. I've seen most of them stumble sooner or later, and they usually write highly inefficient code. So in my eyes, it is a good idea that Joe asks these questions (I find it rather alarming that his school taught him about MFC, but not about the stack and the heap).

@Joseph: I'll come back to your question later, either with a link or with a try to give an answer myself (it's just difficult to explain that in an understandable way in a few sentences).

I am nearly certain that the specialized processor registers and corresponding machine instructions for a stack originated in microprocessors (such as the Intel 8008 microprocessor, the predecessor to the 8080, from which the Pentium processor architecture is derived) in which recursion in higher-level languages was not used (initially?).

I assume that the PDP-11 processors, in which environment (I believe) C was originally developed, also has stack registers and instructions, but I do not know for sure. Assuming it does, then I assume the processor also did not initially support recursion in higher-level languages.

To get a better understanding of the concept of stacks and heaps, it is necessary to study as many processor architectures, operating systems and language implementations as possible. It is also necessary to understand that the C and C++ language standards do not require use of a stack for function calls, function parameters and local data.

The IBM 360 architecture was designed nearly half a century ago. It does not have a stack or anything equivalent to a stack. Most languages supporting recursion in a 360 architecture do not use a stack for function calls and for passing parameters. Instead, a linked list of stored register data and other vital data is used and the memory for each recursive call is allocated from the equivalent of a heap. I do not know how the C++ language is implemented in a 360 environment, but it is entirely possible that function calls, function parameters and local data are also allocated from the "heap".

I nice historical summary of microprocessors is at Chips ( http://www.antiquetech.com/chips/chips.htm) from the The Antique Chip Collector's web site. It shows that the 8008 has a 7-level (fixed) stack, whereas the 8080 has a stack pointer (register), which is much more useful.

Now, you somewhat reversed the original argument, in part confirming my point of view, and in part contradicting yours.

Maybe the confusion originates from different notions of a stack: While you (both) seem to see the stack rather as part of the hardware, for me it is basically a LIFO data structure which can be implemented independently from any specific hardware. Yes, most processors support the implementation of a stack by providing specialized registers and instructions. But the stack is (in modern processors) not a separate memory area maintained by the hardware, but just one or more arbitrary regions in the addressable memory space, and it's completely up to the OS, or, more generally, to the software, where and how stacks are created and used. An OS just benefits from the specific registers and instructions like PUSH, POP, CALL and RETURN to implement its stack mechanisms. Besides that, the hardware has no notion (in an oversimplified way) of concepts like stack and heap - they are created and maintained by software.
Originally posted by Sam Hobbs
I am nearly certain that the specialized processor registers and corresponding machine instructions for a stack originated in microprocessors (such as the Intel 8008 microprocessor, the predecessor to the 8080, from which the Pentium processor architecture is derived) in which recursion in higher-level languages was not used (initially?).Note that I never said that the stack is needed only for recursion in higher level languages. Using a stack to push the instruction pointer upon a subroutine call and to pop it back upon return is a far older concept (besides that, recursion is no invention of high-level languages - recursive calls have ever been written in machine language, and languages like FORTH were heavily stack-based). What I said is rather the opposite: That a stack (or equivalent mechanism) is a precondition to implementing a high-level language which allows for recursive calls, and if the hardware offers no specific support for a stack, the OS or even the compiler has to provide it.
Originally posted by Sam Hobbs
I assume that the PDP-11 processors, in which environment (I believe) C was originally developed, also has stack registers and instructions, but I do not know for sure. Assuming it does, then I assume the processor also did not initially support recursion in higher-level languages.Yes, the PDP-11 had a dedicated stack pointer, and the JSR and RTS instructions used it. Hower, even without that hardware support, C could have been developed on the PDP-11 - by implementing the call stack as a pure software data structure.
Originally posted by Sam Hobbs
The IBM 360 architecture was designed nearly half a century ago. It does not have a stack or anything equivalent to a stack. Most languages supporting recursion in a 360 architecture do not use a stack for function calls and for passing parameters. Instead, a linked list of stored register data and other vital data is used and the memory for each recursive call is allocated from the equivalent of a heap. I do not know how the C++ language is implemented in a 360 environment, but it is entirely possible that function calls, function parameters and local data are also allocated from the "heap". Yes, again. "The stack" is not part of the hardware, but the concept of a data structure, in the special case we are discussing here, that data structure is used to store instruction pointers and local variables. Its implementation may be specifically supported by the hardware, but need not (as, appearently, in the case of the IBM 360). Hence, a C or C++ implementation on the 360 uses its own stack. It is not the "heap", but just a part of memory it uses as its "stack".
Originally posted by Sam Hobbs So if I must simplify things, perhaps I could say that instead of using the term "stack" it might be bvetter to use the term "local data".I think when talking about C/C++, it is preferrable to use the term "automatic variables". A "local" variable could be static, in this case, it is not created on the stack.

Originally posted by Sam Hobbs
The extent to which the processor has a "notion" of a stack is a matter of opinion. To the extent that the Intel x86 processor architecture has the stack pointer and stack base registers, and machine instructions to maintain the stack, it is possible to say that the processor has a stack. The only significant peice that is not specialized is the memory, as you say.Agreed. However, it is interesting how the differing notion of the term "stack" (the "opinion") has influenced this discussion so far... ;)
I am not sure what would be considered to be an "equivalent mechanism" but a stack is not required to support recursion.An equivalent mechanism would be any kind of LIFO data structure. Or in other words, a data structure which allows you to repeatedly save instruction pointers (and possibly other data) at some time and restore them in reverse order later. Now this could of course be implemented as a linked list or yet some other kind of data structure, but it had to be accessed in a LIFO way - so a stack is commonly used for that.
Not necessarily. A stack is not a necessity for recursion. As said above. "Stack" in the sense of "some kind of LIFO mechanism".

Good. So do I. :)