# RE: [stack] CLIP, CONS, Registers, Blocks, IF-ELSE-THEN (was: Joy ful CLIP: early version)

## wtanksley@bigfoot.com — 2000-05-11 21:07:14

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

     >> There are tons of other reasons to want a register

    >> scheduler, of course.

    >> I'm being deliberately minimalistic.

    >Okay... so we agree.

     Probably not ;-), but I'll certainly agree that your choices and priorities

    are respectable.

     >> >Ahh. You're right. That was silly. The way you wrote it is better.

    >> >It could be written even more concisely if we had a "spin" primitive

    >> >that executes a program over and over again:

    >> >  [f] spin -> f f f f f ...

    >> Or even more efficient, a lazy evaluator

    >> (continuation-based, perhaps) which

    >> only generates the needed executions.  But I won't be able

    >> to do that until

    >> I understand continuations well enough.

    >It's interesting that you bring up continuations again. I had left the

    >idea behind with applicative systems. I don't see what use they'd have

    >in a Joy-like system. But ... maybe they would be useful ...

     I posted a message about backtracking just a while ago.  Clearly,

    backtracking is useful, and it works using continuations.

     >> >CONS allows you to generate programs at runtime, based on

    >> >other programs

    >> >except with a parameter "hard-wired" in. I don't see how

    >> >APPEND fills

    >> >this role...

    >> I don't have any idea what you mean by "hard-wired".

    >For, suppose we had just obtained our screen size from the

    >window manager

    >and our "x" and "y" are on the stack. Then all we have to do is

    >  [render] cons cons

    >and *POOF*, we have a new fine-tuned compiled version of "render" on

    >the stack that takes into account the fixed screen size. Of course,

    >the system might not bother to optimize the new program until it

    >realizes that it is going to be duplicated and called MANY times,

    >in a loop.

     Okay.  You're asking for a way to compile parameters into a procedure.  No

    problem.  You do it, as you note, the same way you build procedures.  Let's

    suppose x and y are on the stack:

    NAME: myRender

     swap append append ( add the parameters )

     ' render append ( add the function )

    myRender compile: myRender ( compile the quotation we just built into a

    function which has the same name. )

     >In case this still is not clear, let me point out the way Joy's "cons"

    >works:

    >  5 [foo] cons  ->  [5 foo]

    >As you can see, "cons" has the effect of hard-wiring the parameter

    >"5" into the program "foo" that had been pushed onto the stack.

     Right.

    As I discussed, APPEND operates in exactly the same way as cons in this

    respect, except that APPEND adds to the end of the list/array rather than

    the beginning.  (And it can only add atoms, not lists; in order to add a

    list, you have to express it as an atom first.)

     >> Programs in LISP are trees, right?  That's why a tree

    >> structure, the s-exp,

    >> is used to represent them, and that's why a tree-building

    >> program, CONS, is

    >> used to create them.

    >Hmm... I'm not sure if Joy's CONS is really the same thing as LISP's

    >construct that runs by the same name ...

     It is.

     >> Programs in concatenative languages are lists.

    >Well, not any more than LISP's programs are lists.

     You're going to have to really slow down and read my message.  You're

    assuming a LOT of false stuff, and it's really throwing you off.

    s-exps are trees, by definition.  Concatenative programs are better

    expressed as lists.  Think about it: concatenation makes sense on a list,

    but it makes no sense on a tree.

     >You could say

    >that programs in concatenative languages are also trees.

     Yes, you could.  This is what Joy does.  However:

     >They're

    >lists, but members of the list may also be lists, in the case of

    >a quotation.

     What's special about a quotation, I ask rhetorically?  Simply this: a

    quotation is _data_, not a part of the program.  It's a literal in the same

    sense that an integer is a literal.  If Joy manipulated our integers in tree

    form but didn't provide quotations, would Joy be a tree-structured language?

    No.  It would be a list-structured language with tree-structured data.

     >Joy's syntax is really very similar to LISP ...

    >the main difference is that we use []s instead of ()s, and omit

    >the outermost []. Of course, LISP is different in many other ways,

    >for instance, in that it does not use an explicit stack and

    >relies heavily on bound variables.

     Whew!  That's a heavy statement, and very untrue.  Joy doesn't have a

    distinguished position for functions versus parameters, and Lisp does.  Joy

    doesn't use [] to indicate function calls, but rather to indicate data

    boundaries.

     >> Therefore, an array-building program is sufficient.  CONS is

    >> a quite easy

    >> way to build a program, but it's simply overkill.

    >To me, CONS seems like the perfect way to build programs in Joy.

     It may very well be -- but only because, thanks to its implementation of IF,

    Joy uses data as code as part of its regular execution.  In other words, in

    order to write a simple Joy function which happens to use IF, you _have_ to

    construct some tree-based data.

    Forth programmers get around that by not using tree-structured data as parts

    of programs, and when such is needed, by using function calls (since a

    function call provides something very like a tree structure, although

    without the inefficiency).

     >But, I agree that it's not appropriate in a system that does not

    >provide automatic garbage collection. In such a system, it would

    >probably be better to have something like a COMPILE that takes a

    >pointer to a buffer of execution tokens and compiles the whole thing.

     If there are two ways of doing things, one requiring GC and one not

    requiring GC, the one not requiring GC is more efficient.  This isn't just

    opinion; it's established fact.  See Baker's papers on GC and

    thermodynamics.

     >But, even if one goes the automatic-memory-management route, there

    >are alternatives to CONS. For instance, there is CAT (concat) and UNIT:

    >  [x] [y] cat  ->  [x y]

    >  [x] unit     ->  [[x]]

     This is essentially what happens when you use APPEND instead of CONS.

    (Although APPEND takes a scalar and a list, rather than two lists.)  Unit,

    in this context, is the act of allocating a new, empty buffer.

     >> >Hmm... I don't think I quite understand what you're suggesting

    >> >(or is this just a joke :-)) ... you say to make it circular ...

    >> >do you mean, set it up so that if stack space is exhausted the stack

    >> >pointer just wraps around and begins eating up the bottom

    >> >of the stack?

    >> It's not a joke, and that's exactly what I meant.

    >> Mathematically, it makes

    >> absolutely no sense; but programmatically, it's very

    >> logical, and highly

    >> controllable.

    >> It's also very minimalist.  :-)

    >Well. In this kind of system, it wouldn't be possible to reliably do

    >some kinds of recursion. Hard to say how serious that would be ...

     Yes, it is.  Especially when it's so vague.

    More specifically, it would be hard to express extremely deep recursion.

    But realistically, it's already hard to express that; the programmer wishing

    to do that type of job usually finds some other way to do it.

     >> >> >Currently, there are no primitives for dealing with

    >> >> >arrays, buffers,

    >> >> >or things of that kind. Also, there is no support for lambdas

    >> >> >or definitions.

    >> >> Add the dictionary, and you'll have support for buffers, and

    >> >> a buffer is an array.

    >> >Yeah... I might end up using this sort of solution. In the

    >> >long term,

    >> >though, I'd like to find some way to unify quoted programs

    >> >with arrays,

    >> >so that primitives like "cons" and "concat" could work on both.

    >> cons will never work with true arrays; arrays respond only

    >> to indexing and concatenation.

    >What about insertion and deletion (of chunks into and out of the middle

    >of arrays)? These are things I'd want to be able to do with arrays too.

     Those are nothing more or less than indexing, concatenation, and array

    creation.

    Insertion creates a new array the size of both arrays together, then appends

    the elements of the first array up to the insertion point, then appends all

    of the elements of the second array, then appends the rest of the elements

    of the first array.  It then destroys the original first array.

    Deletion operates in the same basic way -- it creates a new array which

    contains some of the stuff contained in the old one, then treats the new

    array as though it were the old one.

     >Of course, I'd use them sparingly unless there's some automatic memory

    >management in place to improve their performance.

     Memory management would only hurt their performance.

    Of course, these things never happen in a vacuum; there's always some code

    _calling_ these array mutators.  It's quite possible that this code needs

    memory management of the arrays because it's not written linearly.  There's

    nothing wrong with that.

    At a low level, though, you want to start implementing without garbage

    collection, and only start using GC after you've implemented it.  If you

    think that you can't implement any more of your design until you add GC,

    that's your call.  I would disagree; I don't think it's possible to have GC

    until you have operations can use it.

     >> And since quotations are completely and correctly modelled

    >> by arrays, and

    >> arrays can be held in buffers, if you add support for buffers and

    >> compilation into those buffers you have all of the

    >> essentials for handling quotations.

    >Yes, that probably is not a bad way to do it for now. But, in the

    >long-term, I'd like to have some automatic memory management, so

    >that programmers do not have to worry about manually allocating,

    >resizing, and freeing buffers.

     Sure.  But you start by adding buffers to your system, and making your

    system use those buffers, and as your system gets more complete it can do

    more of the work of managing those buffers.

     >> So you're right; using quotations for conditionals isn't a

    >> terrible idea.  It just isn't simple.

    >Right. There are disadvantages to using quotations for conditionals,

    >but despite these I still like the idea.

     Understandably.

    Personally, I dislike the whole idea of complex conditionals.  They make

    your definitions much larger, and make it harder to break them apart into

    smaller definitions.  I think the Joy 'if' is too complex; not only does it

    take three parameters, it also requires both 'if' and 'else' blocks.  Chuck

    Moore doesn't even use ELSE blocks anymore; he simply returns at the end of

    his IF block, and performs the ELSE action after the endif.  This clearly

    would have the effect of keeping definitions short.

     >> Do you remember how I suggested compiling quotations to

    >> wordcode, with one

    >> cell per word/literal?  Well, IF and THEN may be immediate,

    >> but when they're

    >> quoted treat them just like any other word -- their wordcode

    >> is a single cell long.  In other words, they aren't executed.

    >> It's only when you're compiling the quotation that you

    >> actually execute the IF.

    >And you can only compile a quotation that has "IF" in it if the "THEN"

    >is in sight. Yes, this could be a solution. However, it seems kind of

    >strange that "immediate" words would then not always be executed

    >immediately, but may be executed at various times while the program

    >is running.

     They execute only when the system is generating code.  That's their job.

    There's a problem with my solution, though.  Some words in Forth look ahead

    in their source code, but if a quotation has already parsed the source for

    them they can't do that.  I think this is a message: quotations embedded in

    the source and source parsing don't ever mix.

    Of the two, I choose to keep source parsing, because it's a quick, simple,

    powerful operation, adding no overhead to the runtime.

     >Nevertheless, it _could_ work (although I think I'm

    >more inclined to just stick with the quotation-taking conditionals).

     I'm inclined to get rid of the idea of quotations as a special data

    structure.  I want to keep them, but I don't want to leave them as something

    which can be entered as a literal at anytime, nor do I wish to encourage

    their use where they aren't needed.

    If you need a quotation, you should be able to build it, just the same as

    when you need a list you can build it.  You can also write a microlanguage

    which will build either one for you -- but I won't do it for you, lest I get

    in your way when you're doing something else.

     >> Laziness might be hard in concatenative languages, though.

    >> The problem is

    >> that programs are assumed to be laid out in terms of

    >> dataflow, and are

    >> assumed to act sequentially on a single object, the stack.

    >> This single

    >> object is a bottleneck to parallelism (and laziness).

    >> Fortunately, there's

    >> a solution -- the stack can be usually treated as groups of

    >> items, and the

    >> dataflow-nature of stack based programming makes those

    >> groups easier to

    >> discover than they otherwise would be.  A good optimiser,

    >> lazy or otherwise,

    >> could treat those groups seperately.

    >Yes... something like this would make automatic laziness and

    >concurrency

    >not too hard. However, laziness and concurrency can only safely be

    >done if the programs in question are pure, i.e. they have no effect

    >except on the stack. If a group of programs are impure, then they must

    >be executed in the order specified; attempting to be lazy and postpone

    >one or trying to execute both at once may be bad.

     But this depends on what you mean by "pure".  Every procedure is in a sense

    pure if it performs only what it's supposed to do.  Displaying to the screen

    is perfectly fine, so long as you're supposed to do that.  A lazy/parallel

    compiler would have to track all of the different resources which are being

    modified and used, and could thus reasonably easily handle an impure

    functions in a pure language.  Assuming the language in question is

    concatenative, of course -- if it's not, the order the language is written

    in is not the order it's supposed to execute in, and the compiler has to

    make assumptions about instruction ordering.

     >> In many architectures there are enough registers to hold at

    >> least two Forth

    >> tasks onboard at the same time.  That is FAST context

    >> switching.  (In the

    >> x86, you can discard the TOS register by using direct memory

    >> references, at

    >> a speed penalty, so you can still fit two tasks onboard if

    >> it's worth the loss.)

    >This is a nice idea, but it wouldn't work on x86. Many instructions,

    >such as DIV, IN, and OUT require that the specific registers

    >EAX and EDX be used. And, CALL and RET require that ESP be used for

    >the return stack.

     This is why you can only fit two processes on an x86, even after discarding

    the TOS register.

     >Thus, if you were to switch tasks safely, you

    >would at least have to save EAX, EDX, ESP, and EIP (you _might_ be able

    >to get away with having the data stack pointers for two tasks be kept

    >in separate registers or in static memory addresses so that they don't

    >have to be saved). So, you can't really keep two tasks "on

    >board" at once;

    >it will at least be necessary to swap out those four registers.

     Ah, but if both tasks are truly on board you're going to save and restore

    all the registers anyhow when you task switch.

    And if only one task is on board, it's not a problem to store the DS in EDX,

    the TOS in EAX, and so on.

     >But, since we're going to be executing hundreds of thousands of

    >instructions in between context switches, the time needed to save

    >these four registers is insignificant. And, the monumental gain

    >of going ahead and allocating the other four registers will

    >FAR outweigh

    >the tiny loss of having to save them. At least, that's my suspicion;

    >I haven't done any benchmarks, so I can't really say.

     That's possible.  I'm only bringing up the options.  As I said, "if it's

    worth the loss."

     >- "iepos" (Brent Kerby)

     -Billy

## iepos@tunes.org — 2000-05-12 18:30:38

    > >It's interesting that you bring up continuations again. I had left the

    > >idea behind with applicative systems. I don't see what use they'd have

    > >in a Joy-like system. But ... maybe they would be useful ...

    >

    > I posted a message about backtracking just a while ago.  Clearly,

    > backtracking is useful, and it works using continuations.

     Ahh... I'll have to go back sometime and follow some of those

    links you gave...

     > >For, suppose we had just obtained our screen size from the

    > >window manager

    > >and our "x" and "y" are on the stack. Then all we have to do is

    >

    > >  [render] cons cons

    >

    > >and *POOF*, we have a new fine-tuned compiled version of "render" on

    > >the stack that takes into account the fixed screen size. Of course,

    > >the system might not bother to optimize the new program until it

    > >realizes that it is going to be duplicated and called MANY times,

    > >in a loop.

    >

    > Okay.  You're asking for a way to compile parameters into a procedure.  No

    > problem.  You do it, as you note, the same way you build procedures.  Let's

    > suppose x and y are on the stack:

    >

    > NAME: myRender

     Okay. Let me see if I've got this straight... That line was supposed

    to create a new empty buffer and name it "myRender", right?

    But wait, a pointer to it is getter pushed on the stack, too, right?

     >  swap append append ( add the parameters )

     Hmm. I'm not quite following this. Okay, "swap" gets things in order

    so that the "x" parameter is on top and the empty buffer beneath.

    Then we append. But wait, wouldn't we need to swap again before

    we append the "y"? Oh, no, because the "y" is prepended, since

    we want it to get pushed before the "x" in the resulting program.

    But wait. That wouldn't work... doesn't append care what order the buffer

    comes in? The buffer either has to be on top and the other item beneath

    or the other way around, right? So which way is it?

     >  ' render append ( add the function )

     Hmm. Okay, "' render" pushes a pointer to the "render" function onto

    the stack, right? And this pointer can be treated like a buffer.

    So we append it, completing the buffer we've been constructing.

    But, there's a problem here, I think. We have the buffer that contains

    our two parameters "x" and "y", and we have a buffer for the render

    function; what we need to is _concatenate_ them together. If I

    understand, this is not what your "append" does. "append" only adds

    a single item, right?

     > myRender compile: myRender ( compile the quotation we just built into a

    > function which has the same name. )

     Not sure I understand this. Isn't a pointer to our buffer on the stack.

    If so, then why are we pushing another one with "myRender"?

     > >> Programs in LISP are trees, right?  That's why a tree

    > >> structure, the s-exp,

    > >> is used to represent them, and that's why a tree-building

    > >> program, CONS, is

    > >> used to create them.

    > >>  [...]

    > >> Programs in concatenative languages are lists.

    >

    > >Well, not any more than LISP's programs are lists.

    >

    > You're going to have to really slow down and read my message.  You're

    > assuming a LOT of false stuff, and it's really throwing you off.

    >

    > s-exps are trees, by definition.  Concatenative programs are better

    > expressed as lists.  Think about it: concatenation makes sense on a list,

    > but it makes no sense on a tree.

     Hmm... I think I might be see what I was missing. When you see the s-exp

      (3 4 5)

    you are thinking of it as the tree:

         *

        / \

       3   *

          / \

         4   *

            / \

           5  nil

    Right? I was thinking that LISP lists were not necessarily always

    implemented with pointer chains in this way, that they could sometimes

    be implemented with arrays. But perhaps this is not true; I'm not

    very knowledgable about LISP and have never done any practical

    programming in it, so I'll just retreat and take back my above

    statement about LISP programs :-)

     > >You could say

    > >that programs in concatenative languages are also trees.

    >

    > Yes, you could.  This is what Joy does.  However:

     One thing I should clarify... When I said that Joy programs could

    be thought of as trees, I meant something like this: that this program

       0 [[dup . 1 +] dup call] dup call

    could be thought of as the tree:

             0 * dup call

               |

          ----------

          * dup call

          |

      ---------

      dup . 1 +

    That is what I meant, in case it was not clear.

     > >They're

    > >lists, but members of the list may also be lists, in the case of

    > >a quotation.

    >

    > What's special about a quotation, I ask rhetorically?

     Quotations are very special, a very important part of Joy.

    At least, that's my perspective.

    There's an interesting class of programs can be constructed from

    just "i", "dip", "cons", "dup", and "drop" using concatenation and

    quotation. Surprisingly, if you supplement these with some primitives

    for I/O, you can do just about anything, even without extra primitives

    for arithmetic, branching, and looping. This was demonstrated somewhat

    by my little interpreter that emulates fixed-point arithmetic

    (at http://www.tunes.org/~iepos/prog.c with 'remarks' file in same

    directory).

    In fact, I believe that the Joy base {call, dip, cons, dup, drop} corresponds

    closely to the {I, B, C, W, K} base of good old applicative combinatory

    logic.

    Since "i", "dip", "cons" require quotations in order to work, this

    may explain a bit why I find quotations so special.

     > Simply this: a quotation is _data_, not a part of the program.

    > It's a literal in the same sense that an integer is a literal.

     Well. Yes. I guess you could say that quotations are data.

     > >Joy's syntax is really very similar to LISP ...

    > >the main difference is that we use []s instead of ()s, and omit

    > >the outermost []. Of course, LISP is different in many other ways,

    > >for instance, in that it does not use an explicit stack and

    > >relies heavily on bound variables.

    >

    > Whew!  That's a heavy statement, and very untrue.  Joy doesn't have a

    > distinguished position for functions versus parameters, and Lisp does.  Joy

    > doesn't use [] to indicate function calls, but rather to indicate data

    > boundaries.

     Yes, there are many many differences. All I meant to say was that LISP

    and Joy are both based on lists. But then again, my experience with LISP

    is very limited ...

     > >But, even if one goes the automatic-memory-management route, there

    > >are alternatives to CONS. For instance, there is CAT (concat) and UNIT:

    > >  [x] [y] cat  ->  [x y]

    > >  [x] unit     ->  [[x]]

    >

    > This is essentially what happens when you use APPEND instead of CONS.

    > (Although APPEND takes a scalar and a list, rather than two lists.)  Unit,

    > in this context, is the act of allocating a new, empty buffer.

     Hmm... based on what I saw earlier, it looks to me like your APPEND is

    more similar to "cons" than to "cat". UNIT does not need to be taken

    as an extra primitive, since its effect can be emulated by creating

    an empty buffer and then APPEND'ing a single thing to it.

    By the way, earlier you seemed to have some construct "NAME" for making

    an empty buffer. It seemed to involve (gasp) binding a variable name.

    Ideally, it seems like we'd just use "[]" to push an empty buffer

    onto the stack.

     > >> cons will never work with true arrays; arrays respond only

    > >> to indexing and concatenation.

    >

    > >What about insertion and deletion (of chunks into and out of the middle

    > >of arrays)? These are things I'd want to be able to do with arrays too.

    >

    > Those are nothing more or less than indexing, concatenation, and array

    > creation.

    >

    > Insertion creates a new array the size of both arrays together, then appends

    > the elements of the first array up to the insertion point, then appends all

    > of the elements of the second array, then appends the rest of the elements

    > of the first array.  It then destroys the original first array.

    >

    > Deletion operates in the same basic way -- it creates a new array which

    > contains some of the stuff contained in the old one, then treats the new

    > array as though it were the old one.

     Oh, I see... Yes you could construct insertion and deletion from

    your favorite primitives: "indexing" (meaning "!" (fetch) and "@" (store)

    I suppose) and "array creation".. You really don't even need concatenation.

    It could be constructed in a similar way to insertion, by appending

    all the elements of the second array one at a time.

     > >Of course, I'd use them sparingly unless there's some automatic memory

    > >management in place to improve their performance.

    >

    > Memory management would only hurt their performance.

     Whoa... now what if somebody tries to insert a 64KB chunk into a

    big 2MB buffer? An automatic memory management system would certainly

    not hurt the performance if it decided not to actually insert the

    chunk, but instead just keep track and pretend that it inserted

    it. Of course, a programmer could do that himself, although it

    could get messy.

     > Personally, I dislike the whole idea of complex conditionals.  They make

    > your definitions much larger,

     Hmm... do they really? Let's compare:

      [x] [y] if

    to:

      IF x ELSE y THEN

    Looks like the FORTH one is larger by a bit.

     > and make it harder to break them apart into smaller definitions.

     Hmm... that's interesting. Do some FORTH programmers write definitions

    that include incomplete IFs? If so, then this may be a valid point.

     > I think the Joy 'if' is too complex; not only does it

    > take three parameters, it also requires both 'if' and 'else' blocks.

     True. I've considered adding another primitive "opt" that would take

    just an "if" block.

     > There's a problem with my solution, though.  Some words in Forth look ahead

    > in their source code, but if a quotation has already parsed the source for

    > them they can't do that.  I think this is a message: quotations embedded in

    > the source and source parsing don't ever mix.

     Yes. I think that may be true.

     > Of the two, I choose to keep source parsing, because it's a quick, simple,

    > powerful operation, adding no overhead to the runtime.

     And, I choose to keep quotations because quotations are cool.

     > I'm inclined to get rid of the idea of quotations as a special data

    > structure.  I want to keep them, but I don't want to leave them as something

    > which can be entered as a literal at anytime, nor do I wish to encourage

    > their use where they aren't needed.

     Hmm... this style is opposite from the one I'm considering. But it

    sounds like it would probably work out fine. There's no harm in

    trying both approaches.

     > If you need a quotation, you should be able to build it, just the same as

    > when you need a list you can build it.

     Yes. By the way, I mentioned earlier that I wanted some way to unify

    quotations with lists and buffers; I think I've come up with a pretty

    good solution, similar to Joy's. I'm going to have introspecting

    primitives "!" and "@" (similar to FORTH's words of the same names)...

    "@" would take an index and a quotation/list beneath, and would push

    the such-and-such element of the list onto the stack. "!" would

    act similarly, taking the item to store on top of the stack, and then

    the index and the quotation/list. There will also be a "size" primitive

    for inspecting the size of a quotation/list. A quotation would be

    formally identified with a list of execution tokens. Execution tokens

    could be fetched, stored, and compared as a means of reflection.

    It feels kind of funny advocating this technique, since it was only

    a couple months ago you were advocating it, and I was arguing about

    how impure it was.

    Anyway, there are many details to work out...

     > >> In many architectures there are enough registers to hold at

    > >> least two Forth

    > >> tasks onboard at the same time.  That is FAST context

    > >> switching.  (In the

    > >> x86, you can discard the TOS register by using direct memory

    > >> references, at

    > >> a speed penalty, so you can still fit two tasks onboard if

    > >> it's worth the loss.)

    >

    > >This is a nice idea, but it wouldn't work on x86. Many instructions,

    > >such as DIV, IN, and OUT require that the specific registers

    > >EAX and EDX be used. And, CALL and RET require that ESP be used for

    > >the return stack.

    >

    > This is why you can only fit two processes on an x86, even after discarding

    > the TOS register.

     Oh, I see now. At a task-switch, you can just exchange EAX, EDX, ESP, and

    the data stack pointer with the four remaining registers. I thought

    by "fit two tasks onboard" that you meant that you could switch

    tasks without _any_ exchanging of registers or memory. You can't do that on

    x86, but you can switch pretty fast, by doing the four exchanges,

    more-or-less (some other stuff would have to be done to switch EIP).

     > >- "iepos" (Brent Kerby)

    >

    > -Billy

     - "iepos" (Brent Kerby)

## wtanksley@bigfoot.com — 2000-05-12 19:36:32

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

     >> Okay.  You're asking for a way to compile parameters into a

    >> procedure.  No

    >> problem.  You do it, as you note, the same way you build

    >> procedures.  Let's

    >> suppose x and y are on the stack:

    >> NAME: myRender

    >Okay. Let me see if I've got this straight... That line was supposed

    >to create a new empty buffer and name it "myRender", right?

    >But wait, a pointer to it is getter pushed on the stack, too, right?

     Oops.  Sorry, I forgot to document that.

    The word "NAME:" modifies the dictionary by adding a name to it, and setting

    the "current definition" to the address of the name.  The name's default

    behavior when executed will be to push its address on the stack.

    APPEND adds its parameter to the end of the buffer for the "current

    definition."

    I was assuming Forth-like behavior there, not Joy-like behavior.

     >>  swap append append ( add the parameters )

    >Hmm. I'm not quite following this. Okay, "swap" gets things in order

    >so that the "x" parameter is on top and the empty buffer beneath.

     Swap simply exchanges x and y, so that when we append them they go in the

    right order.  Then we append twice, thereby compiling both x and y into the

    buffer.

     >But wait. That wouldn't work... doesn't append care what order

    >the buffer

    >comes in? The buffer either has to be on top and the other item beneath

    >or the other way around, right? So which way is it?

     Neither -- the "current buffer" is a dictionary concept, and APPEND uses it

    by default.  In other words, APPEND is a method of the singleton object

    'dictionary'.

    Sorry, my mistake.  I should have either chosen semantics which matched what

    I knew you were expecting, or I should have clearly documented mine (and

    probably chosen a different name).

     >>  ' render append ( add the function )

    >Hmm. Okay, "' render" pushes a pointer to the "render" function onto

    >the stack, right?

     Yes.

     >And this pointer can be treated like a buffer.

    >So we append it, completing the buffer we've been constructing.

     Almost.  I forgot to append one more thing; I need to append an EXIT, so

    that the word terminates when it reaches its end.  To do that, I can either

    "' EXIT APPEND", or I can ";" (since semicolon's job is to append an EXIT).

     >But, there's a problem here, I think. We have the buffer that contains

    >our two parameters "x" and "y", and we have a buffer for the render

    >function; what we need to is _concatenate_ them together. If I

    >understand, this is not what your "append" does. "append" only adds

    >a single item, right?

     We certainly do NOT want to concatenate them together; we want to

    concatenate a _call_ to render into our buffer.  If we wanted to concatenate

    them together, we would use a function named something like "' render

    APPEND-INLINE".  APPEND-INLINE would probably call APPEND repeatedly.

     >> myRender compile: myRender ( compile the quotation we just

    >> built into a function which has the same name. )

    >Not sure I understand this. Isn't a pointer to our buffer on the stack.

    >If so, then why are we pushing another one with "myRender"?

     No, there's not a pointer on the stack.  But there could be, and even if

    there wasn't I could have been consistant by making the compile: word

    compile the "current buffer" by default.

     >> >> Programs in LISP are trees, right?  That's why a tree

    >> >> structure, the s-exp,

    >> >> is used to represent them, and that's why a tree-building

    >> >> program, CONS, is

    >> >> used to create them.

    >> >>  [...]

    >> >> Programs in concatenative languages are lists.

    >> >Well, not any more than LISP's programs are lists.

    >> s-exps are trees, by definition.  Concatenative programs are better

    >> expressed as lists.  Think about it: concatenation makes

    >> sense on a list, but it makes no sense on a tree.

    >Hmm... I think I might be see what I was missing. When you see

    >the s-exp

    >  (3 4 5)

    >you are thinking of it as the tree:

    >     *

    >    / \

    >   3   *

    >      / \

    >     4   *

    >        / \

    >       5  nil

    >Right? I was thinking that LISP lists were not necessarily always

    >implemented with pointer chains in this way, that they could sometimes

    >be implemented with arrays.  But perhaps this is not true; I'm not

    >very knowledgable about LISP and have never done any practical

    >programming in it, so I'll just retreat and take back my above

    >statement about LISP programs :-)

     Grin.

    Just FYI, then, Lisp programs *must* be expressed as trees; this is why you

    have to use parens in them.  Even if you imagine that (3 4 5) is an array,

    Lisp programs are NEVER written as a single function call; they're always at

    least one layer of nesting deeper.  (add 5 4) may be valid Lisp, but it's

    not a program; (print (add 4 5)) is more likely, and (defun func (x) (print

    (add x 5))) is still more likely.

    The branches of this tree are required because they're parameters being

    applied to functions.  Conversely, take away the ability to apply parameters

    to functions, and you also remove the need for tree-structured code.

    This is fundamental.

    A while ago -- before I'd heard of Joy, and therefore before I'd heard of

    concatenative languages -- someone on the Lisp newsgroup quoted one of the

    inventors of Lisp as saying, "the strength of Lisp is how it's able to treat

    data as code.  Lisp will be dead only when someone comes up with a language

    which does this better."

    Need I spell out the next conclusion I logically make?

     >> >You could say

    >> >that programs in concatenative languages are also trees.

    >> Yes, you could.  This is what Joy does.  However:

    >One thing I should clarify... When I said that Joy programs could

    >be thought of as trees, I meant something like this: that this program

    >   0 [[dup . 1 +] dup call] dup call

    >could be thought of as the tree:

    >         0 * dup call

    >           |

    >      ----------

    >      * dup call

    >      |

    >  ---------

    >  dup . 1 +

    >That is what I meant, in case it was not clear.

     It's absolutely clear.  This is also what I meant.  However, it's notable

    that the _code_ does not itself have a tree structure; rather, some data

    which happens to be literally included in the code has a tree structure.

     >> >They're

    >> >lists, but members of the list may also be lists, in the case of

    >> >a quotation.

    >> What's special about a quotation, I ask rhetorically?

    >Quotations are very special, a very important part of Joy.

    >At least, that's my perspective.

     I agree.  They're not a vital part of any concatenative language, but

    they're such an important part of the theory and notation that I agree with

    you that any concatenative language without them is incomplete.

     >Since "i", "dip", "cons" require quotations in order to work, this

    >may explain a bit why I find quotations so special.

     Ah, but they don't require inline quotations.

     >> >But, even if one goes the automatic-memory-management route, there

    >> >are alternatives to CONS. For instance, there is CAT

    >> >(concat) and UNIT:

    >> >  [x] [y] cat  ->  [x y]

    >> >  [x] unit     ->  [[x]]

    >> This is essentially what happens when you use APPEND instead of CONS.

    >> (Although APPEND takes a scalar and a list, rather than two

    >> lists.)  Unit,

    >> in this context, is the act of allocating a new, empty buffer.

    >Hmm... based on what I saw earlier, it looks to me like your APPEND is

    >more similar to "cons" than to "cat". UNIT does not need to be taken

    >as an extra primitive, since its effect can be emulated by creating

    >an empty buffer and then APPEND'ing a single thing to it.

    >By the way, earlier you seemed to have some construct "NAME" for making

    >an empty buffer. It seemed to involve (gasp) binding a variable name.

    >Ideally, it seems like we'd just use "[]" to push an empty buffer

    >onto the stack.

     It didn't involve binding a variable name; its entire effect was to bind a

    variable name.  You're correct that it was the wrong way to solve the

    problem, though.  Your suggestion is wiser, although I would go a step

    further by not using a _new_ empty buffer, but rather borrowing a temporary

    buffer.

     >> >Of course, I'd use them sparingly unless there's some

    >> >automatic memory

    >> >management in place to improve their performance.

    >> Memory management would only hurt their performance.

    >Whoa... now what if somebody tries to insert a 64KB chunk into a

    >big 2MB buffer? An automatic memory management system would certainly

    >not hurt the performance if it decided not to actually insert the

    >chunk, but instead just keep track and pretend that it inserted

    >it. Of course, a programmer could do that himself, although it

    >could get messy.

     It would *certainly* not hurt performance?  That's a big assertion.  I can

    clearly see that there are cases when it would not hurt too badly, but all

    in all I believe it would damage both performance and code size (and

    therefore bugginess) greatly, because every bit of code which operated on

    that array would have to consider not only the end cases of the array, but

    also the end cases of pointers inserted into the so-called array.

    It's true that you can manage that all automatically; add an extra layer to

    generate code for those cases, add another layer to watch for code which

    will need that, add more layers to ...

    And so on.

    Why?  Why not just go back to simplicity, and get the same job done in the

    same amount of time in all cases using technology which exists now?  Your

    solution at best keeps the problem solution linear; it's not like the simple

    solution is O(2^n) and yours is O(n).

     >> Personally, I dislike the whole idea of complex

    >> conditionals.  They make

    >> your definitions much larger,

    >Hmm... do they really? Let's compare:

    >  [x] [y] if

    >to:

    >  IF x ELSE y THEN

    >Looks like the FORTH one is larger by a bit.

     Trivial cases prove nothing.  This case is so trivial that the overhead of

    the if overwhelms the overhead of your own code.

    Suppose that x and y were four or five words.  Suppose that you're reading

    the word they're included in for the first time.  You don't even know what

    those quotations are _for_ until you finally reach the 'if', which is almost

    invisible it's so small.

    Compare the Moore-style code:

    : one  IF x OTHERWISE y ;

    ...unlike ELSE, "OTHERWISE" compiles a return from the current word.

     >> and make it harder to break them apart into smaller definitions.

    >Hmm... that's interesting. Do some FORTH programmers write definitions

    >that include incomplete IFs? If so, then this may be a valid point.

     No Forth programmer would consider writing a definition with an incomplete

    IF, assuming that you mean an IF without a THEN.  However, every Forth

    programmer writes IFs without ELSEs.

     >> I think the Joy 'if' is too complex; not only does it

    >> take three parameters, it also requires both 'if' and 'else' blocks.

    >True. I've considered adding another primitive "opt" that would take

    >just an "if" block.

     This isn't a bad idea, aside from the abbreviation.  C is evil mainly

    because it abbreviates.  It's better to use a meaningless symbol than it is

    to use an abbreviation for a meaningful word.

     >> There's a problem with my solution, though.  Some words in

    >> Forth look ahead

    >> in their source code, but if a quotation has already parsed

    >> the source for

    >> them they can't do that.  I think this is a message:

    >> quotations embedded in

    >> the source and source parsing don't ever mix.

    >Yes. I think that may be true.

     Actually, I thought of another solution: the current Forth scheme has only

    two levels, normal and immediate.  Perhaps it needs three levels: normal,

    parsing, and immediate.

     >> Of the two, I choose to keep source parsing, because it's a

    >> quick, simple,

    >> powerful operation, adding no overhead to the runtime.

    >And, I choose to keep quotations because quotations are cool.

     And I respect that.  I believe quotations are essential.

     >Yes. By the way, I mentioned earlier that I wanted some way to unify

    >quotations with lists and buffers; I think I've come up with a pretty

    >good solution, similar to Joy's. I'm going to have introspecting

    >primitives "!" and "@" (similar to FORTH's words of the same names)...

    >"@" would take an index and a quotation/list beneath, and would push

    >the such-and-such element of the list onto the stack. "!" would

    >act similarly, taking the item to store on top of the stack, and then

    >the index and the quotation/list. There will also be a "size" primitive

    >for inspecting the size of a quotation/list. A quotation would be

    >formally identified with a list of execution tokens. Execution tokens

    >could be fetched, stored, and compared as a means of reflection.

     This looks exactly like what I was thinking, although I personally wouldn't

    use the names ! and @.  Perhaps I should, though.

    I also have another primitive, which in Forth is named "," (comma).  It

    appends a single execution token onto the current dictionary definition,

    growing the dictionary if needed.  I belive I would use it more than @ and

    !; those two would mainly be useful for patching existing code or writing

    quotations into fixed-sized buffers outside of the dictionary.

    Uh, by the way, Chuck Moore came up with a cool refinement for Forth:

    instead of having a single word ! which takes an address and a value, he has

    a set of words.  A! takes an address and stores it to the "current address

    register"; !A stores a value to the current address reg, and !A+ stores

    something and increments the address register.  This dramatically reduces

    stack manipulations, since most of the time you're using ! and @ you want to

    do multiple manipulations with a single pointer.

    In software, it might be prudent to have an A stack rather than just an A

    register (since words you call could overwrite the value in a register).

    Natually, there are also A@ and @A instructions.

     >> >> In many architectures there are enough registers to hold at

    >> >> least two Forth

    >> >> tasks onboard at the same time.  That is FAST context

    >> >> switching.  (In the

    >> >> x86, you can discard the TOS register by using direct memory

    >> >> references, at

    >> >> a speed penalty, so you can still fit two tasks onboard if

    >> >> it's worth the loss.)

    >> >This is a nice idea, but it wouldn't work on x86. Many instructions,

    >> >such as DIV, IN, and OUT require that the specific registers

    >> >EAX and EDX be used. And, CALL and RET require that ESP be used for

    >> >the return stack.

    >> This is why you can only fit two processes on an x86, even

    >> after discarding the TOS register.

    >Oh, I see now. At a task-switch, you can just exchange EAX,

    >EDX, ESP, and

    >the data stack pointer with the four remaining registers. I thought

    >by "fit two tasks onboard" that you meant that you could switch

    >tasks without _any_ exchanging of registers or memory. You

    >can't do that on

    >x86, but you can switch pretty fast, by doing the four exchanges,

    >more-or-less (some other stuff would have to be done to switch EIP).

     Actually, I wouldn't want to try to fit two tasks onboard at the same time

    unless the compiler was interleaving the tasks at compile-time.  Obviously,

    this is only good for certain types of task -- but it does have interesting

    implications for superscalar processors, since interleaving different

    registers reduces pipeline stalls.

     >- "iepos" (Brent Kerby)

     -Billy

## iepos@tunes.org — 2000-05-12 23:09:36

    > >> Okay.  You're asking for a way to compile parameters into a

    > >> procedure.  No

    > >> problem.  You do it, as you note, the same way you build

    > >> procedures.  Let's

    > >> suppose x and y are on the stack:

    >

    > >> NAME: myRender

    >

    > >Okay. Let me see if I've got this straight... That line was supposed

    > >to create a new empty buffer and name it "myRender", right?

    > >But wait, a pointer to it is getting pushed on the stack, too, right?

    >

    > Oops.  Sorry, I forgot to document that.

    >

    > The word "NAME:" modifies the dictionary by adding a name to it, and setting

    > the "current definition" to the address of the name.  The name's default

    > behavior when executed will be to push its address on the stack.

     But its address won't be pushed in this case, since this is the initial

    use of the name, which gets gobbled up by "NAME:" in a look-ahead

    parsing manner, right? Instead, the address is kept in the

    "current definition" register or static memory address. Okay, I think

    I get it now.

     > >>  swap append append ( add the parameters )

    >

    > >Hmm. I'm not quite following this. Okay, "swap" gets things in order

    > >so that the "x" parameter is on top and the empty buffer beneath.

    >

    > Swap simply exchanges x and y, so that when we append them they go in the

    > right order.  Then we append twice, thereby compiling both x and y into the

    > buffer.

     Yes, that makes sense now. This certainly is an interesting way to do it.

    If I understand now, this is the complete program for hard-wiring in

    the "x" and "y":

      NAME: myRender

      swap append append

      ' render append ;

      myRender compile: myRender

    But it sure seems like it would be easier if we had CONS so we could

    just do:

      [render] cons cons

    But this is probably not compatible with a manual memory management style...

     > A while ago -- before I'd heard of Joy, and therefore before I'd heard of

    > concatenative languages -- someone on the Lisp newsgroup quoted one of the

    > inventors of Lisp as saying, "the strength of Lisp is how it's able to treat

    > data as code.  Lisp will be dead only when someone comes up with a language

    > which does this better."

    >

    > Need I spell out the next conclusion I logically make?

     You conclusion is: it is possible that Lisp is now dead, because

    Mr. Thun has come up with a language which does a better job of

    allowing one to treat data as code.

     > However, it's notable

    > that the _code_ does not itself have a tree structure; rather, some data

    > which happens to be literally included in the code has a tree structure.

     Yes. You could think of it that way.

     > >> > [operations like insertion and deletion]

    > >> >Of course, I'd use them sparingly unless there's some

    > >> >automatic memory

    > >> >management in place to improve their performance.

    >

    > >> Memory management would only hurt their performance.

    >

    > >Whoa... now what if somebody tries to insert a 64KB chunk into a

    > >big 2MB buffer? An automatic memory management system would certainly

    > >not hurt the performance if it decided not to actually insert the

    > >chunk, but instead just keep track and pretend that it inserted

    > >it. Of course, a programmer could do that himself, although it

    > >could get messy.

    >

    > It would *certainly* not hurt performance?  That's a big assertion.

    > I can clearly see that there are cases when it would not hurt too badly,

    > but all in all I believe it would damage both performance and code size (and

    > therefore bugginess) greatly, because every bit of code which operated on

    > that array would have to consider not only the end cases of the array, but

    > also the end cases of pointers inserted into the so-called array.

     All right. I blew it. You're right. There are many cases where the

    physical insertion would be faster. However, now I'm going to modify

    the example. We still have a 2MB buffer. However, now instead of

    inserting 64KB we are only inserting one byte. And, very soon,

    we know that we are going to need to insert some more bytes, probably

    near the same location. We may also need to delete bytes.

    This situation happens in real life. In happens in text editors

    (although 2MB is stretching it). Anyway, I think that now you'd

    agree that physical insertions would be lame in this case; one

    solution would be to keep some padding in areas that are likely

    to have insertions soon, or that have just had deletions.

    Wouldn't it be nice if when you were writing a text editor you didn't

    have to worry about that, and could just freely insert and delete bytes

    here and there without fear of ridiculous performance? But then again,

    there is the argument that memory is very important, and not easy to

    automatically manage, and that a programmer should play a role in deciding

    how it is managed.

    To me, the issue boils down to this question: is automatic memory

    management really a hard problem? Or is it just tedious one? If it

    turns out that there exists a memory management algorithm that

    gives nearly optimal results in nearly all situations, then I'd say:

       Automatic memory management wins hands-down. Why write a system in

       which the programmer has to write relatively bloated programs to

       manually manage something that the system could do just as well?

    On the other hand, if it turns out that memory management is truly

    a hard problem, and that every time someone comes out with a new

    supposedly good algorithm for it, someone else comes out with an

    example program on which it performs horribly, and that even if one

    patches the algorithm to take into account the example, someone else

    can find yet another example on which in performs horribly, then I'd say:

       All right. I guess manual memory management is a good thing after all.

    My guess is that there exist algorithms that in nearly all situations

    do the job as well or better than nearly all programmers would.

    But this is only a guess; I could be wrong.

     > Suppose that x and y were four or five words.  Suppose that you're reading

    > the word they're included in for the first time.  You don't even know what

    > those quotations are _for_ until you finally reach the 'if', which is almost

    > invisible it's so small.

     That's a good point. However, this kind of thing can happens with nearly

    everything in both Joy and Forth, since they are postfix. It seems

    consistent with the spirit of postfix to go ahead and give the programs

    to branch to first, before you get to the "if".

     > >> and make it harder to break them apart into smaller definitions.

    >

    > >Hmm... that's interesting. Do some FORTH programmers write definitions

    > >that include incomplete IFs? If so, then this may be a valid point.

    >

    > No Forth programmer would consider writing a definition with an incomplete

    > IF, assuming that you mean an IF without a THEN.

     Yes, that is what I meant, yes.

     > However, every Forth programmer writes IFs without ELSEs.

     Makes sense...

     > >> I think the Joy 'if' is too complex; not only does it

    > >> take three parameters, it also requires both 'if' and 'else' blocks.

    >

    > >True. I've considered adding another primitive "opt" that would take

    > >just an "if" block.

    >

    > This isn't a bad idea, aside from the abbreviation.  C is evil mainly

    > because it abbreviates.  It's better to use a meaningless symbol than it is

    > to use an abbreviation for a meaningful word.

     I agree; abbreviations are evil, especially when they strip away all

    the vowels; this makes them hard to pronounce, and hard to type,

    when using a keyboard like Dvorak. However, in this case, one need not

    think of "opt" as an abbreviation for "option". I was thinking of it

    as a verb, as in, "He opted to sell his computer".

     > >Yes. By the way, I mentioned earlier that I wanted some way to unify

    > >quotations with lists and buffers; I think I've come up with a pretty

    > >good solution, similar to Joy's. I'm going to have introspecting

    > >primitives "!" and "@" (similar to FORTH's words of the same names)...

    > >

    > >[...]

    >

    > This looks exactly like what I was thinking, although I personally wouldn't

    > use the names ! and @.  Perhaps I should, though.

     There's one thing I might should clarify... The primary use of

    "!" and "@" that I had in mind was in dealing with structures

    other than quotations, such as arrays of pixels, sound samples,

    or characters. It just seems natural, and possibly useful in some

    situations, to extend their use to quotations as well.

     > I also have another primitive, which in Forth is named "," (comma).  It

    > appends a single execution token onto the current dictionary definition,

    > growing the dictionary if needed.  I belive I would use it more than @ and

    > !; those two would mainly be useful for patching existing code or writing

    > quotations into fixed-sized buffers outside of the dictionary.

     Yes, such a "," would be quite useful.

     > Uh, by the way, Chuck Moore came up with a cool refinement for Forth:

    > instead of having a single word ! which takes an address and a value, he has

    > a set of words.  A! takes an address and stores it to the "current address

    > register"; !A stores a value to the current address reg, and !A+ stores

    > something and increments the address register.  This dramatically reduces

    > stack manipulations, since most of the time you're using ! and @ you want to

    > do multiple manipulations with a single pointer.

     Yes. That seems like a useful technique. However, I'd be somewhat hesitant

    to use it, because of the way that it uses an address register instead

    of the stack. Here's a similar solution that I'd like better: just

    have "!" and "@" look at the pointer on the stack but not remove it.

    You could have "!+" and "@+" if you wanted, that would increment the

    pointer. When you were through the pointer, you'd "drop" it off.

    However, that technique would probably not be appropriate for FORTH

    (at least, you'd still want to keep the original "!" and "@" in some form).

    Because of the common use of the single slot variables that are fetched

    and stored with "!" and "@", it would be really annoying if

    one constantly had to drop the pointer off afterwards.

     > >- "iepos" (Brent Kerby)

    >

    > -Billy

     By the way, there's one thing I'd like to bring up. While fiddling

    with my interpreter, I've been getting a lot of mysterious

    Segmentation Faults because of accidentally running things like

    "call", "dip", and "if" with integers on the stack instead of programs.

    Thus, I've been thinking about adding some type-checking. But,

    I've run into a brick wall. I realized that if we have branching,

    it is sometimes impossible to tell at compile-time what the types

    of things on the stack will be.

    I'm just curious to know what you suggest to remedy this. Here are

    some possible policies the system could have, if it tries to

    find out the type of a thing on the stack but can't, yet would

    like to know because it is getting ready to execute, say, a "+" and

    wants to be sure it's two ints on the stack:

      1) Emit an error message that the programmer is too sneaky.

      2) Install a runtime check to make sure the types are right

         (this would involve carrying around some type tags).

      3) Don't do any checks, and just hope we're okay.

    Right now, I'm leaning toward #1. However, I'm pretty this means

    that there will be some cases that the programmer will be absolutely

    sure is program is safe, yet the system rejects it because it is

    not smart enough. My guess is that this could happen regardless

    of how smart the system is.

    - "iepos" (Brent Kerby)

## wtanksley@bigfoot.com — 2000-05-13 01:03:06

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

     >> >>  swap append append ( add the parameters )

    >> >Hmm. I'm not quite following this. Okay, "swap" gets things in order

    >> >so that the "x" parameter is on top and the empty buffer beneath.

    >> Swap simply exchanges x and y, so that when we append them

    >> they go in the

    >> right order.  Then we append twice, thereby compiling both x

    >> and y into the buffer.

    >Yes, that makes sense now. This certainly is an interesting

    >way to do it.

    >If I understand now, this is the complete program for hard-wiring in

    >the "x" and "y":

    >  NAME: myRender

    >  swap append append

    >  ' render append ;

    >  myRender compile: myRender

    >But it sure seems like it would be easier if we had CONS so we could

    >just do:

    >  [render] cons cons

    >But this is probably not compatible with a manual memory

    >management style...

     No, it's not.  It's also wasteful of memory, and it produces a program which

    runs _slower_ than the original.  But that's okay; include a single word at

    the end, for example, "compile-optimised", and you've got it as good as

    mine.

    Let me rewrite mine a little, using a better style:

    swap [] append append ' renderer append function: myRenderer

    compile-optimised

    Here's the same code, only without the naming, so it's equivalent to yours:

    swap [] append append ' renderer append

    Better?  "[]" is a word (not syntax) which prepares a static buffer to hold

    a definition, and returns the buffer address.  append works as before, but

    this time takes the address of a buffer.  compile-optimised takes the

    address of a buffer and compiles it into the dictionary.

    Remove the words I used at the end to give this new word a name, and you're

    ready to compare.  The two take almost the same amount of words, but the

    append version requires no memory management.

     >> A while ago -- before I'd heard of Joy, and therefore before

    >> I'd heard of

    >> concatenative languages -- someone on the Lisp newsgroup

    >> quoted one of the

    >> inventors of Lisp as saying, "the strength of Lisp is how

    >> it's able to treat

    >> data as code.  Lisp will be dead only when someone comes up

    >> with a language which does this better."

    >> Need I spell out the next conclusion I logically make?

    >You conclusion is: it is possible that Lisp is now dead, because

    >Mr. Thun has come up with a language which does a better job of

    >allowing one to treat data as code.

     Actually, I'm more of the opinion that whoever said that should eat his

    words, but yes.  ;-)

     >> >> > [operations like insertion and deletion]

    >> >> >Of course, I'd use them sparingly unless there's some

    >> >> >automatic memory

    >> >> >management in place to improve their performance.

    >> >> Memory management would only hurt their performance.

    >> >Whoa... now what if somebody tries to insert a 64KB chunk into a

    >> >big 2MB buffer? An automatic memory management system would

    >> >certainly

    >> >not hurt the performance if it decided not to actually insert the

    >> >chunk, but instead just keep track and pretend that it inserted

    >> >it. Of course, a programmer could do that himself, although it

    >> >could get messy.

    >> It would *certainly* not hurt performance?  That's a big assertion.

    >> I can clearly see that there are cases when it would not

    >> hurt too badly,

    >> but all in all I believe it would damage both performance

    >> and code size (and

    >> therefore bugginess) greatly, because every bit of code

    >> which operated on

    >> that array would have to consider not only the end cases of

    >> the array, but

    >> also the end cases of pointers inserted into the so-called array.

    >All right. I blew it. You're right. There are many cases where the

    >physical insertion would be faster. However, now I'm going to modify

    >the example. We still have a 2MB buffer. However, now instead of

    >inserting 64KB we are only inserting one byte. And, very soon,

    >we know that we are going to need to insert some more bytes, probably

    >near the same location. We may also need to delete bytes.

    >This situation happens in real life.

     Agreed.  Furthermore, even if this situation didn't actually exist, there

    are other situations where we really DO need automatic memory management.

    For example, it's VERY handy in building parsers (eww).  And so on.

    So I argued wrongly when I tried to point out that automatic memory

    management is slower.  It sometimes is -- but sometimes it's the only

    possible way to manage memory, and even when it's not the only possibility

    it's often easier and not all that much slower.

    Fortunately, that wasn't the point I was trying to make originally.  I was

    originally trying to demonstrate that you should start in your compiler by

    implimenting the primitive operations (which are always manual), and testing

    them manually.  Later on you can write automatic control programs which use

    those primitive components, but for now you want to start small.

    The point is that at every point you have a completely working language.

    It's more fun that way!  Plus, if you really think your language is good,

    you'd want to write your GC algorithm in it!!!!  (Okay, I'm kidding.  Nobody

    WANTS to write a GC algorithm.  Except for an insane freak.  Hey, me too!

    Okay, two insane freaks.)

     >In happens in text editors

    >(although 2MB is stretching it).

     Well, in THAT case there's an easier method -- don't keep the entire text in

    a single buffer; instead, keep it in a ragged array (a linked list of

    lines).  That doesn't require memory management either.  But that's a

    special case.

     >To me, the issue boils down to this question: is automatic memory

    >management really a hard problem? Or is it just tedious one?

     It's both.  But I think that the current GC solutions are sufficient.

     >My guess is that there exist algorithms that in nearly all situations

    >do the job as well or better than nearly all programmers would.

    >But this is only a guess; I could be wrong.

     You'd certainly be wrong, until we have computers that can write programs in

    general as well as humans.

     >> Suppose that x and y were four or five words.  Suppose that

    >> you're reading

    >> the word they're included in for the first time.  You don't

    >> even know what

    >> those quotations are _for_ until you finally reach the 'if',

    >> which is almost invisible it's so small.

    >That's a good point. However, this kind of thing can happens

    >with nearly everything in both Joy and Forth, since they are

    >postfix.

     That's true, but nowhere else in either Forth or Joy do you have data

    structures which span more than a few characters.  With everything else, you

    get to see the next operator right away, and it's usually easy to tell the

    operator apart from the data.  Not so with quotations.

     >It seems

    >consistent with the spirit of postfix to go ahead and give

    >the programs to branch to first, before you get to the "if".

     This is true.  It's also purely functional, which has some theoretical

    advantages.  However, we can see that it has some negative effects, and it

    certainly is harder to compile for.

    All in all, though, Forth programmers have tried that before, and it's never

    stuck.

     >> >Yes. By the way, I mentioned earlier that I wanted some way to unify

    >> >quotations with lists and buffers; I think I've come up

    >> >with a pretty

    >> >good solution, similar to Joy's. I'm going to have introspecting

    >> >primitives "!" and "@" (similar to FORTH's words of the

    >> >same names)...

    >> This looks exactly like what I was thinking, although I

    >> personally wouldn't

    >> use the names ! and @.  Perhaps I should, though.

    >There's one thing I might should clarify... The primary use of

    >"!" and "@" that I had in mind was in dealing with structures

    >other than quotations, such as arrays of pixels, sound samples,

    >or characters. It just seems natural, and possibly useful in some

    >situations, to extend their use to quotations as well.

     Oh!  I had no idea that's what you meant.  Yes, that makes especial sense in

    a primitive system, such as you're building.  No doubt you plan to get rid

    of them later, but for now they're essential.

     >> I also have another primitive, which in Forth is named ","

    >> (comma).  It

    >> appends a single execution token onto the current dictionary

    >> definition,

    >> growing the dictionary if needed.  I belive I would use it

    >> more than @ and

    >> !; those two would mainly be useful for patching existing

    >> code or writing

    >> quotations into fixed-sized buffers outside of the dictionary.

    >Yes, such a "," would be quite useful.

     Oh, it does require allocation which can smoothly grow -- the easiest way to

    do that is by what OTA calls "rubberband allocation", like the Forth

    dictionary or Unix's sbrk.

     >> Uh, by the way, Chuck Moore came up with a cool refinement for Forth:

    >> instead of having a single word ! which takes an address and

    >> a value, he has

    >> a set of words.  A! takes an address and stores it to the

    >> "current address

    >> register"; !A stores a value to the current address reg, and

    >> !A+ stores

    >> something and increments the address register.  This

    >> dramatically reduces

    >> stack manipulations, since most of the time you're using !

    >> and @ you want to

    >> do multiple manipulations with a single pointer.

    >Yes. That seems like a useful technique. However, I'd be

    >somewhat hesitant

    >to use it, because of the way that it uses an address register instead

    >of the stack.

     As I mentioned, in hardware you _want_ to use a register, but in software a

    stack would be just as efficient.  Not _the_ stack, but rather an additional

    stack.  Yes, I know what you're about to say: "But that makes those words

    impure, because they affect more than the stack!"  Well, think about it --

    those words are memory access words, and as such they already affect more

    than the stack.  :-)

     >Here's a similar solution that I'd like better: just

    >have "!" and "@" look at the pointer on the stack but not remove it.

    >You could have "!+" and "@+" if you wanted, that would increment the

    >pointer. When you were through the pointer, you'd "drop" it off.

     This is fine if you've only got one pointer and you never need to do any

    data manipulations.

     >However, that technique would probably not be appropriate for FORTH

    >(at least, you'd still want to keep the original "!" and "@"

    >in some form).

    >Because of the common use of the single slot variables that are fetched

    >and stored with "!" and "@", it would be really annoying if

    >one constantly had to drop the pointer off afterwards.

     Right.  That's why any technique shouldn't steal the names ! and @, since

    they're already used.  In general, avoid reusing names for functions with

    similar-but-different semantics.

     >- "iepos" (Brent Kerby)

     -Billy