The Transformational Approach to Program Development

We present an overview of the program transformation techniques which have been proposed over the past twenty-five years in the context of logic programming. We consider the approach based on rules and strategies. First, we present the transformation rules and we address the issue of their correctness. Then, we present the transformation strategies and, through some examples, we illustrate their use for improving program efficiency via the elimination of unnecessary variables, the reduction of nondeterminism, and the use of program specialization. We also describe the use of the transformation methodology for the synthesis of logic programs from first-order specifications. Finally, we illustrate some transformational techniques for verifying first-order properties of logic programs and their application to model checking for finite and infinite state concurrent systems.