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

[spinoza1111]

On Aug 16, 3:20 pm, Standish P <stnd... at gmail.com> wrote:
> [Q] How far can stack [LIFO] solve do automatic garbage collection and
> prevent memory leak ?
>
> Because a stack has push and pop, it is able to release and allocate
> memory. We envisage an exogenous stack which has malloc() associated
> with a push and free() associated with a pop.
>
> The algorithm using the stack would have to be "perfect" to prevent
> stack overflow or condition of infinite recursion depth. This would
> involve data type checking to filter out invalid input. 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.
>
> Are there any standard textbooks or papers that show stacks
> implemented in C/C++/Python/Forth with malloc/free in push and pop ?
> 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.
>
> 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.
>
> =======
> Standish P <stnd... at gmail.com>

Garbage collection doesn't use a stack. It uses a "heap", which is in
the abstract a collection of memory blocks of different lengths,
divided into two lists, generally represented as linked lists:

1.  A list of blocks that are free and may be used to store new data

2.  A list of blocks that are in use, or haven't been freed (yet)

There is no way you could do memory management of all but the most
trivial and fixed-length data chunks using a stack. Sure, you could
reserve thousands of bytes on the stack for an array but suppose your
language allows arrays to grow or shrink. To keep its property of
being adjacent, you'd have to do something horrible such as move
unrelated data allocated later, which raises all sorts of security
issues, doesn't it.

A stack, or something which works like a stack (that is, a stack) is a
necessary but not sufficient condition for a working C runtime because
C functions can call themselves recursively, whether directly or
indirectly. If this last condition did not obtain, each function could
give the functions it calls some of its own memory and the called
function could save a fixed set of non-stacked general registers in
that area; this was in fact the practice on IBM 370 and in assembler
language at a time when many "data processing managers" though
recursion was a Communist plot.

However, data structures of variable size, or data structures that
merely take up a lot of space, don't play nice with others on the
stack, so, we place their address on the stack and store them in
another place, which was named the heap, probably, as a sort of
witticism.

Gilbert and Sullivan:

If anyone anything lacks
He'll find it all ready in stacks

was wrong, and needs to be brought up to date:

You cannot do everything in a stack
Unless you code an almighty hack
If you're a coding Knight who says, "Neep",
You'll probably need to implement a heap
A pile a heap of benefits you'll reap
If only my advice in your brain you'll keep
And avoid memory leaks from which data doth seep
By using a well-implemented, well structured, and well-documented
Heap!

[Chorus of Sailors]
We will to heart your advice take, and always use a heap!

[Soloist]
Oh thank you do
To this be true
And always my sage advice do keep
That you always need to use a heap!