Previous: , Up: FDBG Advanced Usage   [Contents][Index]

10.14.4.6 Debugging Global Constraints

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)

A constraint visualizer that does no output, but notifies the user by calling Goal if a solution is lost through domain narrowings. Naturally you have to inform fdbg_guard/3 about the solution in question—stating which variables should have which values. To use fdbg_guard/3, first:

  1. Set it up as a visualizer by calling: 
    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.

  2. At the beginning of your program, form a pair of lists Xs-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 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:

Variable List

a list of Variable-Value terms for which Value was removed from the domain of Variable

Constraint

the constraint that was handled by the dispatcher

Actions

the action list returned by the dispatcher

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(fdbg)).
:- use_module(library(clpfd)).

queens(L, N) :-
        length(L, N),
        domain(L, 1, N),
        constrain_all(L),
        labeling([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),
     domain(L, 1, N),
     lex_chain([[2,4,1,3],L]),
     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 [2,4,1,3] and [3,1,4,2]. The constraint: 

lex_chain([[2,4,1,3],L]),

constraints the search to solutions lexicographically greater than or equal to the first correct solution, and FDBG is told to watch for its disappearance. At some point, the buggy constraint removes it, and 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 type ‘A’ (see FDBG Debugger Commands) to print the annotated form of the goal containing the culprit constraint. Finally, we type ‘A [2,4]’ to print the same information, but taking into account the action list, which is the 4th argument of the 2nd argument of the module prefixed goal. For clarity, the labeling events were not turned off in the session below.

This example shows how FDBG can be used to narrow down what causes invalid pruning. 

| ?- missing(L, [2,4,1,3]).
% The clp(fd) debugger is switched on
Labeling [8, <board_1>]: starting in range 2..4.
Labeling [8, <board_1>]: indomain_up: <board_1> = 2


FDBG Guard:
  4 was removed from <board_2>

Culprit constraint:

user:no_threat(2,<board_2>,1)
    board_2 = 1..4 -> {3}
    Constraint exited.

% The debugger will first creep -- showing everything (trace)
       11      2 Exit:
       clpfd:dispatch_global_fast(no_threat(2,_1511,1),0,0,
       [exit,_1511 in_set[[3|3]]],
       global('$mutable'(0,0),no_threat(2,_1511,1),'$mutable'(11,596),
       _10779,user:no_threat(2,_1511,1))) ? A

clpfd:dispatch_global_fast(no_threat(2,<board_2>,1),0,0,
        [exit,<board_2> in_set[[3|3]]],global($mutable(0,0),no_threat(2,<board_2>,1),
        $mutable(11,596),<fdvar_1>,user:no_threat(2,<board_2>,1)))
    board_2 = 1..4
    fdvar_1 = inf..sup

       11      2 Exit:
       clpfd:dispatch_global_fast(no_threat(2,_1511,1),0,0,
       [exit,_1511 in_set[[3|3]]],
       global('$mutable'(0,0),no_threat(2,_1511,1),'$mutable'(11,596),
       _23859,user:no_threat(2,_1511,1))) ? A [2,4]

clpfd:dispatch_global_fast(no_threat(2,<board_2>,1),0,0,
        [exit,<board_2> in_set[[3|3]]],global($mutable(0,0),no_threat(2,<board_2>,1),
        $mutable(11,596),<fdvar_1>,user:no_threat(2,<board_2>,1)))
    board_2 = 1..4 -> {3}
    fdvar_1 = inf..sup
    Constraint exited.

       11      2 Exit:
       clpfd:dispatch_global_fast(no_threat(2,_1511,1),0,0,
       [exit,_1511
       in_set[[3|3]]],global('$mutable'(0,0),no_threat(2,_1511,1),'$mutable'(11,596),
       _23859,user:no_threat(2,_1511,1))) ? a
% Execution aborted
% advice,source_info
| ?- fdbg_off.
% The clp(fd) debugger is switched off
Send feedback on this subject.