Lessons/Succeed, fail and backtrack - part 2

In Succeed, fail and backtrack - part 1 we described what it means that a predicate succeeds and fails and what backtracking means. By examining a very small program with an extremely little "knowledge base". Here we'll discuss how we can add more abstract rules to such a knowledge base.

In particular we will look at the mentioned grandfather rule:

• "C is the grandfather of A if C is the father of B and B is the father of A"

The rule as it is written here is actually more or less a Visual Prolog clause:

Exercise And an extra father clause:

clauses
	father("Bill", "John").
	father("Pam", "Bill").

And add a grandfather predicate:

class predicates
    grandfather : (string Person, string Grandfather) nondeterm anyflow.
clauses
    grandfather(Person, Grandfather) :-
        father(Father, Grandfather),
        father(Person, Father).

Build the project.

In consistence wih my father predicate, it is the second argument of the grandfather predicate that is the grandfather. In the clause I have chosen to use Person, Father and Grandfather as variable names instead of A, B and C, but otherwise the rule is a "direct" translation of the textual version.

Let us test the new predicate in a way similar to how we tested the father predicate:

Exercise Update the runGoal clauses like this:

clauses
    runGoal() :-
        grandfather("Pam", "John"),
        stdio::write("Yes, John is the grandfather of Pam\n").
    runGoal() :-
        not(grandfather("Bill", "John")),
        stdio::write("No, John is not the grandfather of Bill\n").

Run the project.

When run calls runGoal we first create a backtrack point to the second runGoal clause and then execute the first clause.

In the first runGoal clause we call grandfather("Pam", "John"), so when we enter the grandfather clause Person is "Pam" and Grandfather is "John". We will say that Person is bound to "Pam" and Grandfather is bound to "John" and Father is unbound or free. If we substitute known values for the variables the clause looks like this:

grandfather("Pam", "John") :- father(Father, "John"), father("Pam", Father).

In this clause we will first call the father predicate with a free first argument and a bound second argument. So the data flow in that call is that the first argument is an output argument and the second argument is an input argument.

When we enter the father predicate we have two clauses, so the first thing that happens is that we create a backtrack point to the second clause and then execute the first clause. Since our first argument is free it can match "Bill" in the clause, i.e. if we bind it to "Bill". The second argument is "John" and that also matches "John" clause. So the first clause succeeds and we return to the grandfather clause where the Father variable is now bound to "Bill". If we substitute "Bill" for the Father variable the clause now looks like this:

grandfather("Pam", "John") :- father("Bill", "John"), father("Pam", "Bill").

So now we have to call father("Pam", "Bill"), which means that this time we call the father predicate with two input arguments.

In the father predicate we again first create a backtrack point to the second clause, and then execute the first clause. The first clause fails because the first argument in our call is "Pam" but the first argument in the clause is "Bill". There is no need to consider the second arguments, we just immediately invoke the backtracking mechanism which will bring us to the second clause. The second clause succeeds and we return to the grandfather predicate and since this was the last call in that clause the grandfather predicate also succeeds.

So we return to runGoal where we will write "Yes, John is the grandfather of Pam\n". And then the first clause of runGoal succeeds and we will return to the run predicate.

Exercise Recall that the run predicate will make sure that all backtracking takes place, so carefully consider what happens next. Do we have any backtrack points? If so where do we backtrack to?

Well if you considered correctly, you would recall that we have created three backtrack points in total and also used one of them, so we have two backtrack points left.

The first we created was to the second clause in runGoal, the second backtrack point we created was to the second clause of the father predicate which we had called from the first call in the grandfather predicate which we had called in the first clause in the runGoal predicate. Both these backtrack points still exists, and the one we created in the father predicate was the last one we created so this it the one we will backtrack to.

So at this point we will backtrack to place that is nested rather deeply in something that we have already returned from once.

Furthermore at that backtrack point in the father predicate the first argument was free, when we executed the first clause in that predicate the variable became bound, but when we backtrack to this place the variable is again free. So backtracking not only transfers the program control back to an earlier state, it also restores variables to the free/bound state they were in at that point. Notice that such restore of variables can only make variables free again, bound variables never receive new values, so bound variables already have the correct state.

So we are back at the second clause father("Pam", "Bill"). of the father predicate with the first argument being free and the second argument being "John". When we execute this clause we can bind the free first argument, but the "John" does not match "Bill", so this clause fails.

Once more we backtrack this time to the second clause of runGoal.

So backtracking can jump quite a lot around in your program.