types and operators

[Eric W. Biederman]

Nathan Hawkins <utsl@one.net> writes:
> 
> On 13 Jun 1996, Eric W. Biederman wrote:
> 
> > Nathan Hawkins <utsl@one.net> writes:
> > 
> > > 
> > > The following was written just before I left... Sorry about the long 
> > > delay, but maybe we can finish this subject, and get some code going.
> > > I did do a little research into Lisp implementations, and I'm starting to 
> > > favour option 2 (see below), but as I recall, at the time I wrote this  
> > > (about a month ago) I was for method 2.
> 
> Sorry, I meant to say a favoured option one when I wrote this stuff.
> 
> > > ----------
> > > 
> > > This is a summary of the possible designs for implementing pointer/int
> > > distinctions, along with pros and cons. If I've left out anything important
> > > out, please let me know.
> > > 
> > > 
> > > 1. a small tag within a 32-bit int/pointer
> > >    Pros:
> > >      * probably comes closest to normal Forth
> > >      * a cell on the stack is the same as a cell on the heap
> > >    Cons:
> > >      * loses bits from every pointer and int :-(
> > >      * requires overhead in operators
             does not require overhead in operators.
           One bit lost from pointers is trivial, 2 bits can be billed
           to alignment
           One bit lost for integers is also almost trivial.
> > > 
> > 
> > <commentary>
> > Actually I think I favor this one.  At least for a simple start up.
> > 
> > If we let the tag be the least significant bit, and have it _set_ for
> > pointers we lose no efficiency.  For a pointer load we can simply load
> > the address one byte before a pointer.  This also had advantages like
> > 2+ and CELL+ are equal as in traditional forth.  Since anything less
> > then 1+ on a pointer would greivously confuse the garbage collector I
> > guess that means native unicode support, since we have 16 bit
> > characters <grin>
> 
> Well, one problem with that, is that it would be much better to use
> 32-bit alignment for most things. Also, I would be inclined to use
> different string operator, and let those access strings with byte 
> granularity, while keeping pointers 32-bit aligned.

I am proposing to use 32 bit allignment.  What I meant by 2+ CELL+ =
is that 2 1 SHL 4 =  since it is the least significant bit that is
being used, as a flag.  

For pointers I would use either a pointer to one byte before the
object or a pointer to one byte past the object and do
MOV EBX, Pointer
MOV EAX, [EBX +1] ;; assuming a pointer to one byte before the object.

This incurs virtually no runtime overhead increments don't hardly
count.  The smallest adressable unit in this case would really be 16
bits.  We could probably really only use the upper 15 bits though.

Essentially I propose option 3 except we represent the objects
conservatively and let the collector be more aggressive.

> 
> > When we needed to manipulate all 31 bits we would simply need to be
> > sure that the garabage collector doesn't get called inbetween times.
> > 
> > I would further implement the stacks(RETURN, DATA) so that they grow
> > towards each other, and allocated on the heap.  This would allow
> > multiple threads, and threads that are asynchronous could simply
> > allocate their own subheap on the heap.  This has all the
> > possibilities for recursive heaps someone else mentioned.
> > 
> > This doesn't do a lot for native compilation, or ultimate efficiency
> > but it is workable for a boot strap implementation.
> > 
> > For real efficiency on non-forth hardware the only real possibility is
> > native compilation.  Anton Ertl ( I think that's his name) on
> > comp.lang.forth has done some very good research into native
> > compilation of forth.  Combinding his work with the work on compiling
> > lisp, scheme, ML, would really be the best approach.  But not
> > immediately :)  
> > 
> > </commentary>
> > 
> > > 2. Lisp-style cells, a pointer w/tag, and a 32-bit data element
> > >    Pros:
> > >      * hl things would be easy to implement
> > >      * doesn't lose any bits from pointers and ints :-)
> > >      * don't need to worry much about fragmenting the heap
> > >      * the stack could be implemented as a list on the heap
> > >    Cons:
> > >      * costs twice as much memory for each cell
> > >      * probably quite inefficient
> > > 
> > 
> > <commentary>
> > I think those extra 31 unused bits would get very tempting to use for
> > something.  I can imagine all kinds of hacks we could regret later.
> > Also I don't quite see how that would bye us much but one bit at the
> > expense of 31 for implemtation purposes.
> 
> I certainly didn't intend to waste them. :-) Specifically, I was thinking 
> in terms of lists, implemented almost identically to Lisp. Keeping the type
> tag in the cdr part of the cell would allow us to have 32 bit pointers 
> and integers on the car side.

That's the problem.  You will use those.  The code we write, or the
techniques we chose will not resemble those of Forth.  If our guide
for the LLL is to be Forth it should be essentially Forth.  Under
Option 1 we can write a GCing ANS Forth as fast as any other.  Under
this plan who knows what we will write but it won't be Forth.  Further
the compiled code will be implemented quite differently.

My point is we'll get lost in this implementation and never get
anywhere as Fare was in M4 and assembly.

> 
> This would simplify lots of things, since we could implement words as 
> lists of pointers to code. Stacks could also be implemented as lists, at 
> some cost on the x86, but such stacks could be grown within the heap without
> problems. Also, on Risc machines, this wouldn't be much overhead, because 
> most of them don't seem to have stack instructions...

This would hardly simplify anything, and trash pointer arithmetic
completely.  Furtherd on a Risc the worst crime you can commit is not
keeping your data in registers.

> 
> The point is, the process of garbage collecting such a heap is fairly 
> well documented. While it is arguably inefficient, it seems possible that 
> we may neatly avoid a lot of headaches this way. For instance, linked lists 
> are not seriously affected by being fragmented...

Fragmentation is a non-issue.  We have garbage collection don't worry about it.
Also reducing Fragmentation as much as possible is a major issue to
improve cache performance.

> 
> > </commentary>
> > 
> > > 3. traditional Forth, with a conservative collector
> > >    Pros:
> > >      * would be _very_ easy to implement
> > >    Cons:
> > >      * conserative collector - need I say more?
> > > 
> > > 4. stack frames, with types tagged in the frame
> > >    Pros:
> > >      * supposedly would allow easier identifying of types on the stack
> > >    Cons:
> > >      * needs type tags copied into the heap separately
> > >      * breaks Forth concepts entirely
> > > 
> > > 
> > 
> > 5. Native code compilation with a type smart compiler.
> >    Pros:
> >      * Very efficient.
> >      * Runs fast.
> >    Cons:
> >      * hard to implement
> >      * compiles slow ( likely faster then C though)
> > 
> > <commentary>
> > We really need to get to some version of 5 in the future.
> > 
> > What would be ideal would be to save enough information in word
> > headers so we can native code compile words after we have Forth
> > compiled them.
> 
> That would be the plan. Presumably we implement threaded code of some 
> sort first, then write the compiler on that, or in HLL later. (I would 
> prefer it be written in LLL.)
> 
> > </commentary>
> > 
> > ------------------------------
> > The real challenge to get right will be the implementation of the
> > data space dictionary manipulating words so they work alright in a
> > garbage collected setting.  The fact from ANS forth that dictionaries
> > can be broken into many pieces data, code, etc should help a lot.  The
> > challenge is to tell where garbage collected blocks start and end.
> 
> That's one of the reasons I'm favouring using cons cells. That problem 
> neatly goes away. The garbage collector would only need go through the 
> heap, and would not need to be aware of the dictionary.

The Forth heap, is the Forth dictionary, but it's not as general.
Let's keep it that way.

As far as , C, ALLOT et al. the dictionary data space words.  They
simply allow incremental allocation of space of the Forth dictionary.
Since pointer arithmetic is allowed per ANS for these incrementall
allocated regions we need to take a little care and make sure we set a
proper size.  This is not hard, it simply need some carefull
attention.

> > One bullet that shouldn't be too hard to bite is pointers into the
> > middle of objects.  I would simply keep a lookaside table with the
> > length and location of objects, sorted by location (for binary
> > search), and stack allocate the things.
> 
> Again, this also would be irrelevant where cells are individually equivalent.
> :-) Only "strings" would need this sort of thing. Probably we'd partition 
> the heap into two sections, one for variable length objects without 
> pointers, and the other for cons cells. No lookaside table needed.
> 

Let's say only vectors need this sort of thing.  And Vectors turn up
frequently in normal Forth.  Anyhow I meant it's easy, so we shouldn't
worry about it.

-----------------------------
Finally, a New Thought

I think that the connection between LLL and HLL should be that they
share a common internal native code compiler Language.  And can call
each others routines Natively.  The LLL should be for exposing the
machine as much as possible while making it easy to implement.  The
HLLs should be for writing cool aps etc. 

Eric

If we can tack a GC onto Forth,  will remaining ANS compliant (At least
after we load the ANS compatibilty wordsets) we will have acheived
something I think no other Language has done, and show how truly
reflexive forth really is.