A Heuristic Approach to Program Inversion

Abstract

A notation is given for describing the inverse of multiple functions and of functions of multiple arguments. A technique based upon this notation is presented for taking a program written in pure LISP and automatically deriving a program which computes the inverse function of the given program. This technique di#ers from previous such methods in its use of heuristics to invert conditionals. # x) 2 = x rather than LISP append reverse as given in [2], unary add1 and sub1, and sev- 1. Introduction There are many applications in which it is useful to compute the inverse of some program, that is, to find another program such that feeding the output of the original program as input to the new program produces the original input. One such application is in programming by specification: one would like to define a program to compute the square root of a number by the equation ( supplying an actual iterative method of solving the equation. Another application of program inversion is in...