- lambda x . e: anonymous function, that is, a designated formal argument x along with a function body in which x occurs zero or more times
- x: variable (presumably occurring in an expression with ancestor that is a lambda expression introducing x as a formal argument)
- e1 e2: function application, that is, an expression (presumably representing a function) followed by another expression (presumably representing an actual argument)
- if c then e1 else e2: conditional
- Rec: fixed-point operator, which can be applied to an expression e to provide a declaration-free equivalent of recursion
We will worry about concrete syntax (strings that would be parsed into an equivalent abstract syntax tree) in a later phase of this project.
Semantics
The semantic domain (values) is a subdomain of the abstract syntactic domain consisting only of
- integer constants
- function closures
Next, you will define a function for evaluating expressions represented using the abstract syntax defined above using
call-by-value. (You will explore
call-by-name evaluation in a subsequent phase of this project. See also
this reference.) This function takes two arguments:
- an expression that follows the abstract syntax defined above
- an environment, which maps variable names to values
and returns a value from the semantic domain.
- To evaluate an arithmetic expression, simply incorporate your solution to project 1b.
- An anonymous function definition evaluates to a closure of itself, that is, the same function but with the current environment appended to the environment the function already carries (initially empty, see below).
- A variable evaluates to its associated value in the current environment. If the variable is not found in the current environment, then there is an error.
- A function application is evaluated as follows (this is where the evaluation order is decided):
- The first expression is evaluated in the current environment. (If it the result is not a function closure, lambda x . b, then there is an error.)
- The second expression is evaluated in the current environment.
- The function body b is evaluated in an environment that maps x to the result of the second expression and is otherwise the current environment appended to the environment of the closure.
- A conditional is evaluated as follows. (Note that it is non-strict in e1 and e2, otherwise it would defeat the purpose.)
- The condition is evaluated. (If the result is not an integer constant, then there is an error.)
- If the condition is non-zero, the result is the result of evaluating e1.
- Otherwise the result is the result of evaluating e2.
- The application (Rec e) of the fixed-point operator Rec to a expression e is evaluated as follows.
- If e evaluates to a number, that is the result.
- Otherwise e evaluates to a function closure, lambda f . b, and the result is obtained by evaluating b in an environment that maps f to the (unevaluated) b and is otherwise the current environment appended to the environment of the closure. In this way, when b is evaluated, occurrences of f inside b are mapped to b, thereby producing the effect of recursion.
Examples
eval (Var "x") [] -> error
eval (Var "x") ["x" -> Const 3] -> Const 3
eval (mkFun("x",Plus(Const 7,Var("x")))) [] -> Fun("x",Plus(7,Var("x")),[])
eval (App(mkFun("x",Plus(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(Var "y",Const 3,Const 4)) ["y" -> 7] -> Const 3
eval (If(mkFun("x",Var "x"),Const 3,Const 4)) [] -> Const 3
eval (App(Rec(mkFun("f",mkFun("n",If(Var "n",Times(Var "n",App(Var("f"),Minus(Var "n",Const 1))),Const 1)))),5) [] -> Const 120
where mkFun(x, b) = Fun(x, b, Map.empty). Also, the map syntax [...] used here is pseudo-code; you will have to use Map.add x v Map.empty to add mappings, as well as Map.ofList.
References