Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > [Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

Reply
Thread Tools

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

 
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 16, 12:20*am, Standish P <(E-Mail Removed)> 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 <(E-Mail Removed)>


Another way to pose my question, as occurred to me presently is to ask
if a stack is a good abstraction for programming ? Certainly, it is
the main abstraction in Forth and Postscript and implementable readily
in C,C++ and I assume python.

It is true that the other languages such as F/PS also have borrowed
lists from lisp in the name of nested-dictionaries and mathematica
calls them nested-tables as its fundamental data structure.

I am asking for a characterization of algorithms that benefit from
this abstraction or programming paradigm and comparison with others.

The whole case of OOP is the clustering of thought, ie book-keeping,
in the mind of the programmer around fewer objects than ten or twenty
fold functions.

so the name of the game is the same, ie to help the programmer keep
track of things for writing fault free code without chasing every
case, easy visualization, easy recall and communication with fellow
programmers of abstract concepts in terms of real world objects and
easy modification and code reuse.
 
Reply With Quote
 
 
 
 
John Kelly
Guest
Posts: n/a
 
      08-17-2010
On Tue, 17 Aug 2010 11:53:27 -0700 (PDT), Standish P <(E-Mail Removed)>
wrote:

>Another way to pose my question, as occurred to me presently is to ask
>if a stack is a good abstraction for programming ? Certainly, it is
>the main abstraction in Forth and Postscript and implementable readily
>in C,C++ and I assume python.


>so the name of the game is the same, ie to help the programmer keep
>track of things for writing fault free code without chasing every
>case, easy visualization, easy recall and communication with fellow
>programmers of abstract concepts in terms of real world objects and
>easy modification and code reuse.



"Go is an attempt to combine the ease of programming of an interpreted,
dynamically typed language with the efficiency and safety of a
statically typed, compiled language. It also aims to be modern, with
support for networked and multicore computing"

"To make the stacks small, Go's run-time uses segmented stacks. A newly
minted goroutine is given a few kilobytes, which is almost always
enough. When it isn't, the run-time allocates (and frees) extension
segments automatically"

http://golang.org/doc/go_lang_faq.html



--
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php

 
Reply With Quote
 
 
 
 
John Passaniti
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 2:53*pm, Standish P <(E-Mail Removed)> wrote:
> Another way to pose my question, as occurred to me presently is
> to ask if a stack is a good abstraction for programming ?
> Certainly, it is the main abstraction in Forth and Postscript
> and implementable readily in C,C++ and I assume python.


A stack is a fine abstraction for some kinds of programming. It fails
for others. In languages where functions are first-class entities
that can be stored and passed around like any other kind of data,
stacks can be problematic because a function can out-live the stack
frame they were created in.

> It is true that the other languages such as F/PS also have borrowed
> lists from lisp in the name of nested-dictionaries and mathematica
> calls them nested-tables as its fundamental data structure.


No.

> The whole case of OOP is the clustering of thought, ie book-keeping,
> in the mind of the programmer around fewer objects than ten or twenty
> fold functions.


That's one view of OOP. It's not the only one.

> so the name of the game is the same, ie to help the programmer keep
> track of things for writing fault free code without chasing every
> case, easy visualization, easy recall and communication with fellow
> programmers of abstract concepts in terms of real world objects and
> easy modification and code reuse.


You, like probably everyone else who has thought about how to
"simplify" languages will eventually end up at the same place-- you'll
have a model that meets your objectives, but with some programmers
will find is unnecessarily limiting. More importantly, you'll run
into some classes of problems for which your simple model makes things
inordinately complicated relative to what other languages and
paradigms offer.

Here's a better idea: Become familiar with the languages you've
cited, and more. I would recommend Forth, Lisp, Smalltalk or Ruby,
Lua or JavaScript. Learn each and then come back and tell us if you
think limiting the programmer to objects with stack-ordered lifetimes
is enough. Oh, and while you're at it, dip your toes into a problem
domain you don't normally do any work in. If you're an embedded
systems guy, then spend some time writing a non-trivial web
application. Go outside your comfort zone and find a problem domain
where cherished idioms and tools no longer apply. I think it will
open your eyes.
 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 12:32*pm, John Passaniti <(E-Mail Removed)> wrote:
> On Aug 17, 2:53*pm, Standish P <(E-Mail Removed)> wrote:
>
> > Another way to pose my question, as occurred to me presently is
> > to ask if a stack is a good abstraction for programming ?
> > Certainly, it is the main abstraction in Forth and Postscript
> > and implementable readily in C,C++ and I assume python.

>
> A stack is a fine abstraction for some kinds of programming. *It fails
> for others. *In languages where functions are first-class entities
> that can be stored and passed around like any other kind of data,
> stacks can be problematic because a function can out-live the stack
> frame they were created in.
>
> > It is true that the other languages such as F/PS also have borrowed
> > lists from lisp in the name of nested-dictionaries and mathematica
> > calls them nested-tables as its fundamental data structure.

>
> No.


you are contradicting an earlier poster from forth who admitted the
part on dicts.

>
> > The whole case of OOP is the clustering of thought, ie book-keeping,
> > in the mind of the programmer around fewer objects than ten or twenty
> > fold functions.

>
> That's one view of OOP. *It's not the only one.


and what can you add to enlighten the readers on the other view ?

>
> > so the name of the game is the same, ie to help the programmer keep
> > track of things for writing fault free code without chasing every
> > case, easy visualization, easy recall and communication with fellow
> > programmers of abstract concepts in terms of real world objects and
> > easy modification and code reuse.

>
> You, like probably everyone else who has thought about how to
> "simplify" languages will eventually end up at the same place-- you'll
> have a model that meets your objectives, but with some programmers
> will find is unnecessarily limiting. *More importantly, you'll run
> into some classes of problems for which your simple model makes things
> inordinately complicated relative to what other languages and
> paradigms offer.


The objective is to discuss those cases via specific examples (not
generalities), and talk ABOUT them, not AROUND them.

> Here's a better idea: *


Its a very fine wild goose chase project statement.

> Become familiar with the languages you've
> cited, and more. *I would recommend Forth, Lisp, Smalltalk or Ruby,
> Lua or JavaScript. *Learn each and then come back and tell us if you
> think limiting the programmer to objects with stack-ordered lifetimes
> is enough. *Oh, and while you're at it, dip your toes into a problem
> domain you don't normally do any work in. *If you're an embedded
> systems guy, then spend some time writing a non-trivial web
> application. *Go outside your comfort zone and find a problem domain
> where cherished idioms and tools no longer apply. *I think it will
> open your eyes.


 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 1:19*pm, Standish P <(E-Mail Removed)> wrote:
> On Aug 17, 12:32*pm, John Passaniti <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Aug 17, 2:53*pm, Standish P <(E-Mail Removed)> wrote:

>
> > > Another way to pose my question, as occurred to me presently is
> > > to ask if a stack is a good abstraction for programming ?
> > > Certainly, it is the main abstraction in Forth and Postscript
> > > and implementable readily in C,C++ and I assume python.

>
> > A stack is a fine abstraction for some kinds of programming. *It fails
> > for others. *In languages where functions are first-class entities
> > that can be stored and passed around like any other kind of data,
> > stacks can be problematic because a function can out-live the stack
> > frame they were created in.

>
> > > It is true that the other languages such as F/PS also have borrowed
> > > lists from lisp in the name of nested-dictionaries and mathematica
> > > calls them nested-tables as its fundamental data structure.

>
> > No.

>
> you are contradicting an earlier poster from forth who admitted the
> part on dicts.
>
>
>
> > > The whole case of OOP is the clustering of thought, ie book-keeping,
> > > in the mind of the programmer around fewer objects than ten or twenty
> > > fold functions.

>
> > That's one view of OOP. *It's not the only one.

>
> and what can you add to enlighten the readers on the other view ?
>
>
>
> > > so the name of the game is the same, ie to help the programmer keep
> > > track of things for writing fault free code without chasing every
> > > case, easy visualization, easy recall and communication with fellow
> > > programmers of abstract concepts in terms of real world objects and
> > > easy modification and code reuse.

>
> > You, like probably everyone else who has thought about how to
> > "simplify" languages will eventually end up at the same place-- you'll
> > have a model that meets your objectives, but with some programmers
> > will find is unnecessarily limiting. *More importantly, you'll run
> > into some classes of problems for which your simple model makes things
> > inordinately complicated relative to what other languages and
> > paradigms offer.

>
> The objective is to discuss those cases via specific examples (not
> generalities), and talk ABOUT them, not AROUND them.
>
> > Here's a better idea: *

>
> Its a very fine wild goose chase project statement.
>
>
>
> > Become familiar with the languages you've
> > cited, and more. *I would recommend Forth, Lisp, Smalltalk or Ruby,
> > Lua or JavaScript. *Learn each and then come back and tell us if you
> > think limiting the programmer to objects with stack-ordered lifetimes
> > is enough. *Oh, and while you're at it, dip your toes into a problem
> > domain you don't normally do any work in. *If you're an embedded
> > systems guy, then spend some time writing a non-trivial web
> > application. *Go outside your comfort zone and find a problem domain
> > where cherished idioms and tools no longer apply. *I think it will
> > open your eyes


program a universe simulator using a turing machine.

 
Reply With Quote
 
John Passaniti
Guest
Posts: n/a
 
      08-18-2010
On Aug 17, 4:19*pm, Standish P <(E-Mail Removed)> wrote:
> > > It is true that the other languages such as F/PS also have borrowed
> > > lists from lisp in the name of nested-dictionaries and mathematica
> > > calls them nested-tables as its fundamental data structure.

>
> > No.

>
> you are contradicting an earlier poster from forth who admitted the
> part on dicts.


Then they are wrong.

You asked if Forth "borrowed" lists from Lisp. It did not. In Lisp,
lists are constructed with pair of pointers called a "cons cell".
That is the most primitive component that makes up a list. Forth has
no such thing; in Forth, the dictionary (which is traditionally, but
not necessarily a list) is a data structure that links to the previous
word with a pointer. This is in fact one of the nice things about
Lisp; because all lists are created out of the same primitive cons
cell, you can consistently process any list in the system. In Forth,
any lists (such as the dictionary, if it is a list) are specific to
their purpose and have to be treated individually.

I don't know what you mean by "nested-dictionaries." There is no such
thing in Forth. Dictionaries don't nest. You can create wordlists,
but each wordlist is flat. When most people think of a nested
dictionary, they would think of a structure that would allow any
arbitrary level of nesting, not a string of flat wordlists.

> > > The whole case of OOP is the clustering of thought, ie book-keeping,
> > > in the mind of the programmer around fewer objects than ten or twenty
> > > fold functions.

>
> > That's one view of OOP. *It's not the only one.

>
> and what can you add to enlighten the readers on the other view ?


How one views OOP depends on the language and implementation. Your
statement about having fewer than "ten or twenty fold" functions is
completely arbitrary and is more a matter of style and skill in
decomposition than an intrinsic quality about objects. The poetic
"clustering of thought" is vague but a I guess could be an informal
notion of the bundling of related state and methods. And referring to
it as "book-keeping" suggests some kind of static relationship between
state and methods, although that is not the case in architectures that
stress dynamic relationships. Many people only know OOP through
static, class-based models (such as in languages like C++). But there
are other models. Objects can also be represented not with classes
but by cloning existing objects and then mutating them as needed.
Objects can also be represented with a functional interface using a
closure around an environment. In such cases, objects may be far more
fluid than in static class-based models, and shift over time into
different roles. In such systems, "book-keeping" isn't static. Or
put another way, the language and implementation drive the flavor that
a particular object has.

> > You, like probably everyone else who has thought about how to
> > "simplify" languages will eventually end up at the same place-- you'll
> > have a model that meets your objectives, but with some programmers
> > will find is unnecessarily limiting. *More importantly, you'll run
> > into some classes of problems for which your simple model makes things
> > inordinately complicated relative to what other languages and
> > paradigms offer.

>
> The objective is to discuss those cases via specific examples (not
> generalities), and talk ABOUT them, not AROUND them.


I'd be happy to discuss specific examples, but your understanding of
Forth is flawed, and until you learn more about Forth, I don't think
it would be helpful.

And actually, I did provide a specific example. You apparently didn't
understand it, so let me be more explicit. Here is a function in
Scheme:

(define (hello name)
(lambda ()
(begin
(display "Hello ")
(display name))))

This defines a function that returns another function. You can think
of this as a constructor for a light-weight object that has one value
("name") and one default method (to print "Hello <name>"). The
function that is returned can be stored, passed around, and otherwise
out-live the invocation of this function. For example:

(define example (hello "John"))

In your stack mindset, the value "John" would disappear after the call
to "hello". But in Scheme, the value lives on, as it is part of the
closure captured at the time the function was created.

A stack mindset would not allow this. And this would eliminate the
vast majority of functional programming from your language's
abilities. Maybe you don't care, or maybe you still don't see the
value in this. In that case, I suggest you learn the language and
then think about what your stack mindset prevents.

> > Here's a better idea: *

>
> Its a very fine wild goose chase project statement.


No, it is a vivid example of what you don't know-- and what you don't
know is what will limit you later.
 
Reply With Quote
 
Dennis Lee Bieber
Guest
Posts: n/a
 
      08-18-2010
On Tue, 17 Aug 2010 10:44:27 -0700 (PDT), James Kanze
<(E-Mail Removed)> declaimed the following in
gmane.comp.python.general:

> On Aug 17, 6:21 pm, Standish P <(E-Mail Removed)> 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.
>

In particular, maintaining a "used list"... The address of a "used"
block is in the possession of the application itself and separate from
the memory management... When the application frees it, then it gets
added to the free list... adjacent freed blocks get merged into larger
ones, etc.

Then there is the old Macintosh "handle" which is the address of...
another address. Handles being allocated from a fixed block of memory
containing addresses of variable blocks elsewhere in memory. The memory
manager thereby being free to move the data around (compacting free
space) associated with updating the address stored in the handle itself.
Application code never has to know the actual location of the data.



When one gets down to the roots, everything is just an array of same
sized items (8, 16, 32, 64, 36, 60 bits depending on era and hardware)
accessed by an index starting at 0. All else is structure added on top
of that.

--
Wulfraed Dennis Lee Bieber AF6VN
http://www.velocityreviews.com/forums/(E-Mail Removed) HTTP://wlfraed.home.netcom.com/

 
Reply With Quote
 
John Nagle
Guest
Posts: n/a
 
      08-18-2010
On 8/17/2010 11:20 AM, Standish P wrote:
> On Aug 17, 1:17 am, (E-Mail Removed) (Torben Ęgidius Mogensen) wrote:
>> Standish P<(E-Mail Removed)> 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...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.


That's actually an interesting idea. If you can figure out object
lifetimes at compile time, allocation can be made far more efficient.

One of the basic questions is whether a function will ever "keep"
an object. That is, will the function ever keep a reference to an
object that outlives the return from the function? In many cases,
one can easily determine at compile time that a function will never
keep a passed object. In such a case, you don't have to do reference
count updates on the object. Most math functions have this property,
even vector and matrix math functions - they have no persistent state.

Python could use a bit of this. If a function argument can
be identified as "non-kept", then the function doesn't need to
do reference count updates on it. If a local variable in
a function is used only by "non-keep" functions and operations,
it can be created on the stack and released cheaply at block exit.

One can go much further in lifetime inference than this, as
the papers demonstrate. There's a big win in the simple optimization
of identifying "non-keep" parameters, especially in mathematical work
where they're very common. It's not clear that getting fancier than
that is a win.

Does Shed Skin have this optimization? It should.

John Nagle
 
Reply With Quote
 
Torben Ęgidius Mogensen
Guest
Posts: n/a
 
      08-18-2010
Standish P <(E-Mail Removed)> writes:

> On Aug 17, 1:17*am, (E-Mail Removed) (Torben Ęgidius Mogensen) wrote:
>> Standish P <(E-Mail Removed)> writes:
>> > [Q] How far can stack [LIFO] solve do automatic garbage collection and
>> > prevent memory leak ?

>>
>> See

>
>> http://citeseerx.ist.psu.edu/viewdoc...10.1.1.23.5498


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


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


>> * * * * Torben


> How many programmers have applied the ideas of these papers in their
> programming practice ?


The method was built into a SML compiler which was used (among other
things) to build a web server, which was used (among other things) to
make the web pages and course administrative system at the IT University
of Copenhagen, Denmark.

Good enough for you?

Torben
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      08-18-2010
On 17 Aug, 18:34, Standish P <(E-Mail Removed)> wrote:
> On Aug 16, 11:09*am, Elizabeth D Rather <(E-Mail Removed)> 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 ?


any book of algorithms I'd have thought

http://en.wikipedia.org/wiki/Dynamic_memory_allocation
http://www.flounder.com/inside_storage_allocation.htm

I've no idea how good either of these is

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


I can't make much sense of that. But you seem to see Lisp data
structures in all sorts of strange places. I don't see that Lisp lists
are "nested two column tables"

> we can peek into stacks which is like car.


no.


> if it is not unusually
> costly computation, why not allow it ? there is no need to restrict to
> push and pop.


some stacks have a top() operation.


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


I've no idea what you on about


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C++ 87 08-26-2010 08:44 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C Programming 52 08-25-2010 02:43 PM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
OT: Problem no one can solve so far peace to all A+ Certification 11 07-05-2003 03:00 PM



Advertisments