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.
-Vs where Xs is the list of
variables and Vs is the list of values in question.
This pair should then be assigned the name fdbg_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:
-Value terms for which
Value was removed from the domain of Variable
We 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 that 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