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