Using call/exit analysis for logic program transformation

Abstract. A technique for transformation f definite logic programs is presented. A first phase performs an analysis of the extended call/exit patterns of the source program. It is shown that a particular form of correct abstract call/exit patterns can be used as a guide to control the transformation itself and can help to generate the target program having desired properties. The technique provides aframework which, combined with problem specific information concerning the source program, can lead to nontrivial transformations. 1 In t roduct ion The most popular approaches for definite logic program transformations are based on unfold/fold and goal replacement operations applied to the clauses of a source program. The unfold/fold transformations have been introduced in [5] and later were applied to logic programming in [25, 15, 24]. The recent paper [13] s revisits the framework developed by Tamaki and Sato. In this paper we are developing another approach to logic program trans-formation. Namely, we consider transformations which are performed into two phases: a first phase performs a complete static data flow analysis to derive a transformation guide of the source program, the second phase follows the guide to transform the source logic program (here we follow some basic ideas of [14, 12]). In [1, 2] we have introduced a rather general and powerful approach to derive unfold/fold transformations of definite logic programs by abstract interpreta-tion. The unfold/fold transformations, which can be obtained in this way, have been shown to be more general than those of Tamaki and Sato. Indeed, as it was pointed out in [18, 13], SLD-like tree analysis can produce transformations which cannot always be expressed in terms of unfold/fold transformations