Assignment 9: Continuations

Parameters:

  • Due date: Wednesday April 17 at 11:59PM
  • Upload your solution as a main.ml file on Gradescope.
  • Starter code available here
  • 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) and whether your solution is in continuation-passing style.

Problem 1: Continuation-passing Style [30 pts]

Convert the following functions into continuation-passing form (i.e., all calls must be tail-calls). For each part, you will receive credit for the fraction of our test suite that your solution passes. However, if your solution does not utilize continuations or is not in tail form, you will receive 0 credit.

Problem 1a: Prime Factors [10 pts]

Consider the following function factors, which compute all prime factors of a positive integer:

(* Helper function for 'factors'. *)
let rec factors_helper (n: int) (d: int): int list =
  if n = 1 then []
  else if (n mod d) = 0 then d::(factors_helper (n / d) 2)
  else factors_helper n (d + 1) ;;
              
(* Computes all of the prime factors of n. *)
let factors (n: int): int list =
  factors_helper n 2 ;;

Example usage:

# factors 1 ;; (* Note, 1 is not a prime number and has no prime factors! *)
- : int list = []
# factors 7 ;; (* 7 is prime, so its only factor is 7. *)
- : int list = [7]
# factors 4662 ;;
- : int list = [2; 3; 3; 7; 37]

Write factors in tail form by implementing both factors_cps and factors_helper_cps provided in the starter code; do not change the types of these functions.

Problem 1b: Binary Trees with Prime Vertices [10 pts]

Recall our binary tree data structure:

(* Represents a binary tree. *)
type btree =
  | Leaf of int 
  | Node of int * btree * btree ;;

Consider the following function all_prime, which returns true if all of the vertices (both leaves and nodes) in the provided binary tree are prime numbers:

(* Returns true if all vertices (leaves & nodes) in a btree are prime; 
   otherwise, returns false. *)
let rec all_prime (t: btree): bool =
  match t with
  | Leaf(n) ->
      let num_factors = List.length (factors n) in
      num_factors = 1
  | Node(n, l, r) ->
      let num_factors = List.length (factors n) in
      let n_prime = num_factors = 1 in
      let left_prime = all_prime l in
      let right_prime = all_prime r in
      n_prime && left_prime && right_prime ;;

Example usage:

# all_prime (Leaf(1)) ;;
- : bool = false
# all_prime (Node(13, Leaf(7), Node(11, Leaf(31), Leaf(101)))) ;;
- : bool = true

Write all_prime in tail form by implementing both all_prime_cps and all_prime_helper_cps. Again, do not change the types of these functions.

Problem 1c: Zip [10 pts]

Consider the following function zip_with, which combines two lists with respect to some “zipping” function $f$:

(* Zips two lists into a single list, given a function that combines list 
   elements pair-wise. *)
let rec zip_with (x: 'a list) (y: 'b list) (f: 'a -> 'b -> 'c): 'c list =
  match x, y with
  | [], [] -> []
  | x::xs, y::ys -> (f x y)::(zip_with xs ys f) 
  | _ -> raise Runtime

Example usage:

# zip_with [1] [] (fun x -> fun y -> x) ;;
Exception: Runtime.
# zip_with [0; 1; 2] [1; 1; 1] (fun x -> fun y -> (x + y)) ;;
- : int list = [1; 2; 3]

Write zip_with in tail form by implementing both zip_with_cps and zip_with_helper_cps. Note, you may use the provided assert_runtime function for testing whether calls to zip_with_cps or zip_with_helper_cps throw a Runtime exception.

Problem 2: Try-catch Continued [40 pts]

Many programming languages, like OCaml, allow programmers to catch and handle different variants of exceptions separately:

exception Odd_number_exception ;;

(* Returns true if the provided integer is even; returns false otherwise. *)
let is_even (n: int): bool =
  try
    (try 
       (try 
          if n = 0 then raise (Invalid_argument "zero is even!")
          else if (n mod 2) = 0 then raise Division_by_zero
          else raise Odd_number_exception
        with 
        | Division_by_zero -> true)
     with
     | Odd_number_exception -> false)
  with
  | Invalid_argument(_) -> true ;;

Notice, because Odd_number_exception is not handled by the third (inner-most) try block, it bubbles up and is caught by the second try block. Likewise, any raised Invalid_argument exception bubbles up past the second and third try blocks before being caught caught by the first (outer-most) try block. Hence, this function works as intended:

# is_even 2 ;;
- : bool = true
# is_even 7 ;;
- : bool = false

In this problem, we will extend the try-catch language from lecture to include an arbitrary number of exception handlers, following the semantics of the OCaml code presented above.

Consider the following $\lambda$-calculus with try-catch:

module StringMap = Map.Make(String) ;;

(* Syntax for expressions in the extended try-catch language. *)
type texp =
  | Var of string
  | Lam of string * texp
  | App of texp * texp 
  (* Follows the syntax: Try(try_exp, exception_code, catch_exp) *)
  | Try of texp * int * texp
  (* Follows the syntax: Raise(exception_code) *)
  | Raise of int ;;

(* Syntax for values in the extended try-catch language. *)
type tvalue = 
  (* Follows the syntax: Lam(x, closure, body) *)
  | Lam of string * tvalue StringMap.t * texp ;;

Your primary task is to implement the interpreter interp_h, a continuation-passing style interpreter that interprets expressions from the texp language. This interpreter should satisfy the following criteria:

  1. Var, Lam, and App correspond to variables, $\lambda$ terms, and function application in the $\lambda$-calculus, respectively.
  2. Raise follows the syntax Raise(exception_code), where exception_code is an integer representing the variant of exception that is raised.
  3. Try follows the syntax Try(try_exp, exception_code, catch_exp). Try will attempt to interpret try_exp and catch any raised exceptions with code exception_code by interpreting catch_exp. If an exception with a different code than exception_code is raised, then it “bubbles up” (as illustrated in the example above).
  4. If the interpreter encounters an uncaught exception, it raises an Uncaught_exception exception.
  5. If the interpreter encounters an unbounded variable, it raises a Runtime exception.

After completing your implementation of interp_h, implement interp, which calls interp_h with an initial environment, default continuation, and hanlder map.

Example usage:

# interp (Try(Raise(0), 0, Lam("x", Var("x")))) ;;
- : tvalue = Lam ("x", <abstr>, Var "x")
# interp (Try(Raise(1), 0, Lam("x", Var("x")))) ;;
Exception: Uncaught_exception.

Note, in order to receive full credit for your solution, interp_h must utilize continuations and be in tail form. You may use the provided assert_runtime and assert_uncaught functions while testing if calls to interp or interp_h raise a Runtime or Uncaught_exception, respectively.

Problem 3: The A Normal Form [30pts]

A Normal Forms (ANF)

A Normal Form (ANF) is one of the most well-studied and used representations of functional programs. It was discovered by Amr Sabry and Matthias Felleisen (yes, Northeastern’s Matthias) in 1992 as an alternative to CPS transformations.

The core idea of ANF is to eliminate nested computation by allowing only constants or variables in function arguments. For example, the arithmetic expression

(2 + 3) * 4

will instead be

let x  = 2 + 3 in
let x' = x * 4 in
x'

Why would we want to do this? The answer is that we eventually want to compile functional languages to an instruction set like assembly code. You might remember from Assignment 8 that implementing a direct translation of nested computation (like Pairs) directly to assembly was tricky. But in an ANF grammar, translating to an assembly-like language is drastically simplified.

ANFARM Assembly Pseudocode
let x = 2 + 3 in
let x' = x * 4 in
x'		ADD R0, #2, #3
MUL R0, R0, #4
END

In the pseudocode above, we are first loading register 0 with the value of adding 2 and 3. Then, we multiply the contents of register 0 by 4 then replace with that value. Then, we end our program by returning the contents of register 0.

The intuition as to why the translation is so simplified is because ANF requires every function (such as + and *) to terminate in exactly one step, much like assembly languages do.

Problem Statement

Consider the following grammar of a simple arithmetic language:

type calc = 
  | Const of int
  | Add   of calc * calc
  | Mul   of calc * calc
  | Sub   of calc * calc
  | Div   of calc * calc

Your task is to convert arithmetic expressions into the following ANF grammar:

type value = Var of string | Const of int

type arith_anf = 
  | Val of value
  | Add of value * value
  | Mul of value * value
  | Sub of value * value
  | Div of value * value

type calc_anf = 
  | Finally of arith_anf
  | Let   of string * arith_anf * calc_anf

We suggest you experiment with the given functions eval_calc and eval_calc_anf to get a feel

Problem 3.[30pts]

Implement to_anf, a function of type calc -> calc_anf that converts a nested arithmetic expression into ANF. To do this you must implement a helper function to_anf_h of type calc -> (value -> calc_anf) -> calc_anf that will guide the recursive ANF transformation using continuations.

Your to_anf_h must be written in tail-form: not using tail-form will receive a score of zero points, regardless of autograder output.

Additionally, using eval_calc anywhere in your solution besides tests will receive a score of zero points, regardless of autograder output.

To earn all points, the following must be true for all e : calc:

eval_calc e = eval_calc_anf (to_anf e)

You may use the provided helper function fresh, in which invoking fresh () will generate a string of a fresh variable name.

Hint: There are several valid outputs of to_anf, some easier to implement than others. For example, the following are all valid outputs of to_anf (Mul (Add (Const 2, Const 3), Const 4)):

Let ("x0", Add (Const 2, Const 3),
  Let ("x1", Mul (Var "x0", Const 4), 
    Finally (Val (Var "x1"))))

Let ("x0", Add (Const 2, Const 3),
  Finally (Mul (Var "x0", Const 4)))

Let ("x0", Val (Const 2),
  Let ("x1", Val (Const 3), 
    Let ("x2", Add (Var "x0", Var "x1"), 
      Let ("x3", Val (Const 4), 
        Let("x4", Mul(Var "x2", Var "x3"),
          Finally (Val (Var "x4")))))))