Assignment 7: Welcome to OCaml

Parameters:

  • Due date: Wednesday March. 20 at 11:59PM
  • Use the following starter code
  • Upload your solution as a main.ml file on Gradescope.
  • Ask questions on Piazza or during Office Hours.
  • Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code.
  • Grading: each problem is worth a certain number of points. The points given for each problem is the fraction of tests passed for that problem (i.e., if 50% of the tests are passed for a 20 point problem, 10 points are given).
  • Resources: Chapters 2 and 3 of this online textbook.
  • Note: The autograder score is not your final score on this assignment: some test cases will be withheld. Be sure to test your code thoroughly using assertions!

Problem 1: Basic OCaml

Problem 1a: Basic lists [10 Points]

Write a function sum_if l f of type int list -> (int -> bool) -> int that sums all elements of l for which f evaluates to true.

Example:

> sum_if [0; 1; 2] (fun x -> true);;
- : int = 3

Problem 1b: Basic trees [10 Points]

Consider the following binary tree datastructure:

type btree =
  Leaf of int
  | Node of int * btree * btree

Write a function sum_tree_if t f of type btree -> (int -> bool) -> int that takes arguments that sums all numbers in t which f evaluates to true. Example:

> sum_tree_if (Node(5, Leaf(10), Leaf(20))) (fun _ -> true);;
- : int = 35

Problem 2: $\lambda$-calculus with closures [40 Points]

In class we saw how to implement the untyped $\lambda$-calculus with substitution. In this exercise we will make an efficient untyped $\lambda$-calculus interpreter using environment-passing in OCaml. We will use the following AST for a $\lambda$-calculus with application, $\lambda$-abstraction, let-binding, numbers, and addition:

type lexp =
  (* (e1 e2) *)
    App of lexp * lexp 
  (* lambda x . e *)
  | Abs of string * lexp
  (* let x = e1 in e2 *)
  | Let of string * lexp * lexp
  | Var of string
  | Num of int
  | Add of lexp * lexp

In this exercise we will make an interpreter for lexp that uses environment passing. Recall that an environment maps names to values; we will be using a StringMap for our environment. See the course notes section on “Using hashmaps” for a brief discussion on how to use hashmaps in OCaml. Our language has 2 kinds of values: $\lambda$-abstractions and numbers. So, we define values in the following way:

module StringMap = Map.Make (String)

type lamvalue =
  (* LamV(closure, argument, body) *)
  | LamV of lamvalue StringMap.t * string * lexp
  | NumV of int

type env = lamvalue StringMap.t

let mt_env = StringMap.empty

exception Runtime of string

You probably noticed something odd about the type of LamV: it has an unexpected additional piece of data of type env. This is called a closure, and in this assignment you will have to figure out why it is there! (Hint: it has to do with scope!)

Your task is to implement a function interp_l env e of type env -> lexp -> lamvalue that interprets lexp terms using environment passing. You will receive no credit if you use substitution in your solution. We will evaluate your solution based on the fraction of test cases that pass. Your implementation should raise a Runtime exception if you encounter a runtime error; see the course notes on exceptions.

Example usage:

(* let x = (fun y -> y + y) in x 10 *)
> let p1 = Let("x", Abs("y", Add(Var("y"), Var("y"))), App(Var("x"), Num(10)));;
> interp_l mt_env p1;;
- : lamvalue = NumV 20

Problem 3: Type-safe references in OCaml [40 Points]

Recall the type-safe references discussion from Lecture 12. In this exercise, we will be translating this example into OCaml.

3a: An interpreter [20 Points]

Our goal will be to write an interpreter for a tiny language called hexp with Box, Unbox, Set:

(* atoms do not affect the heap *)
type atom =
  | Num of int
  | Var of string

type hexp =
  Let of string * hexp * hexp
  | Box of atom
  | Unbox of atom
  | Set of atom * atom
  | Atom of atom

Our language has two kinds of values, numbers and locations, which we represent in the following datatype:

type hvalue =
  | NumV of int
  | LocV of int

To represent the heap, we will define heap record that keeps track of (1) the next fresh address in the heap, and (2) a state map that maps integer locations to values:

type heap = { fresh: int; state: hvalue IntMap.t }

(** returns a pair (new_loc, new_heap) where new_heap is the result of inserting value
    into h at location loc *)
let alloc_heap (h:heap) (value:hvalue) : int * heap =
  let ret_address = h.fresh in
  let new_heap = IntMap.add ret_address value h.state in
  (ret_address, { fresh = ret_address + 1; state = new_heap })

(** looks up location in h *)
let lookup_heap (h:heap) (loc:int) : hvalue =
  IntMap.find loc h.state

(* returns a new heap equal to h except at location loc is equal to v *)
let update_heap (h: heap) (loc:int) (v:hvalue) =
  { fresh = h.fresh; state = IntMap.add loc v h.state }

let empty_heap = { fresh = 0; state = IntMap.empty }

Similar to the previous exercise, we define an environment of type henv that maps strings to heap values:

type henv = hvalue StringMap.t

Your task is to write a function interp_h env heap e of type henv -> heap -> hexp -> heap * hvalue that evaluates terms of type hexp and returns a pair (new_heap, return_value).

Example:

> let hp1 = Let("x", Box(Num(10)), Unbox(Var("x")));;
> (snd (interp_h StringMap.empty empty_heap hp1));;
- : hvalue = NumV(10)

There is no requirement to use a particular address to store a value in the heap. We will evaluate your solution based on the fraction of tests that match the expected return_value. Your interpreter should raise a Runtime exception if it encounters invalid runtime behavior.

3b: A typechecker [20 Points]

Now we will make a typechecker to ensure that we do not trigger runtime errors in our interpreter.

We will use the following datatypes:

(* possible types *)
type typ =
  TNum
  | TRef of typ

(* type environment: maps strings to types *)
type tenv = typ StringMap.t

(* typecheck exception to be raised if there is a type error *)
exception Typecheck of string

Your task: Write a function type_of tenv e of type typ StringMap.t -> hexp -> typ that gives the type of e, or raises a Typecheck exception if there is no valid type. The typing rules should match the typing rules in Lecture 12. Examples:

(* let x = ref 10 in !x *)
> let hp1 = Let("x", Box(Num(10)), Unbox(Var("x")));;
> type_of StringMap.empty hp1;;
- : typ = TNum

> let hp2 = Let("x", Box(Num(10)),
              Let("y", Set(Var("x"), Num(20)),
                  Unbox(Var("x"))));;
> type_of StringMap.empty hp2;;
- : typ = TNum