SAMPLE QUESTIONS for Prolog Exam
Note: There is a unification question in this file. You are
responsible for the kinds of simple pattern-matching that is
employed in Prolog's rule invocation process. E.g., you should
easily know that f([X | Y], 7) matches f([a,b,c], W) with
binding {a/X, [b,c]/Y, 7/W}.
I. Consider the following Prolog program: (The rules are num-
bered for your convenience in referring to them.)
[1] a :- b, c, d.
[2] b.
[3] c :- b, e.
[4] c :- b, f.
[5] d.
[6] f.
Suppose we give to Prolog the following one-goal list to solve:
| ?- a.
[a] Beginning with the initial goal list above, indicate
after each goal list the number of the next rule used.
Then write the new goal list that would result from the
application of that rule. If, at a certain point, no
rule is applicable to the goal list, then indicate so -
the next goal list should then be the one that results
from backtracking to the previous state. (Notice that
there are no variables and thus no bindings to keep
track of here.)
[b] BRIEFLY state what would happen in part [a] if rule [4]
were changed to:
[4] c :- b, a.
[c] BRIEFLY state what would happen in part [a] if rule [1]
were changed to:
[1] a :- b, c, !, d.
II. Give Prolog rules for checking the length of a list of
items. (There is no restriction on what a list item
may be.) For example, if presented with the goal
| ?- length([a, b, c], 3). Prolog would respond with:
yes whereas
?- length([a, b], 3). would result in:
no
You may assume that the first argument of "length" in
the original goal does not involve partially unspeci-
fied lists like "[a, b | Rest]", and that the second
argument is a non-negative integer.
III. Consider the following Prolog program:
[1] parent(john, sally).
[2] parent(jim, mike).
[3] parent(carol, john).
[4] parent(carol, sue).
[5] parent(sally, jim).
[6] parent(jim, bob).
[7] sibling(X, Y) :- parent(Z, Y), parent(Z, X), X \== Y.
[8] malelist([john, jim, mike, bob]).
[9] femalelist([sally, carol, sue]).
[10] mother(U, V) :- parent(U, V), female(U).
[11] father(U, V) :- parent(U, V), male(U).
[12] brother(U, V) :- sibling(U, V), male(U).
[13] sister(U, V) :- sibling(U, V), female(u).
Show what happens in solving the goal below. You may
assume (for now) that goals of the form "male(X)." or
"female(X)." become appropriately solved. Show the rule
applied, the goal list, and the variable bindings after
each application of a rule or fact (or, for instance,
after solving a `male(X).' goal). Indicate backtrack-
ing should any be required.
| ?- brother(X, mike).
Give one or more Prolog rules for solving goals like
"male(X)." when added to the previous 13 rules. Obviously,
one or more similar rules for goals like "female(X)." should
be easy to compose and are not required.
UNIFICATION QUESTION
---------------------
IV. Does the goal "ohwell(X, a(b,c), g(W, [H | T]))" match
(i.e., unify with)
[1] V
[2] [XH | XT]
[3] ohwell(V)
[4] ohwell([V | V1])
[5] ohwell(X, a(b,c), g(W, [H | T]))
[6] oh(X, a(b,c), g(W, [H | T]))
[7] ohwell(r(b,c,s), a(G,H), g(wer, [GG]))
[8] ohwell(r(b,QQ,E), fb(G,H), G)
[9] ohwell(X1, X2, g(234, []))
In each case where the answer is yes, give the FINAL binding
for each variable that, when applied to each expression,
unifies them. For example, if we try to match gg(a, X,
f(X,b)) with gg(Y, Y, W), we succeed with final binding
{a/Y, a/X, f(a,b)/W}, but NOT with the binding {a/Y, Y/X,
f(X,b)/W} which, if applied SEQUENTIALLY, would yield the
correct result. You are to specify as a final binding, one
that produces the correct result when applied SIMULTANE-
OUSLY, not sequentially.
V.
Suppose that we represent sets as lists in Prolog. So the
set {a,b,c} would be represented as [a, b, c]. Now assume we
have a list in which there may be repeats, [a,d,a,c,g,c] e.g.
Therefore, this list cannot be a set.
Compose Prolog rules to convert such a list to one which correctly
represents the set of the list elements, {a,d,c,g}. By submitting
the goal "setify([a,d,a,c,g,c], S)." we would expect Prolog to
say yes with binding S = [a,d,c,g].
VI.
Compose Prolog rule(s) for computing Fibonacci(n), the n-th Fibonacci
number. Recall that Fibonacci(0) = Fibonacci(1) = 1, and
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2).
[a]
Do this in the most straightforward way you can. Your rules are likely
to mimic the standard recursive definition given above and require a
large (exponential) amount of computation. This is fine for part [a].
The goal "fib(5, N)" should succeed with N=8. You may assume that
the first argument is supplied as a non-negative integer.
[b]
Now redefine the rules so that they compute Fibonacci(n) iteratively,
much in the way that an ordinary loop in Pascal or C would.
(Hint: Recall the "fast" rules for the factorial function.)
********************** ANSWERS ***********************
I. part a
| ?- a. [1]
b, c, d. [2]
c, d. [3]
b, e, d. [2]
e, d. fail, no applicable rule backtrack to -->
b, e, d. fail, no (additional) applicable rule backtrack to -->
c, d. [4]
b, f, d. [2]
f, d. [6]
d. [5]
<empty> SUCCESS
part b: Infinite recursion. Applying rule 4 reintroduces "a" as a subgoal.
part c: The result is unchanged, and the search is essentially the same.
| ?- a. [1]
b, c, !, d. [2]
c, !, d. [3]
b, e, !, d. [2]
e, !, d. fail, no applicable rule backtrack to -->
b, e, !, d. fail, no (additional) applicable rule backtrack to -->
c, !, d. [4]
b, f, !, d. [2]
f, !, d. [6]
!, d. [!] (choice of [1] on a,
choice of [2] on b in line 2,
choice of [4] on c in line 7, FROZEN)
d. [5]
<empty> SUCCESS
II. length([], 0).
length([H | T], N) :- M is N-1, length(T, M).
The program above will only CHECK lengths. The one below will COMPUTE them,
but only if the lists have finite lengths, i.e., no unspecified tails.
length([], 0).
length([H | T], N) :- length(T, M), N is M+1.
III. first part
| ?- brother(X, mike). [12] {X/U1, mike/V1}
sibling(X, mike), male(X). [7] {X/X2, mike/Y2}
parent(Z2, mike), parent(Z2, X), X\==mike, male(X). [2] {jim/Z2}
parent(jim, X), X\==mike, male(X). [2] {mike/X}
mike\==mike, male(mike). fail "\==" built in backtrack to -->
parent(jim, X), X\==mike, male(X). [6] {bob/X}
bob\==mike, male(bob). "\==" built in
male(bob). (rules for male)
<empty> SUCCESS (with X = bob)
second part
male(X) :- malelist(L), member(X, L).
member(X, [X | L]).
member(X, [H | T]) :- member(X, T).
IV.
[1] yes, with binding { ohwell(X, a(b,c), g(W, [H | T])) / V }
[2] no
[3] no
[4] no
[5] yes, the binding is simple but tricky:
Note that variables in different goals are always local -
so if we give the variables of [5] an index of 5,
the binding would be {X/X5, W/W5, H/H5, T/T5},
( or {X5/X, W5/W, H5/H, T5/T} )
[6] no ("oh" can't match "ohwell")
[7] yes, note that the variable H appears in both the goals we
therfore replace H by H1 in [7]. The binding is
{r(b,c,s)/X, b/G, c/H1, wer/W, H/GG, []/T}
[8] no ("fb" can't match "a")
[9] no ( [] can't match [H | T] )
V. (Well, you shouldn't be given ALL the answers. Work on this one.)
OK, here's the answer:
setify([X], [X]) :- !.
setify([X | Y], W) :- member(X, Y), !, setify(Y, W).
setify([X | Y], [X | W]) :- setify(Y, W).
member(X, [X | Y]) :- !.
member(X, [W | Y]) :- member(X, Y).
% Here are some other set operations:
union([], X, X) :- !.
union([X | Y], Z, W) :- member(X, Z), !, union(Y, Z, W).
union([X | Y], Z, [X | W]) :- union(Y, Z, W).
intersect([], X, []) :- !.
intersect([X | Y], Z, [X | W]) :- member(X, Z), !, intersect(Y, Z, W).
intersect([X | Y], Z, W) :- intersect(Y, Z, W).
VI. [a]
fib(0, 1).
fib(1, 1).
fib(N, R) :- N1 is N-1, N2 is N-2, fib(N1, R1), fib(N2, R2), R is R1 + R2.
[b]
fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, FIB) :- fastfib(0, 1, 1, 1, N, FIB).
fastfib(N2, F2, N1, F1, N1, F1) :- !.
fastfib(N2, F2, N1, F1, N, FIB) :-
NewF is F2+F1,
NewN is N1+1,
fastfib(N1, F1, NewN, NewF, N, FIB).