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

[Standish P]

On Aug 16, 12:47 am, Nick Keighley <nick_keighley_nos... at hotmail.com>
wrote:
> 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.

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 its_curr_val.next.

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 gmail.com>