CIS 194 HW3

CIS 194 HW2 (haskell)

-- CIS 194: Homework 3 (http://www.cis.upenn.edu/~cis194/hw/03-ADTs.pdf)

module HW03 where

data Expression =
    Var String
  | Val Int
  | Op Expression Bop Expression
  deriving (Show, Eq)

data Bop = 
    Plus     
  | Minus    
  | Times    
  | Divide   
  | Gt
  | Ge       
  | Lt  
  | Le
  | Eql
  deriving (Show, Eq)

data Statement =
    Assign   String     Expression
  | Incr     String
  | If       Expression Statement  Statement
  | While    Expression Statement       
  | For      Statement  Expression Statement Statement
  | Sequence Statement  Statement        
  | Skip
  deriving (Show, Eq)

type State = String -> Int

-- Exercise 1

extend :: State -> String -> Int -> State
extend s x v y = if x == y then v else s y

empty :: State
empty _ = 0

-- Exercise 2

boolToInt :: Bool -> Int
boolToInt b = if b then 1 else 0
              
evalE :: State -> Expression -> Int
evalE s (Var v) = s v
evalE s (Val n) = n
evalE s (Op lhs op rhs) =
    case op of
      Plus   -> x + y
      Minus  -> x - y
      Times  -> x * y
      Divide -> x `div` y
      Gt     -> boolToInt $ x > y
      Ge     -> boolToInt $ x >= y
      Lt     -> boolToInt $ x < y
      Le     -> boolToInt $ x <= y
      Eql    -> boolToInt $ x == y
    where x = evalE s lhs
          y = evalE s rhs

-- Exercise 3

data DietStatement = DAssign String Expression
                   | DIf Expression DietStatement DietStatement
                   | DWhile Expression DietStatement
                   | DSequence DietStatement DietStatement
                   | DSkip
                     deriving (Show, Eq)

desugar :: Statement -> DietStatement
desugar (Assign v e)   = DAssign v e
desugar (Incr v)       = DAssign v (Op (Var v) Plus (Val 1))
desugar (If e x y)     = DIf e (desugar x) (desugar y)
desugar (While e x)    = DWhile e (desugar x)
desugar (For i e u x)  = DSequence (desugar i) (DWhile e (DSequence (desugar x) (desugar u)))
desugar (Sequence x y) = DSequence (desugar x) (desugar y)
desugar Skip           = DSkip

-- Exercise 4

evalSimple :: State -> DietStatement -> State
evalSimple s (DAssign v e)   = extend s v (evalE s e)
evalSimple s (DIf e x y)     = if (evalE s e) == 1 then evalSimple s x else evalSimple s y
evalSimple s w@(DWhile e x)  = if (evalE s e) == 1 then evalSimple (evalSimple s x) w else s
evalSimple s (DSequence x y) = evalSimple (evalSimple s x) y
evalSimple s DSkip = s

run :: State -> Statement -> State
run s stmt = evalSimple s $ desugar stmt