Title: Freeness and related analyses of constraint logic programs using abstract interpretation
Authors: Dumortier, Veroniek
Issue Date: Oct-1994
Series Title: pages:281
Abstract: 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
Publication status: published
KU Leuven publication type: TH
Appears in Collections:Informatics Section
Statistics Section

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.