Det-if?

Some Prolog predicates are deterministic under certain (mode) conditions. One way to program this is e.g.

p(X) :-
     (   ground(X)
     ->  q(X), !
     ;   q(X)
     ).

This is a bit cumbersome to write though. I think I’ve seen a meta predicate to generalize this. Does anyone know about such practice? Otherwise, I’d consider this. Next, we also need a good library …

det_if(Cond, Goal) :-
    (   Cond
    ->  Goal,
        !
    ;   Goal
    ).

Shouldn’t this be the responsability of the predicate q to be deterministic under these conditions ?

Do you have a specific example in mind ?

Surely, you want to put the responsibility of being (semi)det as low as possible. In this case (and I’ve seen quite a few similar ones), I have a notdet predicate that produces properties. If we want to check that some property exists, we’d like to write

  xyz_property(p(1)).

But, the underlying predicate makes this non-det. Now, I can re-implement it as below. This is nice and compact and expresses exactly what I want.

xyz_property(P) :-
    det_if(ground(P), xyz_property_(P)).

xyz_property_(P) :-
   ...

Thinking about it, distinct/1,2 can also be improved this way. Tabling already does this: if the goal is ground and it finds an answer it considers the table immediately complete.

1 Like

All the predicates that q calls would also have to be deterministic.

How to improve determinism, whilst decreasing code elegance the least? :grinning:

append/3 is an example:

?- append([a,b], ObviouslyEmpty, [a,b]).
ObviouslyEmpty = [].  % Deterministic

?- append(ObviouslyEmpty, [a,b], [a,b]).
ObviouslyEmpty = [] ;
false.  % Unwanted choicepoint

Removing that unwanted choicepoint in some way, by adding relatively ugly code, is easy.

Removing that unwanted choicepoint in an elegant way, is not easy.

I suppose the aim here is to prevent having to add code which is not increasing the fundamental correctness of the code.

It would be really nice if the Prolog engine could infer determinism by itself - do we have AI yet? :smiley:

When writing foreign predicates, I’ve fairly often had the situation where I check the 1st arg for being a variable, such as the way current_prolog_flag/2 works. This seems to be a common use case, with two alternative goals rather than the same goal with a cut:

p(X, Y) :-
    (  var(X)
    -> lookup_something(X, Y) % call deterministic goal
    ;  backtracking_lookup(X, Y)
    ).

and there can also be a variant:

p(X, Y) :-
    (  var(X)
    -> p_lookup(X, Y) % call deterministic goal
    ;  var(Y)
    -> p_lookup_reverse(Y, X) % call deterministic goal
    ;  p_lookup_backtracking(X, Y)
    ).

In some cases, I can tell if there are no more choices and remove a choicepoint. E.g., the code for between/3 proactively computes the next result and checks if it’s the last one, in which case it does a “return” rather than “return with choiceoint” (PL_retry_address()).

That us more or less what needs to happen, but it is a little ugly :slight_smile: The det_if/2 would deal with the (I think) fairly common case that the implementation for both cases is the same, but we cannot guarantee determinism for the ground case.

I don’t recall encountering this … do you have an example?
I have had situations where the predicate is deterministic or not, depending on the next value, for example between/3.

I have seen them before. In this case I have a file holding Prolog (feature) terms and a nondet predicates that backtracks through these terms. A predicate has_feature(File, Term) should be semidet if Term is ground and nondet otherwise. Of course, the caller can use once/1, but that is rather inelegant. So, the implementation becomes the rather ugly

has_feature(File, Feature) :-
    ground(Feature),
    !,
    once(term_in_file(File, Feature)).
has_feature(File, Feature) :-
    term_in_file(File, Feature).

term_in_file(File, Feature) seems similar to member/2 (I presume it can backtrack through multiple occurrences of matching Feature in File), so perhaps what you want is the analogue of memberchk/2: term_in_file_chk(File, Feature)?

That is a solution, but IMO less elegant. You need an extra predicate and the interface becomes less logical than it could be. That would, for 99% of the applications, also hold for member/2, but here the list also needs to be ground. If the list holds non-ground terms, backtracking using a ground member can be just fine. The well known Einstein riddle solutions often use that.

Abusing => notation a bit:

:- meta_predicate det_cond_goal(0, 0).

det_cond_goal(Cond, Goal), Cond, Goal => true.
det_cond_goal(_Cond, Goal) => Goal.
has_feature(File, Feature) :-
    det_cond_goal(ground(Feature), 
                  term_in_file(File, Feature)).

det_cond_goal/2 is just another name and implementation for det_if/2, no? The original question is whether there is current practice for such a predicate and whether or not we want it in a library? And, if we decide we want it while there is no current practice, how we name it?

P.s., the implementation is wrong. You have to commit twice, both after the condition and after the goal.