Assignment 8: Dynamic Safety

Parameters:

  • Due date: Thursday March. 28 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!

Dynamic safety for pairs [100 Points]

On this assignment you extend the dynamic safety compiler from lecture 16 to handle pairs.

Our micro assembly language is slightly different from the lecture for this assignment, and has the following abstract syntax:

(** a memory unsafe language *)
type asm =
  (* load heap[addr] into reg *)
  | Load of { reg: int; addr: int }
  (* load heap[register[loc_reg]] into reg *)
  | Dynamicload of {reg: int; loc_reg: int}
  (* store register[reg] into heap[addr] *)
  | Store of { reg : int; addr: int }
  (* set register[reg] = value *)
  | Setreg of { reg: int; value: int }
  (* trap: gives a runtime error if register[0] != v *)
  | Trap of int
  (* set register[0] = register[1] + register[2] *)
  | AddInt
  | MulInt
  (* terminate *)
  | Ret

The new instruction is Dynamicload, which loads the location in register loc_rec into reg.

Your goal in this assignment is to compile the following abstract syntax into asm:

type exp =
  | Let of { id: string; binding: exp; body: exp }
  | Var of string
  | Fst of exp
  | Snd of exp
  | Pair of exp * exp
  | Num of int

The semantics of exp is identical to similar languages we have seen in class involving pairs from Lecture 12. We have provided helper functions for running your compiler.

You should fill in the function safe_ast_to_asm with your code, and you should not change its type. Your implementation should raise a Trap exception if an illegal operation is performed (for instance, calling Fst or Snd on a non-pair). We will only test your solution on programs that evaluate to numbers. Here are some examples:

> run_safe Fst(Pair(Num(10), Num(20)));;
- : int = 10

> run_safe (Snd(Num(10)));;
Exception: Trap.

> run_safe (Let{id="x"; binding=Num(10); body=Var("x") });;
- : int = 10

This assignment is quite tricky and will require some low-level programming in assembly. Here are some tips:

  • If you are encountering errors, you may want to try using #trace interp_asm;; in your top-level environment to see output as it runs. This will let you inspect the heap and register state as your code executes.
  • Use assertions to help diagnose errors.