<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Prolog Intro Exercise Notebook ## by Brandon and Giulia This Prolog notebook contans exercises illustrating the basic structure and use of Prolog. To do the exercises you should make your own copy of the Notebook. You can do this as follows: * Log in to SWISH using either Google or Stackoverflow by clicking one of the buttons at the top right of the SWISH window. * Click the "File" menu at the top of this window and select "Save". * Press the green "Fork" button. * Type a new name in the name text box. (This should be unique but memorable. A good idea is to add your university username to the filename.) * Press "Fork Notebook" (or "Fork Program" for normal program files). You can now save your own versions of this file. When you vist SWISH again remember to log back in (using one of the Google or Stackoverflow login buttons). You will probably find that your files are accessible via tabs at the top of the seft hand of the SWISH window. Also, if you select a new tab (by pressing the "+" at the end of the tabs) you can then press the magnifying glass to search for files. If you use the default `user:"me"` search you should get a list of all your own files. To be honest the SWISH file system is a bit strange and confusing. An easy way to find your files is just to add a bookmark in your browser to the URL of the page that shows your file. If you do this remember to then log into SWISH so you can save your further edits. </div> <div class="nb-cell markdown" name="md4"> ## (1) A Typical Prolog Database In the most typical use of prolog, it works like a logical database consisting of facts and rules. This information is used by Prolog to answer queries. In the following example the basic facts concern people described by some very simple properties and relationships. Specifically, the facts are specified using the unary predicates `male/ 1` and `female/ 1` and a binary predicate `parent_of/ 2`. (Here we use the convention of writing `pred/n` to refer to a predicate called `pred` that has `n` argument places.) These predicates can be applied to named people, as you see below. Note that, `parent_of(x,y)` is supposed to mean that '`x` _is the parent of_ `y`', not the other way round. Given these basic properties and relationships, we can specify rules that define new properties and relationships. Take a look at the rules for `grandfather_of` and `sibling_of`, given below; and try to understand how they work. </div> <div class="nb-cell program" name="p1"> %% Facts %% male and female properties % male( john ). male( sirus ). male( sam). female( jill ). female( mary ). %% parent_of(X,Y) relation meaning X is a parent of Y. parent_of( sirus, john ). parent_of( john, mary ). parent_of( mary, tom ). parent_of( mary, sue ). parent_of( john, sam ). parent_of( sam, jill ). %% X is the grandfather of Y grandfather_of( X, Y ) :- male( X ), parent_of( X, Z ), parent_of( Z, Y ). % X is a sibling (brother or sister) of Y sibling_of( X, Y ) :- parent_of( Z, X ), parent_of( Z, Y ), \+( X = Y). % X and Y do not have the samme value. % EXAMPLE QUERTY % This special comment adds queries to the examples menu under the SWISH % query window. This makes it easy to save queries to run later. /** <examples> ?- parent_of(mary, X). ?- parent_of(X, Y). ?- grandfather_of(X, sue). ?- grandfather_of(X, Y). */ </div> <div class="nb-cell markdown" name="md12"> ## Tasks to try on the Family database (a) Experiment with the following queries: </div> <div class="nb-cell query" name="q18"> parent_of(mary, X). </div> <div class="nb-cell query" name="q19"> parent_of(X, Y). </div> <div class="nb-cell query" name="q20"> grandfather_of(X, sue). </div> <div class="nb-cell query" name="q21"> grandfather_of(X, Y). </div> <div class="nb-cell markdown" name="md3"> **Note:** You will see that the queries above can also be selected using a menu that can be accessed using the "Examples" button at the bottom left of the query pane. This menu is created automatically by a declaration in the selected code cell (see end of the above code cell). The "Add current query to examples" option in the Examples menu only works for plain Prolog files, not Notebooks; but it is easy to add a query directly to the Examples declaration of a cell. And in notebooks it is not really necessary to save queries in this way since you can add "query cells" to the notebook. (b) Try entering some more facts into the family.pl file. Add some more relationships involving additional people. As well as using the relation types already defined, add some married relations, and any other relations you fancy. After adding these facts, load your file again and try redoing some of the queries from the previous step, to see what you get. c) Now you are ready to define some more rules for deriving further relationships from the information. Define rules defining each of the following. (Be sure to add these one at a time; and check they work correctly by entering suitable queries to test them.): 1. `mother_of/ 2` 2. `brother_of/ 2` 3. `uncle_of/ 2` 4. `cousin_of/ 2` </div> <div class="nb-cell markdown" name="md2"> ## (2) Matching and Manipulating Lists One of Prolog’s fundamental data structures is the list. A list is a series of data entities, which is represented by a comma-separated sequence enclosed in square brackets. The elements of a list may themselves be complex data structures, but in this exercise we shall confine our attention to cases where the elements are what in Prolog terminology are called atoms. These are simply lower case words. In this part of the exercise we look at some useful list matching predicates that are commonly used in Prolog. Experiment by entering the following queries and noting what output you get. You can also edit the queries or create new ones of your own to explore different ways of using them. </div> <div class="nb-cell query" name="q10"> member( b, [a, b, c, d] ). </div> <div class="nb-cell query" name="q9"> member( X, [a, b, c, d] ). </div> <div class="nb-cell query" name="q11"> member( X, [a, b, c, d] ), member(X, [c, d, e, f]). </div> <div class="nb-cell markdown" name="md10"> The append function can be used to join two lists to form a new list that concatenates the given lists. However it can also be used in other ways. </div> <div class="nb-cell query" name="q12"> append( [a,b,c], [d,e,f], X ). </div> <div class="nb-cell query" name="q13"> append( X, Y, [a,b,c,d,e] ). </div> <div class="nb-cell markdown" name="md9"> To match elements of a list in terms of their position you can use `nth1`. (Why is it called `nth1` instead of just `nth`?) </div> <div class="nb-cell query" name="q2"> nth1( 2, [one, two, three, four], Numname ). </div> <div class="nb-cell query" name="q3"> nth1( N, [one, two, three, four], Numname ). </div> <div class="nb-cell query" name="q6"> nth1( N, List, X ). </div> <div class="nb-cell query" name="q7"> last([this, that, and, the, other], Last). </div> <div class="nb-cell query" name="q8"> last( List, end ). </div> <div class="nb-cell markdown" name="md17"> </div> <div class="nb-cell query" name="q4"> length( [x, y, z], Len ). </div> <div class="nb-cell query" name="q22"> length( List, 5 ). </div> <div class="nb-cell query" name="q5"> length( List, Len). </div> <div class="nb-cell query" name="q27"> select/3 is a predicate I </div> <div class="nb-cell markdown" name="md18"> select/3 is a predicate that has many uses in creating rearrangements of list structures. </div> <div class="nb-cell query" name="q14"> select( X, [a,b,c,d,e], Remainder ). </div> <div class="nb-cell markdown" name="md13"> Making use of the select/3 relation, define a predicate get_two/3, such that `get_two(List, X, Y)` will be true when X and Y are any two members of List. This should be defined so that X and Y can only take the same value if List contains two or more occurrences of the same atom. Test this predicate by trying a few queries using get_two/3. What will happen if List only contains one atom? </div> <div class="nb-cell program" name="p5"> % this wont do much. Try to define get_two in accorance with the requirements given above. get_two( _, _, _) :- true. </div> <div class="nb-cell query" name="q28"> get_two( X, Y, [a,b,c,c]). </div> <div class="nb-cell query" name="q30"> get_two( X, X, [a,b,c,c]). </div> <div class="nb-cell query" name="q29"> get_two( X, X, [a]). </div> <div class="nb-cell markdown" name="md11"> The `permutation/2` predicate can be used either to test whether two list are permutations of each other or to generate permutations of a given list. And can be put to other purposes as well. </div> <div class="nb-cell query" name="q17"> permutation( [this, and, that], [that, and, this]). </div> <div class="nb-cell query" name="q15"> permutation( [this, and, that], P ). </div> <div class="nb-cell query" name="q16"> permutation( P, [and, the, other] ). </div> <div class="nb-cell markdown" name="md6"> Now let us look at how these list manipulation predicates can be combined to define more complex relationships involving lists. The predicate mixup/4 defined bellow can match lists L1, L2, M1, M2, where the elements of L1 and L2 are mixed up and shared between M1 and M2 and also the list L1 and L2 have the same lengths as M1 and M2 respectively. </div> <div class="nb-cell program" name="p4"> mixup( L1, L2, M1, M2 ) :- length(L1, Len1), length(M1, Len1), append( L1, L2, Join), append( M1, M2, Perm ), permutation( Join, Perm ). allmixes( L1, L2, Mixes ):- setof( [M1,M2], mixup(L1, L2, M1, M2), Mixes ). </div> <div class="nb-cell query" name="q1"> mixup( [a,b,c], [x,y], M1, M2). </div> <div class="nb-cell query" name="q31"> allmixes([angel, ghost, bird, dragon], [knife, fork, spoon], Mixes ). </div> <div class="nb-cell markdown" name="md7"> # Heads and Tails Often we want to split a list up so that we separate its first element (its head ) from all the remaining elements (its tail ). This is done using the special matching construct [H | T], where the variable H will match the head of a list and T will match its tail. For example, try the following query: </div> <div class="nb-cell query" name="q23"> [H | T] = [head, followed, by, the, tail]. </div> <div class="nb-cell markdown" name="md14"> More, generally we can use a similar construct to match several elements at the be- ginning of a list and also any remaining elements. For example, try: </div> <div class="nb-cell query" name="q24"> [H1, H2, H3 | T] = [one, two, three, and, all, the, rest]. </div> <div class="nb-cell markdown" name="md15"> As well as being used to divide up a list, the [H | T] syntax can be used to add a new head to a list. To see this, enter the following query and look at the value that gets assigned to NewList: ?- List = [one,two,three], NewList = [zero | List]. Notice that in Prolog ‘=’ is a matching relation, not an assignment, so we get exactly the same effect by entering the query: ?- [one,two,three] = List, [zero | List] = NewList. </div> <div class="nb-cell query" name="q25"> List = [one,two,three], NewList = [zero | List]. </div> <div class="nb-cell markdown" name="md16"> Notice that in Prolog ‘=’ is a matching relation, not an assignment, so we get exactly the same result from the following query: </div> <div class="nb-cell query" name="q26"> [one,two,three] = List, [zero | List] = NewList. </div> <div class="nb-cell markdown" name="md8"> # THE REST IS STILL UNDER CONSTRUCTION </div> <div class="nb-cell markdown" name="md5"> # `bb_planner` </div> <div class="nb-cell program" name="p2"> :- include(bb_planner). coins( [3*10, 5*5, 2*2, 3*1] ). to_pay(37). initial_state( [Coins, Given, ToPay] ) :- coins(Coins), setof( 0*V, N^member(N*V, Coins), Given ), to_pay(ToPay). goal_state( [_,_,0] ). transition( [Coins, Given, ToPay], [CoinsLeft, NowGiven, MoreToPay] ) :- append( Coins1, [ N*V | Coins2] , Coins), N > 0, V =< ToPay, Nminus1 is N-1, append( Coins1, [Nminus1*V | Coins2], CoinsLeft ), append( Given1, [ M*V | Given2], Given ), Mplus1 is M + 1, append( Given1, [Mplus1*V | Given2], NowGiven ), MoreToPay is ToPay - V. loopcheck(off). legal_state(_). equivalent_states(X,X). </div> <div class="nb-cell query" name="q35"> find_solution. </div> <div class="nb-cell markdown" name="md19"> # Missionaries and Cannibals River Crossing Puzzle _Planning_ is a sub-field of the **Knowledge Representation and Reasoning** research area. It is concerned with finding sequences of actions which could be employed to achieve some goal. To illustrate this we consider an old puzzle known as the __Missionaries and Cannibals__ problem. The scenario runs as follows: * There is group of three missionaries and three cannibals, who are attempting to cross a river (under the guidance of the missionaries). * They all start on one bank and have a canoe that can carry any two people across. * The aim is, by a series of crossings, to get all six people to the other side. * The catch is that if there are ever more cannibals than missionaries on either side of the river, the cannibals will eat the hapless missionaries. (All missionaries are hapless when outnumbered by cannibals). To get a good idea of the problem and its complexity, you can play with a simulation at the following web page: * https://www.game.st/game_276_missionaries_and_cannibals.html </div> <div class="nb-cell markdown" name="md20"> The idea of this part of the exercise is to write a program which will automatically find a solution to this problem --- i.e.\ a sequence of states which take us from the initial state to the goal, with every transition being a legitimate boat crossing (and no uncivilised meal times occurring en route). This is a complex problem, requiring a sophisticated solution. However, I will give you most of the code ready written, and you only have to add some details. This may still be challenging, but given the examples in the exercises above and the step by step instructions that follow, you should be able to write a working program. Remember to load your program after each step to check for any syntax errors. Try using simple queries to test the predicates as you define them to check they work as you intend. </div> <div class="nb-cell markdown" name="md21"> ### A suitable state representation In order for the planner to work, it must manipulate _states_ representing the scenario under consideration --- in this case the locations of missionaries and cannibals on the banks of the river. We can represent a group of objects by a list. For instance: `[boat, canni, canni, missi]` and since there are two banks, we can represent the whole situation at any given point in the scenario by two lists. Prolog provides flexible syntax for combining data entities to form more complex structures. One simple way to do this is using the plus symbol, `+`. Thus, I can represent a state in this scenario by a structure such as: ``` [boat, missi, missi, canni, canni] + [canni, missi] ``` In this representation `+` has no special meaning. It is simply used to combine two lists together to form a more complex data structure. I could have used any binary operator --- such as `-` or `=`. (`=` is quite good as it looks a bit like the banks of a river, but I think it would confuse some people.) </div> <div class="nb-cell markdown" name="md22"> # Other Stuff </div> <div class="nb-cell query" name="q32"> is_list([]). </div> <div class="nb-cell query" name="q33"> number(1.1) </div> <div class="nb-cell program" name="p3"> make_numlist(1,[]). make_numlist(N,[X]) :- M is N-1, make_numlist(M,X). eval_numlist([],1). eval_numlist([X],N) :- eval_numlist(X,M), N is M+1. mynth1(N, L, X) :- integer(N), make_numlist(N, NumL), mynth1sub(NumL, L, X). mynth1(N, L, X) :- var(N), mynth1sub(NumL, L, X), eval_numlist(NumL, N). mynth1sub([], [H |_], H). mynth1sub([NumL], [_| Rest], X) :- mynth1sub( NumL, Rest, X). </div> <div class="nb-cell query" name="q34"> mynth1( N, [a,b,c,d,a,f], a ). </div> </div>