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