Lessons/Succeed, fail and backtrack - part 2

In Succeed, fail and backtrack - part 1 we described what is means that a predcate succed and fail and what backtracking means. Bu examining a very small program with an extremely little "knowledge base". Here will 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 Sue\n").
    runGoal() :-
        not(grandfather("Bill", "John")),
        stdio::write("No, John is not the grandfather of Bill\n").

Run the project.

When run call runGoal we first create a backtrack point to thesecond 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 substiture 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. Soince 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 is 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 invokethe backtracking mechanism which will bring us to the second clause. The second clause succeeds and we return to the granfather predicate and since this was the last call in that clause the granfather predicate also succeeds.

So we return to runGoal where we will write "Yes, John is the grandfather of Sue\n". And then the first clause of runGoal have succeed 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 consideret corectly, you would recall that we have created three backtrack points in total andalso 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 grandfacther 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 to this place the variable is again free. So backtracking not only tansfer the program control back to an ealier state it also restore 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.

Summary:

• Running "forward" in clauses will bind variables to values.
• When backtracking variables are freed again to the state they we in.
• Backtracking can really jump a lot around in the code
• To really master Visual Prolog you must master backtracking.

Having said the last thing I will also say that I have met a huge number of quite skilled Visual Prolog programmers that doesn't fully master backtracking. The thing is that quite often the exact "jump pattern" is not important what matters is whether things succeed and fail in the intended way. And that is often much easier to get right than to explain exactly how the execution jumps around. However, when debugging a program it will help the better you understand the backtracking mechanism, because in the debug situation the program is running and hence it does jump around in this very detailed way.