types and operators

[Francois-Rene Rideau]

Let's sum up things from my last post:

   We agree that the GC should primarily know about
* one kind of pointer, perhaps used to encode small integers, too.
* two kind of memory blocks, those made of pointers,
 and those made of raw data, the each block having a known size.

We can add a lot of refinements later, but these are the most important.
Strings, buffers, long integers, whatever, will be raw data to the GC.
   This may mean that mixing pointers and raw data require an additional
indirection, unless we have mixed blocks, but then, it means additional
GC code (not too important, but superfluous as for an initial release),
and an additional size tag (much more inconvenient) for these blocks;
we could have several kinds of blocks, too.

   I think we agree on these points. Where there are choices left,
our rule has always been "implementor chooses". So if you want your
choice against someone else, you'd better implement it first :)


Now, here is my reply to
>>:Eric
>:utsl

>> I have figured out how to do type-safe operators (compile-time
>> type-safe) and identification of all pointers at run-time with no run
>> time cost.  What it does require though is a restriction on how words
>> can manipulate the data stack.   That is words must have a fixed
>> number of arguments and a fixed number of results.
>
> This restriction is would get obnoxious in almost no time. We're talking
> about writing a very extensible language which can be expanded to handle
> doing a lot of things dynamically. In your design, I couldn't even write
> a function like printf! Not to mention breaking the separation between
> the data and return stack. I'd rather stay closer to Forth.

Let me agree with utsl: we're talking about a LLL here.
That the HLL severely restricts itself when using LLL primitives,
which it may well do, to begin with, is another question.
However, I agree that there should be a way to embed HLL type information
and various annotations in LLL code,
that LLL interpreters/compilers could discard,
but that would greatly help LLL<->HLL interface when present.

As for ROLL and PICK and such, they are most useful to the HLL,
unless you want to have one primitive for each n with which to <<n PICK>>,
and to require additional off-stack indirection whenever there are
variable-length arguments.


>> The reason I make the above restriction is as follows.  If words are
>> to use a single stack as C does they can be implemented as allocating
>> frames upon the stack.  The frame holding the funcions arguments, it's
>> return locate, the address of the last words frame, the local
>> variables, a buffer to receive results from functions, and most
>> important a tag that tells what everthing is in the frame.

What you may gain at doing that, is that the implicit tagging of
frames with the return address would automatically give the size
of the frame. It might be an interesting thing to try, but to me,
much too complicated to be worth implementing initially,
and I'm not sure it is worth the complication afterwards.
Could not even be used to GC C code, as it works for the arguments,
but not for the local variables.


> Well, in Forth, we don't use local variables, anyway.
ANS FORTH has at least two standard ways to do local variables,
and non-ANS FORTH's have many more. Surely they are not overused, though.

> The restriction
> that all types of arguments and return values would force us to emulate
> C++ templates when we want to create functions that accept and return
> variable types: create a function for each permutation that might be used.
> Sorry, but this design is much better suited to a traditional procedural
> language with multiple return values.
Ouch. I sure do not want that, neither for HLL nor for LLL.


>> As well as allowing garbage collection, and definite identification of
>> things, it will also allows, some of the trickier things with lambda
>> functions where they same their return stack.  I'm really not certain
>> what kind of discipline is required of functions that get returned
>> through multiple times to keep it all consistent. (We can cross that
>> bridge later).  Also this enables all kinds of traditional
>> optimsations that C can use, and possibly allows using a hacked
>> version of GCC as our code generator.
>
> Not really, C would not be very friendly about having multiple return
> values, especially since C on the x86 returns values in EAX. As for 
> hacking GCC for a code generator: you're out of your mind. Have you taken
> a close look at the source to GCC? It'd be better (and probably almost as
> fast :) to write the code generator in a combination of Awk, Sed, Perl and
> Icon, with a big shell script piping things all over the place....
> While you're at it, you might as well build a front end for ADA as well.
   Yeah. C might be most useful if we can use it "as is", in an OTOP
environment. But as we intend to do runtime code generation,
GCC is out of question. And as utsl says, GCC isn't something you can
extract a part from: by the time you manage to get something running,
you could have rewritten it twice.


>> Things only need to be orderly to present to the garbage collector
>> when a function calls allocates memory from the heap or calls some
>> function that might.  So in general at function call time.
>
> Maybe not even that often. We could probably get by with having the GC
> run only at programmed points, which would allow us to simply make sure
> that nothing significant is on the stack at those points. This is
> consistant with the cooperative multitasking model Fare has spoken of.
Yes. Any function that allocates a predictable amount of stack space
could have this amount preallocated by the calling function,
so that calling functions could be required to do so
(remember: we're talking about LLL stuff; most non-optimized HLL stuff
would indeed be completely framed to allow GC).
Anyway, if we require the stack to be made of proper GC-able objects,
framing is just a matter of "closing" the stack with its current length,
and can be done automatically by the allocation routine that detects the
need for a GC.


>> I have implemented a small test interpreter in C that makes most of
>> this work.  What it uses to make this work is it's own data stack (as
>> nothing else has one.)   All items placed upon this data stack are
>> tagged with their type.  This allows the interpreter to check and make
>> certain that the correct types are passed to a function.
Explicit type tagging is also a possibility we shouldn't exclude,
though I'm convinced it's too much overhead: what makes it useful
is frequent run-time type checking, whereas if we promote a strongly
typed language, most checking could be moved to compile-time,
and restricted to very few infrequent objects that make such
generalized type tagging inefficient.
Moreover, in a page-based allocation scheme,
the high bits of a pointer are enough to tell the type of the object
(at least the GC-type, not forcibly the full HLL-type),
so that many checks are still possible.


>> After the
>> sanity check the intrpreter gathers all of the arguments off of the
>> data stack, passes them to the word, then when the word returns
>> gathers the results back up (looks up their types) and pushes them
>> back upon the data stack.  A compiler should be able to avoid a lot of
>> this work, and generate really good code.
Yes, and then, expilcit type tagging is redundant.


>> I hope this is a framework you can live with, as better eludes me.
> I think I'd rather put up with type munging. :( :( :(
I think we *must* give types when there are,
but not reject code when there aint a simple one.
After all, that's the LLL,
and there will be more than enough types in HLL.
   Surely, if we can have both universally and existentially quantified types
that depend on integers, and accept cases,
all FORTH primitives can eventually be well-typed. But that's not a priority.
   Now for utsl, remember that any frame that might be GC'ed must be clearly
tagged to let the GC know things (notably size, etc). Because frames are
already tagged with their execution address (well, at least the frame that
pointed to them, and from which the GC reached them had such information),
it might be an "optimization" to derive size information from execution
address which this also means having a way to distinguish frames from
normal blocks; but then, there is no absolute requirement from the derived
size to depend *only* on the execution address; the derived size code could
very well pick size info from the frame. Again, this really seems
overly complicated. I'm all for having execution frames mostly standard
frames.
   Please also remember that this complication is not valid for
code between GC, whose results are transient, and that will not last
long enough for a safepoint to be required by our conventions.
Only calls to "PAUSE" should be specially
framed/framable, but then, this preclude growing the frame down afterwards,
unless we copy the frame to the end of heap before,
which can be all the more interesting for continuations etc.
[Remember that I'd like all non-interrupt-driven tasks to share the same
stack/heap/whatever space].

   As a side note, we still haven't decided how "return addresses"
would be encoded. Will we require block-aligned pointers, and have
"base+offset" encoding ? Will we allow "infix" code, and go through
the hassle of identifying the beginning of a block each time ?
The first may be the simplest to implement, and though it is inefficient
at run-time, we don't care for the initial implementation. Let's do it
and wrap it with enough macros so that the user doesn't see it.

   For a longer-term implementation, I propose the latter trick
(allow infix pointers), with some page-based hashing:
Objects on a same "page" will be required to be of same "GC-type",
so by doing simple stuff with the high-bits of a pointer
we can determine the action to take to see the beginning of a block
by checking a page directory.
The exact implementation should priviledge usual cases,
testing them first, and add levels of indirection for unusual cases.
   Objects of large size (several pages) would have their own entry.
Small objects would be grouped on pages where all objects have the same size.
Page boundaries would be respected as much as can be to avoid multi-page
entries. Objects of uncommon sizes would be found by following the
linked or binary list of objects on the page (linked might be better
if there are very few objects).
   Most source and/or destination regions could require exact pointers,
however, which would simplify things. Code for infix pointers would be
called only when we're not sure. This would greatly speed up GC.




> You see, I'd like
> to remain as close to Forth in design as is possible, but with the
> needed extentions. (As well as dumping some minor stupidity in the Forth 
> I/O words.) But I do want it be close enough that most ANS Forth would 
> run, provided it obeys the rules of ANS Forth.
Well, we should surely have ANS compatibility packages eventually,
but direct compatibility is not an issue.

> Your design, while neatly avoiding the problem of finding pointers,
> breaks an unacceptably large number of things. (A good solution, all the
> same, just more suited to building a C over Forth.)
I agree with utsl.


> In general, I'd like to stay away from stack frames.
Unhappily, they are just *required*, not everywhere, but at checkpoints.
Maybe the easiest implementation is to require all data on stack to be
of valid "pointer/integer" type at checkpoints, so that framing is only
knowing the stack length. But even if we do that,
I prefer we insert code to allow more constraining implementations,
if we want to try that later.

> I'd prefer to not have those at all, or let the hll use them if it wants.
Again, frames are only for safe-points.

> But not in the lll, or its calling convention.
Sure. Most primitives are called for transient data and should not frame.

> Those are just my preferences, though.
> We'll have to see what other people think.
My idea seems to satisfy everyone,
but still impose hard constraints on the LLL programmer.

BTW, what grain should we require for PAUSEs ?
We agreed that LLL code should PAUSE at least every 2^-n second,
Where n should preferrably be one more than for the hardware timer.
What should be n ? I think 11 to 16 is good.
What can the PC RTC do already ?


--    ,                                         ,           _ 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/"