Chapter 3 Lab Exercises
Lab 1 Databases
The objective of the following exercise is to get acquainted with the SICS- tus Prolog environment. You will practice writing and compiling programs and execute your programs by posing queries to the system. It is important that you prepare yourself by reading the previous chapters. Also, take the opportunity to try out the debugger and take a look in the manuals.
Exercise 1.1 A Small Deductive Database
Translate the following scenario to definite clause form: 1. Ulrika is beautiful.
2. Nisse is beautiful and rich.
3. Anne is rich and strong.
4. Peter is strong and beautiful. 5. Bosse is kind and strong.
6. All men like beautiful women. 7. All rich persons are happy.
8. All men who like a woman who likes him are happy.
9. All women who like a man who likes her are happy. 10. Nisse likes all women who like him.
12
LAB 2. RECURSIVE DATA STRUCTURES 13 11. Peter likes everyone who is kind.
12. Ulrika likes all men who likes her, provided they are either (1) rich and kind, or (2) beautiful and strong.
Use the program to answer the questions “Who is happy?” and “Who likes whom?”. Also make the program answer the question “How many persons like Ulrika?”. For this query you probably need to use the built-in predicates findall/3 and length/2 about which you can read in the manual.
Explain your choice of the order of the clauses in your program, and the order of premises in the rules.
Exercise 1.2 Recursion
Consider the graph to the right. Rep-
resent the graph as a set of edge/2
facts, where each fact corresponds to a
direct edge between two nodes in the
graph. Then write a predicate path/2
which relates a node to another node
if and only if there is a path from the
former to the latter in the graph. Then
first write a predicate path/3 that de-
scribes the relation between two nodes
and also records the path between them, and second a predicate npath/3 which describes the relationship between two nodes and also returns the length of the path between them. Hint: use the predicate path/3 and the built-in predicate length/2 for finding the length of a list. Your program is required to work with arbitrary graphs without cycles.
Lab 2 Recursive Data Structures
The purpose of the following exercises is to study how to manipulate recursive data structures in Prolog and to get a feeling for how the search strategy of Prolog affects the structure of the program. You are not allowed to use built-in or library predicates defining list operations, except for member/2, append/3.
ab
cdh
ef
g
14 CHAPTER 3. LAB EXERCISES Exercise 2.1 Sorting
Write a predicate issorted/1 checking whether a given list of numbers is sorted in the ascending order.
Write two recursive sorting programs, ssort/2 and qsort/2, that sort lists of integers according to the following two principles:
• Selection sort. Transform a given list L into a list L1 with the same elements, but with the first element being the smallest one. The first element of L1 is the head of the sorted list LS to be obtained, the tail of LS is obtained by sorting the tail of L1.
• Quicksort. Pick an integer N that occurs in the list that should be sorted (for instance the first element in the list) and partition the list in two lists – one that contain all elements less than N and the other with the rest of the elements. Sort the lists and concatenate the resulting (sorted) lists.
Use the built-in predicates =/2 to compare integers. Exercise 2.2 Search Strategies
Consider the recursive predicate middle/2 below:
% middle(X,Xs)
% X is the middle element in the list Xs
middle(X, [X]).
middle(X, [First|Xs]) :-
append(Middle, [Last], Xs),
middle(X, Middle).
Examine how the execution of the following queries is affected by the ordering of the clauses and the premises within clauses.
| ?- middle(X, [a,b,c]).
| ?- middle(a, X).
Try all four possible orderings and (1) explain what happens, and (2) why it happens. Choose two queries and two programs and draw the resulting SLD-trees. One of your SLD-trees should be finite, and the other infinite (in which case you only have to sketch it). You are allowed to treat append/3 as a black-box). Don’t forget to explain what happens when you ask for more than one answer! Which version is preferable for each type of query?
LAB 2. RECURSIVE DATA STRUCTURES 15 Exercise 2.3 An Abstract Machine
In this exercise you will write an interpreter for a small imperative program- ming language which we will call imp. We will assume that the language is given by the following abstract syntax. We first assume the existence of primitive symbols
I – Identifiers
N – Natural numbers
A binding environment is a mapping from identifiers to natural numbers and is an abstraction of a memory. A binding environment can be represented as a list [i1 = n1, . . . ik = nk] where identifier i1 has the value n1, identifier i2 has the value n2 etc. imp also has the following language constructs
% Boolean expressions
B ::= tt | ff | E > E | …
% Arithmetic expressions
E ::= id(I) | num(N) | E + E | E – E | E * E | …
% Commands
C ::= skip | set(I, E) | if(B,C,C) | while(B,C) | seq(C, C)
Here tt and ff are constants for Boolean true and false, skip is a command that does nothing, set(I,E) is a command that assigns the value of E to the identifier I, and seq(C,C) means the sequential execution of the first argument followed by the execution of the second argument.
Choose a suitable Prolog representation of identifiers and natural num- bers. Then define the semantics of imp by first defining predicates describ- ing the values of arithmetic and Boolean expressions, and then a predicate execute/3 describing the semantics of commands. Use Prolog arithmetic to evaluate arithmetic expressions. Predicate execute/3 should relate an ini- tial binding environment S0 and an imp program command P with the final binding environment Sn that is the result of executing P . For example, if S0 is [x=3] and P is the program
seq(set(y,num(1)),
while(id(x) > num(1),
seq(set(y, id(y) * id(x)),
set(x, id(x) – num(1)))))
then the relation should hold if and only if x is bound to 1 and y is bound to 6 in Sn.
16 CHAPTER 3. LAB EXERCISES Exercise 2.4 Set Relations
Prolog defines an order relation on all terms. The built-in (and infix) predi- cates @<, @>=, etc can be used to compare terms according to this order (see the manual for more information). Assume now that we want to represent sets of ground terms as ordered lists without copies. The set {c,b,a} is then represented with the list [a,b,c]. Write a Prolog procedure that computes the union of two sets. The same for intersection. Also write a procedure that produces the powerset of a set, e.g., using the above set we get the powerset:
{∅, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c}}
represented by list [[],[a],[a,b],[a,b,c],[a,c],[b],[b,c],[c]]. (Re-
member that the resulting lists are to be sorted and without repetitions.)
Notes:
1. When defining union/3 and intersection/3 it is possible to deter- mine which of the two current elements that should be included in the solution, simply by comparing them with the aforementioned order on terms.
2. In the last case it might be a good idea to use the built-in predicate findall/3.
Lab 3 Definite Clause Grammars
In the following exercises you will write a “front end” to the imp interpreter in the previous exercise. The program will consist of two parts: a scanner, that takes a string of characters and produces a list of tokens, and a parser, that transforms the list of tokens into a term that can be executed by the interpreter together with an initial binding environment. Hence, the idea is the following:
run(In, String, Out) :-
scan(String, Tokens),
parse(Tokens, AbstStx),
execute(In, AbstStx, Out).
| ?- run([x=3],
“y:=1; z:=0; while x>z do z:=z+1; y:=y*z od”,
Res).
The result Res should be a binding environment where y=6 (that is, the factorial of 3).
LAB 4. SEARCH 17 Exercise 3.1 Parser
In this exercise you will write a parser (in the form of a dcg) which recognizes the following strings of tokens:
::=
|
|
| if
| while
::=
| …
::=
|
|
|
Note that you must implement the parser via a set of dcg rules, and not by the resulting Prolog translation. The parser should return the corresponding abstract syntax object. That object will then be used as input to the abstract machine previously. To make the problem somewhat easier we assume that all operators are right-associative. (This is fine with associative operators such as + and *, but yields non-standard results e.g. for -.)
To make the job somewhat easier you may use an existing Prolog scanner which translates a list of ASCII-characters to a list of tokens (which can be given to the parser). The scanner can be downloaded from the course home page. Play around with the scanner before attempting to write the parser. (In Prolog you may write strings in the form “Prolog” but this is only syntactic sugar for a list of integers corresponding to the ASCII values of the string.)
Lab 4 Search
Three missionaries and three cannibals are standing on the bank of a river. There is a boat but it is only big enough to carry two persons. If the can- nibals, at any time, outnumber the missionaries on either side of the river the cannibals will eat the missionaries. We now want to find a way to trans- port all missionaries and cannibals over the river without having any of the missionaries eaten.
18 CHAPTER 3. LAB EXERCISES
Thus, we have a search problem – a set of states and transitions between them. The problem is to find a sequence of states which takes us from the initial state to a final state without passing an illegal state (a state where the cannibals outnumbers the missionaries on a bank of the river). You will write two Prolog program which, using two different search strategies, helps the missionaries and cannibals to get over to the other side of the river without anyone being eaten.
The programs should display the solution (i.e. the sequence of states) in a readable way. (See the SICStus Prolog manual for printing built-ins.) As both programs solve the same problem, they should produce the same solutions, maybe in different order.
Exercise 4.1 Breadth-First Search
Write a program that searches breadth-first in the state space. Note that there are infinitely many solutions to the problem if “loop” detection is not implemented, which is not required in this assignment. The program can therefore stop after finding the first (i.e. shortest) solution. However, the program should be able to enumerate all solutions to the problem by means of backtracking (if loop detection is implemented then only the loop-free solutions should be enumerated).
Hint. See pages 185–186 in the course book. Exercise 4.2 Depth-First Search
Write a program that searches depth-first in the state space. Note that the space contains loops and that it is necessary for the program to detect these and break them. The program should be able to enumerate all loop-free solutions by means of backtracking. How many are there?
Hint. See pages 181–182 in the course book.
Lab 5 Constraint and Answer Set Program-
ming
Exercise 5.1 Scheduling with Constraint Programming
A ship carrying a number of containers has arrived to a port and all of the containers are to be unloaded. Assume that we have a database describing these containers by means of a predicate container(B,M,D), where B is a
LAB 5. CONSTRAINT AND ANSWER SET PROGRAMMING 19
container’s identifier, M is the number of persons required to unload the con- tainer and D is the duration of unloading (D is assumed to be integer valued). A sample database may thus look as follows:
container(a,2,2).
container(b,4,1).
container(c,2,2).
container(d,1,1).
Additionally some containers may have been put on top of others, for in- stance:
The fact that a container is put on top of another is expressed by the predicate on(B1,B2). For the containers placed as shown in the picture, the database will contain the following facts:
on(a,d).
on(b,c).
on(c,d).
Hence, the container d cannot be drawn before a and c and so forth. Design a CLP(FD)-program that for any database consisting of defini- tions of the predicates container/3 and on/2 minimizes the cost of unloading the containers. The cost is defined as the number of workers hired times the required time (in whole hours); and where all workers are hired for the whole duration of the unloading. Thus, your program should contain a predicate schedule(Workers, EndTime, Cost) which is true if Cost is the minimal cost of scheduling the container database, Workers is the number of workers
required in this solution, and EndTime is the required time.
Hints. Load the finite domain solver library of SICStus by the directive :- use module(library(clpfd)) at the beginning of your program. You should use the global constraint cumulative/2 to solve the problem together with labeling/2, to find the minimal cost. Your definition of schedule/3
is thus likely going to end as follows:
b
a
c
d
20
CHAPTER 3.
schedule(Workers, EndTime, Cost) :-
.
.
.
cumulative(Tasks, [limit(Workers)]),
Cost #= Workers*EndTime,
LAB EXERCISES
labeling([minimize(Cost)], [Cost|StartTimes]).
Work backwards from these definitions and constrain variables accord- ingly. For example, each container should correspond to a task in the list Tasks, and each task should have a start time and end time, represented by constraint variables. How should the start and end times of two tasks be constrained if one container is on top of the other? How should EndTime be constrained with respect to the end times of the tasks?
A Larger Example
Consider the following container database:
container(aa, 2, 2). container(ab, 3, 2).
container(ac, 5, 5). container(ba, 6, 2).
container(bb, 1, 2). container(bc, 3, 3).
container(ca, 3, 2). container(cb, 5, 2).
container(cc, 2, 3).
on(aa, ba). on(ab, ba). on(ab, bb). on(ac, ba).
on(ac, bb). on(ac, bc). on(ba, ca). on(ba, cb).
on(bb, cb). on(bc, cb). on(bc, cc).
For this database your program should report that the optimal solution requires 6 workers and 16 time units, resulting in a cost of 96.
SWI-Prolog
SWI-Prolog also contains a finite domain constraint library which is loaded by
:- use module(library(clpfd)). This library is largely compatible with library(clpfd) in SICStus Prolog, but for this assignment there are three peculiarities that need to be taken into account.
1. The predicate domain/3 which allows one to constrain a list of variables according to a lower and upper bound is not included in SWI-Prolog. Use the predicate ins/2 instead.
2. When using labeling/2, write
LAB 5. CONSTRAINT AND ANSWER SET PROGRAMMING 21 labeling([min(Cost)], [Cost|StartTimes])
instead of
labeling([minimize(Cost)], [Cost|StartTimes]).
3. The global resource limit in cumulative/2 is required to be a pos- itive integer, and is not allowed to be a constraint variable. Thus, cumulative(Tasks, [limit(Workers)]) will report an error since the variable Workers should not have been assigned a concrete value. To fix this, download the modified library clpfd.pl from the course web page, place it in the same directory as your current source file, and replace :- use module(library(clpfd)) by :- use module(clpfd). Depending on your setup you might have to manually use the predi- cate cd/1 to navigate to your current directory. If you have previously loaded library(clpfd) then you might need to restart SWI-Prolog before consulting your file.
Exercise 5.2 Answer Set Programming
This exercise uses the DLV system, which incorporates the stable model se- mantics in the context of disjunctive logic programs. Follow the following steps to install the system in the laboratory environment (to install DLV on your personal computer, follow the instructions at http://www.dlvsystem. com/dlv/).
1. Download the file dlv at the course web page.
2. Move dlv to a location of your choice and make it your current direc-
tory.
3. Make dlv executable by the command chmod a+x dlv.
4. Generate all stable models via the command ./dlv fileName where fileName is the name of your input file.
Emacs has no built-in support for DLV, or any other ASP solver, but one can achieve (almost correct) syntax highlighting by enabling prolog-mode.
For further information on how to use DLV, accompanied by example programs, see the tutorial at http://www.dlvsystem.com/html/The_DLV_ Tutorial.html.
22 CHAPTER 3. Warm-Up
Consider the following DLV program.
man(dilbert).
man(wally).
bachelor(X) :- man(X), not husband(X).
husband(X) :- man(X), not bachelor(X).
LAB EXERCISES
Which consequences can one draw from the above program? Save the above program in a file dilbert.dl, generate all stable models via the com- mand ./dlv dilbert.dl, and compare the result to your expected outcome. For this exercise it is sufficient to explain your reasoning when demonstrating the rest of the lab assignment to your assistant.
Finding Cliques
Generate and test is an influential method for solving computationally hard problems with ASP solvers. In this method a fragment of the program de- scribes a class of models, further conditions discard some of them. For ex- ample, consider the following program which computes all 3-colourings1 of an undirected graph by associating 3-colourings with stable models.
colour(X, red) :-
node(X), not colour(X, green), not colour(X, blue).
colour(X, green) :-
node(X), not colour(X, red), not colour(X, blue).
colour(X, blue) :-
node(X), not colour(X, red), not colour(X, green).
:- edge(X, Y), colour(X, CommonColour), colour(Y, CommonColour).
Here, we assume that the program contains node/1 and edge/2 facts describing the symmetric input graph. The three colour/2 rules represent the “generate” part and state that each node X is red, green, or blue, and can only be assigned one of these three colours. The last rule, with an empty head, represents the “test”, and states that if there exist two nodes X and Y connected with an edge that are coloured with the same colour, then the empty head is true. Since we identify the empty head with falsity this implies that any interpretation which satisfies the body of the rule cannot
1By a 3-colouring of an undirected graph (V,E) with vertices V and edges E we mean a function from V to {red,green,blue} with the property that f(x) ̸= f(y) if {x,y} ∈ E.
LAB 5. CONSTRAINT AND ANSWER SET PROGRAMMING 23
be a stable model. Such rules are called integrity constraints and are used to remove undesired stable models.
Acliqueofsizekinanundirectedgraph(V,E)isasetC⊆V ofsizek such that x,y ∈ C, x ̸= y, implies that {x,y} ∈ E. In other words, it is a collection of k distinct vertices which are all adjacent. Write a DLV program where each stable model of the program corresponds to a clique of size at least 3, with respect to a symmetric input graph represented by node/1 and edge/2 facts.
Hint. The “test” part can be accomplished with a single integrity con- straint, and the generate part of the program can be accomplished by the following rules:
included(X) :- node(X), not excluded(X).
excluded(X) :- node(X), not included(X).
equal(X,X) :- node(X).
three_or_more :-
included(X),
included(Y),
included(Z),
not equal(X, Y),
not equal(Y, Z),
not equal(X, Z).
:- not three_or_more.
Test your program with the files graph small.dl and graph large.dl available on the course web page.