3.4 Practical Session 3

By now, you should feel more at home with writing and runnning basic Prolog programs. The purpose of Practical Session 3 is twofold. First we suggest a series of keyboard exercises, involving trace, which will help you get familiar with recursive definitions in Prolog. We then give a number of programming problems for you to solve.

First the keyboard exercises. As recursive programming is so fundamental to Prolog, it is important that you have a firm grasp of what it involves. In particular, it is important that you understand the process of variable instantiation when recursive definitions are used, and that you understand why both the order of the clauses in a recursive definition, and the order of goals in rules, can make the difference between a knowledge base that is useful and one that does not work at all. So:

1. Load descend1.pl, turn on trace, and pose the query descend(martha,laura). This is the query that was discussed in the notes. Step through the trace, and relate what you see on the screen to the discussion in the text.

2. Still with trace on, pose the query descend(martha,rose) and count how many steps it takes Prolog to work out the answer (that is, how many times do you have to hit the return key). Now turn trace off and pose the query descend(X,Y). How many answers are there?

3. Load descend2.pl. This, remember, is the variant of descend1.pl in which the order of both clauses is switched, and in addition, the order of the two goals in the recursive goals is switched too. Because of this, even for such simple queries as descend(martha,laura), Prolog will not terminate. Step through an example, using trace, to confirm this.

4. But wait! There are two more variants of descend1.pl that we have not considered. For a start, we could have written the recursive clause as follows:

   descend(X,Y) :- child(X,Y).          
 
descend(X,Y) :- descend(Z,Y),
                child(X,Z).

   Let us call this variant descend3.pl. And one further possibility remains: we could have written the recursive definition as follows:

   descend(X,Y) :- child(X,Z),
                descend(Z,Y).
 
descend(X,Y) :- child(X,Y).         

   Let us call this variant descend4.pl.

   Create (or download from the internet) the files descend3.pl and descend4.pl. How do they compare to descend1.pl and descend2.pl? Can they handle the query descend(martha,rose)? Can they handle queries involving variables? How many steps do they need to find an answer? Are they slower or faster than descend1.pl?

   Draw the search trees for descend2.pl, descend3.pl and descend4.pl (the one for descend1.pl was given in the text) and compare them. Make sure you understand why the programs behave the way they do.

5. Finally, load the file numeral1.pl. Turn on trace, and make sure that you understand how Prolog handles both specific queries (such as numeral(succ(succ(0)))) and queries involving variables (such as numeral(X)).

Now for some programming. We are now at the end of the third session, which means we have covered about a quarter of the material we are going to. Moreover, the material we have covered so far is the basis for everything that follows, so it is vital that you understand it properly. And the only way to really get to grips with Prolog is to write programs (lots of them!), run them, fix them when they don't work, and then write some more. Learning a programming language is a lot like learning a foreign language: you have to get out there and actually use it if you want to make genuine progress.

So here are some exercises for you to try your hand on.

1. Imagine that the following knowledge base describes a maze. The facts determine which points are connected, i.e., from which point you can get to which other point in one step. Furthermore, imagine that all paths are one-way streets, so that you can only walk them in one direction. So, you can get from point 1 to point 2, but not the other way round.

   connected(1,2).
connected(3,4).
connected(5,6).
connected(7,8).
connected(9,10).
connected(12,13).
connected(13,14).
connected(15,16).
connected(17,18).
connected(19,20).
connected(4,1).
connected(6,3).
connected(4,7).
connected(6,11).
connected(14,9).
connected(11,15).
connected(16,12).
connected(14,17).
connected(16,19).

   Write a predicate path/2 that tells you from which point in the maze you can get to which other point when chaining together connections given in the above knowledge base. Can you get from point 5 to point 10? Which other point can you get to when starting in point 1? And which points can be reached from point 13?

2. We are given the following knowledge base of travel information:

   byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
 
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
 
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(losAngeles,auckland).

   Write a predicate travel/2 which determines whether it is possible to travel from one place to another by `chaining together' car, train, and plane journeys. For example, your program should answer `yes' to the query travel(valmont,raglan).

3. So, by using travel/2 to query the above database, you can find out that it is possible to go from Vamont to Raglan. In case you are planning a travel, that's already very good information, but what you would then really want to know is how exactly to get from Valmont to Raglan. Write a predicate travel/3 which tells you how to travel from one place to another. The program should, e.g., answer `yes' to the query travel(valmont,paris,go(valmont,metz,go(metz,paris))) and X = go(valmont,metz,go(metz,paris,go(paris,losAngeles))) to the query travel(valmont,losAngeles,X).

4. Extend the predicate travel/3 so that it not only tells you via which other cities you have to go to get from one place to another, but also how, i.e. by car, train, or plane, you get from one city to the next.