In the beginning there was nothing but shallow water. Then a
great crocodile appeared and began thrashing his tail. He made the
water deeper in some places. In other places he heaped up enough mud
to form the land, which was
still very damp and muddy.
         The first men had nothing to eat but frogs, which tasted like
mud, except crunchier. They build their dwellings out of what they
had: mud. When it dried it had some strength (in compression). A hut
had to be built with care, or else it would crumble.
         Gradually more and more things happened. The crocodile was
long gone, and new materials appeared, plexiglass and wood and steel.
And the men said to each other: "It is not appropriate that our
dwellings be made of mud when there better things to make them of. We
will build new hovels. Naturally, the foundations and loadbearing
walls thereof shall be of mud, but we shall hide the mud with painted
wood and polished steel, even on the
inside, which we shall reveal with plexiglass."
         This made a huge difference to the appearance of the dwellings
of men. Now they were arrayed like the lilies of the field. But they
were still made of mud where it counted. And when the men tried to
build an apartment complex or an office tower, it always collapsed.

Key

Dwelling        Software system (from OS on up)
Mud             C

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

>Hello, folks....

>Well, a bit ago I decided to follow Billy's advice and just make a
>simple interactive environment, and not worry about compilation to
>ELF and strange things for a while...
>I've come up with something half-usable and thought I'd let you guys
>know about it. It's at:
>  http://www.tunes.org/~iepos/clip-joyful-0.2.tar.gz

Wow, that was quick!  In that time I managed to fix a single bug in Omega.

>It is an interpreter for a concatenative langauge similar to Joy.
>However, it's not a normal interpreter, since it compiles to
>native x86 code at runtime.

So it's not an interpreter, then.  It's an interactive compiler which emits
native code.

>But, understand that currently it generates
>rather sorry code; it does no register allocation and often juggles
>things on the stack even when they are statically known.

This is a common problem with early compilers.  I don't think it's worrisome
:-).

A couple of points to consider:

1. Is it really worthwhile worrying about optimising juggling stack
elements?  It's something that's _easy_ for the programmer to fix, and
unneeded stack juggles make the code look terrible.  So the programmer has
good reason to want to NOT write unneeded stack juggles.

2. Register allocation is very good, but there's another option.  Why don't
you do some benchmarks, first with and then without allocation; I think you
might be suprised.  Register allocation makes code run faster, but when you
don't register allocate you only use a couple of registers, and task
switching is faster (because you only have to save and restore those
registers).

I'm working on getting my friend's register allocater.  Hopefully it'll be
useful to you.

>  % : like "/", but leaves remainder instead of quotient

It's common to name this MOD, since it's rarely used.  This way, the word
"/MOD" makes sense: it returns both the quotient and remainder.  This is
fast almost everywhere.

>I/O:
>  puts : prints top string on stack (followed by newline)
>  puti : prints top int on stack (followed by newline)

Skip the newline.  A trailing space is okay, although it gets annoying when
you don't need it.

>And, here is the confusing example program included with the tar.gz :-)

> (Count upward, beginning at 0, skipping multiples of five)
> 0 [[dup 5 % 0 = [true] [false] if [] [dup puti] if 1 +] dip
>dup call] dup call

0 [[dup 5 % 0 = [dup puti] [] if 1 +] dip dup call] dup call

?

Why did you write "[true] [false] if" in there?  That's only a NOT, and
since your input is boolean and your output simply does an IF, you can
simply reverse the clauses on the following IF.

>Another problem is that the system never attempts to free string and
>program literals, even when they are long past executed or printed for
>their last time. Of course, this might be considered minor, since it
>happens in ordinary C systems too.

Another choice here would be to retreat a bit and implement a Forth-style
dictionary, and let the programmer manage it.  A Forth-style dictionary is
managed soley by growing and shrinking; shrinking happens when you run
FORGET <word>, and growing occurs whenever you define a word or APPEND a
cell.

("Dictionary" is the wrong word; Forth uses it for a dictionary, but you
don't have to.  The important thing isn't that it's a place to store and
lookup words; the important thing is that it's a region of memory which
starts at some address and can grow or shrink.  Often the dictionary is
overallocated to make growing faster, and the spare space at the end is
called the PAD, and is used for temporary storage.)

>There's another memory-management problem that's worse. In this system,
>"cons" gives one the ability to construct dynamically-allocated
>(by malloc(), currently) programs at runtime, but they will never
>be freed; the programmer has no way to do it manually, and there is
>no automatic garbage collector either.

Grin.  That's a problem.

The solution there is the same -- don't provide CONS yet.  Instead, think of
what you'd do instead which doesn't require seperate memory management.  The
answer's pretty simple -- use APPEND.  APPEND should take one argument, and
append it to the end of the current definition (which has the effect of
enlarging the dictionary by four bytes).

Of course, there is another solution, and long-term it's what you want.  You
want full garbage collection.  It's your call, but I recommend you keep
following the path of least resistance, and make things simple now.  It's
not going to make things any harder later.

>Another problem is that the stack has a statically limited size of
>200000 bytes; this may be changed by a #define at the top of
>the .c file :-)
>Presumably, this could be fixed by somehow guaranteeing that a segfault
>occurs upon overflow and arranging things so that the segfault
>is caught and the stack extended a ways.

That's a good solution.  Another solution would be to make the stack
circular, so that there _is_ no overflow.  This would cause HUGE surprise to
anyone not expecting it ;-), but would remove a _lot_ of potential errors.

Us Forth programmers are widely known for being very wierd.  This reputation
is not without cause.

>Currently, there are no primitives for dealing with arrays, buffers,
>or things of that kind. Also, there is no support for lambdas
>or definitions.

Add the dictionary, and you'll have support for buffers, and a buffer is an
array.  Later on, you'll be able to use the dictionary as its name
indicates, to store names and addresses, which will be useful for
definitions and Billy-style lambdas.

Another thing that's useful for buffers are Forth-style "blocks".  A block
is a 1024-byte (or any other size that's convenient) array which is stored
in a set of buffers; there can be as many buffers as the system needs or
wants.  Blocks are used as follows:

1024 read ( activate block # 1024 )
3 block ! ( write whatever values you want to the current block, using
standard memory operations )
set-modified ( tag it as having changed; this is optional, but it's wise not
to lie )
293934 read ( play with another block )
( ... there are at least 10 blocks cached, and it would be wise to have a
variable which let the programmer know how many are available... )

( ...after modifying all the blocks the programmer wanted to, he can then
run )
flush
( to save all the modified blocks to disk, or )
dump-modified
( to mark all active blocks as unmodified. )

Yes, block access is used for disk access.

>I think that soon I will rewrite the whole system so that the compiler
>keeps track of information about things on the stack; it would keep
>track of the types of stack items, and their exact value, if possible;
>otherwise, it would keep track of where they are stored (possibly in
>registers, on the stack, or perhaps in a static memory location).
>Then, many operations could be implemented by just changing the
>bookkeeping, as Billy has said, without emitting any code.

Right.

>Perhaps a good technique would be to postpone compiling a quotation
>until its first caller is known;

Another effective trick, and the one I use, is to never implicitly compile a
quotation; let quotations be just that, quotations.  They don't have to
remain in text form, because that's very slow for all purposes (except
printing, which is slow anyhow); it's better to store them in wordcode form.
In other words, a quotation is an array of word addresses.

When it comes time to _use_ a quotation, you have two choices: interpret it,
or compile it and then call the result.

>then the quotation could be compiled
>to take the parameters from the most convenient storage locations,
>the one they are already in (but, future callers might have to
>move things
>around to get things into the chosen locations). This technique would
>turn out especially well if there is only one caller; this
>would actually
>be a very common situation, I think; it would happen all the time
>with branching and looping constructs, in which the program to
>branch or loop has just been pushed as a literal.

This is why Forth doesn't use quotations to implement branching and
conditionals.  I think that using quotation for that is a bad idea; it
forces the computer to do extra work, moving those blocks of code all over
the place, when almost always the programmer doesn't need that.

It's easier and faster to have your IF word compile a "CMP TopOfStack, 0 /
DROP TopOfStack / JNZ *0000000*", and then (at compile time) push the
address of the starred zero on the stack (this is called an "unresolved
jump").  Then ELSE is similar: it compiles a "JMP *00000000*", stores the
address right after the JMP into the unresolved jump IF had left on the
stack, and leaves on the stack its own unresolved jump.  THEN simply
resolves a single unresolved jump.

The primitive words here are called "?0BRANCH,", "0BRANCH,", and "BRANCH!".
So in Forth, these words look like this:

: IF   ?0BRANCH, ; IMMEDIATE
: ELSE  0BRANCH, ; IMMEDIATE
: THEN  HERE BRANCH! ; IMMEDIATE

Does this make sense?

Oh, by the way, Forth's word THEN is called ENDIF in some languages.  It's
not the same as BASIC's THEN, which is used to indicate the end of the IF
clause; in Forth, IF does that job.  Forth programmers think of THEN as
being the sequential THEN; a synonym for it would be ANYHOW, since it marks
the start of words which are performed regardless of the result of the
conditional.

>- "iepos" (Brent Kerby)

-Billy

From: peter_easthope@...
>In a message to native-oberon@... at Sat, 6 May 2000
>01:09:51 +0200 (MET DST) Sorren Renner said,
>sr> I hope that some of you will sign up for the new mailing list

>Thanks Sorren.  Joy is new me and I will have study it.

Welcome in.

>sr> ... described at
>sr> http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html :
>sr>   ...
>sr> Whereas all other functional programming languages
>sr> are based on the application of functions to arguments,
>sr> Joy is based on the composition of functions. ...  and no
>sr> environment of name-value pairs.

>The Web site gives this simple example of a text in Joy.

>2 3 +

>2 and 3 certainly appear to be values of arguments and +
>appears to be the name of a function.  Why is "no
>environment of name-value pairs" claimed?

2 and 3 are certainly the arguments which + evaluates.  However, notice two
things: first of all, those arguments are nowhere named (it's all implicit),
and second, those arguments are not tied to the function by any syntax.

Consider the difference between

   2 2 +
and
   2 dup +

(Dup makes a copy of the top-of-stack, so these two functions have the same
behavior.)  As you can see, although + has two explicit arguments in the
first function, it has only one explicit argument in the second one (or
perhaps you could say it has no explicit arguments).

>Thanks,              Peter E.

-Billy

Hello, folks....

Well, a bit ago I decided to follow Billy's advice and just make a
simple interactive environment, and not worry about compilation to
ELF and strange things for a while...

I've come up with something half-usable and thought I'd let you guys
know about it. It's at:

   http://www.tunes.org/~iepos/clip-joyful-0.2.tar.gz

It is an interpreter for a concatenative langauge similar to Joy.
However, it's not a normal interpreter, since it compiles to
native x86 code at runtime. But, understand that currently it generates
rather sorry code; it does no register allocation and often juggles
things on the stack even when they are statically known.

Okay, here are the words implemented now...

Arithmetic:
   + : adds top two stack items
   - : subtracts top stack item from the next
   * : multiplies top two stack items
   / : divides top stack item into the next
   % : like "/", but leaves remainder instead of quotient
   = : compares top two stack items (destructively, like always),
       and does one of the literals "true" or "false".

Combinator:
   dup  :      [x] dup    -> [x] [x]
   pop  :      [x] pop    ->
   swap :  [y] [x] swap   -> [x] [y]
   call :      [x] call   -> x
   dip  :  [y] [x] dip    -> x [y]
   cons :  [y] [x] cons   -> [[y] x]

Boolean:
   true : a literal
   false: a literal
   if   : true  [x] [y]    -> y
          false [x] [y]    -> x

I/O:
   puts : prints top string on stack (followed by newline)
   puti : prints top int on stack (followed by newline)

And, here is the confusing example program included with the tar.gz :-)

  (Count upward, beginning at 0, skipping multiples of five)
  0 [[dup 5 % 0 = [true] [false] if [] [dup puti] if 1 +] dip dup call] dup call

One mysterious problem with the system is that it doesn't work when I
turn on gcc's optimizations (p.s, this is because I forgot to use
"volatile" on the inline assembly; it works now).

Another problem is that the system never attempts to free string and
program literals, even when they are long past executed or printed for
their last time. Of course, this might be considered minor, since it
happens in ordinary C systems too.

There's another memory-management problem that's worse. In this system,
"cons" gives one the ability to construct dynamically-allocated
(by malloc(), currently) programs at runtime, but they will never
be freed; the programmer has no way to do it manually, and there is
no automatic garbage collector either.

Another problem is that the stack has a statically limited size of
200000 bytes; this may be changed by a #define at the top of the .c file :-)
Presumably, this could be fixed by somehow guaranteeing that a segfault
occurs upon overflow and arranging things so that the segfault is caught
and the stack extended a ways.

Currently, there are no primitives for dealing with arrays, buffers,
or things of that kind. Also, there is no support for lambdas or definitions.

I think that soon I will rewrite the whole system so that the compiler
keeps track of information about things on the stack; it would keep
track of the types of stack items, and their exact value, if possible;
otherwise, it would keep track of where they are stored (possibly in
registers, on the stack, or perhaps in a static memory location).
Then, many operations could be implemented by just changing the
bookkeeping, as Billy has said, without emitting any code.

Still, I'm a little puzzled about how exactly to go about register
allocation. I suppose we'd want to reserve the registers mainly
for the top 7 or so stack items (although not necessarily in a fixed
order). The main attack to register allocation schemes happens, I think,
when we need to compile a quotation; when we see it, it might not be known
which registers the parameters are going to be stored in, since we don't
know yet who's going to call it. Ultimately, in compiling a quotation,
one would have to decide what interface it will use, and then it would
be up to the callers to abide by it.

Perhaps a good technique would be to postpone compiling a quotation
until its first caller is known; then the quotation could be compiled
to take the parameters from the most convenient storage locations,
the one they are already in (but, future callers might have to move things
around to get things into the chosen locations). This technique would
turn out especially well if there is only one caller; this would actually
be a very common situation, I think; it would happen all the time
with branching and looping constructs, in which the program to
branch or loop has just been pushed as a literal.

Comments welcome...

- "iepos" (Brent Kerby)

> The Web site gives this simple example of a text in Joy.
>
> 2 3 +
>
> 2 and 3 certainly appear to be values of arguments and +
> appears to be the name of a function.  Why is "no
> environment of name-value pairs" claimed?

Hmm... I'm guessing they mean that there is no _dynamic_ environment
of name-value pairs. That is, there are no formal parameters (like "x")
of functions that get bound to different values each time the function
is entered.

It is true that there are static bindings of names to values
(such as the name "+" to the adding program, as your example),
but these for the most part do not change as the program is run.

> Thanks,              Peter E.

- "iepos" (Brent Kerby)

In a message to native-oberon@... at Sat, 6 May 2000
01:09:51 +0200 (MET DST) Sorren Renner said,
sr> I hope that some of you will sign up for the new mailing list

Thanks Sorren.  Joy is new me and I will have study it.

sr> ... described at
sr> http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html :
sr>   ...
sr> Whereas all other functional programming languages
sr> are based on the application of functions to arguments,
sr> Joy is based on the composition of functions. ...  and no
sr> environment of name-value pairs.

The Web site gives this simple example of a text in Joy.

2 3 +

2 and 3 certainly appear to be values of arguments and +
appears to be the name of a function.  Why is "no
environment of name-value pairs" claimed?

Thanks,              Peter E.

peter_easthope@...   48.7689d N, 123.3017d W, 30 m
Recommended reading:  http://www.naturalstep.org/

Here is a code fragment from the VM.

MODULE Boxes;
Import Out;

TYPE Box* = POINTER TO RECORD;
VAR
         next*:  Box;
PROCEDURE Exec*(stack: BoxStack);
         END Exec;
PROCEDURE Print*;
         END Print;
END Box;

TYPE Int = POINTER TO RECORD(Box);
VAR
         n: LONGINT;
PROCEDURE Exec*(stack: BoxStack);
         BEGIN
                 stack.Push(n);
         END Exec;
PROCEDURE Print*;
         BEGIN
                 Out.String(' Int Box containing: '); Out.Int(n,10);
Out.Ln;
                 IF next # NIL THEN next.Print END
         END Print;
END Int;

TYPE Op = POINTER TO RECORD(Box);
END Op;

TYPE Pop: POINTER TO RECORD(Op);
PROCEDURE Exec*(stack: BoxStack);
         BEGIN
                 stack.Pop;
         END Exec;
END pop;
TYPE Push: POINTER TO RECORD(Op);
PROCEDURE Exec*(stack: BoxStack);
         BEGIN
                 stack.Push;
         END Exec;
END Push;
*
TYPE Plus: POINTER TO RECORD(Op);
PROCEDURE Exec*(stack: BoxStack);
         BEGIN
                 WITH stack[stack.top-1]: Int DO
                         WITH stack[stack.top].n: Int DO
                         stack[stack.top-1].n := stack[stack.top].n +
stack[stack.top-1].n;
                         stack.top := stack.top - 1
                         END
                 END
         END Exec;
END Plus;

TYPE Mul: POINTER TO RECORD(Op);
PROCEDURE Exec*(stack: BoxStack);
         BEGIN
                 WITH stack[stack.top-1]: Int DO
                         WITH stack[stack.top].n: Int DO
                         stack[stack.top-1].n := stack[stack.top].n *
stack[stack.top-1].n;
                         stack.top := stack.top - 1
                         END
                 END
         END Exec;
END Mul;
  ....

....

END Boxes.


NOTICE the type guards (WITH..DO..END) in Plus.Exec and Mul.Exec. If
the two top boxes on the stack are not Int boxes (boxes containing
integers) then the type guards will throw run-time exceptions, since
there are no ELSE clauses. This is where polymorphic dispatch on
argument types would be implemented. "Plus" could be defined for two
Int boxes, 3 Quark boxes, two String boxes, architectural types
(gazebo cupola plus pagoda mod), etc. Types that aren't used in a
program shouldn't be tested for. (Efficiency).

sr

"Both of these languages
which I proposed would have to be written in themselves (although it
would
be permissable to write the second one in the first).

And GC is not trivial no matter what you do :-), and leaving it to
some
other language doesn't let you take advantage of how your language
behaves."

Probably true but not the only consideration. Building a VM in Oberon
for a language like Squeak, which already has its own memory model and
way of performing GC, might be clumsy. One would either have to use
Oberon much as one would use C, using the pseudomodule (actually
implemented in the compiler) SYSTEM to evade type-safety, or make
major changes to the VM, leaving it incompatible with images from
other systems. But we are not in the position of a Squeak porter. Joy
has no preferred memory model at this time, and no legacy images that
must be run bit-identically. If every box is an Oberon POINTER TO
RECORD, then GC is trivial enough to be called trivial. This wouldn't
be the best way to write Joy for a minimal (OTA-like) environment,
but
is the best way I can think of otherwise. If we don't use Oberon, what
shall we use? C? Ugh! This is 21st! Leave C in 20th!

C
****
efficient
portable to anything

Oberon
****
efficient
portable to x86, ARM, can be ported elsewhere
typesafe
GC

I agree that there is an attraction to running on bare hardware.
(Which is why I prefer to run Oberon with Oberon as the OS). But it
will be far easier to make a Joy-like VM with static typing and
polymorphism in Oberon than in itself/over bare metal, and speed is
not important (not that I am conceding the spped argument) at this
point.

I suppose the new language will have to have a name besides "Joy-like
VM". "Surprised by Joy?" Suggestions?

sr

PS I am not making this up!

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

May I suggest "gyros"?

sr

> >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")

From: Soren Renner [mailto:srenner@...]

>Yes. It has to have quotation. The question we should decide
>is whether it needs "define", or actually, where "define"
>should be. See my previous post.
>I am inclined to take "define" out of the interpreter, remove
>the dictionary, and code all ops as Oberon procedures.

It's kind of inconvenient to have an interactive system without the ability
to define things.  However, if you're only designing a VM, that may be
sufficient.  Speaking of VM, have you gotten a chance to read the OTA specs
(a Forthlike VM)?

>"It turns out, though, that 32 stack items is virtually
>infinite (in the words of a prominent Forth programmer). In
>general, it's easy to use more; however, in real use, it's very hard."

>So an array is a fine data structure for a stack. Also, since
>quotations might be quite long, the stack shouldn't be used to
>construct them.

Both statements sound reasonable to me, yes.  Since quotations are built out
of boxes, I would expect you to use the stack only as a place to put two
things before CONSing them together.

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

>I second Mr. Tanksley's motion. (Cries of Hear, hear! from the
>bench would be appreciated.) Permit me to point out that
>garbage collection is trivial if our language is written in a
>typesafe, garbage collected language. Some may object that the
>ultimate goal must be a language written in itself and
>compiling only to machine code. The person I am thinking of
>hasn't joined the list yet, though.

I'm one of the people who would say that, actually.  Both of these languages
which I proposed would have to be written in themselves (although it would
be permissable to write the second one in the first).

And GC is not trivial no matter what you do :-), and leaving it to some
other language doesn't let you take advantage of how your language behaves.

>Soren Renner

-Billy

"Your "IF" primitive seems to pop things off the box stack, but I haven't
            seen any primitives that push things on... Does you[r] system have a
            quotation construct like Joy's "[]"s?"

Yes. It has to have quotation. The question we should decide is whether it needs
"define", or actually, where "define" should be. See my previous post.
I am inclined to take "define" out of the interpreter, remove the dictionary,
and code all ops as Oberon procedures.

"It turns out, though, that 32 stack items is virtually infinite (in the words
of a prominent Forth programmer). In general, it's easy to use more; however, in
real use, it's very hard."

So an array is a fine data structure for a stack. Also, since quotations might
be quite long, the stack shouldn't be used to construct them.

"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"


I second Mr. Tanksley's motion. (Cries of Hear, hear! from the bench would be
appreciated.) Permit me to point out that garbage collection is trivial if our
language is written in a typesafe, garbage collected language. Some may object
that the ultimate goal must be a language written in itself and compiling only
to machine code. The person I am thinking of hasn't joined the list yet, though.

Soren Renner

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

>> In this implementation, the fundamental data structure is a
>> box chain.
>> A box is just a record with a pointer to another box. A box chain is
>> just a linked list. Ignore the asterisks in the declarations below.
>> They specify visibility outside the module.

>> PROCEDURE Exec*(bstack: BoxStack; istack: IntStack; dict: Dictionary;
>> VAR box: Box);

>I'm a bit puzzled about one thing... Why are there two separate stacks
>(a box stack and an int stack)?

For the same reason that Forth has two stacks: one stack holds the
continuation to which the current function will return, and the other stack
holds the data.

>Your "IF" primitive seems to pop things off the box stack, but
>I haven't
>seen any primitives that push things on... Does you system have a
>quotation construct like Joy's "[]"s?

Yes, that's what a box is.  I'm not sure whether or not he's invented a
syntax for boxing yet.

>> This stack is implemented as an array. Of course a depth of 10 is
>> impractical. Should the stack be a linked list instead of an array?

>An array sounds fine to me... but, does Oberon support dynamic
>allocation
>of arrays, so that if you exceeded the bounds you could just reallocate
>a larger one?

It does, but as his words imply, he hasn't implemented that.

It turns out, though, that 32 stack items is virtually infinite (in the
words of a prominent Forth programmer).  In general, it's easy to use more;
however, in real use, it's very hard.

>Of course, an array might not really be acceptable, if you're going to
>be dealing with lots of data on the stack and need to be able
>to quickly
>insert, delete, and move things around. If that were the case, then
>maybe a linked list would be a good option (although you'd probably
>want to group several items under the same node).

Arrays are generally good for this kind of thing, really.  Especially if all
your data items are represented by pointers, in which case it takes less
effort to swap the data items than it would have taken to rebuild a list.

>- Brent Kerby ("iepos")

-Billy

> In this implementation, the fundamental data structure is a box chain.
> A box is just a record with a pointer to another box. A box chain is
> just a linked list. Ignore the asterisks in the declarations below.
> They specify visibility outside the module.
>
> [...]
>
> PROCEDURE Exec*(bstack: BoxStack; istack: IntStack; dict: Dictionary;
> VAR box: Box);

I'm a bit puzzled about one thing... Why are there two separate stacks
(a box stack and an int stack)?

Your "IF" primitive seems to pop things off the box stack, but I haven't
seen any primitives that push things on... Does you system have a
quotation construct like Joy's "[]"s?

> This stack is implemented as an array. Of course a depth of 10 is
> impractical. Should the stack be a linked list instead of an array?

An array sounds fine to me... but, does Oberon support dynamic allocation
of arrays, so that if you exceeded the bounds you could just reallocate
a larger one?

Of course, an array might not really be acceptable, if you're going to
be dealing with lots of data on the stack and need to be able to quickly
insert, delete, and move things around. If that were the case, then
maybe a linked list would be a good option (although you'd probably
want to group several items under the same node).

> sr

- Brent Kerby ("iepos")

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

A short introduction to continuations:

"Continuations Made Simple and Illustrated"
by Denys Duchier

- http://www.ps.uni-sb.de/~duchier/python/continuations.html

--
Massimo Dentico

In this implementation, the fundamental data structure is a box chain.
A box is just a record with a pointer to another box. A box chain is
just a linked list. Ignore the asterisks in the declarations below.
They specify visibility outside the module.

TYPE Box* = POINTER TO RECORD;
VAR
         next*:  Box;
PROCEDURE Exec*(bstack: BoxStack; istack: IntStack; dict: Dictionary;
VAR box: Box);
         END Exec;
PROCEDURE Print*;
         END Print;
END Box;

"Box" is the basic type of box. It doesn't contain anything. You could
call it an abstract type. Here is an extension of "Box" which holds an
integer. Notice that "Exec" doesn't operate on global variables but
takes arguments. This corresponds nicely to Joy: all literals are
functions of type stack -> stack.

TYPE Int* = POINTER TO RECORD(Box);
VAR
         n: LONGINT;
PROCEDURE Exec*(bstack: BoxStack; istack: IntStack; dict: Dictionary;
VAR box: Box);
         BEGIN
                 istack.Push(n);
                 box := box.next;
         END Exec;
PROCEDURE Print*;
         BEGIN
                 Out.String(' Int Box containing: '); Out.Int(n,10);
Out.Ln;
                 IF next # NIL THEN next.Print END
         END Print;
END Int;

Here is another extension of "Box". It holds a string which specifies
an operation. It would probably be better if every primitive op had
its own box type. Then Oberon's polymorphic dispatch on "exec" would
take the place of the IF .. ELSIF ... statement.

TYPE Op* = POINTER TO RECORD(Box);
VAR
         op: Word;
PROCEDURE Exec*(bstack: BoxStack; istack: IntStack; dict:
Dictionary);
         BEGIN
                 IF op = 'POP' THEN
                         istack.Pop;
                 ELSIF op = 'SHOW' THEN
                         istack.Show;
                 ELSIF op = 'DSHOW' THEN
                         dict.Print;
                 ELSIF op = 'PLUS' THEN
                         istack.Plus;
                 ELSIF op = 'MUL' THEN
                         istack.Mul;
                 ELSIF op = 'DUP' THEN
                         istack.Dup;
                 ELSIF op = 'IF' THEN
                         IF istack.stack[istack.top] > 0 THEN
                                 next := bstack.stack[bstack.top];
                         ELSE
                                 box.next :=bstack.stack[bstack.top-1];
                         END;
                         bstack.top := bstack.top - 2;
                 ELSE (* op unprim *)
                         Out.String('unprim '); Out.String(op); Out.Ln;
                         IF next # NIL THEN bstack.Push(next) END;
                         next := dict.get(op);
                 END;
         END Exec;

PROCEDURE Print*;
         BEGIN
                 Out.String(' Op Box containing: ');Out.String(op);
Out.Ln;
                 IF next # NIL THEN next.Print END
          END Print;
END Op;

*****************************************

OK. Now I want to talk about stacks.

TYPE BoxStack* = POINTER TO RECORD;
VAR
         stack: ARRAY 10 OF Box;
         top: INTEGER;

PROCEDURE & new;
         BEGIN
                 top := 0;
         END new;

PROCEDURE Show*;
         VAR i: INTEGER;
         BEGIN
                 Out.String('BSTACK:');
                 FOR i := 0 TO top DO
                 IF stack[i] # NIL THEN stack[i].Print; Out.Ln
END;
                 END;
         END Show;

PROCEDURE GetTop*(VAR box: Box);
         BEGIN
                 box := stack[top];
         END GetTop;

PROCEDURE Push*(b:Box);
         BEGIN
                 stack[top+1] := b;
                 top := top + 1;
         END Push;

PROCEDURE Dup*;
         BEGIN
                 stack[top+1] := stack[top];
                 top := top + 1;
         END Dup;

PROCEDURE Pop*;
         BEGIN
                 top := top - 1;
         END Pop;

END BoxStack;

This stack is implemented as an array. Of course a depth of 10 is
impractical. Should the stack be a linked list instead of an array? It
would require double boxing. Consider a stack implemented as a linked
list with a box B on top of the stack. B.next points to the next box
in the chain, or NIL if the chain is just B (chain length 1). B.next
cannot be used to point to the next element of the stack. So B itself
must be placed in a new kind of box. Then the stack can be a special
kind of box chain. I don't like this idea very much.

*************************************************

You will have noticed that besides box chains and stack arrays there
is also a dictionary. The dictionary maps strings to definitions (box
chains.) However, "define" isn't functional. It could be argued that
"define" in Joy is a meta-level operation which changes the language.
If ops were tied to types as I suggested above, "define" could be
implemented without a dictionary by using the Oberon compiler.

square [dup times] def

==> Modify the source module in which the box types are defined to
include

TYPE Square* = POINTER TO RECORD(Box);
PROCEDURE Exec*(bstack: BoxStack; istack: IntStack);
	 BEGIN
	     dup(bstack: BoxStack; istack: IntStack);
	     times(bstack: BoxStack; istack: IntStack)
	 END Exec
    END Square;

(Notice that the dictionary is gone from the parameters. )
Now call the Oberon compiler (which is VERY fast) on the modified
module. The signature of the module now exports a new procedure.

The VM itself would have to die and be reborn, but maybe that's all
right. We could make the stack persistent.

sr

> >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")

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

> >Anyhow, I didn't suggest
> >saving all of the data stack.
>
> Eh?  I thought you did.  In that case, forget what I said.  I was arguing
> against that.  I don't see a reason to argue against a concept which has no
> defenders :-).

A strange confusion... I'm not sure how this happened :-)

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.

In case some are not familar with terminology relating to lambdas,
I'll give a little background. A lambda is a language device that
allows one to construct a function using a formal parameter; for instance,
if you name the squaring function as

   the function that takes a number 'x' and yields 'x' times 'x'

then you're using a lambda, and we call "x" the formal parameter
(as opposed to an "actual" or "concrete" parameter like "3" that we
could pass to this function).

Nearly all programming language feature a lambda-like construct
(but Joy is an exception). For instance, in Haskell, one could write
the squaring function as

   x -> x*x

C also has a lambda-like construct; you could write the squaring
function as "sqr" provided you had defined it as:

   int sqr(int x){ return x*x; }

But, this requires that one make up the name "sqr", as C does not have
an "anonymous" lambda construct, whereas Haskell does.

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] *

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.

The first word, "x\", is the one that uses a lambda...
One interesting about having such a lambda construct is that it is
possible to construct many of the Joy combinators using it, for instance:

   dup    == x\ [x] [x]
   pop    == x\
   swap   == x\ y\ [x] [y]
   i      == x\ x
   dip    == x\ y\ x [y]
   cons   == x\ y\ [[y] x]
   concat == x\ y\ y x

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\

Anyway, that was just some food for thought...

One other thing... it would probably be good to have some way of ending
the scope of a variable; for this it seems natural to write "\x".
Thus, for the squaring program we might write:

   x\ [x] [x] * \x

By the way, it is not my view that Joy is broken and needs to
be fixed by adding a lambda construct. Joy was deliberately designed
to avoid the formal parameters associated with lambdas, and it
does quite a nice job. In fact, adding a lambda construct as I suggest
would not add any power to the language, as far as what programs
can be constructed in it. 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"):

Rule 1: x\ x   (if there are no future uses of "x") -> i
Rule 2: x\ x   (if there are future uses of "x")    -> dup dip x\
Rule 3: x\ A   (if there are no future uses of "x") -> pop A
Rule 4: x\ A   (if there are future uses of "x")    -> [A] dip x\
Rule 5: x\ [x] (if there are no future uses of "x") ->
Rule 6: x\ [x] (if there are future uses of "x")    -> dup x\
Rule 7: x\ [Z] (if there are no future uses of "x") -> [x\ Z] cons
Rule 8: x\ [Z] (if there are future uses of "x")    -> dup [[x\ Z] cons] dip x\

When we apply the example to this program,

   x\ [x] [x] * [x] -

we get:

   dup x\ [x] * [x] -           (by rule 6)
   dup dup x\ * [x] -           (by rule 6)
   dup dup [*] dip x\ [x] -     (by rule 4)
   dup dup [*] dip -            (by rule 5)

The algorithm happened to generate something fairly compact this time.
Usually we are not so lucky. Of course, there are better algorithms...

Anyway... that's enough for now...

- Brent Kerby ("iepos")

> I'm not sure what a continuation is exactly, but Mr. Thun,
> Joy's author, does, because in the standard Joy library is the following:
>
> ...
>
>     callcc == [conts rest rest] dip step;
>     callcc1 == [conts stack put rest rest] dip step;

That's interesting... I'd never noticed that before.
The core primitive at work seems to be "conts". But, it doesn't
seem to be working right on my (Linux i386) system. I suspect that
maybe "conts" is supposed to push the list of pending primitive programs.
I could be wrong, though. On my system, it does roughly that, except that
the very next primitive word is skipped, and the rest are all lumped
together. For instance,

   conts 1 2 3 + + . .

gives me:

   6
   [[2 3 + +]]

I get a segfault when I do just "conts" by itself...

> It would be nice if we could share code. I wrote a toy VM for a
> language that by strange coincidence, serendipity, or perhaps
> synechdoche resembles Joy.

Cool...

> Details may be found at http://www.oberon.ethz.ch/native/ .
> If a few of us could download Oberon and set it up, I could easily
> post an .Arc (Oberon archive format) file with the toy VM.

All right... I'll have to take a look at Oberon...
I've never used it before...

- Brent Kerby ("iepos")

I'm not sure what a continuation is exactly, but Mr. Thun, Joy's author, does,
because in the standard Joy library is the following:

...

(* - - - - -   C O M B I N A T O R S   - - - - - *)

     b == [i] dip i;
     leftdist == [app2] dip ternary;
     callcc == [conts rest rest] dip step;
     callcc1 == [conts stack put rest rest] dip step;


callcc means "call with current continuation". So there is a continuation
combinator.

It would be nice if we could share code. I wrote a toy VM for a language that by
strange coincidence, serendipity, or perhaps synechdoche resembles Joy. This toy
could not have been written in C, at least by me. I give total props to Oberon.
Oberon is compiled, as fast as C++, typesafe, and garbage collected. (M.C.: post
to start a gc/refcount squabble thread). Its syntax will pose no problem to
anyone. The only tricky thing about Oberon is the environment, which has its own
conventions about mouse usage, editing, and other things. (Here I am speaking of
Oberon S3 in particular, particularly Native and Linux Native.) It has a
mode-less GUI (i.e. no modal dialogues) which runs either in an X window (Linux
Native) or as an OS on bare x86 hardware. Details may be found at
http://www.oberon.ethz.ch/native/ . If a few of us could download Oberon and set
it up, I could easily post an .Arc (Oberon archive format) file with the toy VM.

Here's a T-shirt concept: (front) Its just one d*** thing after another...
			   (back)  concatenative languages mailing list

sr

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

>Anyhow, I didn't suggest
>saving all of the data stack.

Eh?  I thought you did.  In that case, forget what I said.  I was arguing
against that.  I don't see a reason to argue against a concept which has no
defenders :-).

I was kinda hoping that one of use had some direct knowledge of what
continuations should be.  It appears, though, that the best we can do is
that Forth backtracking code (which treated a return pointer as a
continuation).  I guess if it works...

>It might be useful now to mention some of the pros/cons of inlining...

[Summary deleted.]

Thanks.

>- Brent Kerby ("iepos")

-Billy

> >Other than that, an applicative stack frame pretty much does the same
> >thing as a data stack in a concatenative language... both are used
> >to pass around parameters and local variables (although, in a
> >concatenative
> >language there is not a distinction between parameters and
> >local variables).
>
> There's a problem here.  The applicative stack frame is used to hold
> parameters which have been applied to the function, and that's why we save
> it in order to produce a complete continuation.  If we have to save all of
> the data stack, this implies that our language is actually applicative, and
> that pretending otherwise is only a surface sham, doesn't it?

Okay... I'm sort of confused... saving the whole data stack would be
a very silly, inefficient thing to do in most cases, and wouldn't
make sense in a concatenative system, but I don't see how it would
turn the language into an applicative one. Anyhow, I didn't suggest
saving all of the data stack.

> >By the way, now seems like a good time to bring up the FORTH-like
> >technique of keeping the return stack separate from the data stack.
> >[...]
>
> I think this is a good point -- in fact, I don't think it's possible to make
> a concatenative language which shares the data stack with the return stack.
> The two are completely unrelated to each other.

True... it would be quite tricky to share the data stack with the return
stack in a concatenative system...

> Just as an introduction, iepos and I have been arguing over inlining.  He is
> of the opinion that the best inlining is maximal inlining; every time it's
> vaguely possible to inline, you should.  I am of the opinion that the best
> inlining is NO inlining; whenever it's possible to make a call instead of
> inlining the function, you should.
>
> I justify my position by noting that call overhead is minimal in
> concatenative languages.  I'm sure he can defend his own position well, but
> his response to that would probably be that the call time is still not zero.

It might be useful now to mention some of the pros/cons of inlining...
First, some good things that can happen if you don't inline (i.e.,
instead use a procedure via a pointer):

   1) Storage savings, because one does not have to make redundant
      copies of identical procedures.
   2) Speed improvement. Because of the smaller code size, it may be
      possible for a loop to fit within a processor's cache, whereas
      if we had inlined it might not have fit.

These advantages only apply if the same procedure is being used multiple
times. If a procedure is only going to be used one time then inlining
would almost certainly be better, I think. Now, some advantages of inlining:

   1) Time is saved by not jumping around.
   2) Caching may work better because related code will be kept close
      together, whereas if one had not inlined one might have jumped
      way off to some far location and occupy a page of cache
      that is not being used except for one short procedure.
   3) It may be possible to allocate registers more wisely.
      If one uses a procedure multiple times via a pointer, then it
      is necessary to decide one fixed register interface that must
      work for all callers; callers may then need to swap things around
      whereas they wouldn't if the procedure had been inlined.
   4) It may be easier to garbage-collect the procedure when it is
      no longer needed. If one has a complicated tree (or worse yet, a web)
      of procedures that call one another, then garbage-collection will
      tricky. Inlining procedures would permit the web to be simpler.

      (note: problem number 4 with call-by-pointer doesn't happen in
       traditional systems (say, UNIX) because there is nearly no
       dynamic generation of code, and because it is considered tolerable
       for code in a process to be sitting around even when it is
       no longer needed, as long as it is eventually freed when
       the process terminates. I would suspect that garbage-collection
       of procedures would become more serious if one has dynamic
       generation of code, as I'm guessing we'd want in a system)

For small procedures, these advantages tell me that inlining is a
good idea. But, for large procedures, the storage savings compel us
to use a pointer (and not inline). I'm not sure where the best place
is to draw the line. I would estimate that maybe about 1K is a good
place to stop inlining... but maybe that's too high. Experimentation
is probably the best way to figure that out...

By the way, to me the issue of inlining-vs-call-by-pointer seems like
just a special case (although perhaps quite special) of the more
general question of when to copy data structures by-value and when
to copy by-reference. The answer I think that came up earlier is this:

   The smaller the data structure, the more we want to copy-by-value.
   The further apart that the data structure is going to be spread
     out across the system, the more we want to copy-by-value.

As an extreme case, if a data structure is going to be sent all the way
across a network to other computers, we would only attempt copy-by-reference
in most dire circumstances (i.e., very large size). And, of course,
copying-by-reference will not work if one user wants to modify the
structure (although it might be possible for just the modified portion
to be copied with the rest still copied by reference).

> One nice thing about concatenative languages is that inlining is truly
> transparent; there's no code changes needed.

True...

> >- Brent Kerby ("iepos")
>
> -Billy

- Brent Kerby ("iepos")

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

>> In an applicative language, a continuation is a stack frame:
>> it contains all
>> parameters and all local variables of the function in
>> question.  The problem
>> is that concatenative languages have neither parameters nor
>> local variables.
>> As far as I can tell, a continuation is merely "the rest of
>> what would be
>> executed in this function": in other words, it's a pointer
>> to your current
>> position in the current word.  Four bytes, give or take.

>Here's my understanding... a stack frame in an applicative language
>is very similar to the data stack in a concatenative language (such as
>FORTH or Joy), with this exception: an applicative stack frame will
>contain an explicit return address pointer (i.e., the continuation
>parameter) whereas a concatenative data stack typically would not
>(instead relying on a separate "return stack" for this purpose).

>Other than that, an applicative stack frame pretty much does the same
>thing as a data stack in a concatenative language... both are used
>to pass around parameters and local variables (although, in a
>concatenative
>language there is not a distinction between parameters and
>local variables).

There's a problem here.  The applicative stack frame is used to hold
parameters which have been applied to the function, and that's why we save
it in order to produce a complete continuation.  If we have to save all of
the data stack, this implies that our language is actually applicative, and
that pretending otherwise is only a surface sham, doesn't it?

It also makes it impossible to pass parameters to the continuation.

>By the way, now seems like a good time to bring up the FORTH-like
>technique of keeping the return stack separate from the data stack.
>It seems like a good technique in many ways. Most importantly,
>it permits one to call a subroutine seamlessly, without making copies
>of things that are already on the stack, provided that they are in the
>right place (otherwise, they might have to be swapped around).
>This can result in speed savings, and in the case of deep recursion,
>space savings as well.

I think this is a good point -- in fact, I don't think it's possible to make
a concatenative language which shares the data stack with the return stack.
The two are completely unrelated to each other.

>However, I'm guessing that in a system that does inlining well,
>the vast majority of time will be spent in an innermost procedure,
>so that the overhead involving calls might not matter that much anyway.

Just as an introduction, iepos and I have been arguing over inlining.  He is
of the opinion that the best inlining is maximal inlining; every time it's
vaguely possible to inline, you should.  I am of the opinion that the best
inlining is NO inlining; whenever it's possible to make a call instead of
inlining the function, you should.  (Cool difference of opinion, huh?)

I justify my position by noting that call overhead is minimal in
concatenative languages.  I'm sure he can defend his own position well, but
his response to that would probably be that the call time is still not zero.
We could go on for quite a while there.  :-)

One nice thing about concatenative languages is that inlining is truly
transparent; there's no code changes needed.

>- Brent Kerby ("iepos")

-Billy

> In an applicative language, a continuation is a stack frame: it contains all
> parameters and all local variables of the function in question.  The problem
> is that concatenative languages have neither parameters nor local variables.
> As far as I can tell, a continuation is merely "the rest of what would be
> executed in this function": in other words, it's a pointer to your current
> position in the current word.  Four bytes, give or take.

Here's my understanding... a stack frame in an applicative language
is very similar to the data stack in a concatenative language (such as
FORTH or Joy), with this exception: an applicative stack frame will
contain an explicit return address pointer (i.e., the continuation
parameter) whereas a concatenative data stack typically would not
(instead relying on a separate "return stack" for this purpose).

Other than that, an applicative stack frame pretty much does the same
thing as a data stack in a concatenative language... both are used
to pass around parameters and local variables (although, in a concatenative
language there is not a distinction between parameters and local variables).

> Is this right, or do we also need to imitate applicative languages by making
> a copy of the entire data stack?

Hmm... I don't quite understand... What you said before sounds right...
A continuation parameter in the end takes the form of a return address
(four bytes, give or take), and is basically a pointer to the current
word (or rather, the next word).

But, then again, I've never dug into compilers that use continuation
parameters, so I could be wrong.

By the way, now seems like a good time to bring up the FORTH-like
technique of keeping the return stack separate from the data stack.
It seems like a good technique in many ways. Most importantly,
it permits one to call a subroutine seamlessly, without making copies
of things that are already on the stack, provided that they are in the
right place (otherwise, they might have to be swapped around).
This can result in speed savings, and in the case of deep recursion,
space savings as well.

However, I'm guessing that in a system that does inlining well,
the vast majority of time will be spent in an innermost procedure,
so that the overhead involving calls might not matter that much anyway.

- Brent Kerby ("iepos")

It's good to see six people here at the start.  At this rate we'll be able
to form a newsgroup by summer.

Let's get down to business.  There are some things that I've been pondering
about stack languages (a term which I use as shorthand for concatenative
languages, since all of the ones I know of use a single data stack).  I'm
going to start my ponderings with Continuations.

In an applicative language, a continuation is a stack frame: it contains all
parameters and all local variables of the function in question.  The problem
is that concatenative languages have neither parameters nor local variables.
As far as I can tell, a continuation is merely "the rest of what would be
executed in this function": in other words, it's a pointer to your current
position in the current word.  Four bytes, give or take.

Is this right, or do we also need to imitate applicative languages by making
a copy of the entire data stack?

-Billy

From: Soren Renner [mailto:srenner@...]

>Dear Colleagues:
> I thought I was going to be the [co?]moderator. How
>does that work?

I have to check a box for that to happen.  Once I do that, you can handle
any of the new subscriptions we need; okay, you have full privileges.

In the future, email me personally for administrivia, please.

>Soren Renner.

-Billy

Dear Colleagues:
	 I thought I was going to be the [co?]moderator. How does that work?

Soren Renner.