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