arXiv:cs/0111043v1 [] 16 Nov 2001

Prototyping clp(fd) Tracers: a Trace Model
and an Experimental Validation Environment

∗†

Ludovic Langevine, Pierre Deransart, Mireille Ducassé and Erwan Jahier
INRIA/INSA, INRIA, IRISA/INSA, IRISA/IFSIC
{Ludovic.Langevine Pierre.Deransart}@inria.fr, {Mireille.Ducasse Erwan.Jahier}@irisa.fr

Abstract
Developing and maintaining CLP programs requires visualization and explanation
tools. However, existing tools are built in an ad hoc way. Therefore porting tools from
one platform to another is very diﬃcult. We have shown in previous work that, from a
ﬁne-grained execution trace, a number of interesting views about logic program executions
could be generated by trace analysis.
In this article, we propose a trace model for constraint solving by narrowing. This trace
model is the ﬁrst one proposed for clp(fd) and does not pretend to be the ultimate one.
We also propose an instrumented meta-interpreter in order to experiment with the model.
Furthermore, we show that the proposed trace model contains the necessary information
to build known and useful execution views. This work sets the basis for generic execution
analysis of clp(fd) programs.
[23] is a comprehensive version of this paper.

1

Introduction

Developing and maintaining CLP programs beneﬁts from visualization and explanation tools
such as the ones designed by the DiSCiPl European project [10]. For example, the CHIP
search-tree tool [28] helps users understand the eﬀect of a search procedure on the search space;
and the S-Box model [17] allows users to inspect the store with graphical and hierarchical
representations.
However, existing tools are built in an ad hoc way. Therefore porting tools from one platform to another is very diﬃcult. One has to duplicate the whole design and implementation
eﬀort every time.
We have shown in previous work that, from a ﬁne-grained execution trace, a number of
interesting views about logic program executions could be generated by trace analysis [11, 19].
Here we want to generate a generic trace that can be used by several debugging tools. Each
tool gives a useful view of the clp(fd) execution (e.g. the labelling tree or the domain state
evolution during a propagation stage). Each tool selects the relevant data in the generic
∗

This work is partly supported by OADymPPaC, a French RNTL project [26].
In A. Kusalik (ed), Proceedings of the Eleventh Workshop on Logic Programming Environments
(WLPE’01), December 1, 2001, Paphos, Cyprus. Computer Research Repository (http://www.acm.org/corr/),
/0111043; whole proceedings: /0111042.
†

1

2

WLPE’01

trace in order to build its execution view. Therefore, the trace is supposed to contain all
potentially useful information. The tools can be developed simultaneously and reused on
diﬀerent platforms 1 . This approach assumes that there is a generic trace model. In order to
reach this objective, we start with a general model of ﬁnite domain constraint solving which
allows to deﬁne generic trace events.
So far, no ﬁne-grained tracers exist for constraint solvers. Implementing a formally deﬁned
tracer is a delicate task, if even at all possible. This is especially true in the context of
constraint solving where the solvers are highly optimized. Therefore, before going for a “real”
implementation, it is essential to elaborate trace models and experiment them.
In order to rigorously deﬁne the constraint solving trace model, and as we did for Prolog
[20], we use an operational semantics based on [2] and [15]. We deﬁne execution events of
interest with respect to this semantics. On one hand, this formal approach prevents the ﬁnedgrained trace model to be platform dependent. On the other hand, the consistence between
the model and concrete clp(fd) platforms has to be validated.
In order to develop a ﬁrst experimentation, the formal model is implemented as an instrumented meta-interpreter 2 which exactly reﬂects it.
The proposed instrumented meta-interpreter is useful to experimentally validate the model.
It is based on well known Prolog meta-interpretation techniques for the Prolog part and on
the described operational semantic for the constraint part.
The ultimate goal of the meta-interpreter (as in [20]) is to provide an executable speciﬁcation of traces. The traces generated by the meta-interpreter could then be used to validate
a real (and eﬃcient) tracer. At this stage, eﬃciency of the meta-interpreter is not a key issue;
it is used as a prototype rather than as an eﬀective implementation.
Such a tracer may generate a large volume of data. The generic trace must be analyzed
and ﬁltered in order to condense this data down to provide the suﬃcient information to the
debugging tools. To push further the validation we have mimicked a trace analyzer à la
Opium [12] which allow to obtain diﬀerent kinds of views of the execution. This is a way to
show that the proposed trace model contains the necessary information to reproduce several
existing clp(fd) debugging tools.
In this article, due to lack of space we concentrate on the constraint solving part, a trace
of the logic programming part “à la Byrd” [3] could be integrated in the meta-interpreter
(see for example [13]).
The contribution of this article is ﬁrst to rigorously deﬁne a trace model for constraint
solving and to provide an environment to experimentally validate it. This sets the basis for
generic execution analysis of clp(fd) programs.
In the following, Section 2 formally deﬁnes an execution model of clp(fd) narrowing. In
particular, it deﬁnes a 8 steps operational semantics of constraint solving. These steps are the
basis for the trace format deﬁned in Section 3. Section 4 explains how to build an instrumented
meta-interpreter in order to build an experimental environment. Section 5 brieﬂy describes
experiments with the proposed trace and our trace analyzer. Finally, Section 6 discusses the
content of the trace with respect to existing debugging tools.
1

Our OADymPPaC partners will use our trace model to build tools in the CHIP [7], CLAIRE [6] and
GNU Prolog [16] platforms.
2
The meta-interpreter approach to trace clp(fd) program executions has already been used in the APT tool
by Carro and Hermenegildo [4]. However, APT does not access the propagation details. We propose a more
informative trace.

Prototyping clp(fd) Tracers

2

3

Operational Semantics of Constraint Programming

In this section, we propose an execution model of (ﬁnite domain) constraint programming
which is language independent. The operational semantics of constraint programming results from the combination of two paradigms: control and propagation. The control part
depends on the programming language in which the solver is embedded, and the propagation
corresponds to narrowing. Although the notions introduced here are essentially language
independent, we will illustrate them in the context of clp(fd).

2.1

Basic Notations

In the rest of the paper, P(A) denotes the power set of A; r|w denotes the restriction of the
relation r ⊆ A × B to w ⊆ A: r|w = {(x, y) | x ∈ w ∧ (x, y) ∈ r}.
The following notations are attached to variables and constraints: V is the set of all the
ﬁnite domain variables of the problem; D is a ﬁnite set containing all possible values for
variables in V; D is a function D : V → P(D), which associates to each variable x its current
domain, denoted by Dx ; minx and maxx are respectively the lower and upper bounds of Dx ;
C is the set of the problem constraints; var is a function C → P(V), which associates to each
constraint C ∈ C the set of variables of the constraint.

2.2

Reduction Operators

Many explanation tools focus on domain reduction (see for example [15, 21]). When constraints are propagated, the evolution of variable domains is a sequence of withdrawals of
inconsistent values. At each step, for a given constraint, a set of inconsistent values is withdrawn from one (and only one) domain. These values can be determined by algorithms such
as “node consistency”, “arc consistency”, “hyper-arc consistency” or “bounds consistency”
described for example by Marriott and Stuckey [24].
Following Ferrand et al [15], we deﬁne reduction operators. The application of all the
reduction operators of a constraint gives the narrowing operator introduced by Benhamou [2].
Definition 2.1 (Reduction operator). A reduction operator redxC is a function attached
to a constraint C and a variable x. Given the domains of all the variables used in C, it
returns the domain Dx without the values of x which are inconsistent with the domains of the
other variables. The set of withdrawn values is denoted Wx .
redxC (D|var(C) ) = Dx − Wx .
There are as many reduction operators attached to C as variables in var(C). In general,
for eﬃciency reasons, a reduction operator does not withdraw all inconsistent values.
A simple example of reduction operator for C ≡ x > n, where n is a given integer, is
redxC (D|{x} ) = Dx − {v | v ∈ Dx ∧ v ≤ n}.
The evolution of the domains can be viewed as a sequence of applications of reduction
operators attached to the constraints of the store. Each operator can be applied several times
until the computation reaches a ﬁx-point [15]. This ﬁx-point is the set of ﬁnal domain states.
An example of computation with reduction operators is shown in Figure 1. There are
three variables x, y and z and two constraints, x > y and y > z. At the beginning, Dx =
Dy = Dz = {1, 2, 3}, represented by three columns of white squares. Considering the ﬁrst
constraint, it appears that x cannot take the value “1”, because otherwise there would be

4

WLPE’01
x
3
2
1

y

z

x
red

x
x>y

y

z

y
red x > y

x

y

z

y
red y > z

x

y

z

z
red y > z

x

y

z

x
red x > y

x

y

z

Figure 1: Application of reductions to the system {x > y; y > z}.

no value for y such that x > y; redxx>y withdraws this inconsistent value from Dx . This
withdrawal is marked with a black square. In the same way, redyx>y withdraws the value 3
from the domain of y. Then, considering the constraint y > z, the operators redyy>z and
redzy>z withdraw respectively the sets {1} and {2, 3} from Dy and Dz . Finally, a second
application of redxx>y reduces Dx to the singleton {3}. The ﬁx-point is reached. The ﬁnal
solution is: {x = 3, y = 2, z = 1}.

2.3

Awakening and Solved Conditions

An essential notion of constraint propagation is the propagation queue. This queue contains all
the constraints whose reduction operators have to be applied. At each step of the propagation,
a constraint is selected in the propagation queue, according to a given strategy depending on
implementation (for example a constraint with more variables ﬁrst). The reduction operators
of the selected constraint are applied. These applications can make new domain reductions.
When a variable domain is updated, the system puts in the queue all the constraints where this
variable appears. When the queue becomes empty, a ﬁx-point is reached and the propagation
ends. Thus, there are three fundamental operations: selection from the queue, reduction of
variable domains and awakening of constraints.
It is actually not necessary to wake a constraint on each update of its variable domains.
For example, it is irrelevant to wake the constraint x > y at each modiﬁcation of Dx or Dy .
The reduction operators of this constraint are unable to withdraw a value in any domain if
neither the upper bound of Dx nor the lower bound of Dy is updated. Hence, it is suﬃcient
to wake the constraint only when one of those particular modiﬁcations occurs.
Definition 2.2 (Awakening condition). The awakening condition of a constraint C is a
predicate depending upon the modifications of D|var(C) . This condition holds when a new
value withdrawal can be made by the constraint reduction operators. The condition is optimal
when it holds only when a new value withdrawal can be made.
The awakening condition of C is denoted by awake cond(C).
The actual awakening conditions are often a compromise between the cost of their computation and how many awakenings they prevent.
Another condition type permits irrelevant awakenings to be prevented. Let us consider a
constraint C; if the domains of its variables are such that no future value withdrawals can
invalidate the constraint satisfaction, the constraint is said to be solved. In that case, the
reduction operators of this constraint cannot make any new value withdrawal anymore, unless
the system backtracks to a former point. For example, if the two domains Dx and Dy are
such that Dx ∩ Dy = ∅, it is useless to apply the reduction operators of x 6= y. Thus, it is
useless to wake a solved constraint.

Prototyping clp(fd) Tracers

5

Definition 2.3 (Solved condition). The solved condition of a constraint C is a predicate
depending upon the state of D|var(C) . This condition holds only when the domains are such
that C is solved.
The solved condition of C is denoted by solved cond(C).
We can note that a suﬃcient condition is that all variables in var(C) are ground to some
values satisfying the constraint.
In the rest of the paper, a primitive constraint is deﬁned by those three characteristics:
its reduction operators, awakening condition and solved condition.

2.4

Structure of the Constraint Store

The constraint store S is the set of all constraints taken into account by the computation at
a given moment. When the computation begins, the store is empty. Then, constraints are
individually added or withdrawn according to the control part. In the store, constraints may
have diﬀerent status and the store can be partitioned into ﬁve subsets denoted A, S, Q, T, R.
• A is the set of active constraints. It is either a singleton3 (only one constraint is active)
or empty (no constraint is active). The reduction operators associated to the active
constraint will perform the reductions of variable domains.
• S is the set constraints which are said suspended, namely they are waiting to be “woken”
and put into Q in the case of domain modiﬁcations of some of their variable (none has
empty domain).
• Q is the set of constraints in the propagation queue 4 , it contains the constraints waiting
to be activated. In order to reach the ﬁx-point all reduction operators associated to
these constraints must be considered.
• T is the set of solved constraints (true), namely the constraints which hold whatever
future withdrawals will be made.
• R is the set of rejected constraints, i.e. the constraints for which the domain of at least
one variable is empty. In practice it is empty or a singleton, since as soon as there is
one constraint in R the store is considered as “unsatisﬁable” and the computations will
continue according to the control.

2.5

Propagation

The evolution of the store can now be described as state transition functions or “events”
acting in the store, in the style of Guerevitch’s evolving algebras [18]. This is illustrated
in Figure 2. When propagation begins, there is an active constraint. The active constraint
applies its reduction operators as far as possible. Each application of a reduction operator
is a reduce event. It narrows the domain of one and only one variable. If a domain becomes
empty, the constraint is rejected (reject event). A rejected constraint is a sign of failure. If
no failure occurs and no other reduction can be made, the constraint is either solved (true) or
suspended (suspend). A solved constraint will not be woken anymore. A suspended constraint
will be woken as soon as its awakening condition holds. On awakening, the constraint is put
in the propagation queue (wake-up event). When there is no active constraint, one is selected
in the queue (select) and becomes active. If the queue is empty, the propagation ends.
3

This restriction could be alleviated to handle multiple active constraints, for example to handle unification
viewed as equality constraints on Herbrand’s domains.
4
The term queue comes from standard usage. It is in fact a set.

6

WLPE’01

SELECT

Q

Queue
WAKE−UP

SUSPEND

S

A
TELL

Suspended
constraints
TOLD

Active
Constraint
Solved
TRUE

T

REJECT

R

constraints

REDUCE
Rejected
constraints

Store

Figure 2: Events related to the structured store

select

∃C ∈ Q ∧ A = ∅ ∧ R = ∅
Q ← Q − {C}, A ← {C}

reject

∃C ∈ A, ∃x ∈ var(C) · (Dx = ∅)
A ← A − {C}, R ← {C}

wake-up
reduce
true
suspend

∃C ∈ S · awake cond(C) ∧ R = ∅
S ← S − {C}, Q ← Q ∪ {C}
∃C ∈ A, ∃x ∈ var(C) · (Wx 6= ∅) ∧ R = ∅
Dx ← Dx − Wx
∃C ∈ A · solved cond(C) ∧ R = ∅
A ← A − {C}, T ← T ∪ {C}
∃C ∈ A ∧ R = ∅
A ← A − {C}, S ← S ∪ {C}

Figure 3: Propagation events.
tell(C)
told

Wx = Dx − redxC (D|var(C) )

Rule format : Name

A=∅
push h{C}, S, Q, T, R, Di
pop

Figure 4: Control events

Conditions
Def initions
Actions

Prototyping clp(fd) Tracers

7

The propagation is completely deﬁned by the rules given in Figure 3. The rules are
applied in the order in which they are given (from top to bottom). Each rule speciﬁes an
event type. An event modiﬁes the system state: hA, S, Q, T, R, Di. An event occurs when
its pre-conditions hold and no higher-priority event is possible. The rule priority prevents
redundant conditions. For example, a suspend event is made only when no true event is
possible. In the same way, if a reduce event wakes some constraints, all wake-up events are
performed before any other reduce. The rule system still contains some indeterminism: the
choice of C in the rules select and wake-up, and the choice of x in the rule reduce depends on
the solver strategy.
The rules are applied until all the constraints are in T , R and S. No further application
is possible. If R is non empty, the store is “rejected”. Otherwise, it may be considered that a
(set of) solution(s) has been obtained. All constraints in T are already solved. Therefore, any
tuple of values of V which satisﬁes the constraints in S is a solution. The way the computation
will continue depends of the control.

2.6

Control

The evolution of the store described so far assumes that the set of constraints in the store
is invariant, i.e., only their status is modiﬁed. The host constraint programming language
provides the way to build the store and to manage it, with possible interleaving of constraint
management and propagation steps.
In order to remain as independent as possible from the host language, we restrict the
control part to two events: the ﬁrst one adds a constraint C into the store (tell(C) event) and
the second one restores the store and the domains in some previous state (told event).
These events act on the store as illustrated in Figure 2. The tell event puts a new constraint
in the store as the active one.
In clp(fd) the control part is particularly simple and can be described by a (control) stack of
states of the system 5 . The state contains the current store and the domains. The propagation
phase is always performed in the state on top of the control stack. Each tell event includes
a constraint into the store, push the new state on the stack and is followed by a complete
propagation phase. When the ﬁx-point is reached either a new tell(C ′ ) is performed, or a
told. In the later case the stack is popped, thus the former state is restored. As long as the
control stack is not empty, new tell events can be performed on choice points and correspond
to alternative computations.
This semantics is formalized by the two rules of Figure 4. The push and pop operations
work on the control stack. With a diﬀerent host language, the same told event could be used
but with a possibly diﬀerent meaning.

3

Trace Definition

An execution is represented by a trace which is a sequence of events. An event corresponds
to an elementary step of the execution. It is a tuple of attributes. Following the notation of
Prolog traces, the types of events are called ports.
Most attributes are common to all events. For some ports, speciﬁc attributes are added.
For example, reduce events have two additional attributes: the withdrawn values Wx , for the
5

This corresponds to the description of the visit of a standard search-tree of Prolog [9].

8

WLPE’01

variable x whose domain is reduced, and the types of updates made, such a modiﬁcation of
the domain upper bound. The attributes are as follows.
Attributes for all events
• chrono: the event number (starting with 1);
• depth: the depth of the execution, starting with 0, it is incremented at each
tell and decremented at each told;
• port: the event type as presented in Sections 2.5 and 2.6: one of reduce,
wake-up, suspend, true, reject, select, tell and told;
• constraint: the concerned constraint, represented by a quadruple:
• a unique identiﬁer generated at its tell;
• an abstract representation, identical to the source formulation of the
program;
• an concrete representation (e.g. diffN(X, Y, N) for X ## Y + N or
X - N ## Y) ;
• the invocation context, namely the Prolog goal from which the tell is
performed.
• domains: the value of the variable domains before the event occurs;
• store: the content of the constraint store represented by the 5 components
described in section 2.4. Each set of constraints is represented by a list of
pairs (constraint identiﬁer, external representation):
• store A the set of active constraints;
• store S the set of suspended constraints;
• store Q the propagation queue;
• store T the set of solved constraints;
• store R the set of rejected constraints.
Specific attributes for reduce events
• withdrawn: The withdrawn domain
• update: The list of updates, an update is of the form (variable -> type),
where type can be one of ground, any, min, max, see Section 4 for further
explanation;
Specific attribute for wake-up events
• cause: The veriﬁed part of the awakening condition
The attributes are numerous and contain large chunks of information. Indeed, they aim
at providing useful information to automatic trace analysis programs. The more contents the
better. In a default display for users, only some attributes would be chosen. Furthermore,
and as in Opium [12] the trace analysis will be mainly done on the ﬂy, only the attributes
relevant to a given analysis will be retrieved, and no trace will be stored. Therefore there is
no a priori restriction on the number and size of attributes.
Figure 5 shows the source code of program sorted(L). The program sorts three numbers
between 1 and 3 in a very naive way. Following the convention of many systems, constraints
operators are preﬁxed by a “#”. The ﬁgure also shows a trace of the execution. All events
are listed but only with a few event attributes: the event number and port, the constraint
concerned by the event and its variable domains. At reduce events, the variable whose domain
is being reduced as well as the withdrawn values are added.
The ﬁrst two constraints are entered (tell) and suspended without any reduction (events
#1 to #4). The tell of the third one, Y #> Z gives two value withdrawals, ‘1’ from Dy (#6)

Prototyping clp(fd) Tracers

9

sorted([X, Y, Z]):[X, Y, Z] :: 1..3,
% At the beginning, Dx = Dy = Dz = [1..3]
X ## Y, X #>= Y, Y #> Z, % 3 constraints : x 6= y, x ≥ y and y > z
labelling([X, Y, Z]).
% labelling phase, with a “first fail” strategy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

[1]
[1]
[2]
[2]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]

Tell
Suspend
Tell
Suspend
Tell
Reduce
Wake-up
Reduce
Suspend
Select
Reduce
Suspend
Tell
Reduce
Wake-up
Wake-up
True
Select
Reduce
Wake-up

X##Y
X##Y
X#>=Y
X#>=Y
Y#>Z
Y#>Z
X#>=Y
Y#>Z
Y#>Z
X#>=Y
X#>=Y
X#>=Y
X#=2
X#=2
X#>=Y
X##Y
X#=2
X#>=Y
X#>=Y
Y#>Z

X:[1,2,3]
X:[1,2,3]
X:[1,2,3]
X:[1,2,3]
Y:[1,2,3]
Y:[1,2,3]
X:[1,2,3]
Y:[2,3]
Y:[2,3]
X:[1,2,3]
X:[1,2,3]
X:[2,3]
X:[2,3]
X:[2,3]
X:[2]
X:[2]
X:[2]
X:[2]
X:[2]
Y:[2]

Y:[1,2,3]
Y:[1,2,3]
Y:[1,2,3]
Y:[1,2,3]
Z:[1,2,3]
Z:[1,2,3] Y[1]
Y:[2,3]
Z:[1,2,3] Z[3]
Z:[1,2]
Y:[2,3]
Y:[2,3]
X[1]
Y:[2,3]
X[3]
Y:[2,3]
Y:[2,3]
Y:[2,3]
Y:[2,3]
Z:[1,2]

Y[3]

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[4]
[3]
[2]
[1]

True
Select
Reduce
Reject
Told
Tell
Reduce
Wake-up
True
Select
Reduce
Wake-up
True
Select
Reduce
True
Told
Told
Told
Told

X#>=Y
X##Y
X##Y
X##Y
X#=2
X#=3
X#=3
X##Y
X#=3
X##Y
X##Y
Y#>Z
X##Y
Y#>Z
Y#>Z
Y#>Z
X#=3
Y#>Z
X#>=Y
X##Y

X:[2]
X:[2]
X:[2]
X:[]
X:[]
X:[2,3]
X:[2,3]
X:[3]
X:[3]
X:[3]
X:[3]
Y:[2]
X:[3]
Y:[2]
Y:[2]
Y:[2]
X:[3]
Y:[2,3]
X:[1,2,3]
X:[1,2,3]

Y:[2]
Y:[2]
Y:[2]
Y:[2]

X[2]

X[2]
Y:[2,3]
Y:[2,3]
Y:[2,3] Y[3]
Z:[1,2]
Y:[2]
Z:[1,2]
Z:[1,2] Z[2]
Z:[1]
Z:[1,2]
Y:[1,2,3]
Y:[1,2,3]

chrono
depth
port
constraint
domains
withdrawn
update
store_A
store_Q

=
=
=
=
=
=
=
=
=

14
4
REDUCE
(4, X#=2, assign(var(1, X), 2), labelling([X, Y, Z]))
[X::[2..3], Y::[2..3], Z::[1..2]]
X::[3]
[X->any, X->ground, X->max]
[(4, X#=2)]
store_S = [(2, X#>=Y), (3, Y#>Z), (1, X##Y)]
[]
store_T = []
store_R = []

chrono
depth
port
constraint
domains
cause
store_A
store_Q

=
=
=
=
=
=
=
=

16
4
WAKE-UP
(1, X##Y, diff(var(1, X), var(2, Y)), sorted([X, Y, Z]))
[X::[2], Y::[2..3], Z::[1..2]]
[X->ground]
[(4, X#=2)]
store_S
= [(3, Y#>Z), (1, X##Y)]
[(2, X#>=Y)]
store_T = []
store_R = []

Figure 5: A trace of the execution of program sorted([X, Y, Z]), all events are present
with attributes (event number, [depth], constraint C, D|var(C) ). Events #14 and #16 are
displayed with all their attributes.

10

WLPE’01

and ‘3’ from Dz (#8). The ﬁrst reduction modiﬁes the lower bound of Dy and so wakes the
suspended constraint X #>= Y (#7). After those two reductions the constraint is suspended
and the waiting one is selected (#10). At event #12, the domains are Dx = {2, 3}, Dy = {2, 3}
and Dz = {1, 2}. Then the labelling phase begins. With our simple “ﬁrst fail” strategy, the
ﬁrst added constraint is X #= 2. X is ground and equal to 2 and this constraint is solved (#17).
Two other constraints are solved during the propagation, but it leads to Dy = {3}, Dz = {1, 2}
and an empty domain for X (#25). Another labelling constraint is tried (#26), X #= 3 and
leads to the unique solution {X:3, Y:2, Z:1}.

4

Deriving a Tracer from the Operational Semantics

In order to experimentally validate the trace deﬁned in Section 3, we derive, from the operational semantics of Section 2, a clp(fd) interpreter in Prolog that we instrument with trace
hooks. The resulting interpreter, which produces traces, is not meant to be an eﬃcient clp(fd)
system, but to be faithful to the semantics of Section 2. The faithfulness comes from the fact
that the translation of the semantic rules into executable Prolog code is syntactical.
In Section 2, we left the primitive constraints undeﬁned. We therefore ﬁrst propose a
deﬁnition for 8 primitive constraints by specifying, for each, its reduction operators, its solved
condition, and its awakening condition. Note that the deﬁnitions we propose in Table 1 deﬁne
reduction operators that perform a full-arc consistency.
Then, we show how to translate the primitive constraints and the semantic rules into
Prolog. We also show how to interface this Prolog code with the Prolog underlying system.

4.1

Primitive Constraint Definitions

In order to deﬁne a primitive constraint, we need to deﬁne its reduction operators, its solved
condition, and its awakening condition (see Section 2). We deﬁne in Table 1 the 8 primitive
constraints x = y, x 6= y, x = y + n, x 6= y + n, x > y, x ≥ y, x = n, and x 6= n, where x and
y represent two ﬁnite domain variables, and n represents an integer constant. The reduction
operator redxC is deﬁned by the set of values Wx it withdraws from the domain of variable x.
The equality constraint between two variables x and y (x = y) withdraws from the domains
of Dx and Dy the values which are not contained in both domains. The constraint is solved
only when the two variables are ground and have the same value v. At each modiﬁcation of
Dx or Dy , the reduction operators may withdraw new values. The constraints must therefore
be woken at each of their modiﬁcation.
The diﬀerence constraint between two variables x and y (x 6= y) can only reduce the
domains when one of them is ground. However, it is solved as soon as the two domains are
disjoint.

4.2

Data Structures

A constraint variable is represented by a term containing a unique integer, and a string
(its name in the source). A constraint instance is represented by a quadruple containing a
unique constraint number, a string (the constraint as displayed in the source, i.e., its abstract
representation), an internal (concrete) form, a list of constraint variables, and an invocation
context. The invocation context of a constraint is the Prolog goal from which it was invoked.

Prototyping clp(fd) Tracers
Constraint
C
x=y

Wx
Wy
Wx

x 6= y
Wy
x=y+n

x 6= y + n

x>y
x≥y
x=n
x 6= n

Reduction operators
(redxC (D|var(c) ) = Dx − Wx )
= Dx − (Dx ∩ Dy )
=D
 y − (Dx ∩ Dy )
{v} ∩ Dx if Dy = {v}
=
otherwise
 ∅
{v} ∩ Dy si Dx = {v}
=
∅
otherwise

Wx = Dx − (Dx ∩ {v + n, v ∈ Dy })
Wy = Dy − (Dx ∩ {v + n, v ∈ Dy })

{v + n} ∩ Dx if Dy = {v}
Wx =
otherwise
 ∅
{v − n} ∩ Dy if Dx = {v}
Wy =
∅
otherwise
Wx = {v ∈ Dx , v ≤ miny }
Wy = {v ∈ Dy , v ≥ maxx }
Wx = {v ∈ Dx , v < miny }
Wy = {v ∈ Dy , v > maxx }
Wx = D
 x − {n}
{n} if n ∈ Dx
Wx =
∅
otherwise

11
Solved condition
solved cond(C)

Awakening cond.
awake cond(C)

Dx = Dy = {v}

xany ∨ yany

Dx ∩ Dy = ∅

xground ∨ yground

Dx = {vx } ∧
Dy = {vy } ∧
vx = vy + n

xany ∨ yany

∀v ∈ Dy , v+n 6∈ Dx

xground ∨ yground

minx > maxy

xmax ∨ ymin

minx ≥ maxy

xmax ∨ ymin

Dx = {n}
n∈
/ Dx

Table 1: Characteristics of the primitive constraints implemented in the interpreter

The solver state is represented by a sextuplet: (A, S, Q, T, R, D), where A, S, Q, T and R
deﬁne the store as described in Section 2; they are lists of constraints. D is a list of domains.
In order to represent awakening conditions and domain narrowing, we deﬁne ﬁve types of
domain modiﬁcations (following what is done in Eclipse [14]). Each type refers to a particular
constraint variable x.
• xmin refers to a modiﬁcation of the Dx lower bound, e.g., {1, 2, 4} → {2, 4};
• xmax refers to a modiﬁcation of the Dx upper bound, e.g., {1, 2, 4} → {1, 2};
• xany refers to any modiﬁcation of Dx , e.g., {1, 2, 4} → {1, 4};
• xground refers to a grounding of x (Dx becomes a singleton), e.g., {1, 2, 4} → {1};
• xempty refers to an emptying of Dx , e.g., {1, 2, 4} → ∅
Those ﬁve modiﬁcation types respectively appear in the code as X->min, X->max, X->any,
X->ground, and X->empty. Awakening conditions are disjunctions of such modiﬁcation types;
such disjunctions are encoded by lists.

4.3

Translation of the Primitive Constraints

The reduction operators, the solved condition, and the awakening condition deﬁning a primitive constraint are encoded by the following predicates:
• cd reduction(+C, +D, +X, -Wx)6 : takes as input a constraint C, a domain state D,
and a constraint variable x; it succeeds iﬀ the application of redxC (D|var(C) ) withdraws
a non-empty set (bound to Wx). There is one clause per reduction operator of C;
6

As specified in the standard Prolog [9], + denotes input arguments and - denotes outputs arguments.

12
1
2
3
4
5
6
7
8

WLPE’01
cd_reduction(diff(X,Y),D,Y,[Vx]) :is_ground(X,D,Vx),
get_domain(Y,D,Dy),
member(Vx, Dy).
cd_reduction(diff(X,Y),D,X,[Vy]) :is_ground(Y,D,Vy),
get_domain(X,D,Dx),
member(Vy,Dx).

9
10
11
12
13
14
15

cd_awake(diff(X,Y),Cond) :Cond = [X->ground,Y->ground]).
cd_solved(diff(X,Y),D) :get_domain(X,D,Dx),
get_domain(Y,D,Dy),
d_intersection(Dx,Dy,[]).

Figure 6: Deﬁnition of the primitive constraint x 6= y: its two reduction operators, its solved
condition, and its awakening condition, as speciﬁed in Table 1.

• cd solved(+C, +D): takes as input a constraint C and a domain state D; it succeeds
iﬀ the constraint C is solved in the domain state D;
• cd awake(+C, -Cond): takes as input a constraint C and outputs (in Cond) the list of
awakening conditions of C.
Figure 6 shows the implementation of the primitive constraint x 6= y which is simply a
Prolog encoding of the ﬁrst entry of Table 1. The functor diff/2 is the internal encoding of
6=. Predicate is ground(+X, +D, -Vx) takes a constraint variable x and a domain D, and
succeeds iﬀ Dx is a singleton (bound to Vx); get domain(+X, +D, -Dx) takes a constraint
variable x and a domain state D, and outputs the domain of x (Dx ); d intersection(+D1,
+D2, -D) computes the intersection of two domains.

4.4

Translation of the Semantic Rules

Figure 7 contains the translation of the semantic rules of Figures 3 and 4. Each rule is encoded
by a predicate with the same name as the rule. The translation is merely syntactical, except
for the tell and told rules, for which it is unnecessary to save and restore the solver states
(push and pop) since this work is done by the Prolog backtracking mechanism.
Before paraphrasing the code for one rule, we give the meaning of all the (simple) predicates that are not deﬁned elsewhere in the paper: choose in queue(+Q0, -C) takes as input
a queue Q and outputs one of the queue constraints ; it succeeds iﬀ Q is not empty. The choice
of the constraint depends of the solver strategy; subtract(+L1, +L2, -L) computes the difference between two lists; get varC(+C, -V) takes as input a constraint C and outputs a
list of the constraint variables that appear in C; trace(+Port, +C, +St0, +O1, +O2, +O3)
takes as input the diﬀerent event attributes as described in Section 3; it calls the trace analysis
system which can, for example, print a trace line; put end of queue(+C, +Q0, -Q) puts a
constraint at the end of a queue; update domain(+X, +Wx, +D0, -D, -Mod) takes as input
a constraint variable x, a value set Wx (to withdraw), and a domain state D 0 ; it outputs the
state domain D such that Dx = Dx0 − Wx , and the list of modiﬁcation types xmod1 , ..., xmodn
(where modi ∈ {min, max, ground, any, empty}) that characterizes the Wx value removals;
internal(+C, -Ci) takes as input a constraint and outputs its internal representation.
All the predicates translating rules take as input a solver state St0 and output a new
solver state St. St0 and St respectively denote the state of the solver before and after the
application of a rule. The only exceptions are predicates wake up(+St0, -St, +ModIn) and
reduce(+St0, -St, -ModOut) that respectively inputs and outputs an additional argument:

Prototyping clp(fd) Tracers

13

a list of modiﬁcation types (xmod1 , ..., xmodn ). This list is computed in reduce/3 and used
in wake up/3 to check the awakening condition.
Predicate select(+St0, -St) translates the select rule. That rule needs to fulﬁll 3
conditions to be allowed to be applied: ∃C ∈ Q, that is checked line 17 by choose in queue/2
(which fails iﬀ the queue is empty); A = ∅ and R = ∅ that are checked line 15. The 2 actions
to perform when the conditions of the rule hold are Q ← Q − {C}, which is done line 18 by
subtract/3, and A = {C} which is done line 16. The other rules are translated in the same
way.

4.5

Integration with the Underlying Prolog System

The integration of our instrumented constraint solver with the underlying Prolog system is
done by the predicate call constraint/3 which is given in Figure 8. After propagation and
success, it returns the new state of the constraint part (St). If the propagation leads to a
failure, the goal fails.
Predicate prop step/4 performs a propagation step, i.e., it applies one of the 6 propagation rules of Figure 3; it fails if no rule can be applied. The choice of the rule to apply
is done according to the strategy discussed in Section 2.5. Predicate propagation/3 calls
prop step/4 in loop until either a propagation step fails (the ﬁx-point is reached) or the
solver rejects a constraint (the constraint goal is unsatisﬁable).

5

Experimentation

We have made some preliminary experiments of trace analysis with our tracer.
A ﬁrst experiment consists in displaying the labelling (or search-) tree. The analyzed
program solves the well known n-queens problem. Figure 9 shows a search-tree obtained for
the 4-queens problem by trace analysis of a trace generated by our meta-interpreter, and
displayed with dot [22]. Each variable corresponds to a row of the chess-board. The top node
of the displayed tree contains the initial domains, the other nodes contain the reduced domains
if any. The tree shows four failures in square boxes, two solutions and three choice points.
The uppest arc sums up the tell operations for all permanent constraints of the programs.
Each other arc represents a labelling constraint addition.
The trace analysis uses only the tell, told, reduce events. Few attributes were needed: the
port, the concerned constraint and the domains of constraint variables. For reduce events,
the updated variable and the withdrawn set were also needed.
The sequence of tell and told events in the trace corresponds to a depth-ﬁrst left-toright visit of the search-tree where tell and told events respectively correspond to downward
and upward moves in the search-tree. Reconstructing a tree from its visit (for a ﬁxed visit
strategy) is easy. In Figure 9, we took advantage of reduce events to label the nodes with the
propagation results.
A second experiment is the generation of a 3D variable update view [29]. The evolution
of the domains of the variables during the computation is displayed in three dimensions. It
gives a tool à la TRIFID [5] (here however colors are introduced to display speciﬁc events as
in the variable update view of [28]). The trace analyzer makes a VRML ﬁle by computing
domain size on each tell and reject event, and when a solution is found. The details of reduce

14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

WLPE’01

tell(C, St0, St)
St0 = ( [], S,
St = ([C], S,
trace(tell, C,

:Q, T, R, D),
Q, T, R, D),
St0, -, -, -).

told(C, St0) :trace(told, C, St0, -, -, -).

select(St0, St) :St0 = ( [], S, Q0, T, [], D),
St = ([C], S, Q, T, [], D),
choose_in_queue(Q0, C),
subtract(Q0, [C], Q),
trace(select, C, St0, -, -, -).
reject(St0, St) :St0 = ([C], S, Q, T, [], D),
St = ( [], S, Q, T, [C], D),
get_varC(C, VarC),
member(X, VarC),
get_domain(X, D, []),
trace(reject, C, St0, -, -, -).
wake_up(St0, St, ModIn) :St0 = (A, S0, Q0, T, [], D),
St = (A, S,
Q, T, [], D),
member(C, S0),
awake_cond(C, ModIn, True),
subtract(S0, [C], S),
put_end_of_queue(C, Q0, Q),
trace(wake_up, C, St0, True, -, -).

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

reduce(St0, St, ModOut) :St0 = ([C], S, Q, T, [],
St = ([C], S, Q, T, [],
get_varC(C, VarC),
member(X, VarC),
reduction(C, D0, X, Wx),
update_domain(X, Wx, D0,
trace(reduce, C, St0, X,
true(St0, St) :St0 = ([C], S,
St = ( [], S,
solved_cond(C,
T = [C|T0],
trace(true, C,

D0),
D),

D, ModOut),
Wx, ModOut).

Q, T0, [], D),
Q, T, [], D),
D),
St0, -, -, -).

suspend(St0, St) :St0 = ([C], S0, Q, T, [], D),
St = ( [], S, Q, T, [], D),
S = [C|S0],
trace(suspend, C, St0, -, -, -).

reduction(C, D, X, Wx) :internal(C, Ci),
cd_reduction(Ci, D, X, Wx).
awake_cond(C, ModIn, True) :internal(C, Ci),
cd_awake(Ci, Cond),
intersection(Cond, ModIn, True),
not True = [].
solved_cond(C, D) :internal(C, Ci),
cd_solved(Ci, D).

Figure 7: Prolog translation of the semantic rules of Figures 3 and 4

Prototyping clp(fd) Tracers

1
2
3
4
5
6
7
8
9
10
11
12

15

13
14
15
16
17
18
19
20
21

call_constraint(C, St0, St) :tell(C, St0, St1),
propagation(none, St1, St),
( true ; told(C, St), fail ),
St = (_, _, _, _, [], _).
propagation(Mod0, St0, St) :prop_step(St0, St1, Mod0, Mod)
-> ( St1 = (_, _, _, _, [], _)
-> propagation(Mod, St1, St)
; St = St1 )
; St = St0.

prop_step(St0, St, Mod0, Mod)
select(St0, St) -> Mod =
;
reject(St0, St) -> Mod =
;
wake_up(St0, St, Mod0)
-> Mod =
;
reduce(St0, St, Mod)
-> true
;
true(St0, St)
-> Mod =
;
suspend(St0, St) -> Mod =

:none
none
Mod0

none
none.

Figure 8: Integrating the constraint solver with the underlying Prolog system

A::[1..4]
B::[1..4]
C::[1..4]
D::[1..4]
A##B A##C A##D
B##C B##D C##D
A+1##B
A-1##B
A+2##C
A-2##C
A+3##D
A-3##D
B+1##C B-1##C B+2##D
B-2##D C+1##D C-1##D

A#=1
A -> 1
B -> [3..4]
C -> [2, 4]
D -> [2..3]
B#=3
B#=4
D -> 2
B -> 4
C -> 4
D -> 3
B -> []
C -> []

A -> 2
B -> 4
C -> 1
D -> 3

A#=2

A#=3
A -> 3
B -> 1
C -> 4
D -> 2

A#=4
A -> 4
B -> [1..2]
C -> [1, 3]
D -> [2..3]
B#=1
B#=2
B -> 1
B -> 2
C -> 3
D -> 3
D -> []
C -> []

Figure 9: A search-tree of a 4-queens constraint program execution, obtained by trace analysis,
and displayed by dot.

16

WLPE’01

Figure 10: Comparing two search procedures for the 40-queens problem with VRML views
computed by trace analysis.

events allow us to assign color to each kind of domain update (for example minimum or
maximum value removed or domain emptied) as made by Simonis and Aggoun in the Cosytec
Search-Tree Visualizer [28]. The trace analysis is implemented in about 125 lines of Prolog
and generates an intermediate ﬁle. A program implemented in 240 lines of C converts this
ﬁle into VRML format.
Figure 10 shows the resolution of the 40-queens problem with two diﬀerent labelling strategies. We have three axes: variables (horizontal axis of the vertical “wall”), domain size (vertical axis) and time. The ﬁrst strategy is a ﬁrst-fail selection of the labelled variable and the
ﬁrst value tried is the minimum of its domain. The second strategy is also a ﬁrst-fail strategy
but variable list is sorted with the middle variable ﬁrst and the middle of domain is preferred
to its minimum. This strategy derives from one described by Simonis and Aggoun [28]. This
approach allows to compare the eﬃciency of these two strategies by manipulating the 3Dmodel. With the ﬁrst strategy, we get a quick decreasing of the domain size on one side of
the chess-board and a long oscillation of the domain size on the other side. With the second
strategy, the decreasing of domain size is more regular and more symmetrical, the solution
is found faster. In fact, the second strategy, which consists in putting the queens from the
center of the chess-board, beneﬁts more from the symmetrical nature of the problem. The
possibility of moving manually the ﬁgure facilitates observation of such property.

6

Discussion and Conclusion

This article is a ﬁrst attempt to deﬁne new ports for tracing ﬁnite domain solvers. We do not
claim that the trace model presented here is the ultimate one. On the contrary we propose
a methodology to experiment and to improve it. This methodology is based on the following
steps: deﬁnition of an executable formal model of trace, extraction of relevant informations
by a trace analyzer, utilization of the extracted informations in several debugging tools. Each
debugging tool extracts from the same generic trace the information it needs.
The formal approach of trace modeling used here allows to clearly deﬁne the ports. Then
the implementation of the model by a meta-interpreter almost written in ISO-Prolog, a logic
programming language with a clear semantics, allows to preserve its correctness wrt the formal
model. This methodology is eﬃcient enough on small examples and therefore is of practical
interest. However to handle large realistic examples will require hard-coded implementation

Prototyping clp(fd) Tracers

17

of the trace model.
Diﬀerent aspects must be examined to estimate the results. First the formal model itself.
Two ports are directly related to logic programming (tell and told) and correspond to the
well-known ports call and exit of [3], the others correspond to a small number of diﬀerent
steps of computation of the reduction operator ﬁx-point. On the other side we deﬁned a great
number of (possibly large sized) attributes to ensure that each event carries enough potentially
useful informations. This immediately shows the limits of our model: it is probably general
enough to take into account several ﬁnite domain solvers, but tracing the complete behavior
of diﬀerent solvers will require new or diﬀerent ports to take into account diﬀerent kinds
of control, speciﬁc steps of computation (e.g. constraint posting, labelling phase, . . . ), or
diﬀerent algorithms.
The proposed methodology shows the way to progress: deﬁning the trace with a formal
model makes easier to compare diﬀerent trace models. It is thus easier to see which are
the missing ports or attributes. Some solvers use a propagation queue with events instead of
constraints (in this case new ports or same ports but with diﬀerent attributes are necessary), or
do not use backtracking (then told is never used). The question is also to ﬁnd the right balance
between the number of events and the attributes, in such a way that a hard-coded eﬃcient
implementation of (a part of) the trace model is still possible. For example the attribute
withdrawn of the port reduce concerns one variable only. Therefore if several variables are
involved by a single reduction step, there will be several reduce events. Another possibility
would be to have a unique event with a port whose withdrawn attribute includes several
variables at once. Gathering too many informations in one event may slow down the tracer
considerably. The trace production must be as fast as possible in order to keep the best
performances of the solver.
The ports and attributes presented here seem to be a good basis to start the study of
a generic trace for clp(fd). In [8] a sample of additional ports are suggested to cope with
diﬀerent ﬁnite domain solvers.
The second aspect concerns the extraction of tool speciﬁc relevant informations. The
generic trace, by deﬁnition, contains too many informations if used by a unique debugging
tool only. It is also not intended to be stored in a huge ﬁle, but it should be ﬁltered on the
ﬂy and re-formatted for use by some given tool. The methodology we proposed here, à la
opium, is well-known and has been shown to be eﬃcient and general enough to be used in
practice also in hard-coded implementations. It allows to specify the trace analysis in a high
level language (here Prolog) in a way which is independent from the trace production.
For each experimented tool we have presented here there is a speciﬁc analyzer which needs
only few lines of code. With this approach, building diﬀerent views of the same execution
requires only to modify the trace analyzer. Notice that the implementation presented here
assumes that there is only one trace analyzer running in parallel with the solver. The question
of how diﬀerent analyzers, working simultaneously, could be combined is not considered here.
Finally the third aspect concerns the experimentation. The main challenge in constraint
debugging is performance debugging. Our objective is to facilitate the development of constraint resolution analysis tools in a manner which is as independent as possible from the
solvers platforms. The three steps method (generic tracer/trace analyzer/debugging tool)
is a way to approach such a goal. We experimented it by building several analyzers and
(limited) tools very easily, without having to change the trace format. Of course much more
experiences are still needed.
Another way to estimate the results of this article is to consider some of the existing

18

WLPE’01

debugging tools and to observe that most of the informations relevant for each of these tools
are already present in the ports and their attributes. Here are brieﬂy reviewed some platform independent tools7 , namely debugging tools using graphical interfaces where labelling,
constraints and propagation can be visualized.
The Search-Tree Visualization tool for CHIP, described by Simonis and Aggoun [28] displays search-trees, variables and domain evolution. The whole of this information is present in
the proposed ports. Our experimentation shows that search-tree and constraints can easily be
displayed. The relevant information is also present for the Oz Explorer, a visual programming
tool described by Schulte [27], also centered on the search-tree visualization with user-deﬁned
displays for nodes. It is also the case in the search-tree abstractor described by Aillaud and
Deransart [1] where search-tree are displayed with constraints at the nodes.
In Grace, a constraint program debugger designed by Meier [25], users can get information on domain updates and constraint awakenings. This is available in our trace via our 8
ports. Grace also provides the ability to evaluate expressions using the current domain of the
variables. As the domain of the variables is an attribute of all events, it can be obtained by
any analyzer of our trace. The CHIP tool also provide update views in which, for example,
useless awakenings are visible. In our environment useless awakenings could be detected by a
select not followed by a reduce. The visualization tool by Carro and Hermenegildo [5] traces
the constraint propagation in 3 dimensions according to time, variable, and cardinal of the
domain. The required information is present in our trace. The S-boxes of Goualard and Benhamou [17] structure the propagation in and the display of the constraint store. Structuring
the propagation requires to modify the control in the solver. Displaying the store according
to the clausal structure would however cause no problem.
An important aspect, not presented in this paper, concerns the possibility of interactive
tools. This means that some debugging tools may request to re-execute some already traced
execution. Special mechanisms must be involved in order to re-execute eﬃciently and with
the same semantics some part of the execution. How such capability may inﬂuences the form
of the generic trace is still an open question and will be further investigated.

References
[1] C. Aillaud and P. Deransart. Towards a language for clp choice-tree visualisation. In
Deransart et al. [10], chapter 8.
[2] F. Benhamou. Interval constraint logic programming. In A. Podelski, editor, Constraint
Programming: Basics and Trends, pages 1–21. Springer-Verlag, Lecture Notes in Computer Science 910, 1994.
[3] L. Byrd. Understanding the control ﬂow of Prolog programs. In S.-A. Tärnlund, editor,
Logic Programming Workshop, Debrecen, Hungary, 1980.
[4] M. Carro and M. Hermenegildo. Tools for search-tree visualisation: The apt tool. In
Deransart et al. [10], chapter 9.
[5] M. Carro and M. Hermenegildo. The viﬁd/triﬁd tool. In Deransart et al. [10], chapter 10.
7
They are considered as (clp(fd)) platform independent tools in the sense that they are focused on general
properties of finite domain solving: choice-tree, labelling, variables domain evolution.

Prototyping clp(fd) Tracers

19

[6] Y. Caseau, F.-X. Josset, and F. Laburthe. Claire: combining sets, search and rules to
better express algorithms. In D. De Schreye, editor, Proc. of the 15th Int. Conference
on Logic Programming, pages 245–259. MIT Press, 1999.
[7] Cosytec. CHIP++ Version 5.2. documentation volume 6. http://www.cosytec.com, 1998.
[8] Romuald Debruyune, Jean-Daniel Fekete, Narendra Jussien, Mohammad Ghoniem,
Pierre Deransart, Ludovic Langevine, and e al. A proposal of concrete format for fracing
constraint programming (based on a dtd xml), October 2001. Deliverable D2.2.2.1 (in
French).
[9] P. Deransart, A. Ed-Dbali, and L. Cervoni. Prolog, The Standard; Reference Manual.
Springer Verlag, April 1996.
[10] P. Deransart, M. Hermenegildo, and J. Maluszyński, editors. Analysis and Visualisation
Tools for Constraint Programming. Number 1870 in LNCS. Springer Verlag, 2000.
[11] M. Ducassé. Abstract views of Prolog executions with Opium. In P. Brna, B. du Boulay,
and H. Pain, editors, Learning to Build and Comprehend Complex Information Structures: Prolog as a Case Study, Cognitive Science and Technology, chapter 10, pages
223–243. Ablex, 1999.
[12] M. Ducassé. Opium: An extendable trace analyser for Prolog. The Journal of Logic
programming, 39:177–223, 1999. Special issue on Synthesis, Transformation and Analysis
of Logic Programs, A. Bossi and Y. Deville (eds).
[13] M. Ducassé and J. Noyé. Logic programming environments: Dynamic program analysis
and debugging. The Journal of Logic Programming, 19/20:351–384, May/July 1994.
[14] ECLiPSe.
Constraint
icparc.doc.ic.ac.uk/eclipse/.

logic

programming

system.

http://www-

[15] G. Ferrand, W. Lesaint, and A. Tessier. Value withdrawal explanation in CSP. In
M. Ducassé, editor, AADEBUG’00 (Fourth International Workshop on Automated
Debugging), pages 188–201, 2000. The COmputer Research Repository (CORR)
cs.SE/0012005.
[16] GNU-Prolog. A clp(fd) system based on Standard Prolog (ISO) developed by D. Diaz.
http://gprolog.sourceforge.net/ Distributed under the GNU license.
[17] F. Goualard and F. Benhamou. Debugging Constraint Programs by Store Inspection. In
Deransart et al. [10], chapter 11.
[18] Y. Gurevitch. Evolving algebras, a tutorial introduction. Bulletin of the European Association for Theoretical Computer Science, 43:264–284, 1991.
[19] E. Jahier. Collecting graphical abstract views of Mercury program executions. In
M. Ducassé, editor, Proceedings of the International Workshop on Automated Debugging (AADEBUG2000), Munich, August 2000. The COmputer Research Repository
(CORR) cs.SE/0010038.

20

WLPE’01

[20] E. Jahier, M. Ducassé, and O. Ridoux. Specifying Prolog trace models with a continuation semantics. In K.-K. Lau, editor, Proc. of LOgic-based Program Synthesis and
TRansformation, London, July 2000. Springer-Verlag, Lecture Notes in Computer Science 2042.
[21] N. Jussien and V. Barichard. The PaLM system: explanation-based constraint programming. In Proceedings of TRICS: Techniques foR Implementing Constraint programming
Systems, a post-conference workshop of CP 2000, pages 118–133, Singapore, September
2000.
[22] E. Koutsoﬁos and S. North. Drawing graphs with dot. TR 910904-59113-08TM, AT&T
Bell Laboratories, 1991.
[23] Ludovic Langevine, Pierre Deransart, Mireille Ducasse, and Ewan Jahier. Tracing and analyzing execution of clp(fd) programs: a trace model and an experimental validation environment.
Rr, INRIA, Novembre 2001.
Full version of
this paper, Public Deliverable D1.2.1, to appear as INRIA/IRISA Research report.
http://contraintes.inria.fr/OADymPPaC/.
[24] K. Marriott and P.J. Stuckey. Programming with Constraints: An Introduction. The
MIT Press, Cambridge, Massachussets, 1998.
[25] M. Meier. Debugging constraint programs. In U. Montanari and F. Rossi, editors, Proceedings of the First International Conference on Principles and Practice of Constraint
Programming, number 976 in LNCS, pages 204–221. Springer Verlag, 1995.
[26] INRIA-Rocquencourt,
EMN-Nantes,
INSA-Rennes,
University of Orléans,
Cosytec, and ILOG.
Tools for dynamic analysis and development of constraint programs (OADymPPaC), November 2000.
An RNTL French Project.
http://contraintes.inria.fr/OADymPPaC.
[27] C. Schulte. Oz Explorer: A Visual Constraint Programming Tool. In Proceedings of the
Fourteenth International Conference on Logic Programming (Iclp’97), pages 286–300,
Leuven, Belgium, June 1997. The MIT Press.
[28] H. Simonis and A. Aggoun. Search-Tree Visualisation. In Deransart et al. [10], chapter 7.
[29] R. Zoumman. Analyse du comportement du solveur de contraintes basée sur la visualisation de traces (in French). Rapport de stage, INRIA, 2001.

