Demo Lambda Calculus Interpreter

-- definition of expression
data Exp = Var String          -- variable
         | App Exp Exp         -- application
         | Lam String Exp      -- abstraction
         | N   Int             -- integer
         | Op  String Exp Exp  -- operator (a special form of function that takes two params)
         deriving (Eq, Show)

-- value definition
data Val = VN   Int                        -- integer
         | VLam String Exp [(String, Val)] -- abstraction
         deriving (Eq, Show)

-- top level evaluation
eval :: Exp -> Maybe Val 
eval exp = ev [] exp 

-- utility to deal with Maybe
bind :: Maybe a -> (a -> Maybe b) -> Maybe b
bind Nothing  f = Nothing
bind (Just v) f = f v

-- inner level eval
ev :: [(String, Val)] -> Exp -> Maybe Val

-- variables
ev []           (Var x)        = Nothing
ev ((x',v):env) (Var x)        = if x == x' then Just v else ev env (Var x)

-- number
ev env (N x)                   = Just (VN x)

-- abstraction
ev env (Lam x body)            = Just (VLam x body env)

-- operator 
ev env (Op op x y)             = bind (ev env x) $ \vx -> 
                                   bind (ev env y) $ \vy -> 
                                     applyOp op vx vy

-- application                                   
ev env (App f arg)             = bind (ev env f) $ \vf -> 
                                   bind (ev env arg) $ \varg -> 
                                     applyLam vf varg

-- operation application
applyOp :: String -> Val -> Val -> Maybe Val
applyOp "+" (VN x) (VN y) = Just (VN (x + y))
applyOp "-" (VN x) (VN y) = Just (VN (x - y))

-- function application
applyLam :: Val -> Val -> Maybe Val
applyLam (VLam x body env) arg = ev ((x,arg):env) body

-- introduce a symbol for application
infixl 1 |>
(|>) = App

-- test programs in our own language
test1 = Op "-" (N 3) (N 4)
test2 = (Lam "x" (Lam "y" (Op "-" (Var "y") (Var "x")))) |> N 3 |> N 4
test3 = (Lam "x" (Op "+" (N 3) (Var "x"))) |> test1 


main = do 
         print $ eval test1
         print $ eval test2
         print $ eval test3