Debugging Systems
for Constraint Programming
20-21 May 1999
The DiSCiPl project will be achieved in June 1999. The final review will be held May 20-21 1999. It is public. The goals of the project were to define, to implement and to assess novel and effective debugging tools for Constraint Programming. Several debugging tools for correctness and performance analysis of CLP programs will be presented. There are industrial tools running in Chip and Prolog4 and academic tools running in Calypso (GNU-Prolog) and CIAO. The theoretical basis of the tools will also be presented. Most of the tools run over CLP(finite domains) but many of the ideas and tools developed in the project could be easily adaptable to other constraint languages.
May 20: 10h-19h Industrial day:
"DiSCiPl Tools for Analysis and Visualization of Constraint Programs"
May 21: 10h-13h "Theoretical foundations of CLP debugging"
May 20:
Hotel Méridien Montparnasse, Conference space, Picasso 19 rue du Commandant Mouchotte
75014 Paris
Metro Gaite' ou Montparnasse
May 21:
INRIA-Rocquencourt, 78 Rocquencourt, Council room, Bat 7
ftp://ftp.inria.fr/INRIA/directions.html
Christiane Demars, INRIA Rocquencourt,
Annick Theis-Vie'mont, INRIA Rocquencourt
Information
Christiane Demars
INRIA Rocquencourt, Relations Extérieures Bureau des Cours et des Colloques
B.P. 105 - 78153 Le Chesnay Cedex, France. Tel: +33 1 39 63 56 00 Fax +33 1 39 63 56 38 Email: symposia@inria.fr
"DiSCiPl Tools for Analysis and Visualization of Constraint Programs"
| 9h00 | Registration and welcome coffee |
| 10h00 | Opening M.C. Imbert, INRIA-European Affairs Overview of the Project Results |
| 10h30 | Industrial Tools
|
| 12h30 | Lunch |
| 14h 00 | Advanced and Research Tools
|
| 16h30 | The IST Programme N. Sadeh, Project Officer |
| 17h00 | Coffee break |
| 17h30 | Demonstrations and open discussions |
Abstracts of the presentations
1 - Performance Analysis, Debugging and Visualization Tools in CHIP
Visualization tools can be an important help in the design, development and analysis of constraint programs. COSYTEC will present three tools:
(1) Visual Search Tree,
(2) Visualization of Global Constraints
(3) Assertion tool.
They allow different methods of graphically presenting the search procedure, the constraints and constraint propagation. The Visual Search Tree tool provides representations of the form of the search tree, of constraints and variables of the program and of the propagation steps performed after each decision in the tree. The Visualize library for global constraints shows the state of the constraint and helps to understand its constraint reasoning. The Assertions tool allows to perform static analysis for validation and debugging of constraint programs. In this presentation we discuss on several real-world examples (including scheduling, resource allocation and transportation problems) the interest and possibilities of visual tools.
2 - Constraint Debugging Tools in Prolog IV
Prolog IV development system has a set of tools to debug and follow details of the execution of programs. One tool is based upon the addition of assertions in user programs to specify some properties of the predicates. These properties are checked at compile-time or at run-time if necessary. The other tool is a debugger based upon the Box Model Debugger which dispatches informations to various viewers : the Box Model Viewer, the Source Level Viewer and the new Execution Tree Viewer. The Execution Tree Viewer purposes can be summarised as follows:
- to give a full view of an execution tree; - to give a view of a proof;
- to go quickly to a given node of the execution tree; - to help restarting the execution until a given point of the execution is reached.
These tools will be demonstrated through a small debugging session.
3 - Practical Experience with Constraint Debugging Tools
During several months, both OM Partners and ICON tested the prototypes of the constraint debugging tools in CHIP. These tests were conducted by novice and expert users. The programs used for debugging purposes included academic exercises as well as existing and new industrial applications. All end users agreed that the visualization tools significantly improved their understanding of constraint propagation, as well as of the search tree mechanism. This in turn leads to a more efficient development of CLP programs, which are also more performant. The visualization of the global constraints helps to avoid modeling errors and gives rise to new creative ideas. The same holds for the search tree mechanism. As such, these new constraint debugging tools have demonstrated to meet a real need of the end user community.
4 - Debugging with Assertions
We demonstrate a tool that allows to verify at compile time static and dynamic properties of CLP programs. Programs can be documented with assertions expressing several kinds of properties of programs. We propose a general language of assertions for inclusion of such properties as additional specifications in the programs.
The resulting tool generates and checks assertions for Prolog, CLP(R), and CHIP/CLP(fd) programs, and integrates compile-time and run-time checking in a uniform way. The tool allows using properties such as types, modes, non-failure, determinacy, and computational cost, and can treat modules separately, performing incremental analysis. In practice, this modularity allows detecting statically bugs in user programs even if they do not contain any assertions.
5 - Type-Based Diagnoser for CHIP
We demonstrate a tool that infers types for CHIP programs and locates type errors in interaction with the user. The tool consists of two parts. A fully automatic analyzer finds types for a given program. If the types inferred are not as expected by the user an interactive diagnoser can be used. It locates the program clause responsible for the incompatibility. The user's role in the interaction is to provide a selected information about intended types in response to diagnoser's queries. A few interactions may be sufficient to locate a bug. The demonstrated diagnoser works for CHIP but it is easily adaptable to other CLP languages.
6 - Declarative Debugging
The Declarative Diagnoser is a tool which allows to analyze the computation producing a wrong or missing result, and to locate (one of) the erroneous part of program which is responsible for the symptom. Originality of the tool lies in the fact that the user does not need to know how such results have been obtained nor charateristics of the solver. She has only to answer some queries produced by the system.
The tool is an adaptation for constraints of the declarative debugging principle developed in Logic Programming.
7- Debugging with S-Boxes
The tool permits visualizing a graphical abstraction of the store where the structure induced by the program clauses has been reintroduced. The user is allowed to focus on some sets of constraints, gathering others into new ``global constraints'' which are dealt with only by their input/output (their semantics being defined as the conjunction of the user constraints they embed). The tool is based on a notion of S-box , which permits structuring the store and makes it manageable by controling its size and complexity. It allows to observe step by step the constraints variables modifications during the process of constraints solving.
8 - Analyzing Behavior of CLP Programs with Search-Tree Views
The tool concerns performance debugging and gives the user the possibility to visualize synthetical views of the search space.
It is expected that such views help to understand program behaviour, in particular in complex combinatorial problems. The tool is based on search-tree views. Such views are specified by the user separatly in the same language as the program.
The originality of the tool lies in its genericity (the computation space can be analyzed with several views) and the way to specify the abstractions, in particular, using program predicate properties.
9 - Understanding CLP Programs Execution with VIFID Vizualiser
A major difference between constraint programming and other paradigms, specially in what concerns visualization, is the treatment of variables. Variables in constraint programming have values which are often not totally determined, but only partially specified as being those satisfying a certain set of equations. A final solution is reached when the equations in the systems allow the solver to assign a single value to each variable in the problem solution.
We demonstrate the VIFID tool which allows inspecting the runtime values of these variables and offers a way to acquire insight into some characteristics of the running application. This is , of course, useful to understand how the execution proceeds from the point of view of the changes in the domains of the variables, rather than from the point of view of the execution path. A well-designed visualization allows the programmer to quickly spot problems regarding lack of correctness or sources of a deficient performance.
| 9h30 | welcome coffee |
| 10h | DiSCiPl: managment, scientific objectives and results (INRIA) |
| 10h30 | Academic presentations from: UPM (use of assertions, abstract interpretation for program verification, ...) INRIA (DD principles and implementation, search-tree abstraction, constraint propagation analysis with S-Boxes) Linkoeping (static diagnosis) Programme to be completed .... |
| 13h-14h30 | "farewell" lunch buffet in conference room of building 7 |
Participation is free, except for the lunch of May 20.
All participants have to registrate to the industrial day and/or the final review (tick the corresponding box on the registration form).
The optional lunch of May 20 is organised on site (cost: 275 FF).
To registrate, please send the attached form with the payment.
Caution: registration (for the lunch) without payment or purchase order will not be considered.
No registration and no payment on site.
Payment
-by purchase order (for French delegates only). Purchase orders should be enclosed with the printed copy of the registration form.
-by check (in French Currency or Euro). Checks should be enclosed with the printed copy of the registration form and made payable to the Agent Comptable de l'INRIA.
-by bank transfer:
Tre'sorerie Ge'ne'rale des Yvelines, 16 avenue de Saint-Cloud, 78018 Versailles cedex, France
(10071 : bank code ; 78000: branch code ; 00003003958: account number ; 80: key)
Cancellation
------------
Fees will be returned in full for any written cancellation received before May 17, 1999. No refund will be made for cancellations received after this date.
Accomodation
------------
Hotel reservation should be made by each participant. You also could obtain information on
http://www.paris.org/Hotels/
http://www.apcom.fr/yvelines/hotelsrest.htm
Registration form to be returned before May 17, 1999
Name First Name
Company
Address
Zip Code City
Country
Phone Te'l. Fax
Email:
Registration fees (20,6 % VAT included) - Please mark the appropriate
Industrial day: yes/no lunch: yes/no (275 FF)
Final review: yes/no lunch: yes/no
Payment:
- By purchase order (for French delegates only). Le bon de commande devra e^tre joint au bulletin d'inscription.
- By check (in French Currency or Euro) Checks should be enclosed with the printed copy of the registration form and made payable to the Agent Comptable de l'INRIA.
- By bank transfer
Trésorerie Générale des Yvelines, 16 avenue de Saint-Cloud, 78018 Versailles cedex, France
(10071 : bank code; 78000: branch code; 00003003958: account number; 80: key)
Please do not forget to state your name and the Conference reference: DISC99
Bien mentionner votre nom et la référence de la manifestation: DISC99
Send this form (with optional lunch fee) by surface mail to:
INRIA Rocquencourt
Bureau des Cours et des Colloques
B.P. 105
78153 Le Chesnay Cedex
France
If there is no fee, the form can be sent by email to: symposia@inria.fr
-------------------------------DISC99DISC99DISC99DISC99DISC99DISC99DISC99DISC99DISC99DISC99DISC99DISC99 ----------------