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

Standish P stndshp at
Mon Aug 16 10:33:51 CEST 2010

On Aug 16, 12:47 am, Nick Keighley <nick_keighley_nos... at>
> this is heavily x-posted I'm answering from comp.lang.c
> On 16 Aug, 08:20, Standish P <stnd... at> wrote:
> > [Q] How far can stack [LIFO] solve do automatic garbage collection and
> > prevent memory leak ?
> I'm having trouble understanding your question (I read your whole post
> before replying). I strongly suspect the only connection your question
> has with C is that you are using C as your implementation language. I
> think you're trying to ask a question about memory management. You
> might be better off asking your question in a general programming new
> group such as comp.programming (sadly rather quiet these days).
> Note that C doesn't do automatic garbage collection. Memory is either
> freed on exit from a scope (stack-like memory lifetime) or explicitly
> (using free()). Static memory is, conceptually, never freed.
> > Because a stack has push and pop, it is able to release and allocate
> > memory.
> I'm not sure what you mean by some of the terms you use. In a sense a
> pop *is* a release. The memory is no longer available for use.
> > We envisage an exogenous stack which has malloc() associated
> > with a push and free() associated with a pop.
> "exogenous"? Why would you do this? Are you envisioning a stack of
> pointers? The pointers pointing to dynamically allocated memory? Well,
> yes, sure you could implement this in C. It isn't garbage collection
> by any standard definition of the term.

I can clarify what I mean.

Most books implement a stack with a fixed length array of chars and
push chars into it, for eg k&r.

I have a dynamically allocated array of pointers. The cons cell is
allocated as well as the data is allocated for every push and the
pointer points to

Similarly, every pop would move the pointer to its_curr_val.prev. It
would also free the cons cell and the data after making a copy of the
data. Below I explain your point on memory hanging.

> > The algorithm using the stack would have to be "perfect" to prevent
> > stack overflow or condition of infinite recursion depth.
> the memory lifetimes must be stack-like (or close to stack-like)
> > This would
> > involve data type checking to filter out invalid input.
> I'd be more concerned about the memory allocation/dealllocation
> pattern rather than the data types.
> > The task must
> > be casted in an algorithm that uses the stack. Then the algorithm must
> > be shown to be heuristically or by its metaphor, to be correct using
> > informal reasoning.
> why informal reasoning? Why not formal reasoning?
> > Are there any standard textbooks or papers that show stacks
> > implemented in C/C++/Python/Forth with malloc/free in push and pop ?
> well it doesn't sound very hard...
> > If Forth is a general processing language based on stack, is it
> > possible to convert any and all algorithms to stack based ones and
> > thus avoid memory leaks since a pop automatically releases memory when
> > free is an intrinsic part of it.
> don't understand the question.
>    - is forth a general purpose language? Yes
>    - are all algorithms stack based? No

Does Forth uses stack for all algorithms ? Does it use pointers , ie
indirect addressing ? If it can/must use stack then every algorithm
could be made stack based.

> some compuations simply need to hang onto memeory for a long time
>     alloc (obj1)
>     alloc (obj2)
>     alloc (obj3)
>     free (obj2)
>     long_computation()
>     free(obj3)
>     free(obj1)
> this simply isn't stack based. the memory for obj2 cannot be reused on
> stack based scheme whilst long_computation() is going on.

In theory the memory can be locked by a long_computation() . But a non-
stacked based algorithm can also ignore freeing a memory and cause
memory leak, just as an improper usage of stack cause the above
problem. The purpose of a stack is to hold intermediate results ONLY.
Only intermediate results should be below the long_computation, not
those that need not wait for it. That is why heuristic or metaphorical
thinking which considers all aspects simultaneously in a visual human
brain thinking has less chance of error in conceiving such solutions
than formal disjoint and symbolic thought.

> > K&R ANSI has the example of modular programming showing how to
> > implement a stack but he uses a fixed length array. It is also
> > possibly an endogenous stack. We look for an exogenous stack so that
> > element size can vary.
> malloc the memory? I see no garbage collection in your post

a stack properly used does not need separate garbage collection.
freeing is an automatic part of calling pop.

Thats the superiority of a stack based algorithm over linked lists of
unrestricted kinds.

Standish P <stnd... at>

More information about the Python-list mailing list