Freeness and related analyses of constraint logic programs using abstract interpretation

This thesis addresses the derivation of run-time properties of constraint logic programs. Constraint logic programming is more expressive than logic programming due to the combination with constraints. However, the increase in expressivity is often paid in terms of performance. For certain classes of queries, the full power of the constraint solvers is not needed. Run-time properties can then be used by an optimising compiler to generate specialised and efficient code. Deriving run-time properties is formalised in terms of abstract interpretation. This is a method for interprocedural program analysis. We have used one of the existing analysis frameworks for logic programming that was already adapted towards constraint logic programming. The framework allows the developer of a particular program analysis to concentrate on the application-dependent parts and the associated safety conditions. An additional advantage of using an existing framework is the possibility to reuse implementations of the application-independent abstract interpretation procedure. As an application of the framework, this thesis presents an analysis for determining possible constraint interaction. The analysis is named freeness analysis, as it infers which variables act as degrees of freedom with respect to the satisfiability of the constraints in which they occur. This information allows several optimisations such as constraint/goal reordering and parallelisation. The analysis focusses on constraint logic programming languages includingthe logic programming term domain and a numerical domain, although it can easily be extended to other constraint domains as well. The efficiency of the kernel analysis can be improved in two ways: one approach is to retain only minimal information, the other consists of combining the freeness analysis with definiteness information. As the optimisationsare orthogonal, they can be combined, yielding a practical and more complete analysis system. A number of extensions to the analysis (such as the treatment of non-normalised programs, the integration of type information, etc.) further enhance its power. The resulting system forms the basis for a large class of program optimisations.