Demo Lambda Calculus Interpreter
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
-- 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
Haskell
INFO