Lecture 05 - Code Generation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "187e4521",
   "metadata": {},
   "source": [
    "# Code Generation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46918d5b",
   "metadata": {},
   "source": [
    "The following code allows us to use the previously defined lexer/parser:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c3b902e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/opam/.opam/4.13/lib/base64: added to search path\n",
      "/home/opam/.opam/4.13/lib/base64/base64.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ocaml/compiler-libs: added to search path\n",
      "/home/opam/.opam/4.13/lib/ocaml/compiler-libs/ocamlcommon.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/seq: added to search path\n",
      "/home/opam/.opam/4.13/lib/yojson: added to search path\n",
      "/home/opam/.opam/4.13/lib/yojson/yojson.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ppx_yojson_conv_lib: added to search path\n",
      "/home/opam/.opam/4.13/lib/ppx_yojson_conv_lib/ppx_yojson_conv_lib.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ocaml/unix.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/bytes: added to search path\n",
      "/home/opam/.opam/4.13/lib/uuidm: added to search path\n",
      "/home/opam/.opam/4.13/lib/uuidm/uuidm.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/jupyter: added to search path\n",
      "/home/opam/.opam/4.13/lib/jupyter/jupyter.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/result: added to search path\n",
      "/home/opam/.opam/4.13/lib/result/result.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ppx_deriving/runtime: added to search path\n",
      "/home/opam/.opam/4.13/lib/ppx_deriving/runtime/ppx_deriving_runtime.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/jupyter/notebook: added to search path\n",
      "/home/opam/.opam/4.13/lib/jupyter/notebook/jupyter_notebook.cma: loaded\n",
      "File \"simp.mll\", line 13, character 43: syntax error.\n"
     ]
    },
    {
     "ename": "error",
     "evalue": "runtime_error",
     "output_type": "error",
     "traceback": [
      "\u001b[31mException:\nJupyter_notebook__Process.Execution_failure\n {Jupyter_notebook__Process.exit_status = Unix.WEXITED 3; stdout = None;\n  stderr = None}.\nRaised at Jupyter_notebook__Process.capture_and_wait in file \"src/notebook/process.ml\", line 146, characters 44-76\nCalled from Stdlib__Fun.protect in file \"fun.ml\", line 33, characters 8-15\nRe-raised at Stdlib__Fun.protect in file \"fun.ml\", line 38, characters 6-52\nCalled from Topeval.load_lambda in file \"toplevel/byte/topeval.ml\", line 89, characters 4-150\n\u001b[0m"
     ]
    }
   ],
   "source": [
    "#require \"jupyter.notebook\" ;;\n",
    "\n",
    "open Jupyter_notebook;;\n",
    "\n",
    "Process.sh \"ocamllex simp.mll\";;\n",
    "Process.sh \"ocamlc -c simp.ml\";;\n",
    "\n",
    "#use \"psimp.ml\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bfa96d1",
   "metadata": {},
   "source": [
    "## Representing MIPS Code in OCaml"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "265c44df",
   "metadata": {},
   "source": [
    "We define registers as type synomym to ``int``, and define several aliases for the mnemonics: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f3795302",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type register = int\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val v0 : register = 2\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val v1 : register = 3\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val a0 : register = 4\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val a1 : register = 5\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val a2 : register = 6\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val a3 : register = 7\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t0 : register = 8\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t1 : register = 9\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t2 : register = 10\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t3 : register = 11\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t4 : register = 12\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t5 : register = 13\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t6 : register = 14\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t7 : register = 15\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s0 : register = 16\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s1 : register = 17\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s2 : register = 18\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s3 : register = 19\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s4 : register = 20\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s5 : register = 21\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s6 : register = 22\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val s7 : register = 23\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t8 : register = 24\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t9 : register = 25\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sp : register = 29\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val fp : register = 30\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val ra : register = 31\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* We represent registers as numbers. Registers are represented by 0 to 31. *)\n",
    "type register = int\n",
    "\n",
    "(* Value returned by a subroutine *)\n",
    "let v0 : register = 2 \n",
    "let v1 : register = 3 \n",
    "\n",
    "(* Arguments to subroutine *)\n",
    "let a0 : register = 4 \n",
    "let a1 : register = 5\n",
    "let a2 : register = 6\n",
    "let a3 : register = 7\n",
    "\n",
    "(* Temporary registers *)\n",
    "let t0 : register = 8\n",
    "let t1 : register = 9\n",
    "let t2 : register = 10\n",
    "let t3 : register = 11\n",
    "let t4 : register = 12\n",
    "let t5 : register = 13\n",
    "let t6 : register = 14\n",
    "let t7 : register = 15\n",
    "\n",
    "(* Saved registers *)\n",
    "let s0 : register = 16\n",
    "let s1 : register = 17 \n",
    "let s2 : register = 18 \n",
    "let s3 : register = 19 \n",
    "let s4 : register = 20 \n",
    "let s5 : register = 21\n",
    "let s6 : register = 22 \n",
    "let s7 : register = 23 \n",
    "\n",
    "(* Temporary registers $t8 and $t9 will be used for interemdiate results. *)\n",
    "let t8 : register = 24 (* $t8 *)\n",
    "let t9 : register = 25 (* $t9 *)\n",
    "\n",
    "let (sp : register) = 29 (* stack pointer *)\n",
    "let (fp : register) = 30 (* frame pointer *)\n",
    "let (ra : register) = 31 (* return address *)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79771ee7",
   "metadata": {},
   "source": [
    "Instructions are represented as an abstract data type.\n",
    "\n",
    "See https://www.dsi.unive.it/~gasparetto/materials/MIPS_Instruction_Set.pdf for full explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ad4a513c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type label = string\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type instruction =\n",
       "    Add of register * register * register\n",
       "  | Sub of register * register * register\n",
       "  | Addi of register * register * int\n",
       "  | Addiu of register * register * int\n",
       "  | Mul of register * register * register\n",
       "  | Div of register * register\n",
       "  | And of register * register * register\n",
       "  | Or of register * register * register\n",
       "  | Andi of register * register * int\n",
       "  | Ori of register * register * int\n",
       "  | Lw of register * int * register\n",
       "  | Sw of register * int * register\n",
       "  | La of register * label\n",
       "  | Li of register * int\n",
       "  | Move of register * register\n",
       "  | Mfhi of register\n",
       "  | Mflo of register\n",
       "  | Label of label\n",
       "  | Beq of register * register * string\n",
       "  | Bne of register * register * string\n",
       "  | Bgt of register * register * string\n",
       "  | Blt of register * register * string\n",
       "  | Bge of register * register * string\n",
       "  | Ble of register * register * string\n",
       "  | J of label\n",
       "  | Jr of register\n",
       "  | Jal of label\n",
       "  | SysCall\n",
       "  | Verbatim of string\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* We represent instructions as an abstract data type. *)\n",
    "\n",
    "type label = string\n",
    "\n",
    "type instruction =  Add of register * register * register (* add $1, $2, $3 - $1 = $2 + $3 *)\n",
    "                   | Sub of register * register * register (* sub $1, $2, $3; $1 = $2 - $3 *)\n",
    "                   | Addi of register * register * int (* addi $1, $2, 100 - $1 = $2 + 100, immediate means a constant number  *)\n",
    "                   | Addiu of register * register * int (* addi $1, $2, 100 - $1 = $2 + 100, values treated as unsigned, immediate means a constant number  *)\n",
    "                   | Mul of register * register * register (* mul $1, $2, $3 - $1 = $2 * $3, without overflow, result is only 32 bits *)\n",
    "                   | Div of register * register (* div $2, $3 - $hi,$low=$2/$3, Remainder stored in special register hi, Quotient stored in special register lo   *)\n",
    "                   | And of register * register * register (* and $1, $2, $3 - $1 = $2 & $3, bitwise AND *)\n",
    "                   | Or of register * register * register (* or $1, $2, $3 - $1 = $2 | 100, bitwise OR *)\n",
    "                   | Andi of register * register * int (* andi $1, $2, 100 - $1 = $2 & 100, bitwise AND with immediate value  *)\n",
    "                   | Ori of register * register * int (* ori $1, $2, 100 - $1 = $2 | 100, bitwise OR with immediate value  *)\n",
    "                   | Lw of register * int * register (* lw $1, 100 ($2) - load word, $1 = Memory[$2 + 100], copy from memory to register *)\n",
    "                   | Sw of register * int * register (* sw $1, 100 ($2) - store word, Memory[$2 + 100] = $1, copy from register to memory *)\n",
    "                   | La of register * label (* $1 = Address of label *) \n",
    "                   | Li of register * int (* li $1, 100 - Loads immediate value into register *)\n",
    "                   | Move of register * register (* move $1,$2 - $1 = $2, Copy from register to register *)\n",
    "                   | Mfhi of register (* mfhi $2, $2 = hi, copy from special register hi to general register *)\n",
    "                   | Mflo of register (* mflo $2, $2 = lo, copy from special register lo to general register *)\n",
    "                   | Label of label \n",
    "                   | Beq of register * register * string (* beq $1, $2, l - if ($1 == $2) go to label l *)\n",
    "                   | Bne of register * register * string (* bne $1, $2, l - if ($1 != $2) go to label l *)\n",
    "                   | Bgt of register * register * string (* bgt $1, $2, l - if ($1 > $2) go to label l *)\n",
    "                   | Blt of register * register * string (* blt $1, $2, l - if ($1 < $2) go to label l *)\n",
    "                   | Bge of register * register * string (* bge $1, $2, l - if ($1 >= $2) go to label l *)\n",
    "                   | Ble of register * register * string (* ble $1, $2, l - if ($1 <= $2) go to label l *)                  \n",
    "                   | J of label (* j l, go to label l, jumpt to target address *)\n",
    "                   | Jr of register (* jump register, jr $1, go to address stored in $1 *)\n",
    "                   | Jal of label (* jump and link, e.g. jal l - $ra=PC+4; go to label l - used when making procedure call. This saves the return address in $ra.  *)\n",
    "                   | SysCall \n",
    "                   | Verbatim of string "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed082b70",
   "metadata": {},
   "source": [
    "MIPS code is simply a list of instructions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cc600abe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type code = instruction list\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type code = instruction list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "076a51d3",
   "metadata": {},
   "source": [
    "The following code prints instructions so that they are readible to the MIPS interpreter (https://cpulator.01xz.net/?sys=mipsr5b-spim). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "24274aae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val print_register : register -> string = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_instruction : instruction -> string = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_code : code -> unit = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print_register (r : register) = \n",
    "    match r with \n",
    "    | 2 | 3 -> \"$v\" ^ (string_of_int (r - v0)) \n",
    "    | 4 |5 |6 | 7 -> \"$a\" ^ string_of_int (r - a0)\n",
    "    | 8|9|10|11|12|13|14|15 -> \"$t\" ^ string_of_int (r - t0) \n",
    "    | 16|17|18|19|20|21|22|23 -> \"$s\" ^ string_of_int (r - s0)\n",
    "    | 24 -> \"$t8\"\n",
    "    | 25 -> \"$t9\"\n",
    "    | 29 -> \"$sp\"\n",
    "    | 30 -> \"$fp\"\n",
    "    | 31 -> \"$ra\"\n",
    "    | _ -> \"$\" ^ string_of_int r\n",
    "\n",
    "let print_instruction (i : instruction) = match i with \n",
    "    | Add (r1, r2, r3) -> \"add \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Sub (r1, r2, r3) -> \"sub \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Addi (r1, r2, i) -> \"addi \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ string_of_int i\n",
    "    | Addiu (r1, r2, i) -> \"addiu \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ string_of_int i\n",
    "    | Mul (r1, r2, r3) -> \"mul \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Div (r1, r2) -> \"div \" ^ print_register r1 ^ \", \" ^ print_register r2\n",
    "    | Beq (r1, r2, l) ->  \"beq \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Bne (r1, r2, l) ->  \"bne \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Bgt (r1, r2, l) ->  \"bgt \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Blt (r1, r2, l) ->  \"blt \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Bge (r1, r2, l) ->  \"bge \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Ble (r1, r2, l) ->  \"ble \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ l\n",
    "    | Li (r, i) -> \"li \" ^ print_register r ^ \", \" ^ string_of_int i\n",
    "    | Lw (r1, o, r2) -> \"lw \" ^ print_register r1 ^ \", \" ^ string_of_int o ^ \"(\" ^ print_register r2 ^ \")\" \n",
    "    | La (r, l) -> \"la \" ^ print_register r ^ \", \" ^  l\n",
    "    | Sw (r1, o, r2) -> \"sw \" ^ print_register r1 ^ \", \" ^ string_of_int o ^ \"(\" ^ print_register r2 ^ \")\" \n",
    "    | Move (r1, r2) -> \"move \" ^ print_register r1 ^ \", \" ^ print_register r2\n",
    "    | Mfhi r -> \"mfhi \"^ print_register r\n",
    "    | Mflo r -> \"mflo \"^ print_register r\n",
    "    | And (r1, r2, r3) -> \"and \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Andi (r1, r2, r3) -> \"andi \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Or (r1, r2, r3) -> \"or \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | Ori (r1, r2, r3) -> \"ori \" ^ print_register r1 ^ \", \" ^ print_register r2 ^ \", \" ^ print_register r3\n",
    "    | SysCall -> \"syscall\"\n",
    "    | Label l -> l ^ \":\"\n",
    "    | J label -> \"j \" ^ label \n",
    "    | Jr r -> \"jr \" ^ print_register r\n",
    "    | Jal label -> \"jal \" ^ label\n",
    "    | Verbatim s -> s\n",
    "   \n",
    "let rec print_code (c : code) : unit = match c with \n",
    "    | [] -> ()\n",
    "    | c :: cs -> (print_endline (print_instruction c); print_code cs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08a43d4d",
   "metadata": {},
   "source": [
    "E.g., you can load the following code into the MIPS interpreter (https://cpulator.01xz.net/?sys=mipsr5b-spim). Try it out!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4cbf14a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "li $t7, 5\n",
      "li $t8, 4\n",
      "add $t8, $t8, $t9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_code [Li (t7, 5); Li (t8, 4); Add (t8, t8, t9)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25601c37",
   "metadata": {},
   "source": [
    "## Compiling Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3a723c3",
   "metadata": {},
   "source": [
    "The following code implement push/pop operations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6fae08e1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "exception E of string\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val push : register -> code = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val pop : register -> code = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* An exception to be used *)\n",
    "exception E of string\n",
    "\n",
    "(* Pushing the content of register r to the stack *)\n",
    "let push (r : register) : code = [Addiu (sp, sp, -4);\n",
    "                                  Sw (r, 0, sp)]\n",
    "\n",
    "(* Popping the stack into register r *)\n",
    "let pop (r : register) : code = [Lw (r, 0, sp);\n",
    "                                 Addiu (sp, sp, 4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ff06fc3",
   "metadata": {},
   "source": [
    "We can define compilation of expressions by traversing the abstract syntax tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "856e3e1c",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[8]\", line 1, characters 20-22:\n1 | let compile_op (o : op) r1 r2 r = match o with \n                        ^^\nError: Unbound type constructor op\n"
     ]
    }
   ],
   "source": [
    "let compile_op (o : op) r1 r2 r = match o with \n",
    "    | Plus -> [Add (r1, r2, r)]\n",
    "    | Minus -> [Sub (r1, r2, r)]\n",
    "    | _ -> raise (E \"Not known.\") \n",
    "\n",
    "let rec compile_exp (r : register) (e : exp) : code = match e with \n",
    "    | Numb n -> [Li (r, n)]\n",
    "    | Op (e1, o, e2) -> compile_exp t8 e1\n",
    "                        @ push t8\n",
    "                        @ compile_exp t9 e2\n",
    "                        @ pop t8\n",
    "                        @ compile_op o r t8 t9\n",
    "    | _ -> raise (E \"not known\");;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fc0367fc",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[9]\", line 1, characters 13-24:\n1 | print_code ((compile_exp s0 (Op (Numb 3, Plus, (Op (Numb 5, Plus, Numb 4))))));;\n                 ^^^^^^^^^^^\nError: Unbound value compile_exp\n"
     ]
    }
   ],
   "source": [
    "print_code ((compile_exp s0 (Op (Numb 3, Plus, (Op (Numb 5, Plus, Numb 4))))));;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16eb1431",
   "metadata": {},
   "source": [
    "## Variables and Assignments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "5e6765f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "exception EEnv of string\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val maxreg : int = 23\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[10]\", line 6, characters 29-38:\n6 | let find_max_register (env : int Env.t) = \n                                 ^^^^^^^^^\nError: The type constructor Env.t expects 0 argument(s),\n       but is here applied to 1 argument(s)\n"
     ]
    }
   ],
   "source": [
    "exception EEnv of string\n",
    "\n",
    "let maxreg = 23\n",
    "\n",
    "(*  Function that finds the largest register in the environment. *)\n",
    "let find_max_register (env : int Env.t) = \n",
    "    Env.fold (fun _ a b -> max a b) env (s0 -1) \n",
    "\n",
    "\n",
    "(* Declaring a variable: \n",
    "  - When trying to declare a variable, and there are too many registers already \n",
    "    reserved, throw an exception. \n",
    "  - Else: Assign to variable x the largest register number + 1.\n",
    "*)\n",
    "let declare_var (env: int Env.t) (x:string) : int Env.t = \n",
    "    if (find_max_register env) >= maxreg\n",
    "     then raise (EEnv \"Too many variables\")\n",
    "     else Env.add x (1 + find_max_register env) env"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "eb71747a",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[11]\", line 1, characters 0-8:\n1 | Env.find \"b\"  (declare_var (declare_var Env.empty \"b\") \"a\");;\n    ^^^^^^^^\nError: Unbound value Env.find\n"
     ]
    }
   ],
   "source": [
    "Env.find \"b\"  (declare_var (declare_var Env.empty \"b\") \"a\");;\n",
    "\n",
    "Env.find \"a\"  (declare_var (declare_var Env.empty \"b\") \"a\");;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2d10a79e",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[12]\", line 1, characters 20-22:\n1 | let compile_op (o : op) r1 r2 r = match o with \n                        ^^\nError: Unbound type constructor op\n"
     ]
    }
   ],
   "source": [
    "let compile_op (o : op) r1 r2 r = match o with \n",
    "    | Plus -> Add (r1, r2, r)\n",
    "    | Minus -> Sub (r1, r2, r)\n",
    "    | _ -> raise (E \"Not implemented.\") \n",
    "\n",
    "let rec compile_exp env (r : register) (e : exp)  : code = match e with \n",
    "    | Id s -> [Move (r, Env.find s env)]\n",
    "    | Numb n -> [Li (r, n)]\n",
    "    | Neg e -> compile_exp env r (Op (Numb 0, Minus, e))\n",
    "    | Op (e1, o, e2) -> compile_exp env t8 e1\n",
    "                        @ push t8\n",
    "                        @ compile_exp env t9 e2\n",
    "                        @ pop t8\n",
    "                        @ [compile_op o r t8 t9];;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2eaa2b1",
   "metadata": {},
   "source": [
    "Compiling expressions: An expression will be translated into a sequence of instructions. \n",
    "This will create a value that we store in the given register."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "df24131f",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[13]\", line 3, characters 33-44:\n3 |     | dcl :: dcls' -> let env' = declare_var env dcl \n                                     ^^^^^^^^^^^\nError: Unbound value declare_var\n"
     ]
    }
   ],
   "source": [
    "let rec compile_dcls env (dcls : string list)  = match dcls with \n",
    "    | [] -> env \n",
    "    | dcl :: dcls' -> let env' = declare_var env dcl \n",
    "                      in compile_dcls env' dcls'\n",
    "\n",
    "let compile_cmd env (c : cmd) : code = match c with \n",
    "    | Asgn (s, e) -> compile_exp env (Env.find s env) e\n",
    "    | _ -> raise (E \"Not implemented.\")\n",
    "\n",
    "let rec compile_cmds env (cs : cmd list) : code = match cs with \n",
    "    | [] -> [] \n",
    "    | c :: cs -> compile_cmd env c @ compile_cmds env cs\n",
    "    \n",
    "\n",
    "let compile_program (p : program) = match p with \n",
    "    | Program (dcls, cmds) -> let env = compile_dcls Env.empty dcls in     \n",
    "        [Verbatim \".set noreorder\"; Verbatim \".text\"; Label \"_start\"]\n",
    "        @ compile_cmds env cmds\n",
    "        @ [Li (v0, 10); SysCall]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2ab5b431",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val p : string =\n",
       "  \"\\nVAR A;\\nVAR B;\\nVAR C;\\nVAR D;\\nVAR Z; \\nA := 128; \\nB := 64;\\nC := 32;\\nD := 16; \\nZ := (A + B) + (C + D)\\n\"\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[14]\", line 15, characters 25-40:\n15 | let mips =  (print_code (compile_program (parse_string p)));;\n                              ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let p = \"\n",
    "VAR A;\n",
    "VAR B;\n",
    "VAR C;\n",
    "VAR D;\n",
    "VAR Z; \n",
    "A := 128; \n",
    "B := 64;\n",
    "C := 32;\n",
    "D := 16; \n",
    "Z := (A + B) + (C + D)\n",
    "\"\n",
    "\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string p)));;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a8207ca",
   "metadata": {},
   "source": [
    "## Compiling SIMP\n",
    "\n",
    "See the slides for an explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4e839c0d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val counter : int ref = {contents = 0}\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val next_val : unit -> int = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[15]\", line 9, characters 20-22:\n9 | let compile_op (o : op) r1 r2 r = match o with \n                        ^^\nError: Unbound type constructor op\n"
     ]
    }
   ],
   "source": [
    "let counter : int ref = {contents = 0}\n",
    "\n",
    "(* Counts up from 1, hence gives us a unique number every time *)\n",
    "let next_val = \n",
    "    fun () ->\n",
    "      counter := (!counter) + 1;\n",
    "      !counter;;\n",
    "\n",
    "let compile_op (o : op) r1 r2 r = match o with \n",
    "    | Plus -> [Add (r1, r2, r)]\n",
    "    | Minus -> [Sub (r1, r2, r)]\n",
    "    | Mult -> [Mul (r1, r2, r)] \n",
    "    | Div -> [Div (r1, r2); Mflo r] \n",
    "\n",
    "let rec compile_exp env (r : register) (e : exp) : code = match e with \n",
    "    | Id s -> [Move (r, Env.find s env)]\n",
    "    | Numb n -> [Li (r, n)]\n",
    "    | Neg e -> compile_exp env r (Op (Numb 0, Minus, e))\n",
    "    | Op (e1, o, e2) -> compile_exp env t8 e1\n",
    "                        @ push t8\n",
    "                        @ compile_exp env t9 e2\n",
    "                        @ pop t8\n",
    "                        @ compile_op o r t8 t9;;\n",
    "\n",
    "\n",
    "let compile_branch o r1 r2 label = match o with \n",
    "    | Lt -> Bge (r1, r2, label)\n",
    "    | Lte -> Bgt (r1, r2, label)\n",
    "    | Gte -> Blt (r1, r2, label)\n",
    "    | Gt -> Ble (r1, r2, label)\n",
    "    | Eq -> Bne (r1, r2, label)\n",
    "    | Neq -> Beq (r1, r2, label)\n",
    "    \n",
    "let compile_cond env o e1 e2 label =   \n",
    "    compile_exp env t8 e1\n",
    "    @ push t8\n",
    "    @ compile_exp env t9 e2\n",
    "    @ pop t8\n",
    "    @ [compile_branch o t8 t9 label]\n",
    "    \n",
    "\n",
    "let rec compile_dcls env dcls = match dcls with \n",
    "    | [] -> env \n",
    "    | dcl :: dcls' -> let env' = declare_var env dcl \n",
    "                      in compile_dcls env' dcls'\n",
    "\n",
    "let rec compile_cmd env (c : cmd) : code = match c with \n",
    "    | If (e, c) -> (let label = \"IFEND\" ^ string_of_int (next_val ()) in\n",
    "                    match e with \n",
    "                    | Cop (e1, o, e2) -> compile_cond env o e1 e2 label\n",
    "                                        @ compile_cmd env c\n",
    "                                        @ [Label label])\n",
    "    | Ite (e, c1, c2) -> (let counter = string_of_int (next_val ()) in\n",
    "                            let label_end = \"IFEND\" ^ counter in\n",
    "                            let label_false = \"IFFALSE\" ^ counter in\n",
    "                match e with \n",
    "                | Cop (e1, o, e2) -> compile_cond env o e1 e2 label_false\n",
    "                                    @ compile_cmd env c1\n",
    "                                    @ [J label_end]\n",
    "                                    @ [Label label_false]\n",
    "                                    @ compile_cmd env c2\n",
    "                                    @ [Label label_end])\n",
    "    | While (e, c) -> ( let counter = string_of_int (next_val ()) in\n",
    "                        let label_loop = \"WLOOP\" ^ counter in\n",
    "                        let label_end = \"WEND\" ^ counter in\n",
    "                match e with \n",
    "                | Cop (e1, o, e2) -> [Label label_loop]\n",
    "                                    @ compile_cond env o e1 e2 label_end\n",
    "                                    @ compile_cmd env c\n",
    "                                    @ [J label_loop]\n",
    "                                    @ [Label label_end])\n",
    "    | Asgn (s, e) -> compile_exp env (Env.find s env) e\n",
    "    | Begin (Program (dcls, cmds)) -> let env' = compile_dcls env dcls in\n",
    "                                      compile_cmds env' cmds \n",
    "    | Print e -> [Li (v0, 1)] \n",
    "                 @ compile_exp env a0 e\n",
    "                 @ [SysCall]\n",
    "    | Input s -> let s_register = Env.find s env in \n",
    "                 [Li (v0, 4); La (a0, \"sinp\"); SysCall; Li (v0, 5); SysCall; Move (s_register, v0)]\n",
    "\n",
    "and compile_cmds env (cs : cmd list) : code = match cs with \n",
    "    | [] -> [] \n",
    "    | c :: cs -> compile_cmd env c @ compile_cmds env cs\n",
    "    \n",
    "\n",
    "\n",
    "let compile_program (p : program) = match p with \n",
    "    | Program (dcls, cmds) -> let env = compile_dcls Env.empty dcls in     \n",
    "        [Verbatim \".set noreorder\"; Verbatim \".data\"; Label \"sinp\"; Verbatim \".asciiz \\\"INPUT>\\\"  \"; Verbatim \".text\"; Label \"_start\"]\n",
    "        @ compile_cmds env cmds\n",
    "        @ [Li (v0, 10); SysCall]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7c347e13",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_if : string = \"\\nVAR A; \\nVAR MAX;\\nIF A > MAX THEN MAX := A\\n\"\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[16]\", line 7, characters 25-40:\n7 | let mips =  (print_code (compile_program (parse_string example_if)));;\n                             ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_if = \"\n",
    "VAR A; \n",
    "VAR MAX;\n",
    "IF A > MAX THEN MAX := A\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_if)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "bdb00c3c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_ite : string =\n",
       "  \"\\nVAR A; \\nVAR B;\\nVAR MAX;\\nIF A > B THEN MAX := A ELSE MAX := B\\n\"\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[17]\", line 8, characters 25-40:\n8 | let mips =  (print_code (compile_program (parse_string example_ite)));;\n                             ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_ite = \"\n",
    "VAR A; \n",
    "VAR B;\n",
    "VAR MAX;\n",
    "IF A > B THEN MAX := A ELSE MAX := B\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_ite)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "2d7c88c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_ite2 : string =\n",
       "  \"\\nVAR x; VAR y; VAR max;\\nx := 3; \\ny := 5;\\nIF x > y\\nTHEN \\n    max := x\\nELSE \\n    max := y\\n\"\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[18]\", line 12, characters 25-40:\n12 | let mips =  (print_code (compile_program (parse_string example_ite2)));;\n                              ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_ite2 = \"\n",
    "VAR x; VAR y; VAR max;\n",
    "x := 3; \n",
    "y := 5;\n",
    "IF x > y\n",
    "THEN \n",
    "    max := x\n",
    "ELSE \n",
    "    max := y\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_ite2)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "634debd1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_block : string =\n",
       "  \"\\nVAR A; VAR B; VAR C; \\nA := 1; B := 2; C := 3; \\nBEGIN \\n    VAR A; VAR B; \\n    A := 4; B := 5; C := 6; \\n    BEGIN \\n        VAR A; \\n        A := 7; \\n        B := 8; \\n        C := 9 \\n    END; \\n    A := 10; B:= 11; C := 12\\nEND; \\nA := 13; B := 14; C := 15\\n\"\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[19]\", line 18, characters 25-40:\n18 | let mips =  (print_code (compile_program (parse_string example_block)));;\n                              ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_block = \"\n",
    "VAR A; VAR B; VAR C; \n",
    "A := 1; B := 2; C := 3; \n",
    "BEGIN \n",
    "    VAR A; VAR B; \n",
    "    A := 4; B := 5; C := 6; \n",
    "    BEGIN \n",
    "        VAR A; \n",
    "        A := 7; \n",
    "        B := 8; \n",
    "        C := 9 \n",
    "    END; \n",
    "    A := 10; B:= 11; C := 12\n",
    "END; \n",
    "A := 13; B := 14; C := 15\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_block)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "48257ed6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_while : string =\n",
       "  \"\\nVAR n; \\nn := 5; \\nWHILE n > 0 DO\\nBEGIN \\nPRINT n; \\nn := n - 1\\nEND\\n\"\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val example_while : string =\n",
       "  \"\\nVAR n; \\nn := 5; \\nWHILE n > 0 DO\\nBEGIN \\nPRINT n; \\nn := n - 1\\nEND\\n\"\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[22]\", line 21, characters 25-40:\n21 | let mips =  (print_code (compile_program (parse_string example_while)));;let mips =  (print_code (compile_program (parse_string example_while)));;\n                              ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_while = \"\n",
    "VAR n; \n",
    "n := 5; \n",
    "WHILE n > 0 DO\n",
    "BEGIN \n",
    "PRINT n; \n",
    "n := n - 1\n",
    "END\n",
    "\"\n",
    "\n",
    "let example_while = \"\n",
    "VAR n; \n",
    "n := 5; \n",
    "WHILE n > 0 DO\n",
    "BEGIN \n",
    "PRINT n; \n",
    "n := n - 1\n",
    "END\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_while)));;let mips =  (print_code (compile_program (parse_string example_while)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c7538df7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val example_input : string = \"\\nVAR x; \\nINPUT x; \\nPRINT (x * x)\\n\"\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[21]\", line 7, characters 25-40:\n7 | let mips =  (print_code (compile_program (parse_string example_input)));;\n                             ^^^^^^^^^^^^^^^\nError: Unbound value compile_program\n"
     ]
    }
   ],
   "source": [
    "let example_input = \"\n",
    "VAR x; \n",
    "INPUT x; \n",
    "PRINT (x * x)\n",
    "\"\n",
    "\n",
    "let mips =  (print_code (compile_program (parse_string example_input)));;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "544170c7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "caf9deb4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dda63a87",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59eff9c4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.13",
   "language": "OCaml",
   "name": "ocaml-jupyter-4.13"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}