- Building Blocks
- SWI-Prolog
- More Induction
- Debugging Prolog
- A Longer Example
- Why Bother with Prolog?
Like this article? We recommend
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