The University of COMP3259: Principles of Programming Languages
Assignment 1
Yaozhu Sun Instructor
Copyright By PowCoder代写 加微信 powcoder
Deadline: 23:59, 21 February 2022
Your solution must be submitted in a single zip file, named as A1_XXX.zip, with XXX replaced by your UID. Please submit your solution on Moodle before the deadline. Your code should be well-written (e.g. proper indentation, readable names, and type signa- tures). You can test your code using stack test. 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.
1 Adding Bitwise Operations
In the second tutorial, we have learnt how to write a simple calculator for arithmetic ex- pressions, including addition, subtraction, multiplication, division, exponentiation, and negation. But we can make our calculator still more powerful!
As we know, integers are commonly represented in a computer as a group of binary digits (or bits for short). A bitwise operation operates on integers at the level of their individual bits. Since a bit is either 0 or 1, any Boolean operation can apply to bits.
For example, a bitwise OR operation between 23 and 48 is as follows:
00010111 (decimal 23)
OR 00110000 (decimal 48)
= 00110111 (decimal 55)
Question 1. (20 pts.) Your first task is to extend the datatype Exp with the following bitwise operations, and then complete the definition of evaluate and showExp.
• And (x .&. y): bitwise conjunction;
• Or (x .|. y): bitwise disjunction;
• Xor (x .^. y): bitwise exclusive disjunction; • Shl (x .<<. y): bitwise left shift;
• Shr (x .>>. y): bitwise right shift.
After finishing your answer to the first question, you should get a working evaluator as well as a pretty printer. However, the calculator is still not fully fledged because we have to manually write abstract syntax like Or (Num 23) (Num 48). Instead, we want to simply write 23 .|. 48. To achieve this, we need to extend our parser.
Question 2. (10 pts.) Modify Tokens.x and Parser.y to support the five bitwise operators. Don’t worry if you know nothing about parser generators. Just follow the example of arithmetic expressions. You can refer to Alex and Happy for details.
By the way, .<<. and .>>. should have the same precedence as ^; .&. should have the same precedence as * and /; .^. should have the same precedence as + and -; .|. should have the lowest precedence.
Note: Tokens.hs and Parser.hs are generated by Alex and Happy using the following commands:
> alex src/Tokens.x
> happy src/Parser.y
2 Taming Eithers
Question 3. (10 pts.) Complete the definition of evaluate2 with bitwise operations.
If you are such a programmer who has a good taste of code, you won’t be much happy with your solution for evaluate2 so far. Though it works, the code is ugly, and the nested creeping indentation may drive you crazy.
Notice that there is a pattern recurring in the 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!
Let’s start with a function called flatMap, which accepts an Either value and a function that encapsulates the rest of the computation, and returns another Either value. More specifically, flatMap has the following type signature:
flatMap :: Either a b -> (b -> Either a b) -> Either a b
Don’t get intimidated by the type signature above! 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 4. (10 pts.) Complete the definition of flatMap.
Having flatMap functions at our service, we can start to refactor evaluate2 to make it
much cleaner.
Question 5. (10 pts.) Create a new function evaluate3 that is similar to evaluate2, but uses flatMap. 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.
After answering the questions above, you may appreciate the power of abstraction. Ac- tually this kind of pattern has a bizarre name in the functional programming literature: we call Either a monad. Don’t worry if you don’t understand it at the moment. We will teach you more about it in the future!
3 Eliminating Zeros
Imagine that we want to evaluate the following expression:
(1+2×3+4÷5−6+78 −9)×0
We may work very hard in evaluating the left sub-expression inside the parentheses. Once we finish it, we will see that it is immediately multiplied by 0, which gives 0 eventually! 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 6. (20 pts.) Define a new function elim0 that does the following:
• Simplify n+0 and 0+n to n; • Simplify n−0 to n;
• Simplify n×0 and 0×n to 0; • Simplify 0÷n to 0;
• Simplify 0n to 0;
• Simplify n0 to 1;
• Simplify −0 to 0;
• Otherwise leave the expression unchanged.
For example:
*Interp> elim0 (Mult (Num 3) (Num 0))
*Interp> elim0 (Mult (Num 3) (Num 2))
Notice that you need to do it recursively:
*Interp> elim0 (Add (Num 4) (Neg (Mult (Num 3) (Num 0))))
4 Inference Rules
In the lecture, we have shown the inference rule for multiplication, namely E×:
e1 → n1 e2 → n2 E× e1 × e2 → n1 × n2
Similar to what we did for eliminating zeros, we want to optimize the evaluation a bit. Thus, besides the existing one, we add two more rules:
e1 → n1 n1 = 0 E×L0 e2 → n2 n2 = 0 E×R0 e1 × e2 → 0 e1 × e2 → 0
Question 7. (10 pts.) Write a derivation tree for the expression e below with the new set of inference rules.
e = (4+8)×(1−1)+16×3
Question 8. (10 pts.) Based on our new inference rules, can there be more than one derivation? If so, show an example and try to change the rules to make sure only one derivation is possible. If not, try to explain why.
The answers to the two questions above can be written in any form (e.g. hand-written, typeset, or ASCII art). Please remember to pack a soft copy of your answers into the zip file you submit.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com