Re: Stack vs. heap?

[Don Bruder <dakidd@sonic.net>]

In article <1150899353.663581.85070@y41g2000cwy.googlegroups.com>,
 "mdj" <mdj.mdj@gmail.com> wrote:

> Martin Doherty wrote:
> > I believe I thoroughly understand the operation of a stack, but the term
> > "heap" is a mystery.  I know it's used in UCSD/Apple Pascal for memory
> > management functions of some kind; can anyone explain to me what a heap
> > is in general concept, and what it's used for in Pascal?
> 
> In general, the 'heap' is the block of space, either starting where
> your program code ends building up, or starting where memory ends
> building down, which is used for dynamic memory allocation.
> 
> The Apple's 6502 has a fixed hardware stack, which resides at memory
> locations $100-1FF. Most systems even slightly more modern than 6502
> allow the stack to be placed anywhere in memory, so it usually ends up
> at one end of program space or the other, depending on the way the CPU
> works.
> 
> In Apple Pascal, while it's called a 'heap' the actual data structure
> employed is a stack. You have a pair of operations - mark, which
> records the current top of heap, and release, which sets the current
> top of heap pointer. Each time you call new in pascal to allocate a new
> object, the top of heap pointer is decremented by the number of bytes
> it takes to store an object of that type.
> 
> So that's Apple Pascal, who's heap is actually a stack. 

*KIND OF*...

A stack always consists of same-sized units (usually, but not always, 
native machine-words) which get operated on atomically (at least from 
the high-level language programmer's perspective - The push and pull/pop 
operations on it may or may not actually be atomic at the machine 
language level, depending on the particular CPU and the routines that a 
given language uses to implement its stack) while a heap gets 
allocated/deallocated (by new/mark and release/dispose) in 
arbitrarily-sized, programmer specified chunks, and may or may not 
appear to be atomic to the programmer. A heap is much more like the 
linked list that you talk about later, in that it *CAN* be (not that 
doing so is a good idea under most circumstances, but the possibility 
exists when such a practice makes sense) randomly accessed, while a 
stack is *ALWAYS* LIFO.

The Apple Pascal heap is "Stack-like", in that the "best practice" is to 
always balance your "new/dispose" or "mark/release" calls. However, 
doing so is *NOT* mandatory. With a stack, LIFO is the way it is - 
period. (barring excursions to machine language routines or similar that 
permit the programmer to manipulate the stack pointer "behind the 
compiler's back", so to speak. But then, we're no longer talking about 
"pure" Pascal.)

> Most
> implementations of Pascal include an operator called dispose, which
> teamed up with new, does automatic heap management. Unfortunately you
> don't have this functionality in Apple Pascal. In C, the equivalent
> standard library functions are malloc(), and free() (althought C also
> has a realloc function for convenient resizing of arrays, etc)
> 
> You'll actually find that most systems use a fairly simple allocation
> scheme for heaps, like a linked list.
> 
> Now if that's not confusing enough, this heap is not to be confused the
> data structure called a heap, which is (generally) speaking a
> specialised form of tree structure, such that a parent node is always
> greater than, or equal to it's children. This is commonly used to
> implement priority queues, or sometimes for sorting.

That's a binary tree, not a heap. A binary tree is almost certainly 
implemented within the confines of the heap, but it is not, in and of 
itself, actually a heap. At best, it could be considered a "sub-heap" of 
the main program heap. 

A heap, by definition, has *NO* inherent structure - It is, as the name 
implies, a "heap" of bytes, available for whatever use the programmer 
sees fit to put them to, in whatever size chunks, having whatever (or 
none whatsoever) structure he cares to use them for. The programmmer is 
100% responsible for properly dealing with a heap-objects he 
allocates/deallocates via the mark/release or new/dispose functionality 
provided by the language. "Fancier" languages *MAY* implement some form 
of garbage collection to assist the programmer by maintaining the heap 
as a contiguous block of "available heap space" through coalescing 
released heap objects into a block "behind the scenes", but that 
behavior is entirely optional, and the results of having it happen 
*CANNOT* be counted on from one implementation to the next if any sort 
of "sanity" is to prevail. Likewise, any structure imposed on a heap is 
purely the responsibility of the programmer imposing said structure, and 
the compiler will cheerfully let the programmer shoot himself in the 
foot if he isn't careful with what he does. Stack-tinkering, on the 
other hand, is either impossible (within the constraints of the language 
being used) or strictly checked at compile-time, and always operates on 
fixed-size objects which get pushed onto, or popped/pulled off of the 
stack in what appears (to the programmer) to be an atomic operation, 
with the last pushed object being the first to get popped/pulled off the 
stack. (as mentioned above, barring the programmer "breaking the rules" 
by tinkering with the stack pointer through some mechanism outside the 
rules of the high-level language he's using)

A stack is the spring-loaded pile of plates at the end of the salad bar 
- Last one put on the stack is the first one grabbed. A heap is the 
various buckets of salad-makings on the salad bar - some lettuce here, 
some radishes there, some cucumbers someplace else, etc, and there is 
*NO* enforced order as to which you hit first. Although common sense 
says you probably want the lettuce, tomatoes, and other "stuff" before 
you add the dressing, there's nothing stopping you from starting with 
the dressing, and going backwards to the lettuce bowl if that's what you 
actually want to do.

-- 
Don Bruder - dakidd@sonic.net - If your "From:" address isn't on my whitelist,
or the subject of the message doesn't contain the exact text "PopperAndShadow"
somewhere, any message sent to this address will go in the garbage without my
ever knowing it arrived. Sorry... <http://www.sonic.net/~dakidd> for more info