Assignment 4: Declarative Programming Solution

1 Introduction
In this assignment, you will gain experience in Prolog and ML, two representative programming languages for logic programming and functional programming respectively.
2 Logic Programming
Answer Q1 and Q2 in a Prolog program with the file name assg4.pl. Your program will be graded in “SICStus Prolog 3.12.7” in the CSE Unix platform (command “sics”). The queries should be written in comments. For each code segment and query, you should clearly indicate with comments its corresponding question number.
1. Recall the successor notation for representing natural numbers, and the sum(X,Y,Z) relation defined in the lecture, which is true if Z is the sum of X and Y.
(a) Based on sum/3, define product(X,Y,Z) which is true if Z is the product of X and Y.
(b) Give the query to compute the product of 3 and 4.
(c) Give the query to compute the result of 8 divided by 4.
(d) Give the query to find the factors of 6.
(e) Based on product/3, define exp(X,Y,Z) which is true if Z is the result of X raised to the power Y (i.e., XY = Z).
(f) Give the query to compute 23.
(g) Give the query to compute log2 8.
2. A finite automaton (or finite state machine/automaton) is a collection of finitely many states and transitions between states due to finitely many different kinds of input. States are usually represented by circles and transitions by arrows between state circles. For the purpose of this question, states are labeled with the English alphabet and inputs are labeled by natural numbers.
Figure 1 gives an example automaton. In the example, say if we start in state “c” and give the input string “01111”, then we end up in state “a”.
If we consider only states that are involved in one or more transitions (that is, there would not be isolated states), then we can represent an automaton by some Prolog facts of the form transition(F,X,T), where F and T are the “from” and “to” states of the transition
respectively and X is the symbol triggering the transition.
(a) Encode the automaton in Figure 1 with some transition(F,X,T) facts.
c
b
a
0 0
0
1
1
1
Figure 1: An Example Finite Automaton
(b) Define a Prolog relation state(N), which is true if N is a state in the automaton defined in the transition/3 facts.
(c) Define a Prolog relation walk(S,B,E), which is true if we can go from state B to state E with input sequence S in the form of a list. (For example, using the automaton in Figure 1, walk([0,1,1,1,1],c,a) should be true.)
Your program should at least work correctly on the example automaton in Figure 1. Besides, we shall test your program using other automata.
3 Functional Programming
Answer Q3 and Q4 in an ML program with the file name assg4.ml. Your program will be graded in “Standard ML of New Jersey 110.0.7” in the CSE Unix platform (command “sml”). For each code segment, you should clearly indicate with comments its corresponding question number.
3. Recall the (slightly re-worded) type definition of a binary tree in the lecture:
datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree;
where “nil” stands for the empty tree and “bt” is the tag of a non-empty binary tree. The following is an example of an int bTree:
bt(bt(nil,74,nil),
105,
bt(bt(nil,109,nil),
109,
bt(nil,121,nil)
)
)
(a) An inorder traversal of a binary tree traverses the left subtree, then the root and lastly the right subtree recursively. For example, an inorder traversal of the example tree above should visit the nodes in the order: 74, 105, 109, 109, and 121. Write an ML function inorder that accepts a binary tree and returns a list of all the elements of the tree in the order of inorder traversal.
(b) Write a similar ML function preorder that produces a list of elements visited in a preorder traversal, which visits the root before traversing the left and then right subtrees.
(c) Write a similar ML function postorder that produces a list of elements visited in a postorder traversal, which visits the root only after traversing the left and then right subtrees.
Your functions should all use pattern matching.
4. This question is about list processing.
(a) Write an ML function symmetric that takes an integer 𝑖, an integer 𝑛, and a list of length 𝑛 where 1≤𝑖≤𝑛, and check whether the 𝑖th element of the list is identical to the (𝑛+1−𝑖)th element. That is, given a list [𝑎1,𝑎2,…,𝑎𝑛], check whether 𝑎𝑖=𝑎𝑛+1−𝑖.
(b) Based on the symmetric function in part (a), define an ML function palindrome that takes an integer 𝑛, and a list of length 𝑛, and check whether the list is a palindrome. That is given a list [𝑎1,𝑎2,…,𝑎𝑛], check whether 𝑎1=𝑎𝑛, 𝑎2=𝑎𝑛−1, …, and 𝑎𝑖=𝑎𝑛+1−𝑖 for all 1≤𝑖≤𝑛. For example, the list [9,8,6,8,9] is a palindrome.
(c) Write an ML function rev that takes a list of any type as input and returns a list containing all elements of the input list but in reverse order. You are not allowed to use any built-in functions.