encapsulating-effects-exercise.ipynb

{
 "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": null,
   "id": "4313a4e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "val NAME = \"\"\n",
    "val COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15342603",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "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": null,
   "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": [],
   "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": null,
   "id": "eb35c7e6",
   "metadata": {},
   "outputs": [],
   "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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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": null,
   "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": [],
   "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",
    "        ???\n",
    "      else err(e, tgot)\n",
    "    }\n",
    "\n",
    "  e match {\n",
    "    case Var(x) => Right(tenv(x))\n",
    "    case ConstDecl(x, e1, 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) =>\n",
    "      ???\n",
    "    case Binary(Plus|Times, e1, e2) =>\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) => typecheck(tenv, e1, TBool) flatMap { _ =>\n",
    "      ???\n",
    "    }\n",
    "    case Fun(x, yt @ (y, t), tret, e1) => {\n",
    "      ???\n",
    "    }\n",
    "    case Call(e1, e2) =>\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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "id": "6e523d01",
   "metadata": {},
   "outputs": [],
   "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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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": null,
   "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": [],
   "source": [
    "def doreturn[S, A](a: A): DoWith[S, A] =\n",
    "  ???"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f8163f1-cf87-4beb-8dbd-324b849e1156",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": [],
   "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": null,
   "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": [],
   "source": [
    "def domodify[S](f: S => S): DoWith[S, Unit] = \n",
    "  ???"
   ]
  },
  {
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "source": [
    "def freshVar(x: String): Int => (Int, String) =\n",
    "  { i =>\n",
    "      ???\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c9387bd-f827-48f0-96b2-527fd727298a",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": [],
   "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": null,
   "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": [],
   "source": [
    "def freshVarWith(x: String): DoWith[Int, String] =\n",
    "  ???"
   ]
  },
  {
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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(_) =>\n",
    "        ???\n",
    "\n",
    "      case Var(x) =>\n",
    "        ???\n",
    "\n",
    "      case ConstDecl(x, e1, e2) => fresh(x) flatMap { x_ =>\n",
    "        ???\n",
    "      }\n",
    "\n",
    "      case Unary(uop, e1) =>\n",
    "        ???\n",
    "\n",
    "      case Binary(bop, e1, e2) =>\n",
    "        ???\n",
    "\n",
    "      case If(e1, e2, e3) =>\n",
    "        ???\n",
    "\n",
    "      case Fun(x, (y, t), tret, e1) =>\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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "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": null,
   "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": [],
   "source": [
    "def uniquify(e: Expr): Expr = {\n",
    "  require(isClosed(e), s\"$e should be closed\")\n",
    "  ???\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": null,
   "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": [],
   "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": null,
   "id": "9065e962",
   "metadata": {},
   "outputs": [],
   "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": null,
   "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": [],
   "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",
    "    ???\n",
    "  ) { (h, acc) =>\n",
    "    ???\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "369fa030-18bb-44b1-9ac5-aed93363af2e",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": [],
   "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": null,
   "id": "a523fa60",
   "metadata": {},
   "outputs": [],
   "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": null,
   "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": [],
   "source": [
    "def mapFirstWith[S, A](l: List[A])(f: A => Option[DoWith[S, A]]): DoWith[S, List[A]] = l match {\n",
    "  case Nil =>\n",
    "    ???\n",
    "  case h :: t =>\n",
    "    ???\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "424f6d6a-6f9c-47bc-ae6f-4a31259b985c",
   "metadata": {},
   "source": [
    "#### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": [],
   "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",
   "path": "/Users/bec/Library/Jupyter/kernels/scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}