# 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