# Reversible Joy?

## Brent Kerby — 2002-08-21 00:28:40

    The last while I've been doing some reading on reversible computing systems.

    It's quite a fascinating idea, really; you all might like to look at Mike

    Frank's page on reversible computing: http://www.cise.ufl.edu/~mpf/rc/ and

    also again Baker's paper:

    http://linux.rice.edu/~rahul/hbaker/ReverseGC.html.

    This got me thinking ... what would Joy look like if it was modified to be

    purely reversible? Here are a few of my thoughts on that:

    First off, as mentioned earlier we'll need to leave behind the "i"

    combinator, since it leaves no record of the program that is executed, and

    thus is not reversible. A suitable replacement is "run":

     [A] run == A [A]

    Next, the "dip" operator of Joy will need to be modified, since in its

    current form it is not reversible ("dip" leaves no record of what program

    has been executed). A suitable modified "dip" (we'll call it "rip", a

    contraction of "reversible dip") could work like this:

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

    This works like dip" except that it also leaves a record telling what

    program was "dipped". However, there is now a little complication: what if

    we want to "dip" a literal program? For example, what if we want to

    construct "dupd"? We cannot simply do "[dup] rip" because that will leave a

    useless "[dup]" quotation on top of the stack.

    To fix this it seems expedient to define a complement to the quotation

    construct, for removing literals from the stack. We will designate this

    using {}'s (curly braces). And so, we will say "{dup}" to destroy the

    "[dup]" quotation off the top of the stack. So, we construct "dupd" in this

    way:

      dupd == [dup] rip {dup}

    This does seem cumbersome, that everytime you want to "dip" a literal, you

    will have to specify that literal twice, once before the "rip" to push the

    literal, and once after the "rip" to the pop the literal. Also note that

    this problem is not unique to "rip"; it will also occur with the arithmetic

    operators "+", "-", "*", "/" (or rather, the modified reversible versions of

    them). Everytime you want to add a constant or multiply by a constant, it

    will be necessary to push the constant before the operation and pop it off

    afterward ... it seems to be a fact of life for reversible computing here:

    the operator must be sandwiched by the constant so that regardless of

    execution direction (forwards or backwards) the constant will be encountered

    before the operator. But, we could maybe permit some sugar of this kind

    (resembling applicative function-call syntax):

      dupd == dip(dup)

    where in general "f(x)" stands for "[x] f {x}". Of course this "sugar"

    destroys the concatenative feel of the system, so it may not be desirable at

    all. Maybe there is a better way.

    Anyhow, there are many curious issues that come up with reversible Joy. One

    question is this: is there a complete reversible combinatory base? In other

    words, is there a set of reversible combinators from which all reversible

    combinators can be constructed? It seems like there is. We can try {run,

    unrun, swap, rip, cons, tack, dup}, but I doubt this is quite complete in

    the above sense (I believe it does give Turing completeness, or rather the

    closest thing to it while being purely reversible). Probably we'll need a

    primitive for a reversible form of "cat":

      [B] [A] rat == [B A] [A]

    By the way, as long as we treat quotation as opaque, "cons" is acceptable as

    a reversible combinator, but if quotation is transparent then it must be

    rejected or modified (since, for example,  "[[B] [A] swap] uncons" is

    ambiguous and could be either "[B] [[A] swap]" or "[A] [[B]]").

    Now here's something very curious! ... The above function-call sugar is

    actually powerful enough to replace both the "[]" and "{}" constructs by

    using "dup" and "undup":

         dup(A)   ==  [A] dup {A} == [A] [A] {A} == [A]

     [A] undup(A) ==  [A] [A] undup {A} == [A] {A} ==

    It seems very twisted that this actually works, that you can use "dup(A)" to

    push a literal and "undup(A)" to pop one off. Perhaps the "()" construct is

    suitable as the fundamental. It seems like it. It may even make "[]" and

    "{}" obsolete, since in a reversible system they would almost always be used

    in cumbersome pairs, I suspect.

    From this brief excursion, it's looking like a reversible Joy could be very

    interesting ... I think it is definitely worthy of having a searcher written

    for it, so we can easily solve the minimal base questions :-)

    Feel free to share comments, or to demand clarification on something if I've

    left it all foggy ... :-)

    - Brent