The University of Hong Kong
COMP3258: Functional Programming
Assignment 2
Deadline: 23:59, Nov 15, 2018 (HKT)
Notice:
- You can start from the sample code provided on Moodle. Feel free to edit it, as longas you follow the
- Onlythe following libraries are allowed to be imported in this 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 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.
4. 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
- 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 (hardor easy). It is optional and will not affect your
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 deftning 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.
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]
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]
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_factor := ′/′ factor op_factor | ϵ factor := ′(′ expr ′)′ | list | identif ier 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 tokenfunction in hs to remove leading and trailing spaces.
- Yourparser should reflect the left-associativity of the See the last example in question 4.
- Integers can be
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:
*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 theinput
Expected running results:
*Main> runParser (char 'a') "a" Just 'a' *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
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:
*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]
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 anexpression
- Firsttranslate the expression into a program on a simple stack machine, and then run the
*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]
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
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:
- Youmay need to build a simple parser for parsing the
- Use \n in string to print a blank
- quit to quit the
Example 1:
*Main> main > no such command Error > quit *Main>
- Directevaluation of any expressions from first section, for example, 1 + 2, x * 2.
- Print ans = value, where value is the calculated
- Allthe operations in the first section should be
- You can assume the environment is empty if the let command is notsupported by your REPL. Otherwise you should use the current enviroment to evaluate the expression.
- Print Error if the expression evaluates toNothing.
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
- Supportvariable assignment let var = expression, such as let a = 10 and let b = a + 10.
- expression is the Exprin Problem 1.
- Ifthe expression on the right hand evaluates to Nothing, then print Error, and keep the environment
- Aftercommand let x = expression, it should echo x = value where the value is the evaluated result of the expression. See examples
- Anew assignment creates an new entry in the environment and the variable can be used in any later
- Thelater assignment overrides the old value in the
Example 3:
*Main> main > 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>
- envto print the current environment in alphabetical order (Library function sort
can be used here)
- Noticethat new assignment overrides the old one, so there shouldn’t be duplicated entries for a same
- Print empty string “” if environment is
- The format to print is var = value per line. Don’t print extra blank line after the final
Example 4:
*Main> main > env > let a1 = [1,2,3] a1 = [1,2,3] > 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.
