Due Date: Thu 4 NovIn this project, you will redo project 1c but with call-by-name evaluation and without a fixed-point operator in the abstract syntax. This amounts to an almost verbatim implementation of the calculus described here (except that we still don't have a list type).In particular, you should implement a separate auxiliary function for beta substitution. Then use this function in the evaluation of function application. There will be no environment anymore for evaluation or function closures. A function application is evaluated as follows (this is where the evaluation order is decided).
Exampleseval (Var "x") -> error (* your eval function should no longer include a branch for Var *) eval (Fun("x",Plus(Const 7,Var("x")))) -> Fun("x",Plus(7,Var("x"))) eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3)) -> Const 10 eval (App(Var("x"),Const 3) -> error eval (If(Const 7,Const 3,Const 4)) -> Const 3 eval (If(Const 0,Const 3,Const 4)) -> Const 4 eval (If(Fun("x",Var "x"),Const 3,Const 4)) -> Const 3 eval (If(Fun("x",Var "y"),Const 3,Const 4)) -> Const 3 let Y = (* you get to define it yourself, as in the handout -- this is cool! *) eval (App(App(Y, Fun("f",Fun("n",If(Var "n",Times(Var "n",App(Var("f"),Minus(Var "n",Const 1))),Const 1)))), Const 5) -> Const 120 |
Teaching > Comp 371/471: Theory (and Practice) of Programming Languages > Projects > Fall 2010 >