COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

Code (Week 4)

module Week4 where

data AST = Number Int 
         | Plus AST AST 
         | Times AST AST 
         | Let AST (AST -> AST)


type Value = Int 

eval :: AST -> Value 
eval (Number n) = n 
eval (Plus e1 e2) = eval e1 + eval e2 
eval (Times e1 e2) = eval e1 * eval e2 
eval (Let e1 f) = let v1 = eval e1
                      e2subst = f (Number v1)
                      v2 = eval e2subst 
                   in v2


step :: AST -> Maybe AST 
step (Number n) = Nothing
step (Plus (Number n) (Number m)) = Just (Number (n + m))
step (Plus (Number n) e2) = let Just e2' = step e2
                             in Just (Plus (Number n) e2')
step (Plus e1 e2) = let Just e1' = step e1
                     in Just (Plus e1' e2)
step (Times (Number n) (Number m)) = Just (Number (n * m))
step (Times (Number n) e2) = let Just e2' = step e2
                             in Just (Times (Number n) e2')
step (Times e1 e2) = let Just e1' = step e1
                     in Just (Times e1' e2)
step (Let (Number n) f) = Just . f $ Number n
step (Let e1 f) = let Just e1' = step e1 
                   in Just (Let e1' f)

reflTransClo :: AST -> AST 
reflTransClo (Number n) = (Number n)
reflTransClo e = let Just e' = step e
                  in reflTransClo e'  

run :: AST -> Int
run e = let Number n = reflTransClo e
         in n 
-- let x = 3 in let y = 4 in x + y end end 
example :: AST 
example = Let (Number 3) (\x -> Let (Number 4) (\y -> Plus x y))

The example can be executed in big-step semantics by typing eval example and in small-step semantics by typing run example.

2018-11-16 Fri 19:37

Announcements RSS