Joy, Dolphin, Memory Management (was: Joy, FORTH, ...)

[btanksley@hifn.com]

From: iepos@tunes.org [mailto:iepos@tunes.org]

>> >Hmm... maybe a quote from the manual will help
>> >(from "Atomic Programs of Joy"):

>> >  A value of the list type is just a special case of a quotation in
>> >  which the elements are themselves literals.

>> I see what you mean.  Yes, this is an oddity of Joy.  (And 
>> it causes me some
>> confusion -- do you know what Joy does when you type "[+ 3] 
>> uncons"?)  

>Hmm... well, there's one way to find out...

>A test shows that you'll wind up with two things on the stack,
>"[3]" and "+"; this is confusing... It doesn't make sense that "+"
>would be on the stack; there doesn't seem to be any other way to get
>it there; I would have guessed that it would have
>executed "+", expecting two more numbers on the stack.

I would not expect it to execute anything -- but I completely understand why
you would.  In fact, given what little we know about Joy, I would almost
expect it to crash; it's undefined behavior.  However, apart from crashing,
I would expect it to leave a value of type 'function' on the stack.

As you point out, it's not clear where that type came from, and there's no
operations defined on it.

>Anyhow, I try to avoid "uncons"; to me, it seems similar to "undo".

No it's not -- 

  uncons == dup first swap rest.

'first' has the same problem as 'uncons', and it's clearly necessary.

>> The fact that quotations can be manipulated as lists isn't too hard
>> to handle; the problem is that lists are sometimes actually
>> quotations (as above), NOT true lists.

>Indeed, "[+ 3]" does not fall into the "list type" as the author of Joy
>defined it; this is because the elements of the quotation are not all
>literals; specifically, "+" is not a literal. To be a literal, it
>would have to be a primitive program that has the sole effect of
>pushing one thing onto the stack, but "+" is not this way...

Right.  One solution is to make the list manipulation programs treat
quotations as lists (which is what they do in Joy, although it's not
documented); in order to do that, we would have to add that new datatype,
"function", and it would be proper to provide a way to explicitly provide
it.

>> I'm currently compiling directly to the dictionary; I never 
>> write to the
>> disk.  It looks like the result will go into Dolphin as part 
>> of the kernal
>> utilities (and possibly as part of the kernel itself, the 
>> VM), so I'll never
>> write code deliberately to the disk (although the user may 
>> do this if they wish).

>Ahh... looking at Dolphin, I guess you're writing this in C and
>maybe some assembly.

Nope.  We started in Pygmy Forth, and we're moving to gForth; we'll
eventually metacompile it.  There is some assembly, of course, but we plan
on keeping that to a minimum.

>By the way, in C, if you know you're 
>dealing with an x86 machine, is it safe to do something like this? :

>  genprogram()();

>where "genprogram" is some program that allocates and fills an array
>of bytes with x86 code and returns it (cast to a void function 
>pointer)...
>I guess if it isn't safe, then you could just use some assembly to
>interface with your code generator...

It's safe only if you also know all the details of your compiler, and
generate the code accordingly.

>> Yes, it's x86, which makes the full register optimization a 
>> lot of pain for
>> very little gain.  Fortunately, the guy who's doing the 
>> optimizer claims
>> that it's very easy -- he's produced three versions in four days.

>Wow...

Sam is pretty impressive that way...  :)

>> I plan to implement quotations as arrays of pointers to 
>> word-structures (the
>> structures contain the name, code, and optimization info).  
>> Anything that's
>> not quoted gets compiled; compilation inlines certain 
>> primitives and always
>> generates a "CALL" instruction for everything else.  The 
>> stack is cached in
>> as many registers as possible (either that, or I'll cache 
>> TOS only in AX and
>> not cache anything else -- I have to compare).  Tail calls 
>> are converted to
>> jumps whenever possible.

>Interesting... One question... how are you planning on 
>implementing lists?

I'm not going to -- this Forth doesn't have dynamic memory management.  You
might say that the purpose of this is to prove whether or not Forth can be
adapted to work like Joy.

>I'm guessing you're going to supply special primitives for lists,
>and distinguish them from quoted programs (unlike Joy)...

You might say that.  On the other hand, my quotations are going to be
treated the same as an array...

>But then,
>the question is: are you going to keep the lists all in one piece,
>or are you going to split them up, and link the pieces with pointers?
>This seems like quite an important thing, as lists I'm guessing
>will play quite an important role in the system, and their efficiency
>will largely determine the efficiency of the whole system...

Nope.  They won't exist.

Even the arrays themselves won't have much of an effect on the efficiency of
the system -- until later.  Later on I start depending on my ability to take
source code, generate a quotation from it, and then run the quotation
through several different code generators at runtime, profiling the result.

>Another question is: will lists be kept directly on the stack, or
>will only pointers to them (off in the heap somewhere) be kept?

Eventually, everything will be kept in memory.

>The more I think about it, the more I like the idea of just keeping
>everything directly on the stack; of course, a problem that arises
>if one does this literally is that it becomes very expensive to
>shuffle things around on the stack... I'm not sure how serious this
>might be.

Also, you can't cache the top of the stack in a register.  I have really no
idea why you like the idea; it doesn't even make sense to me.

>Also, it is interesting that you think of using "CALL"... I'm inclined
>to always inline everything, but I guess this might not be practical
>in some cases...

It's impossible (recursive programs) and wasteful (cache locality inside
loops).

>but, recursion would at least would not be a special
>problem, as it can always be replaced by non-recursive things...

That's highly non-trivial.  Uncomputable, in fact.

>If there are some large programs that are used so many times that
>for storage (and caching) purposes one does not want to inline them,
>then this seems like a special case of a more general problem
>of things being copied so much that one wants to use 
>copying-by-reference
>rather than physical copying... if possible, it should be handled
>by the same mechanism...

Why?

>Anyhow, these are all rather raw thoughts... Probably the best way
>to figure out the best way is to experiment...

Sounds rational to me.

>There is one optimization that I've been thinking of that I think
>might be quite important... Often before using a procedure, one
>makes copies of the parameters if one still needs them, so that they
>are not permanently gobbled up by the procedure... For instance,
>if one has a big buffer of pixels on the stack (in the form of a list),
>and one is getting ready to flush them to the screen using "refresh",
>but one still wants the buffer of pixels, then one might do:

>  [refresh] sip

>or perhaps

>  dup refresh

>which is equivalent in this case, since "refresh" only uses 
>one parameter.
>Now, the point I wanted to get at is that it would be silly if the
>system implemented this by physically making a copy of the pixels;
>this is because "refresh" probably does not really need to write over
>the pixels; it probably just reads them, incrementing the stack pointer
>as it goes along. The pixels could probably be restored at the end
>just by backing up the stack pointer. However, some care might need
>to be taken to make this work; "refresh" might naturally use some of
>the stack as a scratch space, effectively destroying previous pixels...
>To make the technique work, one would have to make "refresh" use
>somewhere else as scratch space (probably it would just use 
>the original
>top of the stack, behind the pixel data)...

Or you could just depend on the fact that the list/array of pixels is in
memory, so a 'dup' only duplicates an address.

At some point it seems that we want to do what the programmer asks us to do,
instead of something radically different.

>Anyhow, precisely how this kind of optimization might be carried out
>is not quite clear to me...

"pessimization".

>> Except for the stack optimization and quotation, this is 
>> straight out of the
>> book for Machine Forth.  (http://www.ultratechnology.com).  
>> The quotation
>> unmistakably fits with the spirit of machine Forth; the 
>> optimization would
>> fit only if it were a user word and not a default action (I 
>> have to think about that).

>One other thing... it seems like you are thinking of keeping quotations
>in uncompiled form at runtime (with a compiled form attatched to it,
>perhaps)... It seems possible to me that one could always keep 
>quotations
>in compiled form, if one is willing to give up "uncons" and the other
>introspecting primitives...

This is true, but what would that gain me?

>The essential primitive then for forming
>new programs at runtime is "cons", which takes a base program "p", and
>another thing off the stack "x", and yields a modified program that is
>like the base program except that when run, the "x" is pushed before
>"p" is run... It seems conceivable that "cons" could be implemented
>dealing only with compiled programs, although if one was going to
>use such a constructed program many many times, then it would pay
>off to keep an uncompiled version available so one could optimize it;
>however, if one was going to use it, say, one time, then it would
>pay off not to waste time optimizing it.

That's the whole purpose of keeping quotations in "array of pointers to
function structs" form.  An array of function structs is less efficient to
execute than a stream of native code (although not disasterously less so,
since the appropriate interpreter is simply a loop containing an indirect
call), but it contains (or points to) information which can be used to count
executions, profile execution times, and so on.

So the first time you 'unquote' a program (that is, run it) you can just
'interpret' the list; the second time, you can compile it and run the
result, and the third and fourth time you just run the compiled result.  Any
more runs trigger a bigger, fancier optimiser...  And so on.

But that stuff isn't part of the VM; it's user code.

>> >but there is something lame about doing it that way... Anyway,
>> >I just realized that I'm talking about these variable-stack words
>> >now, which you really dislike, so I'd better stop, I guess :-)

>> No, all the words you implemented here are constant stack effect.

>Oh, that's true... But, if I gone one step further and mentioned a
>"dign" or "buryn" that took an integer off the stack telling how
>deep to go, _then_ I would have been talking about words with
>variable stack effects :-)

That's true.  It's easy to picture how to build such a word -- a loop would
do quite nicely.

>- "iepos" (Brent Kerby)

-Billy