Home > Articles > Programming > General Programming/Other Languages

  • Print
  • + Share This
Like this article? We recommend

Like this article? We recommend

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
  • + Share This
  • 🔖 Save To Your Account