Instructions

  • Deadline: Friday March 29, 2024.
  • 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). Only ask questions relating to the quiz as private Piazza questions.
  • 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.
  • Note: The autograder score is not your final score.
  • The quiz is graded out of 100 points in total.
  • Logistic note: on this quiz, we will be answering questions on Piazza during three specific time windows: 1-2PM on Thursday, 1-2PM on Friday, and 4-5PM on Friday. We will not answer any quiz-related questions on Piazza outside of these times.

Problem 1: OCaml Programming [26 points]

Problem 1a [13 points]

Consider the following binary tree data-structure:

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

Write a function even_even that takes a btree as an argument and returns true if and only if there are an even number of vertices (this includes both Leaf and Node variants) with an even value.

Example usage:

# even_even (Node(3, Leaf(-5), Leaf(0))) ;;
- : bool = false
# even_even (Node(3, Node(2, Leaf(-1), Leaf(13)), Leaf(0))) ;;
- : bool = true

Note, to do modular arithmetic in OCaml, you need the mod keyword:

# 7 mod 3 ;;
- : int = 1

Problem 1b [13 points]

Write a function longest_string that takes a string list as an argument and returns the first string with the greatest length. If the provided string list is empty, then the function should raise a Runtime exception.

Example usage:

# longest_string [] ;;
Exception: Runtime.
# longest_string ["cat"; "dog"] ;;
- : string = "cat"

Note, you may use the provided assert_runtime function for testing whether calls to longest_string throw a Runtime exception.

Problem 2: Garbage Collection [12 points]

Recall the Micro-C language with mark-and-sweep garbage collection discussed during lecture

type microc =
  | Let of { id: string; binding: microc; body: microc }
  | Var of string
  | Malloc
  | Gc (* triggers mark-and-sweep garbage collection *)
  | Free of microc
  | Set of {loc: microc; value: microc}
  | Deref of {loc: microc}
  | Num of int ;;

type value =
  | VNum of int
  | VLoc of int ;;

and consider the following program

let exp: microc = 
  Let("x", Let("x", Malloc,
               Let("y", Malloc, 
                   Let("z", Malloc, 
                       Let("_", Set(Var("x"), Num(10)),
                           Let("_", Set(Var("y"), Var("x")),
                               Let("_", Set(Var("z"), Var("x")),
                                   Var("z"))))))),
      Let("y", Gc, (* line A *)
          Var("x"))) ;; (* line B *)

Suppose we run the program exp shown above, using the interp_c interpreter discussed in lecture. Which of the following pairs are marked as free in the heap once we reach line B and after mark-and-sweep garbage collection is performed on line A?

  1. $``x” \mapsto \mathrm{VNum}(10)$
  2. $``y” \mapsto \mathrm{VNum}(10)$
  3. $``z” \mapsto \mathrm{VNum}(10)$
  4. $0 \mapsto \mathrm{VNum}(10)$
  5. $1 \mapsto \mathrm{VLoc}(0)$
  6. $2 \mapsto \mathrm{VLoc}(0)$

For each answer that applies, write true in the corresponding definition in the starter code; otherwise, write false.

Problem 3: Dynamic Safety [50 points]

Because dynamic safety ensures that values have the correct type at runtime, we are sometimes able to write programs which could not be expressed in a statically-typed language. For example, consider the following Python code:

>>> def f(b):
...   if b:
...     return True
...   else:
...     return 20
... 
>>> 10 + f(False)
30
>>> 10 + f(True)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'bool'

Notice, we are able to write if statements that return a bool or an int. In this problem, we will reimplement the if-lang from earlier in the semester with dynamic safety in order to support conditionals that may either return a bool or an int.

For this problem, we will slightly alter our micro-assembly language to include a version of the compare-select syntax:

(* Represents an expression in the tiny assembly language. *)
type tinyasm = 
  | Load of { reg: int; addr: int } 
  | Store of { reg : int; addr: int } 
  | Setreg of { reg: int; value: int } 
  | Trap of int 
  | AddInt 
  (* If the value in register 0 is 0, then sets register regr to the value in 
     regf (the false case); otherwise, sets register regr to the value in regt 
     (the true case). *)
  | CSel of { regr: int; regt: int; regf: int }
  | Ret ;;

As stated in the comment, the semantics of CSel are, if the current value in register 0 is 0 (false), then we set register with ID regr to the value in register regf; otherwise, if the current value in register 0 is not 0 (true), then we set register with ID regr to the value in register regt.

Your task is to implement the function safe_if_to_asm, which compiles the following language into tinyasm with dymanic safety:

(* Represents an expression in the if-lang. *)
type ifexp =
  | Num of int
  | Bool of bool
  | Add of ifexp * ifexp 
  (* Follows the syntax: If(guard, then, else) *)
  | If of ifexp * ifexp * ifexp ;;

In order for your compiler to be considered complete with dynamic safety, we require that:

  1. If the guard of an If expression is not a boolean, then a Trap must be thrown from within the tiny assembly interpreter;
  2. If either the left or right expression of an Add is not a number, then a Trap must be thrown from within the tiny assembly interpreter;
  3. The then and else branches of an If expression may have different types;
  4. Like in lecture, safe_if_to_asm (Bool(true)) evalutes to 1 and safe_if_to_asm (Bool(false)) evalutes to 0.

After completing your implementation of safe_if_to_asm, implement run_if_safe, which compiles a ifexp program into tinyasm and then runs it using the tiny assembly interpreter.

Example usage:

# run_if_safe (Add(If(Bool(true), Num(25), Num(0)), Num(-23))) ;;
- : int = 2
# run_if_safe (If(Num(-43), Bool(false), Bool(true))) ;;
Exception: Trap.

Note, you may use the provided assert_trap function for testing whether calls to run_if_safe throw a Trap exception. We have given you substantial starter code for this problem.

Problem 4: Rust [12 points]

Consider the following Rust program:

fn gobble(a : Box<u64>) -> () {
    println!("nom {}", *a);
}

fn gobble2(b : &u64) -> () {
    println!("nom {}", *b);
}

fn gobble3(c : Box<&u64>) -> () {
    println!("nom {}", *c);
}

fn main() {
    let x = Box::new(10);
    let y = Box::new(*x);
    let z = Box::new(30);
    gobble(y);
    gobble2(&x);
    gobble3(Box::new(&z));
}

State whether each of the following is true or false about the above Rust program (put your answers in the relevant part of the starter code):

  1. All dynamically allocated memory can only be safely freed only after main finishes executing.
  2. When gobble is called, ownership of the location allocated by Box::new(*x) is moved from y to a.
  3. When gobble2 is called, ownership of the location allocated by Box::new(10) is moved from x to b.
  4. At the end of main, x owns the location allocated by Box::new(10)
  5. When gobble3 is called, ownership of the location allocated by Box::new(30) is moved from z to c.
  6. The location allocated by Box::new(&z) is freed once gobble3 finishes executing.