INSTITUTSBERICHT 95.24, INSTITUT F?R INFORMATIK, UNIVERSIT?T Z?RICH, 1995

Opportunistic Logic Program Analysis and Optimisation*

Enhanced Schema-Based Transformations for

Logic Programs and their Usage in an Opportunistic Framework for Program

Analysis and Optimisation

Wamberto W. Vasconcelos**, Norbert E. Fuchs

Institut f?r Informatik
Universit?t Z?rich
Switzerland
{vascon,fuchs}@ifi.unizh.ch

A program schema is a generic description of a logic program highlighting important features and suppressing unimportant ones. A schema-based transformation is an abstract description of syntactic changes that transform programs into more efficient ones while preserving their meaning. We define an enhanced schema language that can be used to describe concisely a very large class of logic programs and their transformations. We present a realistic framework to automatically transform a complete program in an opportunistic way: all available schema-based transformations are systematically matched against the program, and if the matching is successful, the suggested alterations are carried out. Heuristic selection criteria guarantee that the optimal sequence of transformations is performed. We have implemented OpTiS, a prototypical transformation system, based on these ideas.

1 Introduction

The clean declarative semantics of logic programs hides many performance issues which must be accounted for if the program is to be executed using the currently available technology. These efficiency issues can be dealt with either at an early stage, during the preparation of the program, or at a later stage, when a complete, possibly inefficient, logic program is analysed and its inefficient constructs are detected and appropriately modified, yielding a program with a better computational performance.

If the first approach is taken and performance issues are to be considered during the preparation of the program then standard logic programming constructs, also named programming techniques, which guarantee a good computational behaviour to those logic programs incorporating them, can be used. Prolog programming techniques have been extensively studied (e.g. [Bowles et al. 94], [O'Keefe 90], [Ross 89] and [Sterling & Shapiro 94]); some programming techniques have been assigned names, such as accumulator pairs and difference lists, and are now part of the folklore of the logic programming community. It has been advocated that these standard practices should be explicitly taught as part of a discipline of methodical logic programming development [Kirschenbaum et al. 94; Sterling & Kirschenbaum 91] and logic programming environments have been implemented (e.g. [Bowles et al. 94] and [Robertson 91]) incorporating them.

The second approach addresses efficiency issues after the program has been devised, trying to optimise the existing code. This involves the analysis and subsequent transformation of a given, possibly inefficient, logic program into an equivalent version with better computational behaviour. The analysis and transformation tasks should be as automated as possible, thus relieving logic programmers from the extra burden of worrying about performance issues. An underlying assumption of this approach is that commonly occurring but computationally inefficient constructs in logic programs can be identified and eliminated.

* This work was carried out within the European Human Capital and Mobility Scheme (contract No. CHRX-CT 93-00414/BBW 93.0268) while the first author was visiting the Institut f?r Informatik, Universit?t Z?rich. This paper should replace a previous work entitled Enhanced Schema-Based Transformations for Logic Programs and their Opportunistic Usage in Program Analysis and Optimisation (Technical Report 95-16, Institut f?r Informatik, Universit?t Z?rich), extending and updating it.
** PhD Student, Department of Artificial Intelligence, University of Edinburgh, Scotland, U.K., sponsored by the Brazilian National Research Council (CNPq), Grant No. 201340/91-7, while on leave of absence from UECE/Cear?, Brazil.