csci3155

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a105002c-be69-423a-92c4-af05a77af8a2",
   "metadata": {},
   "source": [
    "# Lab: Recursion, Inductive Data Types, and Abstract Syntax Trees\n",
    "\n",
    "<!-- 3 Expressions -->\n",
    "\n",
    "<!-- 4 Binding and Scope -->\n",
    "\n",
    "<!-- 8 Recursion -->\n",
    "\n",
    "<!-- 9 Inductive Data Types -->\n",
    "\n",
    "### Learning Goals\n",
    "\n",
    "The primary learning goals of this assignment are to build intuition for\n",
    "the following:\n",
    "\n",
    "Functional Programming Skills  \n",
    "Representing data structures using algebraic data types.\n",
    "\n",
    "Programming Languages Ideas  \n",
    "Representing programs as abstract syntax.\n",
    "\n",
    "### Instructions\n",
    "\n",
    "A version of project files for this lab resides in the public\n",
    "[pppl-lab1](https://github.com/csci3155/pppl-lab1) repository. Please\n",
    "follow separate instructions to get a private clone of this repository\n",
    "for your work.\n",
    "\n",
    "You will be replacing `???` in the `Lab1.scala` file with solutions to\n",
    "the coding exercises described below. Make sure that you remove the\n",
    "`???` and replace it with the answer.\n",
    "\n",
    "You may add additional tests to the `Lab1Spec.scala` file. In the\n",
    "`Lab1Spec.scala`, there is empty test class `Lab1StudentSpec` that you\n",
    "can use to separate your tests from the given tests in the `Lab1Spec`\n",
    "class. You are also likely to edit `Lab1.worksheet.sc` for any scratch\n",
    "work.\n",
    "\n",
    "Single-file notebooks are convenient when experimenting with small bits\n",
    "of code, but they can become unwieldy when one needs a multiple-file\n",
    "project instead. In this case, we use standard build tools (e.g., `sbt`\n",
    "for Scala), IDEs (e.g., Visual Studio Code with Metals), and source\n",
    "control systems (e.g., `git` with GitHub). While it is almost overkill\n",
    "to use these standard software engineering tools for this lab, we get\n",
    "practice using these tools in the small.\n",
    "\n",
    "If you like, you may use this notebook for experimentation. However,\n",
    "**please make sure your code is in `Lab1.scala`; this notebook will not\n",
    "graded.**\n",
    "\n",
    "## Recursion\n",
    "\n",
    "### Repeat String\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 1**</span> Write a recursive\n",
    "function `repeat`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f7013900",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrepeat\u001b[39m"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repeat(s: String, n: Int): String = {\n",
    "    if (n == 0) \"\"\n",
    "    else s + repeat(s, n - 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54e4328d-f72f-42f8-944e-26e893c9ee2a",
   "metadata": {},
   "source": [
    "where `repeat(s, n)` returns a string with `n` copies of `s`\n",
    "concatenated together. For example, `repeat(\"a\",3)` returns `\"aaa\"`.\n",
    "Implement by this function by direct recursion. Do not use any Scala\n",
    "library methods.\n",
    "\n",
    "### Square Root\n",
    "\n",
    "In this exercise, we will implement the square root function. To do so,\n",
    "we will use Newton’s method (also known as Newton-Raphson).\n",
    "\n",
    "Recall from Calculus that a root of a differentiable function can be\n",
    "iteratively approximated by following tangent lines. More precisely, let\n",
    "$f$ be a differentiable function, and let $x_0$ be an initial guess for\n",
    "a root of $f$. Then, Newton’s method specifies a sequence of\n",
    "approximations $x_0, x_1, \\ldots$ with the following recursive equation:\n",
    "\n",
    "$$\n",
    "x_{n + 1} = x_n - \\frac{f(x_n)}{f'(x_n)}\n",
    "\\;.$$\n",
    "\n",
    "The square root of a real number $c$ for $c > 0$, written $\\sqrt{c}$, is\n",
    "a positive $x$ such that $x^2 = c$. Thus, to compute the square root of\n",
    "a number $c$, we want to find the positive root of the function:\n",
    "$$f(x) = x^2 - c \\;.$$ Thus, the following recursive equation defines a\n",
    "sequence of approximations for $\\sqrt{c}$:\n",
    "$$x_{n + 1} = x_n - \\frac{x_n^2 - c}{2 x_n} \\;.$$\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 2**</span> First, implement a\n",
    "function `sqrtStep`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c539e344",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrtStep\u001b[39m"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sqrtStep(c: Double, xn: Double): Double = {\n",
    "    val n = (xn * xn) - c\n",
    "    val d = 2 * xn\n",
    "    xn - (n / d)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dffe57a-0f30-4de2-b713-67870c807c77",
   "metadata": {},
   "source": [
    "that takes one step of approximation in computing $\\sqrt{c}$ (i.e.,\n",
    "computes $x_{n + 1}$ from $x_n$).\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 3**</span> Next, implement a\n",
    "function `sqrtN`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9bb776bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrtN\u001b[39m"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sqrtN(c: Double, x0: Double, n: Int): Double = {\n",
    "    if (n == 0) x0\n",
    "    else sqrtN(c, sqrtStep(c, x0), n - 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "387179d2-3946-46c8-9c89-888ce27a1933",
   "metadata": {},
   "source": [
    "that computes the $n$th approximation $x_n$ from an initial guess $x_0$.\n",
    "You will want to call `sqrtStep` implemented in the previous part.\n",
    "\n",
    "You need to implement this function using recursion and no mutable\n",
    "variables (i.e., `var`s)—you will want to use a recursive helper\n",
    "function. It is also quite informative to compare your recursive\n",
    "solution with one using a `while` loop.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 4**</span> Now, implement a\n",
    "function `sqrtErr`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5bfde3b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "cmd7.sc:3: value abs is not a member of object almond.display.Math\n",
      "    if (Math.abs((x0 * x0) - c) < epsilon) x0\n",
      "             ^\n",
      "Compilation Failed"
     ]
    }
   ],
   "source": [
    "def sqrtErr(c: Double, x0: Double, epsilon: Double): Double = {\n",
    "    val next = sqrtStep(c, x0)\n",
    "    if (Math.abs((x0 * x0) - c) < epsilon) x0\n",
    "    else sqrtErr(c, next, epsilon)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85e68de9-8cad-4a3f-a34c-b0292ffa3cad",
   "metadata": {},
   "source": [
    "that is very similar to `sqrtN` but instead computes approximations\n",
    "$x_n$ until the approximation error is within $\\varepsilon$ (`epsilon`),\n",
    "that is, $|x_n^2 - c| < \\varepsilon \\;.$ You can use your absolute value\n",
    "function `abs` implemented in a previous part. A wrapper function `sqrt`\n",
    "is given in the template that simply calls `sqrtErr` with a choice of\n",
    "`x0` and `epsilon`.\n",
    "\n",
    "You need to implement this function using recursion, though it is useful\n",
    "to compare your recursive solution to one with a `while` loop.\n",
    "\n",
    "## Data Structures Review: Binary Search Trees\n",
    "\n",
    "In this question, we review implementing operations on binary search\n",
    "trees from Data Structures. Balanced binary search trees are common in\n",
    "standard libraries to implement collections, such as sets or maps. For\n",
    "simplicity, we do not worry about balancing in this question.\n",
    "\n",
    "Trees are important structures in developing interpreters, so this\n",
    "question is also critical practice in implementing tree manipulations.\n",
    "\n",
    "A binary search tree is a binary tree that satisfies an ordering\n",
    "invariant. Let $n$ be any node in a binary search tree whose left child\n",
    "is $l$, data value is $d$, and right child is $r$. The ordering\n",
    "invariant is that all of the data values in the subtree rooted at $l$\n",
    "must be $< d$, and all of the data values in the subtree rooted at $r$\n",
    "must be $\\geq d$. We will represent a binary trees containing integer\n",
    "data using the following Scala `case class`es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d3700708",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mTree\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mEmpty\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Tree\n",
    "case object Empty extends Tree\n",
    "case class Node(l: Tree, d: Int, r: Tree) extends Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e795398-4da3-46b3-b556-f0bc5852a97d",
   "metadata": {},
   "source": [
    "A `Tree` is either `Empty` or a `Node` with left child `l`, data value\n",
    "`d`, and right child `r`.\n",
    "\n",
    "For this question, we will implement the following four functions.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 5**</span> The function `repOk`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2d4949ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrepOk\u001b[39m"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repOk(t: Tree): Boolean = {\n",
    "    def check(t: Tree, min: Int, max: Int): Boolean = t match {\n",
    "      case Empty => true\n",
    "      case Node(l, d, r) =>\n",
    "        d >= min && d < max && check(l, min, d) && check(r, d, max)\n",
    "    }\n",
    "    check(t, Int.MinValue, Int.MaxValue)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9902f78c-a33b-4ca0-8ae9-b3033b4426b9",
   "metadata": {},
   "source": [
    "checks that an instance of `Tree` is valid binary search tree. In other\n",
    "words, it checks using a traversal of the tree the ordering invariant\n",
    "described above. This function is useful for testing your\n",
    "implementation.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 6**</span> The function `insert`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5792d194",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36minsert\u001b[39m"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def insert(t: Tree, n: Int): Tree = t match {\n",
    "    case Empty => Node(Empty, n, Empty)\n",
    "    case Node(l, d, r) =>\n",
    "      if (n < d) Node(insert(l, n), d, r)\n",
    "      else Node(l, d, insert(r, n))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "036345e1-2834-4042-ab05-e89da6ffcd11",
   "metadata": {},
   "source": [
    "inserts an integer into the binary search tree. Observe that the return\n",
    "type of `insert` is a `Tree`. This choice suggests a functional style\n",
    "where we construct and return a new output tree that is the input tree\n",
    "`t` with the additional integer `n` as opposed to destructively updating\n",
    "the input tree.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 7**</span> The function\n",
    "`deleteMin`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "25a13b75",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdeleteMin\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def deleteMin(t: Tree): (Tree, Int) = {\n",
    "    require(t != Empty)\n",
    "    (t: @unchecked) match {\n",
    "      case Node(Empty, d, r) => (r, d)\n",
    "      case Node(l, d, r) =>\n",
    "        val (l1, m) = deleteMin(l)\n",
    "        (Node(l1, d, r), m)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97630bf8-7afd-4dd9-8aa4-3dcb7ff05df8",
   "metadata": {},
   "source": [
    "deletes the smallest data element in the search tree (i.e., the leftmost\n",
    "node). It returns both the updated tree and the data value of the\n",
    "deleted node. This function is intended as a helper function for the\n",
    "`delete` function.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 8**</span> The function `delete`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6fe5bb5f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdelete\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def delete(t: Tree, n: Int): Tree = t match {\n",
    "    case Empty => Empty\n",
    "    case Node(l, d, r) if n < d =>\n",
    "      Node(delete(l, n), d, r)\n",
    "    case Node(l, d, r) if n > d =>\n",
    "      Node(l, d, delete(r, n))\n",
    "    case Node(l, d, r) =>\n",
    "      if (l == Empty) r\n",
    "      else if (r == Empty) l\n",
    "      else {\n",
    "        val (r1, min) = deleteMin(r)\n",
    "        Node(l, min, r1)\n",
    "      }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c131559-294b-4894-be21-3ab2cdf996fb",
   "metadata": {},
   "source": [
    "removes the first node with data value equal to `n`. This function is\n",
    "trickier than `insert` because what should be done depends on whether\n",
    "the node to be deleted has children or not. We advise that you take\n",
    "advantage of pattern matching to organize the cases.\n",
    "\n",
    "## Interpreter: JavaScripty Calculator\n",
    "\n",
    "In this question, we consider the arithmetic sub-language of JavaScripty\n",
    "(i.e., a basic calculator). We represent the abstract syntax for this\n",
    "sub-language in Scala using the following inductive data type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "32b17391",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\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[32mtrait\u001b[39m \u001b[36mUop\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNeg\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[36mMinus\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mTimes\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mDiv\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr                                            // e ::=\n",
    "case class N(n: Double) extends Expr                         //   n\n",
    "case class Unary(uop: Uop, e1: Expr) extends Expr            // | uop e1\n",
    "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2\n",
    "\n",
    "sealed trait Uop              // uop ::=\n",
    "case object Neg extends Uop   //   -\n",
    "\n",
    "sealed trait Bop              // bop ::=\n",
    "case object Plus extends Bop  //   +\n",
    "case object Minus extends Bop // | -\n",
    "case object Times extends Bop // | *\n",
    "case object Div extends Bop   // | /"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f579c467-070f-4902-a445-8a0109a81130",
   "metadata": {},
   "source": [
    "In comments, we give a grammar that connects the abstract syntax with\n",
    "the concrete syntax of the language. We consider grammars in more detail\n",
    "subsequently<span class=\"hidden\">in **?@sec-grammars**</span>. For now,\n",
    "it is fine to ignore the concrete syntax or use your intuition for the\n",
    "connection. ow, given the inductive data type `Expr` defining the\n",
    "abstract syntax:\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 9**</span> Implement the `eval`\n",
    "function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "054fca87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NaN\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m\n",
       "\u001b[36mexpr1\u001b[39m: \u001b[32mBinary\u001b[39m = \u001b[33mBinary\u001b[39m(bop = Div, e1 = \u001b[33mN\u001b[39m(n = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mN\u001b[39m(n = \u001b[32m0.0\u001b[39m))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def eval(e: Expr): Double = e match {\n",
    "  case N(n) => n\n",
    "  case Unary(Neg, e1) => -eval(e1)\n",
    "  case Binary(Plus, e1, e2) => eval(e1) + eval(e2)\n",
    "  case Binary(Minus, e1, e2) => eval(e1) - eval(e2)\n",
    "  case Binary(Times, e1, e2) => eval(e1) * eval(e2)\n",
    "  case Binary(Div, e1, e2) => eval(e1) / eval(e2)\n",
    "}\n",
    "val expr1 = Binary(Div, N(0.0), N(0.0))\n",
    "println(eval(expr1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03c23117-f6c3-4427-b88a-eb985f06120d",
   "metadata": {},
   "source": [
    "that evaluates the Scala representation of a JavaScripty expression `e`\n",
    "to the Scala double-precision floating point number corresponding to the\n",
    "Scala representation of the JavaScripty *value* of `e`. At this point,\n",
    "you have implemented your first language interpreter!\n",
    "\n",
    "To go in more detail, consider a JavaScripty expression $e$, and imagine\n",
    "$e$ to be concrete syntax. This text is parsed into a JavaScripty AST\n",
    "`e`, that is, a Scala value of type `Expr`. Then, the result of `eval`\n",
    "is a Scala number of type `Double` and should match the interpretation\n",
    "of $e$ as a JavaScript expression. These distinctions can be subtle but\n",
    "learning to distinguish between them will go a long way in making sense\n",
    "of programming languages.\n",
    "\n",
    "To see what a JavaScripty expression $e$ should evaluate to, you may\n",
    "want to run $e$ through a JavaScript interpreter to see what the value\n",
    "should be. For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "931bda9b-2809-4d50-91d6-25b9872deb60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres13\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m7\u001b[39m"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 + 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ad9e62ed-da7b-4af3-8247-379b7321d3c5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres14\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m0\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 / 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "0f0791e5-834d-4536-8634-4f503740caf6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres15\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m32\u001b[39m"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6 * 4 - 2 + 10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "392df5bb-64b7-4b89-bb92-2dce9ee0e9a8",
   "metadata": {},
   "source": [
    "### Experiment in a Worksheet\n",
    "\n",
    "Scala worksheets provide an interactive interface in the context of a\n",
    "multi-file project. A worksheet is a good place to start for\n",
    "experimenting with an implementation, whether on existing code or code\n",
    "that you are in the process of writing. A scratch worksheet\n",
    "`Lab1.worksheet.sc` is provided for you in the code repository.\n",
    "\n",
    "To test and experiment with your `eval` function, you can write\n",
    "JavaScripty expressions directly in abstract syntax like above. You can\n",
    "also make use of a parser that is provided for you: it reads in a\n",
    "JavaScripty program-as-a-`String` and converts into an abstract syntax\n",
    "tree of type `Expr`.\n",
    "\n",
    "For your convenience, we have also provided in the template `Lab1.scala`\n",
    "file, an overloaded `eval: String => Double` function that calls the\n",
    "provided parser and then delegates to your `eval: Expr => Double`\n",
    "function.\n",
    "\n",
    "### Test-Driven Development and Regression Testing\n",
    "\n",
    "Once you have experimented enough in your worksheet to have some tests,\n",
    "it is useful to save those tests to run over-and-over again as you work\n",
    "on your implementation. The idea behind test-driven development is that\n",
    "we first write a test for what we expect our implementation to do.\n",
    "Initially, we expect our implementation to fail the test, and then we\n",
    "work on our implementation until the test succeeds. IDEs have features\n",
    "to support this workflow. While a test suite can never be exhaustive, we\n",
    "have provided a number of initial tests for you in `Lab1Spec.scala` to\n",
    "partially drive your test-driven development of the functions in this\n",
    "assignment.\n",
    "\n",
    "### Additional Notes\n",
    "\n",
    "While you may not need them in this assignment, the `ast.scala` file\n",
    "also includes some basic helper functions for working with the AST, such\n",
    "as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ec9b583",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValue(e: Expr): Boolean = e match {\n",
    "  case N(_) => true\n",
    "  case _ => false\n",
    "}\n",
    "\n",
    "val e_minus4_2 = N(-4.2)\n",
    "isValue(e_minus4_2)\n",
    "\n",
    "val e_neg_4_2 = Unary(Neg, N(4.2))\n",
    "isValue(e_neg_4_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6705b4d2-c5d5-429c-a1ba-df9a2afb602e",
   "metadata": {},
   "source": [
    "the defines which expressions are values. In this case, literal number\n",
    "expressions `N(` $n$ `)` are values where $n$ is the meta-variable for\n",
    "JavaScripty numbers. We represent JavaScripty numbers in Scala with\n",
    "Scala values of type `Double`.\n",
    "\n",
    "We also define functions to pretty-print, that is, convert abstract\n",
    "syntax to concrete syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "769e512d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prettyNumber(n: Double): String =\n",
    "  if (n.isWhole) \"%.0f\" format n else n.toString\n",
    "\n",
    "def pretty(v: Expr): String = {\n",
    "  require(isValue(v))\n",
    "  (v: @unchecked) match {\n",
    "    case N(n) => prettyNumber(n)\n",
    "  }\n",
    "}\n",
    "\n",
    "pretty(N(4.2))\n",
    "pretty(N(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82aed5b1-4bc6-4683-a890-4728eb767ff1",
   "metadata": {},
   "source": [
    "We only define `pretty` for values, and we do not override the\n",
    "`toString` method so that the abstract syntax can be printed as-is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "222fbd39",
   "metadata": {},
   "outputs": [],
   "source": [
    "e_minus4_2.toString\n",
    "e_neg_4_2.toString"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc7426dc-4ec1-47d3-b116-d3f5da85ed0c",
   "metadata": {},
   "source": [
    "The `@unchecked` annotation tells the Scala compiler that we know the\n",
    "pattern match is non-exhaustive syntactically, so we do not want to be\n",
    "warned about it. However, we see that our definition of `isValue` rules\n",
    "out the potential for a match error at run time (right?).\n",
    "\n",
    "## Submission\n",
    "\n",
    "If you are a University of Colorado Boulder student, we use Gradescope\n",
    "for assignment submission. In summary,\n",
    "\n",
    "-   [ ] Create a private GitHub repository by clicking on a GitHub\n",
    "    Classroom link from the corresponding Canvas assignment entry.\n",
    "-   [ ] Clone your private GitHub repository to your development\n",
    "    environment (using the `<> Code` button on GitHub to get the\n",
    "    repository URL).\n",
    "-   [ ] Work on this lab from your cloned repository. Use Git to save\n",
    "    versions on GitHub (e.g., `git add`, `git commit`, `git push` on the\n",
    "    command line or via VSCode).\n",
    "-   [ ] Submit to the corresponding Gradescope assignment entry for\n",
    "    grading by choosing GitHub as the submission method.\n",
    "\n",
    "You need to have a GitHub identity and must have your full name in your\n",
    "GitHub profile in case we need to associate you with your submissions."
   ]
  }
 ],
 "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
}