Project 1d

Due Date: Thu 4 Nov

In 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). 
  1. The first expression is evaluated. (If it the result is not a function closure, lambda x . b, then there is an error.)
  2. Beta substitution is performed to substitute the second expression (without evaluating it) for every free occurrence of x in b.
  3. The resulting function body (after the substitution) is evaluated.

Examples

eval (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
Comments