## 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.

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)