Lessons/Succeed, fail and backtrack - part 1

So why is it a logical programming language? And why do we call it predicates and clauses?

Logic is a formalized approach to

• propositions like "John is the father of Bill"
• rules like "C is the grandfather of A if C is the father of B and B is the father of A"
• questions like "Who is the father of John"

Visual Prolog can formalize logical entities. The Visual Prolog compiler has a number of strict validation checks that will help you write the programs you intend. But to keep things simple we will "work around" those checks in this lesson. To do that work around you should update enter the following code in the console project:

Exercise In a console project update the run clause and add a runGoal predicate, like this:

clauses
    run() :-
        foreach runGoal() do
        end foreach.
 
class predicates
    runGoal : () nondeterm.
clauses
    runGoal().

Build the project.

Compared to what we have see so far you will notice the token nondeterm in the declaration of run2 and you will also get a warning about 'nondeterm'. We have inserted nondeterm to get around some compiler errors that we would later get, and instead we now get some warnings. For now we will just ignore these warnings and in the sequel of this lesson you should just accept to write nondeterm and also anyflow where told.

Back to the main subject. Let us start with the proposition "John is the father of Bill".

Here we have two "things": John and Bill, and a "relation" between these, namely that one is the father of the other. In Visual Prolog I can formalize this proposition in the following way:

father("Bill", "John").

father is a predicate/relation taking two arguments, where the second is the father of the first.

Notice that I have chosen that the second person should be the father of the first. I might as well have chosen it the other way around: The order of the arguments is the choice of the "designer" of the formalization. However, once you have chosen, you must be consistent. So in my formalization the father must always be the second person.

Exercise Add this code to the project:

class predicates
    father : (string Person, string Father) nondeterm anyflow.
clauses
    father("Bill", "John").

Build the project.

Now that we have a (tiny) "knowledge base", we will try to find the answer to some questions. Let's first see the "magic":

Exercise Update the runGoal clause like this:

clauses
	runGoal() :-
		father("Bill", "John"),
		stdio::write("Yes, John is the father of Bill").

Run the project.

Then add one more clause like this:

clauses
	runGoal() :-
		father("Bill", "John"),
		stdio::write("Yes, John is the father of Bill").
 
	runGoal() :-
		father("Sue", "John"),
		stdio::write("Yes, John is the father of Sue").

And run the project again.

Finally, modify add one more clauses like this:

clauses
	runGoal() :-
		father("Bill", "John"),
		stdio::write("Yes, John is the father of Bill").
 
	runGoal() :-
		father("Sue", "John"),
		stdio::write("Yes, John is the father of Sue").
 
	runGoal() :-
		not(father("Sue", "John")),
		stdio::write("No, John is the not the father of Sue").

And run the project again.

To understand what is going on we need to understand the concept of succeed and fail. When we call father("Bill", "John") the call will succeed, because there is a clause that matches this call. When we call father("Sue", "John") the call will fail, because the clauses for the father predicate cannot match this call. The call not(father("Sue", "John")) will succeed because not is special predicate that succeeds if its argument fails and fails if the argument succeeds.

Using the words succeed and fail' we can now explain the clauses.

Let us first consider each of the three clauses individually (as if they were the only one)

The first clause runGoal() :- father("Bill", "John"), stdio::write("Yes, ..."). works like this: runGoal() succeeds if father("Bill", "John") and stdio::write("Yes, ...") succeeds, otherwise it fails.

So when we call runGoal() we will first run father("Bill", "John") and if that succeeds (which we know it will) we will call stdio::write("Yes, ...").

The predicate stdio::write is a predicate that succeeds no matter which arguments it is called with and in addition it will also write the arguments to the standard output stream.

So all in all, the first clause will succeed and also write "Yes, ..." to the standard output stream.

In the second clause we will first run father("Sue", "John") and since that call fails, the entire clause fails, and therefore we will not call stdio::write in this clause.

In the third clause we first call not(father("Sue", "John")). As mentioned above this call succeeds and therefore we will also call stdio::write in this clause.

Now that we know how each clause works individually, lets look at the effect of having them all three. This is actually the most unique feature of logical programming languages, but probably also the most tricky one to understand. The idea is based on the logical "or": to runGoal() will succeed if the first clause "or" the second clause "or" the third clause succeeds. It is true, but it is not sufficiently detailed when actually programming in Visual Prolog. Here I will provide a much more detailed and operative description of how it works.

When we invoke runGoal(), which has three clauses. We will first create a backtrack point to the two other clauses, and then excecute the first clause.

A backtrack point is a "thing" that describes a place in our program where we had two alternative ways to fulfill our goal. We do one thing but make a note about the other possibility. If we at some point fail, we backtrack to the place we noted in the most recent backtrack point we created and follow the alternative way we noted in the backtrack point. (That backtrack point is then used and thus discarded).

So with all three runGoal() clauses we will first create a backtrack point to the two last clauses and then execute the first clause. As discussed above the first clause will succeed, so we will return from runGoal() to the place in run() where runGoal() was called from, but we have also created a backtrack point to the two last clauses of runGoal().

The code we wrote in the run clause will (without going into the datails) has the effect that we backtrack according to our backtrack point, so after returning from runGoal the first time we will backtrack to the last two runGoal clauses.

When we backtrack to the last two clauses there is a choice between the second and the third clause, so again a backtrack point is created, this time to the third clause, and then the second clause is executed.

As mentioned before the second clause will fail in the not(father("Sue", "John")) call, when this happens we will again backtrack to where the latest backtrack point says, i.e. to the third runGoal clause. The third clause is the last clause so here we don't have a choice point and therefore we do not have any more backtrack points left.

The third clause will execute as described above and runGoal will return to then run() clause, and with no more backtrack points run() will finish and eventually the entire program will finish.

Notice that we backtracked two times in this program:

• The first time we backtracked back into a predicate that had already returned one time, and therefore a single call to runGoal returned twice to run
• The second backtrack was from the nested call to father in the second runGoal clause to the third runGoal clause.

Summary

• Calls can succeed or fail.
• Whenever there is a choice point a backtrack point is created to the second choice and the first choice is pursued.
• When a predicate fails program control is backtracked to the latest backtrack point.
• Backtrack may "jump" out from nested calls
• Backtracking may also "jump" back into already succeeded calls
• So as a result of backtracking a certain predicate call may succeed/return several times.