Mini-Project 2: The Environment Model

One-Week Check-in

For the one-week check-in, you must submit:

• (10%) An implementation of desugar, as detailed in the mini-project specification. You should be able to leave your implementations of the other functions partial or empty as long as your code builds.
• (30%) Solutions to the written problems below.

Note. We will not re-test parts of the mini-project from the one-week check-in. To recieve full credit on the mini-project, you must successfully submit both the one-week check-in and the complete mini-project.

Written Problems

Desugaring

let rec even (n : int) : bool =
  let rec odd (n : int) : bool =
    if n = 0
    then false
    else even (n - 1)
  in
  if n = 0
  then true
  else odd (n - 1)

let add (x : int) (y : int) : int = x + y

let five_plus_five_is_even : bool = even (add 5 5)

Desugar the above program according to the desugaring rules given in the mini-project 2 specification (please use reasonable indentation to make it easier on our graders).

Closures

let x : int = 1 in
let f : int -> int =
  let x : int = 2 in
  fun (y : int) -> x + y
in
let g : int -> int = fun (x : int) -> x in
g

Determine the closure which the above expression evaluates to according to the semantic rules given in the mini-project 2 specification.

Semantic Derivations

let f : int -> int =
  let x : int = 2 in
  fun (y : int) -> x
in f 1

Let e_1 be defined as above. Determine a value v such that \langle \varnothing, e_1 \rangle \Downarrow v is derivable using the semantic rules of mini-project 2. Provide the derivation.

let f = let x = 2 in fun y -> x in f 1

Let e_2 be defined as above. Determine a value v such that e_2 \Downarrow v is derivable using the semantic rules of mini-project 1. Provide the derivation.