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

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