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

Discussion in 'Python' started by Standish P, Aug 16, 2010.

  1. Standish P

    Standish P Guest

    [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 <>
     
    Standish P, Aug 16, 2010
    #1
    1. Advertising

  2. * Standish P, on 16.08.2010 09:20:
    > [garble garble]


    Nonsense article "We look for an exogenous stack" cross-posted to

    [comp.lang.c],
    [comp.lang.c++],
    [comp.theory],
    [comp.lang.python],
    [comp.lang.forth].

    Please refrain from following up on Standish' article.


    Cheers,

    - Alf

    --
    blog at <url: http://alfps.wordpress.com>
     
    Alf P. Steinbach /Usenet, Aug 16, 2010
    #2
    1. Advertising

  3. Standish P, 16.08.2010 09:20:
    > We envisage an exogenous stack which has malloc() associated
    > with a push and free() associated with a pop.


    What's your use case?

    Stefan
     
    Stefan Behnel, Aug 16, 2010
    #3
  4. Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

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

    On 16 Aug, 08:20, Standish P <> 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.

    > 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

    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.

    > 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
     
    Nick Keighley, Aug 16, 2010
    #4
  5. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 12:47 am, Nick Keighley <>
    wrote:
    > this is heavily x-posted I'm answering from comp.lang.c
    >
    > On 16 Aug, 08:20, Standish P <> 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 <>
     
    Standish P, Aug 16, 2010
    #5
  6. Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On 16 Aug, 09:33, Standish P <> wrote:
    > On Aug 16, 12:47 am, Nick Keighley <>
    > > On 16 Aug, 08:20, Standish P <> 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.
     
    Nick Keighley, Aug 16, 2010
    #6
  7. Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 10:20 am, Standish P <> wrote:
    > [Q] How far can stack [LIFO] solve do automatic garbage collection and
    > prevent memory leak ?
    >

    Most programs can be written so that most of their memory allocations
    are matched by destructors at the same level.

    However the allocations that can't be written this way typically tend
    to be the small frequently-called ones used for nodes in dynamic graph
    objects, or small resizeable buffers to hold strings and the like.
    This is where you get the performance hit with repeated calls to
    malloc() and free().

    So generally it's not worthwhile writing a stack allocator for a
    normal program. That's not to say there aren't a few individual cases
    where it can help performance. (See the chapter "Memory games" in my
    book Basic Agorithms for details about memory allocation strategies).
     
    Malcolm McLean, Aug 16, 2010
    #7
  8. Standish P

    spinoza1111 Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 3:20 pm, Standish P <> 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 <>


    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!
     
    spinoza1111, Aug 16, 2010
    #8
  9. Standish P

    spinoza1111 Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 7:20 pm, Malcolm McLean <>
    wrote:
    > On Aug 16, 10:20 am, Standish P <> wrote:> [Q] How far can stack [LIFO] solve do automatic garbage collection and
    > > prevent memory leak ?

    >
    > Most programs can be written so that most of their memory allocations
    > are matched by destructors at the same level.
    >
    > However the allocations that can't be written this way typically tend
    > to be the small frequently-called ones used for nodes in dynamic graph
    > objects, or small resizeable buffers to hold strings and the like.
    > This is where you get the performance hit with repeated calls to
    > malloc() and free().
    >
    > So generally it's not worthwhile writing a stack allocator for a
    > normal program. That's not to say there aren't a few individual cases
    > where it can help performance. (See the chapter "Memory games" in my
    > book Basic Agorithms for details about memory allocation strategies).


    Even if it's a troll, it was droll.

    In a language that of necessity has a runtime stack or something that
    works like a stack (eg., a stack) one finds that the need for explicit
    stacks is lessened. For example, in my compiler for [start shameless
    plug] "Build Your Own .Net Language and Compiler [end shameless plug]
    I did not need to use an explicit stack to do recursive descent.

    Instead, I simply called finer grained procedures, passing the
    compiler state as a parameter, allowing the runtime stack to manage
    the return.

    To build an explicit stack in this program would have been folly, for
    it would have been necessary to either preallocate the stack and thus
    legislate the maximum complexity of source code, or use a lot of
    memory management in the pre-existing runtime heap.

    You didn't tell us you published a book. Can you identify the
    publisher?
     
    spinoza1111, Aug 16, 2010
    #9
  10. Standish P

    jacko Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    > is it possible to convert any and all algorithms to stack based ones and thus avoid memory leaks?

    No, not really. If you keep the allocated things and free them in
    reverse order on exit, then well yes, but practically, early free()
    frees memory for reuse on low memory systems. In this sense not
    'reversed' out of order free is essential in some contexts.

    The question then becomes what is the best heap fragmentation/
    compaction strategy and what is the best allocation algorithm to
    allocate addresses?
     
    jacko, Aug 16, 2010
    #10
  11. Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 3:14 pm, spinoza1111 <> wrote:
    >
    > To build an explicit stack in this program would have been folly, for
    > it would have been necessary to either preallocate the stack and thus
    > legislate the maximum complexity of source code, or use a lot of
    > memory management in the pre-existing runtime heap.
    >

    The problem is that if you reallocate the stack, you invalidate all
    pointers to objects on it. So you have to use handles instead. At
    which point you might as well admit that you are no longer programming
    in C.
    >
    >
    > You didn't tell us you published a book. Can you identify the
    > publisher?- Hide quoted text -
    >

    It's a print on demand, by Lulu. O'Reilley said they liked it but they
    couldn't sell books on C. (I've an open invitation to write a computer
    book for them in another language).

    I don't really recommend print on demand. The nice thing is that you
    can sell the book for about half the price it would cost under a
    traditional publishing model. The problem is that people still use
    acceptance by a traditional publisher as a filter.
     
    Malcolm McLean, Aug 16, 2010
    #11
  12. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 12:38 am, "Alf P. Steinbach /Usenet" <alf.p.steinbach
    > wrote:
    > * Standish P, on 16.08.2010 09:20:
    >
    > > [garble garble]

    >
    > Nonsense article "We look for an exogenous stack" cross-posted to
    >
    >    [comp.lang.c],
    >    [comp.lang.c++],
    >    [comp.theory],
    >    [comp.lang.python],
    >    [comp.lang.forth].
    >
    > Please refrain from following up on Standish' article.


    I am sorry that I did not post one of those porn baiting spams
    featuring YOUR MOTHER NUDE that you so like for others to see - AND -
    that you never complain about. Go and continue with your work and dont
    mess in my threads.

    Cheers,
    Standish

    >
    > Cheers,
    >
    > - Alf
    >
    > --
    > blog at <url:http://alfps.wordpress.com>
     
    Standish P, Aug 16, 2010
    #12
  13. Re: [Q] How far can stack [LIFO] solve do automatic garbage collection and prevent memory leak ?

    In message
    <>, Standish
    P wrote:

    > We envisage an exogenous stack which has malloc() associated
    > with a push and free() associated with a pop.


    Since when are malloc(3) and free(3) exogenous?
     
    Lawrence D'Oliveiro, Aug 17, 2010
    #13
  14. Re: [Q] How far can stack [LIFO] solve do automatic garbage collection and prevent memory leak ?

    Standish P <> writes:

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


    See


    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5498

    http://portal.acm.org/citation.cfm?doid=174675.177855

    http://www.springerlink.com/content/m2074884n6gt612h/

    Torben
     
    Torben Ægidius Mogensen, Aug 17, 2010
    #14
  15. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 4:20 am, Malcolm McLean <>
    wrote:
    > On Aug 16, 10:20 am, Standish P <> wrote:> [Q] How far can stack [LIFO] solve do automatic garbage collection and
    > > prevent memory leak ?

    >
    > Most programs can be written so that most of their memory allocations
    > are matched by destructors at the same level.
    >
    > However the allocations that can't be written this way typically tend
    > to be the small frequently-called ones used for nodes in dynamic graph
    > objects, or small resizeable buffers to hold strings and the like.
    > This is where you get the performance hit with repeated calls to
    > malloc() and free().
    >
    > So generally it's not worthwhile writing a stack allocator for a
    > normal program. That's not to say there aren't a few individual cases
    > where it can help performance. (See the chapter "Memory games" in my
    > book Basic Agorithms for details about memory allocation strategies).


    all the page numbers in your books TOC have a little varying offset
    from actual, pictures are nice for kids ..
     
    Standish P, Aug 17, 2010
    #15
  16. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?


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


    Is this all that a heap is or is there more to it ? I have been
    looking for simple but complete explanation of heap for a while and
    not gotten to it. I think I am looking for a stack allocation on the
    same pattern. In a disk, a file is fragmented in many contiguous
    blocks and is accessed automatically.

    > 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


    This you might want to take this to the Forth people because they are
    marketing their language as a cure for all that plagues programming
    today.

    > 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!- Hide quoted text -
    >
    > - Show quoted text -
     
    Standish P, Aug 17, 2010
    #16
  17. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 16, 11:09 am, Elizabeth D Rather <> wrote:
    > On 8/15/10 10:33 PM, Standish P wrote:


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

    >
    > Forth uses two stacks.  The "data stack" is used for passing parameters
    > between subroutines ("words") and is completely under the control of the
    > programmer.  Words expect parameters on this stack; they remove them,
    > and leave only explicit results.  The "return stack" is used primarily
    > for return addresses when words are called, although it is also
    > available for auxiliary uses under guidelines which respect the primary
    > use for return addresses.
    >
    > Although implementations vary, in most Forths stacks grow from a fixed
    > point (one for each stack) into otherwise-unused memory.  The space
    > involved is allocated when the program is launched, and is not managed
    > as a heap and allocated or deallocated by any complicated mechanism.  On
    > multitasking Forth systems, each task has its own stacks.  Where
    > floating point is implemented (Forth's native arithmetic is
    > integer-based), there is usually a separate stack for floats, to take
    > advantage of hardware FP stacks.
    >
    > >>     - 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.

    >
    > Forth uses its data stack for parameter passing and storage of temporary
    > values.  It is also possible to define variables, strings, and arrays in
    > memory, in which case their addresses may be passed on the data stack.
    >
    > Forth is architecturally very simple.  Memory allocations for variables,
    > etc., are normally static, although some implementations include
    > facilities for heaps as needed by applications.


    > although some implementations include facilities for heaps as needed by applications.


    How are these heaps being implemented ? Is there some illustrative
    code or a book showing how to implement these heaps in C for example ?

    Are dictionaries of forth and postscript themselves stacks if we
    consider them as nested two column tables which lisp's lists are in
    essence, but only single row. Multiple rows would just be multiple
    instances of it at the same level inside parens.

    we can peek into stacks which is like car. if it is not unusually
    costly computation, why not allow it ? there is no need to restrict to
    push and pop.

    roll( stack_name, num)

    itself can give all those postfix permutations that push and pop cant
    generate with a single stack. Can we use dictionaries to generate
    multiple stacks inside one global stack ?
     
    Standish P, Aug 17, 2010
    #17
  18. Standish P

    James Kanze Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 17, 6:21 pm, Standish P <> wrote:
    > > 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)


    > Is this all that a heap is or is there more to it ?


    There are many different ways to implement a heap. The above is
    not a good one, and I doubt that it's really used anywhere.

    > I have been looking for simple but complete explanation of
    > heap for a while and not gotten to it.


    Complete in what sense? The basic principle of how to use it is
    simple. As for how to implement it, there are many different
    algorithms that can be used.

    > I think I am looking for a stack allocation on the same
    > pattern.


    Stack allocation is far, far simpler (usually).

    > In a disk, a file is fragmented in many contiguous blocks and
    > is accessed automatically.


    At the system level, the same thing holds for memory, and the
    actual physical memory is "fragmented" into contiguous blocks,
    each the size of a page. The MMU (hardware) makes this
    transparent to user programs, however.

    > > There is no way you could do memory management of all but the most
    > > trivial and fixed-length data chunks using a stack.


    The length isn't the issue. The order of allocation and freeing
    is. (For many specific uses, stack based allocators can and
    have been used, but they don't work for generally allocation.)

    --
    James Kanze
     
    James Kanze, Aug 17, 2010
    #18
  19. Standish P

    Standish P Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 17, 1:17 am, (Torben Ægidius Mogensen) wrote:
    > Standish P <> writes:
    > > [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.

    >
    > See


    How many programmers have applied the ideas of these papers in their
    programming practice ? I paste the abstract for convenience

    > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5498


    Abstract:
    This paper describes a memory management discipline for programs that
    perform dynamic memory allocation and de-allocation. At runtime, all
    values are put into regions. The store consists of a stack of regions.
    All points of region allocation and deallocation are inferred
    automatically, using a type and effect based program analysis. The
    scheme does not assume the presence of a garbage collector. The scheme
    was first presented by Tofte and Talpin (1994); subsequently, it has
    been tested in The ML Kit with Regions, a region-based, garbage-
    collection free implementation of the Standard ML Core language, which
    includes recursive datatypes, higher-order functions and updatable
    references (Birkedal et al. 96, Elsman and Hallenberg 95). This paper
    defines a region-based dynamic semantics for a skeletal programming
    language extracted from Standard ML. We present the inference system
    which specifies where regions can be allocated and de-allocated and a
    detailed proof that the system is sound wi...

    >
    > http://portal.acm.org/citation.cfm?doid=174675.177855


    ABSTRACT
    We present a translation scheme for the polymorphically typed call-by-
    value &lgr;-calculus. All runtime values, including function closures,
    are put into regions. The store consists of a stack of regions. Region
    inference and effect inference are used to infer where regions can be
    allocated and de-allocated. Recursive functions are handled using a
    limited form of polymorphic recursion. The translation is proved
    correct with respect to a store semantics, which models as a region-
    based run-time system. Experimental results suggest that regions tend
    to be small, that region allocation is frequent and that overall
    memory demands are usually modest, even without garbage collection.

    >
    > http://www.springerlink.com/content/m2074884n6gt612h/
    >


    Abstract
    We report on our experience with designing, implementing, proving
    correct, and evaluating a region-based memory management system.
    dynamic storage management - regions - Standard ML



    >         Torben
     
    Standish P, Aug 17, 2010
    #19
  20. Standish P

    Brad Guest

    Re: How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

    On Aug 17, 10:34 am, Standish P <> wrote:
    > On Aug 16, 11:09 am, Elizabeth D Rather <> wrote:
    >
    > How are these heaps being implemented ? Is there some illustrative
    > code or a book showing how to implement these heaps in C for example ?
    >

    Forth does not use a heap, except maybe to implement malloc/free which
    many Forth apps do not use. The dictionary is a linked list structure.
    Now seems like a good time for you to teach yourself Forth (by
    studying the best commercial implementation you can find) since you
    seem to be working with a clean slate. But I will say a few things
    about stacks in general.

    There are many ways to implement stacks. The simplest is to declare
    some space for the stack and then post-increment or pre-decrement a
    stack pointer depending on whether you're pushing or popping. Normally
    you make the memory for them big enough that they don't overflow.

    If you are concerned about stack overflow you can change the
    implementation. Add bounds checking, for example.

    Another trick is to use an 8-bit stack pointer. Then you will have a
    circular stack. If there is underflow or overflow it at least will not
    step on other data. It will only return bad data, which you may find
    preferable to an ugly crash. OTOH, bugs that cause spectacular
    failures tend to be discovered. You can also initialize the stack
    memory with a pattern like 0xDEAD and then after sufficiently
    exercising the code, examine the memory contents to see the "high
    water mark" of the stack pointer.

    -Brad
     
    Brad, Aug 17, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Oleg
    Replies:
    5
    Views:
    2,467
    Ray Andraka
    Feb 18, 2004
  2. Andy Dingley
    Replies:
    45
    Views:
    1,654
    Andy Mabbett
    Jun 11, 2006
  3. RC
    Replies:
    2
    Views:
    445
    Chase Preuninger
    Jan 8, 2008
  4. Standish P
    Replies:
    52
    Views:
    1,234
    Nick Keighley
    Aug 25, 2010
  5. Standish P
    Replies:
    87
    Views:
    1,648
Loading...

Share This Page