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