Instructions

  • Deadline: Friday April 19 at 11:59PM.
  • We will answer questions on Piazza between 1–2pm on Thursday, between 1–2pm on Friday, and between 4–5pm on Friday. Ask all questions as private Piazza questions.
  • Starter code: here
  • This quiz is to be completed on your own. Please do not consult with classmates. You are permitted to use the course notes and an installation of OCaml (either locally or with the online tool from class).
  • Upload a single file called main.ml to GradeScope. Your upload should be valid OCaml: be sure your upload runs without errors. Use the provided starter code.
  • You should consult primarily with the course notes and the course textbook while answering questions on this quiz.
  • The autograder score is not your final score.
  • The quiz is graded out of 100 points in total.

Problem 1: Reasoning about continuations [10pts]

Below are two different implementations of the higher-order function map.

let rec map l f = map_h l f (fun x -> x)  
and map_h l f k = match l with
| [] -> k []
| x :: xs -> map_h xs f (fun c -> k ((f x) :: c))

let rec map2 l f = map2_h l f (fun x -> x)
and map2_h l f k = match l with
| [] -> k []
| x :: xs -> map2_h xs f (fun c -> (f x) :: (k c))

Problem 1.1 [2.5pts] What is the type of k in map_h and map2_h? No partial credit will be awarded.

(a) int list -> 'a list

(b) 'a list -> 'a list

(c) 'a list -> 'b list

(d) ('a list -> 'b list) -> 'b list

Problem 1.2 [5pts] Which ones, if any, are written in continuation passing style? No partial credit will be awarded.

(a) None

(b) map_h

(c) map2_h

(d) Both are in CPS.

Problem 1.3 [2.5pts] For a list l and a function f, describe the relationship between the outputs of map l f and map2 l f without referring directly to the code or control context/call stack. No partial credit will be awarded for incorrect answers.

Problem 2: Writing code in continuation passing style [40pts]

Consider the following binary tree with nodes labeled with some type 'a:

type 'a btree = 
| Leaf 
| Node of 'a btree * 'a * 'a btree

Problem 2. [40pts] Write a function exists that takes in four arguments:

  • t : 'a btree,
  • f : 'a -> bool,
  • succ : 'a -> 'b,
  • fail : () -> 'b, and returns succ v if there exists a node Node(_, v, _) in the tree in which f v = true. If there does not exist such a v, then return fail ().

If there are multiple nodes in the binary tree that satisfy f, then the exists calls succ the topmost leftmost such node–the first node encountered in a pre-order traversal of the tree. See the examples below for how this works.

Your answer must be written in contination-passing style; no points will be awarded if your submission is not in CPS.

You may NOT use helper functions or exception handling. No points will be awarded if any helper function, library function, or exceptions are used in the implementation.

Here are some example input-outputs of the function:

exists (Leaf) (fun _ -> true) (fun _ -> 1) (fun _ -> 2) ;;
- : int = 2

exists 
  (Node(Leaf, 2, Leaf)) 
  (fun x -> x - 2 = 0) 
  (fun x -> "wow!") 
  (fun _ -> "not wow!") ;;
- : string = "wow!"

exists 
  (Node(Node(Leaf, "hello", Leaf), "world", Node(Leaf, "!", Leaf))) 
  (fun s -> String.length s = 5) 
  (fun s -> s) 
  (fun _ -> "No string found!") ;;
- : string = "world"

exists 
  (Node(Node(Leaf, "hello", Leaf), "!", Node(Leaf, "world", Leaf))) 
  (fun s -> String.length s = 5) 
  (fun s -> s) 
  (fun _ -> "No string found!") ;;
- : string = "hello"

Problem 3: Control with Continuations [50 Points]

In this problem we will be adding a break construct to a small imperative language with while loops. Intuitively, break immediately terminates the execution of a loop and resumes computation from the end of the loop. Many languages with loops support break statements, such as Python:

>>> for i in range(5):
...     if i == 3:
...         break
...     print(i)
... 
0
1
2

We will use the following grammar for our language:

type impexpr =
  Var of string
  | Add of impexpr * impexpr
  | Lt of impexpr * impexpr
  | Eq of impexpr * impexpr
  | Num of int

type impstmt =
  Assgn of string * impexpr
  | While of { guard: impexpr; body: impstmt }
  | Break_if of impexpr
  | Seq of impstmt * impstmt

type impprog = { body: impstmt; ret: impexpr }

The semantics of While { guard; body } are: If guard evaluates to true in the current environment, then execute Seq(body, While { guard; body }). Otherwise, do nothing.

The semantics of Break_if are:

  • If Break_if is executed outside the context of a loop, it does nothing.
  • If the argument of Break_if evaluates to true inside of a loop, then the inner-most loop should immediately terminate.

An impprog first (1) runs body from an empty environment, and then (2) runs ret and returns whatever ret evaluates to.

This example is analogous to the above Python example, and executes a while loop that increments x until 3 < x, at which point it breaks:

let prog = { body=Seq(Assgn("x", Num(0)),
                      While { guard=Lt(Var("x"), Num(5));
                              body = Seq(
                                  Break_if(Lt(Num(3), Var("x"))),
                                  Assgn("x", Add(Var("x"), Num(1))))}); ret=Var("x") } in
assert ((interp_prog prog) = VInt(4))

Your task is to fill in the bodies of interp_stmt_h and interp_prog in the starter code. We have provided you with a type signature for the continuations as well as an implementation for interp_impexpr. Do not change these type signatures (you can think of these type signatures as hints for how to set up your solution; we’ve told you what the continuations should look like).

Problem 4 (CS5400 Only, 20 Points)

This problem is only for students enrolled in CS5400. Students enrolled in CS4400 are not required to complete this problem and it will not be graded.

Problem 4 Part A

State whether the following are true or false (2.5 points each):

  1. Continuations require first-class functions in order to be implemented.
  2. One benefit of tail-form recursion is that it can be more efficient to execute.
  3. You try to run the following Python program:
    >>> "string" + 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate str (not "int") to str

    The above error message is a result of Python’s runtime enforcing dynamic safety.

  4. Unlike C, the Rust language does not support new and free, and therefore is considered a garbage-collected language.
  5. An important design criteria of the type-checkers we studied in class is that they are fast to execute.

Consider the following type-system for the simply-typed lambda-calculus with references:

\[\dfrac{}{\texttt{Γ ⊢ num : Number}}~\text{(T-Num)} \qquad \dfrac{x ∈ Γ \qquad Γ(x) = τ}{\texttt{Γ ⊢ x : }τ}~\text{T-Var}\] \[\dfrac{\texttt{Γ ∪ \{x ↦ τ\} ⊢ e : τ'}} {Γ ⊢ \texttt{λ x:τ. e : τ → τ'}}~\text{(T-Lambda)} \qquad \qquad \dfrac{\texttt{Γ ⊢ e1 : τ → τ'} \qquad \texttt{Γ ⊢ e2 : τ}}{\texttt{Γ ⊢ (e1 e2) : τ'}}~\text{(T-App)}\] \[\dfrac{Γ ⊢ \texttt{e} : τ}{Γ ⊢ \texttt{box e} : \texttt{Ref}~τ}~\text{(T-Ref)} \quad \quad \dfrac{Γ ⊢ \texttt{e} : \texttt{Ref τ}}{Γ ⊢ \texttt{unbox e : τ}}~\text{(T-Unbox)} \quad\quad \dfrac{Γ ⊢ \texttt{e1} : \texttt{Ref τ} \quad\quad Γ ⊢ \texttt{e2} : \texttt{τ}}{Γ ⊢ \texttt{set e1 e2 : TNum}}~\text{(T-Set)}\]

Which of the following are true or false about the above type system (see here for an implementation)? (2.5 points each)

  1. All well-typed programs in the according to the above type-system terminate.
  2. Suppose we changed the rule for T-Set to:
\[\dfrac{Γ ⊢ \texttt{e1} : \texttt{Ref τ}_1 \quad\quad Γ ⊢ \texttt{e2} : \texttt{τ}_2}{Γ ⊢ \texttt{set e1 e2 : TNum}}~\text{(T-Set2)}\]

Then, there is a way to write a well-typed program that causes a runtime error to occur.

  1. Suppose we kept using the T-Set2 rule, but now we eliminate the ability to unbox a value (i.e., we remove the unbox syntax from our language). Then, it is not possible to write a program that causes a runtime error to occur.