Could we use multiple stacks?
Sean 'Captain Napalm' Conner
Thu, 16 May 1996 23:45:59 -0400 (EDT)
On some network somewhere in cyberspace, Eric W. Biederman transmitted:
> About Stacks Building up from the Forth Model
> (And my ideas Fare seems to have been confused,
> and I know I have change my position since I
> first posted. )
> ANS forth has 4 stacks
> The Return Stack
> The Data Stack
> The Floating Point Stack
> The Dictionary Data Stack ( you use allot to allocate or deallocate from it )
Actually, ANS Forth has the following stacks:
Floating Point Stack
The Control/Floating point stack CAN be separate from the Data Stack, but
an implementation doesn't have to have separate stacks for these. The
Dictionary Data Stack isn't really a stack (per say). You use ALLOT to
allocate space, but that's it if all you are using is the CORE word set. If
you use the CORE EXTENSION, you have MARKER which allows you to define a
word such that execution of said word will deallocate everything created
since MARKER was last used. FORGET is in the TOOLS EXTENSION word set (and
I'm not including anything from the MEMORY word set).
> I suggest we add a
> Root Pointer Stack
> The argument for having a floating point stack is that there is a
> whole class of programs that do intensive floating point operations.
> Windowing systems and GUI's seem to be in among those. Additionally
> floating point registers are a very real part of practically all
> machine architecures, and it is simpler to generate good floating
> point code if you don't commonly put your numbers on the data stack,
> as that looses a lot of type information.
I think this has to do with two things:
The Intel 80x87 (which is stack based)
Stack manipulation noise words
in that order.
> With regards to Forths Dictionary Data Stack we will probably replace
> that with a garbage collected heap, but how it could be implemented in
> an ANS compatibility layer is an interesting question. It is my
> intention for the moment to see how close to ANS forth we can be and
> still have a garbage collector.
But traditionally, garbage collection has been explicit with FORGET and/or
MARKER and not with any automagical system to determine which words are no
longer used. Not all Forth systems allowed nameless words ( :NONAME is a
CORE EXTENSION word and it's value is pretty limited (as you have to keep
track of the generated xt anyway).
> The seperation of the return and data stacks actually is a plus in
> several ways, the big one is that you aren't always tripping over you
> return addresses when you want to use the stack. That and there is a
> great deal more symmetry between word arguments and return values.
It probably had more to do with ease of implemenation than anything. It
gets pretty messy trying to write code to remove parameters if you have to
work around a return address (as well as return values).
> First abandon the idea as the function frame as the basic unit used
> for continuations. Instead introduce the idea of stack continuations.
> A stack continuations is a saved place upon a stack subject to all of
> the usual restrictions of continuations, but instead implemented for
> that stack. A normal scheme continuation would be the collection of
> the continuations of all the stacks a function uses. A stack frame is
> then generated whenever a continuation is generated.
Correct me if I'm wrong, but all a continuation is is state information
such that you can restart the CPU with a saved state. In a stack based
system, the only state you have is the stack pointers, so the fewer stacks
you have, the less state you have to save/restore.
> Also, the return stack, if separated from the heap scratchpad,
> and unless specifically allocated for the current thread,
> could be limited to a fixed number of pages:
> any kind of deep recursion should be done accross real-time checkpoints,
> and hence must regularly allow GC.
> Copying stack (the usual method for having light-weight continuations)
> is too expensive for such deep recursion,
> and heap-based recursion will be much cheaper
> (remember: using the GC'ed heap is cheap),
> while specifically reserving non-shared space for the stack
> would be a good idea if the stack is going to be very deep.
But stacks do their own GC. Values are pushed onto it for use, and when
no longer needed, popped off. What's the problem (besides keeping track of
dynamically allocated globs of memory)?
> > I strongly suspece that Garbage collection is not the right solution
> > for every memory management task.
> Indeed, GC is NOT the right solution for EVERY mm task,
> and there should be ways for the LLL to work without it.
> *Static* memory management (again, done by the compiler
> with more or less human help) is often a good/necessary solution
> to many problems, *when possible*.
> (particularly when there's hard real-time/real-space requirement).
> Actually, real-time requirements can be met better with a garbage
> collector then with user memory management (unless it has a trivially
> simple usage pattern.) The reason is a real time collector is
> completely bounded in the time it takes. While normal memory
> management along with generic reference counting is susceptible to
> recursiv freeing.
The best case is when you know EXACTLY how much memory you need to use.
Then there is no problem with fragmentation (which is why you use GC in the
first place, to defrag memory). I can restrict myself to using only X
amount of memory (say, 128k, 1M, whatever) and splitting it up as I see fit.
The problem comes when you try to be all things to all people by allowing
no limits whatsoever, so you get code that does:
somep = realloc(newsize,somep);
/* manipulate somep */
Where realloc() (or equivilent) will allocate memory, free memory,
increase a block, reduce a block and otherwise fragment memory till there's
nothing left but to either compact it or restart.
Imposing limits is somethings a GOOD thing to do. Some of us don't like
GNU because of their not limits to anything anytime philosophy (and their
code tends to be bloated anyway ... ).
> A small note:
> Forth is technically more extensible then LISP.
> There is a reason you never heard of a Forth macro.
Nor have you ever heard of lambda functions in Forth either, and
manipulating code is system dependant (unlike LISP, where one CAN manipulate
code, since it's just a list).
-spc (I like Forth, but I don't ... )