# RE: [stack] Lambdas, Definitions

## wtanksley@bigfoot.com — 2000-05-04 00:29:11

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

     >Anyway, now for a topic I've been wanting to discuss for a

    >little while:

    >"lambdas" and their relationship to definitions, in

    >concatenative languages.

    >Some of this was discussed earlier on the TUNES list, but my thoughts

    >on the subject have cleared up a bit since then, so I don't mind

    >restating a bit of it.

     This is a clear restatement, yes.

     >Anyway, now back to concatenative languages. In Joy, one can construct

    >a squaring program as:

    >  dup *

    >What I'm going to suggest now is that it might be interesting if Joy

    >was extended so that one could also construct in a way like this:

    >  x\ [x] [x] *

     ...although I'm sure you meant to write this x\[x x *], since otherwise the

    scope of the parameter would be undefined, and the multiplication would be

    operating on quotations, which simply doesn't make any sense.

    I'm also pretty sure that you meant to say that it would be easy to extend a

    concatenative language to have a lambda construct; you couldn't have meant

    that Joy would be improved by such, because Joy is a proof-by-example that a

    language without a lambda construct is meaningful and useful.  Joy would be

    going back on its purpose by having such a thing.

    In fact, generally speaking it is simple to extend a concatenative language

    this way, because the words/functions in a concatenative language can often

    be made to parse the source ahead of them.  Thus, you could define a word

    "lambda" which did exactly what you wanted.  There are several packages in

    Forth which provide something similar; they either parse ahead and convert a

    simple infix syntax into Forth source, or they define "local variables"

    which are active for the duration of the current definition, and otherwise

    behave like VALUES (which are kinda like variables).

    IMO, and in the opinions of many more experienced than I, using the first

    can be useful when you're writing mathematical software; it's nice to be

    able to write Fortran code in a Fortran-like language.  Using the second is

    a clear indication that your code needs to be rewritten, because you've

    failed to understand dataflow.  (Of course, there's always the other point

    of view; that you should use whatever tools are available, and who cares

    about understanding.)

     >Here's the meaning of this program, word by word:

    >  "x\"  Pop the top item off the stack and call it "x".

    >  "[x]" Push x onto the stack.

    >  "[x]" Push x onto the stack.

    >  "*"   Multiply the top two things on the stack.

     There's a lot of problems with this.  The biggest one is that this new

    language invents a concept of "calling" items names.  Where do the items go

    when they're not being called?  Do they take up space?  Do they have any

    kind of overhead?

     >Moreover, such a lambda construct makes Joy's "==" syntax unnesessary,

    >in principle, and probably also in practice. For instance, suppose

    >one made these definitions:

    >  sqr    == dup *

    >  dot    == [*] cons dip [*] cons dip +

    >One could get the same effect using a couple lambdas instead of "==":

    >  [dup *] sqr\

    >  [[*] cons dip [*] cons dip +] dot\

     That's really facinating, but it's not correct; sqr would drop the quotation

    [dup *] on the stack when invoked, and you'd have to use i to invoke it.

    Nor is it correct to say that lambda makes definition unnecessary; or if it

    is, it's true either way.  Lambda requires a definition construct.

     >By the way, it is not my view that Joy is broken and needs to

    >be fixed by adding a lambda construct.

     Right.  You're more exploring what can be done with a language while still

    keeping it concatenative.  An interesting project.

    For those who weren't on the Tunes list, Brent has come up with some

    interesting results involving concatenative languages.  He first became

    interested in them when he figured out how to mathematically transform his

    favorite type of language into a concatenative one; watching him attempt to

    explain that to me would no doubt be amusing (I've been programming in Forth

    for a long time, so I was a quick convert to concatenative languages).  If

    such interests you, check the mailing list archives at www.tunes.org.

     >There even exist systematic ways that one

    >can use to eliminate these lambdas, replacing them with combinators

    >like "dup", "dip", and "cons". Here is a simple but lame algorithm

    >to do just that thing (it uses "i", "dip", "cons", "dup", and "pop"):

     [clip].

     >The algorithm happened to generate something fairly compact this time.

    >Usually we are not so lucky. Of course, there are better algorithms...

     Speaking of optimization...  Optimising concatenative languages is a

    facinating area of study, from what I've seen.  At

    http://www.ultratechnology.com Chuck Moore, the inventor of Forth, which was

    the first concatenative language, explains (or has explained) the changes

    Forth has gone through.  The language he's now using was carefully designed

    to be very efficient while still being fully concatenative (although that's

    not a word he uses, or even knows about).  There was a recent discussion on

    the Forth newsgroup news:comp.lang.forth about static typechecking for

    Forth, complete with static polymorphism.  MPE, a Forth company, sells a

    compiler which they claim perfectly optimises stack juggling.  My friend

    finished writing a similar optimiser in a matter of 3 days (if anyone's

    interested, I'll try to get him to post the code).

    I have hypothesised that optimising concatenative languages is easier than

    optimising other languages, because the programmer has written the program

    with dataflow in mind (commonly used things _must_ be near the top of the

    stack), so the most critical part of the optimization is already done.

     >- Brent Kerby ("iepos")

     -Billy

## iepos@tunes.org — 2000-05-04 15:18:18

    > >Anyway, now back to concatenative languages. In Joy, one can construct

    > >a squaring program as:

    > >

    > >  dup *

    > >

    > >What I'm going to suggest now is that it might be interesting if Joy

    > >was extended so that one could also construct in a way like this:

    > >  x\ [x] [x] *

    >

    > ...although I'm sure you meant to write this x\[x x *], since otherwise the

    > scope of the parameter would be undefined, and the multiplication would be

    > operating on quotations, which simply doesn't make any sense.

     Hmm... The original way I wrote it is still what I meant.

    I need to clarify... Okay, when I say "[foo]", I mean

      Push "foo" onto the stack.

    "foo" usually happens to be a program, and thus doing "[foo]" would

    usually have the effect of pushing a program onto the stack. In fact,

    in the original Joy, every well-formed expression denotes a program

    and thus "[foo]" would in all cases push a program onto the stack.

    However, in the extension I'm thinking of it becomes possible for some

    expressions to denote things other than programs. For example,

    if the number two is on the stack and we do "x\", then now "x"

    becomes a name for the number two, something other than a

    program. If, at this point we tried to do just "x", we'd have an

    error, because we'd be running something other than a program;

    what we want is to run "[x]", which pushes two back onto the stack.

    Hmm... Does that make sense now?

     > I'm also pretty sure that you meant to say that it would be easy to extend a

    > concatenative language to have a lambda construct; you couldn't have meant

    > that Joy would be improved by such, because Joy is a proof-by-example that a

    > language without a lambda construct is meaningful and useful.  Joy would be

    > going back on its purpose by having such a thing.

     I agree. A point was made by Joy not having a lambda construct.

    But, Joy has a definition construct; it seems to me like a natural

    generalization to have a lambda construct...

    For instance, here's a case where you might want a lambda:

    You've been using an interactive system and have been pushing and

    fiddling with things on the stack. You've ended up with a number

    or other structure on top of the stack that you find very interesting;

    in fact, it is so interesting that you'd like to give it a name.

    And this is exactly what a lambda would let you do; you'd just do

    "foo\" and *POOF* you can now refer to your number as "foo".

    Note that you cannot get anywhere with just "=="; you might like to

    say "foo == " but then you'd get stuck because you wouldn't know

    what to put on the right side. I like to think of lambda as a dynamic

    definition construct.

     > In fact, generally speaking it is simple to extend a concatenative language

    > this way, because the words/functions in a concatenative language can often

    > be made to parse the source ahead of them.  Thus, you could define a word

    > "lambda" which did exactly what you wanted.  There are several packages in

    > Forth which provide something similar; they either parse ahead and convert a

    > simple infix syntax into Forth source, or they define "local variables"

    > which are active for the duration of the current definition, and otherwise

    > behave like VALUES (which are kinda like variables).

     Yes. I can see how lambdas could be implemented that way...

     > >Here's the meaning of this program, word by word:

    > >

    > >  "x\"  Pop the top item off the stack and call it "x".

    > >  "[x]" Push x onto the stack.

    > >  "[x]" Push x onto the stack.

    > >  "*"   Multiply the top two things on the stack.

    >

    > There's a lot of problems with this.  The biggest one is that this new

    > language invents a concept of "calling" items names.  Where do the items go

    > when they're not being called?  Do they take up space?  Do they have any

    > kind of overhead?

     A naive system would implement lambdas by keeping an environment table

    of names and values; it would change as things go along. Every time

    one used a lambda, a new item would be added to the table; it would

    be removed when the lambda's scope ended.

    Of course, an efficient system would in many cases not actually use

    a table this way; in particular, if it can foresee the end of the

    lambda's scope, then it need not use a table at runtime at all,

    but instead could just leave the item on the stack (although the

    system would have to be carefully designed so that it appears that

    the item has disappeared off the stack; i.e., it would have to be skipped

    over (in a dip-like way) if other programs are run which use the top

    of stack). One possible way to implement lambdas would be to directly

    compile them into dips, dups, and such using an algorithm like the

    one mentioned earlier.

     > >Moreover, such a lambda construct makes Joy's "==" syntax unnesessary,

    > >in principle, and probably also in practice. For instance, suppose

    > >one made these definitions:

    > >

    > >  sqr    == dup *

    > >  dot    == [*] cons dip [*] cons dip +

    > >

    > >One could get the same effect using a couple lambdas instead of "==":

    > >  [dup *] sqr\

    > >  [[*] cons dip [*] cons dip +] dot\

    >

    > That's really facinating, but it's not correct; sqr would drop the quotation

    > [dup *] on the stack when invoked, and you'd have to use i to invoke it.

     Not so. When "sqr\" is used, it is the actual program "dup *" that is on

    the stack, and thus this actual squaring program will be mapped to the

    name "sqr".

    You might say that the lambda construct, as I've defined it, has a

    built-in unquoting effect. This makes sense when you considering that

    it also has a built-in duplicating effect (if the item is used more than

    once), destructive effect (if it is not used at all), dipping effect

    (if it is used after other programs), and consing effect (if it is

    used within a quotation). We might say that lambda is really an

    all-in-one combinator.

     > Nor is it correct to say that lambda makes definition unnecessary; or if it

    > is, it's true either way.  Lambda requires a definition construct.

     Hmm... my view is that lambda is a generalization of a definition construct.

    Definition is a special case of lambda in which the thing-to-be-defined

    is statically known (has justed been pushed on the stack as a literal).

     > For those who weren't on the Tunes list, Brent has come up with some

    > interesting results involving concatenative languages.  He first became

    > interested in them when he figured out how to mathematically transform his

    > favorite type of language into a concatenative one;

     By the way, that favorite type was the Purely Applicative type, a system

    that was (in principle) based solely on the binary construct of

    single-parameter-function-application. I still have a sort of interest

    in this kind of system; in a way, it is simpler even than Joy, as it

    would require only one essential construct, whereas Joy requires

    two (concatenation and quotation). I've never yet seen a system such as

    this implemented; the main disadvantage of it is that it is hard to

    implement well on processors; one would probably end up compiling to

    a concatenative intermediate language.

     > There was a recent discussion on the Forth newsgroup news:comp.lang.forth

    > about static typechecking for Forth, complete with static polymorphism.

     Wouldn't that be nice?

     > MPE, a Forth company, sells a compiler which they claim perfectly

    > optimises stack juggling.  My friend finished writing a similar

    > optimiser in a matter of 3 days (if anyone's interested, I'll try

    > to get him to post the code).

     That would be quite interesting, if he'd post the code

    (if I can read it;  it's probably in FORTH, I suppose).

    Yeah... FORTH really sounds interesting. Sometime I'm going to dig in

    and learn it, maybe with that book you recommended (Leo Brodie's

    "Thinking Forth", it was, I think).

    If I understand, FORTH's major weakness is that one cannot manipulate

    programs at runtime; one cannot push them onto the stack, and execute

    them, and "cons" them (But, I could be mistaken, I guess; perhaps some

    FORTH systems have ways of dynamically dealing with programs).

    Even in C, one could manipulate function pointers and call through them,

    although "cons"ing is not allowed.

    Also, Joy-like quotations could be used to unify FORTH's relatively

    disunified control constructs... FORTH systems have several keywords

    (ELSE, THEN, NEXT, and probably others) that act only to delimit programs;

    These could all be eliminated, "[" and "]" playing their role, if

    one modified "IF" and "FOR" to look on the stack for programs to

    branch on or iterate.

    It would be cool, I think, if the efficiency of FORTH could be

    combined with the elegance of Joy-like quotations. Perhaps sometime

    I'll start working on such a project. But it's quite a formidable task

    to me, as I have basically no experience with making compilers.

    A while back I found some docs on the ELF format and also a very

    useful "Whirlwind Tutorial on Creating Really Teensy ELF Executables",

    but I'm still intimidated by all these weird headers and tables :-)

     > I have hypothesised that optimising concatenative languages is easier than

    > optimising other languages, because the programmer has written the program

    > with dataflow in mind (commonly used things _must_ be near the top of the

    > stack), so the most critical part of the optimization is already done.

     I also suspect this is true.

     > >- Brent Kerby ("iepos")

    >

    > -Billy

     - Brent Kerby ("iepos")

## wtanksley@bigfoot.com — 2000-05-05 02:05:57

    This is being bcc'ed to the guy who implemented the optimizer.  Sam, if

    you'd care to make your optimiser public, feel free to upload it to this

    egroup or email it to me.  Oh, and feel free to join the group :-); we could

    stand to have a wider diversity of opinions.

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

     >> >Anyway, now back to concatenative languages. In Joy, one

    >> >can construct

    >> >a squaring program as:

    >> >  dup *

    >> >What I'm going to suggest now is that it might be interesting if Joy

    >> >was extended so that one could also construct in a way like this:

    >> >  x\ [x] [x] *

    >> ...although I'm sure you meant to write this x\[x x *],

    >> since otherwise the

    >> scope of the parameter would be undefined, and the

    >> multiplication would be

    >> operating on quotations, which simply doesn't make any sense.

    >Hmm... The original way I wrote it is still what I meant.

    >I need to clarify... Okay, when I say "[foo]", I mean

    >  Push "foo" onto the stack.

     When Joy says that, it means "push a quotation containing only foo onto the

    stack."  Making Joy do something else within the special case of a lambda

    would seem to be counter to your purpose; if lambdas, for some reason,

    require this, then lambdas are clearly not a good fit for Joy.

     >"foo" usually happens to be a program, and thus doing "[foo]" would

    >usually have the effect of pushing a program onto the stack. In fact,

    >in the original Joy, every well-formed expression denotes a program

    >and thus "[foo]" would in all cases push a program onto the stack.

     Every well-formed expression _can_ denote a program, but that doesn't mean

    that all of them do.  If foo is a program, doing 'foo' will run the program,

    and if 'foo' is a literal or quotation, doing 'foo' will push it on the

    stack.

     >However, in the extension I'm thinking of it becomes possible for some

    >expressions to denote things other than programs. For example,

    >if the number two is on the stack and we do "x\", then now "x"

    >becomes a name for the number two, something other than a

    >program. If, at this point we tried to do just "x", we'd have an

    >error, because we'd be running something other than a program;

    >what we want is to run "[x]", which pushes two back onto the stack.

    >Hmm... Does that make sense now?

     No.  I mean, it makes your example clear, but it lacks a lot: first, it

    lacks delimitation (you had to invent a funky chunk of syntax to make it

    make sense); second, it lacks consistency; and third, it lacks reliability

    (why should a defined word cause an error?).

    It's strange that you'd see a need for "something other than a program."

    You can create a word which means 2 by writing a program which has no effect

    other than pushing 2 on the stack; the program is then in every way

    equivalent to '2'.

     >But, Joy has a definition construct; it seems to me like a natural

    >generalization to have a lambda construct...

     Well, if you had said "specialization" this would make sense.  A lambda is a

    special case of definition.  But let's wait on that; a while later you give

    some reasons for calling lambda a "generalization" of definition.

     >For instance, here's a case where you might want a lambda:

    >You've been using an interactive system and have been pushing and

    >fiddling with things on the stack. You've ended up with a number

    >or other structure on top of the stack that you find very interesting;

    >in fact, it is so interesting that you'd like to give it a name.

    >And this is exactly what a lambda would let you do; you'd just do

    >"foo\" and *POOF* you can now refer to your number as "foo".

    >Note that you cannot get anywhere with just "=="; you might like to

    >say "foo == " but then you'd get stuck because you wouldn't know

    >what to put on the right side. I like to think of lambda as a dynamic

    >definition construct.

     The Forth way to do this is to create a constant (although variables would

    also be possible).  I do agree that definitions are not general enough to

    handle this; that's because Joy deliberately chose to make definitions a

    seperate language, not part of the main concatenative language, in order to

    make the result more easily analyzable by conventional means.  There are

    many similar compromises in Joy.

     >> >Here's the meaning of this program, word by word:

    >> >  "x\"  Pop the top item off the stack and call it "x".

    >> >  "[x]" Push x onto the stack.

    >> >  "[x]" Push x onto the stack.

    >> >  "*"   Multiply the top two things on the stack.

    >> There's a lot of problems with this.  The biggest one is

    >> that this new

    >> language invents a concept of "calling" items names.  Where

    >> do the items go

    >> when they're not being called?  Do they take up space?  Do

    >> they have any

    >> kind of overhead?

    >A naive system would implement lambdas by keeping an environment table

    >of names and values; it would change as things go along. Every time

    >one used a lambda, a new item would be added to the table; it would

    >be removed when the lambda's scope ended.

     This would, of course, be a new concept for the language, something I would

    be loathe to introduce without completely changing the meaning of the

    language.

    Forth uses this, by the way.  It's a good speed optimization, but it means

    that some words have effects aside from the stack, and that isn't very

    Joylike.  On the other hand, with concatenative languages it's easy to

    predict where those special effects will apply, so you can afford to

    disregard them except when they're needed.

     >Of course, an efficient system would in many cases not actually use

    >a table this way; in particular, if it can foresee the end of the

    >lambda's scope, then it need not use a table at runtime at all,

    >but instead could just leave the item on the stack (although the

    >system would have to be carefully designed so that it appears that

    >the item has disappeared off the stack; i.e., it would have to

    >be skipped

    >over (in a dip-like way) if other programs are run which use the top

    >of stack). One possible way to implement lambdas would be to directly

    >compile them into dips, dups, and such using an algorithm like the

    >one mentioned earlier.

     I would consider this a more Joy-like solution, but it isn't simple; it

    requires some parsing.  Fortunately, aside from the parsing, the basic

    algorithm is simple (using my notation; yours cannot be expressed in Joy):

    x\[anything x else x something]

    -->

    [anything] dup dip [else] dip something

    In other words, for a single lambda, find all of the occurances and quote

    between them.  Replace every occurance except for the last one with "dup

    dip"; replace the last one with "dip", and unquote the sequence following

    the last occurrence.  Repeat this algorithm every time you reach a lambda

    (lambdas must be lexically nested; every lambda must be completely contained

    by any lambda containing any part of it).

    If you look at the language Rebol (www.rebol.org), you'll see that they have

    a similar construct; in Rebol, text inside a block is not parsed by the

    language (it's only lexed), and there are operators which can do similar

    transformations.  For example, your lambda is similar or identical to

    Rebol's "[block text var]/var=3" construct (IIRC).  Rebol is an interesting

    language; it's directly derived from Forth, but instead of being

    concatenative like Forth, it borrows Forth's ability to parse ahead in the

    source.

    I'd like to build a language which inherited its basic ideas, including a

    simple VM, from Forth; concatenative refinements from Joy (meaning, of

    course, the papers on the Joy website); and a parsing engine like Rebol's.

    Oh, I'd also like static typing and polymorphism.  It would look and act

    largely like Forth; I wouldn't expect, for example, to include garbage

    collection or full-powered quotations (although I would definitely include a

    primitive equivalent).  I'd also like to see a language which started with

    Joy (fully garbage collected, etc.) and added stuff from Forth and other

    languages.

    Ideal would be if both languages wound up looking and acting similar, so

    that we could almost give them the same name without dishonesty.  One, the

    Forth-descended language, could be used when you need precise control of the

    machine (Forth is famous for that); the other could be used when you don't

    need that kind of precision, but instead want the machine to handle details

    like garbage collection for you.

    Speaking of GC, check out ftp://ftp.netcom.com/pub/hb/hbaker/home.html;

    there you'll find columns on Forth, garbage collection, and a number of

    other interesting topics.  I especially enjoyed the ForthStack, ReverseGC,

    and ThermoGC papers.

     >> >Moreover, such a lambda construct makes Joy's "==" syntax

    >> >unnesessary,

    >> >in principle, and probably also in practice. For instance, suppose

    >> >one made these definitions:

    >> >  sqr    == dup *

    >> >  dot    == [*] cons dip [*] cons dip +

    >> >One could get the same effect using a couple lambdas

    >> >instead of "==":

    >> >  [dup *] sqr\

    >> >  [[*] cons dip [*] cons dip +] dot\

    >> That's really facinating, but it's not correct; sqr would

    >> drop the quotation

    >> [dup *] on the stack when invoked, and you'd have to use i

    >> to invoke it.

    >Not so. When "sqr\" is used, it is the actual program "dup *"

    >that is on

    >the stack, and thus this actual squaring program will be mapped to the

    >name "sqr".

    >You might say that the lambda construct, as I've defined it, has a

    >built-in unquoting effect. This makes sense when you considering that

    >it also has a built-in duplicating effect (if the item is used

    >more than

    >once), destructive effect (if it is not used at all), dipping effect

    >(if it is used after other programs), and consing effect (if it is

    >used within a quotation). We might say that lambda is really an

    >all-in-one combinator.

     You do claim that lambda is a generalization of all combinators.  However,

    you can see from my simple algorithm above that lambda is completely

    described by quotation, dip, dup, and drop; therefore, those elements are

    truly the source of its combinatorial generality.  In addition, 'dip' is a

    black box, performance-wise, so algorithms using it will be black boxes to

    the programmer trying to think in terms of performance.  (In Forth there is

    no 'dip'; instead, you save a stack item by shoving it onto the return

    stack, which has the exact same effect.)

    You're also equating lambda to i (unquoting), but in order to do that you

    have to seriously trash Joy's syntax.  I don't see what benefit you're

    getting from that.

     >> Nor is it correct to say that lambda makes definition

    >> unnecessary; or if it

    >> is, it's true either way.  Lambda requires a definition construct.

    >Hmm... my view is that lambda is a generalization of a

    >definition construct.

    >Definition is a special case of lambda in which the thing-to-be-defined

    >is statically known (has justed been pushed on the stack as a literal).

     Here's the place I was thinking about when I mentioned that you provided

    evidence that your lambda was a generalization of a definition.  I see your

    point.

    However, I don't see this as a generalization of definition, but rather as a

    use of what we called "slots" (AKA constants) or of parsing, together with

    definition.

     >> For those who weren't on the Tunes list, Brent has come up with some

    >> interesting results involving concatenative languages.  He

    >> first became

    >> interested in them when he figured out how to mathematically

    >> transform his

    >> favorite type of language into a concatenative one;

    >By the way, that favorite type was the Purely Applicative

    >type, a system

    >that was (in principle) based solely on the binary construct of

    >single-parameter-function-application. I still have a sort of interest

    >in this kind of system;

     In other words, currying.  That wasn't the only thing it's based on, of

    course; it also used combinators more than any other applicative language

    I've seen.

     >in a way, it is simpler even than Joy, as it

    >would require only one essential construct, whereas Joy requires

    >two (concatenation and quotation).

     We've spent a lot of time arguing over that, and it's amazing that after all

    that volume of text neither one of us has budged an inch.  Especially

    considering how after our debates, you added an entire additional LANGUAGE

    onto your purely applicative system in order to handle actually performing

    actions.

    Your language requires the same number of constructs as concatenative

    languages require, and when you're finished, you still don't have the

    ability to run anything; you can only make mathematical statements which may

    or may not be decidable.

    Joy requires concatenation and quotation; your language requires application

    and grouping.

     >I've never yet seen a system such as

    >this implemented; the main disadvantage of it is that it is hard to

    >implement well on processors; one would probably end up compiling to

    >a concatenative intermediate language.

     You could do that, but you could also parse it into a tree and interpret the

    tree.  If the mapping it described was computable, of course.

     >> There was a recent discussion on the Forth newsgroup

    >> news:comp.lang.forth

    >> about static typechecking for Forth, complete with static

    >> polymorphism.

    >Wouldn't that be nice?

     It looked good.  The guy didn't post his source, but it looked simple

    enough; just add a single compile-time type stack, and add type info to each

    word.  With an implementation of backtracking as well, you could also

    dispatch on the return type of the word, which would be really impressive

    (and useful, for certain words).

     >> MPE, a Forth company, sells a compiler which they claim perfectly

    >> optimises stack juggling.  My friend finished writing a similar

    >> optimiser in a matter of 3 days (if anyone's interested, I'll try

    >> to get him to post the code).

    >That would be quite interesting, if he'd post the code

    >(if I can read it;  it's probably in FORTH, I suppose).

     I'll mention it to him (via bcc).

     >Yeah... FORTH really sounds interesting. Sometime I'm going to dig in

    >and learn it, maybe with that book you recommended (Leo Brodie's

    >"Thinking Forth", it was, I think).

     Starting Forth is a great starter; Thinking Forth is more philosophical.

     >If I understand, FORTH's major weakness is that one cannot manipulate

    >programs at runtime; one cannot push them onto the stack, and execute

    >them, and "cons" them (But, I could be mistaken, I guess; perhaps some

    >FORTH systems have ways of dynamically dealing with programs).

     Although this is a true statement, it's not Forth's greatest weakness; in

    fact, it's almost irrelevant.  If you want to do this style of program

    manipulation in Forth you can either use strings or arrays of execution

    tokens.  Forth philosophy encourages you to not do that, though, because

    it's slow and generally not needed; it's better to do things like that at

    compile-time whenever possible.  Forth provides a full toolkit for that.

     >Even in C, one could manipulate function pointers and call

    >through them, although "cons"ing is not allowed.

     Of course, you can also do that in Forth; consing is trivial, using the word

    "compile,", and execution tokens may be manipulated as easily as integers.

     >Also, Joy-like quotations could be used to unify FORTH's relatively

    >disunified control constructs... FORTH systems have several keywords

    >(ELSE, THEN, NEXT, and probably others) that act only to

    >delimit programs;

    >These could all be eliminated, "[" and "]" playing their role, if

    >one modified "IF" and "FOR" to look on the stack for programs to

    >branch on or iterate.

     I've always thought that would be cool.  At the same time, though, the way

    Forth does it is very efficient and exactly as flexible, and Forth's words

    aren't as disunified as they might appear at first glance.  Those words

    which you claim exist only to delimit programs do not in fact have any

    delimitation action; their action is to do things like compile and resolve

    jumps.  It turns out that all of Forth's conditional words can be used

    together interchangably to create some facinating control structures.

     >It would be cool, I think, if the efficiency of FORTH could be

    >combined with the elegance of Joy-like quotations.

     I'd like this.

     >Perhaps sometime

    >I'll start working on such a project. But it's quite a formidable task

    >to me, as I have basically no experience with making compilers.

     There's not as much to worry about as you might expect.

    Do not try to make a compiler, for that is impossible.  Instead, realize the

    truth: there is no compiler.  There is only a word-by-word recogniser with

    two states.  If the state is "interpreting", execute the meaning of each

    word as you reach it.  If the state is "compiling", and the meaning of the

    word is tagged as "immediate", execute the meaning of the word; otherwise

    append a call to the word into the current definition.

    Now, define a word named ":" which parses one word out of the input stream,

    starts a new definition with that name, and sets the state to "compiling".

    Define another word called ";" which is tagged as immediate, whose action is

    to compile an EXIT and then set the state to "interpreting".

    You're done.

    Making this system write executables to the disk is best done through a

    process called "target compiling".  We could discuss that, but it'd be

    easier for you to learn Forth first, and see how they do it; in the

    meantime, you have a full-powered interactive system which generates compact

    native code.  Inlining is a trivial extension which can be applied in small

    steps, each of which are tested.  Peephole optimization is also well-tested.

     >- Brent Kerby ("iepos")

     BTW, should I refer to you as Brent or iepos?  And, just as an amusing

    sidelight, I keep mispronouncing your nick as "yay-ross", since the p

    reminds me of the Greek rho and the spelling and word shape is otherwise

    similar to Greek.

    -Billy

## iepos@tunes.org — 2000-05-05 22:44:32

    > >Hmm... Does that make sense now?

    >

    > No.  I mean, it makes your example clear, but it lacks a lot: first, it

    > lacks delimitation (you had to invent a funky chunk of syntax to make it

    > make sense); second, it lacks consistency;

     These do not make sense to me. To me, the extension seems fairly clear

    and consistent; it does not really add any funky syntax. Programs are

    still constructed from words with just concatenation and quotation. All

    I'm adding are schemes of words: "x\", "y\", "foo\", "x", "y", "foo", etc.

     > and third, it lacks reliability

    > (why should a defined word cause an error?).

     This is not unique to my extension. You complain that I can get an error

    by doing something like this:

      2 x\ x

    When it comes time to run "x", there is an error because it is not a

    program, but a number. But, one can get a similar error in normal Joy

    with this program:

      2 i

    This causes an error because the number two on the stack is not a program:

      run time error: quotation as top parameter needed for i

     > >For instance, here's a case where you might want a lambda:

    > >[...]

    >

    > The Forth way to do this is to create a constant (although variables would

    > also be possible).  I do agree that definitions are not general enough to

    > handle this;

     It may be that Forth's "constant" feature is an alternative way to

    deal with this, as you say ...

    By the way, it should not be construed that lambdas are like global

    variables, and that one could just modify its value (using the top

    item on the stack) by closing its scope with "\x" and opening again

    with "x\". This technique would be okay in some situations;

    however, I would consider it unacceptable for a quotation to close

    any lambdas that it did not open, or for a quotation to leave unclosed

    any lambdas it opened. For instance, supposing "rep" repeats a procedure

    so many times, one might want to use this to count to ten:

      0 x\               (initialize x to zero)

      [x put             (print current value of x)

       x 1 + \x x\]      (increment x)

      10 rep             (do that 10 times)

    This program is bad. It is invalid because the quotation attempts to

    close the scope of "x" when it did not open it. The program could be

    rewritten in a proper way as:

      0                    (put zero on the stack)

      [x\ x put x 1 + \x]  (print the top item on the stack and increment it)

      10 rep               (do that ten times)

    This time, the program leaves the current number on the stack, instead

    of trying to keep it stored in a variable.

    The closing "\x" would probably be considered optional; all lambdas

    introduced in a quotation would probably be considered to be implicitly

    closed at the end. Anyway, that program could be written without lambdas as:

      0

      [dup put 1 +]

      10 rep

    More concise, in this case.

    By the way, you may want to know my rationale for not liking quotations

    breaking my scope rules. The reason is that it would turn lambdas into

    a nightmare; they could no longer be eliminated using combinators

    in the systematic way mentioned earlier. Also, programing would be more

    painful, because one would frequently be worrying that a program one

    runs will change the value of some important variable.

     > >A naive system would implement lambdas by keeping an environment table

    > >of names and values; it would change as things go along. Every time

    > >one used a lambda, a new item would be added to the table; it would

    > >be removed when the lambda's scope ended.

    >

    > This would, of course, be a new concept for the language, something I would

    > be loathe to introduce without completely changing the meaning of the

    > language.

     Well, I agree that adding lambdas would be a significant change

    to the language. However, the idea of a table with names and values

    is not entirely new in Joy; it already uses a form of it in

    implementing its "==". It must keep a table of things that have been

    defined and what they have been defined to.

     > Forth uses this, by the way.  It's a good speed optimization, but it means

    > that some words have effects aside from the stack, and that isn't very

    > Joylike.

     In a sense, this is true. However, as I mentioned just above, variables

    could not be used as a means of passing parameters around. That would

    still have to happen through the stack. For instance, in a mythical

    system that implements lambdas as I'm thinking of them, if I type in

      [0] x\ some x thing x other x

    then I can be sure that "some", "thing", and "other" will not tamper

    with the "x" variable. It will be guaranteed to contain "0" when it

    is used all three times. In fact, the system could have "beta-reduced"

    the program to:

      some 0 thing 0 other 0

    but this technique is kind of like inlining, so you probably wouldn't

    like it :-)

     > I would consider this a more Joy-like solution, but it isn't simple; it

    > requires some parsing.  Fortunately, aside from the parsing, the basic

    > algorithm is simple (using my notation; yours cannot be expressed in Joy):

    >

    > x\[anything x else x something]

     First let me get straight what this means in your notation...

    This is a program that takes a item off the stack (call it "x")

    and then does "anything", and then pushes "x" back on the stack,

    and then does "else", and then pushes another copy of "x" on the stack,

    and then does "something". Is that right?

     > -->

    >

    > [anything] dup dip [else] dip something

     This doesn't seem to work. A copy of "anything" gets made,

    which I don't think is intended. Maybe you meant:

      [anything] dip dup [else] dip something

     > In other words, for a single lambda, find all of the occurances and quote

    > between them.  Replace every occurance except for the last one with "dup

    > dip"; replace the last one with "dip", and unquote the sequence following

    > the last occurrence.

     Something must be wrong with this, because it didn't work on the example.

    Maybe if you just use "dip dup" it will always work...

    I'm not sure... Anyway, this technique doesn't take into the account

    the possibility that "x" may not be used at all; one would then have

    to use "drop", I suppose. Also, it doesn't take into account the

    possibility that "x" may be used within a quotation, such as in this case:

      x\[anything [else x some] thing]

    One would need to use "cons" in that case, I think...

    By the way, the lambda construct you've defined, if I understand,

    does not perform dequotation. Thus, it alone is not powerful enough

    to construct things like "i", "dip", "cons", and "concat" (although

    it could be used to construct "dup", "drop", "swap", and such);

    however, if you supplement your lambda construct with "i", you can

    construct all those things:

      dup    == x\[x x]

      drop   == x\[]

      swap   == x\[y\[x y]]

      dip    == x\y\[x i y]

      cons   == x\y\[y x i]

      concat == x\y\[y i x i]

    The fact that your lambda construct requires "i" to be complete suggests

    to me that something is wrong with it.

     > Repeat this algorithm every time you reach a lambda

    > (lambdas must be lexically nested; every lambda must be completely contained

    > by any lambda containing any part of it).

     I could see how you might want that... It seems to be a syntactic necessity,

    by the way you use "[" and "]" to indicate the scope of a lambda.

     > I'd like to build a language which inherited its basic ideas, including a

    > simple VM, from Forth; concatenative refinements from Joy (meaning, of

    > course, the papers on the Joy website); and a parsing engine like Rebol's.

    > Oh, I'd also like [...]

     Sounds like a good plan!

     > Speaking of GC, check out ftp://ftp.netcom.com/pub/hb/hbaker/home.html;

    > there you'll find columns on Forth, garbage collection, and a number of

    > other interesting topics.  I especially enjoyed the ForthStack, ReverseGC,

    > and ThermoGC papers.

     Yeah... I've read ForthStack and ReverseGC... they were interesting.

     > You do claim that lambda is a generalization of all combinators.  However,

    > you can see from my simple algorithm above that lambda is completely

    > described by quotation, dip, dup, and drop;

     Throw in "cons" and you're okay...

     > therefore, those elements are

    > truly the source of its combinatorial generality.

     It is true... You could look at it that way, that "dup", "drop",

    "dip", and "cons" are really the primitive things. Or, alternatively,

    you could argue that the real primitive things are "sip", "cat", and "unit",

    along with "drop":

      [y] [x] sip    ==   [y] x [y]

      [y] [x] cat    ==   [y x]

          [x] unit   ==   [[x]]

          [x] drop   ==

    These primitives, after all, form just as complete a base, as evidenced by:

      dup  == [] sip

      cons == [drop unit] sip cat

      dip  == [drop [drop]] sip cat sip

    That's a fun thing about combinators; they can all be constructed

    in terms of each other, so it's arbitrary to say which are really

    more primitive.

    However, lambdas can be used to construct all combinators; therefore,

    lambda is really the ultimate primitive.

    Okay, just kidding :-)

     > >Hmm... my view is that lambda is a generalization of a

    > >definition construct.

    > >Definition is a special case of lambda in which the thing-to-be-defined

    > >is statically known (has justed been pushed on the stack as a literal).

    >

    > Here's the place I was thinking about when I mentioned that you provided

    > evidence that your lambda was a generalization of a definition.  I see your

    > point.

    >

    > However, I don't see this as a generalization of definition, but rather as a

    > use of what we called "slots" (AKA constants) or of parsing, together with

    > definition.

     Maybe it is possible to look at it that way... I don't really understand

    how Forth constants or slots work, though...

     > >in a way, it is simpler even than Joy, as it

    > >would require only one essential construct, whereas Joy requires

    > >two (concatenation and quotation).

    >

    > We've spent a lot of time arguing over that, and it's amazing that after all

    > that volume of text neither one of us has budged an inch.  Especially

    > considering how after our debates, you added an entire additional LANGUAGE

    > onto your purely applicative system in order to handle actually performing

    > actions.

    >

    > Your language requires the same number of constructs as concatenative

    > languages require, and when you're finished, you still don't have the

    > ability to run anything; you can only make mathematical statements which may

    > or may not be decidable.

    >

    > Joy requires concatenation and quotation; your language requires application

    > and grouping.

     I still have no idea where this grouping construct is coming from :-)

    There is no grouping construct. But I'm not really going to defend

    that purely applicative system now. A Joy-like system (concatenative with

    quotation) seems better to me now, despite the fact that it is slightly

    more complex syntactically.

     > >Yeah... FORTH really sounds interesting. Sometime I'm going to dig in

    > >and learn it, maybe with that book you recommended (Leo Brodie's

    > >"Thinking Forth", it was, I think).

    >

    > Starting Forth is a great starter; Thinking Forth is more philosophical.

     Oh... Hmm... I think "Starting Forth" is out-of-print, though...

     > >If I understand, FORTH's major weakness is that one cannot manipulate

    > >programs at runtime; one cannot push them onto the stack, and execute

    > >them, and "cons" them (But, I could be mistaken, I guess; perhaps some

    > >FORTH systems have ways of dynamically dealing with programs).

    >

    > Although this is a true statement, it's not Forth's greatest weakness;

    > [...]

    >

    > >Even in C, one could manipulate function pointers and call

    > >through them, although "cons"ing is not allowed.

    >

    > Of course, you can also do that in Forth; consing is trivial, using the word

    > "compile,", and execution tokens may be manipulated as easily as integers.

     Hmm. I'm confused. Here's my question: in Forth, is it possible to pass

    around pointers to a real ready-to-run program (like one can in C)?

    If so, then, out of curiousity, what is the syntax for it? For instance,

    if I have a program "foo" defined as

      : foo dup * ;

    then how do I push a function-pointer to "foo" onto the stack? And then,

    how would I call through such a pointer? In Joy, it'd be easy;

    you'd just do "[foo]" and then use "i" to call (except that then it

    would not be implemented using function pointers).

     > >Also, Joy-like quotations could be used to unify FORTH's relatively

    > >disunified control constructs... FORTH systems have several keywords

    > >(ELSE, THEN, NEXT, and probably others) that act only to

    > >delimit programs;

    > >These could all be eliminated, "[" and "]" playing their role, if

    > >one modified "IF" and "FOR" to look on the stack for programs to

    > >branch on or iterate.

    >

    > I've always thought that would be cool.  At the same time, though, the way

    > Forth does it is very efficient and exactly as flexible, and Forth's words

    > aren't as disunified as they might appear at first glance.  Those words

    > which you claim exist only to delimit programs do not in fact have any

    > delimitation action; their action is to do things like compile and resolve

    > jumps.

     I guess that's true. I had thought that a FORTH compiler, when it saw

    an "IF", would scan through and look for the "ELSE" or "THEN", and then

    recursively compile the segments after them (and then resolve the jumps),

    but it looks like that's not the case.

     > It turns out that all of Forth's conditional words can be used

    > together interchangably to create some facinating control structures.

     This reminded me of an interesting thing I saw while looking through

    some FORTH code... it appears that within a "DO" loop that one can

    refer to the index as "i". I thought it was interesting that FORTH

    does it that way; it uses a named variable instead of keeping the

    index explicitly on the stack. I wonder what would happen if one

    needed a nested loop ... would the system automatically use "j" for the

    inner loop, or would it use "i", and the coder would have to have

    explicitly pushed the outer "i" on the stack before, if it needed it ... ?

     > >Perhaps sometime

    > >I'll start working on such a project. But it's quite a formidable task

    > >to me, as I have basically no experience with making compilers.

    >

    > There's not as much to worry about as you might expect.

    >

    > Do not try to make a compiler, for that is impossible.  Instead, realize the

    > truth: there is no compiler.

     Okay :-)

     > There is only a word-by-word recogniser with

    > two states.  If the state is "interpreting", execute the meaning of each

    > word as you reach it.  If the state is "compiling", and the meaning of the

    > word is tagged as "immediate", execute the meaning of the word; otherwise

    > append a call to the word into the current definition.

     I suppose control words like "IF", "ELSE", "THEN", and "LOOP" are

    tagged "immediate", whereas most others are not...

    But then, you'd have the silly problem of FORTH systems that you can't

    use control constructs unless you're in compiling mode (unless the control

    words somehow used a separate stack from the others). I'm not

    sure I really like this interpreting-mode/compiling-mode paradigm.

     > Now, define a word named ":" which parses one word out of the input stream,

    > starts a new definition with that name, and sets the state to "compiling".

    > Define another word called ";" which is tagged as immediate, whose action is

    > to compile an EXIT and then set the state to "interpreting".

    >

    > You're done.

     Except that I then have to go back and actually implement all the words :-)

     > Making this system write executables to the disk is best done through a

    > process called "target compiling".  We could discuss that, but it'd be

    > easier for you to learn Forth first, and see how they do it;

     Whoa... hold on. So you're suggesting I only compile into memory...

    I suppose that could work, and would avoid the need to hassle with ELF...

    Perhaps within that interactive system then I'd write a compiler that

    could compile to ELF or other things. Then, if all goes well, the

    system would be rewritten in itself and compiled with the compiler.

     > >- Brent Kerby ("iepos")

    >

    > BTW, should I refer to you as Brent or iepos?

     Either one is fine with me...

     > And, just as an amusing sidelight, I keep mispronouncing your nick

    > as "yay-ross", since the p reminds me of the Greek rho and the

    > spelling and word shape is otherwise similar to Greek.

     Well. Greek is Greek to me. I would probably pronounce the name "eep-oze".

     > -Billy

     I've noticed one interesting things about these posts...

    This is my third message on this topic, and each message

    has approximately doubled in size. We're going to have to start

    clipping soon :-)

    - Brent Kerby ("iepos")

## wtanksley@bigfoot.com — 2000-05-06 02:45:26

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

     >> >Hmm... Does that make sense now?

    >> No.  I mean, it makes your example clear, but it lacks a

    >> lot: first, it

    >> lacks delimitation (you had to invent a funky chunk of

    >> syntax to make it

    >> make sense); second, it lacks consistency;

    >These do not make sense to me. To me, the extension seems fairly clear

    >and consistent; it does not really add any funky syntax. Programs are

    >still constructed from words with just concatenation and quotation. All

    >I'm adding are schemes of words: "x\", "y\", "foo\", "x", "y",

    >"foo", etc.

     You're also adding the convention that quotation behaves specially when

    you're quoting a single lambda-defined word, and that mentioning a lambda

    variable without a single surrounding quote attempts to unquote the contents

    of the variable.  You're also forgetting to list \x (as opposed to x\).

     >> and third, it lacks reliability

    >> (why should a defined word cause an error?).

    >This is not unique to my extension. You complain that I can

    >get an error by doing something like this:

    >  2 x\ x

    >When it comes time to run "x", there is an error because it is not a

    >program, but a number. But, one can get a similar error in normal Joy

    >with this program:

    >  2 i

    >This causes an error because the number two on the stack is

    >not a program:

    >  run time error: quotation as top parameter needed for i

     This is true, but the entity doing the complaining is clearly identifiable:

    it's "i".  Specifically, you're passing in data of the wrong type.  (It's

    always a runtime error on Joy, but it could be changed to a compile-time

    error, as we've discussed.)

    The point is that everything in Joy has meaning in and of itself.  Your

    lambdas only have meaning when they're inside a quotation, and there they

    must be the only thing inside that quotation.  It's a pretty strange

    convention, isn't it?

     >> >For instance, here's a case where you might want a lambda:

    >> >[...]

    >> The Forth way to do this is to create a constant (although

    >> variables would

    >> also be possible).  I do agree that definitions are not

    >> general enough to handle this;

    >It may be that Forth's "constant" feature is an alternative way to

    >deal with this, as you say ...

     It should work the same, although Forth constants lack lexical behavior.

    (But then Forth doesn't have any concept of scoping, so there's no real

    surprise.)

     >By the way, it should not be construed that lambdas are like global

    >variables, and that one could just modify its value (using the top

    >item on the stack) by closing its scope with "\x" and opening again

    >with "x\". This technique would be okay in some situations;

    >however, I would consider it unacceptable for a quotation to close

    >any lambdas that it did not open, or for a quotation to leave unclosed

    >any lambdas it opened.

     Same here.  In fact, I would consider it an error.

     >The closing "\x" would probably be considered optional; all lambdas

    >introduced in a quotation would probably be considered to be implicitly

    >closed at the end.

     Good point.  Although, as you saw, I wouldn't use lambdas in the same way

    you are.

     >By the way, you may want to know my rationale for not liking quotations

    >breaking my scope rules. The reason is that it would turn lambdas into

    >a nightmare; they could no longer be eliminated using combinators

    >in the systematic way mentioned earlier. Also, programing would be more

    >painful, because one would frequently be worrying that a program one

    >runs will change the value of some important variable.

     This last is an issue simply with lambdas in general.  It's why lambdas are

    bad.

     >is used all three times. In fact, the system could have "beta-reduced"

    >the program to:

    >  some 0 thing 0 other 0

    >but this technique is kind of like inlining, so you probably wouldn't

    >like it :-)

     I hate it already.  ;-)  No I don't; it's fine.

    There is a problem with it, aside from the problems SICP mentions with that

    simplistic model of function-calling.  Specifically, how many times does it

    get evaluated?  Will it get evaluated exactly once, or will it get evaluated

    once every time its variable appears, or will it get evaluated at most once?

    And when does that evaluation occur?

    You'll have to make an arbitrary decision in order to answer these

    questions, and it'll have to go into a FAQ.  All for a question which never

    before needed to be asked.

     >> I would consider this a more Joy-like solution, but it isn't

    >> simple; it

    >> requires some parsing.  Fortunately, aside from the parsing,

    >> the basic

    >> algorithm is simple (using my notation; yours cannot be

    >> expressed in Joy):

    >> x\[anything x else x something]

    >First let me get straight what this means in your notation...

    >This is a program that takes a item off the stack (call it "x")

    >and then does "anything", and then pushes "x" back on the stack,

    >and then does "else", and then pushes another copy of "x" on the stack,

    >and then does "something". Is that right?

     Yes.

     >> -->

    >  [anything] dip dup [else] dip something

     (Yes, that's correct.)

     >> In other words, for a single lambda, find all of the

    >> occurances and quote

    >> between them.  Replace every occurance except for the last

    >> one with "dup

    >> dip"; replace the last one with "dip", and unquote the

    >> sequence following

    >> the last occurrence.

    >Something must be wrong with this, because it didn't work on

    >the example.

    >Maybe if you just use "dip dup" it will always work...

     Yes.

     >I'm not sure... Anyway, this technique doesn't take into the account

    >the possibility that "x" may not be used at all; one would then have

    >to use "drop", I suppose.

     Oh, you're right.  Boundary case.

     >Also, it doesn't take into account the

    >possibility that "x" may be used within a quotation, such as

    >in this case:

    >  x\[anything [else x some] thing]

    >One would need to use "cons" in that case, I think...

     True.  Good point.  So that algorithm sucked really bad.  Textual

    replacement sucks a lot less, I think.

     >By the way, the lambda construct you've defined, if I understand,

    >does not perform dequotation.

     That's correct.  Nor does it perform printing, arithmetic, or exotic dances.

    Strangely, I seem to be happy with that.

    Specifically, my construct does not attempt to change data it's given.  It

    accepts the data, and then places the data where indicated.  Yours does

    attempt to change the data, and it's not clear why you would choose to do

    so, or having chosen to do so you'd see unquoting as any better than any

    other transformation (such as length or something similar).

     >Thus, it alone is not powerful enough

    >to construct things like "i", "dip", "cons", and "concat" (although

    >it could be used to construct "dup", "drop", "swap", and such);

    >however, if you supplement your lambda construct with "i", you can

    >construct all those things:

    >  dup    == x\[x x]

    >  drop   == x\[]

    >  swap   == x\[y\[x y]]

    >  dip    == x\y\[x i y]

    >  cons   == x\y\[y x i]

    >  concat == x\y\[y i x i]

    >The fact that your lambda construct requires "i" to be

    >complete suggests to me that something is wrong with it.

     I'm not sure how it suggests that.  The fact that your lambda construct

    requires a major change in the behavior of quotation and parsing would seem

    to suggest something stronger.

     >> Repeat this algorithm every time you reach a lambda

    >> (lambdas must be lexically nested; every lambda must be

    >> completely contained

    >> by any lambda containing any part of it).

    >I could see how you might want that... It seems to be a

    >syntactic necessity,

    >by the way you use "[" and "]" to indicate the scope of a lambda.

     Well, I was saying that about the algorithm, not the syntax.  It's true that

    my syntax makes that requirement as well.  But then my algorithm doesn't

    work, so who cares?

     >Maybe it is possible to look at it that way... I don't really

    >understand how Forth constants or slots work, though...

     I believe you're the one who first brought up the idea of slots.  At first I

    didn't like the idea of adding variables to Joy, but you pointed out that

    for multithreading, they'd be needed.

    Forth constants are just definitions which take their value from a stack

    item.  They wouldn't fit into Joy.

     >> >in a way, it is simpler even than Joy, as it

    >> >would require only one essential construct, whereas Joy requires

    >> >two (concatenation and quotation).

    >> We've spent a lot of time arguing over that, and it's

    >> amazing that after all

    >> that volume of text neither one of us has budged an inch.  Especially

    >> considering how after our debates, you added an entire

    >> additional LANGUAGE

    >> onto your purely applicative system in order to handle

    >> actually performing actions.

    >> Your language requires the same number of constructs as concatenative

    >> languages require, and when you're finished, you still don't have the

    >> ability to run anything; you can only make mathematical

    >> statements which may or may not be decidable.

    >> Joy requires concatenation and quotation; your language

    >> requires application and grouping.

    >I still have no idea where this grouping construct is coming from :-)

    >There is no grouping construct.

     Read all of our emails.  There's actually a whole list of "constructs" which

    both languages require; there's nothing magically simple about either one

    compared to the other.  The only real difference is that this purely

    applicative language requires a parser to go ever the entire input file

    before executing any of it, while a purely concatenative language doesn't.

    It's that simple.

     >But I'm not really going to defend

    >that purely applicative system now. A Joy-like system

    >(concatenative with

    >quotation) seems better to me now, despite the fact that it is slightly

    >more complex syntactically.

     The really strange thing about this statement is that a a concatenative

    system has NO syntax.  When you consider that an applicative system HAS

    syntax, you have to wonder where statements like that come from.  How could

    no syntax be more syntactically complex than some syntax?

     >> >Yeah... FORTH really sounds interesting. Sometime I'm going

    >> >to dig in

    >> >and learn it, maybe with that book you recommended (Leo Brodie's

    >> >"Thinking Forth", it was, I think).

    >> Starting Forth is a great starter; Thinking Forth is more

    >> philosophical.

    >Oh... Hmm... I think "Starting Forth" is out-of-print, though...

     Both are, but you can get copies from several places.  Ask in

    comp.lang.forth (sorry, not gonna sell mine :-).

     >> >Even in C, one could manipulate function pointers and call

    >> >through them, although "cons"ing is not allowed.

    >> Of course, you can also do that in Forth; consing is

    >> trivial, using the word

    >> "compile,", and execution tokens may be manipulated as

    >> easily as integers.

    >Hmm. I'm confused. Here's my question: in Forth, is it possible to pass

    >around pointers to a real ready-to-run program (like one can in C)?

    >If so, then, out of curiousity, what is the syntax for it? For

    >instance, if I have a program "foo" defined as

    >  : foo dup * ;

    >then how do I push a function-pointer to "foo" onto the stack?

     "'" (pronounced "tick") returns the execution token of the word following it

    in the source.  Note that tick is not immediate, so if you want it to take

    effect immediately you have to use the immediate version "[']".  (This is an

    ANSI innovation; in the original Forth ' was immediate.)

     >And then, how would I call through such a pointer?

     EXECUTE would call the pointer; COMPILE, would compile it.

     >In Joy, it'd be easy;

    >you'd just do "[foo]" and then use "i" to call (except that then it

    >would not be implemented using function pointers).

     No, that wouldn't give you a function pointer; it would give you a

    quotation, with all the strengths and weaknesses thereof -- but "[foo]

    first" would.  The problem is that function pointers aren't documented as

    part of Joy.

     >> >Also, Joy-like quotations could be used to unify FORTH's relatively

    >> >disunified control constructs... FORTH systems have several keywords

    >> >(ELSE, THEN, NEXT, and probably others) that act only to

    >> >delimit programs;

    >> >These could all be eliminated, "[" and "]" playing their role, if

    >> >one modified "IF" and "FOR" to look on the stack for programs to

    >> >branch on or iterate.

    >> I've always thought that would be cool.  At the same time,

    >> though, the way

    >> Forth does it is very efficient and exactly as flexible, and

    >> Forth's words

    >> aren't as disunified as they might appear at first glance.

    >> Those words

    >> which you claim exist only to delimit programs do not in

    >> fact have any

    >> delimitation action; their action is to do things like

    >> compile and resolve jumps.

    >I guess that's true. I had thought that a FORTH compiler, when it saw

    >an "IF", would scan through and look for the "ELSE" or "THEN", and then

    >recursively compile the segments after them (and then resolve

    >the jumps), but it looks like that's not the case.

     Right.  It would be a pretty scary way of solving the problem.  :-)  This

    way you can define your own contitional words.

     >This reminded me of an interesting thing I saw while looking through

    >some FORTH code... it appears that within a "DO" loop that one can

    >refer to the index as "i". I thought it was interesting that FORTH

    >does it that way; it uses a named variable instead of keeping the

    >index explicitly on the stack.

     Actually, that's not a named variable; it's a procedure whose action differs

    from system to system, but one common action for "i" is to fetch the top

    item on the return stack.

    There's no way to "keep" the index on the data stack; the user could move it

    off at any time, and in fact would _have_ to in order to get anything done.

    It's easy to keep the count on the return stack, though.

     >I wonder what would happen if one

    >needed a nested loop ... would the system automatically use "j" for the

    >inner loop, or would it use "i", and the coder would have to have

    >explicitly pushed the outer "i" on the stack before, if it

    >needed it ... ?

     The innermost loop is always i; the next outer loop is j.  Both are

    procedures, not variables, although neither one has a defined meaning

    outside of a loop or after anyone's done anything to the return stack.

     >> There is only a word-by-word recogniser with

    >> two states.  If the state is "interpreting", execute the

    >> meaning of each

    >> word as you reach it.  If the state is "compiling", and the

    >> meaning of the

    >> word is tagged as "immediate", execute the meaning of the

    >> word; otherwise

    >> append a call to the word into the current definition.

    >I suppose control words like "IF", "ELSE", "THEN", and "LOOP" are

    >tagged "immediate", whereas most others are not...

     Exactly.  Good.

     >But then, you'd have the silly problem of FORTH systems that you can't

    >use control constructs unless you're in compiling mode (unless

    >the control

    >words somehow used a separate stack from the others). I'm not

    >sure I really like this interpreting-mode/compiling-mode paradigm.

     Also exactly correct.

    There's also a simple solution to this one -- always operate in compilation

    mode, and execute a chunk of code when the compilation stack goes to zero.

    Don't worry about that right now, though.

    Keep things simple for starters, and make them complicated if you need to

    AFTER they work in their simple form.  It turns out that it's no great pain

    to declare "thou shalt not use these words in interactive mode," because

    it's so easy to make and use a definition whenever you need to use them.

    Instead of:

      start-timer 100 for my-word next end-timer

    you can just write:

    :NONAME start-timer 100 for my-word next end-timer ; EXECUTE

     >> Making this system write executables to the disk is best

    >> done through a

    >> process called "target compiling".  We could discuss that,

    >> but it'd be

    >> easier for you to learn Forth first, and see how they do it;

    >Whoa... hold on. So you're suggesting I only compile into memory...

     Yup.  In other words, solve one problem at a time.  First solve parsing (by

    defining the language such that it's not needed), then solve dictionary

    lookup (in Forth's case, a very simple static linked list), then solve

    interactivity (again simple), then code generation (always emit CALLs

    directly to the words).  And so on.  At every step after this you have a

    working system.

     >I suppose that could work, and would avoid the need to hassle

    >with ELF...

     Until later.  And then you can implement it as cleverly as you need to.

     >I've noticed one interesting things about these posts...

    >This is my third message on this topic, and each message

    >has approximately doubled in size. We're going to have to start

    >clipping soon :-)

     I have a real tendancy to do that.

     >- Brent Kerby ("iepos")

     -Billy

## iepos@tunes.org — 2000-05-12 19:58:13

    > >These do not make sense to me. To me, the extension seems fairly clear

    > >and consistent; it does not really add any funky syntax. Programs are

    > >still constructed from words with just concatenation and quotation. All

    > >I'm adding are schemes of words: "x\", "y\", "foo\", "x", "y",

    > >"foo", etc.

    >

    > You're also adding the convention that quotation behaves specially when

    > you're quoting a single lambda-defined word, and that mentioning a lambda

    > variable without a single surrounding quote attempts to unquote the contents

    > of the variable.

     Yes, true.

     > You're also forgetting to list \x (as opposed to x\).

     Oops, yes. Although "\x" is in a way not essential.

     > The point is that everything in Joy has meaning in and of itself.  Your

    > lambdas only have meaning when they're inside a quotation, and there they

    > must be the only thing inside that quotation.  It's a pretty strange

    > convention, isn't it?

     I don't understand your complaint. Everything makes sense when you

    interpret

      "x\"   as: pop the top item off the stack and call it "x".

      "[foo] as: push "foo" onto the stack.

    It then makes perfect sense that "x\ x" has an unquoting effect.

    Read it as,

      Pop the top item off the stack and call it 'x'.

      Then, do 'x'.

    On the other hand, if I had done "x\ [x]", it would make perfect sense

    (well, other than that it's an program that does nothing). Read it as:

      Pop the top item off the stack and call it 'x'.

      Then, push 'x' back onto the stack.

     > >By the way, you may want to know my rationale for not liking quotations

    > >breaking my scope rules. The reason is that it would turn lambdas into

    > >a nightmare; they could no longer be eliminated using combinators

    > >in the systematic way mentioned earlier. Also, programing would be more

    > >painful, because one would frequently be worrying that a program one

    > >runs will change the value of some important variable.

    >

    > This last is an issue simply with lambdas in general.  It's why lambdas are

    > bad.

     True, although the scoping rules minimize the effect. My main reason

    for not liking lambdas is that they are cluttery; it is often more

    concise to use some combinators.

    However, I suspect that there are _some_ situations where lambdas

    would be appropriate. Well. Hmm.. surely there must be some,

    somewhere. Okay. dare me to come up with a specific example :-)

     > >  [0] x\ some x thing x other x

    > >

    > >In fact, the system could have "beta-reduced" the program to:

    > >

    > >  some 0 thing 0 other 0

    >

    > There is a problem with it, aside from the problems SICP mentions with that

    > simplistic model of function-calling.  Specifically, how many times does it

    > get evaluated?  Will it get evaluated exactly once, or will it get evaluated

    > once every time its variable appears, or will it get evaluated at most once?

    > And when does that evaluation occur?

     Well, it doesn't really matter, since "0" is just a literal, with no

    side effects. Okay, so let's suppose that it was instead

      [0 dup .] x\ some x thing x other x

    (where "." means, print the top item on the stack, like in FORTH).

    This would be beta-reduced, as before, to

      some 0 dup . thing 0 dup . other 0 dup .

    Well, the "0 dup ." will get evaluated three times. That is what the user

    asked for in the original program, and that is clearly what will happen

    with the beta-reduced version. If the user had not wanted it to be

    evaluated three times he would have done

      0 dup . x\ some [x] thing [x] other [x]

    or perhaps

      0 dup . unit x\ some x thing x other x

    or with combinators:

      0 dup . [some] dip [thing] sip [other] sip

     > You'll have to make an arbitrary decision in order to answer these

    > questions, and it'll have to go into a FAQ.  All for a question which never

    > before needed to be asked.

     This does not make any sense. I do not see the need for any arbitrary

    decisions.

     > >By the way, the lambda construct you've defined, if I understand,

    > >does not perform dequotation.

    >

    > That's correct.  Nor does it perform printing, arithmetic, or exotic dances.

    > Strangely, I seem to be happy with that.

    >

    > Specifically, my construct does not attempt to change data it's given.  It

    > accepts the data, and then places the data where indicated.  Yours does

    > attempt to change the data, and it's not clear why you would choose to do

    > so, or having chosen to do so you'd see unquoting as any better than any

    > other transformation (such as length or something similar).

     Because unquoting is a very *SPECIAL* operation, similar to

    duplication, reordering, dropping.

    Basically, give me my lambda construct, and we have Turing-completeness

    (I think). Give me yours, and, well, we don't.

    Here's a challenge: use my lambda construct to construct a loop that

    runs "foo" over and over again.

    Impossible? Nope:

      [x\ foo [x] x] z\ [z] z

    This is the same as:

      [[foo] dip dup call] dup call

     > Forth constants are just definitions which take their value from a stack

    > item.  They wouldn't fit into Joy.

     Oh, well it sounds like Forth constants are very similar to my lambda

    construct ... except that they probably can't be executed within

    loops and such things, can they?

     > Read all of our emails.  There's actually a whole list of "constructs" which

    > both languages require; there's nothing magically simple about either one

    > compared to the other.  The only real difference is that this purely

    > applicative language requires a parser to go ever the entire input file

    > before executing any of it, while a purely concatenative language doesn't.

    > It's that simple.

     That is a major difference, yes.

     > >Hmm. I'm confused. Here's my question: in Forth, is it possible to pass

    > >around pointers to a real ready-to-run program (like one can in C)?

    > >If so, then, out of curiousity, what is the syntax for it? For

    > >instance, if I have a program "foo" defined as

    >

    > >  : foo dup * ;

    >

    > >then how do I push a function-pointer to "foo" onto the stack?

    >

    > "'" (pronounced "tick") returns the execution token of the word following it

    > in the source.  Note that tick is not immediate, so if you want it to take

    > effect immediately you have to use the immediate version "[']".  (This is an

    > ANSI innovation; in the original Forth ' was immediate.)

     Okay.

     > >And then, how would I call through such a pointer?

    >

    > EXECUTE would call the pointer; COMPILE, would compile it.

     All right... and EXECUTE and COMPILE are not immediate either, right?

    That is, you could run them at runtime and they would take the function

    pointers off the real data stack, not off the compile stack, right?

     > >In Joy, it'd be easy;

    > >you'd just do "[foo]" and then use "i" to call (except that then it

    > >would not be implemented using function pointers).

    >

    > No, that wouldn't give you a function pointer; it would give you a

    > quotation, with all the strengths and weaknesses thereof --

     Well, in my Joy-like system, doing "[foo]" pushes a 32-bit function

    pointer onto the stack, and "call" calls it.

     > but "[foo] first" would.  The problem is that function pointers aren't

    > documented as part of Joy.

     Yes, this is interesting. Hopefully a revision of my system will

    have something like "first"; if it is used on a quotation, then the

    thing result will be a "execution token". An execution token would

    probably be implemented as a pair of 32-bit ints; the first would

    be the type of the word (maybe 0 for "call", 1 for "dip", 2 for "cons",

    etc., and then others to signal int literals, string literals, and

    program literals), while the second would be optional, used only

    in cases of literals, to tell the actual literal value.

     > > I wonder what would happen if one needed a nested loop

    > > [...]

    >

    > The innermost loop is always i; the next outer loop is j.

    > [...]

     Thanks for the explanation...

     > >But then, you'd have the silly problem of FORTH systems that you can't

    > >use control constructs unless you're in compiling mode (unless

    > >the control

    > >words somehow used a separate stack from the others). I'm not

    > >sure I really like this interpreting-mode/compiling-mode paradigm.

    >

    > Also exactly correct.

    >

    > There's also a simple solution to this one -- always operate in compilation

    > mode, and execute a chunk of code when the compilation stack goes to zero.

    > Don't worry about that right now, though.

     Right. That would be a good solution.

    - "iepos" (Brent Kerby)

## wtanksley@bigfoot.com — 2000-05-12 20:26:33

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

     >> >These do not make sense to me. To me, the extension seems

    >> >fairly clear

    >> >and consistent; it does not really add any funky syntax.

    >> >Programs are

    >> >still constructed from words with just concatenation and

    >> >quotation. All

    >> >I'm adding are schemes of words: "x\", "y\", "foo\", "x", "y",

    >> >"foo", etc.

    >> The point is that everything in Joy has meaning in and of

    >> itself.  Your

    >> lambdas only have meaning when they're inside a quotation,

    >> and there they

    >> must be the only thing inside that quotation.  It's a pretty strange

    >> convention, isn't it?

    >I don't understand your complaint. Everything makes sense when you

    >interpret

    >  "x\"   as: pop the top item off the stack and call it "x".

    >  "[foo] as: push "foo" onto the stack.

     So would you say that "[2]" means "push 2 on the stack?"

     >It then makes perfect sense that "x\ x" has an unquoting effect.

    >Read it as,

    >  Pop the top item off the stack and call it 'x'.

    >  Then, do 'x'.

    >On the other hand, if I had done "x\ [x]", it would make perfect sense

    >(well, other than that it's an program that does nothing). Read it as:

    >  Pop the top item off the stack and call it 'x'.

    >  Then, push 'x' back onto the stack.

     _Everywhere_ else in Joy, [x] means "push [x] on the stack", no matter what

    x is.  Why should this be changed?

     >> >By the way, you may want to know my rationale for not

    >> >liking quotations

    >> >breaking my scope rules. The reason is that it would turn

    >> >lambdas into

    >> >a nightmare; they could no longer be eliminated using combinators

    >> >in the systematic way mentioned earlier. Also, programing

    >> >would be more

    >> >painful, because one would frequently be worrying that a program one

    >> >runs will change the value of some important variable.

    >>

    >> This last is an issue simply with lambdas in general.  It's

    >> why lambdas are bad.

    >True, although the scoping rules minimize the effect.

     Read SICP.  They discuss this effect in some detail.

     >My main reason

    >for not liking lambdas is that they are cluttery; it is often more

    >concise to use some combinators.

    >However, I suspect that there are _some_ situations where lambdas

    >would be appropriate. Well. Hmm.. surely there must be some,

    >somewhere. Okay. dare me to come up with a specific example :-)

     I actually have seen times where "local variables", Forth's closest approach

    to lambdas, were used effectively.  Never mind that every single time it

    would have been better to rewrite the code without them; the problem was

    that the programmer was a C programmer and wasn't Thinking Forth.  Sometimes

    that's appropriate.

    I don't want to design my language to be used by people with that problem,

    though.

     >> There is a problem with it, aside from the problems SICP

    >> mentions with that

    >> simplistic model of function-calling.  Specifically, how

    >> many times does it

    >> get evaluated?  Will it get evaluated exactly once, or will

    >> it get evaluated

    >> once every time its variable appears, or will it get

    >> evaluated at most once?

    >> And when does that evaluation occur?

    >If the user had not wanted it to be

    >evaluated three times he would have done

    >  0 dup . x\ some [x] thing [x] other [x]

     Ah.  So the problem is only solved by contradicting Joy's quotation syntax.

     >> >By the way, the lambda construct you've defined, if I understand,

    >> >does not perform dequotation.

    >> That's correct.  Nor does it perform printing, arithmetic,

    >> or exotic dances. Strangely, I seem to be happy with that.

    >> Specifically, my construct does not attempt to change data

    >> it's given.  It

    >> accepts the data, and then places the data where indicated.

    >> Yours does

    >> attempt to change the data, and it's not clear why you would

    >> choose to do

    >> so, or having chosen to do so you'd see unquoting as any

    >> better than any

    >> other transformation (such as length or something similar).

    >Because unquoting is a very *SPECIAL* operation, similar to

    >duplication, reordering, dropping.

    >Basically, give me my lambda construct, and we have Turing-completeness

    >(I think). Give me yours, and, well, we don't.

     Don't give me either construct, and we have turing completeness; it's

    already in the language.  So adding one or the other construct is just

    gilding the lily -- it's a luxury.  You're trying to treat lambda as though

    it were an independant language.  It's not; we're trying to _add_ it to Joy.

    As a result, you're winding up making huge modifications to the syntax of

    Joy in order to make this peripheral construct independant of Joy.

     >> Forth constants are just definitions which take their value

    >> from a stack item.  They wouldn't fit into Joy.

    >Oh, well it sounds like Forth constants are very similar to my lambda

    >construct ...

     Yes, as a matter of fact.  Except that they don't change the language.

    (They're more like my lambdas in that sense.)

     >except that they probably can't be executed within

    >loops and such things, can they?

     Um...  Why would you deduce that?  They can be executed anywhere.

     >> >And then, how would I call through such a pointer?

    >> EXECUTE would call the pointer; COMPILE, would compile it.

    >All right... and EXECUTE and COMPILE are not immediate either, right?

    >That is, you could run them at runtime and they would take the function

    >pointers off the real data stack, not off the compile stack, right?

     Correct.  They would have no use as immediate words; their purpose is to

    manipulate data.

    BTW, the name is "COMPILE,", pronounced compile-comma.  In Forth, "comma" is

    a suffix which by convention denotes that the word it's attached to appends

    something to the current definition.

     >> >In Joy, it'd be easy;

    >> >you'd just do "[foo]" and then use "i" to call (except that then it

    >> >would not be implemented using function pointers).

    >> No, that wouldn't give you a function pointer; it would give you a

    >> quotation, with all the strengths and weaknesses thereof --

    >Well, in my Joy-like system, doing "[foo]" pushes a 32-bit function

    >pointer onto the stack, and "call" calls it.

     In Joy it doesn't.

     >> but "[foo] first" would.  The problem is that function

    >> pointers aren't documented as part of Joy.

    >Yes, this is interesting. Hopefully a revision of my system will

    >have something like "first"; if it is used on a quotation, then the

    >thing result will be a "execution token". An execution token would

    >probably be implemented as a pair of 32-bit ints; the first would

    >be the type of the word (maybe 0 for "call", 1 for "dip", 2 for "cons",

    >etc., and then others to signal int literals, string literals, and

    >program literals), while the second would be optional, used only

    >in cases of literals, to tell the actual literal value.

     That would certainly be reasonable.  In other words, a bytecode, possibly

    like the one described by OTA's specs.  Another approach is to include

    numeric literals (31 bits plus high bit zero) and execution tokens (31 bits

    plus high bit 1).  XTs are pointers to structures which contain type

    information.

     >- "iepos" (Brent Kerby)

     -Billy