Mark van Gulik — 2000-05-20 19:07:53

--- In concatenative@egroups.com, iepos@t... wrote:

> Greetings... I know this is a bit random, but it seems interesting

...

> The Joy-like "dip" combinator can be constructed as:
>
> swap unit cat call
>
> Here is how it works:
>
> [x] [f] swap unit cat call
> [f] [x] unit cat call (swap)
> [f] [[x]] cat call (unit)
> [f [x]] call (cat)
> f [x] (call)
>
> This construction is interesting because "call" is the only

unquoting

> combinator it relies on. This means that there exist complete bases
> that have "call" as the sole unquoting combinator. In particular,
> {swap, dup, drop, cat, unit, call} would work.

*** After writing this I discovered a major flaw with the logic, described
at the end, but you may want to go down this path anyhow just to see it's a
dead end, and why....

I'm not sure if any of you have noticed, but not only can Joy be considered
to be built up from S-expressions, but all the operators can be considered
simple manipulations of a tree:

\ \
/\ /\
A /\ ---> B /\
B /\ A C
/ \
swap C

or, rotating the tree left 45 degrees...

(* * * . C) (* * . C)
| | | ---> | |
A B swap B A

As someone pointed out earlier, Joy doesn't have a "distinguished position"
for function application. That goes well with referential transparency
(i.e., evaluation order doesn't matter).

The first notation is probably clearer, even though it's harder to type.
Anyhow, note that C is allowed to be an empty tree. Here are some other
operations expressed as tree rewrites...

\ \
/\ ---> /\
A /\ A /\
/ \ A C
dup C

\ \
/\ ---> /\
A /\ /\ C
/ \ A []
unit C

\
/\ \
/ \ /\
/\ \ /\ C
A1/\ \ A1/\
A2 \ \ A2 \
... \ ---> ...
/\ \ /\
Ax [] \ Ax/\
/\ B1/\
/ \ B2 \
/\ \ ...
B1/\ \ /\
B2 \ \ By []
... \
/\ \
By [] \
/\
cat C

\ \
/\ /\
/ \ F /\
/ \ A1 \
/\ /\ ---> ...
F /\ i C /\
A1 \ Ax C
...
/\
Ax []

Anyone care to try some other operators?

There might be a way to avoid the ellipsis notation. Appending two lists
together in a functional language involves something like (pardon my rusty
Scheme)...

(define Append (x y)
(cond
(x (cons
(first x)
(Append (rest x) y)))
(t y)))

Thus, cat could be written in Joy as:

cat == [swap cons] fold

Yeah! That should help. Let's do fold as two rewriting rules:

\
/\ \
[] /\ /\
X /\ ---> X Z
F /\
/ \
fold Z

\ \
/\ /\
/\ \ B /\
A B \ A /\
/\ ---> X /\
X /\ F /\
F /\ F /\
/ Z / Z
fold fold

Am I way off with this? Something doesn't look right about those two F's,
where only the upper one is allowed to be "invoked". Maybe that's the
problem, I'm thinking about invocation, when what I've been doing so far is
partial evaluation. Here's my best guess of why I'm uncomfortable with
this. All operations are associative in Joy, including ones constructed
from others (because they're mere concatenations of associative operations
themselves). That makes them isomorphic to some subgroup of functions of
one argument under composition. Yes, that's functions of one argument, in
particular the stack. The "execution" model (assuming these programs are
ever executed, of course) passes the stack in and gets it back out of each
function in turn. Associative transformations on the program are cancelled
out by this monadic behavior of the stack. So at "execution time", the
above chain is: B A X F F fold . Z (using the dot notation like dotted
pairs in Scheme). I've been treating B as a subprogram that pushes one
value on the stack. Joy doesn't have a type system which can guarantee
this, so my correspondence between subprograms and subprograms that add one
value to the stack is false. Best case, I could add a type system to Joy to
enforce this, but I'd still be in the situation that if B had the effect of
pushing seven values, none of the rewriting rules would correctly apply
until B was expanded.

Sigh. It seemed like a good idea at the time.

I realize now that without a type system, a subprogram can push a "random"
amount of information on the stack and a subprogram to the right of it can
remove a "correlated random" amount of information from the stack. This is
even useful if you want to implement something like dupN or popN. A type
system would weaken the language (actually, weaken the expressiveness while
strengthening the semantics). It would no longer be Joy (but mere Pleasure
:-).

iepos@tunes.org — 2000-05-20 19:36:05

> [...]
>
> I've been treating B as a subprogram that pushes one
> value on the stack. Joy doesn't have a type system which can guarantee
> this, so my correspondence between subprograms and subprograms that add one
> value to the stack is false. Best case, I could add a type system to Joy to
> enforce this, but I'd still be in the situation that if B had the effect of
> pushing seven values, none of the rewriting rules would correctly apply
> until B was expanded.
>
> Sigh. It seemed like a good idea at the time.

Okay, I'm going to try to restate the problem you see, to make sure
I understand. You're saying something like this: wouldn't it be
nice if we had the rewrite rule that

A B swap

is always replacable by

B A

But we can't really have that rewrite rule because it would only work
if "A" and "B" were programs that pushed just one thing onto the stack
(moreover, it would only work if "A" and "B" had no side effects, since
if they did then reversing the order in which they are executed may
change things).

If this is what you meant, then I have some good news, I think.
Restate the rule this way:

[A] [B] swap

is always replacable by

[B] [A]

This rule would always hold; regardless of what programs "A" and "B" were,
"[A]" and "[B]" will always be side-effect-free programs that push
one thing onto the stack.

One problem with doing it this way, though, is that this rule only
applies to quoted programs, and not to, say, integer literals;
that is, we couldn't use our rule to prove that

1 2 swap == 2 1

My view is that Joy's syntax for integer literals needs to be changed
so that one would do "[1]" and "[2]" to push integers onto the stack,
and not just "1" and "2". That would solve the problem. I like
to interpret "[foo]" as "push 'foo' onto the stack", and since
"foo" is usually a program, usually a program gets pushed onto the
stack, but if "foo" was an integer, then an integer would get pushed.

Then, we could give these rewrite rules for some of Joy's combinators:

[B] [A] swap -> [A] [B]
[A] dup -> [A] [A]
[A] drop ->
[B] [A] cons -> [[B] A]
[B] [A] concat -> [B A]
[A] i -> A
[B] [A] dip -> A [B]

These rules could then be considered full specifications of the
combinators, and they would hold for any well-formed Joy expressions
"A" and "B".

- Brent Kerby ("iepos")

Brian Rice — 2000-05-20 19:43:51

At 02:07 PM 5/20/00 -0500, you wrote:

>--- In concatenative@egroups.com, iepos@t... wrote:
> > Greetings... I know this is a bit random, but it seems interesting
>...
> > The Joy-like "dip" combinator can be constructed as:
> >
> > swap unit cat call
> >
> > Here is how it works:
> >
> > [x] [f] swap unit cat call
> > [f] [x] unit cat call (swap)
> > [f] [[x]] cat call (unit)
> > [f [x]] call (cat)
> > f [x] (call)
> >
> > This construction is interesting because "call" is the only
>unquoting
> > combinator it relies on. This means that there exist complete bases
> > that have "call" as the sole unquoting combinator. In particular,
> > {swap, dup, drop, cat, unit, call} would work.
>
>
>*** After writing this I discovered a major flaw with the logic, described
>at the end, but you may want to go down this path anyhow just to see it's a
>dead end, and why....
>
>
>I'm not sure if any of you have noticed, but not only can Joy be considered
>to be built up from S-expressions, but all the operators can be considered
>simple manipulations of a tree:
>
> \ \
> /\ /\
>A /\ ---> B /\
> B /\ A C
> / \
>swap C
>
>
>or, rotating the tree left 45 degrees...
>
> (* * * . C) (* * . C)
> | | | ---> | |
> A B swap B A
>
>As someone pointed out earlier, Joy doesn't have a "distinguished position"
>for function application. That goes well with referential transparency
>(i.e., evaluation order doesn't matter).
>
>The first notation is probably clearer, even though it's harder to type.
>Anyhow, note that C is allowed to be an empty tree. Here are some other
>operations expressed as tree rewrites...
>
>
> \ \
> /\ ---> /\
> A /\ A /\
> / \ A C
> dup C
>
> \ \
> /\ ---> /\
> A /\ /\ C
> / \ A []
> unit C
>
> \
> /\ \
> / \ /\
> /\ \ /\ C
>A1/\ \ A1/\
> A2 \ \ A2 \
> ... \ ---> ...
> /\ \ /\
> Ax [] \ Ax/\
> /\ B1/\
> / \ B2 \
> /\ \ ...
> B1/\ \ /\
> B2 \ \ By []
> ... \
> /\ \
> By [] \
> /\
> cat C
>
> \ \
> /\ /\
> / \ F /\
> / \ A1 \
> /\ /\ ---> ...
> F /\ i C /\
> A1 \ Ax C
> ...
> /\
> Ax []
>
>Anyone care to try some other operators?
>
>There might be a way to avoid the ellipsis notation. Appending two lists
>together in a functional language involves something like (pardon my rusty
>Scheme)...
>
>(define Append (x y)
> (cond
> (x (cons
> (first x)
> (Append (rest x) y)))
> (t y)))
>
>Thus, cat could be written in Joy as:
>
> cat == [swap cons] fold
>
>
>Yeah! That should help. Let's do fold as two rewriting rules:
>
>
> \
> /\ \
> [] /\ /\
> X /\ ---> X Z
> F /\
> / \
> fold Z
>
> \ \
> /\ /\
> /\ \ B /\
> A B \ A /\
> /\ ---> X /\
> X /\ F /\
> F /\ F /\
> / Z / Z
> fold fold
>
>Am I way off with this? Something doesn't look right about those two F's,
>where only the upper one is allowed to be "invoked". Maybe that's the
>problem, I'm thinking about invocation, when what I've been doing so far is
>partial evaluation. Here's my best guess of why I'm uncomfortable with
>this. All operations are associative in Joy, including ones constructed
>from others (because they're mere concatenations of associative operations
>themselves). That makes them isomorphic to some subgroup of functions of
>one argument under composition. Yes, that's functions of one argument, in
>particular the stack. The "execution" model (assuming these programs are
>ever executed, of course) passes the stack in and gets it back out of each
>function in turn. Associative transformations on the program are cancelled
>out by this monadic behavior of the stack. So at "execution time", the
>above chain is: B A X F F fold . Z (using the dot notation like dotted
>pairs in Scheme). I've been treating B as a subprogram that pushes one
>value on the stack. Joy doesn't have a type system which can guarantee
>this, so my correspondence between subprograms and subprograms that add one
>value to the stack is false. Best case, I could add a type system to Joy to
>enforce this, but I'd still be in the situation that if B had the effect of
>pushing seven values, none of the rewriting rules would correctly apply
>until B was expanded.
>
>Sigh. It seemed like a good idea at the time.
>
>I realize now that without a type system, a subprogram can push a "random"
>amount of information on the stack and a subprogram to the right of it can
>remove a "correlated random" amount of information from the stack. This is
>even useful if you want to implement something like dupN or popN. A type
>system would weaken the language (actually, weaken the expressiveness while
>strengthening the semantics). It would no longer be Joy (but mere Pleasure
>:-).

Now, *this* is why I joined the list! :-)

I'm definitely going to give this some thought, thanks for the idea and
examples. One (untested idea) suggestion is to push associativity out into
user-land, which of course amounts to a kind of small type system. It would
do exactly as you suggest in your last paragraph, but perhaps do it in the
least damagin way, or at least that's my experience with systems in logic
where you hack at the syntactic rules to make problems tractible.

Just my 2 cents.

~
http://www.tunes.org/~water/

wtanksley@bigfoot.com — 2000-05-20 20:17:37

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

>> Sigh. It seemed like a good idea at the time.

>Okay, I'm going to try to restate the problem you see, to make sure
>I understand. You're saying something like this: wouldn't it be
>nice if we had the rewrite rule that

> A B swap

>is always replacable by

> B A

>But we can't really have that rewrite rule because it would only work
>if "A" and "B" were programs that pushed just one thing onto the stack
>(moreover, it would only work if "A" and "B" had no side effects, since
>if they did then reversing the order in which they are executed may
>change things).

Well said, iepos. Yes, reordering rules aren't expressible by merely
textual rules in concatenative languages. Rewriting rulse are by definition
textual, and concatenative languages _do_ have rewriting rules. However,
all of their reordering rules depend on properties of the functions being
addressed.

>If this is what you meant, then I have some good news, I think.
>Restate the rule this way:

> [A] [B] swap

>is always replacable by

> [B] [A]

>This rule would always hold; regardless of what programs "A"
>and "B" were,
>"[A]" and "[B]" will always be side-effect-free programs that push
>one thing onto the stack.

That's accurate. It's something of a waste of time, though; you're
sacrificing ruleset simplicity on the altar of textual rewriting. You need
to give in and admit to yourself that textual rewriting doesn't work for all
situations.

>One problem with doing it this way, though, is that this rule only
>applies to quoted programs, and not to, say, integer literals;
>that is, we couldn't use our rule to prove that

> 1 2 swap == 2 1

>My view is that Joy's syntax for integer literals needs to be changed
>so that one would do "[1]" and "[2]" to push integers onto the stack,
>and not just "1" and "2". That would solve the problem.

No, it wouldn't. Textual rewrites STILL couldn't express all possible
reorderings, any more than they could express all possible reorderings in
any other language. You're trying all these strange measures to solve a
problem which can't be solved.

A directly parallel problem exists in all other language systems, including
applicative ones (although it happens that applicative systems can textually
handle this particular situation, there are many others which they cannot).
My intuitive reaction is to state that it's not a problem, but I have to
admit that your reaction (trying to find a solution) is more sane :-).

>I like
>to interpret "[foo]" as "push 'foo' onto the stack", and since
>"foo" is usually a program, usually a program gets pushed onto the
>stack, but if "foo" was an integer, then an integer would get pushed.

But this isn't how quotations work. [foo] is a quotation literal, and its
runtime effect is to push a quotation on the stack. No matter what foo is,
[foo] pushes a quotation on the stack. foo can be one, zero, or thirteen
words long, and [foo] will still consistently push a quotation on the stack.

THIS is one of Joy's "rewriting" rules. It happens to fit in exactly with
another one of Joy's rewriting rules: Any group of words may be replaced by
a single word which is defined to have the same effect as that group of
words.

>Then, we could give these rewrite rules for some of Joy's combinators:
> [B] [A] swap -> [A] [B]
> [A] dup -> [A] [A]
> [A] drop ->
> [B] [A] cons -> [[B] A]
> [B] [A] concat -> [B A]
> [A] i -> A
> [B] [A] dip -> A [B]
>These rules could then be considered full specifications of the
>combinators, and they would hold for any well-formed Joy expressions
>"A" and "B".

Again, this doesn't even come CLOSE to solving the problem you're attempting
to solve; those are certainly NOT full specifications. They're nothing more
than attempted textual rewrite rules; as such, they miss anything without
quotations.

>- Brent Kerby ("iepos")

-Billy

wtanksley@bigfoot.com — 2000-05-20 20:23:33

From: Brian Rice [mailto:water@...]

>Now, *this* is why I joined the list! :-)

I was glad to see that you'd joined, too.

>I'm definitely going to give this some thought, thanks for the
>idea and examples.

Same here, although mainly because it goes against everything I understand
about concatenative languages. You see, one of my main rules is that
concatenative languages are not tree-structured but rather list-structured.
I still suspect I'm right, but I'm going to read that email very closely.

BTW, I consider banning all random-stack-effect words to be reasonable.

>One (untested idea) suggestion is to push
>associativity out into
>user-land, which of course amounts to a kind of small type
>system.

What does it mean to "push associativity out into user-land"? I've never
heard anything like that phrase before; it means nothing to me.

I'm very much in favor of a type system. I posted some links to some
discussion of a very powerful and extremely simple implementation of an
ML-power typesystem which requires no additional parsing in the language
(quite impressive).

-Billy

Mark van Gulik — 2000-05-21 18:38:55

From: wtanksley@...

>
> From: Brian Rice [mailto:water@...]
>>I'm definitely going to give this some thought, thanks for the
>>idea and examples.
>
> Same here, although mainly because it goes against everything I understand
> about concatenative languages. You see, one of my main rules is that
> concatenative languages are not tree-structured but rather list-structured.
> I still suspect I'm right, but I'm going to read that email very closely.
>
> BTW, I consider banning all random-stack-effect words to be reasonable.

Actually, if you look at the spine of the tree you'll see that the
manipulations I was doing were actually list-structured. All the patterns
were expressed in a kind of continuation-passing style, where the "rest of
the list" was simply the rightmost pattern variable in the tree, usually
labelled with C or Z.

Maybe a key to expressing complete rewriting rules for Joy lies a bit
deeper. If a top-level program takes no arguments and produces a finite
list of literals (say we ban quotation literals in the final output for now)
on the stack as its result, I'm fairly confident we can express the
program's evaluation strictly in terms of a finite list of rewriting rules.

On a mostly unrelated topic, I was considering how much expressive power was
lost by Joy's lack of support for lexical closures. Sure, locally bound
variables and arguments can be bisimulated by finite stack manipulations,
but are lexically closed variables also possible (the question of software
re-use being my motivating concern)?

A simple scheme (no pun intended) to support closures would be to simply
implement a closed function as a pair of things -- the function and an
aggregate of lexically closed variables. Every time a closure is needed,
this pair of things would be used. To invoke the closure, simply push the
aggregate of closed variables onto the stack (as an aggregate) and invoke
the function, which is written to expect this aggregate to be on the top.

Closure provides enough power to easily support polymorphism, which in turn
is strong enough to host object-oriented programming. I'm *not* saying Joy
is object-oriented, I'm just saying an object-oriented language can be built
fairly easily and efficiently on top of it.