How far can stack [LIFO] solve do automatic garbage collection and prevent memory leak ?

[Richard Harter]

On Thu, 19 Aug 2010 04:14:42 -0700 (PDT), spinoza1111
<spinoza1111 at yahoo.com> wrote:

>On Aug 18, 1:44=A0am, James Kanze <james.ka... at gmail.com> wrote:
>> On Aug 17, 6:21 pm, Standish P <stnd... at gmail.com> wrote:
>>
>> > > Garbage collection doesn't use a stack. It uses a "heap",
>> > > which is in the abstract a collection of memory blocks of
>> > > different lengths, divided into two lists, generally
>> > > represented as linked lists:
>> > > 1. =A0A list of blocks that are free and may be used to store
>> > > new data
>> > > 2. =A0A list of blocks that are in use, or haven't been freed (yet)
>> > Is this all that a heap is or is there more to it ?
>>
>> There are many different ways to implement a heap. =A0The above is
>> not a good one, and I doubt that it's really used anywhere.
>
>Actually, that's the only way to implement a heap in the abstract.
>Forest and trees, mate. Mathematically a heap is a block of storage, a
>list of free blocks and a list of allocated blocks. All the rest is
>detail for the little techies to normally, get wrong. The confusion
>between scientific and technical progress is a mirror of the (far more
>serious) confusion between scientific progress and ethical advance.
>
>Sure, when you free a block it is a good idea to see if you can join
>it with its neighbors to get the biggest "bang for the buck".

[snip]

I appreciate your desire to provide a "mathematical" definition
but the one you gave won't quite do.  Your definition does not
specify what is meant by a block.  The notion of defining a heap
as a list of free list and a list of allocated blocks is
unfortunate. Neither a free list nor a list of allocated blocks
is of the essence.

It isn't easy to give a good definition of a heap (in the sense
of a storage heap) but here is a shot at it.

A heap is a data structure consisting of a pair (H,B) of
substructures, operations (split,join), and attribute A where:

H is a set of sequentially addressable elements.  That is, the
elements form a sequence, each element has an integer associated
with it (its address) and the difference between the addresses of
successive elements is a constant, w.  Let h_i be the address of
the initial element of H and h_f be the address of the final
element of H.

B is a set of integers such that (1) each element b of B is an
address of an element of H, and (2) h_i and h_f are elements of
B.  From this definition we can define the successor succ(b) of
each element (h_f has no successor) and we can order B if we
wish.

Given the construction of succ on B we can define block(b) as the
set of elements in H such that their addresses a satisfy

    b <= a < succ(a)

It is trivial to prove that the blocks of B divide H into
disjoint subsets that cover H.

The attribute A is defined for elements of B.  A(b) may have
either of two values - free and inuse.  A block b is said to be
free if A(b) = free and in use if A(b) = inuse.

An address, h, of H is said to be free if A(largest address b in
B that is <= h) = free and in use otherwise. 

Now for the two operations: 

The join operator operates on all free elements of b except h_f.
It removes the successor of an element of b.  The effect is to
set succ(b) := succ(succ(b)).

The split operator operates on all free element addresses in H
that are not element addresses in B.  Let s be the argument for
split.  Split adds s to B.  The effect of split is to find the
largest address b in B that is smaller than s, set succ(s) :=
succ(b) and succ(b) := s.  Note that the successor changes
implicitly follow from the definitions of H, B, split, and join.

The above definition covers defining a storage heap.  It
establishes what blocks are, what the sequence of blocks is, and
how to alter the sequence of blocks.

The important thing here is that free lists/allocated lists are
not basic abstractions; rather they are derived concepts based on
the primitive concept of a block and the operations performed on
a set of blocks.