# Assignment 7 specification

Tue Oct 30

module A07Sol where

In this assignment, we’ll define a small language of arithmetic expressions that can be interpreted and compiled into lower-level instructions.

# Numeric operators

Let’s begin with binary and unary operators. You have seen these enumerated types previously, but we’ll also define how to interpret them.

data UnaryOp
= Sqrt    -- square root
| Neg     -- negate
| Abs     -- absolute value
deriving (Eq, Show)

Here is a tiny interpreter that converts each unary operator into one of the Haskell numeric functions. The Abs constructor is implemented using the abs function, which has the required type Double -> Double. The Neg constructor is implemented using an operator section of the subtraction operator: to negate a value, you subtract it from zero.

runUnaryOp :: UnaryOp -> Double -> Double
runUnaryOp Abs = abs
runUnaryOp Neg = (0-)
-- TODO: You should add a clause for Sqrt.

Here are some examples of its usage:

ghci> runUnaryOp Sqrt 25
5.0
ghci> runUnaryOp Abs (-10)
10.0
ghci> runUnaryOp Neg (10)
-10.0
ghci> runUnaryOp Neg (-10)
10.0

Now for the binary operators.

data BinaryOp
| Sub     -- subtract
| Mul     -- multiply
| Div     -- divide
| Pow     -- power (exponent)
deriving (Eq, Show)

We can similarly define what these do by translating each to a Haskell numeric function. These are all operator sections. The first few are done for you:

runBinaryOp :: BinaryOp -> Double -> Double -> Double
runBinaryOp Add = (+)
runBinaryOp Pow = (**)
-- TODO: You should add clauses for Sub, Mul, Div.

Some sample uses:

ghci> runBinaryOp Add 3 5
8.0
ghci> runBinaryOp Pow 2 12
4096.0
ghci> runBinaryOp Sub 10 15
-5.0
ghci> runBinaryOp Mul 10 15
150.0

# Expression trees

As presented in class, arithmetic expressions are trees. Here is a type defining a tree in which we can have literal numbers, variable names, and both kinds of operators.

data Arith
= Num Double
| Var String
| UnaryOp UnaryOp Arith
| BinaryOp BinaryOp Arith Arith
deriving (Eq, Show)

To evaluate expression trees, we need an environment that provides values for any variables that may be present in the tree. Evaluation can produce an error only if it encounters a variable not present in the environment. We’ll represent the environment as a list of pairs:

type Environment = [(String, Double)]

Some sample environments:

env1 :: Environment
env1 = [("x", 13), ("y", -95)]
env2 :: Environment
env2 = [("z", -5), ("k", 350), ("pi", pi)]

This evaluator differs from the one we did in class by returning an Either type where the Left value represents the name of an unknown variable.

evaluate :: Environment -> Arith -> Either String Double

We’ll do the recursive cases first. We evaluate one or both subtrees recursively, and then apply the runUnaryOp or runBinaryOp as needed. I will explain the <$> and <*> more thoroughly in class, but they allow us to apply the appropriate run function within a functor (such as Either or Maybe). evaluate env (UnaryOp op t) = runUnaryOp op <$> evaluate env t
evaluate env (BinaryOp op t1 t2) =
runBinaryOp op <\$> evaluate env t1 <*> evaluate env t2

Now we need clauses for the two base cases: the Num and Var constructors. These will construct either a Right value carrying a number, or Left value carrying the name of an unknown variable. (Use case and lookup to access the environment.)

evaluate env (Num val) = error "TODO: evaluate Num"
evaluate env (Var name) = error "TODO: evaluate Var"

## Sample expressions

Formula for the area of a circle: $$\pi r^2$$

egCircle :: Arith
egCircle =
BinaryOp Mul (Num pi) (BinaryOp Pow (Var "r") (Num 2)) ghci> evaluate [] egCircle
Left "r"
ghci> evaluate [("r",8)] egCircle
Right 201.06192982974676
ghci> evaluate [("r",2.22)] egCircle
Right 15.483025233951938

Here is an expression for the Pythagorean theorem (Euclidean distance): $$\sqrt{x^2 + y^2}$$

egEuclid :: Arith
egEuclid =
UnaryOp Sqrt
(BinaryOp Pow (Var "x") (Num 2))
(BinaryOp Pow (Var "y") (Num 2))) ghci> evaluate [] egEuclid
Left "x"                   -- Encountered unknown variable 'x'
ghci> evaluate [("x",8)] egEuclid
Left "y"                   -- Encountered unknown variable 'y'
ghci> evaluate [("x",8),("y",5)] egEuclid
Right 9.433981132056603    -- Correct answer
ghci> evaluate [("x",3),("y",4)] egEuclid
Right 5.0                  -- Correct answer

Next example is one arm of the quadratic formula:

$\frac{ -b + \sqrt{b^2-4ac} }{2a}$

egQuadratic :: Arith
BinaryOp Div
(UnaryOp Neg (Var "b"))
(UnaryOp Sqrt
(BinaryOp Sub
(BinaryOp Pow (Var "b") (Num 2))
(BinaryOp Mul
(Num 4)
(BinaryOp Mul (Var "a") (Var "c"))))))
(BinaryOp Mul (Num 2) (Var "a")) These are some of the exact test cases I used for our implementation of the quadratic formula in assignment 1:

ghci> evaluate [] egQuadratic
Left "b"
ghci> evaluate [("a",2),("b",9),("c",3)] egQuadratic
Right (-0.36254139118231254)
ghci> evaluate [("a",1),("b",-1),("c",-1)] egQuadratic
Right 1.618033988749895
ghci> evaluate [("a",2),("b",8),("c",6)] egQuadratic
Right (-1.0)
ghci> evaluate [("a",1),("b",30),("c",pi)] egQuadratic
Right (-0.1050878704703262)

Finally, here is the Manhattan distance, using absolute value: $$|x1-x2|+|y1-y2|$$

egManhattan :: Arith
egManhattan =
(UnaryOp Abs (BinaryOp Sub (Var "x1") (Var "x2")))
(UnaryOp Abs (BinaryOp Sub (Var "y1") (Var "y2"))) And here are some of the test cases on Manhattan distance from assignment 1:

ghci> evaluate [("x1",3),("y1",2),("x2",9),("y2",2)] egManhattan
Right 6.0
ghci> evaluate [("x1",-3),("y1",-4),("x2",-8),("y2",9)] egManhattan
Right 18.0
ghci> evaluate [("x1",0),("y1",0),("x2",1),("y2",1)] egManhattan
Right 2.0
ghci> evaluate [("x1",3),("y1",6.1),("x2",3),("y2",2)] egManhattan
Right 4.1

# A stack machine

Now we’re going to consider a very different way of evaluating arithmetic expressions. Instead of interpreting operations in a tree format, this one follows a sequence of instructions and uses a stack for temporary memory. This is a lot more like executing assembly language or machine code.

Here is a sample program (not in Haskell notation) for a stack machine, and a trace of its stack when x=3 and y=4.

Instructions:    Stack (grows to the right):
ε (empty)
PUSH 2           3   2
POW              9
LOAD y           9   4
PUSH 2           9   4    2
POW              9   16
PUSH 0.5         25  0.5
POW              5

Each instructions pushes and/or pops values from the stack:

• LOAD retrieves the value of a variable from the environment, and pushes it onto the stack.

• PUSH pushes a literal number onto the stack.

• POW and other binary operators pop the top two elements from the stack, execute the operation, and then push the result.

So here is one way to represent instructions as a Haskell data type:

data Instruction
= Push Double
| Bop BinaryOp
| Abso
deriving (Eq, Show)

We allow any BinaryOp to be an instruction. We could do the same for UnaryOp, but instead let’s compile away the Sqrt and Neg, and only provide one unary instruction: Abso for absolute value. To do square root and negation, we just use these equivalences in terms of Pow and Sub:

• $$\sqrt{x} = x^{0.5}$$
• $$-x = 0 - x$$

So the sample stack program above would be represented as a list of instructions, like this:

stEuclid :: [Instruction]
stEuclid =
[Load "x", Push 2, Bop Pow,
Load "y", Push 2, Bop Pow,
Bop Add, Push 0.5, Bop Pow]

When evaluating trees, there was one kind of error: a missing variable. So we had the tree evaluator return Either String Double, where the String indicated the name of the missing value.

When executing a list of instructions, there can be two kinds of errors: a missing variable, and also a stack underflow. Underflow happens when an instruction needs more operands than are available on the stack. Consider this program:

Instructions:    Stack (grows to the right):
ε (empty)
PUSH 3            3
PUSH 4            3  4
PUSH 5            3  4  5
MUL               3  20
POW              *UNDERFLOW*

When the program reaches the POW instruction, it requires two operands on top of the stack, but there is only one. So an underflow error occurs.

We’ll represent our two types of errors using a data type:

data ExecutionError
= StackUnderflow Instruction
| MissingVar String
deriving (Eq, Show)

In Haskell, we’ll just represent the stack as a list of numbers. Prepend with the list constructor (:) to push. Pattern-match the head element(s) to pop.

type Stack = [Double]

Now we’re ready to define the execution of our stack machine. It takes an environment, an initial stack, and a list of instructions. It returns a resulting stack, or else an error.

execute :: Environment -> Stack -> [Instruction] ->
Either ExecutionError Stack

If there are no instructions left to execute, just return the stack:

execute _ stack [] = Right stack

A push instruction adds a value to the stack, and continues with subsequent instructions:

execute env stack (Push val : prog) =
execute env (val : stack) prog

A binary operator pattern-matches to find two values on the top of the stack, and then applies the operator, pushes the result, and continues with subsequent instructions:

execute env (y:x:stack) (Bop op : prog) =
execute env (runBinaryOp op x y : stack) prog

TODO: There are still three clauses for you to complete:

• computing the absolute value

• loading a variable from the environment, or reporting MissingVar if it’s not available.

• reporting a StackUnderflow if there weren’t enough arguments on the stack for Bop or Abso.

Executing some small sample programs:

ghci> execute [] [] [Push 8]
Right [8.0]
ghci> execute [] [] [Load "x"]
Left (MissingVar "x")
ghci> execute [] [] [Bop Pow]
Left (StackUnderflow (Bop Pow))
ghci> execute [] [] [Push 3, Push 4, Bop Div]
Right [0.75]
ghci> execute [] [] [Push (-8), Abso]
Right [8.0]
ghci> execute [] [] [Push 9, Abso]
Right [9.0]
ghci> execute [("x",4)] [] [Load "x"]
Right [4.0]
ghci> execute [("x",4)] [] [Load "x", Load "x", Bop Mul]
Right [16.0]

# A compiler!

There are no more tasks for you to complete in this section, but we’re going to do something pretty amazing. We’re going to compile (translate) the expression trees into a list of stack machine instructions. The type of the compiler says exactly that:

compile :: Arith -> [Instruction]

The base cases are pretty easy:

compile (Num x) = [Push x]
compile (Var name) = [Load name]

Unary operators are ‘compiled away’ either by converting them to binary operators:

compile (UnaryOp Sqrt t) = compile (BinaryOp Pow t (Num 0.5))
compile (UnaryOp Neg t) = compile (BinaryOp Sub (Num 0) t)

or using the Abso instruction:

compile (UnaryOp Abs t) = compile t ++ [Abso]

And binary operators are compiled quite simply like this:

compile (BinaryOp op t1 t2) = compile t1 ++ compile t2 ++ [Bop op]

Check it out — here are compiled programs for the three sample trees:

ghci> compile egEuclid
[Load "x", Push 2.0, Bop Pow,
Load "y", Push 2.0, Bop Pow,
Bop Add, Push 0.5, Bop Pow]
[Push 0.0, Load "b", Bop Sub, Load "b", Push 2.0, Bop Pow,
Push 4.0, Load "a", Load "c", Bop Mul, Bop Mul, Bop Sub,
Push 0.5, Bop Pow, Bop Add, Push 2.0, Load "a", Bop Mul, Bop Div]
ghci> compile egManhattan
[Load "x1", Load "x2", Bop Sub, Abso,
Load "y1", Load "y2", Bop Sub, Abso, Bop Add]

And we can execute those programs in given environments, and produce the same result as the evaluator:

ghci> evaluate [("x1",-3),("y1",-4),("x2",-8),("y2",9)] egManhattan
Right 18.0
ghci> execute [("x1",-3),("y1",-4),("x2",-8),("y2",9)] [] (compile egManhattan)
Right [18.0]
ghci> evaluate [("a",2),("b",9),("c",3)] egQuadratic
Right (-0.36254139118231254)
ghci> execute [("a",2),("b",9),("c",3)] [] (compile egQuadratic)
Right [-0.36254139118231254]
ghci> evaluate [("x",8),("y",5)] egEuclid
Right 9.433981132056603
ghci> execute [("x",8),("y",5)] [] (compile egEuclid)
Right [9.433981132056603]

You also get the same error results if there are unused variables.

ghci> evaluate [("k",9)] egEuclid
Left "x"
ghci> execute [("k",9)] [] (compile egEuclid)
Left (MissingVar "x")

A correctly-compiled expression tree should never produce a StackUnderflow.

main :: IO ()
main = return ()