Intensive Prolog is a multimedia package
of interactive video, a course text, a workbook, a set
textbook, computer software, and a reference manual.
The video cassette is divided into four
30-minute interactive sessions.
At the start of the first session,
we consider this simple Prolog program and the query,
is Bedford en route to Rome?
Frank Kriwaczek and Malcolm Dixon take up the story.
So here's our initial goal, and here's
what the Prolog interpreter does.
It introduces a procedure status box.
Notice the two clause branches at the bottom of the procedure
box showing there are two on_route clauses.
The clause counter is set at 0.
Showing neither has been tried yet.
The computer must now search its database,
looking for a match for this goal.
What I'm going to do here is handle the database search.
The method used by Prolog to search its database
is as follows--
set the clause counter to 1, go to the database
and take a copy of the first on_route clause,
and bring it over.
Now compare it with the goal.
Does it match?
Well, that's a job for the unification program.
No, it doesn't match.
Rome doesn't match Bedford.
so dead-end the first clause branch and discard the clause.
So now increment the clause counter again.
Go over to the database and take a copy of the second on_route
clause and bring it over.
Now, this on_route clause contains
variables P, A, and NP.
And to avoid possible confusions in taking this copy,
I'll subscript all the variables with 1.
P1, P1, A1, NP1, and NP1.
Now does this match?
Yes, this matches because P1 is a variable
and could be instantiated to Bedford.
So put a clause status box on the second branch.
You can subsequently tick it or cross it
depending on the ultimate outcome of the processing
of this clause branch.
The goal, on_route P1, can only succeed
if the two subgoals in the body succeed.
So the program now starts building itself
a tree reflecting this goal-subgoal relationship.
P1 is instantiated to Bedford.
And this must be done in both places P1 appears.
The subgoals are now processed one at a time.
It starts with move Bedford, A1, and P1,
which becomes the new focus of attention.
So it's in the database search.
Set the clause counter to one, take
a copy of the first move clause, bring it over, and compare it.
No, this doesn't match.
Bedford doesn't match home.
So we'll have to dead-end the first clause branch
and discard the clause.
Increment the counter again, take a copy of the second move
clause.
Yes, this is a match.
A1 can be instantiated to train, and NP1 to Gatwick.
So put a clause status box on the second clause branch.
So a match has been found for move Bedford, A1, and P1
with some instantiations.
A1 is instantiated to train and NP1 is instantiated to Gatwick.
Notice that NP1 occurs twice.
So NP1 must be instantiated to Gatwick in both places.
The left-hand goal now succeeds because move
Bedford, train, Gatwick is a fact.
There are no further subgoals to be derived
on this side of the tree.
So we can tick the clause status box and also
the procedure status box.
But there's a second subgoal to test on the right-hand side
of the tree.
So we now shift our attention to this other subgoal.
And so on, until eventually, the query on_route(Bedford)
succeeds.
In the second video session, we look
at how the route-finding program used earlier
can be expanded to include a How so that a list of actions
used on a route can be output.
Marc Eisenstadt explains the execution of the query.
What we're going to do is to try and illustrate
the way in which the variable How becomes
instantiated in successively greater
detail during each recursive invocation of route.
We've built this bank of TV monitors
to display the workings of a Prolog program.
To begin with, we'll pick up from where Malcolm began.
This was his query, and we've seen a match with clause
to a route.
Remembering that all variables are subscripted,
we've instantiated Place1 and Finish1.
In order to accommodate the ever-lengthening list,
we've had to continue the line on the second screen.
But the intention is to read right across.
Let's look at the first of the two subgoals.
The first one is move from one place
by an action to a new place.
One of these variables was an input variable.
So as it's already instantiated in the head,
Place1 would have immediately been instantiated as Bedford.
Clause 2 of move is the first match
since the move starts at Bedford.
And that match instantiates Act1 to train and NewPlace1
to Gatwick.
Now, in fact, all occurrences of Act1 are instantiated.
This means that within the third argument of the top goal,
Act1, which is in the head of the list,
is instantiated to train.
And we'll see that more MoreActs1 becomes
successively more instantiated at each recursive invocation.
So now Prolog will have to check the second subgoal to start
to find the tail of the list.
That's more Act1.
And this is just what's going to happen.
This time, our search for matching clauses
finds a match in clause 1.
And this is where MoreActs2 is instantiated to the empty list
everywhere it occurs.
So now we know what MoreActs1 is, namely,
the list whose head is plane and whose tail is the empty list.
And this is true everywhere that MoreActs1 occurs.
How is then instantiated to a list
whose head is train and whose tail is
the list we've just seen.
And that is Prolog's output and answer to the query.
In fact, this is beautified to simply train, plane.
So that's demonstrated successive instantiation
in some detail.
Although to the outside world, the appearance
is, of course, just one of two inputs
and one output with the list of actions, train comma plane,
being output.
Video 3 is concerned with harnessing backtracking.
An example using member is used as one illustration.
This is where we can harness backtracking to our advantage.
To generate our solutions, what I do
is make this query part of a larger conjunctive query.
So I have the query, member X, a, b, c, d, e.
Then I have the instruction, write(X).
And now I tell it to fail using the primitive, fail.
So running this program, X is instantiated to a via X1.
Then a is displayed on the screen.
And then a failure occurs.
So the program is forced to backtrack,
looking for alternative ways of making
this conjunction succeed.
Write is one of those primitives which cannot be redone
on backtracking.
So member must be retried.
So this clause branch will be failed,
and now a match will be looked for using the second member
clause.
But to see this in action, we really
need to look at the sequence of AORTA diagrams
from start to finish.
This composite query splits into a tree
with three linked branches.
Looking at the first goal, member X, a, b, c, d e,
this matches on the first member clause
with X instantiated to a.
Now the program writes out this value for X.
And now the program encounters the fail primitive.
For the top status box to succeed,
all three below must succeed.
But fail can never succeed, So the program now
starts backtracking.
Write cannot be redone, so it fails,
and we backtrack further.
In fact, we backtrack to this clause status box,
where we last had a successful match.
This clause fails, and we reset the procedure goal to a query.
So, carrying on, the interpreter increments the clause counter
and brings over the second member clause.
This causes the tree to build up.
Now Xs2 is instantiated to the list, b, c, d, e.
The interpreter now processes the lower procedure box.
It brings over the first member clause.
It matches with X2 and X3 instantiated to b.
So ticks work their way up the tree.
Now the program writes out b and then fails, so backtrack.
Back the program goes to the last successful match.
What you have seen are just small sections
of the video in the multimedia course on Intensive Prolog.
The whole pack includes two hours
of interactive video, a course text, a workbook, a set
textbook, computer software, and a reference manual.