# More reversible Joy ideas

## Brent Kerby — 2002-09-07 04:11:19

    Looks like this list has been pretty quiet for a while. So I just thought I

    might write up some more thoughts I've had about reversible Joy. Some of

    this may duplicate what I've already said before, although hopefully things

    are a bit clearer now.

    First off, for a reversible Joy to be perfectly and beautifully reversible,

    we want each word to have a dual. For example, if we have "dup", then we

    also need "undup"; if we have "run", we need "unrun", and so forth ("swap"

    is special, since it is its own reverse; several other operations have this

    property as well, such as arithmetic negation, "xor", and the fourier

    transform (when it is normalized properly)).

    A complication arises when we consider quotations. Once we have pushed a

    quotation, how can we reverse this operation? We could use "zap" (i.e.,

    "pop"), except that we cannot allow "zap" in a reversible system. So, the

    natural solution seems to be to admit a dual to the quotation construct,

    just as there is a dual to every word. I suggested maybe using curly braces

    to notate this; so, you'd say "[A]" to push something onto the stack and

    "{A}" to get rid of it. Thus "[A] {A}" would do nothing.

    But, there's a problem with this setup. Oftentimes we'd like to dip a

    particular program (i.e., do something like "[A] dip"). But we cannot allow

    "dip" itself in the system, since (like "i") it destroys the information

    about what program is run. So we define a reversible version of "dip", that

    we call "rip":

      [B] [A] rip   ==   A [B] [A]

    Now we can "dip" a particular program by doing "[A] rip", except that the

    program "A" is left sitting on the stack, and we have to get rid of it with

    "{A}". This works, but it is quite messy, and gets ridiculously tedious when

    we try to do nested dips. For example, to do

      [[A] dip] dip

    we'd have to do

      [[A] rip {A}] rip {[A] rip {A}}

    Each time we add another level of nesting, the size of the program more than

    doubles, going up exponentially, when it should simply be linear.

    The natural solution seems to be to admit the application construct, which

    we write with ()'s (parentheses). This solves the problem in a very curious

    way (I'll explain how below). My initial reaction is that it seems ugly to

    have all three constucts (the []'s, {}'s, and ()'s). But then it so happens

    that the application construct can make the other two obsolete.

    So then we end up with a hybrid system that is a combination of

    concatenative and applicative. But it's not terribly complex, because the

    addition of the new application construct is balanced in part by the

    elimination of the original quotation construct.

    So, how does the application construct work? Well, basically it pushes a

    literal (known data), runs a literal program that may use it, and then

    unpushes the literal data. The definition fundamentally is this:

      f(x)  ==  [x] f {x}

    This sounds like a conventional system with a stack frame. A major problem

    with traditional stack frames (like in C) is that it wastes space, since a

    parameter must remain on the stack until the end of a function (even if the

    parameter has served its purpose near the beginning the function). Perhaps

    this problem will also happen here, we might wonder? Well, one big

    difference here is that only literals are allowed as parameters; so they

    don't need to be stored dynamically on a stack the same way. You might say

    that the literals always take up space (in the code) from the very beginning

    of the program; no space is allocated when they are pushed, and none is

    freed when they are popped, so it doesn't really matter if they are popped

    later than they need to be. That's how I see it, at least. How this all will

    settle how in practice is hard to say.

    Anyhow, we know that theoretically the application construct is enough to

    consume both quotation constructs because

      dup(x)   ==  [x]

      undup(x) ==  {x}

    Yet, the question remains: is this artificial? Is it going to require us to

    have a bunch of ugly dup's and undup's everywhere? I think that the answer

    is no, fortunately. This is because it is very rare for literal data to make

    its way out to the final output of a program; usually, literal data is only

    used to perform an internal transformation, and then it is no longer needed

    (this fits the application construct perfectly, which is essentially a way

    of scoping literal data). For those rare times that literal data does make

    it to the output, it seems natural to say that a duplication has indeed

    taken place, because the literal data is still present in the code as well

    as in the output.

    A surprising result of this excursion, to me, is to see that mainstream

    systems are not as far off from the ideal as we might think. It appears that

    the natural way to run code is nondestructively (in essense, by using "run"

    instead of the irreversible "i"), which is compatible with how processors

    run code using an instruction pointer. In contrast, I might have envisioned

    that the theoretically ideal way was for a processor to suck up

    instructions, destroying them after they have been executed, although we can

    see now that this is not good.

    The other curious result is that the application appears to be a naturally

    fundamental primitive. Yet, it appears that concatenation should also be a

    primitive; yes, we can technically simulate concatenation using application

    (using the "rap" technique described a few posts back, or ">>" like in

    Haskell), by pretending that concatenation is an ordinary function, but this

    in essence only hides concatenation from the surface; it must still be

    present in the internals of the system. (But perhaps I'm wrong here; maybe

    there is an elegant way for application to consume concatenation).

    One question that bothers me still is how to express the rewrite rules for

    the basic operators, using application and not the quotation construct. We

    can express "swap" by saying

      [B] [A] swap  ==  [A] [B]

    But how can we express "swap" using application instead of []'s? We can try

    this:

      (swap f swap)(A)(B)  == f(B)(A)

    Similarly for "dup" we can do:

      (dup f undup)(A)  == f(A)(A)

    This seems not sufficient, though, although maybe it is.

    One other question is regarding exactly what class of operations we should

    allow in a pure reversible Joy. Should we allow a "dup cat"?:

      [A] dupcat  ==  [A A]

    It is reversible, and easily so if we consider quotation as opaque (more

    difficult, or maybe unimplementable, otherwise).

    Anyhow; still it would be neat to make a brute-force searcher for this kind

    of system. But first it seems important to iron out these details first,

    regarding exactly what class of things we want to allow in the system. At

    this point, it seems hard to say which class is most natural (whether we

    should even admit "cons", and then how about "dupcat"). Perhaps everything

    that is reversible should be admitted; but is this possible?

    - Brent