Because proofs are boring. That is a given!

Controlling PROLOG

In my last post I introduced the concept of backtracking and as promised, this time I will be writing about cut, fail and repeat.

Cut

There are two main reasons to understand and use the cut feature:

  • performance: the program will be faster, because PROLOG will not try to satisfy clauses or facts that the programmer knows they are not going to be satisfiable.
  • resources: the program needs less memory, as the backtracking branching points before the cut don’t need to be stored.

Cut types:

There are two types of cut:

  • GREEN cut: this is normally used just for better performance, the cases are removed and the found solutions / instances can not be changed.
  • RED cut: the program doesn’t have the same solutions but it will have an anomalous behaviour.

Using cut

It is important to know that cut is not a logic predicate. It is in fact just a tool to interfere in the semantics of the program procedure. The cut “cuts” some of the ramifications from the search tree. This way, the predicates before the cut are going to be instantiated just once. Example:

x :- p, !, q.
x :- r.

This would be a simple way to write if p then q else r for those more familiar with imperative languages.

Fail

Prolog has two pre-defined predicates true and fail, where true always succeed and fail always fails. Easy, right? ;)

Consider that one has the following problem to model: ‘Susan likes all fruits but apples’. To do it in PROLOG, we can ‘break’ it in smaller pieces of information. Let’s start with the easiest part and write ‘Susan likes all fruits’, in PROLOG:

like(susan,X) :- fruit(X).

So now, we need to exclude the apples. For that, we first check if X is apple. If it is true, then we fail the ‘Susan likes X’ rule. In PROLOG:

like(susan,X) :- apple(X), fail.
like(susan,X) :- fruit(X).

Using cut with fail together is possible to implement negation, as one can see in the example below:

not X :- X, !, fail.
not X.

so not X fails if X has no solution, that means, if X is true.

And also makes our first example faster, eliminating the backtracking when something is never true. Try:

like(susan,X) :- apple(X), !, fail.
like(susan,X) :- fruit(X).

Repeat

It is also pretty straight forward: it repeats the rule until the next rule is true or valid. For example:

checkchar(X) :- repeat, get0(X).
getchar(X) :- checkchar(X), X > 32, !.

checkchar will be repeated until it gets a printable input.

Be aware that cut has side effects and the use of it can lead to not desirable results. Double check the order of your rules and if you are not sure, try to solve your problem with lists and recursion. It also helps to draw the search tree sometimes! =)

The next post will be a bit more theoretical and technical again, so that we can get our hands really dirty afterwards!