{- CSci 450/503 Fall 2014
   Examination #2
   H. Conrad Cunningham
   02 November 2014 -- original
   08 November 2014 -- clean formatting, comments

1234567890123456789012345678901234567890123456789012345678901234567890

-}

module Exam02 where

-- Abstract Syntax Tree for expression 
-- adapted from Chapter 3 of Cook's Anatomy of Programming Languages
data Exp = Num Int 
    -- constant
         | Add Exp Exp -- add two expressions
         | Sub Exp Exp -- subtract second from first
         | Var String  -- variable name
-- addition for 8(b)
         | Mul Exp Exp -- multiply
         | Div Exp Exp -- divide first by second
-- addition for 8(c)
         | If Exp Exp Exp -- If expression

-- Environment giving values of variables
type Env = [(String, Int)]

-- Evaluate an expression in an environment
evaluate :: Exp -> Env -> Int
evaluate (Num i) env    = i
evaluate (Add a b) env  = (evaluate a env) + (evaluate b env)
evaluate (Sub a b) env  = (evaluate a env) - (evaluate b env)
evaluate (Var x) env    = case lookup x env of
                              Just x  -> x
                              Nothing -> error ("undefined variable " 
                                                ++ show x)
-- addition for 8(b)
evaluate (Mul a b) env  = (evaluate a env) * (evaluate b env)
evaluate (Div a b) env  = (evaluate a env) `div` (evaluate b env)
-- addition for 8(c)
evaluate (If e v1 v2) env = 
    if (evaluate e env) /= 0 then (evaluate v1 env)
                             else (evaluate v2 env)
    -- could also use condiion as guard

showExp :: Exp -> String
showExp (Num i)   = show i
showExp (Var x)   = show x
showExp (Add l r) = "(" ++ showExp l ++ "+" ++ showExp r ++ ")"
showExp (Sub l r) = "(" ++ showExp l ++ "-" ++ showExp r ++ ")"
-- addition for 8(b)
showExp (Mul l r) = "(" ++ showExp l ++ "*" ++ showExp r ++ ")"
showExp (Div l r) = "(" ++ showExp l ++ "/" ++ showExp r ++ ")"
-- addition for 8(c)
showExp (If e l r) = "(if " ++ showExp e ++ " then " ++ showExp l ++ 
                                      " else " ++ showExp r ++ ")"


-- 8(a) size counts number of operators
size :: Exp -> Int
size (Add l r)  = 1 + size l + size r
size (Sub l r)  = 1 + size l + size r
size (Mul l r)  = 1 + size l + size r
size (Div l r)  = 1 + size l + size r
size (If e l r) = 1 + size e + size l + size r
size _          = 0  -- Num, Var

-- NOT USED: collect variables from expression
vars :: Exp -> [String]
vars (Num _ )   = []
vars (Var x)    = [x]
vars (Add l r)  = vars l ++ vars r
vars (Sub l r)  = vars l ++ vars r
vars (Mul l r)  = vars l ++ vars r
vars (Div l r)  = vars l ++ vars r
vars (If e l r) = vars e ++ vars l ++ vars r

-- NOT USED: height of expression tree
heightExp :: Exp -> Int
heightExp (Num _)    = 1
heightExp (Var _)    = 1
heightExp (Add l r)  = 1 + max (heightExp l) (heightExp r)
heightExp (Sub l r)  = 1 + max (heightExp l) (heightExp r)
heightExp (Mul l r)  = 1 + max (heightExp l) (heightExp r)
heightExp (Div l r)  = 1 + max (heightExp l) (heightExp r)
heightExp (If e l r) = 1 + max (heightExp e) (max (heightExp l) (heightExp r))

-- expressions for testing
ex1 = (Mul (Add (Num 10) (Var "x")) (Sub (Var "y") (Num 1)))
ex2 = (Mul (Add (Num 10) (Var "x")) (If (Var "y") (Num 3) (Num 4)))

env1 = [("z",3),("x",1),("y",2)] :: Env
env2 = [("z",3),("x",1),("y",0)] :: Env