Notice:
The University of Hong Kong COMP3258: Functional Programming
Assignment 2 Deadline: 23:59, Nov 15, 2018 (HKT)
- You can start from the sample code provided on Moodle. Feel free to edit it, as long as you follow the pdf.
- Only the following libraries are allowed to be imported in this assignment. Parsing is the code for Lecture that can be found on Moodle.import Data.Char import Data.List import Parsing import System.IO
- Please submit a single Haskell file, named as A2_XXX.hs, with XXX replaced by your UID, and follow all the type signatures strictly. No need to submit Parsing.hs. In the case that Moodle rejects your .hs file, please submit it as A2_XXX.zip, which includes only one file A2_XXX.hs.
- Make sure your code can be compiled and run. Even if a function cannot pass all test cases, you can get partial marks.
- If only partial functionality is supported for REPL part, please give one line com- ment explaining which commands are supported.
- If you would like, please add a line of comment at the end of your file to tell us how many hours you did spend on this assignment, and how do you feel (hard or easy). It is optional and will not affect your scores.1
1 Expression Trees
This time our expression trees are about lists instead of integers. And we are going to define an evaluation function which returns a value of Maybe [Int].
In Haskell, Maybe is a type constructor used to represent “a value or nothing”. A value of type Maybe a is either Just a (just a value of type a) or Nothing, as Maybe has 2 data constructors by the following definition (which is included in Prelude library).
data Maybe a = Just a | Nothing
Maybe describes values with a context of possible failure attached. For example, if we expect a function returns a integer, but it might have error, we can set its return type to be Maybe Int, and let it returns Nothing when error happens. When there is no error, the function can return Some 3 for example if 3 is the calculated result.
If the input type of your function is Maybe a, you need to take care of the 2 possible forms of the argument. The following example shows how to use pattern matching to define a function f that converts Nothing to -1.
f :: Maybe Int -> Int f (Just n) = n f Nothing = -1
Let’s start from defining operations.
data Op = Add | Sub | Div deriving (Eq, Show)
We support 3 operations on lists. Add and Sub can be understood as vector addition and substraction. And Div works in a similar way. Essentially, an operation takes 2 lists with the same lengths. For each element from one list, add it to, or substract it from, or divide it by the element from in the same position from the other list. Specially, if the 2 operands are both empty lists, the result should be empty list.
Problem 1. (10 pts.) Implement a function applyOp :: Op -> Maybe [Int] -> Maybe [Int] -> Maybe [Int] that calculate the result when applying an operation.
2
The function should return Nothing when: Any of its input is Nothing, or its input lists are in different lengths, or dividing by zero happens.
Expected running results:
*Main> applyOp Add (Just [1,2,3]) (Just [1,1,1]) Just [2,3,4] *Main> applyOp Sub (Just [1,2,3]) (Just [1,1,1]) Just [0,1,2]
*Main> applyOp Div (Just [2,3,4]) (Just [2,2,2]) Just [1,1,2] *Main> applyOp Div (Just []) (Just []) Just []
*Main> applyOp Div (Just [2,3,4]) (Just [2,0,2]) Nothing *Main> applyOp Add (Just [1,2]) (Just [1,1,1]) Nothing
*Main> applyOp Sub (Just [1,2,3]) Nothing Nothing
Our Expr data type is defined for expression trees on lists.
data Expr
= Bin Op Expr Expr | Val [Int]
| Var String deriving (Eq, Show)
Expr have 3 data constructors. Bin is for all binary operations over expressions. Val stands for values and Var is used by variables.
We use an environment Env to store the values of variables. The library function lookup could be used to search in an environment.
type Env = [(String, [Int])]
Problem 2. (5 pts.) Implement a function eval :: Env -> Expr -> Maybe [Int] to evaluate expression trees. eval should return Nothing if the lengths of 2 lists for one operation is different, or any divisor is 0, or a variable cannot be found in the environment.
Expected running results:
eval [] (Bin Add (Val [1,2,3]) (Val [1,1,1])) Just [2,3,4]
3
eval [("x",[1..3])] (Bin Add (Var "x") (Val [1,1,1]))
Just [2,3,4]
eval [] $ Bin Add (Bin Add (Val [1]) (Val [2])) (Bin Div (Val [3]) (Val [2]))
Just [4]
*Main> eval [("x1",[1..10]),("x2",[2..11])] (Bin Add (Var "x1") (Var "x2"))
Just [3,5,7,9,11,13,15,17,19,21]
4
2 Parsing Expressions
Then let’s write a parser for those expression trees. You may want to review Tutorial 4 and Lecture 7 when doing this section. And don’t forget you can use functions defined in Parsing.h.
Here is the grammer of our expressions:
expr := term op_term op_term := (′+′ | ′−′) term op_term | ε term := factor op_factor
op_f actor := ′ /′ f actor op_f actor | ε factor := ′(′ expr ′)′ | list | identifier
list := ′[′ (integer some_ints | ε) ′]′ some_ints := ′,′ interger some_ints| ε
You can assume the identifiers start with a lower case letter, and may contain any alphabetic or numeric characters after the first one, without any spaces in it.
Notice:
• Use the token function in Parsing.hs to remove leading and trailing spaces.
• Your parser should reflect the left-associativity of the operators. See the last
example in question 4.
• Integers can be negative.
Problem 3. (10 pts.) Implement a function pList :: Parser Expr for parsing lists based on the last 2 rules in our grammer above.
Expected running results:
5
*Main> parse pList "[1,2,3]" [(Val [1,2,3],"")] *Main> parse pList "[]" [(Val [],"")]
*Main> parse pList " [ 1 , 2 , 3 ]" [(Val [1,2,3],"")]
Problem 4. (20 pts.) Implement a function pExpr :: Parser Expr for parsing Exprs. Expected running results:
*Main> parse pExpr "[1,2,3]+[1,1,1]" [(Bin Add (Val [1,2,3]) (Val [1,1,1]),"")] *Main> parse pExpr "[1,2,3]-[1,1,1]" [(Bin Sub (Val [1,2,3]) (Val [1,1,1]),"")] *Main> parse pExpr "[] / []" [(Bin Div (Val []) (Val []),"")] *Main> parse pExpr " [10] - [3] - [2] - [1]" [(Bin Sub (Bin Sub (Bin Sub (Val [10]) (Val [3])) (Val [2])) (Val [1]),"")]
Now we are going to implement a general function that works for any Parser. Instead of parse, this function runs a parser and returns the parsed thing, but it fails when the parser does not parse the whole string. Thurs, for example, it can tell if a given string is grammacially incorrect.
data Parser a = P (String -> [(a,String)])
In the data type definition of Parser in Parsing.h, we are using empty list to represent
failure of a parsing process. In our function, we would like to convert it to Nothing.
Problem 5. (5 pts.) Implement a function runParser :: Parser a -> String -> Maybe a. runParser runs a given parser once to parse the full string and returns the parsed result.
Notice:
• Return Nothing when the parser fails
• Return Nothing when the parser only consumes part of the input
Expected running results:
*Main> runParser (char 'a') "a" Just 'a'
6
*Main> runParser (char 'a') "aa" Nothing *Main> runParser pList "[]" Just (Val [])
*Main> runParser pList "[]]" Nothing *Main> runParser pExpr "x+[1]" Just (Bin Add (Var "x") (Val [1])) *Main> runParser pExpr "x++" Nothing
7
3 Compilation
Instead of defining eval directly, we can give expressions meaning by compiling expres- sions onto a simple stack machine.
Consider that the stack machine supports the following instructions:
data Instr = IVal [Int] | IBin Op | IVar String deriving (Eq, Show)
Instructions contains integer literal IVal, variable Var, and binary operations IBin. The evaluation of instructions are based on a simple stack, which is modeled as a list of list of integers:
type Stack = [[Int]]
Initially the stack would be empty, when implementing instruction, the state of the stack changes. Instruction IVal xs will push xs into the stack, and IVar x will push the value of variable x (if it is in the environment) into stack. IBin op will pop two values from the stack, and apply the binary operator to them, and then push the result into the stack.
type Prog = [Instr]
A program is a list of instructions. Implementing a program is implementing instructions
in it sequentially.
Before compiling, we can do static checking on an expression to catch some possible errors eariler. It is static in contrast with dynamtic checking because we do not need to run the program or calculate the result of expressions.
Problem 6. (5 pts.) Implement a function check :: Expr -> Env -> Bool that when any binary operations in the input expression takes 2 lists with different lengths, or when any variable cannot be found in the enviroment.
Expected running results:
8
*Main> check (Val [1..10]) []
True
*Main> check (Bin Add (Val [1,2]) (Val [0,1])) []
True
*Main> check (Bin Div (Val [1]) (Val [0])) []
True
*Main> check (Bin Add (Val [1]) (Bin Sub (Val [2]) (Val [1]))) []
True
*Main> check (Bin Add (Var "x") (Bin Sub (Val [2]) (Val [1]))) [("x",[1,2])]
False
Problem 7. (10 pts.) Implement a function compile :: Expr -> Env -> Maybe Prog that compiles an expression into a program that can be run in the stack machine after checking the expression with given environment using check. It returns Nothing when checking fails.
Expected running results:
*Main> compile (Val [1..10]) []
Just [IVal [1,2,3,4,5,6,7,8,9,10]]
*Main> compile (Bin Add (Val [1,2]) (Val [0,1])) []
Just [IVal [0,1],IVal [1,2],IBin Add]
*Main> compile (Bin Div (Val [1]) (Var "x")) [("x",[1])]
Just [IVar "x",IVal [1],IBin Div]
*Main> compile (Bin Div (Val [1]) (Var "x")) [("x",[])]
Nothing
After compiling successfully, we need a function to run the program. We assume the input program and environment together have passed checking as its compiled by our compile function. But there still could be runtime error.
Problem 8. (10 pts.) Implement a function runProg :: Prog -> Env -> Maybe [Int]. runProg runs a program with an empty stack at the beginning. Return Nothing when error happens.
Expected running results:
*Main> runProg [IVal [0,1],IVal [1,2],IBin Add] [] Just [1,3] *Main> runProg [IVal [0,1],IVal [1,2],IBin Div] [] Nothing
*Main> runProg [IVar "x"] [("x",[0..3])]
Just [0,1,2,3]
9
With all those functions defined so far, you should be able to verify that the two ap- proaches always give the same result:
• Direct evaluation over an expression
• First translate the expression into a program on a simple stack machine, and then
run the program.
*Main> let Just exp = runParser pExpr “[3,2]-[1,0]” *Main> exp
Bin Sub (Val [3,2]) (Val [1,0])
*Main> eval [] exp
Just [2,2]
*Main> check exp []
True
*Main> let Just prog = compile exp [] *Main> prog
[IVal [1,0],IVal [3,2],IBin Sub] *Main> runProg prog []
Just [2,2]
10
4 REPL: Read-Eval-Print Loop
In previous programs, we are required to pass an environment to the evaluation process manually, which is quite inconvenient. Also there is no way for us to change the value of a variable during the calculation.
In this section we are going to develop a very simple REPL to compute the value of an expression. A REPL is an interactive program, which reads the input, executes the input, prints the result and waits for the next input. For example, GHCi is the REPL for Haskell.
The REPL stores values of variables in Env, therefore we can directly refer to those variables during calculation. To hide the details about IO, you can paste the following code to the assignment:
main :: IO () main = do
hSetBuffering stdin LineBuffering hSetBuffering stdout NoBuffering repl []
repl :: Env -> IO () repl env = do
putStr "\n> " line <- getLine dispatch env line
dispatch :: Env -> String -> IO () dispatch = error "TODO"
If you enter main in GHCi, it enters the REPL with an empty environment. The REPL prints a prompt > and waits for the command from the user.
*Main> main
>
You job is to implement the dispatch method that takes the current environment and
11
the command from the user, executes the command, prints the result, and goes back to REPL. The following functions are provided to take care of IO things for you:
quit :: IO () quit = return ()
loop :: String -> Env -> IO () loop str next = do
putStrLn str repl next
When you call the function quit from dispatch, it will exit the REPL. You can pass a String and current environment to loop, which will print the String for you and continue to REPL with the environment you provided.
What is more, you can call the show function to convert a list of integers to a string when you need.
Problem 9. (20 pts.) Please complete the dispatch function. You need to support 4 types of commands to get full marks. If any illegal case occurs, just print Error and continue to REPL, for example, when receiving illegal commands.
Hints:
• You may need to build a simple parser for parsing the commands. • Use \n in string to print a blank line.
1. quit to quit the loop.
Example 1:
*Main> main
> no such command Error
> quit *Main>
2. Direct evaluation of any expressions from first section, for example, 1 + 2, x * 2. • Print ans = value, where value is the calculated result.
• All the operations in the first section should be supported.
12
• You can assume the environment is empty if the let command is not supported by your REPL. Otherwise you should use the current enviroment to evaluate the expression.
• Print Error if the expression evaluates to Nothing. Example 2:
*Main> main
> [1]
ans = [1] > [1] + [2] + [3] + [4]
ans = [10] > [1,2] + []
Error
> [1,2] + [3,4,5] Error
> [1,2] + [3,4] ans = [4,6]
> [1] + [2] - [3] / [4] ans = [3]
> quit
3. Supportvariableassignmentletvar=expression,suchasleta=10andlet
b = a + 10.
- expression is the Expr in Problem 1.
- If the expression on the right hand evaluates to Nothing, then print Error,and keep the environment unchanged.
- After command let x = expression, it should echo x = value where thevalue is the evaluated result of the expression. See examples below.
- A new assignment creates an new entry in the environment and the variablecan be used in any later commands.
- The later assignment overrides the old value in the environment.
Example 3:
*Main> main
13
> let x = [1,2] x = [1,2]
> env
x = [1,2]
> let x = [1] + [2] + [3] x = [6]
> let x = y Error
> let x = [1] + [0] x = [1]
> let x = [1] + [] Error
> let y = x y = [1]
> quit *Main>
4. env to print the current environment in alphabetical order (Library function sort can be used here)
- Notice that new assignment overrides the old one, so there shouldn’t be duplicated entries for a same variable.
- Print empty string “” if environment is empty.
- The format to print is var = value per line. Don’t print extra blank line after
the final line.
Example 4:
*Main> main > env
> let a1 = [1,2,3] a1 = [1,2,3]
14
> let a2 = [2,3,0] a2 = [2,3,0]
> env a1 = [1,2,3] a2 = [2,3,0]
> a1 / a2 Error
> env a1 = [1,2,3] a2 = [2,3,0]
> quit *Main>
Code style and submission (5 pts.)
All functions should be implemented in a single Haskell file, named as A2_XXX.hs, 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. In the case that Moodle rejects your .hs file, please submit it as A2_XXX.zip, which includes only one file A2_XXX.hs. Please at least make sure your file can compile!
Plagiarism
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.
15