csci3155

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "71c6cfda",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel $\\rightarrow$ Restart) and then **run all cells** (in the menubar, select Cell $\\rightarrow$ Run All).\n",
    "\n",
    "Make sure you fill in any place that says `???`, `YOUR CODE HERE`, \"???\", \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "4313a4e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n",
       "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"\"\u001b[39m"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val NAME = \"Jack Sangdahl\"\n",
    "val COLLABORATORS = \"N/A\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9e75639-fa29-4bcb-a412-bd8ece4194ce",
   "metadata": {},
   "source": [
    "$\\newcommand{\\TirName}[1]{\\text{#1}}\n",
    "\\newcommand{\\inferrule}[3][]{\n",
    "  \\let\\and\\qquad\n",
    "  \\begin{array}{@{}l@{}}\n",
    "  \\TirName{#1}\n",
    "  \\\\\n",
    "  \\displaystyle\n",
    "  \\frac{#2}{#3}\n",
    "  \\end{array}\n",
    "}\n",
    "\\newcommand{\\infer}[3][]{\\inferrule[#1]{#2}{#3}}\n",
    "$\n",
    "\n",
    "# Exercise: Programming with Encapsulated Effects\n",
    "\n",
    "<!-- 3 Expressions -->\n",
    "\n",
    "<!-- 4 Binding and Scope -->\n",
    "\n",
    "<!-- 8 Recursion -->\n",
    "\n",
    "<!-- 9 Inductive Data Types -->\n",
    "\n",
    "<!-- 11 Concrete Syntax -->\n",
    "\n",
    "<!-- 12 Abstract Syntax and Parsing -->\n",
    "\n",
    "<!-- 13 Exercise: Syntax -->\n",
    "\n",
    "<!-- 14 Static Scoping -->\n",
    "\n",
    "<!-- 15 Judgments -->\n",
    "\n",
    "<!-- 16 Variables, Basic Values, and Judgments Lab -->\n",
    "\n",
    "<!-- 18 Operational Semantics -->\n",
    "\n",
    "<!-- 19 Functions and Dynamic Scoping -->\n",
    "\n",
    "<!-- 20 Big-Step Exercise -->\n",
    "\n",
    "<!-- 21 Evaluation Order  -->\n",
    "\n",
    "<!-- 26 Static Type Checking -->\n",
    "\n",
    "<!-- 27 Objects -->\n",
    "\n",
    "<!-- 27 Static Type Checking Lab -->\n",
    "\n",
    "<!-- 30 Mutable State -->\n",
    "\n",
    "<!-- Encapsulating Effects Exercise -->\n",
    "\n",
    "### Learning Goals\n",
    "\n",
    "The primary learning goal of this exercise is to get experience\n",
    "programming with encapsulated effects.\n",
    "\n",
    "We will also consider the idea of transforming code represented as an\n",
    "abstract syntax tree to make it easier to implement subsequent passes\n",
    "like interpretation.\n",
    "\n",
    "### Instructions\n",
    "\n",
    "This assignment asks you to write Scala code. There are restrictions\n",
    "associated with how you can solve these problems. Please pay careful\n",
    "heed to those. If you are unsure, ask the course staff.\n",
    "\n",
    "Note that `???` indicates that there is a missing function or code\n",
    "fragment that needs to be filled in. Make sure that you remove the `???`\n",
    "and replace it with the answer.\n",
    "\n",
    "Use the test cases provided to test your implementations. You are also\n",
    "encouraged to write your own test cases to help debug your work.\n",
    "However, please delete any extra cells you may have created lest they\n",
    "break an autograder.\n",
    "\n",
    "### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "0d92d0c2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f54ea3fcefbe483a990582ef3ecd2a1d",
     "grade": false,
     "grade_id": "testing",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[39m\u001b[36mRun this cell FIRST before testing.\n",
       "import $ivy.$                                , org.scalatest._, events._, flatspec._, matchers.should._\n",
       "\u001b[39m\n",
       "\u001b[32mimport \u001b[39m\u001b[36m$ivy.$                                            , org.scalatestplus.scalacheck._\n",
       "\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mpassed\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Run this cell FIRST before testing.\n",
    "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._, matchers.should._\n",
    "import $ivy.`org.scalatestplus::scalacheck-1-18:3.2.19.0`, org.scalatestplus.scalacheck._\n",
    "def report(suite: Suite): Unit = suite.execute(stats = true)\n",
    "def assertPassed(suite: Suite): Unit =\n",
    "  suite.run(None, Args(new Reporter {\n",
    "    def apply(e: Event) = e match {\n",
    "      case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n",
    "      case _ => ()\n",
    "    }\n",
    "  }))\n",
    "def passed(points: Int): Unit = {\n",
    "  require(points >= 0)\n",
    "  if (points == 1) println(\"*** 🎉 Tests Passed (1 point) ***\")\n",
    "  else println(s\"*** 🎉 Tests Passed ($points points) ***\")\n",
    "}\n",
    "def test(suite: Suite, points: Int): Unit = {\n",
    "  report(suite)\n",
    "  assertPassed(suite)\n",
    "  passed(points)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a662e14f-b397-418e-a640-0dd8f91e9fc1",
   "metadata": {},
   "source": [
    "## TypeScripty: Numbers, Booleans, and Functions\n",
    "\n",
    "### Syntax\n",
    "\n",
    "In this assignment, we consider a simplified TypeScripty with numbers,\n",
    "booleans, and functions types.\n",
    "\n",
    "Function literals\n",
    "$x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1$\n",
    "have exactly one parameter, are always named, and must have a return\n",
    "type annotation. The name may be used to define recursive functions.\n",
    "\n",
    "The expressions include variable uses $x$, variable binding\n",
    "$\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2$, unary\n",
    "$\\mathop{\\mathit{uop}} e_1$ and binary $e_1 \\mathbin{\\mathit{bop}} e_2$\n",
    "expressions, if-then-else $e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3$, and\n",
    "function call $e_1\\texttt{(}e_2\\texttt{)}$. The unary operators are\n",
    "limited to number negation $\\texttt{-}$ and boolean negation\n",
    "$\\texttt{!}$, and the binary operators are limited to number addition\n",
    "$\\texttt{+}$, number times $\\texttt{*}$, and equality $\\texttt{===}$:\n",
    "\n",
    "$$\n",
    "\\begin{array}{rrrl}\n",
    "  \\text{types} & \\tau& \\mathrel{::=}&\n",
    "  \\texttt{number}\n",
    "  \\mid\\texttt{bool}\n",
    "  \\mid\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau'\n",
    "  \\\\\n",
    "  \\text{values} & v& \\mathrel{::=}&\n",
    "  n\n",
    "  \\mid b\n",
    "  \\mid x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n",
    "  \\\\\n",
    "  \\text{expressions} & e& \\mathrel{::=}&\n",
    "  x\n",
    "  \\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n",
    "  \\\\\n",
    "  & & \\mid& n\n",
    "  \\mid\\mathop{\\mathit{uop}} e_1\n",
    "  \\mid e_1 \\mathbin{\\mathit{bop}} e_2\n",
    "  \\\\\n",
    "  & & \\mid& b\n",
    "  \\mid e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n",
    "  \\\\\n",
    "  & & \\mid& x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n",
    "  \\mid e_1\\texttt{(}e_2\\texttt{)}\n",
    "  \\\\\n",
    "  \\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{-}\\mid\\texttt{!}\n",
    "  \\\\\n",
    "  \\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{+}\\mid\\texttt{*}\\mid\\texttt{===}\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "Figure 1: Syntax of TypeScripty with recursive functions and limited\n",
    "arithmetic-logical expressions.\n",
    "\n",
    "We give a Scala representation of the abstract syntax, along with an\n",
    "implementation of computing the free variables of an expression and\n",
    "determining an expression is closed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "eb35c7e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mTyp\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mTNumber\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mTBool\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mTFun\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mVar\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConstDecl\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mN\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mUnary\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mBinary\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mB\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIf\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mFun\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCall\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mUop\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNeg\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNot\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mBop\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mTimes\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mEq\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfreeVars\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36misClosed\u001b[39m"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trait Typ                                                // t\n",
    "case object TNumber extends Typ                          // t ::= number\n",
    "case object TBool extends Typ                            // t ::= bool\n",
    "case class TFun(yt: (String,Typ), tret: Typ) extends Typ // t ::= (y: t) => tret\n",
    "\n",
    "trait Expr                                                       // e\n",
    "case class Var(x: String) extends Expr                           // e ::= x\n",
    "case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2\n",
    "\n",
    "case class N(n: Double) extends Expr                         // e ::= n\n",
    "case class Unary(uop: Uop, e1: Expr) extends Expr            // e ::= uop e1\n",
    "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop b2\n",
    "\n",
    "case class B(b: Boolean) extends Expr                    // e ::= b\n",
    "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3\n",
    "\n",
    "case class Fun(x: String, yt: (String, Typ), tret: Typ, e1: Expr) extends Expr // e ::= x(y: t): tret => e1\n",
    "case class Call(e1: Expr, e2: Expr) extends Expr                               // e ::= e1(e2)\n",
    "\n",
    "trait Uop                   // uop\n",
    "case object Neg extends Uop // uop ::= -\n",
    "case object Not extends Uop // uop ::= !\n",
    "\n",
    "trait Bop                     // bop\n",
    "case object Plus extends Bop  // bop ::= *\n",
    "case object Times extends Bop // bop ::= *\n",
    "case object Eq extends Bop    // bop ::= ===\n",
    "\n",
    "def freeVars(e: Expr): Set[String] = e match {\n",
    "  case Var(x) => Set(x)\n",
    "  case ConstDecl(x, e1, e2) => freeVars(e1) | (freeVars(e2) - x)\n",
    "  case N(_) | B(_) => Set.empty\n",
    "  case Unary(_, e1) => freeVars(e1)\n",
    "  case Binary(_, e1, e2) => freeVars(e1) | freeVars(e2)\n",
    "  case If(e1, e2, e3) => freeVars(e1) | freeVars(e2) | freeVars(e3)\n",
    "  case Fun(x, (y, _), _, e1) => freeVars(e1) - x - y\n",
    "  case Call(e1, e2) => freeVars(e1) | freeVars(e2)\n",
    "}\n",
    "\n",
    "def isClosed(e: Expr): Boolean = freeVars(e).isEmpty"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51fc43c3-617d-4e9b-9b52-144ff63d77c7",
   "metadata": {},
   "source": [
    "### Static Type Checking\n",
    "\n",
    "The typing judgment $\\Gamma \\vdash e : \\tau$ says, “In typing\n",
    "environment $\\Gamma$, expression $e$ has type $\\tau$” where the typing\n",
    "environment $\\Gamma\\mathrel{::=}\\cdot\\mid\\Gamma, x : \\tau$ is a finite\n",
    "map from variables to types, assigning types to the free variables of\n",
    "$e$. We give the expected typing rules that we have seen before,\n",
    "restricted to this simpler language:\n",
    "\n",
    "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n",
    "\n",
    "$\\inferrule[TypeVar]{\n",
    "}{\n",
    "  \\Gamma \\vdash x : \\Gamma(x)\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeConstDecl]{\n",
    "  \\Gamma \\vdash e_1 : \\tau_1\n",
    "  \\and\n",
    "  \\Gamma, x : \\tau_1 \\vdash e_2 : \\tau_2\n",
    "}{\n",
    "  \\Gamma \\vdash \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeNumber]{\n",
    "}{\n",
    "  \\Gamma \\vdash n : \\texttt{number}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeNeg]{\n",
    "  \\Gamma \\vdash e_1 : \\texttt{number}\n",
    "}{\n",
    "  \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\texttt{number}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeArith]{\n",
    "  \\Gamma \\vdash e_1 : \\texttt{number}\n",
    "  \\and\n",
    "  \\Gamma \\vdash e_2 : \\texttt{number}\n",
    "  \\and\n",
    "  \\mathit{bop}\\in \\left\\{  \\texttt{+}, \\texttt{*} \\right\\}\n",
    "}{\n",
    "  \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{number}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeBool]{\n",
    "}{\n",
    "  \\Gamma \\vdash b : \\texttt{bool}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeEq]{\n",
    "  \\Gamma \\vdash e_1 : \\tau\n",
    "  \\and\n",
    "  \\Gamma \\vdash e_2 : \\tau\n",
    "}{\n",
    "  \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 : \\texttt{bool}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeIf]{\n",
    "  \\Gamma \\vdash e_1 : \\texttt{bool}\n",
    "  \\and\n",
    "  \\Gamma \\vdash e_2 : \\tau\n",
    "  \\and\n",
    "  \\Gamma \\vdash e_3 : \\tau\n",
    "}{\n",
    "  \\Gamma \\vdash e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 : \\tau\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeFunctionRec]{\n",
    "  \\Gamma, x :  \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' , y : \\tau \\vdash e' : \\tau'\n",
    "}{\n",
    "  \\Gamma \\vdash  x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e'  :  \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeCall]{\n",
    "  \\Gamma \\vdash e_1 :  \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n",
    "  \\and\n",
    "  \\Gamma \\vdash e_2 :  \\tau\n",
    "}{\n",
    "  \\Gamma \\vdash e_1\\texttt{(}e_2\\texttt{)} : \\tau'\n",
    "}$\n",
    "\n",
    "Figure 2: Typing of TypeScripty with recursive functions and limited\n",
    "arithmetic-logical expressions.\n",
    "\n",
    "## Error Effects\n",
    "\n",
    "As we have seen, the most direct way to implement a type checker\n",
    "following the typing judgment $\\Gamma \\vdash e : \\tau$ is a function\n",
    "`hastype: (Map[String, Typ], Expr) => Typ` that takes an typing\n",
    "environment $\\Gamma$ represented by a `Map[String, Typ]` and an\n",
    "expression $e$ represented by a `Expr` and returns a type $\\tau$\n",
    "represented by a `Typ`:\n",
    "\n",
    "``` scala\n",
    "def hastype(tenv: Map[String, Typ], e: Expr): Typ = ???\n",
    "```\n",
    "\n",
    "However, with this function signature for `hastype`, we necessarily have\n",
    "to throw an exception or crash to indicate that an expression $e$ is\n",
    "ill-typed. An expression is ill-typed when there are no rules that allow\n",
    "us to derive a judgment $\\Gamma \\vdash e : \\tau$ for any $\\tau$ and\n",
    "$\\Gamma$.\n",
    "\n",
    "In this exercise, we implement a version of `hastype` that makes\n",
    "explicit the possibility of a type error.\n",
    "\n",
    "### Type-Error Result\n",
    "\n",
    "We first extend our typing judgment form $\\Gamma \\vdash e : r$ where a\n",
    "type-checker result $r$ is either a type $\\tau$ or a type-error result\n",
    "$\\mathit{typerr}$:\n",
    "\n",
    "<span class=\"text\">type-checker result</span>\n",
    "$\\quad  r  \\mathrel{::=}  \\mathit{typerr}  \\mid  \\tau$\n",
    "\n",
    "<span class=\"text\">type-error result</span>\n",
    "$\\quad  \\mathit{typerr}  \\mathrel{::=}  \\mathop{\\mathsf{typerr}}(e : \\tau)$\n",
    "\n",
    "This extended judgment form makes explicit when an expression is\n",
    "ill-typed. A type-error result\n",
    "\n",
    "$$\n",
    "\\mathop{\\mathsf{typerr}}(e : \\tau)\n",
    "$$\n",
    "\n",
    "includes an expression $e$ with its inferred type $\\tau$ but is used in\n",
    "a context another type is expected. We can consider such a type-error\n",
    "result being used to give a descriptive error message to the programmer.\n",
    "\n",
    "We now give some rules that introduce type-error results and propagates\n",
    "them:\n",
    "\n",
    "$\\fbox{$\\Gamma \\vdash e : r$}$\n",
    "\n",
    "$\\inferrule[TypeErrorNeg]{\n",
    "  \\Gamma \\vdash e_1 : \\tau_1\n",
    "  \\and\n",
    "  \\tau_1 \\neq \\texttt{number}\n",
    "}{\n",
    "  \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 :  \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1) \n",
    "}$\n",
    "\n",
    "$\\inferrule[PropagateNeg]{\n",
    "  \\Gamma \\vdash e_1 :  \\mathit{typerr}\n",
    "}{\n",
    "  \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 :  \\mathit{typerr}\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeErrorEq]{\n",
    "  \\Gamma \\vdash e_1 : \\tau_1\n",
    "  \\and\n",
    "  \\Gamma \\vdash e_2 : \\tau_2\n",
    "  \\and\n",
    "  \\tau_1 \\neq \\tau_2\n",
    "}{\n",
    "  \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 :  \\mathop{\\mathsf{typerr}}(e_2 : \\tau_2) \n",
    "}$\n",
    "\n",
    "$\\inferrule[PropagateEq1]{\n",
    "  \\Gamma \\vdash e_1 :  \\mathit{typerr}\n",
    "}{\n",
    "  \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 :  \\mathit{typerr}\n",
    "}$\n",
    "\n",
    "$\\inferrule[PropagateEq2]{\n",
    "  \\Gamma \\vdash e_2 :  \\mathit{typerr}\n",
    "}{\n",
    "  \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 :  \\mathit{typerr}\n",
    "}$\n",
    "\n",
    "Observe that the $\\TirName{TypeErrorEq}$ blames $e_2$: it infers the\n",
    "type $\\tau_1$ for $e_1$ and then expects that $e_2$ has type $\\tau_1$.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 1 (4 points)**</span> Define the\n",
    "$\\TirName{TypeErrorNot}$ rule that introduces a type-error result when\n",
    "the boolean negation expression $\\mathop{\\texttt{!}} e_1$ is ill-typed:\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2d9795c-8c11-4fb7-9c86-9a55c1ccd663",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "cd79e4bdf75b953b4f599263415f45a5",
     "grade": true,
     "grade_id": "hastype-typeerror-not",
     "locked": false,
     "points": 4,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "If the type of `e1` is not a boolean, a type error should be raised. The $\\TirName{TypeErrorNot}$ rule can be implemented as such:\n",
    "\n",
    "$\\inferrule[TypeErrorNot]{\n",
    "    \\Gamma \\vdash e_1 : \\tau_1 \\and \\tau_1 \\neq \\texttt{boolean}\n",
    "}{\n",
    "    \\Gamma \\vdash \\mathop{\\texttt{!}} e_1 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1)\n",
    "}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c636cad7-6a99-4a6d-b5eb-a95056b49ec1",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: Use $\\TirName{TypeErrorNeg}$ as a model.\n",
    "-   You may give the rule in LaTeX math or as plain text (ascii art)\n",
    "    approximating the math rendering. For example,\n",
    "\n",
    "<!-- -->\n",
    "\n",
    "    TypeErrorNeg\n",
    "    Gamma |- e1 : tau1  tau1 != number\n",
    "    ------------------------------------------\n",
    "    Gamma |- -e1 : typerr(e1 : tau1 != number)\n",
    "\n",
    "The LaTeX code for the rendered $\\TirName{TypeErrorNeg}$ rule above is\n",
    "as follows:\n",
    "\n",
    "``` tex\n",
    "\\inferrule[TypeErrorNeg]{\n",
    "  \\Gamma \\vdash e_1 : \\tau_1\n",
    "  \\and\n",
    "  \\tau_1 \\neq \\texttt{number}\n",
    "}{\n",
    "  \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 :  \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1 \\neq \\texttt{number})\n",
    "}\n",
    "```\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 2 (8 points)**</span> Define\n",
    "**two** $\\TirName{TypeErrorIf}$ rules that introduces a type-error\n",
    "result when the if-then-else expression\n",
    "$e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3$ is ill-typed:\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1442119d-5f94-46a2-a5b5-98d138cf3ee4",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c65bd4e71cb952a36967e8ce3c7846d8",
     "grade": true,
     "grade_id": "hastype-typeerror-if",
     "locked": false,
     "points": 8,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The two types of errors that need to be fielded are if condition `e1` is nota boolean value, or if branches `e2` and `e2` do not have the same type. These rules can be implemented as such:\n",
    "\n",
    "$\\inferrule[TypeErrorIf1]{\n",
    "    \\Gamma \\vdash e_1 : \\tau_1 \\and \\tau_1 \\neq \\texttt{boolean}\n",
    "}{\n",
    "    \\Gamma \\vdash e_1 \\mathop{\\texttt{?}} e_2 : e_3 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1)\n",
    "}$\n",
    "\n",
    "$\\inferrule[TypeErrorIf2]{\n",
    "    \\Gamma \\vdash e_1 : \\texttt{boolean}\n",
    "    \\and \\Gamma \\vdash e_2 : \\tau_2\n",
    "    \\and \\Gamma \\vdash e_3 : \\tau_3\n",
    "    \\and \\tau_2 \\neq \\tau3\n",
    "}{\n",
    "    \\Gamma \\vdash e_1 \\mathop{\\texttt{?}} e_2 : e_3 \\mathop{\\mathsf{typerr}}(e_2 : \\tau_2, e_3 : \\tau_3)\n",
    "}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8fa5d8f-f8e0-494f-a2c5-424f8676a458",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: Use $\\TirName{TypeErrorNeg}$ and $\\TirName{TypeErrorEq}$ as a\n",
    "    model for the two rules, respectively.\n",
    "\n",
    "### Implementation\n",
    "\n",
    "We represent a type-error result $r$ as an\n",
    "`Either[StaticTypeError, Typ]`.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 3 (26 points)**</span> Complete\n",
    "the following implementation of\n",
    "\n",
    "`hastype: (Map[String, Typ], Expr) => Either[StaticTypeError, Typ]`\n",
    "\n",
    "corresponding to the judgment form $\\Gamma \\vdash e : r$.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "14b2c8ce",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d6ced05c47f1d78d16a5489ab77967f8",
     "grade": false,
     "grade_id": "hastype-typeerror-implementation",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mclass\u001b[39m \u001b[36mStaticTypeError\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mhastype\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36minferType\u001b[39m"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "case class StaticTypeError(tbad: Typ, esub: Expr, e: Expr) {\n",
    "  override def toString = s\"StaticTypeError: invalid type $tbad for sub-expression $esub in $e\"\n",
    "}\n",
    "\n",
    "def hastype(tenv: Map[String, Typ], e: Expr): Either[StaticTypeError, Typ] = {\n",
    "\n",
    "  def err[T](esub: Expr, tgot: Typ): Either[StaticTypeError, T] =\n",
    "    Left(StaticTypeError(tgot, esub, e))\n",
    "\n",
    "  def typecheck(tenv: Map[String, Typ], e: Expr, tshould: Typ): Either[StaticTypeError, Unit] =\n",
    "    hastype(tenv, e) flatMap { tgot =>\n",
    "      if (tgot == tshould)\n",
    "        Right(())\n",
    "      else err(e, tgot)\n",
    "    }\n",
    "\n",
    "  e match {\n",
    "    case Var(x) => Right(tenv(x))\n",
    "    case ConstDecl(x, e1, e2) =>\n",
    "      hastype(tenv, e1) flatMap { t1 =>\n",
    "          hastype(tenv + (x -> t1), e2)\n",
    "      }\n",
    "    case N(_) => Right(TNumber)\n",
    "    case B(_) => Right(TBool)\n",
    "    case Unary(Neg, e1) => typecheck(tenv, e1, TNumber) map { _ => TNumber }\n",
    "    case Unary(Not, e1) => typecheck(tenv, e1, TBool) map { _ => TBool }\n",
    "    case Binary(Plus|Times, e1, e2) =>\n",
    "      typecheck(tenv, e1, TNumber) flatMap { _ =>\n",
    "          typecheck(tenv, e2, TNumber) map { _ => TNumber }\n",
    "      }\n",
    "    case Binary(Eq, e1, e2) =>\n",
    "      hastype(tenv, e1) flatMap { t1 =>\n",
    "        hastype(tenv, e2) flatMap { t2 =>\n",
    "          if (t1 == t2) Right(TBool) else err(e2, t2)\n",
    "        }\n",
    "      }\n",
    "    case If(e1, e2, e3) =>\n",
    "      typecheck(tenv, e1, TBool) flatMap { _ =>\n",
    "          hastype(tenv, e2) flatMap { t2 =>\n",
    "              hastype(tenv, e3) flatMap { t3 =>\n",
    "                  if (t2 == t3) Right(t2) else err(e3, t3)\n",
    "              }\n",
    "          }\n",
    "      }\n",
    "    case Fun(x, yt @ (y, t), tret, e1) =>\n",
    "      val funcType = TFun(yt, tret)\n",
    "      hastype(tenv + (x -> funcType) + (y -> t), e1) flatMap { tbody =>\n",
    "          if (tbody == tret) Right(funcType)\n",
    "          else err(e1, tbody)\n",
    "      }\n",
    "    case Call(e1, e2) =>\n",
    "      hastype(tenv, e1) flatMap {\n",
    "          case TFun((_, targ), tret) => typecheck(tenv, e2, targ) map { _ => tret }\n",
    "          case tgot => err(e1, tgot)\n",
    "      }\n",
    "  }\n",
    "}\n",
    "\n",
    "def inferType(e: Expr): Either[StaticTypeError, Typ] = {\n",
    "  require(isClosed(e), s\"$e should be closed\")\n",
    "  hastype(Map.empty, e)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2e96f44-91d8-41ef-ad03-1787239e8f56",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   The `err` helper function is simply a shortcut to construct\n",
    "    `StaticTypeError` with the input expression `e`.\n",
    "-   The `typecheck` helper function implements a common functionality\n",
    "    where we want to call `hastype` recursively with a sub-expression to\n",
    "    infer a type `tgot` and check it is equal to an expected type\n",
    "    `tshould`. If `tgot != tshould`, we return an `err`; otherwise, we\n",
    "    return success.\n",
    "-   Hint: Start by implementing the $\\TirName{Type}$ rules from\n",
    "    <a href=\"#fig-typescripty-minrecfun-typing\"\n",
    "    class=\"quarto-xref\">Figure 2</a> without worrying about type errors.\n",
    "    Then, add $\\TirName{TypeError}$ and $\\TirName{Propagate}$ cases.\n",
    "-   Note that not all the $\\TirName{TypeError}$ and\n",
    "    $\\TirName{Propagate}$ rules are given, but they follow the patterns\n",
    "    given above. If you get stuck to implement the code for\n",
    "    $\\TirName{TypeError}$ for a particular construct, try writing out\n",
    "    the rule.\n",
    "-   It is fine to initially pattern match on\n",
    "    `Either[StaticTypeError, Expr]` values that result from calls to\n",
    "    `hastype` and `typecheck` (i.e., for `Left` and `Right` values).\n",
    "    However, challenge yourself to replace them with `map` or `flatMap`\n",
    "    calls to minimize your typing and opportunities for bugs to creep\n",
    "    in. It is possible to replace all pattern matches for `Left` and\n",
    "    `Right` values with calls to `map` and `flatMap` calls.\n",
    "-   Use the given cases (e.g., $\\TirName{TypeNeg}$,\n",
    "    $\\TirName{TypeErrorNeg}$, $\\TirName{PropagateNeg}$) as a model.\n",
    "    Identify how $\\TirName{TypeNeg}$, $\\TirName{TypeErrorNeg}$, and\n",
    "    $\\TirName{PropagateNeg}$ manifests in the code.\n",
    "-   For accelerated students, you can make the code even more compact\n",
    "    (and arguably more readable) by replacing `flatMap` and `map` calls\n",
    "    with `for`-`yield` expressions. Note that not all cases can be\n",
    "    implemented with `for`-`yield` expressions.\n",
    "\n",
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "fd5d3dfc",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "410d74ebf1a362f169386234cef5a82a",
     "grade": true,
     "grade_id": "hastype-constdecl-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd41$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/ConstDecl\u001b[0m\n",
      "\u001b[32m- should TypeConstDecl\u001b[0m\n",
      "\u001b[32m- should PropagateConstDecl1\u001b[0m\n",
      "\u001b[32m- should PropagateConstDecl2\u001b[0m\n",
      "\u001b[36mRun completed in 6 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Binary(Plus, N(1), N(2)) \n",
    "  val e2 = Binary(Times, Var(\"a\"), N(3))\n",
    "\n",
    "  val e3 = ConstDecl(\"a\", e1, e2)\n",
    "  \"hastype/ConstDecl\" should \"TypeConstDecl\" in {\n",
    "    assertResult(Right(TNumber)) {inferType(e1) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateConstDecl1\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(ConstDecl(\"a\", bade, N(1))) }\n",
    "  }\n",
    "\n",
    "  it should \"PropagateConstDecl2\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(ConstDecl(\"a\", N(1), bade)) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "3fedb1ca",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2ccc667ac624a8997f777e6df3d695ca",
     "grade": true,
     "grade_id": "hastype-not-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd42$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/Unary/Not\u001b[0m\n",
      "\u001b[32m- should TypeNot\u001b[0m\n",
      "\u001b[32m- should TypeErrorNot\u001b[0m\n",
      "\u001b[32m- should PropagateNot\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Unary(Not, B(true))\n",
    "  \"hastype/Unary/Not\" should \"TypeNot\" in {\n",
    "    assertResult(Right(TBool)) {inferType(e1) }\n",
    "  }\n",
    "\n",
    "  val e2 = Unary(Not, N(1))\n",
    "  it should \"TypeErrorNot\" in {\n",
    "    assertResult(Left(StaticTypeError(TNumber, N(1), e2))) {inferType(e2) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateNot\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Unary(Not, bade)) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "cfa09d18",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "62cfbcc928e347c29f53bbd95f940e3c",
     "grade": true,
     "grade_id": "hastype-plus-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd43$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/Binary/Plus|Times\u001b[0m\n",
      "\u001b[32m- should TypeArith\u001b[0m\n",
      "\u001b[32m- should TypeErrorArith\u001b[0m\n",
      "\u001b[32m- should PropagateArith\u001b[0m\n",
      "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Binary(Plus, N(1), N(2))\n",
    "  \"hastype/Binary/Plus|Times\" should \"TypeArith\" in {\n",
    "    assertResult(Right(TNumber)) { inferType( Binary(Times, e1, N(2)) ) }\n",
    "  }\n",
    "\n",
    "  val e2 = Binary(Plus, B(true), e1)\n",
    "  it should \"TypeErrorArith\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, B(true), e2))) { inferType(e2) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateArith\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Binary(Plus, bade, N(3))) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "5fcb7d22",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e0cd4dc1c6b8b6a646f4c974996f2dcf",
     "grade": true,
     "grade_id": "hastype-if-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
      "\u001b[32mcmd44$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/If\u001b[0m\n",
      "\u001b[32m- should TypeIf\u001b[0m\n",
      "\u001b[32m- should TypeErrorIfGuard\u001b[0m\n",
      "\u001b[32m- should TypeErrorIfBody\u001b[0m\n",
      "\u001b[32m- should PropagateIf\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Binary(Plus, N(1), N(2))\n",
    "  \"hastype/If\" should \"TypeIf\" in {\n",
    "    assertResult(Right(TNumber)) { inferType( If(B(true), e1, N(3)) ) }\n",
    "  }\n",
    "\n",
    "  val e2 = If(N(1), e1, e1)\n",
    "  it should \"TypeErrorIfGuard\" in {\n",
    "    assertResult(Left(StaticTypeError(TNumber, N(1), e2))) { inferType(e2) }\n",
    "  }\n",
    "\n",
    "  val e3 = If(B(false), B(true), N(1))\n",
    "  it should \"TypeErrorIfBody\" in {\n",
    "    assertResult(Left(StaticTypeError(TNumber, N(1), e3))) { inferType(e3) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateIf\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(If(B(true), bade, N(3))) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "449ea45d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "40a19d9980eb789b6eca1d18553ef385",
     "grade": true,
     "grade_id": "hastype-fun-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n",
      "\u001b[32mcmd45$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/Fun\u001b[0m\n",
      "\u001b[32m- should TypeFun\u001b[0m\n",
      "\u001b[32m- should PropagateFun\u001b[0m\n",
      "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 2\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Binary(Times, Var(\"i\"), N(3))\n",
    "  def fun(e: Expr) = Fun(\"f\", (\"i\", TNumber), TNumber, e)\n",
    "  \"hastype/Fun\" should \"TypeFun\" in {\n",
    "    assertResult(Right(TFun((\"i\", TNumber), TNumber))) { inferType(fun(e1)) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateFun\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(fun(bade)) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "73508956",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ec856ba1df491639a9800ab24b3a7a23",
     "grade": true,
     "grade_id": "hastype-call-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd46$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype/Call\u001b[0m\n",
      "\u001b[32m- should TypeCall\u001b[0m\n",
      "\u001b[32m- should TypeErrorCall\u001b[0m\n",
      "\u001b[32m- should PropagateCall2\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val e1 = Binary(Times, Var(\"i\"), Call(Var(\"f\"), N(3)))\n",
    "  def fun(e: Expr) = Fun(\"f\", (\"i\", TNumber), TNumber, e)\n",
    "  val e2 = \n",
    "  \"hastype/Call\" should \"TypeCall\" in {\n",
    "    assertResult(Right(TNumber)) { inferType(Call(fun(e1), N(10))) }\n",
    "  }\n",
    "\n",
    "  val e3 = Call(B(true), N(1))\n",
    "  it should \"TypeErrorCall\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, B(true), e3))) { inferType(e3) }\n",
    "  }\n",
    "\n",
    "  val badesub = B(true)\n",
    "  val bade = Binary(Plus, N(1), badesub)\n",
    "  it should \"PropagateCall2\" in {\n",
    "    assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Call(fun(e1),bade)) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "c170737a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f7e3385fd933df313e764a9a55bd64c6",
     "grade": true,
     "grade_id": "hastype-all-tester",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd47$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mhastype\u001b[0m\n",
      "\u001b[32m- should type check factorial\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (2 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val factorial = Fun(\"fact\", (\"n\", TNumber), TNumber,\n",
    "    If(Binary(Eq, Var(\"n\"), N(1)),\n",
    "    N(1),\n",
    "    Binary(Times, Var(\"n\"), Call(Var(\"fact\"), Binary(Plus, Var(\"n\"), N(-1)))))\n",
    "  )\n",
    "  \"hastype\" should \"type check factorial\" in {\n",
    "    assertResult(Right(TNumber)) { inferType(Call(factorial, N(4))) }\n",
    "  }\n",
    "}, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4896a74-23f0-4392-9488-da88ab020973",
   "metadata": {},
   "source": [
    "## Mutation Effects\n",
    "\n",
    "### Defining Generic `DoWith` Methods\n",
    "\n",
    "Recall the idea of encapulating a state transforming function\n",
    "`S => (S, A)` as a collection-like data type\n",
    "(**?@sec-encapsulating-mutation-effects**), which we call a\n",
    "`DoWith[S, A]`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "6e523d01",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mclass\u001b[39m \u001b[36mDoWith\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mDoWith\u001b[39m\n",
       "\u001b[32mimport \u001b[39m\u001b[36mDoWith._\u001b[39m"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed class DoWith[S, A] private (doer: S => (S, A)) {\n",
    "  def map[B](f: A => B): DoWith[S, B] = new DoWith[S, B]({\n",
    "    (s: S) => {\n",
    "      val (s_, a) = doer(s)\n",
    "      (s_, f(a))\n",
    "    }\n",
    "  })\n",
    "\n",
    "  def flatMap[B](f: A => DoWith[S, B]): DoWith[S, B] = new DoWith[S, B]({\n",
    "    (s: S) => {\n",
    "      val (s_, a) = doer(s)\n",
    "      f(a)(s_)\n",
    "    }\n",
    "  })\n",
    "\n",
    "  def apply(s: S): (S, A) = doer(s)\n",
    "}\n",
    "\n",
    "object DoWith {\n",
    "  def doget[S]: DoWith[S, S] = new DoWith[S, S]({ s => (s, s) })\n",
    "  def doput[S](s: S): DoWith[S, Unit] = new DoWith[S, Unit]({ _ => (s, ()) })\n",
    "}\n",
    "\n",
    "import DoWith._"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db0a5acb-4f1a-47e9-86d4-b088e97537e5",
   "metadata": {},
   "source": [
    "Consider a `DoWith[S,A]` as a “collection” holding an `A` somewhat like\n",
    "`List[A]` or `Option[A]`. While `List[A]` encapsulates a sequence of\n",
    "elements of type `A` elements and `Option[A]` encapsulates an optional\n",
    "`A`, a `DoWith[S, A]` encapsulates a *computation* that results in an\n",
    "`A`, using an input-output state `S` (i.e., a `S => (S, A)` function).\n",
    "It is collection-like because it also has `map` and `flatMap` methods to\n",
    "transform that computation.\n",
    "\n",
    "We also define two functions for a client to create a `DoWith[S, A]`\n",
    "encapsulating particular `S => (S, A)`{.scala functions}:\n",
    "\n",
    "-   The `doget[S]` method constructs a `DoWith[S, S]` that makes the\n",
    "    “current” state the result (i.e., `s => (s, s)`). Intuitively, it\n",
    "    “gets” the state.\n",
    "-   The `doput[S](s: S)` method constructs a `DoWith[S, Unit]` that\n",
    "    makes the given state `s` the “current” state (i.e.,\n",
    "    `_ => (s, ())`). Intuitively, it “puts” `s` into the state.\n",
    "\n",
    "We require the client to create `DoWith[S, A]` values using only the\n",
    "`doget` and `doput` constructors.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 4 (4 points)**</span> Read the\n",
    "implementations `map[B]` and `flatMap[B]` methods of `DoWith[S, A]`\n",
    "above. Explain how they transform the encapsulated `doer: S => (S, A)`\n",
    "function. Compare and contrast them—what do they do that is same, and\n",
    "what is the key difference between them?\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c74beb30-b33b-4209-9229-a75606fed770",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "37061be7f5cd361ab5e98f4a5ee7970b",
     "grade": true,
     "grade_id": "map-flatMap-diff",
     "locked": false,
     "points": 4,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "### `map[B]` Method\n",
    "This method transforms the result `A` into another result `B`, while leaving the state of `S` unchanged. In the context of the encapsulated function `doer: S => (S, A)`, `map` modifies the second element of the tuple produced by `doer`, applying `f` toget `B`.\n",
    "\n",
    "### `flatMap[B]` Method\n",
    "This method chains a new `DoWith[S, B]` computation that depends on the result of the current one, which potentially alters the state of `S` again. In the context of the encapsulated function `doer: S => (S, A)`, the first computation of `flatMap` produces a new state and result `(S', A)`. Then, based on the value of `A`, a new computation `f(A)` is performed, which may further transform the state to `S''` and the resulting value in `B`.\n",
    "\n",
    "### Comparison\n",
    "Both `map` and `flatMap` methods work with computations of type `S => (S, A)` and return new computations that transform the result. These methods differ in mutability — `map` only transforms the resulting value while keeping the state intact, whereas `flatMap` can transform both the result and the state through chaining additional computations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91c410d7-d065-4456-aaf0-c23faf60d85c",
   "metadata": {},
   "source": [
    "As a `DoWith[S, A]` encapsulates any function of type `S => (S, A)`,\n",
    "there are other commonly needed functions of this type. We implement\n",
    "methods for constructing `DoWith[S, A]` encapsulating two more\n",
    "commonly-needed computations in terms of `doget` and `doput`.\n",
    "\n",
    "-   The `doreturn[S, A](a: A)` method constructs a `DoWith[S, A]` that\n",
    "    leaves the “current” state as-is and returns the given result `a`\n",
    "    (i.e., `s => (s, a)`). It technically does not need to be given in\n",
    "    the library, as it can be defined in terms of `doget` and `map`.\n",
    "-   The `domodify[S](f: S => S)` method constructs a `DoWith[S, Unit]`\n",
    "    that “modifies” the state using the given function `f: S => S`\n",
    "    (i.e., `s => (f(s), ())`). It technically does not need to be given\n",
    "    in the library, as it can be defined in terms of `doget`, `doput`,\n",
    "    and `flatMap`.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 5 (4 points)**</span> Implement\n",
    "`doreturn[S, A](a: A)` that creates a `DoWith[S, A]` that encapsulates\n",
    "the computation `(s: S) => (s, a)` using `doget`, `doput`, `map`, and/or\n",
    "`flatMap`.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "4a4287fc",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "97598cf8176538e585af2be753ebefc8",
     "grade": false,
     "grade_id": "doreturn-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdoreturn\u001b[39m"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def doreturn[S, A](a: A): DoWith[S, A] = doget[S] flatMap { s => doput(s) map { _ => a } }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f8163f1-cf87-4beb-8dbd-324b849e1156",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "a1c918c0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "be56763277879729950e0129c6ef5703",
     "grade": true,
     "grade_id": "doreturn-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd50$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mdoreturn\u001b[0m\n",
      "\u001b[32m- should Test1\u001b[0m\n",
      "\u001b[32m- should Test2\u001b[0m\n",
      "\u001b[32m- should Test3\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  \"doreturn\" should \"Test1\" in { assertResult( (0,1) ) { doreturn(1)(0) }}\n",
    "  it should \"Test2\" in { assertResult( (2,\"test\") ) { doreturn(\"test\")(2) }}\n",
    "  it should \"Test3\" in { assertResult( (2,List(1,2,3)) ) { doreturn(List(1,2,3))(2) }}\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b168529d-126e-4a31-b290-59fc2e2b7a87",
   "metadata": {},
   "source": [
    "<span class=\"theorem-title\">**Exercise 6 (4 points)**</span> Implement\n",
    "`domodify[S](f: S => S)` that creates a `DoWith[S, Unit]` that\n",
    "encapsulates the computation `(s: S) => (f(s), ())` using `doget`,\n",
    "`doput`, `map`, and/or `flatMap`.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "fa1dec1a",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "fe4c1a7e4e4f25883a7446451c07f5b3",
     "grade": false,
     "grade_id": "domodify-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdomodify\u001b[39m"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def domodify[S](f: S => S): DoWith[S, Unit] = doget[S] flatMap { s => doput(f(s)) }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa1a5947-0c35-44cc-865c-af026c9bc03e",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: To define `doreturn` and `domodify`, it might help first to do\n",
    "    type-directed programming where you ignore what a `DoWith[S, A]`\n",
    "    actually is and think of it as `Either[S, A]` or abstractly as\n",
    "    `M[S, A]` for an unknown type constructor `M`. There only limited\n",
    "    things you can do by composing `doget`, `doput`, `map`, and\n",
    "    `flatMap`.\n",
    "\n",
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "93fe1d63",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0c845d5a21bb4705b132ee18cb9b1d1e",
     "grade": true,
     "grade_id": "domodify-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mdomodify\u001b[0m\n",
      "\u001b[32m- should Test1\u001b[0m\n",
      "\u001b[32m- should Test2\u001b[0m\n",
      "\u001b[32m- should Test3\u001b[0m\n",
      "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  \"domodify\" should \"Test1\" in { assertResult( (6,()) ) { domodify({a:Int => 2*a})(3) }}\n",
    "  it should \"Test2\" in { assertResult( (\"testtest\",()) ) { domodify({x:String => x+x})(\"test\") }}\n",
    "  it should \"Test3\" in { assertResult( (List(1,2,3,4),()) ) { domodify({l:List[Int] => l:+4})(List(1,2,3))}}\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6bf317b-a3b1-4aa5-8e04-aede510edc39",
   "metadata": {},
   "source": [
    "### Renaming Bound Variables\n",
    "\n",
    "Recall that with static scoping, we see expressions as being equivalent\n",
    "up to the renaming of bound variables\n",
    "(**?@sec-renaming-bound-variables**). For example, we see the following\n",
    "two expressions as being equivalent for the purposes of the language\n",
    "implementation:\n",
    "\n",
    "``` js\n",
    "const four = (2 + 2); (four + four)\n",
    "```\n",
    "\n",
    "``` js\n",
    "const x = (2 + 2); (x + x)\n",
    "```\n",
    "\n",
    "even though the concrete syntax for the human user is different in their\n",
    "choice of variable names.\n",
    "\n",
    "While being able to choose variable names that shadows another variable\n",
    "is important for the human user, we have seen that clashing variable\n",
    "names adds complexity to the language implementation. For example,\n",
    "mishandling of clashing variable names results in accidental dynamic\n",
    "scoping (**?@sec-dynamic-scoping**) and substitution has to account for\n",
    "variable shadowing (**?@sec-substitution**).\n",
    "\n",
    "Observing that renaming bound variables preserves meaning for the\n",
    "language implementation, one approach for simplifying the handling of\n",
    "variable scope is to implement a *lowering* pass that renames bound\n",
    "variables in a consistent manner so that variable names are globally\n",
    "unique. For example, we could lower the following expression\n",
    "\n",
    "``` js\n",
    "const a = ((a) => a)(1) + ((a) => a)(2); a\n",
    "```\n",
    "\n",
    "by renaming bound variables to, for example,\n",
    "\n",
    "``` js\n",
    "const a_0 = ((a_1) => a_1)(1) + ((a_2) => a_2)(2); a_0\n",
    "```\n",
    "\n",
    "We will implement the above lowering pass in a few steps.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 7 (4 points)**</span> Write a\n",
    "function `freshVar(x: String)` that returns a function of type\n",
    "`Int => (Int, String)`, which takes a current index-state `i: Int` and\n",
    "returns the pair of the next index state `i + 1` and the string `x` with\n",
    "the index appended and separated by `\"_\"` (specifically,\n",
    "`s\"${x}_${i}\"`):\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "70c8ba22",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4db7c0a40e8bdb85a7c6c1c88b86f075",
     "grade": false,
     "grade_id": "freshVar-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfreshVar\u001b[39m"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def freshVar(x: String): Int => (Int, String) = i => (i + 1, x + \"_\" + i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c9387bd-f827-48f0-96b2-527fd727298a",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "1eec1ec4",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8dbbc418bc069f4bf5cd578668e84d8f",
     "grade": true,
     "grade_id": "freshVar-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd54$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mfreshVar\u001b[0m\n",
      "\u001b[32m- should satisfy the property\u001b[0m\n",
      "\u001b[36mRun completed in 6 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n",
    "  \"freshVar\" should \"satisfy the property\" in {\n",
    "    forAll (\"x\", \"i\") { (x: String, i: Int) =>\n",
    "      freshVar(x)(i) should be (i + 1, s\"${x}_${i}\")\n",
    "    }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3de0aa9c-fd52-4178-8b57-643729b4c1d8",
   "metadata": {},
   "source": [
    "Aside: Writing lots of tests is painful. In the above, we use an idea\n",
    "called *property-based testing* to make it less painful and more\n",
    "effective. A property-based testing library enables specifying a\n",
    "property on inputs like in the above for `x: String` and `i: Int`, and\n",
    "the library will choose lots of random inputs with which to check the\n",
    "property. Importantly, the library also enables the client to specify\n",
    "how to generate inputs (e.g., what range, what distribution), though we\n",
    "do not do anything special to control the input generation in the above.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 8 (4 points)**</span> Write a\n",
    "function `freshVarWith(x: String): DoWith[Int, String]` that behaves\n",
    "like `freshVar(x: String): Int => (Int, String)` in\n",
    "<a href=\"#exr-freshVar\" class=\"quarto-xref\">Exercise 7</a>.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "ebced2e2",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2b383203a1ca61a750129f4e907efaed",
     "grade": false,
     "grade_id": "freshVarWith-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfreshVarWith\u001b[39m"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def freshVarWith(x: String): DoWith[Int, String] =\n",
    "  doget[Int] flatMap { i => doput(i + 1) map { _ => x + \"_\" + i } }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75c2997d-0121-449f-a524-ecc078970ad9",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: Remember that `DoWith[Int, String]` encapsulates a function of\n",
    "    type `Int => (Int, String)`. Use `freshVar` as a guide to creating\n",
    "    the `DoWith[Int, String]` using `doget`, `doput`, `map`, and/or\n",
    "    `flatMap`.\n",
    "-   For accelerated students, you may try to use a `for`-`yield`\n",
    "    expression to replace your `map` and `flatMap` calls.\n",
    "\n",
    "A lowering pass is a transformation function from `Expr => Expr`. To\n",
    "rename bound variables in a consistent manner, we need an enviroment to\n",
    "remember what the name should be for a free variable use in the input\n",
    "`Expr`. Thus, we need to define a helper function\n",
    "`rename(env: Map[String, String], e: Expr)` that takes as input an\n",
    "`env: Map[String, String]` that maps original names to new names for the\n",
    "free variable uses in `e`.\n",
    "\n",
    "We also need a way to choose how to rename bound variables so that they\n",
    "are unique. The client of `rename` might want to rename variables\n",
    "uniquely in different ways (e.g., using an integer counter, using the\n",
    "original name with an integer counter). Thus, we add an additional\n",
    "callback parameter\n",
    "\n",
    "`fresh: String => DoWith[S, String]`\n",
    "\n",
    "for the client to specify how they want to specify the fresh name given\n",
    "the original name where they can choose a state type `S` to use through\n",
    "renaming.\n",
    "\n",
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "59e121cb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "95401071328374fd7d0acba7c0cc8be9",
     "grade": true,
     "grade_id": "freshVarWith-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd56$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mfreshVarWith\u001b[0m\n",
      "\u001b[32m- should satisfy the property\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n",
    "  \"freshVarWith\" should \"satisfy the property\" in {\n",
    "    forAll (\"x\", \"i\") { (x: String, i: Int) =>\n",
    "      freshVarWith(x)(i) should be (i + 1, s\"${x}_${i}\")\n",
    "    }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3bfb9f2-fe61-41cf-9e92-5f128b5b2e74",
   "metadata": {},
   "source": [
    "<span class=\"theorem-title\">**Exercise 9 (24 points)**</span> Implement\n",
    "a function `rename` that renames variable names in `e` consistently\n",
    "using the given callback to `fresh` to generate fresh names for bound\n",
    "variables and `env` to rename free variable uses.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "3ff17100",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ece6ee45347070a85242d7d9307fd598",
     "grade": false,
     "grade_id": "rename-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrename\u001b[39m"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def rename[S](env: Map[String, String], e: Expr)(fresh: String => DoWith[S, String]): DoWith[S, Expr] = {\n",
    "  def rename(env: Map[String, String], e: Expr): DoWith[S, Expr] = {\n",
    "    def r(e: Expr) = rename(env, e)\n",
    "    e match {\n",
    "      case N(_) => doreturn(e)\n",
    "      case B(_) => doreturn(e)\n",
    "\n",
    "      case Var(x) =>\n",
    "        env.get(x) match {\n",
    "            case Some(newName) => doreturn(Var(newName))\n",
    "            case None => doreturn(e)\n",
    "        }\n",
    "\n",
    "      case ConstDecl(x, e1, e2) =>\n",
    "        fresh(x) flatMap { x_ =>\n",
    "            r(e1) flatMap { e1Renamed =>\n",
    "                rename(env + (x -> x_), e2) map { e2Renamed =>\n",
    "                    ConstDecl(x_, e1Renamed, e2Renamed)\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "\n",
    "      case Unary(uop, e1) => r(e1) map { e1Renamed => Unary(uop, e1Renamed) }\n",
    "\n",
    "      case Binary(bop, e1, e2) =>\n",
    "        r(e1) flatMap { e1Renamed =>\n",
    "            r(e2) map { e2Renamed => Binary(bop, e1Renamed, e2Renamed) }\n",
    "        }\n",
    "\n",
    "      case If(e1, e2, e3) =>\n",
    "        r(e1) flatMap { e1Renamed =>\n",
    "            r(e2) flatMap { e2Renamed =>\n",
    "                r(e3) map { e3Renamed => If(e1Renamed, e2Renamed, e3Renamed) }\n",
    "            }\n",
    "        }\n",
    "\n",
    "      case Fun(x, (y, t), tret, e1) =>\n",
    "        fresh(x) flatMap { x_ =>\n",
    "            fresh(y) flatMap { y_ =>\n",
    "                rename(env ++ Seq(x -> x_, y -> y_), e1) map { e1Renamed =>\n",
    "                    Fun(x_, (y_, t), tret, e1Renamed)\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "\n",
    "      case Call(e1, e2) =>\n",
    "        r(e1) flatMap { e1 =>\n",
    "          r(e2) map { e2 => Call(e1, e2) }\n",
    "        }\n",
    "    }\n",
    "  }\n",
    "  rename(env, e)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1785b12-6117-46a6-b5c1-8d084599d74d",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: Use the given cases for `N` and `Call` as models. The only\n",
    "    methods for manipulating `DoWith` objects needed in this exercise\n",
    "    are `doreturn`, `map`, and `flatMap`.\n",
    "-   **Accelerated**: You may try to use `for`-`yield` expressions to\n",
    "    replace your `map` and `flatMap` calls.\n",
    "\n",
    "### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "008eecc0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9efbe8c21276cc5893170648e4fe920f",
     "grade": true,
     "grade_id": "rename-tester",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename\u001b[0m\n",
      "\u001b[32m- should rename in a DoWith\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    " \"rename\" should \"rename in a DoWith\" in {\n",
    "    val e1 = ConstDecl(\"a\", N(1), Var(\"a\"))\n",
    "    val e1p = ConstDecl(\"aa\", N(1), Var(\"aa\"))\n",
    "\n",
    "    assertResult( (1, e1p) ) {\n",
    "      rename(Map.empty, e1){ x => domodify[Int](n => n + 1) map { _ => x + x } }(0)\n",
    "    }\n",
    "  }\n",
    " }, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "eb86e401",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9f99fea0bf530561a08a1ac395976f96",
     "grade": true,
     "grade_id": "rename-b-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd59$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename/B\u001b[0m\n",
      "\u001b[32m- should RenameB\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n",
    "  def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n",
    "  def r(e: Expr) = renv(Map.empty, e)\n",
    "\n",
    "  \"rename/B\" should \"RenameB\" in {\n",
    "    assertResult( (0, B(true)) ) { r(B(true)) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "fb51b0f2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a858edae6e7b668554c2450a11eb0c8e",
     "grade": true,
     "grade_id": "rename-var-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd60$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename/Var\u001b[0m\n",
      "\u001b[32m- should RenameVar\u001b[0m\n",
      "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n",
    "  def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n",
    "  def r(e: Expr) = renv(Map.empty, e)\n",
    "\n",
    "  \"rename/Var\" should \"RenameVar\" in {\n",
    "    assertResult( (0, Var(\"y\")) ) { renv(Map(\"x\" -> \"y\"), Var(\"x\")) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "0f91cc33",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4ee6c2e809e0b3da63081628038a320e",
     "grade": true,
     "grade_id": "rename-constdecl-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd61$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename/ConstDecl\u001b[0m\n",
      "\u001b[32m- should RenameConstDecl\u001b[0m\n",
      "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n",
    "  def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n",
    "  def r(e: Expr) = renv(Map.empty, e)\n",
    "\n",
    "  def e(x: String) = ConstDecl(x, N(1), Var(x))\n",
    "  \"rename/ConstDecl\" should \"RenameConstDecl\" in {\n",
    "    assertResult( (1, e(\"x0\")) ) { r(e(\"foo\")) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "3043ad33",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8bf04f09f2e6ad7c3cf1b95420f2e42e",
     "grade": true,
     "grade_id": "rename-fun-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
      "\u001b[32mcmd62$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename/Fun\u001b[0m\n",
      "\u001b[32m- should RenameFun\u001b[0m\n",
      "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n",
    "  def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n",
    "  def r(e: Expr) = renv(Map.empty, e)\n",
    "\n",
    "  def e(f: String, y: String) = Fun(f, (y, TNumber), TNumber, Call(Var(\"f\"), Var(\"y\")))\n",
    "  \"rename/Fun\" should \"RenameFun\" in {\n",
    "    assertResult( (2, e(\"x0\", \"x1\")) ) { r(e(\"foo\", \"bar\")) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "13177ece",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4e45cf96c86a87a489df4d6a67af2121",
     "grade": true,
     "grade_id": "rename-factorial-tester",
     "locked": true,
     "points": 4,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n",
      "\u001b[32mcmd63$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mrename\u001b[0m\n",
      "\u001b[32m- should rename bound variables consistently for factorial\u001b[0m\n",
      "\u001b[32m- should rename with a different fresh\u001b[0m\n",
      "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 2\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n",
    "  def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n",
    "  def r(e: Expr) = renv(Map.empty, e)\n",
    "\n",
    "  def factorial(fact: String, n: String) = Fun(fact, (n, TNumber), TNumber,\n",
    "    If(Binary(Eq, Var(n), N(1)),\n",
    "    N(1),\n",
    "    Binary(Times, Var(n), Call(Var(fact), Binary(Plus, Var(n), N(-1)))))\n",
    "  )\n",
    "\n",
    "  \"rename\" should \"rename bound variables consistently for factorial\" in {\n",
    "    assertResult( (2, factorial(\"x0\", \"x1\")) ) { r(factorial(\"fact\", \"n\")) }\n",
    "  }\n",
    "\n",
    "  it should \"rename with a different fresh\" in {\n",
    "    assertResult( (4, factorial(\"fact0\", \"n2\")) ) {\n",
    "      val e = factorial(\"fact\", \"n\")\n",
    "      rename[Int](Map.empty, e)(x => doget flatMap { i => doput(i + 2) map { _ => s\"${x}${i}\" } })(0)\n",
    "    }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88bdb153-d9bc-4772-86f5-aebe0a8b8429",
   "metadata": {},
   "source": [
    "<span class=\"theorem-title\">**Exercise 10 (4 points)**</span> Finally,\n",
    "implement the lowering-transformation function `uniquify: Expr => Expr`\n",
    "on closed expressions using a call to `rename` to rename bound variables\n",
    "consistently with the `freshVarWith: String => DoWith[Int, String]`\n",
    "function defined above. Start the `Int` counter-state at `0`.\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "24fa60ef",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bb21762ce36cdb75c3b26c78ef37cb84",
     "grade": false,
     "grade_id": "uniquify-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36muniquify\u001b[39m"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def uniquify(e: Expr): Expr = {\n",
    "  require(isClosed(e), s\"$e should be closed\")\n",
    "  val counterState = 0\n",
    "  val freshVar: String => DoWith[Int, String] = freshVarWith\n",
    "  var renamedExpr: DoWith[Int, Expr] = rename(Map(), e)(freshVar)\n",
    "  renamedExpr(counterState)._2\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04c11eb3-5299-4a78-a73a-cfb1690928ef",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "-   Hint: The `rename` and `freshVarWith` functions constructs `DoWith`\n",
    "    objects. The `uniquify` finally uses a `DoWith[Int, String]` object.\n",
    "    How? By calling it with the initial state `0`.\n",
    "\n",
    "#### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "7dc1f2d2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "338a55434d352c17fe37abfc4b18efaf",
     "grade": true,
     "grade_id": "uniquify-tester",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n",
      "\u001b[32mcmd65$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32muniquify\u001b[0m\n",
      "\u001b[32m- should work on the example\u001b[0m\n",
      "\u001b[32m- should work another example\u001b[0m\n",
      "\u001b[36mRun completed in 7 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 2\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n",
    "  def idfun(f: String, y: String) =\n",
    "    Fun(f, (y, TNumber), TNumber, Var(y))\n",
    "  def aconst(x1: String, x2: String, x3: String, x4: String, x5: String) =\n",
    "    ConstDecl(x1, Binary(Plus, Call(idfun(x2, x3), N(1)), Call(idfun(x4, x5), N(2))), Var(x1))\n",
    "  def nm(x: String, i: Int) = s\"${x}_${i}\"\n",
    "\n",
    "  \"uniquify\" should \"work on the example\" in {\n",
    "    forAll { (x1: String, x2: String, x3: String, x4: String, x5: String) =>\n",
    "      uniquify(aconst(x1, x2, x3, x4, x5)) should be {\n",
    "        aconst(nm(x1, 0), nm(x2, 1), nm(x3, 2), nm(x4, 3), nm(x5, 4))\n",
    "      }\n",
    "    }\n",
    "  }\n",
    "\n",
    "  val e = ConstDecl(\"a\", ConstDecl(\"a\", N(1), Var(\"a\")), ConstDecl(\"b\",N(2), Var(\"b\")))\n",
    "  val exp = ConstDecl(\"a_0\", ConstDecl(\"a_1\", N(1), Var(\"a_1\")), ConstDecl(\"b_2\", N(2), Var(\"b_2\")))\n",
    "  it should \"work another example\" in {\n",
    "    assertResult(exp) { uniquify(e) }\n",
    "  }\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbd68990-6a54-4b7a-a803-41e9c2c76028",
   "metadata": {},
   "source": [
    "### `DoWith` with Collections\n",
    "\n",
    "Recall the higher-order function `map` we considered previously for\n",
    "`List`s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "9065e962",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmap\u001b[39m"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def map[A, B](l: List[A])(f: A => B): List[B] =\n",
    "  l.foldRight[List[B]](\n",
    "    Nil\n",
    "  ) { (h, acc) =>\n",
    "    f(h) :: acc\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a412e371-e057-4b12-bd63-eb2104c075c6",
   "metadata": {},
   "source": [
    "We may want to use `DoWith` to encapsulate some stateful computation\n",
    "with other data structures, like `List`s. For example, we want a version\n",
    "of `map` that can take a stateful callback:\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 11 (4 points)**</span> Implement\n",
    "a function `mapWith` for `List` that takes a stateful callback function\n",
    "`f: A => DoWith[S, B]`:\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "1bb63578",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "47940fa52b9ac6f17bc42ab1aabc5314",
     "grade": false,
     "grade_id": "mapWith-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmapWith\u001b[39m"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mapWith[S, A, B](l: List[A])(f: A => DoWith[S, B]): DoWith[S, List[B]] =\n",
    "  l.foldRight[DoWith[S, List[B]]](\n",
    "      doreturn(Nil)\n",
    "  ) { (h, acc) =>\n",
    "      f(h) flatMap { b =>\n",
    "          acc map { bs =>\n",
    "              b ::bs\n",
    "          }\n",
    "      }\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "369fa030-18bb-44b1-9ac5-aed93363af2e",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "2cc00334",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8153b1fdc48b0960100f83d828aa0e35",
     "grade": true,
     "grade_id": "mapWith-tester",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
      "\u001b[32mcmd68$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mmapWith\u001b[0m\n",
      "\u001b[32m- should Test1\u001b[0m\n",
      "\u001b[32m- should Test2\u001b[0m\n",
      "\u001b[32m- should Test3\u001b[0m\n",
      "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val l = List(1, 2, 3, 4, 5)\n",
    "  val r1 = l.map { i => i + 1 }\n",
    "\n",
    "  def dowith1[W]: DoWith[W,List[Int]] = mapWith(l) { i: Int => doreturn(i + 1) }\n",
    "      \n",
    "  \"mapWith\" should \"Test1\" in { assertResult((true,r1)) { dowith1(true) } }\n",
    "  it should \"Test2\" in {assertResult((42,r1)) { dowith1(42) }}\n",
    "  it should \"Test3\" in {assertResult((2 * l.length + 1, r1)) {\n",
    "        val dw: DoWith[Int,List[Int]] = mapWith(l) { i: Int =>\n",
    "          domodify[Int](s => s + 2) map { _ => i + 1 }\n",
    "        }\n",
    "        dw(1)\n",
    "      }}\n",
    "}, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2061336b-912b-4be5-82b7-bb4894c11ce5",
   "metadata": {},
   "source": [
    "Also recall the `mapFirst` function we defined previously that replaces\n",
    "the first element in `l` where `f` returns `Some(a)` with `a`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "a523fa60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirst\u001b[39m"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mapFirst[A](l: List[A])(f: A => Option[A]): List[A] = l match {\n",
    "  case Nil => Nil\n",
    "  case h :: t =>\n",
    "    f(h) match {\n",
    "      case None => h :: mapFirst(t)(f)\n",
    "      case Some(h) => h :: t\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b88d3328-5bf0-4ba9-84bd-8fb37b46b1d6",
   "metadata": {},
   "source": [
    "<span class=\"theorem-title\">**Exercise 12 (4 points)**</span> Implement\n",
    "a function `mapFirstWith` for `List` that instead takes a stateful\n",
    "callback function `f: A => Option[DoWith[S, B]]`:\n",
    "\n",
    "**Edit this cell:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "f22eb076",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "59cf107ce7934c9aa80564c7169349b0",
     "grade": false,
     "grade_id": "mapFirstWith-answer",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirstWith\u001b[39m"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mapFirstWith[S, A](l: List[A])(f: A => Option[DoWith[S, A]]): DoWith[S, List[A]] = l match {\n",
    "    case Nil => doreturn(Nil)\n",
    "    case h :: t =>\n",
    "    f(h) match {\n",
    "        case Some(doer) => doer map { newHead => newHead :: t }\n",
    "        case None => mapFirstWith(t)(f) map { tail => h :: tail }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "424f6d6a-6f9c-47bc-ae6f-4a31259b985c",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "626bee45",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9f8622d87ad3a7b701904166a0514993",
     "grade": true,
     "grade_id": "mapFirstWith-tester",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
      "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n",
      "\u001b[32mmapFirstWith\u001b[0m\n",
      "\u001b[32m- should Test1\u001b[0m\n",
      "\u001b[32m- should Test2\u001b[0m\n",
      "\u001b[32m- should Test3\u001b[0m\n",
      "\u001b[32m- should Test4\u001b[0m\n",
      "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
      "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
      "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
      "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
      "\u001b[32mAll tests passed.\u001b[0m\n",
      "*** 🎉 Tests Passed (4 points) ***\n"
     ]
    }
   ],
   "source": [
    "test(new AnyFlatSpec {\n",
    "  val l = List(1, 2, -3, 4, -5)\n",
    "  val r = List(1, 2, 3, 4, -5)\n",
    "  def dowith[W]: DoWith[W,List[Int]] = mapFirstWith(l) { (i: Int) => if (i < 0) Some(doreturn(-i)) else None }\n",
    "      \n",
    "  val w1 = true\n",
    "  val w2 = 10\n",
    "  val w3 = \"test_str\"\n",
    "  val w4 = List\n",
    "      \n",
    "  \"mapFirstWith\" should \"Test1\" in { assertResult((w1,r)){ dowith(w1) } }\n",
    "  it should \"Test2\" in {assertResult((w2,r)) { dowith(w2) }}\n",
    "  it should \"Test3\" in {assertResult((w3,r)) { dowith(w3) }}\n",
    "  it should \"Test4\" in {assertResult((w4,r)) { dowith(w4) }}\n",
    "}, 4)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}