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