# Re: [stack] Re: More on Reversible Joy

## Brent Kerby — 2002-08-27 00:27:57

    > 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, it doesn't really matter fundamentally whether the garbage

    is forced to be kept on the main stack, or on a garbage stack (i.e., where

    "zap" takes the data). Either way, whenever garbage is produced and the

    programmer doesn't want to deal with it anymore, he must explicitly move it

    (either to the bottom of the stack, or to the garbage stack).

    Your statement suggests that you think this burden on the programmer is

    unacceptable. Yet, I believe it has been shown that the Fourier transform

    can be done without producing a single piece of garbage. Also, I seem to

    recall that a purely reversible quicksort algorithm exists. So, perhaps it

    is not so bad to require programmers to explicitly dispose of garbage,

    seeing that even fairly complex algorithms can be written without generating

    any garbage.

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

     Ahh! This is quite a clever idea, to recycle garbage. There are probably few

    applications where it is acceptable to start with totally arbitrary data.

    However, one example might be for a square root approximation; you could

    recycle a piece of garbage to use as the initial approximation. As Baker has

    mentioned, the final approximation for a square root (by one algorithm, at

    least) still encodes the initial approximation in its low-order bits, and so

    is reversible, provided bits have not been truncated do to rounding. This

    brings up a disturbing problem: rounding is not reversable, yet it pervades

    many numerical algorithms; is it feasable to keep from rounding?

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

     Right, if you know what your garbage is, then it is possible to reuse it, or

    even to reversibly destroy it. That's why, for example, adding a literal

    using the reversible "+" (where "[3] [2] +  ==  [5] [2]") doesn't have to

    produce any garbage:

      [3] + {3}

    Here we add 3 to the top of the stack, and then cleanly destroy the unneeded

    3 using {}s. The {} construct does not destroy information any more than

    []'s create new information; the information about the stack item removed by

    {} is still present in the code, just as the information about the stack

    item pushed by [] is present in the code from the beginning.

    Similarly, "dup" is acceptable because it creates no new information, even

    though it creates a new stack item. Also "undup" destroys no information,

    even though it destroys a stack item.

     > 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

     It seems to me that for most I/O you can approximate reversibility; for

    instance, to reverse a statement that output some text to the user, you can

    simply output the same thing except with the text bracketed somehow or

    prepended with some text indicating that it is a reverse output; or you

    could do nothing at all (that might be acceptable). But you're right that

    some I/O could be inherently irreversible; for example, if your system

    controls a nuclear missle launching device, and the system launches the

    missile, then there is no way to acceptably reverse that operation :-)

     > but I don't see the point of having both

    > reversible and irreversible addition in the same system.

     Right. In fact, there's arguably no point to having an irreversible addition

    at all.

     > > - Brent

    >

    > Ivan

     - Brent

## e1_t — 2002-08-27 03:41:43

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

     > > 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, it doesn't really matter fundamentally whether

     the garbage

     > is forced to be kept on the main stack, or on a garbage stack

     (i.e., where

     > "zap" takes the data). Either way, whenever garbage is produced and

     the

     > programmer doesn't want to deal with it anymore, he must explicitly

     move it

     > (either to the bottom of the stack, or to the garbage stack).

    >

    > Your statement suggests that you think this burden on the

     programmer is

     > unacceptable. Yet, I believe it has been shown that the Fourier

     transform

     > can be done without producing a single piece of garbage. Also, I

     seem to

     > recall that a purely reversible quicksort algorithm exists. So,

     perhaps it

     > is not so bad to require programmers to explicitly dispose of

     garbage,

     > seeing that even fairly complex algorithms can be written without

     generating

     > any garbage.

    >

     What I meant is that words/functions in concatenative languages

    generally operate on the first few elements of the stack. If every

    word created garbage and placed it on the stack garbage would get in

    the way and you'd have to do heaps of unecessary stack manipulations

    to get it out of the way. This just complicates things.

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

    >

    > Ahh! This is quite a clever idea, to recycle garbage. There are

     probably few

     > applications where it is acceptable to start with totally arbitrary

     data.

     > However, one example might be for a square root approximation; you

     could

     > recycle a piece of garbage to use as the initial approximation. As

     Baker has

     > mentioned, the final approximation for a square root (by one

     algorithm, at

     > least) still encodes the initial approximation in its low-order

     bits, and so

     > is reversible, provided bits have not been truncated do to

     rounding. This

     > brings up a disturbing problem: rounding is not reversable, yet it

     pervades

     > many numerical algorithms; is it feasable to keep from rounding?

    >

     Why wouldn't truncation or rounding be reversible? You could create

    garbage value containing information on the truncated bits or

    rounding information.

    Bigger problem I think is that floating point is inprecise and

    there's always a small error present. Eventually that error grows and

    the result cannot be reversed. Floating point may not be suitable for

    reversible systems.

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

    >

    > Right, if you know what your garbage is, then it is possible to

     reuse it, or

     > even to reversibly destroy it. That's why, for example, adding a

     literal

     > using the reversible "+" (where "[3] [2] +  ==  [5] [2]") doesn't

     have to

     > produce any garbage:

    >

    >   [3] + {3}

    >

    > Here we add 3 to the top of the stack, and then cleanly destroy the

     unneeded

     > 3 using {}s. The {} construct does not destroy information any more

     than

     > []'s create new information; the information about the stack item

     removed by

    If by add to the top of the stack you mean add the 3's together how

    is this different from normal addition? The operation isn't

    reversible. As for creating and deleting data - that's what it

    appears like at the high-level. At the low-level there could be some

    way of remapping the second stack or converting the values so that

    nothing gets destroyed or created.

     > {} is still present in the code, just as the information about the

     stack

     > item pushed by [] is present in the code from the beginning.

    > Similarly, "dup" is acceptable because it creates no new

     information, even

     > though it creates a new stack item. Also "undup" destroys no

     information,

     > even though it destroys a stack item.

    >

     What happens if undup is used on something that hasn't been dup-ed?

    Or what happens if you dup-licate a value then perform some

    operations on it and then undup it? There's a loss of information

    either way.

     >

    > - Brent

     Ivan

## Brent Kerby — 2002-08-27 06:54:38

    > What I meant is that words/functions in concatenative languages

    > generally operate on the first few elements of the stack. If every

    > word created garbage and placed it on the stack garbage would get in

    > the way and you'd have to do heaps of unecessary stack manipulations

    > to get it out of the way.

     Hmm ... "heaps" doesn't seem accurate to me; it only takes a single "buryn"

    to stash a stack item to the bottom, and perhaps a word could be added

    specifically to bury the top item to the very bottom of the stack; then it

    would be just as easy to bury the item as it would to zap it, right? But

    you're right; if there is garbage being created with every operation, then

    it is going to be a big pain to deal with.

    However, if garbage is being created with every operation, then there's a

    bigger problem: the system's storage will soon be exhausted. It is not a

    good idea to encourage the programmer to leave garbage everywhere and expect

    that the low-level system can magically clean it up (although it can clean

    up most of it, by interrupting the program, making a safe copy of the

    non-garbage data, and then uncomputing the entire the program back to the

    beginning). It is much better to encourage a true reversible style at all

    levels of the system by keeping garbage creation at a minimum.

     > Why wouldn't truncation or rounding be reversible? You could create

    > garbage value containing information on the truncated bits or

    > rounding information.

     Well, I guess in the sense that you use "reversible", rounding is

    reversible, but so is every other computational operation. Really, rounding

    discards information; it can only be reversible if the information is not

    really discarded (e.g., by putting it on a garbage stack). Trying to store

    such massive amounts on the garbage stack causes a severe problem: your

    system storage will run out. It is not correct to try to accumulate large

    amounts of garbage and then imagine that there is some sneaky low-level

    trick to reuse the space without destroying the garbage.

     > As for creating and deleting data - that's what it

    > appears like at the high-level. At the low-level there could be some

    > way of remapping the second stack or converting the values so that

    > nothing gets destroyed or created.

     Why have a high-level and a low-level? Why have a reversible system

    simulating an irreversible system? That approach is doomed to only limited

    success, because the only way to delete unknown data is to actually export

    it out of the system in some form (either heat, sound, light, etc.) which

    unavoidably causes energy loss; to save it to a garbage stack only

    procrastinates the problem. The only true solution is to not create garbage

    in the first place, or at least keep it at a minimum.

     > What happens if undup is used on something that hasn't been dup-ed?

     It causes an error, just as dividing by zero would cause an error. Of

    course, there are a variety of designs as to how exactly the system handles

    errors (probably it would halt the program and let the programmer inspect

    the system to see what went wrong, allowing him also to backtrack through

    the program to see what happened earlier).

     > Or what happens if you dup-licate a value then perform some

    > operations on it and then undup it? There's a loss of information

    > either way.

     Once again, an error occurs. There is no loss of information because the

    "undup" operation is not allowed to be carried out.

     > > - Brent

    >

    > Ivan

     - Brent

## e1_t — 2002-08-27 09:12:38

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

     > > What I meant is that words/functions in concatenative languages

    > > generally operate on the first few elements of the stack. If every

    > > word created garbage and placed it on the stack garbage would get

     in

     > > the way and you'd have to do heaps of unecessary stack

     manipulations

     > > to get it out of the way.

    >

    > Hmm ... "heaps" doesn't seem accurate to me; it only takes a

     single "buryn"

     > to stash a stack item to the bottom, and perhaps a word could be

     added

     > specifically to bury the top item to the very bottom of the stack;

     then it

    bury-ing is a non-trivial stack operation and shouldn't be necessary

    for general purpose programming - like I said it would just

    complicate the system not to mention it would have to be used after

    every operation that produces garbage.

     > would be just as easy to bury the item as it would to zap it,

     right? But

     > you're right; if there is garbage being created with every

     operation, then

     > it is going to be a big pain to deal with.

    >

    > However, if garbage is being created with every operation, then

     there's a

     > bigger problem: the system's storage will soon be exhausted. It is

     not a

    That's why there should be some way to recycle garbage. Garbage

    doesn't really get "created" - it's just that one of the inputs gets

    transformed into garbage while the other is the result of the

    operation.

     > good idea to encourage the programmer to leave garbage everywhere

     and expect

     > that the low-level system can magically clean it up (although it

     can clean

     > up most of it, by interrupting the program, making a safe copy of

     the

     > non-garbage data, and then uncomputing the entire the program back

     to the

     > beginning). It is much better to encourage a true reversible style

     at all

     > levels of the system by keeping garbage creation at a minimum.

    >

    > > Why wouldn't truncation or rounding be reversible? You could

     create

     > > garbage value containing information on the truncated bits or

    > > rounding information.

    >

    > Well, I guess in the sense that you use "reversible", rounding is

    > reversible, but so is every other computational operation. Really,

     rounding

     > discards information; it can only be reversible if the information

     is not

    Well if you're making a reversible system then all the operations

    have to be reversible - rounding is no different from addition in

    this case. Using your own example if 3 2 + results in 5 2 on the

    stack then why wouldn't rounding of 4.3 result in 4.0 as a result and

    0.3 as garbage?

     > really discarded (e.g., by putting it on a garbage stack). Trying

     to store

     > such massive amounts on the garbage stack causes a severe problem:

     your

     > system storage will run out. It is not correct to try to accumulate

     large

     > amounts of garbage and then imagine that there is some sneaky low-

     level

     > trick to reuse the space without destroying the garbage.

    >

     Creation of new values shouldn't be allowed in such a system - only

    recycling. Now it's either up to the programmer to do it himself or

    there could be a recycler that does it for him - in a way that's

    similar to garbage collection - a programmer can do it but it's a lot

    simpler to just have a garbage collector do it for him. It's in fact

    more crucial than garbage collection because freeing data is a

    simpler concept then reusing garbage data.

    For that matter just about every functional language hides the

    details of what actually goes on in the system - the implementation

    is far from functional but to the programmer it appears to be

    functional.

     > > As for creating and deleting data - that's what it

    > > appears like at the high-level. At the low-level there could be

     some

     > > way of remapping the second stack or converting the values so that

    > > nothing gets destroyed or created.

    >

    > Why have a high-level and a low-level? Why have a reversible system

    > simulating an irreversible system? That approach is doomed to only

     limited

    You're not simulating an irreversible system.

    What if you were to create a processor with a reversible instruction

    set?

    Or even if you're not, how would you write such a language on a

    conventional processor (regardless of what language you're writing it

    in)?

    By low-level I mean the actual implementation of the language - or in

    other words what happens behind the scenes.

    How is it that in all languages with garbage collection you can just

    keep creating stuff without freeing it and never run out of memory

    (well of course you CAN run out of memory if all of the allocated

    stuff is still in use but normally that's not the case and generally

    you'd only end up with such a program if your goal was to run out of

    memory)?

    The garbage collector gets rid of all the stuff thats not in use

    behind the scenes - similarly a recycler could do the same for a

    reversible language.

     > success, because the only way to delete unknown data is to actually

     export

     > it out of the system in some form (either heat, sound, light, etc.)

     which

     > unavoidably causes energy loss; to save it to a garbage stack only

    > procrastinates the problem. The only true solution is to not create

     garbage

     > in the first place, or at least keep it at a minimum.

    >

     Not creating garbage is impossible and minimizing it and recycling it

    is the whole idea.

     > > What happens if undup is used on something that hasn't been dup-

     ed?

     >

    > It causes an error, just as dividing by zero would cause an error.

     Of

     > course, there are a variety of designs as to how exactly the system

     handles

     > errors (probably it would halt the program and let the programmer

     inspect

     > the system to see what went wrong, allowing him also to backtrack

     through

     > the program to see what happened earlier).

    >

    > > Or what happens if you dup-licate a value then perform some

    > > operations on it and then undup it? There's a loss of information

    > > either way.

    >

    > Once again, an error occurs. There is no loss of information

     because the

     > "undup" operation is not allowed to be carried out.

    >

     So dup does in fact create a value and undup can only remove it if no

    operations are peformed on it.

    So why would you dup a value then if you can't do anything with it?

     > > > - Brent

    > >

    > > Ivan

    >

    > - Brent

## Brent Kerby — 2002-08-27 16:21:10

    > How is it that in all languages with garbage collection you can just

    > keep creating stuff without freeing it and never run out of memory

    > (well of course you CAN run out of memory if all of the allocated

    > stuff is still in use but normally that's not the case and generally

    > you'd only end up with such a program if your goal was to run out of

    > memory)?

    > The garbage collector gets rid of all the stuff thats not in use

    > behind the scenes - similarly a recycler could do the same for a

    > reversible language.

     If I understand correctly, the laws of thermodynamics forbid the

    construction of such a recycler. The problem you run up against is that in a

    reversible system you must hold on to the garbage, because it is necessary

    in order to execute backward. If at any point you destroy the garbage, it

    will not be possible to reverse execution anymore. If you were thinking of

    "reusing" the garbage data by selectively toggling its bits to make it what

    you wanted, that is impossible in a reversible system (if you try to do it

    using a conditional, for example, you will have to preserve a bit telling

    whether the branch was taken or not, thus preserving the garbage). The only

    way to destroy the garbage is to unrun the program that generated it.

     > Not creating garbage is impossible

     Are you sure ... ? From what I've read, it seems like it may be feasible. It

    requires a dramatic change in programming style (even loops and conditionals

    have to work a bit differently, to ensure their reversibility), and certain

    algorithms may become harder, but I don't think it's been proven impossible

    yet; it fact, it looks promising.

    By the way, Baker's papers seem to have been taken off the original server,

    but you can get them (or specifically the one on reversible computing) here:

    http://home.pipeline.com/~hbaker1/ReverseGC.html

    - Brent

## e1_t — 2002-08-27 23:29:30

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

     > > How is it that in all languages with garbage collection you can

     just

     > > keep creating stuff without freeing it and never run out of memory

    > > (well of course you CAN run out of memory if all of the allocated

    > > stuff is still in use but normally that's not the case and

     generally

     > > you'd only end up with such a program if your goal was to run out

     of

     > > memory)?

    > > The garbage collector gets rid of all the stuff thats not in use

    > > behind the scenes - similarly a recycler could do the same for a

    > > reversible language.

    >

    > If I understand correctly, the laws of thermodynamics forbid the

    > construction of such a recycler. The problem you run up against is

     that in a

     > reversible system you must hold on to the garbage, because it is

     necessary

     > in order to execute backward. If at any point you destroy the

     garbage, it

     > will not be possible to reverse execution anymore. If you were

     thinking of

     > "reusing" the garbage data by selectively toggling its bits to make

     it what

     > you wanted, that is impossible in a reversible system (if you try

     to do it

     > using a conditional, for example, you will have to preserve a bit

     telling

     > whether the branch was taken or not, thus preserving the garbage).

     The only

     > way to destroy the garbage is to unrun the program that generated

     it.

    You seem to be confusing the concept of a recycler with that of a

    garbage collector. As I mentioned earlier a recycler does not destroy

    garbage - it recycles it and it's reversible - that was the whole

    point.

    I used garbage collectors as an example of a system that does a

    similar thing for conventional irreversible systems to counter your

    statement that it's not a good idea to encourage the programmer to

    leave garbage anywhere and expect it to magically disappear because

    that's exactly what garbage collectors (and recyclers) are supposed

    to do.

    Manually recycling garbage would be a difficult task - much more so

    than freeing allocated memory is in current irreversible systems.

     >

    > > Not creating garbage is impossible

    >

    > Are you sure ... ? From what I've read, it seems like it may be

     feasible. It

    Well if you think about it you can't have reversible addition

    operator that doesn't create garbage - it's just not possible. All

    the papers on reversible computing that I've seen so far say that

    every reversible operation needs to have at least as many outputs as

    inputs. Addition has only one output therefore the second output has

    to be garbage.

     > requires a dramatic change in programming style (even loops and

     conditionals

     > have to work a bit differently, to ensure their reversibility), and

     certain

     > algorithms may become harder, but I don't think it's been proven

     impossible

    If garbage is recycled yes, it's possible - but like I said you can't

    have addition operator that has just 1 ouput and is reversible -

    similarly you can't have addition with two outputs that doesn't

    create garbage. Sure you can couple it with some other potentially

    useful operation (for example + can perform both addition and

    subtraction at the same time - you can still reproduce the inputs

    from the outputs so the operation is reversible. However the second

    output is still garbage if it's not needed for the computation).

     > yet; it fact, it looks promising.

    >

    > By the way, Baker's papers seem to have been taken off the original

     server,

     > but you can get them (or specifically the one on reversible

     computing) here:

     > http://home.pipeline.com/~hbaker1/ReverseGC.html

    >

     That very paper talks of the exact same thing I mentioned - only

    instead of calling it a recycler they call it a reversible garbage

    collector. The paper also provides a perfect template for a

    reversible instruction set.

    Thanks for the link.

     > - Brent

     Ivan

## Brent Kerby — 2002-08-30 17:01:44

    Sorry, Ivan, that this reply has taken so long ... I meant to send it much

    sooner, but a slight computer problem erased most of it, and so I'm

    rewriting it now hoping it will make sense.

     > > > Not creating garbage is impossible

    > >

    > > Are you sure ... ? From what I've read, it seems like it may be

    > feasible. It

    >

    > Well if you think about it you can't have reversible addition

    > operator that doesn't create garbage - it's just not possible.

     Sure it is. The addition operator naturally creates two outputs, and both

    are valuable; it's just that you're used to the control one (the one that is

    identical to the input) being useless and thus garbage. However, it is

    actually quite useful in many cases. For example (illustrating here the "*"

    operation rather than "+"; I hope you don't mind), to compute the

    polynomial "4x^2 + 3x + 1" you can do this (assuming "x" is on the top of

    stack):

      [4] swap * dip(+(3)) * dip(+(1))

    Here, we compute "4x" and then add 3 to it, and then multiply by "x" again

    and add 1. It is quite convenient that the "*" operator preserves the "x",

    since otherwise we would have to hassle with duplicating the "x". Here's how

    an irreversible system might do it:

      [4] swap [*] sip [3 +] dip * 1 +

    Granted, both versions seem too big for what they do, but the reversible

    version is not really any worse or harder to make in this case.

    This example started me thinking about a possible way to improve stack

    manipulation ... I was thinking that maybe it would be good to have the

    return stack be explicit, by having operators to transfer an item from the

    main stack to the return stack or vice versa (like in FORTH). Then I was

    thinking that it could be convenient for parameters sometimes to be passed

    through the return stack; in particular, for "*" and "+" it would be

    convenient for the control parameters (i.e., the ones that are not modified)

    to be passed through the return stack. And, in general, I think it could be

    a good convention for control parameters to generally be passed through the

    return stack. Using this idea, the example could be rewritten this way:

      [4] * +(3) * +(1)

    This expects "x" as a parameter on the return stack (and it remains there

    the whole computation). First it computes "4x", then adds three, multiplies

    by "x" again, and adds 1. Seems pretty slick. Of course, the language has

    now been tailored to this example, so more examples would be in order, to

    see if it holds up.

     > If garbage is recycled yes, it's possible - but like I said you can't

    > have addition operator that has just 1 ouput and is reversible -

    > similarly you can't have addition with two outputs that doesn't

    > create garbage.

     As they say, "One man's trash is another man's treasure". To me the control

    output of addition is very useful in most circumstances and is rarely to be

    considered garbage. The addition operator naturally has two outputs; it's

    just that we're used to a system that destroys one of them.

     > Sure you can couple it with some other potentially

    > useful operation (for example + can perform both addition and

    > subtraction at the same time - you can still reproduce the inputs

    > from the outputs so the operation is reversible.

     I assume you're talking about a "+-" operator like this:

      7 2 +-  == 9 5

    This is quite an interesting operator. I seem to remember it being useful in

    the Fourier transform, among other things. It is reversible, and so we'd

    hope that it could be constructed from the reversible (2-output) addition

    and subraction operators. If we make a naive attempt, we get something like

    this (reverting to the no-return-stack versions of "+" and "-"):

      over dip(+) swap -

    And it would work like this:

       7 2 over dip(+) swap -

    == 7 2 7 dip(+) swap -

    == 9 2 7 swap -

    == 9 7 2 -

    == 9 5 2

    But this unfortunately produces a garbage "2". You might say, "Garbage is

    inevitable. We might as well just stop here and accept it". However, a

    method exists to do the operation without producing garbage; we just have to

    look a bit harder:

      - *(2) swap +

    It works like this:

       7 2 - *(2) swap +

    == 5 2 *(2) swap +

    == 5 4 swap +

    == 4 5 +

    == 9 5

    The beautiful thing about this construction is that it is perfectly

    reversible. You get the reverse simply by running the whole thing backwards

    (inverting each primitive along the way):

      - swap /(2) +

    I hope that now you can see the beauty of the 2-output "+" and "-": with the

    2-output ones, "+" and "-" are the reverse of each other (either one can

    exactly undo the other), but this is not the case with either a 1-output

    version or a 3-output version. But, you seem very reluctant to agree with

    anything I say, so I won't get my hopes up ...

     > > [Baker's ReverseGC paper]

    >

    > That very paper talks of the exact same thing I mentioned - only

    > instead of calling it a recycler they call it a reversible garbage

    > collector.

     You're right. This paper, among others, shows that you can get rid of

    garbage by reversing the process that created it, and it proposes this kind

    of recycling to be done perhaps periodically and automatically. This

    approach works and may be useful in many cases; however, there is a problem

    with it: what do you do when the user wants to step the execution back a

    little bit, but the needed garbage has already been recycled. When that

    happens, it looks like it will be necessary for the system to recreate the

    garbage. This whole system could then get quite complex; yet, I admit it

    would probably still be manageable, and it could be useful.

    But it seems so much better just to entirely throw out the unnecessary

    complexity of garbage recycling, by designing algorithms that produce no

    garbage, or an amount small enough to be managed by the user. A

    general-purpose system will have to have some means of dissipating some

    garbage, since if it has a means of input (through the keyboard, mouse,

    etc.) then information could only increase indefinitely (until storage is

    exhausted) unless there is some means of dissipation. Perhaps information

    could be dissipated in the form of light, which would scatter throughout the

    room and present less of a local heating problem; but, I don't know much

    about the practicality of this (there would have to be a means of converting

    electrical energy to light without producing heat; I'm not sure if this is

    possible. Another option is to use photonic computers).

     > > - Brent

    >

    > Ivan

     - Brent

    [Non-text portions of this message have been removed]

## Ivan Tomac — 2002-09-10 06:35:34

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

     > > > > Not creating garbage is impossible

    > > >

    > > > Are you sure ... ? From what I've read, it seems like it may be

    > > feasible. It

    > >

    > > Well if you think about it you can't have reversible addition

    > > operator that doesn't create garbage - it's just not possible.

    >

    > Sure it is. The addition operator naturally creates two outputs,

     and both

    You are coupling addition with an identity operation.

     > are valuable; it's just that you're used to the control one (the

     one that is

     > identical to the input) being useless and thus garbage. However, it

     is

     > actually quite useful in many cases. For example (illustrating here

     the "*"

    Like I said addition can be coupled with another potentially useful

    operation but in many cases that other operation is not necessary for

    the computation itself which makes it garbage. Sure, garbage can

    somehow be transformed into something useful and that's the whole

    point of recycling whether you do it manually or not.

     > operation rather than "+"; I hope you don't mind), to compute the

    > polynomial "4x^2 + 3x + 1" you can do this (assuming "x" is on the

     top of

     > stack):

    >

    >   [4] swap * dip(+(3)) * dip(+(1))

    >

    > Here, we compute "4x" and then add 3 to it, and then multiply

     by "x" again

     > and add 1. It is quite convenient that the "*" operator preserves

     the "x",

     > since otherwise we would have to hassle with duplicating the "x".

     Here's how

     > an irreversible system might do it:

    >

    >   [4] swap [*] sip [3 +] dip * 1 +

    >

    > Granted, both versions seem too big for what they do, but the

     reversible

     > version is not really any worse or harder to make in this case.

    >

    > This example started me thinking about a possible way to improve

     stack

     > manipulation ... I was thinking that maybe it would be good to have

     the

     > return stack be explicit, by having operators to transfer an item

     from the

     > main stack to the return stack or vice versa (like in FORTH). Then

     I was

     > thinking that it could be convenient for parameters sometimes to be

     passed

     > through the return stack; in particular, for "*" and "+" it would be

    > convenient for the control parameters (i.e., the ones that are not

     modified)

    I think a more elegant approach would be to give programmers the

    ability to create auxilary stacks.

    This is slightly off topic but I've actually been thinking about this

    concept of multiple auxilary stacks for a bit and it might even be a

    way to simulate primitive types in a language like Forth without

    turning it into a typed language as well as increase it's potential

    for pipelining and parallel execution of code - ANS-Forth standard in

    fact allows for a Forth implementation to have a separate floating

    point stack and adding types to a typeless language in this manner is

    simply an extension of this concept.

    This would only work well for primitive types and not so well for

    more abstract ones.

     > to be passed through the return stack. And, in general, I think it

     could be

     > a good convention for control parameters to generally be passed

     through the

     > return stack. Using this idea, the example could be rewritten this

     way:

     >

    >   [4] * +(3) * +(1)

    >

    > This expects "x" as a parameter on the return stack (and it remains

     there

     > the whole computation). First it computes "4x", then adds three,

     multiplies

     > by "x" again, and adds 1. Seems pretty slick. Of course, the

     language has

     > now been tailored to this example, so more examples would be in

     order, to

     > see if it holds up.

    >

    > > If garbage is recycled yes, it's possible - but like I said you

     can't

     > > have addition operator that has just 1 ouput and is reversible -

    > > similarly you can't have addition with two outputs that doesn't

    > > create garbage.

    >

    > As they say, "One man's trash is another man's treasure". To me the

     control

     > output of addition is very useful in most circumstances and is

     rarely to be

     > considered garbage. The addition operator naturally has two

     outputs; it's

     > just that we're used to a system that destroys one of them.

    >

    > > Sure you can couple it with some other potentially

    > > useful operation (for example + can perform both addition and

    > > subtraction at the same time - you can still reproduce the inputs

    > > from the outputs so the operation is reversible.

    >

    > I assume you're talking about a "+-" operator like this:

    >

    >   7 2 +-  == 9 5

    >

    > This is quite an interesting operator. I seem to remember it being

     useful in

     > the Fourier transform, among other things. It is reversible, and so

     we'd

     > hope that it could be constructed from the reversible (2-output)

     addition

     > and subraction operators. If we make a naive attempt, we get

     something like

     > this (reverting to the no-return-stack versions of "+" and "-"):

    >

    >   over dip(+) swap -

    >

    > And it would work like this:

    >

    >    7 2 over dip(+) swap -

    > == 7 2 7 dip(+) swap -

    > == 9 2 7 swap -

    > == 9 7 2 -

    > == 9 5 2

    >

    > But this unfortunately produces a garbage "2". You might

     say, "Garbage is

     > inevitable. We might as well just stop here and accept it".

     However, a

     > method exists to do the operation without producing garbage; we

     just have to

     > look a bit harder:

    >

    >   - *(2) swap +

    >

    > It works like this:

    >

    >    7 2 - *(2) swap +

    > == 5 2 *(2) swap +

    > == 5 4 swap +

    > == 4 5 +

    > == 9 5

    >

    > The beautiful thing about this construction is that it is perfectly

    > reversible. You get the reverse simply by running the whole thing

     backwards

     > (inverting each primitive along the way):

    >

    >   - swap /(2) +

    >

    > I hope that now you can see the beauty of the 2-output "+" and "-":

     with the

     > 2-output ones, "+" and "-" are the reverse of each other (either

     one can

     > exactly undo the other), but this is not the case with either a 1-

     output

     > version or a 3-output version. But, you seem very reluctant to

     agree with

     > anything I say, so I won't get my hopes up ...

    >

     I apologize. I was just expressing my thoughts on this, don't take it

    personally - I think the whole point of having message boards such as

    this one is to exchange ideas and thoughts.

    I don't disagree with most of the things you said - I just think we

    have a different point of view on some things.

    I think that pretty much all of what you said is useful but at a

    lower level (for a reversible assembly language, reversible Forth or

    a high-level language compiler/optimizer for reversible systems).

     > > > [Baker's ReverseGC paper]

    > >

    > > That very paper talks of the exact same thing I mentioned - only

    > > instead of calling it a recycler they call it a reversible garbage

    > > collector.

    >

    > You're right. This paper, among others, shows that you can get rid

     of

     > garbage by reversing the process that created it, and it proposes

     this kind

     > of recycling to be done perhaps periodically and automatically. This

    > approach works and may be useful in many cases; however, there is a

     problem

     > with it: what do you do when the user wants to step the execution

     back a

     > little bit, but the needed garbage has already been recycled. When

     that

     > happens, it looks like it will be necessary for the system to

     recreate the

     > garbage. This whole system could then get quite complex; yet, I

     admit it

    Not necessarily - the code itself would in fact be a lot simpler and

    more readable.

    I agree that many of the initial recyclers will probably be crude and

    very inefficient but eventually they will improve just like the

    compilers and garbage collectors for current generation of high-level

    languages have improved.

    Manual recycling will contribute to this. By finding and researching

    efficient algorithms to manually recycle garbage at the low level

    automatic recyclers and code optimizers for reversible systems will

    become more and more powerful by utilizing those algorithms and

    transforming inefficient but readable code into efficient but

    unreadable code.

     > would probably still be manageable, and it could be useful.

    >

    > But it seems so much better just to entirely throw out the

     unnecessary

     > complexity of garbage recycling, by designing algorithms that

     produce no

     > garbage, or an amount small enough to be managed by the user. A

    > general-purpose system will have to have some means of dissipating

     some

     > garbage, since if it has a means of input (through the keyboard,

     mouse,

     > etc.) then information could only increase indefinitely (until

     storage is

     > exhausted) unless there is some means of dissipation. Perhaps

     information

     > could be dissipated in the form of light, which would scatter

     throughout the

     > room and present less of a local heating problem; but, I don't know

     much

     > about the practicality of this (there would have to be a means of

     converting

     > electrical energy to light without producing heat; I'm not sure if

     this is

     > possible. Another option is to use photonic computers).

     The idea of scattering garbage throughout the room in form of light

    sounds interesting - it would to some extent integrate the computer

    with the room itself and with the outside world making input and

    output reversible at least to a certain extent.

    That actually gave me an idea.

    This may be very impractical and difficult to use but I think it

    would be interesting if someone tried to develop a reversible input

    device - for example a keyboard where the keys would constantly get

    remapped to reflect what keys have been pressed before.

     > - Brent

    >

     Ivan

## Brent Kerby — 2002-09-10 17:20:33

    > I think a more elegant approach would be to give programmers the

    > ability to create auxilary stacks.

     Yeah... Auxilary stacks would be very useful I think. Here's a possible

    starting point for the syntax:

      a\   Transfer an item from the main stack to the 'a' stack

      a/   Transfer an item from the 'a' stack to the main stack

      a    Execute the top item on the 'a' stack

      A    Reverse-execute the top item on the 'a' stack

    The idea is that the programmer can use as many auxilary stacks as he wants,

    and that a new auxilary stack is created the first time an item is

    transfered to it. It may seem strange that the execution of a auxiliary

    stack item be the simplest operation syntax-wise (i.e., you can execute the

    top item on an auxilary stack by simply using the name of the auxilary

    stack); the reason is that if you do this, you can unify the system

    dictionary with the auxiliary stacks (i.e., you can then effectively define

    a new word by pushing a program onto a named auxiliary stack, and then

    execute that word simply by calling its name).

    The other curious idea is to use capitalization to control execution

    direction; e.g., you'd do "DUP" to reverse "dup". For the non-alphabetic

    symbols, we pretend "-" is the capital "+", and "%" is the capital of "*",

    etc. (% maybe could be used as the division symbol if / is used to transfer

    items from auxiliary stacks)

    Also it would seem handy to be able to have an unnamed auxiliary stack, so

    that you could do "\ foo /" to do a dipped "foo".

    Other ideas... perhaps the functionality of the auxiliary stacks could be

    extended far enough that they could be used as arrays. (it would be handy if

    the system provided an elegant way of moving though and processing arrays,

    rather than just providing indexed fetch and store constructs to manipulate

    them as most languages do). Maybe constructs could be provided to transfer

    items to and from the bottom of an auxiliary stack as well as the top. Maybe

    a construct to circulate the stack (transfer the top item to the bottom, or

    vice versa, which gives the effect of moving through the stack when used

    repeatedly). Maybe a construct to let an auxiliary stack become the main

    stack (perhaps by swapping the entire stacks, or else by letting there be a

    "current stack" pointer or something like that).

     > This is slightly off topic but I've actually been thinking about this

    > concept of multiple auxilary stacks for a bit and it might even be a

    > way to simulate primitive types in a language like Forth without

    > turning it into a typed language as well as increase it's potential

    > for pipelining and parallel execution of code - ANS-Forth standard in

    > fact allows for a Forth implementation to have a separate floating

    > point stack and adding types to a typeless language in this manner is

    > simply an extension of this concept.

     Maybe you're thinking of making each stack homogenous (all items in it must

    be the same type), a consequence being that for each type there would have

    to be a main stack associated with it (where operations that dealt with that

    type would expect the data to be). This could be a very useful idea, I

    think. In a system with runtime types, this would reduce the amount of

    typing information that would have to be stored, and makes it even more

    reasonable to use the arrays-as-stacks paradigm.

     > > I hope that now you can see the beauty of the 2-output "+" and "-": with

     the

     > > 2-output ones, "+" and "-" are the reverse of each other (either one can

    > > exactly undo the other), but this is not the case with either a 1-output

    > > version or a 3-output version. But, you seem very reluctant to agree

     with

     > > anything I say, so I won't get my hopes up ...

    >

    > I apologize. I was just expressing my thoughts on this, don't take it

    > personally - I think the whole point of having message boards such as

    > this one is to exchange ideas and thoughts.

     There's no need to apologize really. This discussion has been quite fruitful

    in that what you've said has stimulated quite a few new ideas in my mind,

    and I'm guessing similarly for you.

     > I think that pretty much all of what you said is useful but at a

    > lower level (for a reversible assembly language, reversible Forth or

    > a high-level language compiler/optimizer for reversible systems).

     It puzzles me that you deem reversibility to be valuable only at the low

    level of the system. Surely this is better than not having reversibility at

    all, but why not let reversibility extend through the whole system and reap

    the full benefits?

    Perhaps it comes back to the 2-output "+" thing again. (You don't have to

    agree with me; but because this issue seems so fundamental, it seems

    worthwhile to address again, more carefully this time). If I'm not mistaken,

    you dislike this operator in two ways:

     1) it is too much of a hassle for a programmer to use it manually, because

    it constantly creates garbage that the programmer usually doesn't need

     2) it is unnatural. it has an output that doesn't even have to do with

    addition.

    Is that a decent summary of your perspective? Anyhow, here's how things seem

    to me:

     1) the 1-output "+" is a hassle for a programmer to use manually, because

    it destroys information from the system that the programmer usually still

    needs (often this requires the programmer to duplicate one of the summands

    before the operation).

        The 2-output "+" does _not_ create garbage; how could it? It creates

    nothing; the outputs are no larger than the inputs. If there is garbage in

    the output, it is only because there was garbage in the inputs to begin

    with.

     2) the 1-output "+" is unnatural. It reduces the total size of the data,

    and is irreversible.

        There is nothing unnatural about having a control input (one that is

    passed straight through to the output). At the gate logic level, most of the

    basic reversible gates have controls: the Fredkin's gate and Toffolli's gate

    both use controls. Also, the controlled-not gate (which in essense performs

    an XOR while preserving one of the inputs) uses a control.

        Having a control does not create garbage. After all, the control is

    present both before and after the operation. Thus if a control is garbage

    after the operation, then it was before also, and thus it is not the

    controlled operation that created the garbage. It's the programmer that

    creates garbage when he arbitrarily decides that the control is no longer

    needed after the operation is finished.

    Again, I don't mind if you still don't agree. I have no real proof to give

    you at this point that the 2-output "+" really can be convenient for a

    programmer in practice. That can only come when someone actually makes a

    nontrivial reversible system founded on it.

     > The idea of scattering garbage throughout the room in form of light

    > sounds interesting - it would to some extent integrate the computer

    > with the room itself and with the outside world making input and

    > output reversible at least to a certain extent.

     Yeah, once you've dispelled garbage in the form of light, in theory you

    could recover the garbage if you could make all the light turn around and

    come back, although in practice it is impossible to make the light come back

    once it has diffused all over the room (this is a good thing if it is bad

    information and you really want to get rid of it).

    - Brent

## Serguey Zefirov — 2002-09-11 23:55:29

    Hello Brent,

    Tuesday, September 10, 2002, 10:20:33 AM, you wrote:

    I've found the following paper:

    http://www.santafe.edu/projects/CompMech/papers/QAQG.html

    Quantum Automata and Quantum Grammars

    C. Moore and J. P. Crutchfield

    Santa Fe Institute

    1399 Hyde Park Rd.

    Santa Fe, NM 87501, USA

    Abstract

    To study quantum computation, it might be helpful to generalize

    structures from language and automata theory to the quantum case. To

    that end, we propose quantum versions of finite-state and push-down

    automata, and regular and context-free grammars.  We find analogs of

    several classical theorems, including pumping lemmas, closure

    properties, rational and algebraic generating functions, and Greibach

    normal form. We also show that there are quantum context-free

    languages that are not context-free.

    --

    Best regards,

     Serguey                            mailto:sz@...

## Manfred von Thun — 2002-09-27 08:35:22

    This is a longish note on Church numerals and related concepts.

    http://www.latrobe.edu.au/philosophy/joy/jp-church.html

    Church numerals are repetition combinators,

    e.g. "C3" means "call the function 3 times"

     so  the Joy program   [dup *] C3    computes the 8-th power

    There is a whole theory surrounding such beasts.

    Brent knows more about it than  I do.

    The object of this note is to show that it can all be done in Joy.

    I am sorry I have not been more active on the group lately.

    My current teaching load does keep me rather busy.

      - Manfred

## Manfred von Thun — 2002-10-01 07:30:58

    Just spotted two apparently very recent concatenative languages:

    Onyx:      http://www.canonware.com/

    Stoical:   http://stoical.sourceforge.net/summary.php

    Both seem to be Forth inspired and implement the stack as an array.

    Certainly worth looking at.

      - Manfred