Run deterministic goals first, to improve performance and determinism

Nice to know
1

Here is code to call/1 a list of goals, reordering the list to call the deterministic goals first.

Deterministic goals are defined at SWI-Prolog -- Testing deterministic predicates - they succeed exactly once, and might have choicepoints - the choicepoints will result in failure.

% Calls the deterministic Goals first
% Goals must be free from side-effects
deferred_goals(Goals) :-
    deferred_goals_(Goals, uncert, Us-Us).
    
deferred_goals_([], C, Us-[]) :-
    deferred_goals_cert_(C, Us).
deferred_goals_([G|Gs], C, Us-T) :-
    % Check whether only 1 solution
    (   \+ call_nth(G, 2)
    ->  call(G),
        % Is a certainty, so can remove any choicepoints
        !,
        % Flag that a certainty has been applied
        deferred_goals_(Gs, cert, Us-T)
    ;   T = [G|T0],
        deferred_goals_(Gs, C, Us-T0)
    ).  
    
deferred_goals_cert_(uncert, Us) :-
    % The certainties have already been applied
    maplist(call, Us).
deferred_goals_cert_(cert, Us) :-
    % Try again - some Goals might now be certainties
    deferred_goals(Us).

As a simple example:

?- time(((X=1;X=2), X=2, (X=2;X=3;false))).
% 3 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 53317 Lips)
X = 2 ;
% 9 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 439947 Lips)
false.

… which can be rewritten as:

?- time(deferred_goals([(X=1;X=2), X=2, (X=2;X=3;false)])).
% 60 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 902514 Lips)
X = 2.

There is only 1 successful “path” through these goals and their choices, so the choicepoints have been removed.

As a motivating example - here is the popular Einstein puzzle, as a reasonably efficient Prolog solution: language agnostic - Solving "Who owns the Zebra" programmatically? - Stack Overflow

I am ignoring its redefinition of select/3. It runs:

?- time(zebra(Owns, Hs)).
% 604 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 5770021 Lips)
Owns = german,
Hs = [h(yellow, norwegian, cats, water, dunhill), h(blue, dane, horse, tea, blend), h(red, brit, birds, milk, pallmall), h(green, german, zebra, coffee, prince), h(white, swede, dog, beer, bluemaster)] ;
% 1,097 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 8450878 Lips)
false.

It can be rewritten as:

left_of(A,B,C):- append(_,[A,B|_],C).
next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C).

zebra(Owns, HS):-     % (* house: color,nation,pet,drink,smokes *)
    HS   = [ h(_,norwegian,_,_,_),    h(blue,_,_,_,_),   h(_,_,_,milk,_), _, _],
    Goals = [
        select([ h(red,brit,_,_,_),       h(_,swede,dog,_,_),
            h(_,dane,_,tea,_),       h(_,german,_,_,prince)], HS),
        select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill),
            h(_,_,_,beer,bluemaster)],                        HS),
        left_of( h(green,_,_,coffee,_),   h(white,_,_,_,_),        HS),
        next_to( h(_,_,_,_,dunhill),      h(_,_,horse,_,_),        HS),
        next_to( h(_,_,_,_,blend),        h(_,_,cats, _,_),        HS),
        next_to( h(_,_,_,_,blend),        h(_,_,_,water,_),        HS),
        member(  h(_,Owns,zebra,_,_),                              HS)
    ],
    deferred_goals(Goals).

… which runs as:

?- time(zebra(Owns, Hs)).
% 600 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 2213655 Lips)
Owns = german,
Hs = [h(yellow, norwegian, cats, water, dunhill), h(blue, dane, horse, tea, blend), h(red, brit, birds, milk, pallmall), h(green, german, zebra, coffee, prince), h(white, swede, dog, beer, bluemaster)] ;
% 55 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 742751 Lips)
false.

The total number of inferences has been better than halved, by reordering to leave the multiple-solution goals until last :grinning_face:

As evidence that the inference count corresponds as expected to performance:

% Without using deferred_goals
?- time((between(1, 50_000, _), zebra(Owns, Hs), fail)).
% 84,999,999 inferences, 8.454 CPU in 8.454 seconds (100% CPU, 10054264 Lips)
false.

vs:

% Using deferred_goals
?- time((between(1, 50_000, _), zebra(Owns, Hs), fail)).
% 32,699,999 inferences, 3.016 CPU in 3.016 seconds (100% CPU, 10842352 Lips)
false.

Caveats:

  • The goals must be free from side-effects
  • The goals must not be sensitive to their execution order
1 Like