The University of Hong Kong COMP3259: Principles of Programming Languages
Assignment 1 Deadline: 23:59, Feb 10th, 2021
Tutor
Yaoda Zhou ydzhou@cs.hku.hk
Course Instructor
Bruno Oliveira bruno@cs.hku.hk
Div /\ /\
Mult Sub /| |\
/| |\ 5Sub 6Add
/\/\ 5223
Question 1. (5 pts.) Please define the expression for the abstract syntax tree in Figure? (Please answer it in Declare.hs)
Question 2. (5 pts.) What’s the result of evaluating this expression? (Please answer it in Declare.hs)
2
1 Pretty Printing and Expression Evaluation
Now we can write down so many expressions, but in Haskell. Sometimes it is too difficult to read the Haskell expressions, as you wrote in first question.
We wish to read the mathematical form of an Haskell expression. For example, the mathematical form of e1 is (3 + 4), the mathematical form of e2 is (3 + ((4 – 5) * 7)) and e3 is (((1 + 2) / 3) – ((5 – 6) * 8)).
Note: The definition of e1, e2 and e3 can be found at Declare.hs.
Question 3. (10 pts.) Your task is to finish function showExpr :: Exp -> String.
Now you have the interpreter printing the concrete representation of the abstract syntax.
*Declare> e2
(3 + ((4 – 5) * 7))
On the console will automatically invoke that showExpr function and print the concrete representation of e2.
Next task is compute the result of expressions.
For example, the result of e1 is 7 and the result of e2 is -4.
Question 4. (10 pts.) Complete function evaluate :: Exp -> Int in file Interp.hs.
If you have gone through the tutorials, then congratulations! You have created a fully working calculator all by yourself.
3
2 Error Handling (Cont.)
Question 5. (10 pts.) Complete the definition of evaluate2 with Power and Neg operation.
If you are such a programmer who has a good taste of code, you won’t be much happy of your solution for evaluate2 in the tutorial. Though it works, the code is so ugly, and the nested creeping indentation makes you want to scratch your head.
Notice that there is a pattern recurring in our code. Every time we evaluate some expressions, we get an Either value, we pattern match it and fork the computation: If the result is Right we make the contained value available to the rest of computation; If the result is Left, we skip the rest of the computation and propagate the error message.
A good programmer is able to recognize the pattern, and try to abstract it to improve the code. Let’s do it!
For starters, let’s define a function called bindE, which given an Either value and a function that encapsulates the rest of the computation, returns another Either value.
More specifically, bindE has the following type signature:
bindE :: Either a b -> (b -> Either a b) -> Either a b
Don’t get intimidated by the above type signature! The definition is just like what we had in the evaluate2 function: We pattern match the first argument, if it is Left, we just return it; If it is Right, we apply the value contained in Right to the second argument
(which is a function) and get another Either value.
Question 6. (10 pts.) Complete the bindE function.
Having bindE functions at our service, we can start to refactor evaluate2 to make it
much cleaner.
Question 7. (10 pts.) Create a new function evaluate3 that is similar to evaluate2, but uses bindE. Note that now you don’t have to explicitly deal with Either values (e.g., pattern matching), except when you have to create them. The resulting code should be significantly simpler than evaluate2.
4
Now you should be able to appreciate the power of abstraction. Actually this kind of pattern has a bizarre name in the functional programming literature, we call it an Either Monad. Don’t worry if you don’t understand, we will be dealing with it a lot in the future tutorials!
5
3 Eliminating Zeros
Consider we want to evaluate the following expression
(1+2*3+4/5-6+7^8-9) * 0
We may work very hard in evaluating the left subexpression inside the parenthesis – and once we finish, we will see it is immediately multiplied by 0, which gives 0 directly! In this case, it’s endurable; after all, we only did evaluation involving 8 operators and 9 numbers. But how about thousands of operators and numbers? I wish I could know in advance that the result is going to be 0 anyway, so I can save my efforts!
Let’s write a function that can help us detect it.
Question 8. (10 pts.) Create a new function elimiZeros that does the following: Add your code in Interp.hs file.
Simplify n – 0 to n
Simplify n + 0 and 0 + n to n
Simplify n * 0 and 0 * n to 0
Simplify 0 ^ n to 0
Simplify – 0 to 0
Otherwise leave the expression unchanged.
For example:
*Interp> elimiZeros (Add (Num 3) (Num 0))
3
*Interp> elimiZeros (Add (Num 3) (Num 2))
(3 + 2)
Notice you may need to do it recursively:
*Interp> elimiZeros (Add (Num 4) (Neg (Mult (Num 3) (Num 0))))
4
6
4 Inference rules (Cont.)
e1->n1 e2->n2 ———————-E+ Add e1 e2 -> n1 + n2
In the lecture, we have a rule E+. In the following we replace it with three rules. We assume the knowledge of arithmetic equality, so you don’t need any reason for a correct equation in the form of n = n (e.g. 5 = 5) or n1 /= n2 (e.g. 4/=5).
e1->n1 e2->n2 n1=0 ———————————-E+1
Add e1 e2 -> n2
e1->n1 e2->n2 n2=0 ———————————-E+2
Add e1 e2 -> n1
e1->n1 e2->n2 n1/=0 n2/=0 ————————————–E+3
Add e1 e2 -> n1 + n2
Question 9. (10 pts.) Assuming we replace inference rule E+ by E+1, E+2 and E+3, please write the derivation for the e2. You may create a text file derivation.txt where you can write the answer to this and the next two question.
Question 10. (10 pts.) Write the derivation for the expression e3 with the new set of inference rules.
Question 11. (5 pts.) Based on our new inference rules, can there be more than one derivation? Try to explain why.
Question 12. Code style and submission (5 pts.)
7
5 Note
Your solution must be submitted in a single zip file, named as A1_XXX.zip, with XXX replaced by your UID. Your code should be well-written (e.g. proper indentation, names, and type annotations) and documented. Please submit your solution on Moodle before the deadline. Please at least make sure your code compiles!
Please do this assignment on your own; if, for a small part of an exercise, you use some- thing from the Internet or were advised by your classmate, please mark and attribute the source in a comment. Do not use publicly accessible code sharing websites for your assignment to avoid being suspected of plagiarism.
8