Lab 1 (Intro + Interpreters).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "68a562a5",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "# Lab 1 \n",
    "\n",
    "- It is recommended to **go through this file with a partner**. \n",
    "- Ensure to **ask** if anything is not clear - first your partner, then a lab helper.\n",
    "- You want to first go through the accompanying code of the lectures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "145c161e",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "## Ex. 1 - Different Phases\n",
    "\n",
    "You are given the following SIMP program: \n",
    "```\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",
    "1. What does its lexical syntax look like on paper? \n",
    "2. What does its phrasal syntax look like on paper? \n",
    "3. What does its abstract syntax look like? (Both on paper and in OCaml!)\n",
    "4. What does a corresponding assembler program look like on paper? (You can use ARM instructions or the MIPS instruction set: https://www.dsi.unive.it/~gasparetto/materials/MIPS_Instruction_Set.pdf - in the lecture, we will use the latter.\n",
    "You can test your program here: https://cpulator.01xz.net/?sys=mipsr5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1b1fc868",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Findlib has been successfully loaded. Additional directives:\n",
      "  #require \"package\";;      to load a package\n",
      "  #list;;                   to list the available packages\n",
      "  #camlp4o;;                to load camlp4 (standard syntax)\n",
      "  #camlp4r;;                to load camlp4 (revised syntax)\n",
      "  #predicates \"p,q,...\";;   to set these predicates\n",
      "  Topfind.reset();;         to force that packages will be reloaded\n",
      "  #thread;;                 to enable threads\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "type op = Plus | Minus | Mult | Div\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type exp = Id of string | Numb of int | Op of exp * op * exp\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cond = Eq | Neq | Lte | Lt | Gte | Gt\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type condexp = Cop of exp * cond * exp\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cmd =\n",
       "    Asgn of string * exp\n",
       "  | Ite of condexp * cmd * cmd\n",
       "  | If of condexp * cmd\n",
       "  | While of condexp * cmd\n",
       "  | Begin of program\n",
       "  | Print of exp\n",
       "and program = Program of string list * cmd list\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val p : program = Program ([], [])\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type op = Plus | Minus | Mult | Div \n",
    "\n",
    "type exp = Id of string | Numb of int | Op of exp * op * exp \n",
    "\n",
    "type cond = Eq | Neq | Lte | Lt | Gte | Gt \n",
    "type condexp = Cop of exp * cond * exp\n",
    "                                          \n",
    "type cmd = Asgn of string * exp \n",
    "         | Ite of condexp * cmd * cmd | If of condexp * cmd \n",
    "         | While of condexp * cmd\n",
    "         | Begin of program \n",
    "         | Print of exp \n",
    "         \n",
    "and program = Program of string list * cmd list\n",
    "\n",
    "let p : program = (* TODO *)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33d1be7d",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "## Ex. 2 - Error Analysis \n",
    "\n",
    "When do the following errors appear - lexical analysis, syntactic analysis, semantic analysis, or during the interpreter/execution? Static or dynamic?\n",
    "\n",
    "Program 1 in SIMP: \n",
    "```\n",
    "VAR 1var;\n",
    "1var = 3\n",
    "```\n",
    "\n",
    "Program 2 in SIMP: \n",
    "```\n",
    "VAR x\n",
    "```\n",
    "\n",
    "Program 3 in SIMP: \n",
    "```\n",
    "VAR x;\n",
    "x = 2 + 3;\n",
    "```\n",
    "\n",
    "Program 4 in C: \n",
    "```\n",
    "char *cp = 'x';\n",
    "```\n",
    "\n",
    "Program 5 in Java: \n",
    "```\n",
    "class X {\n",
    "  void increment() { ... }\n",
    "}\n",
    "\n",
    "X x = new X;\n",
    "x.decrement();\n",
    "```\n",
    "\n",
    "Program 6 in Python: \n",
    "```\n",
    "class X:\n",
    "  def increment(self):\n",
    "    ...\n",
    "\n",
    "x = X()\n",
    "x.decrement()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f69791eb",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "## Ex. 3 - Interpretation \n",
    "\n",
    "Below is the full code for the interpreter you saw in class for SIMP:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "3914828a",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type op = Plus | Minus | Mult | Div\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type exp = Id of string | Numb of int | Op of exp * op * exp\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cond = Eq | Neq | Lte | Lt | Gte | Gt\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type condexp = Cop of exp * cond * exp\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cmd =\n",
       "    Asgn of string * exp\n",
       "  | Ite of condexp * cmd * cmd\n",
       "  | If of condexp * cmd\n",
       "  | While of condexp * cmd\n",
       "  | Begin of program\n",
       "  | Print of exp\n",
       "and program = Program of string list * cmd list\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "module Env :\n",
       "  sig\n",
       "    type key = String.t\n",
       "    type 'a t = 'a Map.Make(String).t\n",
       "    val empty : 'a t\n",
       "    val is_empty : 'a t -> bool\n",
       "    val mem : key -> 'a t -> bool\n",
       "    val add : key -> 'a -> 'a t -> 'a t\n",
       "    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t\n",
       "    val singleton : key -> 'a -> 'a t\n",
       "    val remove : key -> 'a t -> 'a t\n",
       "    val merge :\n",
       "      (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t\n",
       "    val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t\n",
       "    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int\n",
       "    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool\n",
       "    val iter : (key -> 'a -> unit) -> 'a t -> unit\n",
       "    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b\n",
       "    val for_all : (key -> 'a -> bool) -> 'a t -> bool\n",
       "    val exists : (key -> 'a -> bool) -> 'a t -> bool\n",
       "    val filter : (key -> 'a -> bool) -> 'a t -> 'a t\n",
       "    val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t\n",
       "    val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t\n",
       "    val cardinal : 'a t -> int\n",
       "    val bindings : 'a t -> (key * 'a) list\n",
       "    val min_binding : 'a t -> key * 'a\n",
       "    val min_binding_opt : 'a t -> (key * 'a) option\n",
       "    val max_binding : 'a t -> key * 'a\n",
       "    val max_binding_opt : 'a t -> (key * 'a) option\n",
       "    val choose : 'a t -> key * 'a\n",
       "    val choose_opt : 'a t -> (key * 'a) option\n",
       "    val split : key -> 'a t -> 'a t * 'a option * 'a t\n",
       "    val find : key -> 'a t -> 'a\n",
       "    val find_opt : key -> 'a t -> 'a option\n",
       "    val find_first : (key -> bool) -> 'a t -> key * 'a\n",
       "    val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option\n",
       "    val find_last : (key -> bool) -> 'a t -> key * 'a\n",
       "    val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option\n",
       "    val map : ('a -> 'b) -> 'a t -> 'b t\n",
       "    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t\n",
       "    val to_seq : 'a t -> (key * 'a) Seq.t\n",
       "    val to_rev_seq : 'a t -> (key * 'a) Seq.t\n",
       "    val to_seq_from : key -> 'a t -> (key * 'a) Seq.t\n",
       "    val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t\n",
       "    val of_seq : (key * 'a) Seq.t -> 'a t\n",
       "  end\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val example_env : int Env.t = <abstr>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 3\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "exception RuntimeError of string\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val eval : exp -> int Env.t -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val eval_condexp : condexp -> int Env.t -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val eval_cmd : cmd -> int Env.t -> int Env.t = <fun>\n",
       "val eval_program : program -> int Env.t -> int Env.t = <fun>\n",
       "val eval_commands : cmd list -> int Env.t -> int Env.t = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type op = Plus | Minus | Mult | Div \n",
    "\n",
    "type exp = Id of string | Numb of int | Op of exp * op * exp \n",
    "\n",
    "type cond = Eq | Neq | Lte | Lt | Gte | Gt \n",
    "type condexp = Cop of exp * cond * exp\n",
    "                                          \n",
    "type cmd = Asgn of string * exp \n",
    "         | Ite of condexp * cmd * cmd | If of condexp * cmd \n",
    "         | While of condexp * cmd\n",
    "         | Begin of program \n",
    "         | Print of exp \n",
    "         \n",
    "and program = Program of string list * cmd list\n",
    "\n",
    "(* This will define maps with strings as key *)\n",
    "module Env = Map.Make(String)\n",
    "\n",
    "(* Env.empty denotes the empty environment. \n",
    "We can add elements to an environment via Env.add.\n",
    "This is the environment which only binds “a” to 3. *)\n",
    "let example_env = Env.add \"a\" 3 Env.empty;;\n",
    "\n",
    "(* We can look up elements in an environment via Env.find.\n",
    "Env.find throws an exception if the key does not exist.*)\n",
    "Env.find \"a\" example_env;;\n",
    "\n",
    "exception RuntimeError of string\n",
    "\n",
    "let rec eval (e : exp) env : int = match e with \n",
    "    | Id x -> Env.find x env \n",
    "    | Numb n -> n \n",
    "    | Op (e1, Plus, e2) -> eval e1 env + eval e2 env\n",
    "    | Op (e1, Minus, e2) -> eval e1 env - eval e2 env\n",
    "    | Op (e1, Mult, e2) -> eval e1 env * eval e2 env\n",
    "    | Op (e1, Div, e2) ->  (match (eval e2 env) with \n",
    "                          | 0 -> raise (RuntimeError \"Divison by 0\")\n",
    "                          | _ -> eval e1 env / eval e2 env)\n",
    "                          \n",
    "let eval_condexp (e : condexp) env : int = match e with                          \n",
    "    | Cop (e1, Eq, e2) -> if (eval e1 env = eval e2 env) then 1 else 0\n",
    "    | Cop (e1, Neq, e2) -> if (eval e1 env = eval e2 env) then 0 else 1\n",
    "    | Cop (e1, Lte, e2) -> if (eval e1 env <= eval e2 env) then 1 else 0\n",
    "    | Cop (e1, Lt, e2) -> if (eval e1 env < eval e2 env) then 1 else 0\n",
    "    | Cop (e1, Gte, e2) -> if (eval e1 env >= eval e2 env) then 1 else 0\n",
    "    | Cop (e1, Gt, e2) -> if (eval e1 env > eval e2 env) then 1 else 0\n",
    "\n",
    "let rec eval_cmd (c : cmd) env  = match c with \n",
    "    | Asgn (x, e) -> Env.add x (eval e env) env\n",
    "    | If (e, c) -> (match (eval_condexp e env) with \n",
    "                        | 1 -> eval_cmd c env \n",
    "                        | 0 -> env\n",
    "                        | _ -> raise (RuntimeError \"Error in condition of If\")\n",
    "                        )\n",
    "    | Ite (e, c1, c2) -> (match (eval_condexp e env) with \n",
    "                        | 1 -> eval_cmd c1 env \n",
    "                        | 0 -> eval_cmd c2 env\n",
    "                        | _ -> raise (RuntimeError \"Error in condition of If\"))\n",
    "    | While (e, c) -> (match (eval_condexp e env) with \n",
    "                        | 1 -> eval_cmd (While (e, c)) (eval_cmd c env)\n",
    "                        | _ -> env)\n",
    "    | Begin p -> let _ = eval_program p env in env\n",
    "    | Print e -> let _ = print_endline (\"OUTPUT:\" ^ string_of_int (eval e env)) in env\n",
    "    \n",
    "and eval_program p env = match p with \n",
    "    | Program (xs, cmds) -> eval_commands cmds Env.empty\n",
    "\n",
    "and eval_commands (cs : cmd list) env = match cs with \n",
    "    | [] -> env\n",
    "    | c :: cs -> eval_commands cs (eval_cmd c env)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ba9f7e0",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "1. Extend expressions and the interpreter with a unary negation operator for integers, ``Neg``. \n",
    "Write an example of code and test that it evaluates correctly. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc2b974b",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[5]\", line 3, characters 19-21:\n3 | let e = (* TODO *) ;;\n                       ^^\nError: Syntax error\n"
     ]
    }
   ],
   "source": [
    "(* Write an example expression *)\n",
    "\n",
    "let e = (* TODO *) ;;\n",
    "\n",
    "eval e;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c741ab89",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "2. Extend commands with a ``DoWhile`` loop. \n",
    "\n",
    "See the following explanation of Wikipedia: \n",
    "*The do while construct consists of a process symbol and a condition. First the code within the block is executed. Then the condition is evaluated. If the condition is true the code within the block is executed again. This repeats until the condition becomes false.*\n",
    "\n",
    "Write an example of code and test that it evaluates correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b70d503",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [],
   "source": [
    "(* Write an example program *)\n",
    "\n",
    "let p = (* TODO *) ;;\n",
    "\n",
    "eval_program p Env.empty;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a0ced0f",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "3. Write a domain-specific language to manipulate Strings. \n",
    "\n",
    "You want to be able to: \n",
    "- Define variables of type String. \n",
    "- Concatenate Strings.\n",
    "- Print Strings.\n",
    "\n",
    "a.) Define a datatype ``string_exp`` of string expressions. \n",
    "   Your data type should contain: \n",
    "   - identifiers which represent strings.\n",
    "   - the empty string.\n",
    "   - a possibility to concatenate Strings.\n",
    "\n",
    "b.) Define a datatype ``string_stm`` of statements manipulating string variables. \n",
    "    They should contain:\n",
    "    - assignments \n",
    "    - the possibility to concatenate statements \n",
    "    \n",
    "c.) Define an interpreter for 1.) expressions, and 2.) statements.\n",
    "\n",
    "d.) (Optional - challenge) Build the possibility of Strings into ``Simp``. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92b5f507",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [],
   "source": [
    "(* Your code comes here *)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65e21f24",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "## Ex. 4 - Challenge\n",
    "\n",
    "Extend SIMP with unary function definitions: \n",
    "```\n",
    "\n",
    "type cmd = ... | FunctionDef of string (* function name *) \n",
    "                 * string (* arg name *) \n",
    "                 * cmd\n",
    "```\n",
    "\n",
    "and epxressions with a way to call a function: \n",
    "```\n",
    "\n",
    "type exp = ... | App of string (* function *) \n",
    "                        * exp (* argument *)\n",
    "```\n",
    "\n",
    "Define an interpreter for this extended language. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55eb0e1e",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "outputs": [],
   "source": [
    "(* Your code comes here *)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SoS",
   "language": "sos",
   "name": "sos"
  },
  "language_info": {
   "codemirror_mode": "sos",
   "file_extension": ".sos",
   "mimetype": "text/x-sos",
   "name": "sos",
   "nbconvert_exporter": "sos_notebook.converter.SoS_Exporter",
   "pygments_lexer": "sos"
  },
  "sos": {
   "kernels": [
    [
     "OCaml 4.13",
     "ocaml-jupyter-4.13",
     "OCaml",
     "",
     ""
    ],
    [
     "Python 3 (ipykernel)",
     "python3",
     "python3",
     "",
     {
      "name": "ipython",
      "version": 3
     }
    ],
    [
     "SoS",
     "sos",
     "",
     "",
     "sos"
    ]
   ],
   "panel": {
    "displayed": true,
    "height": 0
   },
   "version": "0.24.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}