Skip to content

Homework 11: Compiling

Due: Sunday, November 23rd, 11:59pm

Start with the template code here.

  • Replace each failwith "TODO" with your solution.
  • Be sure to test your solutions in utop or in tests alongside your submission. To load your file into utop, use #use "hw11.ml";;.
  • Submit your version of hw11.ml to the HW11 assignment on Gradescope. Only submit hw11.ml; NOT any other files or folders.
  • At the top of the template file, there is a comment for you to write in approximately how many hours you spent on the assignment. Filling this in is optional, but helpful feedback for the instructors.

Compiling from MiniPython to StackLang

In this homework, we will continue analyzing MiniPython, which we looked at in HW10. Below is our language, MiniPython (also found in the template file):

MiniPython 
module StringMap = Map.Make(String)

type value = int
type op = | Add | Mul | EQ | Sub | Gt

let eval_binop (o : op) (v1 : value) (v2 : value) : value = 
    match o with 
    | Add -> v1 + v2
    | Mul -> v1 * v2
    | Sub -> v1 - v2
    | EQ -> if v1 = v2 then 1 else 0
    | Gt -> if v1 > v2 then 1 else 0

module MiniPython = struct
type expr = | Value of value | Var of string | App of op * expr list

type cmd = | Assign of string * expr | Ite of expr * cmd * cmd | Seq of cmd * cmd | While of expr * cmd | Skip

let rec eval_expr (m : value StringMap.t) (e: expr) : value = 
    match e with 
    | Value v -> v
    | Var x -> StringMap.find x m
    | App (o, es) -> 
        (match es with 
        | [e1; e2] -> eval_binop o (eval_expr m e1) (eval_expr m e2)
        | _ -> failwith "Got wrong number of arguments"
        )

let rec eval_cmd (m : value StringMap.t) (c : cmd) : value StringMap.t = 
    match c with 
    | Assign (x, e) -> StringMap.add x (eval_expr m e) m
    | Ite (e, c1, c2) -> if eval_expr m e = 1 then eval_cmd m c1 else eval_cmd m c2
    | Seq (c1, c2) -> let m' = eval_cmd m c1 in eval_cmd m' c2
    | While (e, c) -> 
        if eval_expr m e = 1 then 
            let m' = eval_cmd m c in 
            eval_cmd m' (While (e, c))
        else 
        m
    | Skip -> m
end

Just as we compiled CalcLang to StackLang in Week 11, we now will compile MiniPython to StackLang. Our version of StackLang will be a bit different than class. In particular, to handle MiniPython, we will extend the evaluator to also allow jumps backwards instead of jumps forwards. We do this by using the following definitions (the complete ):

module StackLang = struct 
  type instr = 
    | Push of value
    | PrimOp of op
    | Get of string
    | Set of string
    | JumpIfNotOne of int
    | Jump of int

  type config = {
    pc : int;
    ins : instr list;
    stack : value list;
    env : value StringMap.t
  }
  ...
end

Here, an instr is the same as in the notes, with the exception that Jump/JumpIfNotOne is allowed to have positive and negative offsets. In the notes, a configuration was a tuple of a list of instructions, a stack, and an environment, and we consumed (i.e., dropped) instructions as we executed them, and finished execution once the list of instructions was empty. Now, we are using a different approach: the list of instructions, ins will stay constant through execution. Instead, we have a program counter pc that will index into this list, and evolve as the StackLang program executes. Let's now look at the evaluator for StackLang:

StackLang 
let step (cfg : config) : config =
    match List.nth cfg.ins cfg.pc with 
    | Push v -> { cfg with pc = cfg.pc + 1; stack = v :: cfg.stack }
    | Set s -> 
    (match cfg.stack with 
        | [] -> failwith "Stack empty"
        | v::stack' -> { cfg with pc = cfg.pc + 1; stack = stack'; env = StringMap.add s v cfg.env }
    )
    | Get s -> 
    (match StringMap.find_opt s cfg.env with
    | None -> failwith "Unknown variable"
    | Some v -> { cfg with pc = cfg.pc + 1; stack = v :: cfg.stack }
    )
    | PrimOp op -> 
    (match cfg.stack with 
        | v1 :: v2 :: stack' -> 
        (* Important: ordering of v1 and v2 is flipped. This is on purpose. *)
        let v = eval_binop op v2 v1 in { cfg with pc = cfg.pc + 1; stack = v :: stack' }
        | _ -> failwith "Not enough elements on stack."
    )
    | Jump n -> { cfg with pc = cfg.pc + n }
    | JumpIfNotOne n -> 
        (match cfg.stack with
        | v :: stack' -> 
            if v <> 1 
            then { cfg with pc = cfg.pc + n; stack = stack' } 
            else { cfg with pc = cfg.pc + 1; stack = stack' }
        | _ -> failwith "Not enough elements on stack"
        )

type program = instr list

let rec loop (cfg : config) : config =
    if 0 <= cfg.pc && cfg.pc < List.length cfg.ins then 
      loop (step cfg)
    else cfg

let init_config p = { pc = 0; ins = p; stack = []; env = StringMap.empty }

let execute (p : program) : value StringMap.t =
  (loop (init_config p)).env

let get_pc_list (p : program) : int list * value StringMap.t = ...

For every "normal" instruction (Push/Get/Set/PrimOp), the program counter pc advances by one. For Jump n, the program counter changes to pc + n (remember that n could be positive or negative). For JumpIfNotOne n, the program counter advances by one if the top of the stack is one; otherwise, it also changes to pc. To run the program, we initialize pc = 0, with an empty stack an environment. We then run the program until pc is out of bounds, at which point we stop. Because we only run MiniPython for its side effects to the environment, we let the return type of execute be an environment. In addition to execute, we also give you a function get_pc_list that also returns the history of the program counter as the program evaluated.

Your task is to compile MiniPython to StackLang. 

let rec compile_expr (e : MiniPython.expr) : StackLang.program = 
  failwith "TODO"

let rec compile_cmd (c : MiniPython.cmd) : StackLang.program = 
  failwith "TODO"

Your compiler will be evaluated via correctness, meaning that, given a command c : MiniPython.cmd, if c successfully executes via MiniPython.eval under the empty environment to return a final environment env, then compile_cmd c must execute via StackLang.execute and return the same environment.

Grading Criteria

Correctness of your compiler.

Hint

compile_expr will behave similarly to how the corresponding cases behave in our compiler from Week 11. For every expression e, if we run compile_expr e under the empty stack, we should get a stack with exactly one value left on top.

For compile_cmd, Ite will be more or less similar to how control flow was achieved in our compiler from Week 11. While is a bit trickier; it is similar to Ite, but we jump over the entire rest of the while-loop code if the guard is false. If the guard is true, we will instead run the body of the while loop, then perform a jump with a negative offset so that we run the while loop again. For every command c, if we run compile_cmd c under the empty stack, we should have an empty stack after the compiled program finishes running.

Example Programs

In the template, we provide you with three example programs in MiniPython: if_cmd, which uses Assign, Seq, and Ite; while_cmd, which uses Assign and While; and fib_cmd, which uses the entire language. Here, fib_cmd : int -> MiniPython.cmd computes the ith Fibonacci number using MiniPython, given input i.

To test your compiler, we provide a function test_compile : MiniPython.cmd -> string -> (value option * value option) which, runs the given command in MiniPython, runs the compiled command in StackLang, and returns the final value of the two environments on the variable given as the second argument. We also give you helper functions as a convenience for running test_compile on the three example programs; you can run these in utop to test your compiler. Be sure to test your compiler on many small example programs to make sure it runs correctly before you debug the correctness on the Fibonacci example.