View source for Lessons/Succeed, fail and backtrack - part 2

From wiki.visual-prolog.com

← Lessons/Succeed, fail and backtrack - part 2

You do not have permission to edit this page, for the following reasons:

The action you have requested is limited to users in the group: emailconfirmed.
You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page.

In {{Lesson|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:

{{Lessons/Exercise|And an extra <vp>father</vp> clause:

<vip>
clauses
	father("Bill", "John").
	father("Pam", "Bill").
</vip>

And add a <vp>grandfather</vp> predicate:

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

Build the project.}}

In consistence wih my <vp>father</vp> predicate, it is the second argument of the <vp>grandfather</vp> predicate that is the grandfather.  In the clause I have chosen to use <vp>Person</vp>, <vp>Father</vp> and <vp>Grandfather</vp> as variable names instead of <vp>A</vp>, <vp>B</vp> and <vp>C</vp>, 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 <vp>father</vp> predicate:

{{Lessons/Exercise|Update the <vp>runGoal</vp> clauses like this:

<vip>
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").
</vip>

Run the project.}}

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

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

<vip>
grandfather("Pam", "John") :- father(Father, "John"), father("Pam", Father).
</vip>

In this clause we will first call the <vp>father</vp> 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 <vp>father</vp> 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 <vp>"Bill"</vp>.  The second argument is "John" and that also matches "John" clause.  So the first clause succeeds and we return to the <vp>grandfather</vp> clause where the <vp>Father</vp> variable is now bound to <vp>"Bill"</vp>.  If we substitute <vp>"Bill"</vp> for the <vp>Father</vp> variable the clause now looks like this:

<vip>
grandfather("Pam", "John") :- father("Bill", "John"), father("Pam", "Bill").
</vip>

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

In the <vp>father</vp> 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 <vp>"Pam"</vp> but the first argument in the clause is <vp>"Bill"</vp>.  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 <vp>grandfather</vp> predicate and since this was the last call in that clause the grandfather predicate also succeeds. 

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

{{Lessons/Exercise|Recall that the <vp>run</vp> 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 <vp>runGoal</vp>, the second backtrack point we created was to the second clause of the <vp>father</vp> predicate which we had called from the first call in the <vp>grandfather</vp> predicate which we had called in the first clause in the <vp>runGoal</vp> 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 <vp>father</vp> 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 <vp>father("Pam", "Bill").</vp> of the <vp>father</vp> predicate with the first argument being free and the second argument being <vp>"John"</vp>.  When we execute this clause we can bind the free first argument, but the <vp>"John"</vp> does not match <vp>"Bill"</vp>, so this clause fails.

Once more we backtrack this time to the second clause of <vp>runGoal</vp>.

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

[[Category:Lessons|{{SUBPAGENAME}}]]

Templates used on this page:

Return to Lessons/Succeed, fail and backtrack - part 2.

Retrieved from "https://wiki.visual-prolog.com/index.php?title=Lessons/Succeed,_fail_and_backtrack_-_part_2"

View source for Lessons/Succeed, fail and backtrack - part 2

Search

Navigation

external links

collaboration

Personal tools

Views