After a bit more thinking about this, a few more thoughts surfaced ...

First, I probably didn't clearly explain the whole point of the
reversibility idea. The point is to have a Joy system where for every
program that does something (to the stack), there is a complementary program
of the same size and structure that can return the system to its original
state.

It might seem that a system like this would be too restrictive, since it
could not permit the destruction of information. For example, suppose we are
challenged to construct the squaring function, given a multiplication
operator "*" that works like this:

2 3 * == 6 3

We can try the obvious, "dup *", but this leaves a piece of garbage data on
top of the stack (the original number), and we cannot simply destroy this
garbage in a reversible system. Yet we know a true squaring function (one
that leaves no extra garbage) should in theory be possible to construct,
because it is reversible (by taking a square root). But it will be as
difficult to construct it as it will to construct a square root function. It
is a good question whether this kind of square root function could be
constructed (using iteration) in a way that is purely reversible (this is
probably answered in the literature somewhere).

A consequence of using a purely reversible system is that computing the
inverse of a function is no harder than computing the original function;
however, perhaps in many cases this is only because strict reversibility
makes it harder to compute both functions.

One interesting thing about the peculiar function application construct is
that it possesses this property:

The reverse of F(x) is "F'(x)", where "F'" is the reverse of "F".

This may seem trivial, but essentially this says that in finding the reverse
of a compound program it is not necessary to reach inside the parameters of
function applications.

Also, the [] and {} constructs are reverses of each other; i.e., {X} is the
reverse of [X], for any particular X, and vice versa.

One final interesting thing about the application construct (which we denote
with ()'s) ... Last post it was shown that the application construct is
sufficient to eliminate []'s and {}'s, provided we have "dup" and "undup".
But something even stronger can be shown: this application construct can be
used to eliminate concatenation itself! (leaving application as the sole
construct).

To do this we'll need a modified, reversible form of the "sap" combinator:

[B] [A] rap == A B [B] [A]

And now, we can simply use "rap(A)(B)" as a replacement for "A B":

rap(A)(B) == [B] [A] rap {A} {B} == A B [B] [A] {A} {B} == A B

So we have mutated Joy from its natural beautiful concatenative form to a
form where an incarnation of function application has taken over everything.
But the result may not be as ugly as we think. (If concatenation is taken
from the system, then we can relax the rules on parentheses, to permit "rap
A B" to mean "rap(A)(B)", and now we can say "dip dup" or "dip swap" for
"dupd" and "swapd", and such, with no parentheses needed)

I should mention that this mutation can take place even if we are not
dealing with a reversible Joy. We can simply alternatively define the
application construct this way:

F(X) == [X] F zap

It's hard to tell what all the consequences of this is ... It really doesn't
quite seem natural to have application take over everything because in
expressing the rewrite rules for the combinators we need to use the []'s
(application doesn't seem like enough), i.e.:

[B] [A] rip == A [B] [A]
[A] run == A [A]
[A] dup == [A] [A]
[A] [A] undup == [A]
[B] [A] rat == [B A] [A]

We can attempt to express some of them using ()'s:

rip(A)(B) == A
run(A) == A

But I don't see how to do it for the other combinators. Interestingly,
though, from that attempt with "rip" and "run", it looks like "rip"
simulates the classical K combinator, and "run" the I combinator. This could
probably be taken further.

One other exciting question in regard to this reversible system is: does
this mean we can do complex Church numerals arithmetic? I would see no
reason why not, because reversibility enables us to simulate the negative
numbers, and also fractional, irrational, and imaginary. It would be quite
interesting to see precisely how this would work.

Comments still welcome.

- Brent

On Wed, 21 Aug 2002, Brent Kerby wrote:

[..lots of good stuff about reversible operations in a Joy-like language]

Legend has it that in the 20's one of the great physicists of the
time (Fermi? Dirac?..?) used to say, when told of a brilliant new idea
in quantum mechanics, "It is crazy, totally crazy. But is it crazy
enough?"

You know much more about reversible computation than I do, so
I can presume you know about quantum computation, which has to
be reversible for reasons that I do not understand. (I know
that you are planning to build a quantum-Joy computer whose
machine language is called Qjoy ..)

Here is my tuppence ha'penny's worth:

A single stack is fine for postfix and for concatentive languages.
But it my be that it is not enough fore reversible compuutation.
Maybe a different structure - perhaps two stacks:
to compute 8 3 -
push 8 and then 3 onto the normal stack as before.
then remove both and push 5 onto the normal stack,
but also push the 3 onto the reversal stack.
So, the reverse of the subtraction operation has to be an addition
(well, of course) with a twist: pop both stacks, push the ordinary
sum of what as just been popped (that's the 8) onto the ordinary
stack, and then push the 3 (which came from the reversal stack)
onto the ordinary stack.

Hope this helps.

[..]

> One other exciting question in regard to this reversible system is: does
> this mean we can do complex Church numerals arithmetic? I would see no
> reason why not, because reversibility enables us to simulate the negative
> numbers, and also fractional, irrational, and imaginary. It would be quite
> interesting to see precisely how this would work.

What a coincidence. I have just been working on Church arithmetic
in Joy. But I won't attempt negative numbers and so on. However,
with lazy evaluation or some kind of optimisation it might be possible:
[..F..] five-times [..F..] neg-two-times == [..F..] three-times

Good luck with Qjoy

Incidentally, you have probably seen on the Joy page my link
to your combinator paper in the tunes directory.

- Manfred

On Fri, 23 Aug 2002, Manfred von Thun wrote:

[..]
> A single stack is fine for postfix and for concatentive languages.
> But it my be that it is not enough fore reversible compuutation.
> Maybe a different structure - perhaps two stacks:
> to compute 8 3 -
> push 8 and then 3 onto the normal stack as before.
> then remove both and push 5 onto the normal stack,
> but also push the 3 onto the reversal stack.
> So, the reverse of the subtraction operation has to be an addition
> (well, of course) with a twist: pop both stacks, push the ordinary
> sum of what as just been popped (that's the 8) onto the ordinary
> stack, and then push the 3 (which came from the reversal stack)
> onto the ordinary stack.

Here is a reasonable notation to use for the rules and for
tracing the forward and reverse execution. Write stacks and
atomic programs on alternate lines. On odd-numbered lines write
the ordinary stack on the left, and the reversal stack on the right.
This line describes the "before-state" for forward execution. On even
numbered lines write the atomic program in the middle. On the
next line write the "after-state" for forward execution, which is also
the "before-state" of the following execution. The program now
occurs in the middle of the even-numbered lines. Read downwards
we have forward execution, read upwards we have reverse execution.
For the reverse execution the reversal stack must contain sufficient
information to be used with the ordinary stack to "reconstitute"
the ordinary stack as it was before the forward execution.

Here is an execution of the program
[a b c] size 4 + dup succ =
which evaluates to false under ordinary evaluation. We need
to find that reversal stack which is needed to perform the
reverse execution of the program. It is the one in line 15.
The semantics for reverse execution can be read off from
this same trace.

Ordinary stack Program Reversal stack
1. -- --
2. [a b c]
3. -- [a b c] --
4. size
5. -- 3 -- [a b c]
6. 4
7. -- 3 4 -- [a b c]
8. +
9. -- 7 -- [a b c] 4
10. dup
11. -- 7 7 -- [a b c] 4
12. succ
13. -- 7 8 -- [a b c] 4
14. =
15. -- false -- [a b c] 4 7 8

The reversal stack must contain exactly enough information for
the reversal: no less, of course, but also no more in order to be
reversible by a quantum computer.

It would be interesting to devise operators which are symmetric
with respect to the two stacks and the direction of execution.
(This was expressed badly, maybe you know what I mean.)

- Manfred

> A single stack is fine for postfix and for concatentive languages.
> But it my be that it is not enough fore reversible compuutation.
> Maybe a different structure - perhaps two stacks:
> to compute 8 3 -
> push 8 and then 3 onto the normal stack as before.
> then remove both and push 5 onto the normal stack,
> but also push the 3 onto the reversal stack.
> So, the reverse of the subtraction operation has to be an addition
> (well, of course) with a twist: pop both stacks, push the ordinary
> sum of what as just been popped (that's the 8) onto the ordinary
> stack, and then push the 3 (which came from the reversal stack)
> onto the ordinary stack.

The main advantage I see of this "reversal stack" idea is that it allows
irreversible programs to become reversible, simply by changing the
interpretation of basic operators (i.e., -, +, zap, etc.); in essence, all
information that the program destroys is not actually destroyed, but instead
piled onto the reversal stack. For example, I suppose that the new "zap"
would simply transfer an item from the normal stack to the reversal stack.

This method is attractive because it does not require a change of
programming style, since all the operators do the same thing they've always
done, if you ignore the reversal stack. However, I suspect that in this kind
of system, the size of the reversal stack would increase rapidly, consuming
all the free space of the system. For example, suppose one is writing a loop
to subtract 3 from each element in an array; this might well be done using
"map", but in any case the code "3 -" will probably be involved. The problem
is that with each execution of "3 -", an additional item is added to the
reversal stack (a 3). This is all a great waste of space; because the 3 is
specified as a literal, it should not have to be preserved on the reversal
stack at all, much less multiple times.

But, perhaps a useful compromise would be to keep the reversal stack, but
let "zap" be essentially the only operator that communicates with it. In
other words, make the other operators reversible:

3 2 + == 5 2
3 2 - == 1 2
3 2 * == 6 2
(...)

This way, the user still has the option of disposing of garbage when he can
see no way to prevent creating it. Yet he will have to do so explicitly with
"zap". This might encourage a responsible programming style. Hopefully then
a small enough amount of garbage will be produced that it can reasonably be
kept on the system over a long time frame.

(As a side note, to cleanly subract 3 from the top item, the programmer
should do "-(3)", using that peculiar function application syntax, or in
other words, "[3] - {3}", which removes the "3" after it is finished being
used in the subtraction. This gets into that annoying issue again that,
theoretically, number literals should require []'s around them, yet it is
inconvenient)

A reversal stack is in theory unneccessary, since it is possible for the
programmer to bury his garbage data deep into the bottom of the normal
stack, instead of on the reversal stack. (Yet having a reversal stack does
make things cleaner)

> - Manfred

Thanks for your comments...

- Brent

Is anyone using Joy for real-world applications? If so, what are
some of these?

Asim

--- In concatenative@y..., Brent Kerby <iepos@t...> wrote:

> > A single stack is fine for postfix and for concatentive languages.
> > But it my be that it is not enough fore reversible compuutation.
> > Maybe a different structure - perhaps two stacks:
> > to compute 8 3 -
> > push 8 and then 3 onto the normal stack as before.
> > then remove both and push 5 onto the normal stack,
> > but also push the 3 onto the reversal stack.
> > So, the reverse of the subtraction operation has to be an addition
> > (well, of course) with a twist: pop both stacks, push the ordinary
> > sum of what as just been popped (that's the 8) onto the ordinary
> > stack, and then push the 3 (which came from the reversal stack)
> > onto the ordinary stack.
>
> The main advantage I see of this "reversal stack" idea is that it

allows

> irreversible programs to become reversible, simply by changing the
> interpretation of basic operators (i.e., -, +, zap, etc.); in

essence, all

> information that the program destroys is not actually destroyed,

but instead

> piled onto the reversal stack. For example, I suppose that the

new "zap"

> would simply transfer an item from the normal stack to the reversal

stack.

>
> This method is attractive because it does not require a change of
> programming style, since all the operators do the same thing

they've always

> done, if you ignore the reversal stack. However, I suspect that in

this kind

> of system, the size of the reversal stack would increase rapidly,

consuming

> all the free space of the system. For example, suppose one is

writing a loop

> to subtract 3 from each element in an array; this might well be

done using

> "map", but in any case the code "3 -" will probably be involved.

The problem

> is that with each execution of "3 -", an additional item is added

to the

> reversal stack (a 3). This is all a great waste of space; because

the 3 is

> specified as a literal, it should not have to be preserved on the

reversal

> stack at all, much less multiple times.
>
> But, perhaps a useful compromise would be to keep the reversal

stack, but

> let "zap" be essentially the only operator that communicates with

it. In

> other words, make the other operators reversible:
>
> 3 2 + == 5 2
> 3 2 - == 1 2
> 3 2 * == 6 2
> (...)
>
> This way, the user still has the option of disposing of garbage

when he can

> see no way to prevent creating it. Yet he will have to do so

explicitly with

> "zap". This might encourage a responsible programming style.

Hopefully then

> a small enough amount of garbage will be produced that it can

reasonably be

> kept on the system over a long time frame.
>

Unless you had a way of recycling data the amount of garbage would
remain the same. In fact if the garbage kept accumulating on the main
stack that would prevent you from accessing data that isn't garbage.
On the other hand explicit use of zap isn't very efficient - you'd
pretty much have to use it after every operation that produces
garbage.

The way I see it is that it's not garbage that's the problem - it's
introduction of new values. From what I read about reversible
computing in the past few days it seems that every operation needs to
have (at least?) as many outputs as it has inputs. This makes sense
and if you have a small number of values to keep track of recycling
of garbage is possible although difficult. By introducing new values
into the system the overall complexity grows quickly.

So maybe instead of putting new values onto the stack maybe taking
some garbage from the garbage stack and transforming it into
something usable is a better option? Think of it this way - if the
garbage value is known all it takes is a sequence of bit
transformation instructions to turn the garbage value into something
useful - the operation is still reversible and the garbage value can
be reproduced. This wouldn't work if garbage is unknown.

Interesting topic by the way. I wasn't aware of the importance of
reversible computation until you pointed it out. A few months ago I
bought a book on quantum computing just haven't got around to reading
it yet.

> (As a side note, to cleanly subract 3 from the top item, the

programmer

> should do "-(3)", using that peculiar function application syntax,

or in

> other words, "[3] - {3}", which removes the "3" after it is

finished being

> used in the subtraction. This gets into that annoying issue again

that,

> theoretically, number literals should require []'s around them, yet

it is

> inconvenient)
>

This is just my opinion but I don't like the idea of mixing
reversible and irreversible operations in the same language - the
code would look very ugly and you'd lose the benefits of having a
reversible system. There are some operations that can't be reversed
like I/O for example and possibly some that may have to be
irreversible to be useful but I don't see the point of having both
reversible and irreversible addition in the same system.

> A reversal stack is in theory unneccessary, since it is possible

for the

> programmer to bury his garbage data deep into the bottom of the

normal

> stack, instead of on the reversal stack. (Yet having a reversal

stack does

> make things cleaner)
>
> > - Manfred
>
> Thanks for your comments...
>
> - Brent

Ivan

--- In concatenative@y..., Asim Jalis <asimjalis@a...> wrote:

> Is anyone using Joy for real-world applications? If so, what are
> some of these?
>

Someone please correct me if I'm wrong but I don't think anyone is
using Joy for any serious applications right now.
I'm sure many members of this message board would like to but the
current Joy interpreter is fairly limited and very slow.
Eventually someone will write a new Joy interpreter/compiler.

> Asim

Ivan

e1_t scripsit:

> I'm sure many members of this message board would like to but the
> current Joy interpreter is fairly limited and very slow.

"Slow", I can't argue with, but please note that Joy1 provides the
same programming facilities as ISO (ANSI) C, with the exception of
the wide-string and locale-related library calls.

--
Deshil Holles eamus. Deshil Holles eamus. Deshil Holles eamus.
Send us, bright one, light one, Horhorn, quickening, and wombfruit. (3x)
Hoopsa, boyaboy, hoopsa! Hoopsa, boyaboy, hoopsa! Hoopsa, boyaboy, hoopsa!
-- Joyce, _Ulysses_, "Oxen of the Sun" jcowan@...

--- In concatenative@y..., John Cowan <cowan@c...> wrote:

> e1_t scripsit:
>
> > I'm sure many members of this message board would like to but the
> > current Joy interpreter is fairly limited and very slow.
>
> "Slow", I can't argue with, but please note that Joy1 provides the
> same programming facilities as ISO (ANSI) C, with the exception of
> the wide-string and locale-related library calls.
>

What I meant by limited is that it provides no foreign language
interface, no graphics, sockets, heaps of things - really foreign
language interface is the biggest problem cause all the other things
could be added through that (you could just map a library into Joy).
A language needs those things to be useful in the real world.

Ivan

e1_t scripsit:

> What I meant by limited is that it provides no foreign language
> interface, no graphics, sockets, heaps of things - really foreign
> language interface is the biggest problem cause all the other things
> could be added through that (you could just map a library into Joy).

I agree, except for the unfortunate equation:

FFI + Interpreter + Portability = 0

But people do write useful programs in pure ANSI C.

It would be easy to and a socket interface, though.

--
John Cowan
jcowan@...
I am a member of a civilization. --David Brin

On Wed, 21 Aug 2002, Brent Kerby wrote:

[..]
> One other exciting question in regard to this reversible system is: does
> this mean we can do complex Church numerals arithmetic? I would see no
> reason why not, because reversibility enables us to simulate the negative
> numbers, and also fractional, irrational, and imaginary. It would be quite
> interesting to see precisely how this would work.

I happened to be reading a paper by Paul Bailes:

http://www.itee.uq.au/~paul/papers/F-3-txt-iee.pdf
"Programming without Data -
Toward a Totally Functional Programming Style"

which gave a reference that I have not read but which might be of
interest to you (if you do not know it already):

Boehm, H. and Cartwright, R.,
"Exact Real Arithmetic: Formulating Real Numbers as Functions",
in Turner, D.A. (ed)
_Research Topics in Functional Programming_,
Addison-Wesley 1990.

Bailes writes that Boehm and Cartwright represent a real number by
a function which computes the number to any required precision.
Whether such functions are reversible I do not know.

I hope this is of some use.

- Manfred

Manfred von Thun scripsit:

> http://www.itee.uq.au/~paul/papers/F-3-txt-iee.pdf

That's http://www.itee.uq.edu.au/~paul/papers/F-3-txt-ieee.pdf
(Moral: always copy and paste URLs, never retype them.)

--
All Gaul is divided into three parts: the part John Cowan
that cooks with lard and goose fat, the part www.ccil.org/~cowan
that cooks with olive oil, and the part that www.reutershealth.com
cooks with butter. -- David Chessler jcowan@...

On Fri, 30 Aug 2002, John Cowan wrote:

> Manfred von Thun scripsit:
>
> > http://www.itee.uq.au/~paul/papers/F-3-txt-iee.pdf
>
> That's http://www.itee.uq.edu.au/~paul/papers/F-3-txt-ieee.pdf
> (Moral: always copy and paste URLs, never retype them.)

Ooops, thanks, yes, sorry.

You may not know that I still live in the early 80's, last century:
VT 100 terminal, Lynx web browser, VMS operating system, Pine mailer.
No copy and paste for us pedestrians !

- Manfred

Manfred von Thun scripsit:

> VT 100 terminal, Lynx web browser, VMS operating system, Pine mailer.
> No copy and paste for us pedestrians !

Ouch. Can't you at least replace the terminal with some boat anchor of
a PC and run a terminal program on it?

--
John Cowan jcowan@...
http://www.ccil.org/~cowan http://www.reutershealth.com
Thor Heyerdahl recounts his attempt to prove Rudyard Kipling's theory
that the mongoose first came to India on a raft from Polynesia.
--blurb for _Rikki-Kon-Tiki-Tavi_

More on Reversible Joy

Brent Kerby — 2002-08-21 17:12:34

Manfred von Thun — 2002-08-23 02:06:58

Manfred von Thun — 2002-08-26 03:54:41

Brent Kerby — 2002-08-26 15:37:16

Asim Jalis — 2002-08-26 18:21:01

e1_t — 2002-08-26 23:49:12

e1_t — 2002-08-27 00:09:52

John Cowan — 2002-08-27 02:05:00

e1_t — 2002-08-27 03:47:03

John Cowan — 2002-08-27 15:33:48

Manfred von Thun — 2002-08-30 04:26:33

John Cowan — 2002-08-30 05:14:16

Manfred von Thun — 2002-08-30 05:25:42

John Cowan — 2002-08-30 05:47:49