CSCI3180 Principles of Programming Languages, Spring 2015-2016 Department of Computer Science and Engineering, The Chinese University of Hong Kong Copyright © 2016 CSE, CUHK Page 1 of 3 Assignment 4: Declarative Programming Due: 19:00, Sat 14 May 2016 Full marks: 100 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 CSCI3180 Principles of Programming Languages, Spring 2015-2016 Department of Computer Science and Engineering, The Chinese University of Hong Kong Copyright © 2016 CSE, CUHK Page 2 of 3 (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 CSCI3180 Principles of Programming Languages, Spring 2015-2016 Department of Computer Science and Engineering, The Chinese University of Hong Kong Copyright © 2016 CSE, CUHK Page 3 of 3 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. CSCI3180 Principles of Programming Languages --- Declaration --- I declare that the assignment here submitted is original except for source material explicitly acknowledged. I also acknowledge that I am aware of University policy and regulations on honesty in academic work, and of the disciplinary guidelines and procedures applicable to breaches of such policy and regulations, as contained in the website http://www.cuhk.edu.hk/policy/academichonesty/ Assignment 4 Name: Student ID: Email Addr: