COMP24412 Academic Session: 2020-21
Lab 2: Prolog
Giles Reger (with thanks to Joe Razavi and Martin Riener)
Before we begin a few points:
• Submission is via git for this lab – see the section at the end of this document about submission.
• You should use your comp24412 repository (branch lab2) as a starting point. To get the starting code run
git checkout master
git remote add base https://gitlab.cs.man.ac.uk/mbaxjgr2/comp24412_2020_base.git
git fetch base
git checkout base/lab2
git checkout -b lab2
git push -u origin lab2
This grabs the starter code from the base repository, creates a new branch in your repository, and pushes this new branch to your repository on GitLab.
• This document consists of three parts. Only Part 1 and Part 2 are assessed. The very long Part 0 exists to give you some practice with Prolog, skip as much of this as you want as soon as you are happy. Beware, some exercises in Part 0 are harder than those in Parts 1 and 2.
• Parts 1 and 2 are independent. The beginning of each part is easier than the end, so if you are stuck on one part, you might try switching to the other.
Learning Objectives
At the end of this lab you should be able to:
1. Use the Prolog interactive mode to load and query Prolog programs 2. Model simple constraint solving problems in Prolog
3. Define recursive relations in Prolog
4. Explain issues surrounding termination in Prolog
5. Use an accumulator approach to detect cycles in reasoning
1
Part 0: Getting Started
As noted above, you don’t get any marks for doing things in Part 0 but doing some of it will probably help with your Prolog in general. The important thing is that you think about what you’re doing and what you’ve learnt – don’t just go through the exercises completing them and skipping the thinking parts! There are solutions to all of the exercises in Part 0 at the end but we strongly suggest you give things a go before taking a look! (The last of these warmup exercises were the assessed exercises last year!)
Running Prolog (read this)
Open up a terminal and run swipl. You have just started the SWI-Prolog interactive mode, it should look a bit like this.
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.7.11)
Copyright (c) 1990-2009 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?-
The ?- is the prompt where we can type things. To get out of interactive mode you should type halt. (the . is necessary).
The expected usage is that your Prolog program (knowledge base) is stored in a file and you load this into the interactive mode and query it. For the warmup exercises we suggest you create a file warmup.pl (open it in gedit or similar) and run swipl in the same directory. Alter- natively, we can add queries directly to a program and run this from the command line using the pl command but we assume that you are using the interactive mode.
Warning. Not all Prolog implementations are the same. We are using SWI-Prolog in this course because it is what is on the teaching machines. They also have Sictus Prolog if you prefer to use that.
To load your warmup.pl file into interactive mode type 1 ?- [warmup].
true.
The true response tells you that the file was loaded correctly. You can now type queries directly in the interactive mode. Add the line loves(mouse,cheese) and loves(monkey,banana) to warmup.pl and run the following query
2 ?- loves(X,Y).
X = mouse,
Y = cheese
(You probably need to reload the file). Recall that this returns an answer substitution (assignment to variables). Type ; to get more answers or . to stop searching. In this example what happens to the answers you get if you swap the two lines you have in warmup.pl?
If you change warmup.pl you can reload it into interactive mode by typing [warmup] again. You don’t need to stop and restart interactive mode.
2
Facts and Queries
Above you gave an extensional definition for a predicate loves/2. We write it as loves/2 to indicate that it has the name loves and arity 2. You don’t type in the 2. The reason we do this is because you’re allowed to define a separate predicate loves/3 etc. Try adding some more facts above this predicate and asking different queries of the facts. If your query contains variables then Prolog will match it against the known facts. Try and write some queries that just return true, some that return false, and some that return an answer substitution.
Experiment with Unification
Recall that two terms unify if we can apply the same substitution to both terms and produce two terms that are syntactically equal. In Prolog the notion of equality is to do with whether things unify.
Decide if the following terms are syntactically unifiable (without occurs-check) using the builtin =/2 predicate on the prolog shell and write down your results. You can use subsumes term/2 to check if the first argument matches the second term (but if this is confusing then skip it for now). Recall, the difference between unification and matching is that two terms unify if we can apply a substitution to both terms to reach two syntactically equal terms, whereas in matching you may only apply a substitution to the matching term.
Note that =/2 is special as you can use it infix. So the normal =(1+1,2) can be written as 1+1 = 2, which is a bit nicer to read. Just type these queries into interactive mode (they don’t rely on any defined predicates).
term A = term B A matches B A unifies with B a=b
1+1= X+Y= X+Y= f(a) =
f(X,Y) = f(X,a) =
2
2
Z f(a,b) f(Y,a) f(b,X) f(Y,Z,X)
f(Y,a,b).
f(Y,a,a).
a
X [A,B]
f(X,Y,Z)
f(X,X,Y)
f(X,X,Y)
= = =
[X]=
[a]= [X|Xs] =
[X,Y,Z] =[[A,B]|[C,D]]
Why does a not unify with b? It might seem obvious but we are assuming that things with unique names are unique. This is different from first-order logic, which has no such constraint. This is often referred to as the unique names assumption.
Why does 1+1 not unify with 2? Note that in 1+1 the + is infix and the term could be written +(1,1) now the equality +(1,1) = 2 is no different to f(a,a) = b for the purposes of unification. Numbers and symbols such as + are just treated as any other symbol.
For the last case concerning lists you may want to write out the syntax tree for the two lists. As a quick reminder [X | Xs] stands for a list with head X and tail Xs.
3
Exploring Lists
Consider the following definition for a predicate that checks whether its argument is a list.
isa_list([]). % The empty list is a list
isa_list([Head | Tail]) :-
isa_list(Tail). %Any head prepended to a tail list is a list”
This is a recursive definition. Do you understand what is going in? Try running the queries isa list([a,b]) and isa list(a) and think about what is going on. Now use a similar approach to define a recursive predicate member of/2 that should succeed if the first argument is a member of its second argument (a list).
Now consider the following definition for a predicate nonmember of/2 that should succeed if the first argument is not a member of its second argument (a list).
nonmember_of(_X,[]). % Any element is not in the empty list
nonmember_of(X,[Head|Tail]) :-
dif(X,Head), % X is different from the head
nonmember_of(X, Tail). % X is not in the tail
The dif predicate is a special in-built predicate that adds the constraint that the variables X and Head are not allowed to unify to the same elements in the future – note that this is more general than the in-built \= predicate which requires its arguments to be sufficiently instantiated. Note also that dif is different from not as it only restricts unification rather than inverting the truth of a subgoal.
For each of the three predicates, write a query containing variables that succeeds and one that fails. All of the queries should terminate, ie. query, false. must return with false.
More pattern matching with Lists
Lists are important in Prolog. We will often need to pattern match against lists. For example, add following rule to warmup.pl
bigger_than_one([_,_|_]).
It defines a relation bigger_than_one that is true on all lists with at least two elements. It does this by matching against the start of the list with _,_, ensuring at least two elements, and then the rest of the list with |_ allowing for longer lists. Try this rule out on various lists.
The rule
same_head([X|_],[X|_]).
relates any two lists with the same first element (head) regardless of length etc. Try it out on some pairs of lists, what about lists containing lists? Now
• Write a rule that relates any two lists with the same second elements.
• Write a rule that relates any two lists such that one is a prefix of the other e.g. they are equal
up to the length of the shortest.
Define all different
Using nonmember of/2, define alldifferent(List) such that all elements in List are different. Hint: think about a suitable base case. Then define the recursive that describes what additional constraints have to hold if a new element is prepended to this list.
4
Try your predicate on the following queries:
alldifferent(Xs).
alldifferent([]).
alldifferent([a, A, B])
alldifferent([a | Xs])
alldifferent([X, Y, X | Zs])
Xs=[ , , , , ], member of(X,Xs), alldifferent([X|Xs])
Can you find some other interesting queries?
Exploring terms
This one is less important but interesting. If you’re running out of time then consider skipping it, or just reading through it without doing the exercises.
Terms are built out of functions applied to objects but these are not functions in the sense of the mathematical functions you may be used to. They are term algebras or algebraic data types. For this reason we should, perhaps, call function symbols constructors as they construct new terms from smaller terms. In contrast to other programming languages that contain data-types, Prolog performs no type-checking. This is the reason for defining predicates in the style of isa list that describe those terms that are lists.
To understand what this means let us first note that objects are really zero-arity functions (i.e. func- tions applied to zero arguments). Due to the unique name assumption we have that a = b is always false as objects with different names are always different.
The same concept applies to terms. Functions applied to different terms represent different objects e.g. because a and b are different the terms f(a) and f(b) are always different. The nice thing about this characterisation is that terms from an algebraic data type have a single model (all symbols are interpreted as themselves) – if you’re not sure what we mean by ‘model’ then we will revisit this later in the course.
We use terms to store structured data. For example, we can define lists using a next constructor instead of using the in-built syntax e.g. next(a,next(b,empty)) for [a,b]. Another common data type you will use is that of a tuple – a fixed-length list of values. The semantics of terms mean that two tuples are always different if their contents is different. This is, therefore, a good way of encoding some state of a system or a row of a table.
A common data type used in many examples is that of natural numbers. This has one object (zero) and one constructor (succ for successor). Terms are of the form zero, succ(zero), succ(succ(zero)) etc. If we wanted to introduce the name two for succ(succ(zero)) we might try and write this as two = succ(succ(zero)) but this won’t work because our notion of equality (=) is that of algebraic data types (which doesn’t allow this). It is possible to define our own equality over terms but this usually needs the help of a predicate that can describe the structure of a term (a so-called meta-logical predicate).
To get some experience modelling things using terms, have a go at completing the following Prolog program by adding more students, courses, and groups and finishing the relations.
student(bob).
course(comp24412).
group(h).
5
entry(row(Student,Course,Group)) :-
student(Student), course(Course), group(Group).
table(Table) :-
% check that Table is a list of rows
select_table_group(Table,Group,Result) :-
% check that the rows in Result are exactly
% the rows in Table that have group Group
This kind of idea is similar to what you should be thinking about in the next exercise.
Scheduling Exercise
A major difference between Prolog and languages you may be more familiar with is that Prolog is a declarative programming language e.g. one describes what a solution to a problem looks like rather than how to produce it. We explore this idea here.
The problem is that of scheduling. I have to meet 6 project students in pairs and have 3 slots in which I can do this but there are some constraints. Let us call the students student1 etc and the slots slot1 etc and fix that a higher-numbered slot occurs after a lower-numbered slot. The constraints are that:
1. student1 must meet in slot1
2. student2 and student3 must meet in the same slot 3. student1 and student4 cannot meet in the same slot 4. student6 cannot meet in slot1 or slot3
Clearly I should meet each student exactly once.
We suggest that you start by specifying which objects are students using a student/1 relation. Re- member that unless you explicitly mention an object it does not exist due to the domain closure assumption.
Now you should complete the following predicate definition for meetings one two three/3. We suggest using alldifferent/1 for the first point and defining a predicate are_students/1 similar to member_of/2 for the second point. Here the notation A-B is shorthand for defining a pair of things i.e. the predicate has 3 arguments, but each represents a pair X-Y that goes in there. So even though your predicate definition has a variable for each student, the query meetings one two three(Slot1, Slot2, Slot3) will report answers like Slot1=studentX-studentY.1
meetings_one_two_three(A-B,C-D,E-F) :-
% A-F are different
% A-F are students
% constraint 1
% constraint 2
% constraint 3
% constraint 4
% (optional, pairs are arbitrarily ordered to prevent multiple equivalent solutions)
1But calling meetings one two three(A,B,C,D,E,F) with 6 arguments should not work.
6
If you choose to arbitrarily order students then this should place the ‘larger’ student (with the higher number) on the left.
The constraints above require disjunction over a single predicate e.g. f(X) is true for some given values of X. Recall that the goals in a rule are a conjunction. There are two possible approaches one could take here.
1. Define a helper-predicate that enumerates the disjuncts that are true and then simply use this predicate along with backtracking to enumerate the possible solutions. For example, if you would like to express that X=1 or X=2 at a given point, you can define a predicate one or two/1 via two facts (one or two(1). one or two(2).) and use one or two(X) instead.
2. Use lists to give the given values. If X=1 or X=2 then X is a member of the list [1,2].
We suggest writing out our answer in a separate meetings.pl file. Note that you should let Prolog do the work here, you should not infer the consequences of the constraints yourself and write out the solution.
Now think about the following, preferably write down your answers to check against the solutions later:
1. What is the search space of this problem e.g. the number of all possible solutions without constraints
2. How many solutions to the constraints should there be? Does your program return all possible solutions? If not comment on why not (it is not necessary to but you should understand why).
3. Does the order in which you check the constraints affect (i) the number of solutions returned, or (ii) the amount of work required to find all solutions?
Finally, can you think of a non-trivial constraint to add that means that there is no solution?
Family Relations
A very natural relationship to model is that of family relations. We’ll explore this idea here and use it to look at recursively defined relations. For the first few steps use the greek_family.pl Prolog knowledge base provided in your git repository in the part0 directory. Note that this is technically incomplete and also contains some relations that are not universally agreed upon. It’s just a bit of fun and interesting for this example as the Greek god family relations were… complex.
Step 1. Non-Recursive Relations
Define the following binary relations in a file family_relations.pl
• father(X, Y ). X is the father (a parent who is a man) of Y
• mother(X, Y ). X is the mother (a parent who is a woman) of Y
• sibling(X, Y ). X and Y have at least one parent the same but are different people.
• brother(X,Y). X is a man and a sibling of Y
• sister(X, Y ). X is a woman and a sibling of Y
• first cousin(X, Y ). A parent of X is a sibling of the parent of Y and X and Y are different people.
7
You may also want to add some other relations, such as aunt, niece, grandparent etc. To test these relations you can load the two files e.g.
1 ?- [greek_family].
2 ?- [family_relations].
and check a few queries do what you expect, such as
3 ?- father(zeus,artemis).
true
4 ?- sister(hera,X).
X = zeus ;
X = demeter.
5 ?- first_cousin(mygdon,orpheus).
true.
Write queries to answer the following questions:
1. Who is the father of zeus?
2. Is giles a parent of anybody?
3. Which first cousins are of different gender?
4. Which men have sisters? Can we get a unique list of answers?
What about the query Which men do not have fathers? This is tricky as we cannot answer this without negation (why not?). But this allows us to demonstrate a safe usage of negation. The safe case to use negation-as-failure is if you ensure that the negated part of the query is fully-instantiated when it is executed. Can you write a query that ensures this? Secondly, note that the way that we have modelled the parents relation makes this query difficult to answer and therefore we should change our representation to make it easier to answer the queries we want to ask.
Step 2. Recursive Relations
The above relations were defined in a fixed way in terms of other relations. The power of Prolog is in recursive relations where a relation can be defined in terms of itself. Extend family_relations.pl with the following two recursive relations:
1. ancestor(X, Y ). X is an ancestor of Y if X is Y ’s parent or an ancestor of one of Y ’s parents. A person should not be their own ancestor.
2. cousin(X, Y ). The general definition of cousin is to share a common ancestor such that the closest common ancestor is two or more generations away i.e. they are not siblings or paren- t/children. Note that this is a generalisation of the common usage that refers to a first cousin (you share great-grandparents with a second cousin etc).
Write queries (using your new relations) to answer the following questions:
1. Find all ancestors of zeus
2. Find all descendants of zeus
3. Can two people be cousins when one is an ancestor of the other?
8
Step 3. Time-Travelling God
Chronos is the greek personification of time. In mythology he created himself but let us use our imaginations and pretend he was a child of zeus and hera but also the mother and father of uranus and gaia (time is ungendered). Add these facts to greek_familiy.pl and check what happens when you ask for Chronos’ cousins. Can you explain what is going on?
Step 4. Reflection on Modelling
In this final step we ask you to think about the best way to model this family relation. Firstly, reflect on whether the parents relation is a good way of modelling a parent relation. Are there things in your family model, or in the real world, that are difficult to capture with this relation. How might you better model the parent relation? Next, come up with an improved way of modelling the family relationship and either convert the above knowledge base or write your own e.g. your own family, a historical family, or a fictional family.
Zebra Puzzle
Consider the following puzzle:
There are five consecutive houses, each of a different colour and inhabited by men of different nationalities. They each own a different pet, have a different favourite drink and drive a different car. We know the following:
1. The Englishman lives in the red house.
2. The Spaniard owns the dog.
3. Coffee is drunk in the green house.
4. The Ukrainian drinks tea.
5. The green house is immediately to the right of the ivory house.
6. The Porsche driver owns snails.
7. The Masserati is driven by the man who lives in the yellow house.
8. Milk is drunk in the middle house.
9. The Norwegian lives in the first house on the left.
10. The man who drives a Saab lives in the house next to the man with the fox.
11. The Masserati is driven by the man in the house next to the house where the horse is kept.
12. The Honda driver drinks orange juice.
13. The Japanese drives a Jaguar.
14. The Norwegian lives next to the blue house.
The problem is: Who owns the Zebra? Who drinks water?
The challenge in this part is to translate the English description of the puzzle into Prolog and find the answer to the puzzle. Thankfully, the above describes a list of facts so it shouldn’t be too complicated. You will have to think about how to model the above knowledge to help answer the given queries. Hint: represent a house as a relation h(Nationality, Pet, Cigarette, Drink, Color) and define a predicate that succeeds if it is given a list of houses matching the above constraints.
9
Solving Arithmetic Constraints
This one introduces a Prolog library that you won’t have to use later and is not ex- aminable. You may want to skip this one. We have kept it here in case anybody is interested in this topic.
Earlier we have seen how to introduce constraints and use Prolog to solve them but we haven’t explored arithmetic yet. Prolog provides the clpfd library to solve constraints involving arithmetic. To use this library you should include the following at the start of your Prolog program:
:- use_module(library(clpfd)).
You may also find this website helpful.
In this part of the exercise you are a busy farmer with two important tasks to handle. You have
chosen to tackle these using constraints in Prolog.
Paying Taxes
The government has just introduced a new tax on cows and chickens. You check your records and realise that you’ve not been recording how many of each animal you have, only how many heads and feet all of your animals have in total.
Write a Prolog program to work out how many cows and chickens you have given that the sum of heads is 65, the sum of feet is 226. You should assume that all animals have the normal number of heads and feet.
Use arithmetic constraints to implement the core relation cows_chicken_eqs(Cows,Chicken) that only expresses the two equations about the numbers of heads and feet. Write a second predicate cows_chicken(Cows, Chicken) that assigns appropriate domains for Cows and Chicken and labels the constraints obtained from the core relation to obtain a solution to the puzzle.
Hint: The query cows_chicken_eqs(Cows,Chicken) of the core relation must always succeed and show the (simplified) constraints but it may not unify the variables with concrete solutions. The query cows_chicken(Cows,Chicken) to the final predicate must unify the variables with concrete solutions but it may not show any constraints.
Planting Crops
Next you need to decide which crops to plant in each of your fields. You have three crops: cabbages, potatoes, and carrots. However, the government department for ‘picturesque fields from above’ does not allow you to plant the same crop in two adjacent fields.
Your fields are laid out as shown in the below map:
10
You are doubtful if this is even possible but to prove it you formulate the situation as a constraint satisfaction problem where each crop is represented by a number. Use a list of six elements repre- senting the fields A to F. First, implement a core predicate crops_eqs(Fields) that describes which neighbouring fields can not have the same crops.
Then implement a predicate crops3(Fields) that assigns domains to the variables in Fields and labels the constraints obtained from the core predicate. Convince yourself that the requirements are impossible to fulfill by checking that the query crops3(Fields) does not find an answer.
After reporting your findings, the department just reiterates the requirements above. However, you think you could get away with planting lavender as an additional crop. Similar to crops3(Fields), implement a predicate crops4(Fields) that uses a four element domain instead and convince yourself that a query to the predicate now yields a solution.
Hint: To find a satisfying assignment of crops to fields you should number the crops and capture the adjacency of fields as disequality constraints. Keep in mind that constraints have their own predicates for equality (#=) and disequality (#\=).
You notice that the fields [1, 2, 3, 4, 1, 2] and [2, 1, 3, 4, 2, 1] describe the same solution where the names of crop one and two are just switched. Implement a core predicate crops_asym(Fields) that adds asymmetry constraints on the field.
11
Some Solutions to Part 0
We give solutions to most exercises in Part 0. Some solutions files exists in part0/solutions of your git repository (branch lab2).
Exploring Lists
A correct definition of member_of/2 is
member_of(X,[Head|_Tail]) :- % X is member of a list
X = Head. % if X is the head of the list
member_of(X,[_Head|Tail]) :- % X is member of the list
member_of(X, Tail). % if X is member of the tail
It is interesting to note that the Prolog engine will need to try both rules on every input as any fact that unifies with the head of one rule will unify with the head of the other. However, if we rewrite the base case to the more succinct
member_of(X,[X|_Tail]). % directly unify in head
we will fail to unify with the base case if it does not apply, thus leading to less backtracking.
Define all different
Another recursive function. The base case is that all members of the empty list are different. The recursive case is that all members of a list are different if the head of a list is not a member of the tail, and all members of the tail are different.
all_different([]).
all_different([X|Xs]) :-
nonmember_of(X,Xs),
all_different(Xs).
Scheduling Exercise
See part0/solutions/meetings.pl for an example solution. Some things to note:
• Because of the closed-world nature of Prolog it’s necessary to declare all six student objects explicitly. We use a student/1 relation to declare these objects to be of the type student – this is very common in modelling in an untyped language (e.g. Prolog).
• There is some symmetry in the constraints where we want to say that two students can appear in either order in a pair of slots. It may be tempting to use the disjunction operator but the given solution avoids this by defining an auxiliary rule (student23slot). I tend to avoid disjunction where it might impact readability.
You were also asked to think about some things
1. The search space is all permutations of 6 students, which is 720 – this is taking things after we have declared that all students are different. If we look at the problem before this then it is 66 = 46656. All constraints should reduce the size of the search space until we just get the soutions.
2. If we don’t arbitrarily order pairs then there are 6 possible solutions, otherwise there is one. If we have constrained the order of one pair during the constraints then it might return 3 or 4 e.g. if we did not fully capture the symmetry of all constraints.
12
3. (i) no as long as we don’t use anything dependent on cut, which you shouldn’t. (ii) yes, a simple example is the difference between checking A-F are different before checking that they are students and vice-versa.
A simple way to remove all solutions would be to add a constraint that is equivalent to false, e.g. a=b. Family Relations
See part0/solutions/family relations.pl for an example solution. Below we give some comments on each of the steps:
Step 1
• In our solution we define a more sensible binary parent relation, similarly we define a general sibling relation, both of these allow our definition of other relations to be simpler than if we used the parents relation directly.
• It might be tempting to define father as a parent who is not a mother, but consider
father(X,Y) :- not(mother(X,Y)), parent(X,Y).
The meaning of this is that if it can find a mother X for Y then the not query will fail and there will be no fathers. We want to avoid using negation wherever possible and only use it in ‘safe’ places (see below).
• The queries for the given questions can be given as follows for the provided family relation definitions.
1. father(X,zeus).
2. parent(giles,_). – we use _ as the query doesn’t care who the child is if they exist
3. first_cousin(X, Y), man(X), woman(Y). – note that as first_cousin is symmetric we can make X a man and Y a woman without losing any solutions.
4. A simple answer is man(Y), sister(_X,Y), which is likely to give the same answer multiple times as the definition of sister just requires the sharing of one parent and Prolog will backtrack and find he other parent and use this to return the same answer. There are a few ways to get unique solutions. One would be to use the built-in distinct predicate. Another would be to use the forbidden cut operator to define a relation
has_sister(X) :- sister(_Y,X), !.
andthendefinethequeryman(X), has_sister(X).Anaiveexplanationofthecutoperator is that it tells Prolog not to backtrack before the operator. Therefore, here we tell it not to look for other sisters. The cut operator is non-logical but is often essential for making Prolog programs efficient (and not return too many answers). But we don’t introduce you to cut because it can be tricky to get right – try looking up the difference between a green cut and a red cut.
• For Which men do not have fathers a safe solution is man(X), not(father(_,X)).
an unsafe solution is
not(father(_,X)), man(X).
as the query father(_,X) can succeed, making the whole query fail. The key point is that we need to fix the man X before asking if he has a father.
13
Step 2
• The first thing to note here is that the notion of cousin in the general sense can be non-intuitive. The given proposed solution works by using an accumulator to track the path of ancestry in the ancestor predicate and then using this to ensure that the shared ancestor is at least two generations away. There may be better solutions.
• Ancestorsofzeuscanbegivenasancestor(X,zeus,_)anddescendantsareancestor(zeus,X,_) e.g. the other direction
• Given our definition of cousin, yes – see cousin(X,Y), ancestor(X,Y,_) but this will depend on how you have defined cousin!
Step 3
• What you will observe is that there are infinite answers. This is because we have a loop in the graph that we are recursing over.
Step 4
• The parents relation is bad for lots of reasons – it doesn’t capture cases where somebody has one parent or three parents, it doesn’t capture step-parents or adoptive parents, and it seems to assume the gender of parents by the order of arguments and therefore doesn’t support same-sex parents.
Zebra and Crossing
See solution in part0/solutions/zebra.pl.
14
Part 1: Electrical Interference
You have joined a team working on the space program of a small country. The team is working hard trying to design a probe to send to a distant planet. The electrical engineering department is working on a list of components of the probe. For each pair of components, they have done tests to see whether the components can be put close to each other without interfering with each other and breaking. They have summarised their results so far in the following Prolog database (there is a copy of this in part1/database.pl).
component(antenna).
component(transponder).
component(radar).
component(spectrometer).
component(imu).
component(camera).
component(cpu).
component(ram).
safe_with(radar,cpu).
safe_with(cpu,radar).
safe_with(radar,imu).
safe_with(imu,radar).
safe_with(imu,camera).
safe_with(camera,imu).
safe_with(imu,cpu).
safe_with(cpu,imu).
safe_with(imu,ram).
safe_with(ram,imu).
safe_with(ram,cpu).
safe_with(cpu,ram).
safe_with(ram,camera).
safe_with(camera,ram).
safe_with(camera,transponder).
safe_with(transponder,camera).
safe_with(camera,cpu).
safe_with(cpu,camera).
safe_with(cpu,spectrometer).
safe_with(spectrometer,cpu).
safe_with(cpu,antenna).
safe_with(antenna,cpu).
safe_with(antenna,spectrometer).
safe_with(spectrometer,antenna).
safe_with(antenna,transponder).
safe_with(transponder,antenna).
safe_with(transponder,spectrometer).
safe_with(spectrometer,transponder).
Your task is to write software in Prolog to help the designers of the probe check that their designs will work, in that they only place components close together if the engineers have shown those com- ponents don’t interfere. You should complete the provided file part1/electrical.pl. Note that to gain full marks you must provide an explanation of what you have done (see mark scheme at the end).
15
Exercise 1
To get started, write a predicate safe_list/1 (i.e. a predicate with functor name safe_list and taking 1 argument) which takes a list of components and which succeeds if and only if every component in the list is safe for use with every other component. For example safe_list([cpu,imu,radar]) should succeed, but safe_list([ram,cpu,radar]) should fail. You may define extra predicates if you wish (this is true for all exercises in this lab).
Now, the engineers don’t just want to study lists of components, they also want to analyse abstract designs for the probe. A design is a list where each element is either of the form part(C) for some component C, or else of the form shield(L), where L is a design and the first element of L is of the form part(c). For example
[part(imu), shield([
part(cpu),shield([part(cpu)])
]
is a design, but
])
[part(imu), shield([
shield([part(cpu)]),shield([part(cpu)])
])
is not, because all the elements in the argument of the outermost shield are themselves of the form
]
shield(X) – the first one is not of the form part(X) as required.
You can assume that you will be given a properly formatted design. However, you may find it in- structive to write a predicate to check whether a design is properly formatted (no marks for this).
The meaning of sheild(L) is that the elements of L have been electrically shielded from the outside world. That means that we can check whether a design is safe by checking whether all the parts which are not inside shields are safe when used with each other, then recursively checking whether the contents of each shield are a safe design. For example, the design
[part(radar), part(imu), shield([
part(antenna),part(transponder)])
]
is safe, because the radar and imu are safe together, and the antenna and transponder are safe
together. But
[part(radar), part(camera), shield([
part(antenna),part(transponder)])
]
is not safe because it puts the radar and camera together without surrounding one of them with
shielding, while
[part(radar), part(imu), shield([
part(antenna),part(camera)])
]
is not safe because the camera and antenna are not safe together.
16
Exercise 2
Write a predicate safe_design/1 which, when given a design as input, succeeds if and only if the design is safe in the above sense. Note it is unlikely that you will be able to use the predicate safe_list/1 from Exercise 1 directly, however the structure of your answer to this exercise is likely to be similar. It is likely that you will need to define auxiliary predicates. You do not need to worry about how your predicate behaves if the argument is not a design according to the definition above. If you are struggling with this part, you might find the next one easier.
Since the finished probe is supposed to be carried into space by a rocket, it is important for it to be as light as possible. The engineers are trying to use as little shielding as possible. As a first approximation, they want the software to count the number of times shield is used in a design.
Exercise 3
Write a predicate count_shields/2 which succeeds if and only if its second argument is the number of times shield occurs in its first argument. It must be possible to use your predicate in the query count_shields(D,N) where D is a design and N is a variable, so that Prolog returns the number. For example
count_shields([part(imu),shield([
part(ram),shield([part(radar)])
]),
shield([part(cpu)])
],N)
should return N = 3. You do not need to worry about the behaviour of your predicate if the first
argument is not a design according to the first definition.
Finally, the engineers want to check that a design does not have any components missing. The idea is that they will provide a design and a list of components, and the software should be able to tell if each component in the list is used exactly once somewhere in the design.
Exercise 4
Write a predicate design_uses/2 which accepts a design and a non-empty list of components as arguments, and succeeds if and only if the first argument is a design, and the components used in the design are exactly those listed in the list. Each element in the list must be used exactly once in the design (if a component is repeated, it should be occur as many times in the design as there are repetitions of it in the list). Note that the elements may appear in a different order in the design compared to the list. Finally, the predicate should fail if the first argument is not a design as defined above (we do count the empty list as a design).
Before attempting to write design_uses/2, you should first write a predicate split_list/3 with three arguments, which succeeds if the first argument can be split up into the other two arguments. For example, the query split_list([1,2,3],X,Y) should return the results
X = [1, 2, 3],
Y = []
X = [1, 2],
Y = [3]
X = [1, 3],
17
Y = [2]
X = [1],
Y = [2, 3]
X = [2, 3],
Y = [1]
X = [2],
Y = [1, 3]
X = [3],
Y = [1, 2]
X = [],
Y = [1, 2, 3]
It may be helpful to think about going through the list element by element, and allocating each el- ement either to the second or third argument, before recursively allocating the rest. You may then like to contemplate the results of the query split_list([1,2,3],[H],R).
Make sure your test your solution(s). You should ensure that your solution works where components are repeated in the component list, for example, design_uses(D,[imu,imu]).
Exercise 5
Once you have finished all the exercises, you should try running the query design_uses(D,[imu,cpu]). Ideally this will list all possible designs using one imu and one cpu. This will depend on ensuring your previous definitions are not unnecessarily restrictive. If this works, try running the query
design_uses(X,[transponder,spectrometer,antenna,ram,cpu,imu,radar,camera]),
safe_design(X),
count_shields(X,2)
although you might prefer to see if you can find a solution manually first. It might be that your Prolog code goes into an infinite loop. Don’t worry if so as this was a difficult exercise, but there might be interesting lessons to learn from how your code behaves given this query. Note that even code which makes this query terminate might not terminate in any practical length of time!
Answer the following questions as comments in the code:
1. How many solutions should the query design_uses(D,[imu,cpu]) return? Why?
2. If the query design_uses(D,[imu,cpu]) terminates for you, what ensures that it terminates. If it does not, why not?
3. How would you phrase a query for a solution using the transponder, antenna, radar and cpu such that the radar is not shielded?
18
Part 2: Crossing the River
Perhaps you know the following puzzle:
A farmer is traveling with a wolf, a goat, and a cabbage to the market. On the way she encounters a river that she can only cross with a boat. Unfortunately, the boat is so small that she can take only one of the three to the other side. What makes matters worse is that when left alone, the wolf will eat the goat and the goat will eat the cabbage. Is there a way to get everyone safely to the other side? If yes, which sequence of moves will do the trick?
We will solve the puzzle in several steps: first, we will describe the datastructures and introduce some helpful predicates. Next, we will write a solution that finds the moves but will not terminate. At least we will get rid of moves that lead us back to situations we have already encountered.
Why? This puzzle is a good (small) example of how we can use logical programming to generate plans as sequences of actions to achieve goals under some constraints.
Exercise 6: Data-structures and Helper Predicates
Define a predicate is pos/1 that describes the sides of the river. There is no name in the puzzle, so let’s call them south and north. In other words, the queries is pos(south). and is pos(north). will succeed but nothing else.
Define a predicate side opposite/2 that represents crossing the river. Therefore, side opposite is true if (and only if) both arguments are opposite sides of the river. Remember that the farmer needs to be able to row back.
We also need to track the position of the farmer, the wolf, the goat and the cabbage2. The easiest way to group these up is to use a function fwgc/4 that stores the position. Let us define a predicate is state that describes what a possible state of the system is. The predicate is state/1 is true for terms of the shape fwgc(Farmer,Wolf,Goat,Cabbage) where each of the variables is one side of the river. E.g. the query is state(fwgc(north,south,north,north)). will succeed but is state(nostate). and is state(fwgc(athome, , , )). must fail.
How many answers should is state(S) have? Out of is pos, side opposite, and is state, which have been defined extensionally and which have been defined intensionally?
Exercise 7: An Inefficient Solution
Define a predicate safestate/1 that is true when its argument is a state in which the wolf cannot eat the goat and the goat cannot eat the cabbage. Convince yourself that it always terminates – you can do this by making sure that
safestate(S), false.
reports false as the false part will only be reachable if safestate(S) terminates.
The next step encodes crossing the river. Define a predicate puzzlestate moves/2 relates the
current state to a list of moves that lead there:
• Initially, everyone is in the south.
Hint: use the empty list as starting history e.g. the base case is where we are at the start and have taken no moves.
2Why is there no need to track the boat?
19
• Assume we have already derived a state S0 reachable via the moves Ms. Describe a new state S that follows the rules of the game and that is safe. Give the rule a name M. Then the state S is reachable with history [M|Ms].
Hints:
– Make use of the helper-predicates defined above (you will not need all of them)
– If the farmer goes alone (M=alone), the new state will have her on the other side but
everything else stays the same.
– If the farmer takes one of the items with her (M=wolf, M=goat, M=cabbage), they will switch sides together and the other two items remain where they are.
When you run the query puzzlestate moves(fwgc(north,north,north), Moves), it is stuck in an infinite derivation loop. Why do we get non-termination here? Write your answer as a comment in the code.
Define a predicate isa_list(L) that is true whenever L is a list. You can use isa list(Moves), puzzlestate moves(fwgc(north,north,north), Moves) to enforce a fair enumeration of lists that ensures the solution is found before non-termination. Why does this work? Write an answer as a comment in the code.
Exercise 8: An Efficient Solution
Based on your solution for puzzlestate moves/2, define a predicate puzzlestate moves without/3 that extends it with an accumulator. Add a goal to all rules that ascertains that the new state does not repeat during the derivation. Remember that an accumulator grows during the recursion while the list of moves shrinks.
Convince yourself that puzzlestate moves without(fwgc(north,north,north), Moves, []) pro- duces the correct solutions and write a query puzzlestate moves without(State, Moves, []), false that shows termination. How can we be sure that this query will always terminate? Add the query and explanation as comments in your code.
20
Submission and Mark Scheme
Submission is via git. You must work on the lab2 branch and tag your submission as lab2 solution. The provided submit.sh script does this for you. Note that you must push your tagged commit to Gitlab before the deadline (it is not good enough just to make the commit locally).
Your work will be marked offline and returned to you with comments. We may automate some tests on your code so please do not edit the general layout (e.g. headings) of the provided files and make sure you use the specified predicate names.
The marking scheme is as follows. • Part 1 (10 marks)
1. (1 mark) for correct safe_list/1
2. (2 marks) for correct safe_design/1, 1 mark if missing a case
3. (2 marks) for correct count_shields/2, 1 mark if missing a case
4. (4 marks) with 2 marks for split_list/2 and 2 marks for the final design_uses/2
5. (1 mark) for answering questions correctly (0.5 for first, 0.3 for second, 0.2 for third)
• Part 2 (10 marks)
6. (2 marks) for correct data structures and helper predicates (Exercise 6)
7. (3 marks) for a correct inefficient solution, 2 marks if mostly correct, 1 mark if attempt made
8. (1 mark) for a correct discussion of the reasons for non-termination and fair enumeration
9. (3 marks) for a correct efficient solution, 2 marks if mostly correct, 1 mark if attempt made
10. (1 mark) for providing a query and explanation to show that the efficient solution terminates
You must provide explanations of the work you have done as comments in the submitted files. These should go beyond standard comments in programs and should not simply reiterate the rules in English e.g. aim to explain the idea not the code. In all cases, up to half of the marks may be deducted if the explanation of the code is not sufficient. You should aim to write in full sentences. You may include brief examples.
21