Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there any difference between using the "or" operator and using several clauses?

Tags:

prolog

What are the differences in results and execution, if any, between

memb(X, [Y,L]) :- X == Y ; memb(X,L).

and

memb(X, [Y,L]) :- X == Y.
memb(X, [Y,L]) :- memb(X,L).
like image 279
4xel Avatar asked Feb 16 '21 12:02

4xel


Video Answer


3 Answers

There is no difference. The first way of writing the program helps you keep the number of clauses small.

Although you will get a warning about "singleton variable L" in the second case as L is left unused in program 2, clause 1 and 2. This will alert you to a potential problem.

Bindings are unrolled when going through ;:

foo(X,Y) :- (X=2 ; X=Y).

Then

?- foo(X,Y).
X = 2 ;         % X is 2 but Y is left floating OR
X = Y.          % both variables are now "the same"

?- foo(X,4).
X = 2 ;         % X is 2 and Y is 4 OR 
X = 4.          % both X and Y are 4.

The compiler does not directly transform the code though.

In SWI-Prolog:

Case 1:

?- listing(memb/2).
memb(A, [B, C]) :-
    (   A==B
    ;   memb(A, C)
    ).

Case 2:

?- listing(memb/2).
memb(A, [B, _]) :-
    A==B.
memb(A, [_, B]) :-
    memb(A, B).
like image 44
David Tonhofer Avatar answered Oct 13 '22 20:10

David Tonhofer


There is no semantic difference but there may be a performance difference when calling the predicate. Let's illustrate that with an example:

walk([]).
walk([_| Tail]) :-
    walk(Tail).

Assuming a Prolog system implementing first-argument indexing, the following queries don't create any choice-point:

| ?- walk([]).
yes

| ?- walk([_,_,_]).
yes

We can rewrite the walk/1 predicate into a single, semantically equivalent clause:

walk(List) :- List = []; List = [_| Tail], walk(Tail).

But now we will get:

| ?- walk([]).                                             
true ? ;
no

| ?- walk([_,_,_]).                                        
true ? ;
no

I.e. we lost the benefit of first-argument indexing in avoiding the creation of spurious choice-points (when calling the walk/1 predicate with a bound argument).

Writing clauses whose body is a disjunction is usually not a good programming idiom. In most cases, using separate clauses makes the code easier to read and (as the example above illustrates) more efficient. But most coding guideline rules have exceptions and that's also the case here. Sometimes a clause head unifies with one or more argument sub-terms, a relatively costly operation. For example:

foo([_, _, Three| _], bar(_, [_, Second]), _) :-
    ...

This is an artificial example but complex head unifications can often be found in non-trivial code. The cost of the complex clause head unification across several clauses that repeat it may be avoided by using a single clause and disjunctions as it would only be done once (per call to the predicate).

like image 193
Paulo Moura Avatar answered Oct 13 '22 19:10

Paulo Moura


I think that a detailed answer to your question could get very technical, well beyond my know-how... but surely you should consider the efficiency implications of avoiding costly tests, made possible by the 'syntax sugar' introduced by the 'or' operator.


a_rule(...) :-
  costly_preamble(...),
  ( costly_test(...),
    take_a_path(...)
  ; take_another(...)
  ).

Apart the obvious efficiency implications illustrated by goals naming, also note that take_another(...) will be executed if costly_test(...) or take_a_path(...) would fail.

The if/then/else construct (->)/2 has been introduced long ago to alleviate such problems...

like image 43
CapelliC Avatar answered Oct 13 '22 21:10

CapelliC