Description
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., X
Y
= Z).
(f) Give the query to compute 2
3
.
(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.
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.
4 Submission and Marking
Submit the two files assg4.pl and assg4.ml in Blackboard (https://elearn.cuhk.edu.hk/).
You can submit your assignment multiple times. Only the latest submission counts.
Plagiarism is strictly monitored and heavily punished if proven. Lending your work to others is
subjected to the same penalty as the copier. You have to insert the following statement as
comments in your Prolog and ML programs.
