How far can stack [LIFO] solve do automatic garbage collection and prevent memory leak ?
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
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
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