swi prolog: conjunction and cut

Question

I am trying to implement a prolog interpreter in java. I am trying to figure out how the ',' operator should work. I tried to implement an equivalent rule like this:

and(A, B) :- A, B.

I am testing my implementation based on the logic base below with test cases c1, c2 and c3. All of them should output '1' and 'false'. I noticed, however, that the last rule (c3) prints '12' and 'false'. I ran the same test in SWI prolog and there too, the last rule outputs '12' and 'false'.

So is my assumption incorrect, that the comma operator can be coded as ','(X, Y) :- X, Y.?

n(1).
n(2).
and(X, Y) :- X, Y. % this is used to compare with the built in operator ','

c1 :-     n(X),     write(X),     =(1, X),     !, fail.
c2 :- ','(n(X), ','(write(X), ','(=(1, X), ','(!, fail)))).
c3 :- and(n(X), and(write(X), and(=(1, X), and(!, fail)))).

The cut applies prunes backtracking within the context of predicate clause in which it is called. So and(!, fail) will fail and backtrack in the place where it was called. Whereas, ','(!, fail), being the same as !, fail will not backtrack. So the behavior of and(!, fail) is not the same as !, fail. You would have to write and(!, fail), !. — lurker
@lurker, thanks for the answer. I will need to chew on it for a while. What I find hard to understand is that c1 apparently is equivalent to c2 but c2 isn't equivalent to c3. The fact that ',' is an operator while 'and/2' is a rule appears to be the difference? — wolare
In Prolog, there is a predicate called write_canonical(X) which lets you write a term the way Prolog sees it canonically. Try write_canonical((A, B)). — lurker

lambda.xy.x lambda.xy.x · Accepted Answer · 2018-08-08T11:07:08

You are correct about the nature of , as binary function but the translation to and does not yet explain how to interpret the conjunction. Let's have a look at a general Prolog rule:

head :-  % we disregard variables at the moment
  goal1,
  goal2,
  goal3.

fact. % a fact is a rule without a body

This can be read as "the goals imply the head" or alternatively "to derive the head we need to derive each of the goals". But goal1 might be a rule itself, so we need some kind of TODO list (usually implemented as a stack but the exact behaviour does not matter right now). We start with the query on our TODO list. If an element of the list is a fact, we can just remove it. To remove a rule, we need to derive all the goals so we replace the head on the list with the goals. Let's look at it with an example:

make(coffee).
make(tea).
make(orange_juice).
make(croissant).
make(scrambled_eggs).

prepare(beverage) :-
    make(coffee).
prepare(beverage) :-
    make(tea).
prepare(beverage) :-
    make(orange_juice).
prepare(food) :-
    make(croissant).
prepare(food) :-
    make(scrambled_eggs).

breakfast :-
    prepare(beverage),
    prepare(food).

When we query for breakfast we get:

?- breakfast.
true ;
true ;
true ;
true ;
true ;
true.

It's a little boring not to know what we have for breakfast, but there are six ways to have one. So how did we get there?

We started with breakfast on the todo list:

breakfast

the only rule head that fits is the last one, so we change our TODO to:

prepare(beverage)
prepare(food)

We now have multiple rules that tell us what beverage to make, let's pick the first one:

make(coffee)
prepare(food)

Luckily, make(coffee) is a fact so we can just cross it off our list.

prepare(food)

Similarly we can prepare the food:

make(croissant)

and because there's a corresponding fact we're done making breakfast (output true). But we made some choices: we could have prepared tea or orange juice instead of coffee and we could have made scrambled eggs instead of the croissant. That means we can backtrack:

make(croissant)

ok, there was no choice involved there, let's go back further:

prepare(food)

and expand this to

make(scrambled_eggs).

which is again a fact (true again :) ). When we backtrack even further, we get all combinations of making beverages and food and print true for all 6 of them.

A cut prevents backtracking to a point before it was placed. Let's modify the rule as follows:

breakfast :-
    prepare(beverage),
    !,
    prepare(food).

Now we cannot undo the beverage choice, so we will end up with coffee and scrambled eggs or coffee and a croissant:

?- breakfast.
true ;
true.

So the conjunction tells us which things to derive next and the cut tells us to stop backtracking. In both cases we will need a data structure that records the last sequence of choices we have and which we already made. It must be a sequence because we need to remember both what else we can pick as a beverage and as food. In the case of a cut we can forget everything in the sequence past the last cut, i.e. a the cut cuts off the choice point sequence. As a result we commit to that particular choice.

I hope that helps a little with the implementation.

swi prolog: conjunction and cut

1 Answers