Node:FDBG Debugging Global Constraints, Next:FDBG Code of the Built-In Visualizers, Previous:FDBG Showing Selected Constraints (advanced version), Up:FDBG Advanced Usage
Missing pruning and excessive pruning are the two major classes of bugs in the implementation of global constraints. Since CLP(FD) is an incomplete constraint solver, missing pruning is mainly an efficiency concern (but ground instances for which the constraint does not hold should be rejected). Excessive pruning, however, means that some valid combinations of values are pruned away, leading to missing solutions. The following exported predicate helps spotting excessive pruning in user-defined global constraints:
fdbg_guard(:Goal, +Constraint, +Actions)
fdbg_guard/3 about the solution in
question--stating which variables should have which values. To
use fdbg_guard/3, first:
fdbg_on([..., constraint_hook(fdbg_guard(Goal)), ...])
As usual, the two other arguments will be supplied by the FDBG core when
calling fdbg_guard/3.
-Vsfdbg_guard using
?- fdbg_assign_name(Xs-Vs, fdbg_guard).
When these steps have been taken, fdbg_guard/3 will watch the
domain changes of Xs done by each global constraint C.
Whenever Vs is in the domains of Xs at entry to C, but
not at exit from C, Goal is called with three more
arguments:
-ValueWe will now show an example using fdbg_guard/3. First, we will need a
few extra lines of code:
%% print_and_trace(MissValues, Constraint, Actions): To be used as a Goal for
%% fdbg_guard to call when the given solution was removed from the domains
%% of the variables.
%%
%% MissValues is a list of Var-Value pairs, where Value is the value that
%% should appear in the domain of Var, but has been removed. Constraint is
%% the current constraint and Actions is the list of actions returned by it.
%%
%% This predicate prints MissValues in a textual form, then shows the current
%% (culprit) constraint (as done by fdbg_show/2), then turns on the Prolog
%% tracer.
print_and_trace(MissValues, Constraint, Actions) :-
print(fdbg_output, '\nFDBG Guard:\n'),
display_missing_values(MissValues),
print(fdbg_output, '\nCulprit constraint:\n\n'),
fdbg_show(Constraint, Actions),
trace.
display_missing_values([]).
display_missing_values([Var-Val|MissVals]) :-
fdbg_annotate(Var,AVar,_),
format(fdbg_output, ' ~d was removed from ~p~n', [Val,AVar]),
display_missing_values(MissVals).
Suppose that we have written the following N Queens program, using
a global constraint no_threat/3 with a bug in it:
:- use_module(library(clpfd)).
:- use_module(library(fdbg)).
queens(L, N) :-
length(L, N),
domain(L, 1, N),
constrain_all(L),
labeling([ff,enum], L).
constrain_all([]).
constrain_all([X|Xs]):-
constrain_between(X,Xs,1),
constrain_all(Xs).
constrain_between(_X,[],_N).
constrain_between(X,[Y|Ys],N) :-
no_threat(X,Y,N),
N1 is N+1,
constrain_between(X,Ys,N1).
no_threat(X,Y,I) :-
fd_global(no_threat(X,Y,I), 0, [val(X),val(Y)]).
:- multifile clpfd:dispatch_global/4.
clpfd:dispatch_global(no_threat(X,Y,I), S, S, Actions) :-
ground(X), !,
remove_threat(Y, X, I, NewYSet),
Actions = [exit, Y in_set NewYSet].
clpfd:dispatch_global(no_threat(X,Y,I), S, S, Actions) :-
ground(Y), !,
remove_threat(X, Y, I, NewXSet),
Actions = [exit, X in_set NewXSet].
clpfd:dispatch_global(no_threat(_,_,_), S, S, []).
remove_threat(X, V, I, Set) :-
Vp is V+I+1, % Bug introduced here
% Vp is V+I, % Good code
Vn is V-I,
fd_set(X, Set0),
list_to_fdset([Vn, V, Vp], VSet),
fdset_subtract(Set0, VSet, Set).
missing(L, Tuple) :-
length(Tuple, N),
length(L, N),
fdbg_assign_name(L-Tuple, fdbg_guard),
fdbg_assign_name(L, board),
fdbg_on(constraint_hook(fdbg_guard(print_and_trace))),
queens(L, N).
We will now use print_and_trace/3 as an argument to the fdbg_guard
visualizer to handle the case when a solution has been removed by a
constraint. The bug shown above causes three
invalid solutions to be found instead of the two correct solutions.
FDBG is told to watch for the disappearance of the first correct
solution, [2,4,1,3]. First, we get two incorrect solutions before
FDBG wakes up, because in these cases the given good solution was made
impossible by a labeling event. The second branch of labeling does
not by itself remove the solution, but at some point on that branch the
bad constraint does remove it, so fdbg_guard/3 calls the given
predicate. This prints the cause of waking (the value which should
not have been removed by the constraint), prints the constraint
itself, then switches the Prolog debugger to trace mode.
At this point, we use the A debugger command (see FDBG Debugger Commands)
to print the annotated form of the goal containing the culprit constraint.
For clarity, the labeling events were not turned off in the session below.
This information can be used to track down why the buggy no_threat/3
performed the invalid pruning.
| ?- missing(L, [2,4,1,3]).
% The clp(fd) debugger is switched on
Labeling [8, <board_1>]: starting in range 1..4.
Labeling [8, <board_1>]: indomain_up: <board_1> = 1
Labeling [13, <board_2>]: starting in range {2}\/{4}.
Labeling [13, <board_2>]: dual: <board_2> = 2
L = [1,2,3,4] ? ;
Labeling [13, <board_2>]: dual: <board_2> = 4
L = [1,4,2,3] ? ;
Labeling [13, <board_2>]: failed.
Labeling [8, <board_1>]: indomain_up: <board_1> = 2
FDBG Guard:
4 was removed from <board_2>
Culprit constraint:
no_threat(2,<board_2>,1)
board_2 = 1..4 -> {3}
Constraint exited.
% The debugger will first creep -- showing everything (trace)
23 2 Exit: clpfd:dispatch_global_fast(no_threat(2,_1001,1),0,0,
[exit,_1001 in_set[[3|3]]]) ? A
clpfd:dispatch_global_fast(no_threat(2,<board_2>,1),0,0,
[exit,<board_2> in_set[[3|3]]])
board_2 = 1..4
23 2 Exit: clpfd:dispatch_global_fast(no_threat(2,_1001,1),0,0,
[exit,_1001 in_set[[3|3]]]) ? A [2,4]
clpfd:dispatch_global_fast(no_threat(2,<board_2>,1),0,0,
[exit,<board_2> in_set[[3|3]]])
board_2 = 1..4 -> {3}
Constraint exited.
23 2 Exit: clpfd:dispatch_global_fast(no_threat(2,_1001,1),0,0,
[exit,_1001 in_set[[3|3]]]) ? a
% Execution aborted
% advice,source_info
| ?- fdbg_off.
% The clp(fd) debugger is switched off