Created
December 19, 2014 09:34
-
-
Save TerrorJack/224b21657cc82f079413 to your computer and use it in GitHub Desktop.
Call-by-value lambda calculus interpreter (which won't work)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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