COMP 590-096 Fall 2010

Assignment 3: Logic programming

Due date: Monday, November 22, 11:59 PM

Submission Instructions

The goal of this assignment is to implement a very basic Prolog interpreter and apply it to several logic programs. You will need to turn in the following:

  1. A report in PDF or Word Document format. The report should describe your implementation, including pseudocode or figures if necessary for understanding what you did. As in the previous assignment, your report should focus on the most "interesting" aspects of your solution, i.e., any non-obvious implementation choices and what you had to do to get the interpreter to work. Your report should be self-contained and it should make it possible for us to evaluate your solution without having to run your source code. Please don't forget to include in your report all the results that are requested in the individual problem instructions below. You will not get credit for results not included in the report.

    The name of the report file should be lastname_firstname_assignment3.pdf or lastname_firstname_assignment3.doc.

  2. Your source code and execution traces (see below for instructions) compressed to a single ZIP file. As before, your code should be well commented, and it should be easy to see the correspondence between what's in the code and what's in the report. You don't need to include executables or various supporting files (e.g., utility libraries) whose content is irrelevant to the assignment. If we find it necessary to run your code in order to evaluate your solution, we will get in touch with you.

    The name of the code archive should be lastname_firstname_assignment3.zip.
Submit your report and code files through Blackboard using the same instructions as in Assignment 1.

Late policy: You lose 25% of the points for every day the assignment is late. If you have a compelling reason for not being able to submit the assignment on time and would like to make a special arrangement, you must let me know ahead of the due date.

Policy on outside sources: Feel free to consult the Web in order to learn more about Prolog and to see examples of Prolog programs or advice on implementing a Prolog interpreter. However, DO NOT submit somebody else's code wholesale as your own work. As usual, whenever you use outside code or references, please be sure to acknowledge them in your report.

Assignment Instructions

As stated above, the goal of this assignment is to implement an interpreter with backward chaining inference for a bare-bones subset of Prolog (see this lecture and Chapter 9 of the textbook for an introduction). Here is an example of the kind of input your interpreter should be able to handle:

Program (KB):
evil(X) :- king(X), greedy(X).
king(john).
greedy(Y).

Query:
evil(john).

The following is a more detailed description of the language syntax:

  • The program consists of clauses and atomic sentences. Each clause has the format

    head_pred(head_arg_list) :- pred_1(arg_list_1), ..., pred_n(arg_list_n).

    and each atomic sentence has the format

    pred(arg_list).

    Each arg_list is a comma-separated list of constants, variables, or lists (see below for details).

  • We will use the convention that variable names start with uppercase letters (X, Y11, Z222, etc.), while predicate names and constants are lowercase strings (king, john, etc.).

  • A list is enclosed in square brackets and the elements are separated by commas. For simplicity, we will assume that list elements can only be numbers, e.g., [1,2,3,4]. The empty list is denoted []. A single-element list is denoted [H]. A list with first element H and tail T is denoted by [H|T]. For example, if you're trying to unify [1,2,3,4] with [H|T], then H = 1 and T = [2,3,4].

Detailed Implementation Instructions

  • Your interpreter should begin by reading in the program from a file or command line, parsing it, and storing it into a KB data structure. Then it should read in each query in turn, parse it, run backward chaining to find all the answers, and display them at the output. See this file and this file for example traces of queries from Program 1 and Program 3 below.

  • Your first step should be to write a parser for Prolog clauses. Use whatever data structures you see fit. Please note that your parser does not need to be robust to syntax errors. That is, you can assume that every sentence given to your interpreter is well-formed. You can even make restrictive assumptions about the format of the strings down to the number of spaces between predicates and arguments, if it makes your life easier. There is no need to implement any features of Prolog not present in the following programs.

  • For the overall structure of the backward chaining algorithm, follow the pseudocode from the lecture notes.

  • Standardizing apart: when you take a rule from the KB and want to apply it to one of your goals, you need to standardize it apart, or rename all the variables to previously unused names. For example, if you want to prove evil(john), you would take the rule evil(X) :- king(X), greedy(X) and standardize it apart by renaming the variable X into, say, X1, to get evil(X1) :- king(X1), greedy(X1) The simplest way of generating new variable names is to keep a numeric global "index" variable. Every time you take a new rule from the KB, you would append that index to its variable names, and increment it for next time.

  • Unification: In order to apply a rule from the KB to one of your goals, you need to unify that rule with the goal, or generate a substitution of variables that makes the rule and the goal the same. To implement unification, you can follow the pseudocode given in Figure 9.1 of the textbook (p. 328 in the 3rd edition and p. 278 in the 2nd edition). However, keep in mind that you do not need to implement a fully general unification routine. In particular, you do not need to include the Occur-Check (in fact, most Prolog interpreters omit it).

  • Substitution: When applying a substitution to a goal, you should be able to deal with composition. For example, a substitution may look someting like X = [H1|L1], H1 = 1, L1 = [H2|L2], H2 = 2, L2 = [H3|L3], H3 = 3, L3 = []. Your substitution routine should be able to figure out that X = [1,2,3].

General Suggestions

  • To get a better understanding of backward chaning, unification, and substitution, you may want to manually work through a few simple examples, like Program 1 below.

  • Most of your effort will go not into implementing backward chaining, but into the various subroutines, including parsing, substitution, and unification. Implementing these operations may be bug-prone, so you should take care, give yourself plenty of time, and approach debugging systematically.

  • To help with debugging, you should tackle the programs in the order listed below. Make sure you get the correct answer to the simpler programs before moving on to the more complex ones. For example, begin by implementing an interpreter without list functionality and get it to run on programs 1 and 2 before tacking program 3.

  • Don't be afraid of recursion!

Programs

Test your interpreter on each of the following programs by executing each query in turn. For each query, include in your report all the answers returned by your program. In the zip file, include complete traces of your program for every query following the examples in this file and this file. In particular, the trace should show every recursive call to the backwards chaining routine, every successful unification and the resulting substitution, and every answer (substitution) found. Feel free to add your own queries and expand the programs.

Program 1

This is the simple program from the lecture notes to help you debug.

parent(abraham,ishmael).
parent(abraham,isaac).
parent(isaac,esau).
parent(isaac,jacob).
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
descendant(X,Y) :- parent(Y,X).
descendant(X,Y) :- parent(Z,X), descendant(Z,Y).

Queries:

parent(isaac,X).
parent(X,abraham).
grandparent(X,Y).
descendant(X,Y).
grandparent(X,Y), descendant(X,Y).

Example output:

? parent(isaac,X).
yes
X = esau
X = jacob

? parent(X,abraham).
no

See this file for a sample trace of the query grandparent(X,Y).

Program 2: Graph coloring

This is the Australia problem:

colorable(Wa,Nt,Sa,Q,Nsw,V) :- diff(Wa,Nt), diff(Wa,Sa), diff(Nt,Q), diff(Nt,Sa), diff(Q,Nsw), diff(Q,Sa), diff(Nsw,V), diff(Nsw,Sa), diff(V,Sa).
diff(red,blue).
diff(red,green).
diff(green,red).
diff(green,blue).
diff(blue,red).
diff(blue,green).

Query:

colorable(Wa,Nt,Sa,Q,Nsw,V).

Be sure to find and display all the solutions to the query.

Program 3: Lists and Sets

This problem requires you to implement list functionality for your interpreter. The append function below was discussed in the lecture notes. Also, see this file for a sample trace of the query append([1,2,3],[4,5,6],X).

append([],Y,Y).
append([X|L],Y,[X|Z]) :- append(L,Y,Z).
union([],X,X).
union([X|R],Y,Z) :- member(X,Y), union(R,Y,Z).
union([X|R],Y,[X|Z]) :- union(R,Y,Z).
foo(X,L,[X|L]).
foo(X,[L|H],[L|R]) :- foo(X,H,R).
bar([],[]).
bar([L|H],R) :- bar(H,R1), foo(L,R1,R).

To complete the above program, you should write the definitions for the following functions yourself (and include these definitions in your report):

  • member(X,Y): this function should give the answer "yes" if element X is a member of list Y.
  • reverse(X,Y): X is the input, and Y is the output (reversed list). For example, reverse([1,2,3,4],Y) should give the answer Y = [4,3,2,1].
  • intersect(X,Y,Z): Z should be the result of intersecting lists X and Y.

Queries:

append([1,2,3],[4,5,6],X).
append([1,2,3],X,[1,2,3,4,5,6]).
append(X,Y,[1,2,3,4]).
member(4,[1,2,3,4]).
member(3,[1,2,4]).
member(X,[1,2,3,4]).
reverse([1,2,3,4],[3,4,2,1]).
reverse([1,2,3,4],R).
foo(1,[2,3,4],X).
bar([1,2,3,4],X).
union([1,2],[3,4],X).
union([1,2],[1,2,3,4],X).
intersect([1,2,3,4],[5,1,3,6],X).

 In your report, be sure to explain what the functions foo and bar do (and how they do it), and why the union and intersect queries produce the results that they do.

Program 4

Write your own program and your own queries. Try to push the limits of your interpreter by giving it more and more complex queries. For this part, you can use snippets of Prolog code found on the Web (but be sure to cite your sources).

Extra Credit

Research and implement additional Prolog functionality not listed above, for example, arithmetic operations, negation, or cuts. As before, the amount of credit you will receive will vary based on the amount of extra work you did and on the thoroughness of your discussion/analysis. If you implement anything for extra credit, please be sure to include a clearly marked "Extra Credit" section in your report.