Assignment 9: Prolog
Due: 5:00pm, Friday, November 9. [Students scheduled to present November 12 or earlier, and any teammates of these students, have an assignment deadline of 5pm, November 19.] Value: 30 pts.
Create and submit a text file containing Prolog definitions of the predicates requested below.
Part A: unite
Write a unite
predicate where unite(A, B, U)
applies
for some U that holds every element found in A or B but
without any duplicates.
(It may assume that A and B do not contain duplicates.)
Below is a sample test illustrating a correct solution; but a correct solution might well find a different ordering instead, and it might find additional reorderings of the list.
?- unite([a,c,e], [b,d,c], X). X = [a, b, c, d, e] ; No
To do this, you'll likely find the built-in member
predicate useful; member(X, L)
applies whenever X
can be found in the list L.
You'll also likely find the NOT operator “\+
”
useful.
Both are illustrated by the below definition of all_unique
which applies to any list containing no duplicates.
all_unique([]).
all_unique([H | T]) :- \+ member(H, T), all_unique(T).
Part B: connect
![](maze0.png)
Say we have an adj
predicate that applies when two
locations in a maze are adjacent. The below example shows how to
define adj
for the maze illustrated at right.
edge(q00, q01). edge(q01, q11). edge(q10, q11). edge(q00, q10). edge(q10, q20).
edge(q02, q12).
edge(q21, q22).
adj(X, Y) :- edge(X, Y).
adj(X, Y) :- edge(Y, X).
Define a connect
predicate where connect(S, T, V)
applies whenever there is a route from S to T.
The final V is present simply to be a list tracking
locations visited earlier in the recursion;
this will help you to avoid infinite recursion.
?- connect(q01, q20, []). true? ; yes ?- connect(q01, q02, V). no
Using the Prolog interpreter
The gprolog command is freely available; it is already installed in the Linux lab. Once installed, you can start the interactive interpreter with the “gprolog” command.
You will want to compose some predicates of your own in a text file. Suppose, for example, that you have stored your solutions in a file named “soln.pl”. To load these predicates into the interpreter, you will first want to ensure you're in the same directory as the file, start gprolog, and then enter the filename enclosed in single quotes and brackets.
linux% cat soln.pl edge(q00, q01). edge(q01, q11). edge(q10, q11). edge(q00, q10). edge(q10, q20). edge(q02, q12). edge(q21, q22). adj(X, Y) :- edge(X, Y). adj(X, Y) :- edge(Y, X). linux% gprolog GNU Prolog 1.3.0 By Daniel Diaz Copyright (C) 1999-2007 Daniel Diaz | ?- ['soln.pl'].
If you later decide to edit the file, you do not need to exit gprolog but rather just re-execute the command to load the file.
After gprolog loads the file, you can then enter
queries at the interactive prompt. For example,
if the file contained the above definition of adj
defining the maze, we could enter a query to ask what locations
are adjacent to q00
.
| ?- adj(q00, X). X = q01 ? ; X = q10 ? ; no
The interpreter first responds with q01
as a
solution; after you type “;” to suggest that it
continue searching for solution, it responds with q10
as an alternative solution. A request to find more solutions
leads to the response of “no”.