Principles of Programming Languages II

A3: Environment-based interpreter

For this assignment you will write an environment-based interpreter for Fb using closures.

Your interpreter must do no substitution when it is running, it needs to follow the lecture and use environments / closures.
Along with the lecture, Leroy's semantics slides define the operational semantics rules which serve as the specification for such an interpreter.
As with the first assignment we will use the FbDK. For this assignment you will write all your code in the file Fb/fbinterp.ml, constructing an eval function there which will in turn invoke your closure-based interpreter.

Here is a suggested expression type which includes closures. (We put an E in front of the standard Fb data type constructors for reasons which will soon become clear.)

type eexpr =
  | EVar of ident | EFunction of ident * eexpr | EAppl of eexpr * eexpr
  | EPlus of eexpr * eexpr | EMinus of eexpr * eexpr | EEqual of eexpr * eexpr
  | EAnd of eexpr * eexpr| EOr of eexpr * eexpr | ENot of eexpr
  | EIf of eexpr * eexpr * eexpr | EInt of int | EBool of bool
  | EClosure of eexpr * envt

and envt = (ident * eexpr) list

Notice the type of closures and environments in the above -- an environment is a list of identifiers and expressions. This is the Association list representation of a mapping, see the List module docs for how List.assoc etc allow lists of key/value pairs to serve as maps. You can alternatively use the OCaml Map module but the mutual recursion between expressions and environments makes this harder.

One issue with re-using the FbDK is the type of expressions above needs to include closures. Rather than redoing the FbDK lexer/parser/etc codebase just write translation functions between the Fb expressions, expr, and the new eexpr type above. Something like

let rec expr_to_eexpr e =
   match e with
       Var(x) -> EVar(x)
     | Int(x) -> EInt(x)
     | Bool(x) -> EBool(x)
     | Let(i, e1, e2) -> EAppl(EFunction(i, expr_to_eexpr e2), expr_to_eexpr e1) (* encode let *)
     | Appl(e1, e2) -> EAppl(expr_to_eexpr e1, expr_to_eexpr e2)
	...

let rec eexpr_to_expr e = ...

Note that since we are writing a translator front-end here anyway we may as well eliminate some syntax to make our jobs easier in the interpreter .. you can see above that I turned Let into an application, and Let Rec can be treated similarly (that is why it is not in the eexpr grammar above).
Assuming your interpreter is eeval : eexpr -> eexpr, with these conversion functions you can then define the top-loop eval : expr -> expr function as
```
let eval e = eexpr_to_expr(eeval (expr_to_eexpr e))
```

For this assignment submit ONLY the file fbinterp.ml with your interpreter code.

PL II