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