Implicit-References-Vars.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implicit References\n",
    "\n",
    "Previously, we looked at explicit references in Lettuce using statements such as `NewRef`, `DeRef` and\n",
    "`AssignRef`.\n",
    "\n",
    "As a warmup exercise, what value does the following program compute?\n",
    "\n",
    "~~~ \n",
    "let x = NewRef(10) in \n",
    "   let g = function (y) \n",
    "            DeRef(x)\n",
    "        in \n",
    "       let dummy = AssignRef(x, 20) in \n",
    "            g (dummy)\n",
    "~~~\n",
    "\n",
    "*Answer:* Should be 20. Why? Note that x maps itself to a location (1) in the memory which stores the value 10.\n",
    "The function g ignores its argument and returns the dereference of x, i.e, whatever the location (1) points to.\n",
    "Next, we change this location to 20 under the hood. So when g is finally called, we get the contents of location (1), which is 20.\n",
    "\n",
    "\n",
    "Thus far, we have been using explicit references, wherein, we have to use NewRef to create a new reference,\n",
    "use DeRef everytime we want its value and AssignRef to assign to it.\n",
    "\n",
    "If we forget to use DeRef, we do not get the same result. As an example, consider the program\n",
    "\n",
    "~~~\n",
    "let x = NewRef(1) in\n",
    "   x\n",
    "~~~\n",
    "\n",
    "It returns a reference to a location in the store.\n",
    "\n",
    "However,  the program\n",
    "\n",
    "~~~\n",
    "let x = NewRef(1) in \n",
    "   DeRef(x)\n",
    "~~~\n",
    "\n",
    "returns the value 1.\n",
    "\n",
    "Our goal in this notebook is to mimic the behavior of mutable vars in scala. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The value of x is 11"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m11\u001b[39m\n",
       "\u001b[36my\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m10\u001b[39m"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var x = 10 // We do not need special NewRef when a var is created\n",
    "val y = x // Note that no deref is needed to get the value of x\n",
    "x = x + 1 // Here, we can assign to a var just like a ref, but on the RHS, we did notneed a deref.\n",
    "print(s\"The value of x is $x\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lecture, we will study **implicit references**. \n",
    "- These are references but we do not want to use NewRef to create a reference, we will look at syntax similar to `var` declarations in Scala.\n",
    "- We do not wish to use derefs to get the value. Whenever we refer to a var, we would directly like to get its value without using a deref.\n",
    "- Finally, we would like to use assignment on these vars just like we did on references.\n",
    "\n",
    "### Syntax for Vars in Lettuce\n",
    "\n",
    "Let us add an extra bit of syntax that will allow us to create such implicit references. Since this is lettuce,\n",
    "we will use the `let var` binding to specify that whatever is being bound to will be an implicit reference.\n",
    "\n",
    "~~~\n",
    "let var x = <expr> in \n",
    "      <body expr> \n",
    "~~~\n",
    "\n",
    "We will discard explicit reference operations `NewRef`, `AssignRef`, `DeRef`. Instead, we will just have the\n",
    "`let var` binding to create new implicit references (we will call them \"vars\" since they will behave exactly like\n",
    "scala's vars), and assignments.\n",
    "\n",
    "\n",
    "Let us do some example programs.\n",
    "\n",
    "~~~\n",
    "let var x = 10 in \n",
    "    let dummy = AssignVar(x, 20) in \n",
    "        x\n",
    "~~~\n",
    "\n",
    "This will be equivalent to \n",
    "\n",
    "~~~\n",
    "let x = NewRef(10) in \n",
    "    let dummy = AssignRef(x, 20) in \n",
    "        DeRef(x)\n",
    "~~~\n",
    "\n",
    "Note that `AssignRef` is now  called `AssignVar`, there is no more `DeRef`. These are the two major changes to our syntax.\n",
    "\n",
    "What does this program do?\n",
    "\n",
    "~~~ \n",
    "let var x = 10 in \n",
    "   let g = function (y) \n",
    "            x\n",
    "        in \n",
    "       let dummy = AssignVar(x, 20) in \n",
    "            g (dummy)\n",
    "~~~\n",
    "\n",
    "We can implement some funky stuff such as changing the binding of a function.\n",
    "\n",
    "~~~\n",
    "let var f = function (x) x + 10 in \n",
    "  let g = function (y) y - 10 in \n",
    "    let d = f(10) in \n",
    "       let dummy = AssignVar(f, g) in \n",
    "          d - f(10)\n",
    "~~~\n",
    "\n",
    "Notice how we assigned `f` to `g` because `f` is a var. So it is assignable. Also note that we do not need\n",
    "to say DeRef in this language. Finally, notice how g is an immutable val whereas f is a mutable var.\n",
    "\n",
    "## Abstract Syntax of Lettuce with Mutable References\n",
    "\n",
    "$$\\begin{array}{rcll}\n",
    "\\mathbf{Program} & \\rightarrow & TopLevel(\\mathbf{Expr}) \\\\[5pt]\n",
    "\\mathbf{Expr} & \\rightarrow & Const(\\mathbf{Number}) \\\\\n",
    " & | & Ident(\\mathbf{Identifier}) \\\\\n",
    " & | & Plus(\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n",
    " & | & Minus(\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n",
    " & | & Mult (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n",
    " & | & Geq (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n",
    " & | & Eq (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n",
    " & | & IfThenElse(\\mathbf{Expr}, \\mathbf{Expr}, \\mathbf{Expr}) & \\text{if (expr) then expr else expr} \\\\\n",
    " & | & Let( \\mathbf{Identifier}, \\mathbf{Expr}, \\mathbf{Expr}) & \\text{let identifier = expr in expr} \\\\\n",
    " & | & FunDef( \\mathbf{Identifier}, \\mathbf{Expr}) & \\text{function (identifier-formal-parameter) expr } \\\\ \n",
    " & | & FunCall(\\mathbf{Expr}, \\mathbf{Expr}) & \\text{function call - expr(expr)} \\\\\n",
    " & | & \\color{red}{LetVar}(\\mathbf{Identifier}, \\mathbf{Expr}, \\mathbf{Expr}) & \\text{let var stmt -- compare to let binding.}\\\\\n",
    " & | & \\color{red}{AssignVar}(\\mathbf{Identifier}, \\mathbf{Expr}) & \\text{assign a var to a value. }\n",
    "\\end{array}$$\n",
    "\n",
    "It should be an easy exercise to define this in Scala, which we will do later.\n",
    "\n",
    "## Operational Semantics\n",
    "\n",
    "How do we evaluate implicit references under the hood? Simple, the same way as we evaluate explicit references. In other words, we are going to keep the innards of our interpreter unchanged from what it was previously.\n",
    "\n",
    "Let us recap how this was done. This part is  cut and paste from the last week's notes.\n",
    "\n",
    "1. We will make a _new value type_ for references since our expressions an evaluate to real numbers, booleans, closures and now <font color=\"red\"> references </font>.\n",
    "2. To go hand in hand with references, we need to define an abstract notion of memory. We will call this a <font color=\"red\"> store </font>.\n",
    "\n",
    "<font color=\"red\"> Note that the vars will point to these references. </font>\n",
    "\n",
    "\n",
    "### Stores\n",
    "\n",
    "Memory address are going to be numbered 0, 1, 2, .... with natural numbers and each address is going to be associated with a value. \n",
    "\n",
    "The store needs to support the following operations.\n",
    "\n",
    "- Create a new memory cell in the store and assign it to a value. This is exactly what will implement the `NewRef` operation. Let us call it <font color=\"red\">createNewCell</font> operation on stores.\n",
    "\n",
    "- Lookup the value of a memory cell. Let us call it <font color=\"red\"> lookupCellValue </font> operation. If the value does not exist, we will return error (and bail).\n",
    "\n",
    "- Assign a cell to a new value. Let us call it <font color=\"red\"> assignToCell </font>\n",
    "\n",
    "Hand in hand with stores, we have to extend our value type. Existing value types are\n",
    "- `ErrorValue` to denote error -- though in our physical implementation, we have never issued this value. We rather prefer to bail with an exception. We will continue to do so to make our lives simpler. Operational semantics will be written with error values, but the actual code will bail on error.\n",
    "\n",
    "- `NumValue(f)` for number `f`. We will denote these as reals $\\mathbb{R}$ in our semantics.\n",
    "- `BoolValue(b)` for boolean `b`. We will denote these as $\\mathbb{B}$ in our semantics.\n",
    "- `Closure(x, e, sigma)` for closures. We will denote these as $\\mathbf{Closure}$ in our semantics.\n",
    "\n",
    "Finally, we add references:\n",
    "- `Reference(j)`, which is a reference to cell number j in our store. \n",
    "\n",
    "### Operational Semantics\n",
    "\n",
    "Once again, our operational semantics defines an __eval__ function that has three parts to it.\n",
    "$$\\newcommand\\semRule[3]{\\begin{array}{c} #1 \\\\ \\hline #2 \\\\\\end{array}\\ \\ \\text{(#3)}} $$\n",
    "$$\\newcommand\\eval{\\mathbf{eval}}$$\n",
    "$$\\eval(\\texttt{expr}, \\texttt{env}, \\texttt{store})  = (\\text{value}, \\text{new-store}) $$\n",
    "\n",
    "Let us explain how it will be organized. There are two kinds of bindings: \n",
    "- Immutable vals are bound to values in the environment.\n",
    "- Mutable vars are bound to `Reference(j)` where `j` is an address in the store.\n",
    "\n",
    "### Semantic Rule for Constant\n",
    "\n",
    "The rule for constant remains unchanged.\n",
    "$$\\semRule{}{\\eval(\\texttt{Const(f)}, \\sigma, s) = ( f, s) }{const}$$\n",
    "\n",
    "### Semantic Rule for Identifiers (How the automatic Deref is implemented)\n",
    "\n",
    "Identifiers are going to be slightly more complex. Let us go over the interesting case first.\n",
    "The following rule ensures that whenever we evaluate an identifier $x$ that happens to be\n",
    "a var, we will actually return the stored value.\n",
    "\n",
    "$$\\semRule{x \\in \\text{domain}(\\sigma),\\ \\sigma(x) = \\texttt{Reference}(j), \\texttt{lookupCell}(s, j) = v}{ \\eval(\\texttt{Ident(x)}, \\sigma, s) = (v, s) }{ident-var-ok}$$\n",
    "\n",
    "- The variable $x$ belongs to the environment $\\sigma$.\n",
    "- It evalutes to a reference to cell $j$ in store.\n",
    "- Cell $j$ in the store $s$ has value $v$.\n",
    "- Evaluating the identifier $x$ under environment $\\sigma$ and store $s$ has value $v$.\n",
    "\n",
    "Note how that whenever we touch a reference, we automatically chase the value corresponding to the reference\n",
    "in the store and return that.\n",
    "\n",
    "For immutable, we have the usual semantics:\n",
    "\n",
    "$$\\semRule{x \\in \\text{domain}(\\sigma),\\ \\sigma(x) = v, v \\not= \\texttt{Reference}(j) }{ \\eval(\\texttt{Ident(x)}, \\sigma, s) = (v, s) }{ident-val-ok}$$\n",
    "\n",
    "### Semantic Rules for LetVar\n",
    "\n",
    "We will now write the semantic rule for let ref. The idea is that we will generate a new reference.\n",
    "\n",
    "\n",
    "$$\\semRule{\\eval(\\texttt{e1}, \\sigma, s) = (v, s_1), \\;\\; v \\not= \\mathbf{error},\\;\\;\\; \\texttt{createNewCell}(s_1,v) = (j, s_2)\\;\\;  }{\\eval(\\texttt{LetVar(x, e1, e2)}, \\sigma, s) =  \\eval(\\texttt{e2}, \\sigma[x \\mapsto \\texttt{Reference}(j)], s_2 }{let-var-ok}$$\n",
    "\n",
    "- First evaluate `e1` under the environment $\\sigma$ and store $s$, results in value $v$ that is not error and store $s_1$.\n",
    "- Create a new cell in $s_1$, let it be a reference to cell number j and store $s_2$.\n",
    "- Evaluating `let var x = e1 in e2` is the same as evaluating `e2` under environment $\\sigma[x \\mapsto \\texttt{Reference}(j)]$ and store $s_2$.\n",
    "\n",
    "### Semantic Rule for AssignVar\n",
    "\n",
    "The semantic rule for `AssignVar` is the same as that for `AssignRef` but under a new guise.\n",
    "\n",
    "$$\\semRule{x \\in \\text{domain}(\\sigma),\\ \\sigma(x) = \\texttt{Reference}(j),\\;\\;\\eval(\\texttt{e}, \\sigma, s) = (v, s_1), \\;\\;  \\texttt{assignToCell}(s_1, j, v) = s_2}{ \\eval(\\texttt{AssignVar(x, e)}, \\sigma, s) = (v, s_2) } {assign-var-ok} $$\n",
    "- $x$ must be mapped to a reference to cell $j$ in the current environment $\\sigma$.\n",
    "- $e$ must evaluate under $\\sigma$ and store $s$ to $v$ with new store $s_1$.\n",
    "- The store $s_2$ is obtained when we assign the value $v$ to cell $j$ in $s_1$.\n",
    "- The expression $\\texttt{AssignVar}(x, e)$ under env. $\\sigma$ and store $s$ yields value $v$ and the store $s_2$.\n",
    "\n",
    "The remaining rules remain unchanged from the case of explicit refs. \n",
    "\n",
    "### Implementing the Interpreter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mProgram\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mTopLevel\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConst\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIdent\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMinus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMult\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mGeq\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mEq\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIfThenElse\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mLet\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mFunDef\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mFunCall\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mLetVar\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mAssignVar\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Program\n",
    "sealed trait Expr\n",
    "\n",
    "case class TopLevel(e: Expr) extends Program\n",
    "\n",
    "case class Const(v: Double) extends Expr // Expr -> Const(v)\n",
    "case class Ident(s: String) extends Expr // Expr -> Ident(s)\n",
    "\n",
    "// Arithmetic Expressions\n",
    "case class Plus(e1: Expr, e2: Expr) extends Expr // Expr -> Plus(Expr, Expr)\n",
    "case class Minus(e1: Expr, e2: Expr) extends Expr // Expr -> Minus(Expr, Expr)\n",
    "case class Mult(e1: Expr, e2: Expr) extends Expr // Expr -> Mult (Expr, Expr)\n",
    "\n",
    "// Boolean Expressions\n",
    "case class Geq(e1: Expr, e2:Expr) extends Expr\n",
    "case class Eq(e1: Expr, e2: Expr) extends Expr\n",
    "\n",
    "//If then else\n",
    "case class IfThenElse(e: Expr, eIf: Expr, eElse: Expr) extends Expr\n",
    "\n",
    "//Let bindings\n",
    "case class Let(s: String, defExpr: Expr, bodyExpr: Expr) extends Expr\n",
    "\n",
    "//Function definition\n",
    "case class FunDef(param: String, bodyExpr: Expr) extends Expr\n",
    "\n",
    "// Function call\n",
    "case class FunCall(funCalled: Expr, argExpr: Expr) extends Expr\n",
    "\n",
    "// Let Var\n",
    "case class LetVar(x: String, e1: Expr, e2: Expr) extends Expr\n",
    "\n",
    "// Assign Var\n",
    "case class AssignVar(x: String, e: Expr) extends Expr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mValue\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNumValue\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mBoolValue\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mClosure\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mReference\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mErrorValue\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mvalueToNumber\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mvalueToBoolean\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mvalueToClosure\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mImmutableStore\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcreateNewCell\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mlookupCellValue\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36massignToCell\u001b[39m"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Copy from the case for explicit references\n",
    "sealed trait Value\n",
    "\n",
    "\n",
    "/*-- Now we can finish the rest --*/\n",
    "case class NumValue(f: Double) extends Value\n",
    "case class BoolValue(b: Boolean) extends Value\n",
    "/*-- Note: to get recursion working, we will need to make environments different --*/\n",
    "case class Closure(x: String, e: Expr, pi: Map[String, Value]) extends Value \n",
    "/* -- references are here -- */\n",
    "case class Reference(j: Int) extends Value\n",
    "case object ErrorValue extends Value\n",
    "\n",
    "\n",
    "/*2. Operators on values */\n",
    "\n",
    "def valueToNumber(v: Value): Double = v match {\n",
    "    case NumValue(d) => d\n",
    "    case _ => throw new IllegalArgumentException(s\"Error: Asking me to convert Value: $v to a number\")\n",
    "}\n",
    "\n",
    "def valueToBoolean(v: Value): Boolean = v match {\n",
    "    case BoolValue(b) => b\n",
    "    case _ => throw new IllegalArgumentException(s\"Error: Asking me to convert Value: $v to a boolean\")\n",
    "}\n",
    "\n",
    "def valueToClosure(v: Value): Closure = v match {\n",
    "    case Closure(x, e, pi) => Closure(x, e, pi)\n",
    "    case _ =>  throw new IllegalArgumentException(s\"Error: Asking me to convert Value: $v to a closure\")\n",
    "}\n",
    "\n",
    "/*3. Immutable Store */\n",
    "\n",
    "case class ImmutableStore(val nCells: Int, val storeMap: Map[Int, Value])\n",
    "    \n",
    "def createNewCell(s: ImmutableStore, v: Value): (ImmutableStore, Int) = {\n",
    "        /*- make a new cell -*/\n",
    "        val j = s.nCells\n",
    "        val nMap = s.storeMap + (j -> v)\n",
    "        val nStore = ImmutableStore(s.nCells + 1, nMap) // Make a new store with one more cell\n",
    "        (nStore, j)\n",
    "}\n",
    "    \n",
    "def lookupCellValue(s: ImmutableStore, j: Int): Value = {\n",
    "        if (s.storeMap.contains(j)){\n",
    "            s.storeMap(j)\n",
    "        } else {\n",
    "            throw new IllegalArgumentException(s\"Illegal lookup of nonexistant location $j\")\n",
    "        }\n",
    "}\n",
    "    \n",
    "def assignToCell(s: ImmutableStore, j: Int, v: Value): ImmutableStore = {\n",
    "        if (s.storeMap.contains(j)){\n",
    "            val nMap = s.storeMap + (j -> v) // Update the store map.\n",
    "            ImmutableStore(s.nCells, nMap)\n",
    "        } else {\n",
    "            throw new IllegalArgumentException(s\"Illegal assignment to nonexistent location $j\")\n",
    "        }\n",
    "    }\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalProgram\u001b[39m"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evalExpr(e: Expr, env: Map[String, Value], store: ImmutableStore): (Value, ImmutableStore) = {\n",
    "      /* Method to deal with binary arithmetic operations */\n",
    "    \n",
    "    def applyArith2 (e1: Expr, e2: Expr) (fun: (Double , Double) => Double) = {\n",
    "        val (v1, store1) = evalExpr(e1, env, store)\n",
    "        val (v2, store2) = evalExpr(e2, env, store1)\n",
    "        val v3 = fun(valueToNumber(v1), valueToNumber(v2))\n",
    "        (NumValue(v3), store2)\n",
    "    }  /* -- We have deliberately curried the method --*/\n",
    "    \n",
    "    /* Helper method to deal with unary arithmetic */\n",
    "    def applyArith1(e: Expr) (fun: Double => Double) = {\n",
    "        val (v,store1) = evalExpr(e, env, store)\n",
    "        val v1 = fun(valueToNumber(v))\n",
    "        (NumValue(v1), store1)\n",
    "    }\n",
    "    \n",
    "    /* Helper method to deal with comparison operators */\n",
    "    def applyComp(e1: Expr, e2: Expr) (fun: (Double, Double) => Boolean) = {\n",
    "        val (v1, store1) = evalExpr(e1, env, store)\n",
    "        val (v2, store2) = evalExpr(e2, env, store1)\n",
    "        val v3 = fun(valueToNumber(v1), valueToNumber(v2))\n",
    "        (BoolValue(v3), store2)\n",
    "    }\n",
    "    \n",
    "    e match {\n",
    "        case Const(f) => (NumValue(f), store)\n",
    "        \n",
    "        case Ident(x) => {\n",
    "            if (env contains x) {\n",
    "                val v = env(x)\n",
    "                v match {\n",
    "                    case Reference(j) => {\n",
    "                        val v1 = lookupCellValue(store, j)\n",
    "                        (v1, store)           \n",
    "                    }\n",
    "                    case _ => (v, store)\n",
    "                }  \n",
    "            } else \n",
    "                throw new IllegalArgumentException(s\"Undefined identifier $x\")\n",
    "        }\n",
    "    \n",
    "    \n",
    "        case Plus(e1, e2) => applyArith2 (e1, e2) ( _ + _ )\n",
    "            \n",
    "        case Minus(e1, e2) => applyArith2(e1, e2) ( _ - _ )\n",
    "    \n",
    "        case Mult(e1, e2) =>  applyArith2(e1, e2) (_ * _)\n",
    "        \n",
    "        case Geq(e1, e2) => applyComp(e1, e2)(_ >= _)\n",
    "    \n",
    "        case Eq(e1, e2) => applyComp(e1, e2)(_ == _)\n",
    "        \n",
    "        case IfThenElse(e1, e2, e3) => {\n",
    "            val (v, store1) = evalExpr(e1, env, store)\n",
    "            v match {\n",
    "                case BoolValue(true) => evalExpr(e2, env, store1)\n",
    "                case BoolValue(false) => evalExpr(e3, env, store1)\n",
    "                case _ => throw new IllegalArgumentException(s\"If-then-else condition expr: ${e1} is non-boolean -- evaluates to ${v}\")\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        case Let(x, e1, e2) => {\n",
    "            val (v1, store1) = evalExpr(e1, env, store)  // eval e1\n",
    "            val env2 = env + (x -> v1) // create a new extended env\n",
    "            evalExpr(e2, env2, store1) // eval e2 under that.\n",
    "        }\n",
    "    \n",
    "        case FunDef(x, e) => {\n",
    "            (Closure(x, e, env), store) // Return a closure with the current enviroment.\n",
    "        }\n",
    "        \n",
    "        case FunCall(e1, e2) => {\n",
    "            val (v1, store1) = evalExpr(e1, env, store)\n",
    "            val (v2, store2) = evalExpr(e2, env, store1)\n",
    "            v1 match {\n",
    "                case Closure(x, closure_ex, closed_env) => {\n",
    "                    // First extend closed_env by binding x to v2\n",
    "                    val new_env = closed_env + ( x -> v2)\n",
    "                    // Evaluate the body of the closure under the extended environment.\n",
    "                    evalExpr(closure_ex, new_env, store2)\n",
    "                }\n",
    "                case _ => throw new IllegalArgumentException(s\"Function call error: expression $e1 does not evaluate to a closure\")\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        \n",
    "        \n",
    "        case AssignVar(x, e) => {\n",
    "            val (v1, store1) = evalExpr(e, env, store)\n",
    "            val v2 =  if (env contains x) \n",
    "                        env(x)\n",
    "                      else \n",
    "                        throw new IllegalArgumentException(s\"Undefined identifier $x\")\n",
    "            v2 match {\n",
    "                case Reference(j) => {\n",
    "                    val store3 = assignToCell(store1, j, v1)\n",
    "                    (v1, store3)\n",
    "                }\n",
    "                case _ => throw new IllegalArgumentException(s\"AssignVar applied to argument that is not a mutable var\")\n",
    "                \n",
    "            }\n",
    "        }\n",
    "        \n",
    "        case LetVar(x, e1, e2) => {\n",
    "            val (v1, store1) = evalExpr(e1, env, store)\n",
    "            val (store2, j) = createNewCell(store1, v1)\n",
    "            val newEnv = env + (x -> Reference(j))\n",
    "            evalExpr(e2, newEnv, store2)\n",
    "        }\n",
    "        \n",
    "    }\n",
    "\n",
    "}\n",
    "\n",
    "def evalProgram(p: Program) = p match {\n",
    "        case TopLevel(e) => { \n",
    "            // Start with empty environment and empty store\n",
    "            val (v1, s1) = evalExpr(e, Map(), new ImmutableStore(0, Map()))\n",
    "            v1\n",
    "        }\n",
    "}\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result = NumValue(20.0)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36me1\u001b[39m: \u001b[32mLet\u001b[39m = Let(dummy,AssignVar(x,Const(20.0)),Ident(x))\n",
       "\u001b[36me2\u001b[39m: \u001b[32mLetVar\u001b[39m = LetVar(x,Const(10.0),Let(dummy,AssignVar(x,Const(20.0)),Ident(x)))\n",
       "\u001b[36mprog\u001b[39m: \u001b[32mTopLevel\u001b[39m = TopLevel(LetVar(x,Const(10.0),Let(dummy,AssignVar(x,Const(20.0)),Ident(x))))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "/* let var x = 10 in \n",
    "    let dummy = AssignVar(x, 20) in \n",
    "        x\n",
    "        */\n",
    "val x = Ident(\"x\")\n",
    "val e1 = Let(\"dummy\", AssignVar(\"x\", Const(20)), x)\n",
    "val e2 = LetVar(\"x\", Const(10), e1)\n",
    "val prog = TopLevel(e2)\n",
    "\n",
    "println(s\"Result = ${evalProgram(prog)}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result = NumValue(20.0)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mg\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"g\"\u001b[39m)\n",
       "\u001b[36mdummy\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"dummy\"\u001b[39m)\n",
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36me1\u001b[39m: \u001b[32mFunCall\u001b[39m = FunCall(Ident(g),Ident(dummy))\n",
       "\u001b[36me2\u001b[39m: \u001b[32mLet\u001b[39m = Let(dummy,AssignVar(x,Const(20.0)),FunCall(Ident(g),Ident(dummy)))\n",
       "\u001b[36mgdef\u001b[39m: \u001b[32mFunDef\u001b[39m = FunDef(y,Ident(x))\n",
       "\u001b[36me3\u001b[39m: \u001b[32mLet\u001b[39m = Let(g,FunDef(y,Ident(x)),Let(dummy,AssignVar(x,Const(20.0)),FunCall(Ident(g),Ident(dummy))))\n",
       "\u001b[36me4\u001b[39m: \u001b[32mLetVar\u001b[39m = LetVar(x,Const(10.0),Let(g,FunDef(y,Ident(x)),Let(dummy,AssignVar(x,Const(20.0)),FunCall(Ident(g),Ident(dummy)))))\n",
       "\u001b[36mprog\u001b[39m: \u001b[32mTopLevel\u001b[39m = TopLevel(LetVar(x,Const(10.0),Let(g,FunDef(y,Ident(x)),Let(dummy,AssignVar(x,Const(20.0)),FunCall(Ident(g),Ident(dummy))))))"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "/*~~~ \n",
    "let var x = 10 in \n",
    "   let g = function (y) \n",
    "            x\n",
    "        in \n",
    "       let dummy = AssignVar(x, 20) in \n",
    "            g (dummy)\n",
    "~~~*/\n",
    "val g = Ident(\"g\")\n",
    "val dummy = Ident(\"dummy\")\n",
    "val x = Ident(\"x\")\n",
    "\n",
    "val e1 = FunCall(g, dummy)\n",
    "val e2 = Let(\"dummy\", AssignVar(\"x\", Const(20)), e1)\n",
    "val gdef = FunDef(\"y\", x)\n",
    "val e3 = Let(\"g\", gdef, e2)\n",
    "val e4 = LetVar(\"x\",  Const(10), e3)\n",
    "val prog = TopLevel(e4)\n",
    "\n",
    "println(s\"Result = ${evalProgram(prog)}\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result = NumValue(15.0)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36md\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"d\"\u001b[39m)\n",
       "\u001b[36mf\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"f\"\u001b[39m)\n",
       "\u001b[36mg\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"g\"\u001b[39m)\n",
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36my\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)\n",
       "\u001b[36me1\u001b[39m: \u001b[32mMinus\u001b[39m = Minus(Ident(d),FunCall(Ident(f),Const(10.0)))\n",
       "\u001b[36me2\u001b[39m: \u001b[32mLet\u001b[39m = Let(dummy,AssignVar(f,Ident(g)),Minus(Ident(d),FunCall(Ident(f),Const(10.0))))\n",
       "\u001b[36me3\u001b[39m: \u001b[32mLet\u001b[39m = Let(d,FunCall(Ident(f),Const(10.0)),Let(dummy,AssignVar(f,Ident(g)),Minus(Ident(d),FunCall(Ident(f),Const(10.0)))))\n",
       "\u001b[36mgdef\u001b[39m: \u001b[32mFunDef\u001b[39m = FunDef(y,Minus(Ident(y),Const(5.0)))\n",
       "\u001b[36me4\u001b[39m: \u001b[32mLet\u001b[39m = Let(g,FunDef(y,Minus(Ident(y),Const(5.0))),Let(d,FunCall(Ident(f),Const(10.0)),Let(dummy,AssignVar(f,Ident(g)),Minus(Ident(d),FunCall(Ident(f),Const(10.0))))))\n",
       "\u001b[36mfdef\u001b[39m: \u001b[32mFunDef\u001b[39m = FunDef(x,Plus(Ident(x),Const(10.0)))\n",
       "\u001b[36me5\u001b[39m: \u001b[32mLetVar\u001b[39m = LetVar(f,FunDef(x,Plus(Ident(x),Const(10.0))),Let(g,FunDef(y,Minus(Ident(y),Const(5.0))),Let(d,FunCall(Ident(f),Const(10.0)),Let(dummy,AssignVar(f,Ident(g)),Minus(Ident(d),FunCall(Ident(f),Const(10.0)))))))\n",
       "\u001b[36mprog\u001b[39m: \u001b[32mTopLevel\u001b[39m = TopLevel(LetVar(f,FunDef(x,Plus(Ident(x),Const(10.0))),Let(g,FunDef(y,Minus(Ident(y),Const(5.0))),Let(d,FunCall(Ident(f),Const(10.0)),Let(dummy,AssignVar(f,Ident(g)),Minus(Ident(d),FunCall(Ident(f),Const(10.0))))))))"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "/*---\n",
    "let var f = function (x) x + 10 in \n",
    "  let g = function (y) y - 5 in \n",
    "    let d = f(10) in \n",
    "       let dummy = AssignVar(f, g) in \n",
    "          d - f(10)\n",
    "          */\n",
    "val d = Ident(\"d\")\n",
    "val f = Ident(\"f\")\n",
    "val g = Ident(\"g\")\n",
    "val x = Ident(\"x\")\n",
    "val y = Ident(\"y\")\n",
    "\n",
    "val e1 = Minus(d, FunCall(f, Const(10)))\n",
    "val e2 = Let(\"dummy\", AssignVar(\"f\", g), e1)\n",
    "val e3 = Let(\"d\", FunCall(f, Const(10)), e2)\n",
    "val gdef = FunDef(\"y\", Minus(y, Const(5)))\n",
    "val e4 = Let(\"g\", gdef, e3)\n",
    "val fdef = FunDef(\"x\", Plus(x, Const(10)))\n",
    "val e5 = LetVar(\"f\", fdef, e4)\n",
    "val prog = TopLevel(e5)\n",
    "println(s\"Result = ${evalProgram(prog)}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.12.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}