GIT-CERCS-03-04
Kalyan S. Perumalla,
Generating Perfect Reversals of Simple Linear-Codes
Bi-directional execution - executing forward as well as in reverse - is useful
in many contexts. However, traditional techniques for bi-directional execution
are not scalable, as they require infinite storage in the presence of
"destructive" assignments. We present a new approach that eliminates the
scalability problem for bi-directional execution of a class of functions called
linear codes, which are sequences of assignments of arbitrary linear expressions
to variables. Examples of linear codes include Fibonacci-like sequence
generators, and operators such as shift, swap and rotate. We present an
algorithm to generate perfect forward-reverse code pair from any given linear
code, and show that any linear code can be perfectly inverted despite the
presence of destructive assignments and apparent singularities in the input
code. While existing techniques require memory size proportional to forward
execution length, the code generated by our algorithm uses bounded amount
of memory. The memory is proportional only to the number of variables in
the given forward code, and is independent of both forward code size and forward
execution length.