here (except that we do not yet have a list type).
Specifically, you will define an algebraic data type (discriminated union type) that includes the variants for arithmetic expressions along with the following functional language constructs:
We will worry about concrete syntax (strings that would be parsed into an equivalent abstract syntax tree) in a later phase of this project.
The semantic domain (values) is a subdomain of the abstract syntactic domain consisting only of
Next, you will define a function for evaluating expressions represented using the abstract syntax defined above using call-by-name (normal-order evaluation). This function takes an expression that follows the abstract syntax defined above and reduces it to a value from the semantic domain.
If an (unbound) variable occurs in the result of an evaluation, then there is an error.
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.
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(Const 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