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

[Nick Keighley]

On 16 Aug, 09:33, Standish P <stnd... at gmail.com> wrote:
> On Aug 16, 12:47 am, Nick Keighley <nick_keighley_nos... at hotmail.com>
> > On 16 Aug, 08:20, Standish P <stnd... at gmail.com> wrote:

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

I also note that another poster has suggested you are a troll/loon

you seem to be using some computer science-like terms but in an oddly
non-standard manner

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

no at all. How can a goldfish whistle?

> > 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).

this still applies

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

this isn't inherent to a stack implementaion. A stack could be a
malloced block of memory or a linked list.

> I have a dynamically allocated array of pointers. The cons cell is

that *what*? Are you trying to implement Lisp in C or something. Try
comp.lang.lisp for some help there. Have you read "Lisp In Small
Pieces"? Good fun.

> allocated as well as the data is allocated for every push and the
> pointer points to its_curr_val.next.

I'm lost. What does a cons cell have to do with a fixed array of
pointers? Why do you need dynamic memory? Aren't cons cells usually of
fixed size? How can a Lisp-like language use a stack based memory
allocation strategy?

> 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 ?

don't know. Ask the Forth people. Some algoritms are fundamentally not
stack based. If you try to implement them in Forth then either some
memory isn't claimed as soon as possible (a leak) or there is some way
to to have non-stack based memory management.

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

no not really

> Only intermediate results should be below the long_computation, not
> those that need not wait for it.

then you don't have stack-based memory allocation. Make your mind up.

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

sorry, I thought we were talking about computer programming not hippy
crustal healing.

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

and also its weakness.