# Run deterministic goals first, to improve performance and determinism

**URL:** <https://swi-prolog.discourse.group/t/run-deterministic-goals-first-to-improve-performance-and-determinism/8893>\
**Category:** Nice to know\
**Created:** [March 24, 2025, 10:20pm UTC](https://swi-prolog.discourse.group/t/run-deterministic-goals-first-to-improve-performance-and-determinism/8893 "2025-03-24T22:20:30Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [March 24, 2025, 10:20pm UTC](https://swi-prolog.discourse.group/t/run-deterministic-goals-first-to-improve-performance-and-determinism/8893/1 "2025-03-24T22:20:30Z")

</div>

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](https://www.swi-prolog.org/pldoc/man?section=testdet) - they succeed exactly once, and might have choicepoints - the choicepoints will result in failure.

```prolog
% 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:

```prolog
?- 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:

```prolog
?- 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](https://stackoverflow.com/a/8270393/17628336)

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

```prolog
?- 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:

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

```prolog
?- 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 😀

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

```prolog
% 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:

```prolog
% 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