Could we use multiple stacks?

[Francois-Rene Rideau]

First of all, thanks to cooperative multitasking,
we can require the threads to do all the cleanup job needed,
so all of our various stack management tricks can be tried out
on the same system.

Remember:
* interrupt-driven threads have their own stack/heaps anyway,
* usual code is required to checkpoint regularly to allow real-time
 cooperative threading
* checkpointing is costly only if a "switch thread on next checkpoint"
 flag is set.
* so that tight loops can be optimized that don't suffer from checkpointing
 overhead, either
 = the loop can be unrolled several time, to minimize job vs overhead ratio,
 = the loop can be cut into pieces of given length, with checkpoints
  in between, so that each piece fits checkpointing requirements, or
 = a "recovery" routine other than "let me run until next checkpoint"
  can be declared to the semi-preemptive scheduler,
  so that the program can reach a safe state from anywhere in the tight loop.


So, what we must implement NOW:
* a page allocator so that programs (GC managers & other critical threads)
 can manually allocate and deallocate arbitrarily typed and sized
 stacks and heaps
* a mostly FORTH stack machine
* the simplest possible copying GC for generic objects of size n
 that begin with m GC-able values (possible pointers).
* scoping/dictionary management using the GC'ed heap.
* a simple cooperative scheduler
* a simple keyboard handler
* I/O words to have text windows in text mode as arrays
* words to cache the displaying of a text windows
* console management for a text window

Note: it's still time to add floating point management later.


Now replying to both Eric and Sean...
>>>:Fare
>>:Eric
>:spc


[Garbage collecting the Dictionary/Heap]
>   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).
>
Garbage collection is just NEEDED in a dynamical system
(like for instance a distributed multi-user multi-tasking
interactive development system).
You can't escape it because there's NO WAY to manually or statically
determining when an arbitrary word will no longer be used.
Surely on a non-interactive, non-development single-threaded embedded system,
GC can be done manually and statically.
This is just not the general case, that TUNES claims to handle.
I'd be happy the TUNES GC can be stripped down by the compiler
when producing standalone code that does not need it;
but the "main" reflexive development system just HAS TO implement it.


>> 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.
That's indeed the conclusion we arrived at in the previous messages.

>   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.
>
You're wrong **in the general case**, that TUNES must implement:
you must save not only the stack pointer, but the whole stack.
   If you have coarse-grained threads, then you can reserve a big-enough
stack for each of them, and all you need is save the pointer.
   But if you allow fine-grained threads, and/or continuations that can be
entered several times, not just once, then saving a stack pointer just
won't work.


>   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)?
>
The problem is that the stack may contain roots for GC'ed objects.
Surely you should read about the implementation of LISP/Scheme/ML systems...


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


>   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.
>
Again, we're talking about worst case, which a full-fledged version of the
OS must handle. Then, GC is not only to defrag memory;
some GC do not defrag memory at all, and live long; the main role
of the GC is to dynamically reclaim garbage that cannot be freed
from statically determined information.


>   The problem comes when you try to be all things to all people by allowing
> no limits whatsoever, so you get code that does:
> 
> 		while(morestuff)
> 		{
> 		  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.
   I can't see why this would be any problem.
Surely, higher-level constructs should be used,
that do it accurately without your bothering.


>   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 ... ).
I don't see how that no-limit can limit you,
unless you make code bloat part of it, which is unfair,
because removing the limit doesn't cause much bloat per se,
while managing the limits does cause a lot of it.
   Allowing limits, perhaps giving default limits in some cases,
is a good thing. Imposing limits is definitely a NO-NO.


>> 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).
>
Yes, Forth is technically more user-extensible than LISP.
However, the lack of abstraction (lambda expressions) in Forth
is a great weakness, that make extending it in a *modular* way impossible:
lack of scoping, lack of GC, and if ever you implement them,
lack of conventions that would make possible
the exchange of module among users, and hence modules useful.
   I guess our FORTH+Modules+GC could be a serious rival to LISP/Scheme
in many applications, and maybe that's a good reason for FORTH-lovers
to provide a mostly ANS compliant version of the Tunes LLL,
so as to contribute to the expansion of FORTH.
ANS FORTH without GC and modules sure isn't a rival to anything
outside from embedded systems.

--    ,                                         ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
                 TUNES is a Useful, Not Expedient System
WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"