Logic Languages

Prev: Functional Languages Next: Concurrency

12.1-12.2 Check Your Understanding

1. What mathematical formalism underlies logic programming?
2. What is a Horn clause?
3. Briefly describe the process of resolution in logic programming.
4. What is a unification? Why is it important in logic programming?
5. What are clauses, terms, and structures in Prolog? What are facts, rules, and queries?
6. Explain how Prolog differs from imperative languages in its handling of arithmetic.
7. Describe the difference between forward chaining and backward chaining. Which is used in Prolog by default?
8. Describe the Prolog search strategy. Discuss backtracking and the instantiation of variables.

12.2.6-12.4 Check Your Understanding

9. Explain the purpose of the cut (!) in Prolog. How does it relate to \+?
10. Describe three ways in which Prolog programs can depart from a pure logic programming model.
11. Describe the generate-and-test programming idiom.
12. Summarize Prolog’s facilities for database manipulation. Be sure to mention assert, retract, and clause.
13. What sorts of logical statements cannot be captured in Horn clauses?
14. What is the closed world assumption? What problems does it cause for logic programming?

12.6 Exercises

1. Starting with the clauses at the beginning of Example 12.17, use resolution, as illustrated in Example 12.3, to show, in two different ways, that there is a path from a to e.
2. Solve Exercise 6.22 in Prolog.
3. Consider the Prolog gcd program in Figure 1.2. Does this program work “backward” as well as forward? Given integers d and n, can you use it to generate a sequence of integers m such that gcd(n, m) = d? Explain your answer.
4. In the spirit of Example 11.20, write a Prolog program that exploits backtracking to simulate the execution of a nondeterministic finite automaton.
5. Show that resolution is commutative and associative. Specifically, if A, B, and C are Horn clauses, show that (A ⊕ B) = (B ⊕ A) and that ((A ⊕ B) ⊕ C) = (A ⊕ (B ⊕ C)), where ⊕ indicates resolution. Be sure to think about what happens to variables that are instantiated as a result of unification.
6. In Example 12.8, the query ?- classmates(jane_doe, X) will succeed three times: twice with X = jane_doe and once with X = ajit_chandra. Show how to modify the classmates(X, Y) rule so that a student is not considered a classmate of himself or herself.
7. Modify Example 12.17 so that the goal path(X, Y), for arbitrary already-instantiated X and Y, will succeed no more than once, even if there are multiple paths from X to Y.
8. Using only \+ and no cuts, modify the tic-tac-toe example of Section 12.2.5 so it will generate only one candidate move from a given board position. How does your solution compare to the cut-based one in Example 12.22?
9. Prove the claim, made in Example 12.19, that there is no winning strategy in tic-tac-toe, that either player can force a draw.
10. Prove that the tic-tac-toe strategy of Example 12.19 is optimal, wins against an imperfect opponent whenever possible, draws otherwise, or give a counterexample.
11. Starting with the tic-tac-toe program of Figure 12.4, draw a directed acyclic graph in which every clause is a node and an arc from A to B indicates that it is important, either for correctness or efficiency, that A come before B in the program. Do not draw any other arcs. Any topological sort of your graph should constitute an equally efficient version of the program. Is the existing program one of them?
12. Write Prolog rules to define a version of the member predicate that will generate all members of a list during backtracking, but without generating duplicates. Note that the cut- and \+-based versions of Example 12.20 will not suffice; when asked to look for an uninstantiated member, they find only the head of the list.
13. Use the clause predicate of Prolog to implement the call predicate, pretending that it is not built in. You needn’t implement all of the built-in predicates of Prolog; in particular, you may ignore the various imperative control-flow mechanisms and database manipulators. Extend your code by making the database an explicit argument to call, effectively producing a metacircular interpreter.
14. Use the clause predicate of Prolog to write a predicate call_bfs that attempts to satisfy goals breadth-first. Hint: You will want to keep a queue of yet-to-be-pursued subgoals, each of which is represented by a stack that captures backtracking alternatives.
15. Write a list-based insertion sort algorithm in Prolog. Here’s what it looks like in C, using arrays:

void insertion_sort(int A[], int N)
{
    int i, j, t;
    for (i = 1; i < N; i++) {
        t = A[i];
        for (j = i; j > 0; j--) {
            if (t >= A[j-1]) break;
            A[j] = A[j-1];
        }
        A[j] = t;
    }
}

16. Quicksort works well for large lists, but has higher overhead than insertion sort for short lists. Write a sort algorithm in Prolog that uses quicksort initially, but switches to insertion sort, as defined in the previous exercise, for sublists of 15 or fewer elements. Hint: You can count the number of elements during the partition operation.
17. Write a Prolog sorting routine that is guaranteed to take O(n log n) time in the worst case. Hint: Try merge sort; a description can be found in almost any algorithms or data structures text.
18. Consider the following interaction with a Prolog interpreter:

?- Y = X, X = foo(X).
Y = foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(
foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(
foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(
foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(
foo(foo(foo(foo(foo(foo(...

What is going on here? Why does the interpreter fall into an infinite loop? Can you think of any circumstances, presumably not requiring output, in which a structure like this one would be useful? If not, can you suggest how a Prolog interpreter might implement checks to forbid its creation? How expensive would those checks be? Would the cost in your opinion be justified? 19. 12.19-12.21 In More Depth.