# Joy as tree rewriting

## 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.

## peter_easthope@gulfnet.pinc.com — 2000-05-22 19:17:05

    >  ... lexical closures ...

     Someone please explain what a lexical closure is.

    Thanks,       Peter E.