Skip to content

Instantly share code, notes, and snippets.

@TerrorJack
Created December 19, 2014 09:34
Show Gist options
  • Save TerrorJack/224b21657cc82f079413 to your computer and use it in GitHub Desktop.
Save TerrorJack/224b21657cc82f079413 to your computer and use it in GitHub Desktop.
Call-by-value lambda calculus interpreter (which won't work)
import qualified Data.Map as Map
type Env = Map.Map String Term
data Term =
VarTerm String
| IntTerm Int
| BoolTerm Bool
| LambdaTerm String Term
| AppTerm Term Term
| BinOpTerm String Term Term
| IfTerm Term Term Term
eval :: Term -> Env -> Term
eval (VarTerm var) env = env Map.! var
eval (IntTerm x) _ = (IntTerm x)
eval (BoolTerm x) _ = (BoolTerm x)
eval (LambdaTerm var body) _ = (LambdaTerm var body)
eval (AppTerm f_term x_term) env =
let (LambdaTerm var body) = eval f_term env
x_val = eval x_term env
in eval body (Map.insert var x_val env)
eval (BinOpTerm op x_term y_term) env =
if op=="=="
then let (IntTerm x) = eval x_term env
(IntTerm y) = eval y_term env
in BoolTerm (x==y)
else let f = (Map.fromList [("+",(+)),("-",(-)),("*",(*))]) Map.! op
(IntTerm x) = eval x_term env
(IntTerm y) = eval y_term env
in IntTerm (f x y)
eval (IfTerm cond_term then_term else_term) env =
let (BoolTerm x) = eval cond_term env in
if x then eval then_term env else eval else_term env
z_combinator :: Term
z_combinator =
(LambdaTerm "f"
(AppTerm
(LambdaTerm "x"
(AppTerm
(VarTerm "f")
(LambdaTerm "y"
(AppTerm
(AppTerm
(VarTerm "x")
(VarTerm "x"))
(VarTerm "y")))))
(LambdaTerm "x"
(AppTerm
(VarTerm "f")
(LambdaTerm "y"
(AppTerm
(AppTerm
(VarTerm "x")
(VarTerm "x"))
(VarTerm "y")))))))
fac :: Term
fac = AppTerm z_combinator h
h :: Term
h =
(LambdaTerm "fac"
(LambdaTerm "n"
(IfTerm
(BinOpTerm "==" (VarTerm "n") (IntTerm 0))
(IntTerm 1)
(BinOpTerm "*"
(VarTerm "n")
(AppTerm (VarTerm "fac")
(BinOpTerm "-" (VarTerm "n") (IntTerm 1)))))))
top_term :: Term
top_term = (AppTerm fac (IntTerm 5))
main = let (IntTerm result) = eval top_term Map.empty in print result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment