Project 1c

Due Date: Thu 20 Oct

In this project, you will extend the arithmetic expression language from project 1b to a simple lambda calculus (the computational model underlying functional programming languages).

Abstract Syntax

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:
  • 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):
    1. 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.)
    2. The second expression is evaluated in the current environment.
    3. 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.)
    1. The condition is evaluated. (If the result is not an integer constant, then there is an error.)
    2. If the condition is non-zero, the result is the result of evaluating e1.
    3. 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.
    1. If e evaluates to a number, that is the result.
    2. 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

Comments