Search code examples
coding-styleprologdeterministic

Implementing often-occuring determinism patterns in Prolog

When programming in Prolog I often write predicates whose behavior should be semi-deterministic when called with all arguments instantiated (and whose behavior should be non-deterministic otherwise).

A concrete use case for this is my predicate walk/3, which implements graph walks. Since multiple paths can exist between two vertices, the instantiation (+,+) gives multiple choicepoints after true. These are, however, quite useless. Calling code must explicitly use once/1 for performance reasons.

%! walk(+Graph:ugraph, +StartVertex, +EndVertex) is semidet.
%! walk(+Graph:ugraph, -StartVertex, +EndVertex) is nondet.
%! walk(+Graph:ugraph, +StartVertex, -EndVertex) is nondet.
%! walk(+Graph:ugraph, -StartVertex, -EndVertex) is nondet.

Semi-determinism can be forced by the use of once/1 in the calling context, but I want to implement semi-determinism as a property of the predicate walk/3, and not as something that has to be treated specially every time it is called.

In addition to concerns over code aesthetics, the calling context need not always know whether its call to walk/3 is semi-deterministic or not. For example:

%! cycle(+Graph:ugraph, +Vertex) is semidet.
%! cycle(+Graph:ugraph, -Vertex) is nondet.

cycle(Graph, Vertex):-
  walk(Graph, Vertex, Vertex).

I have come up with the following solution, which does produce the correct behavior.

walk_wrapper(Graph, Start, End):-
  call_ground_as_semidet(walk(Graph, Start, End)).

:- meta_predicate(call_ground_as_semidet(0)).
call_ground_as_semidet(Goal):-
  ground(Goal), !,
  Goal, !.
call_ground_as_semidet(Goal):-
  Goal.

However, this solution has deficiencies:

  • It's not generic enough, e.g. sometimes ground should be nonvar.
  • It is not stylistic, requiring an extra predicate wrapper every time it is used.
  • It may also be slightly inefficient.

My question is: are there other ways in which often-occurring patterns of (non-)determinism, like the one described here, can be generically/efficiently/stylistically programmed in Prolog?

Solution

  • You should experiment with double negation as failure. Yes a ground goal can only be true or false, so it should not leave any choice points. Lets assume we have an acyclic graph, to make matters simple:

    enter image description here

    If I use this code:

    edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

path(X,X).
path(X,Y) :- edge(X,Z), path(Z,Y).

    The Prolog system will now leave choice points for closed queries:

    ?- path(a, e).
true ;
true ;
true ;
true ;
true ;
false.

    In my opinion the recommended approach, to eliminate these choice points and nevertheless have a multi-moded predicate, is to use so called meta-programming in Prolog.

    meta-programming is also sometimes derogeratively called non-logical programming, since it is based on non-logical predicates such as ground/1, !/0 or (+)/1. But lets call it meta-programming when declarativity is not impacted.

    You could write a wrapper smart/1 as follows, doing the same as your call_ground_as_semidet/1, but with a small nuance:

    smart(G) :- ground(G), !, \+ \+ G.
smart(G) :- G.

    The Prolog system will not anymore leave a choice point for closed queries:

    ?- smart(path(a,e)).
true.

    The advantage of \+ \+ over once, is that the former does not only leave no choice points, but also removes the trail. It is sometimes called the garbage collection meta-predicate of Prolog.