On Aug 16, 12:47 am, Nick Keighley <nick_keighley_nos...@hotmail.com> wrote: > this is heavily x-posted I'm answering from comp.lang.c > > On 16 Aug, 08:20, Standish P <stnd...@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...@gmail.com> -- http://mail.python.org/mailman/listinfo/python-list
