Exercise set 5.

This is the last week of the haskell programming part of the course, and we are going to talk about testing. In particular, testing with tasty and quickcheck.

Credits

The exercises are based on "the mystery" assignment from the course advanced programming at the university of Copenhagen, which was formulated by Ken Friss Larsen.

Let it be

Consider the Haskell data type:

data Expression =
    Constant Integer
  | Variable Identifier
  | Operator Operator   Expression Expression
  | Let      Identifier Expression Expression
      deriving (Eq, Show, Read)

type Identifier = String

data Operator = Plus | Minus | Times
        deriving (Eq, Show, Read)

and the evaluator:

import qualified Data.Map.Strict as M
import Data.Map(Map)

type Env = Map String Integer

oper :: Operator -> (Integer -> Integer -> Integer)
oper Plus  = (+)
oper Minus = (-)
oper Times = (*)

eval :: Expression -> Env -> Either String Integer
eval (Constant n) env = return n
eval (Operator op x y) env = (oper op) <$> eval x env <*> eval y env
eval (Variable v) env = case M.lookup v env of
                     Nothing -> Left ("Unknown identifier: "++v)
                     Just val -> return val
eval (Let v e body) env = do
  val <- eval e env
  eval body $ M.insert v val env

evalTop e = eval e M.empty

simplify e =
  case e of
    Operator Plus  (Constant c1) (Constant c2) -> Constant(c1+c2)
    Operator Minus (Constant c1) (Constant c2) -> Constant(c1+c2)
    Operator Times (Constant c1) (Constant c2) -> Constant(c1*c2)
    Operator op e1 e2 ->
      Operator op (simplify e1) (simplify e2)
    Let v e body ->
      Let v (simplify e) (simplify body)
    _ -> e

Your tasks are as follows.

• Make Expression an instance of the type-class Arbitrary.

• Write a property prop_eval_simplify that expresses that the simplifier shouldn't change the meaning of an expression.

  Are there any bugs in the code?

• The current simplifier only performs a simple transformation. Namely if the AST contains an operation on two constants, then the operation is performed by the simplifier.

  Extend the simplifier so that it can perform some more transformations. You must implement the following transformations:

  • Expressions containing operation with the constants 0 and 1 can often be simplified. For instance, an expression e multiplied with 0 can be simplified to 0.

  • If a let bound variable is not used in the body of a let-expression, then the binding can be eliminated.

  Explain if your extended simplifier needs to make any assumptions about the expressions being simplified. If you need to make assumptions, you may want to write some new properties and/or need new generator(s) and may need a way to choose the different generator(s) (like we did in the Morse code example).

• Extend the simplifier with more transformations. However, the simplifier should never call the evaluator.