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

Nick Keighley nick_keighley_nospam at hotmail.com
Mon Aug 16 09:47:44 CEST 2010


this is heavily x-posted I'm answering from comp.lang.c

On 16 Aug, 08:20, Standish P <stnd... at gmail.com> 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.

> 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

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.

> 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




More information about the Python-list mailing list