# More on Reversible Joy

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

    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

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

    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

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

    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

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

    > 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

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

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

    some of these?

    Asim

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

    --- 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

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

    --- 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

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

    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@...

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

    --- 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

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

    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

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

    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

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

    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@...

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

    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

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

    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_