Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What use does if_/3 have?

The predicate if_/3 seems to be fairly popular among the few main contributors in the Prolog part of Stack Overflow.

This predicate is implemented as such, courtesy of @false:

if_(If_1, Then_0, Else_0) :-    call(If_1, T),    (  T == true -> call(Then_0)    ;  T == false -> call(Else_0)    ;  nonvar(T) -> throw(error(type_error(boolean,T),_))    ;  /* var(T) */ throw(error(instantiation_error,_))    ). 

However, I have been unable to find a clear, simple, and concise explanation of what this predicate does, and what use it has compared to e.g. the classical if-then-else construct of Prolog if -> then ; else.

Most links I have found directly use this predicate and provide little explanation as to why it gets used, that a non-expert in Prolog could understand easily.

like image 551
Fatalize Avatar asked Oct 03 '16 13:10

Fatalize


1 Answers

In old-fashioned Prolog code, the following pattern arises rather frequently:

 predicate([], ...). predicate([L|Ls], ...) :-         condition(L),         then(Ls, ...). predicate([L|Ls], ...) :-         \+ condition(L),         else(Ls, ...). 

I am using lists here as an example where this occurs (see for example include/3, exclude/3 etc.), although the pattern of course also occurs elsewhere.

The tragic is the following:

  • For an instantiated list, pattern matching can distinguish the first clause from the remaining two, but it cannot distinguish the second one from the last one because they both have '.'(_, _) as the primary functor and arity of their first argument.
  • The conditions in which the last two clauses apply are obviously mutually exclusive.
  • Thus, when everything is known, we want to obtain an efficient, deterministic predicate that does not leave choice points, and ideally does not even create choice points.
  • However, as long as not everything can be safely determined, we want to benefit from backtracking to see all solutions, so we cannot afford to commit to either of the clauses.

In summary, the existing constructs and language features all fall short in some way to express a pattern that often occurs in practice. Therefore, for decades, it seemed necessary to compromise. And you can make a pretty good guess in which direction the "compromises" usually go in the Prolog community: Almost invariably, correctness is sacrificed for efficiency in case of doubt. After all, who cares about correct results as long as your programs are fast, right? Therefore, until the invention of if_/3, this was frequently wrongly written as:

 predicate([], ...). predicate([L|Ls], ...) :-         (    condition(L) ->              then(Ls, ...).         ;    else(Ls, ...).         ) 

The mistake in this is of course that when the elements are not sufficiently instantiated, then this may incorrectly commit to one branch even though both alternatives are logically possible. For this reason, using if-then-else is almost always declaratively wrong, and stands massively in the way of declarative debugging approaches due to its violation of the most elementary properties we expect from pure Prolog programs.


Using if_/3, you can write this as:

 predicate([], ...). predicate([L|Ls], ...) :-         if_(condition(L),             then(Ls, ...),             else(Ls, ...)). 

and retain all desirable aspects. This is:

  • deterministic if everything can be safely decided
  • efficient in that it does not even create choice points
  • complete in that you never incorrectly commit to one particular branch.

The price of this is rather affordable: As Boris mentioned in the comments, you need to implement a reification. I have now some experience with this and found it rather easy with some practice.

Good news everyone: In many cases, condition is of the form (=)/2, or (#=)/2, and the first even ships with library(reif) for free.

For more information, see Indexing dif/2 by Ulrich Neumerkel and Stefan Kral!

like image 52
mat Avatar answered Sep 25 '22 09:09

mat