CSC 550/650: Assignment 2

Relations & Prolog Programs

This assignment involves writing and reasoning with numerous Prolog programs. As part of the documentation for your code, you should include a short English description of each relation that you define. These descriptions should concentrate on the declarative content of each relation (i.e. on what is being defined), rather than on the procedural aspects (i.e. on how it "works").

Your aim in solving these problems should be first to produce the clearest possible solution and only second to make the solution efficient. Solutions for each problem must be clearly separated out. Programs that are difficult to read or understand will be penalized.

  1. Consider the following Prolog program, which defines relations between cities (similar to the example discussed in class). Trace by hand the sequence of resolution steps involved in solving the query ?- connected(X,X). That is, show the list of goals at each step in the Prolog resolution, noting any bindings that occur and also any backtracking that takes place. See the lecture notes for similar examples tracing queries about family relations. road(a, b). road(b, c). road(b, a). road(c, d). connected(City1, City2) :- road(City1, City2). connected(City1, City2) :- road(City1, City3), connected(City3, City2).
  2. Write Prolog facts and/or rules to define the relation sum_range(Low, High, Sum), where Sum is the sum of all the integers between Low and High, inclusive. If Low > High, the Sum is assumed to be 0. For example: ?- sum_range(1, 100, Sum). ?- sum_range(5, 3, Sum). Sum = 5050 Sum = 0 Yes Yes

    Hint: to compute the sum from Low to High, recursively compute the sum from Low+1 to High and then add Low. Be sure that your relation does not produce incorrect answers on backtracking (e.g., if the user hits a semi-colon).

  3. As suggested by several examples from the lectures, one possible use of Prolog is in providing an intelligent front-end to a database. Assume that you are given a set of Prolog facts of the following form, describing courses offered at Creighton. course(Name, loc(Bldg,Room), time(Day,StartHour:StartMin,EndHour:EndMin), instr(FirsName,LastName)). where : is a standard Prolog operator. For instance, the courses taught by Dr. Reed in Spring 2002 could be described using the facts: course(csc107,loc(old_gym,411),time(tue,14:00,15:15),instr(dave,reed)). course(csc107,loc(old_gym,411),time(thu,14:00,15:15),instr(dave,reed)). course(csc551,loc(old_gym,411),time(mon,15:30,16:45),instr(dave,reed)). course(csc551,loc(old_gym,411),time(wed,15:30,16:45),instr(dave,reed)). course(csc550,loc(old_gym,411),time(tue,17:00,19:45),instr(dave,reed)). course(csc650,loc(old_gym,411),time(tue,17:00,19:45),instr(dave,reed)). Your task is to build a simple interface to this database by writing Prolog facts and/or rules to define the following relations:

  4. A (labeled) binary tree is a recursive structure that is either (1) empty, or else (2) consists of a labeled root, a left subtree, and a right subtree. Similar to lists, trees are amenable to representation in the predicate calculus. For example, we may represent an empty tree by the constant void, and a non-empty tree by the term tree(Root,Left,Right) where Root is the label of the root and Left and Right are representations of the left and right subtrees, respectively. Thus the tree with root a and leaves b and c would be represented by the term tree(a,tree(b,void,void),tree(c,void,void)).

  5. Consider the IQ test analogy reasoner described in class, which can be copied from online. You are to modify/extend this program in the following ways:

    You are certainly free (and encouraged) to add more to this program to make it even more powerful/interesting.


  1. Trees are often used to store sorted information for quick retrieval. Thus, it is necessary to be able to traverse a tree systematically and list all of the information stored there. Using the same tree representation as in Exercise 4, write Prolog facts and/or rules to define three different relations between trees and their traversals: (1) pre-order traversal, where the root is listed first, followed by the pre-order listings of the left and right subtrees; (2) in-order traversal, where the root of a tree comes after the in-order listing of the left subtree, but before the in-order listing of the right subtree; and (3) post-order traversal, where the root is listed after the post-order listings of the left and right subtrees. For example, ?- pre_traverse(tree(a,tree(b,void,void),tree(c,void,void)),Pre). Pre = [a,b,c] Yes ?- in_traverse(tree(a,tree(b,void,void),tree(c,void,void)),In). In = [b,a,c] Yes ?- post_traverse(tree(a,tree(b,void,void),tree(c,void,void)),Post). Post = [b,c,a] Yes
  2. A prefix of a list L is any initial segment of L, while a suffix is a final segment of L. Thus, if L is [1,2,3], the prefixes of L are [1], [1,2] and [1,2,3], while the suffixes of L are [1,2,3], [2,3], and [3]. For our purposes, we will not consider the empty list to be a prefix or suffix. Write Prolog facts and/or rules to define the following relations.

    Do not use append in defining prefix, suffix, or sublist.