Reversible computation and Joy

srenner@mail.ru — 2000-05-14 16:33:23

If Joy is understood as linear (currently a topic of debate here),

then is a Joy computation reversible? My intuition is that Joy can be

made reversible if  "garbage" is not collected during a computation

but pushed onto a "garbage stack". 



[2 2 +] i == 4



3 1 + == 4



2 sq == 4



123 121 - == 4



Given 4 on the stack, what information do we need to reconstruct the

computation that created it? Isn't this information exactly the same

as the "garbage" we would normally collect?



In (1), Baker mentions the Carnot engine, which is a simple heat

engine with a piston. There may be an interesting analogy here. Think

of the computation on one side of the piston and the garbage on the

other. No, that won't work, because the combined volume can change.

The volume that is conserved is the memory available to the process.

So the computation + garbage is on one side of the piston and free

memory is on the other. Maybe this analogy isn't very useful. 









(1)Thermodynamics and Garbage Collection  Baker 1993



(2)Linear Logic and Permutation Stacks--The Forth Shall Be First Baker

1993



(3)NREVERSAL of Fortune[1] -- The Thermodynamics of Garbage Collection

Baker 1992