本次HK Haskell代写要求完成4个part的exercise，分别是expression trees、parsing expressions、compilation、REPL。

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).

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.

Let’s start from defining operations.

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.

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 token function in hs to remove leading and trailing spaces.
• Your parser 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 the input

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 an expression
• First translate 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.