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 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:

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(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