# Prolog: Logic Programming for Rapid Development

• Print

## Debugging Prolog

Few people write code that works perfectly the first try. For the rest of us, there are debugging tools. Consider the following simple program, even.pro, from the source for this article:

```isEven(2).
isEven(X) :- Y is X - 2, isEven(Y).```

This program contains an inductive definition of evenness: A number is even if it’s 2, or if it’s constructed by adding 2 to another even number. Let’s see what happens when we try using this definition:

```?- isEven(2).

Yes
?- isEven(4).

Yes```

To get a clearer idea of what Prolog is doing, we can trace the execution of a query:

```trace,isEven(4).
Call: (8) isEven(4) ? creep
^ Call: (9) _L351 is 4-2 ? creep
^ Exit: (9) 2 is 4-2 ? creep
Call: (9) isEven(2) ? creep
Exit: (9) isEven(2) ? creep
Exit: (8) isEven(4) ? creep

Yes```

Each line that begins with Call is an attempt by Prolog to solve a predicate. Lines beginning with Exit indicate success. Now try a query that should evaluate to false:

`?- isEven(5).`

That wasn’t quite what we wanted. Don’t bother waiting for it to finish; it will keep going for a very long time (until you run out of stack space, in fact). The reason can be seen by tracing the query:

```?- trace,isEven(5).
Call: (9) isEven(5) ? creep
^ Call: (10) _L351 is 5-2 ? creep
^ Exit: (10) 3 is 5-2 ? creep
Call: (10) isEven(3) ? creep
^ Call: (11) _L368 is 3-2 ? creep
^ Exit: (11) 1 is 3-2 ? creep
Call: (11) isEven(1) ? creep
^ Call: (12) _L385 is 1-2 ? creep
^ Exit: (12) -1 is 1-2 ? creep
Call: (12) isEven(-1) ? creep
...```

Our inductive definition is purely constructive; we don’t specify a failure case. For natural numbers, we can define a base case of 1, which fails. Our program now looks like this:

```isEven(1) :- fail.
isEven(2).
isEven(X) :- Y is X - 2, isEven(Y).```

Retrying the same query will have the same result; it will keep going until you run out of stack space. Tracing it, you might notice this segment:

```...
Call: (10) isEven(1) ? creep
Call: (11) fail ? creep
Fail: (11) fail ? creep
Redo: (10) isEven(1) ? creep
^ Call: (11) _L368 is 1-2 ? creep
^ Exit: (11) -1 is 1-2 ? creep
Call: (11) isEven(-1) ? creep
...```

This is caused by the backtracking feature of Prolog. When it encounters a failure condition, it backtracks and tries to find a different predicate that works. The first attempt, isEven(1), fails. The line that starts with Redo shows that Prolog is trying this again, a different way. It uses the last definition of the predicate, and tries recursing again.

To avoid this recursion, we need to use a feature of Prolog called the cut. Once Prolog encounters a cut, it won’t backtrack past that cut. The final version of our program, even3.pro, looks like this:

```isEven(1) :- !,fail.
isEven(2).
isEven(X) :- Y is X - 2, isEven(Y).```

The first line contains a cut, the exclamation point (!). Testing it, we see that it now works as expected:

```?- isEven(5).

No```

To see what’s going on under the hood, we can try tracing it again:

```?- trace,isEven(3).
Call: (8) isEven(3) ? creep
^ Call: (9) _L351 is 3-2 ? creep
^ Exit: (9) 1 is 3-2 ? creep
Call: (9) isEven(1) ? creep
Call: (10) fail ? creep
Fail: (10) fail ? creep
Fail: (9) isEven(1) ? creep
Fail: (8) isEven(3) ? creep```