CSE 526: Principles of Programming Languages, Spring 2019

Homework #1

Due: Tue., Feb 18

This is a Prolog programming assignment. You are expected to write a Prolog program that consists of predicates described below. Unless otherwise specified, the solution to each question may have multiple Prolog predicates. You may also use the solution to one question to solve another question. Place all the Prolog predicate definitions you write to solve the following problems in a single file called hw1.P or hw1.p, depending on the Prolog system you used, and submit the file via Blackboard (hand-in procedure is described at the end of this handout).

Part A (Warm-Up):

order: Write a predicate order(L, X, Y) that succeeds if and only if elements X and Y occur in list L such that X occurs before Y. For instance:
- order([a,b,c,d], a, c), order([a,b,c,d],b,d), order([a,b,c,d],c,d), order([a,b,c,d], b,c) all succeed.
- order([a,b,c,d],d,b), order([a,b,c,d],a,e), order([a,b,c,d],a,a) all fail.
- order([a,b,c,d],X,Y) should give X=a, Y=b, and upon backtracking, the following answers:
  - X=a, Y=c
  - X=a, Y=d
  - X=b, Y=c
  - X=b, Y=d
  - ~~X=d, Y=d~~ X=c, Y=d
split: Write a predicate split(L, X, Pre, Succ) that succeeds if and only if element X occurs in list L, and Pre is a list of elements that occur before X in L, and Succ is a list of elements that occur after X in L. The order of elements in Pre and Succ are same as that in L. For instance:
- split([a,b,c,d], a, [], [b,c,d]), split([a,b,c,d],b,[a],[c,d]), split([a,b,c,d],c,[a,b], [d]), split([a,b,c,d],d,[a,b,c],[]) all succeed.
- split([a,b,c,d],d,[],[a,b,c]), split([a,b,c,d],e,[a,b,c,d],[]]), split([a,b,c,d],a,[b],[d]) all fail.
- split([a,b,c,d], X, L1, L2) should give X=a, L1=[], L2=[b,c,d], and upon backtracking, the following answers:
  - X=b, L1=[a], L2=[c,d]
  - X=c, L1=[a,b], L2=[d]
  - X=d, L1=[a,b,c], L2=[]
rotate: Write a predicate rotate(L1, L2) that succeeds if and only if list L1 is a rotation of list L2, i.e., if L1 = [x₁, x₂, x₃, ..., x_n], then L2 = [x_i, x_i+1, ..., x_n, x₁, x₂, ..., x_i-1] for some 1 ≤ i ≤ n For instance:
- rotate([a,b,c,d], [a,b,c,d]), rotate([a,b,c,d],[b,c,d,a]), rotate([a,b,c,d],[c,d,a,b]), rotate([a,b,c,d],[d,a,b,c]) all succeed.
- rotate([a,b,c,d],[a,b,d,c]), rotate([a,b,c,d],[a,d,c,b],[]]), rotate([a,b,c,d],[a,b,b,a]) all fail.
- rotate([a,b,c,d], L2) should give L2=[a,b,c,d], and upon backtracking, the following answers:
  - L2=[b,c,d,a]
  - L2=[c,d,a,b]
  - L2=[d,a,b,c]
Part B (Trees):
For the following five questions, consider using Prolog terms to represent binary trees as follows:
- empty represents an empty tree
- node(V, T₁, T₂), represents a tree with value V at the root, and T₁ and T₂ as the first (left) and second (right) sub-trees.
(a) (b) (c)

For instance,
- Tree (a) in the picture above is represented by term node(5, node(3, node(1, empty, empty), node(2, empty, empty)), node(13, empty, node(8, empty, empty))).
- Tree (b) in the picture above is represented by term node(8, node(2, node(1, empty, empty), node(5, node(3, empty, empty), empty)), node(13, empty, node(21, empty, empty))).
- ~~Tree (c) in the picture above is represented by term node(5, node(3, node(1, empty, empty), node(2, empty, empty)), node(13, node(8, empty, empty), empty)).~~
- Tree (c) in the picture above is represented by term node(5, node(2, node(1, empty, empty), node(3, empty, empty)), node(13, node(8, empty, empty), empty)).
isTree: Write a predicate isTree(T) that succeeds if and only if T is a binary tree.
Clearly, the predicate isTree should succeed for the example term for tree(a) given above. isTree will fail for node(3, 1, 5), node(1, emty, empty), and node(2, node(1, empty), empty).
balanced: Write a predicate balanced(T) that succeeds if and only if T is a binary tree that is height-balanced: i.e., the lengths of the longest root-to-leaf path and the shortest root-to-leaf path differ by at most one.
For example, trees (a) and (c) in the picture above are balanced.
ordered: Write a predicate ordered(T) that succeeds if and only if an in-order traversal of T spells out an increasing sequence of values. For this part, you may assume that all values in T are comparable with "<".
Note: In-order traversal of a tree traverses, at each level, the left subtree, the root, and then the right subtree.
For example, trees (b) and (c) in the above picture are ordered.
build: Write a predicate build(L, T), that, given a list L constructs a tree T such that an in-order traversal of T spells out L.
For example, build([1,2,3,5,8,13,21], T) can give, as T tree (b) in the picture above, as one possible answer.
build_balanced: Write a predicate build(L, T), that, given a list L constructs a balanced tree T such that an in-order traversal of T spells out L.
For example, build_balanced([1,2,3,5,8,13], T) can give, as T tree (c) in the picture above, as one possible answer.

Grading:

There are 8 questions in all, worth 5 points each. Note: not all questions are equally hard, but they are all worth the same number of points.

Submission:

Submit your homework via Blackboard. In "Assignments" area there you will see a form for HW1. Fill it out by uploading the file containing your Prolog program.

The file must be named hw1.P or hw1.p

Make sure you submit the form.

Errata:

Earlier versions had the following errors that have since been corrected:

Mon Feb 10 19:21:18 EST 2020: Examples in Q1 and Q3 had minor errors that have been fixed now.
Wed Feb 12 20:13:57 EST 2020: Examples before Q4, the representation of Tree (c) had an error that's now fixed.

C.R. Ramakrishnan
Last modified: Wed Feb 12 20:13:57 EST 2020


(a)	(b)	(c)