DiSCiPl Debugging Systems for Constraint Programming
by Pierre Deransart
Constraint Programming is an Emerging Software Technology, where
Europe currently enjoys a lead. Although Constraint Programming is relatively
young compared to other languages, technologies and paradigms, it is already
producing convincing results. To allow industry to benefit from this emerging
technology, to take up results and to build applications capable of capturing
and handling real world constraints, Constraint Programming needs a boost
in the form of effective debugging techniques and environments adapted
to its own paradigms. DiSCiPl is a research project funded by the European
Commission's Esprit programme that aims at define, implement and assess
novel and effective debugging systems for Constraint Programming (CP).
Debugging is considered in a broad sense: it concerns both validation
aspects (to build a correct application) as well as methodological aspects
(to find the best solution to a problem by better understanding of constraint
solver behaviour). To satisfy these objectives, tools must locate and explain
bugs, and graphic tools must help interpreting program behaviour and results.
Existing tools reveal to be ineffective in most industrial situations and
tools developed for imperative or functional programming are not adapted
to the context of CP. The main reasons are that the huge number of variables
and constraints makes the computation state difficult to understand, and
that the non deterministic execution increases drastically the number of
computation states which must be analysed. Existing tools do not include
all aspects of debugging is a single environment.
The expected results of the project include:
- novel techniques of high level debugging
- integration of these novel techniques into industrial CP platforms
- assessment of these techniques in industrial applications.
The taken approach is based on three paradigms currently used in advanced
debugging:
- Declarative debugging: The clear semantics of CP languages allows to
adapt debugging techniques developed in the context of Logic Programming.
- Assertion based methods: The user may be unable to understand the results
or the behaviour of a program, due to the complexity of the constraint
system in some intermediate computation state. We propose methods such
as the instantiation of the answer constraints and the use of assertions
describing the expected properties.
- Graphics based methods. The use of graphical tools is of great interest
both to display properties of the solutions, and to follow the history
of changes of variables or constraints. They may be used during debugging,
at several levels, for constraint display and update and combined with
assertion based methods.
None of these paradigms individually provides a complete solution to
the Constraint Logic Programming (CLP) debugging problems. The orientation
taken by the project is firstly to consider them separately in order to
improve and adapt them in the context of CLP, when existing work is not
sufficient, then to find ways and to experiment in order to combine them
in powerful and useful debugging tools. Plugging together basic tools derived
from each of these paradigms is the most interesting challenge of the project.
The definition of the debugging tools has been elaborated in two steps.
First, debugging needs have been analysed with a questionnaire distributed
among partners and their clients, international related mailing lists,
and made public on the project Web site. This first step confirmed that
two crucial aspects of debugging of CP applications are performance debugging
and correctness debugging. Tools should in particular provide efficient
help to observe and understand complexity of resolution.
In a second step possible tools have been analysed and classified. It
has been observed that tools alone could not be sufficient and needed to
be completed with a programming method aimed at facilitating debugging
and thus called 'DiSCiPl debugging methodology'.
Correctness debugging
By correctness debugging we mean the actions the programmer does in
order to make the program behave as expected, ie, according to his/her
intention. The ultimate goal of this debugging activity is to locate all
the errors and faults which are revealed by missing/incorrect answers (semantics
errors). The missing answers problem resolves itself into two formidable
(and undecidable) problems: detecting the reason of failure and detecting
non termination. The potential sources of missing and incorrect answers
are: typos in the program text, wrong typing, wrong design and coding of
modules and procedures, wrong constraint modelisation. Finding these errors
is the traditional debugging activity, but in the CP framework this is
somehow complicated by the fact that the execution of the program is data-driven.
Hence traditional step by step, source oriented and trace oriented approaches
are insufficient.
Performance debugging
Performance debugging has been posed as a very relevant problem. Constraint
programs must be not only correct but also efficient. This is very often
a primary requisite for a constraint program. Most of the times, bad performances
are due to a poor comprehension and modelisation of the problem. Unfortunately
this aspect is sometimes obscured by the constraint solver. As a first
consequence of the problem of performance debugging, there is a need to
understand constraint propagation. Points to investigate are if and why:
- constraints are not waked when expected
- constraints are uselessly waked (small or no reduction of domains).
However the problem it is not only to understand how propagation works,
but also how propagation fails. Finding the reason of failure is useful
in trying to obtain efficient pruning of the failing search alternatives.
Debugging Tools
For performance debugging, tools will be mainly based on visualisation
of the program behaviour. Several tools will offer the possibility of studying
the program behaviour from different points of view in order to help the
user to understand the solvers behaviour and to improve the search strategies.
For correctness debugging, tools will take advantage of the declarative
nature of CLP, based on a declarative kernel language. The tools proposed
will lead to a high level of integration of debugging phases, combining
performance and correctness debugging.
The DiSCiPl consortium is composed of 4 industrial members COSYTEC (France),
PrologIA (France), ICON (Italy) and BIS (Belgium), as well as 4 academic
members: INRIA, University of Bristol (UK), Linköping University (Sweden)
and University of Madrid. ERCIM EEIG is associated partner in the project.
For more information, see http://discipl.inria.fr/.
Please contact:
Pierre Deransart - INRIA
Tel: +33 1 3963 5536
E-mail: pierre.deransart@inria.fr
