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]
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:
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:
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])) []