Week 3

Reading

• An Introduction to Prolog Programming - Ulle Endriss
  • (Chapter 1, Chapter 2, Chapter 3)

Extra Reading (PhD Level)

• Answer Set Programming: A Primer — Eiter et al.
  • (Sections 7 and 8 are optional)

Slides

Exercises

Exercise 03.01: Open the Ciao playground and enter the family program:

parent(emma, magnus).
parent(emma, daniela).
parent(magnus, oscar).
parent(daniela, freja).

• Define grandparent(X, Y) and ask ?- grandparent(emma, X).
• Then ask ?- grandparent(X, freja). — note that you can query in both directions.

Exercise 03.02: Enter the graph program:

edge(a, b).
edge(b, c).

path(X, Y) :- edge(X, Y).
path(X, Z) :- edge(X, Y), path(Y, Z).

• Ask ?- path(a, X). and collect all solutions.
• Replace the second rule with path(X, Z) :- path(X, Y), edge(Y, Z). What happens, and why?

Exercise 03.03: Predict the answer to each query, then check it in Ciao:

?- X = 1 + 2.
?- X is 1 + 2.
?- 3 = 1 + 2.
?- f(X, b) = f(a, Y).
?- [H | T] = [1, 2, 3].
?- X = f(X).

What is the difference between = and is?

Exercise 03.04: Write a Datalog program that does not terminate when run with Prolog.

From now on, the Prolog programs you write should always terminate.

Exercise 03.05: The natural numbers are defined as:

nat(z).
nat(s(X)) :- nat(X).

Implement the following relations on natural numbers: +, -, *, <=, and min.

In the following exercises, use the representation of the natural numbers and the relations defined above.

Exercise 03.06: Use Prolog to determine whether each of the following equations and inequalities has a solution:

• x = 1 + 2
• x + 2 = 3
• x * x + 1 = 5
• x <= min(x, y)

where x and y are natural numbers, and the numerals abbreviate their Peano form (e.g. 2 abbreviates s(s(z))).

Exercise 03.07: Implement odd(X) and even(X) to determine whether a number is odd or even.

Exercise 03.08: Implement the Fibonacci function.

A list can be defined as:

list([]).
list([_ | Xs]) :- list(Xs).

For example, [1, 2, 3] is shorthand for [1 | [2 | [3 | []]]].

Exercise 03.09: Implement prefix(Xs, Ys) and suffix(Xs, Ys) to determine whether the list Xs is a prefix or suffix of Ys.

Exercise 03.10: Implement prefix and suffix in terms of append.

Exercise 03.11: Implement memberOf in terms of append.

Exercise 03.12: Implement two versions of reverse, one using append and one using an accumulator. Draw the proof trees produced by each on a small list.

Exercise 03.13: Implement substitute(A, B, Xs, Ys), which relates Xs to Ys such that every occurrence of A in Xs is replaced by B in Ys.

Exercise 03.14: A binary tree of natural numbers can be defined as:

tree(leaf).
tree(node(X, N, Y)) :- nat(N), tree(X), tree(Y).

• Define a predicate containsUnsorted(T, N) which determines whether the unsorted tree T contains the number N.
• Define a predicate containsSorted(T, N) which does the same for a sorted tree, visiting at most one subtree per node.
• Define predicates minHeight(T, N) and maxHeight(T, N) which relate T to the length of its shortest and longest path from the root to a leaf.
• Define a predicate sum(T, N) which relates T to the sum of its elements.
• Define predicates preOrder(T, Xs), inOrder(T, Xs), and postOrder(T, Xs) which relate T to the list Xs of its elements in that traversal order.

Exercise 03.15: The following definition of remove for lists is incorrect. Fix it:

remove(x, [], []).
remove(x, [x | ys], rs) :- remove(x, ys, rs). 
remove(x, [y | ys], rs) :- remove(x, ys, rs).

Exercise 03.16: For each pair of terms, manually compute a unifying substitution, or report if unification is impossible.

1. unify(42, 42)
2. unify(21, 42)
3. unify(X, 42)
4. unify(42, X)
5. unify(X, Y)
6. unify(X, X)
7. unify(leaf, leaf)
8. unify(X, node(X, 21, X))
9. unify(X, node(Y, 21, Z))
10. unify(node(leaf, X, leaf), node(leaf, 42, leaf))
11. unify(node(X, Y, leaf), node(leaf, Z, leaf))
12. unify(node(X, Y, X), node(node(leaf, 42, leaf), 21, leaf))
13. unify(node(X, Y, Z), node(node(leaf, 42, leaf), 21, Z))
14. unify([X], [1, 2, 3])
15. unify([X, Y, Z], [Z, X, Y])
16. unify([[X], Y], [Y, [2, 3]])
17. unify([X, Y], [1, [2, 3]])
18. unify([X, Y], [1, [X, 3]])
19. unify([X, [Y]], [1, [X, [Y]]])

Exercise 03.17: Describe why the occurs check is necessary in the unification algorithm.

Exercise 03.18: When would you use Datalog to solve a programming problem? And when would you use Prolog?