diff options
Diffstat (limited to 'lab1')
-rw-r--r-- | lab1/build.sbt | 47 | ||||
-rw-r--r-- | lab1/inductive-data-types-lab.ipynb | 825 | ||||
-rw-r--r-- | lab1/project/build.properties | 1 | ||||
-rw-r--r-- | lab1/src/main/scala/jsy/lab1/Lab1.scala | 115 | ||||
-rw-r--r-- | lab1/src/main/scala/jsy/lab1/Lab1.worksheet.sc | 76 | ||||
-rw-r--r-- | lab1/src/main/scala/jsy/lab1/Parser.scala | 153 | ||||
-rw-r--r-- | lab1/src/main/scala/jsy/lab1/ast.scala | 48 | ||||
-rw-r--r-- | lab1/src/test/scala/jsy/lab1/Lab1Spec.scala | 251 |
8 files changed, 1516 insertions, 0 deletions
diff --git a/lab1/build.sbt b/lab1/build.sbt new file mode 100644 index 0000000..e2bc45e --- /dev/null +++ b/lab1/build.sbt @@ -0,0 +1,47 @@ +name := "pppl-lab1" + +lazy val commonSettings = Seq( + organization := "edu.colorado.cs", + version := "4.0.0", + + scalaVersion := "2.13.14", + scalacOptions ++= Seq( + "-unchecked", // Enable additional warnings where generated code depends on assumptions. + "-feature", // Emit warning for features that should be imported explicitly + "-Xcheckinit", // Wrap field accessors to throw an exception on uninitialized access + "-deprecation", // Emit warning and location for usages of deprecated APIs. + "-explaintypes", // Explain type errors in more detail. + "-Ywarn-extra-implicit", // more than one implicit parameter section is defined + "-Xlint:nullary-unit", // nullary methods return Unit + "-Xlint:inaccessible", // inaccessible types in method signatures + "-Xlint:infer-any", // a type argument is inferred to be Any + "-Xlint:missing-interpolator", // literal appears to be missing an interpolator id + "-Xlint:option-implicit", // apply used implicit view + "-Xlint:package-object-classes", // object defined in package object + "-Xlint:stars-align", // wildcard must align with sequence component + "-Xlint:constant", // a constant arithmetic expression results in an error + //"-Xfatal-warnings", // turn warnings into errors + ), + libraryDependencies ++= Seq( + "org.scala-lang.modules" %% "scala-parser-combinators" % "2.4.0", + "org.scalatest" %% "scalatest" % "3.2.19" % "test" + ), + + // set logging to show only errors during runs + logLevel / run := Level.Error, + logLevel / runMain := Level.Error, + Global / excludeLintKeys += logLevel, + + // JVM arguments: 8G heap size, 2M stack size + //javaOptions in Test += "-Xmx8G -Xss2M", + + // scoverage options: always build with coverage + //coverageEnabled := true, + + // scalatest options: -o standard output, D durations + // -e stderr + Test / testOptions += Tests.Argument("-e") +) + +lazy val lab = (project in file(".")). + settings(commonSettings: _*) diff --git a/lab1/inductive-data-types-lab.ipynb b/lab1/inductive-data-types-lab.ipynb new file mode 100644 index 0000000..b2219a1 --- /dev/null +++ b/lab1/inductive-data-types-lab.ipynb @@ -0,0 +1,825 @@ +{ + "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 +} diff --git a/lab1/project/build.properties b/lab1/project/build.properties new file mode 100644 index 0000000..ee4c672 --- /dev/null +++ b/lab1/project/build.properties @@ -0,0 +1 @@ +sbt.version=1.10.1 diff --git a/lab1/src/main/scala/jsy/lab1/Lab1.scala b/lab1/src/main/scala/jsy/lab1/Lab1.scala new file mode 100644 index 0000000..d3a73b1 --- /dev/null +++ b/lab1/src/main/scala/jsy/lab1/Lab1.scala @@ -0,0 +1,115 @@ +package jsy.lab1 + +object Lab1 { + /* + * CSCI 3155: Lab 1 + * Jack Sangdahl + * 09 September 2024 + * + * Partner: N/A + * Collaborators: N/A + */ + + /* Example: Test-driven development of `plus` */ + + def plus(x: Int, y: Int): Int = x + y + + /* Exercises */ + + def repeat(s: String, n: Int): String = { + require(n >= 0) + if (n == 0) "" + else s + repeat(s, n - 1) + } + + def sqrtStep(c: Double, xn: Double): Double = { + val n = (xn * xn) - c + val d = 2 * xn + xn - (n / d) + } + + def sqrtN(c: Double, x0: Double, n: Int): Double = { + require(n >= 0 && c >= 0) + if (n == 0) x0 + else sqrtN(c, sqrtStep(c, x0), n - 1) + } + + def sqrtErr(c: Double, x0: Double, epsilon: Double): Double = { + require(epsilon > 0) + val next = sqrtStep(c, x0) + if (Math.abs((x0 * x0) - c) < epsilon) x0 + else sqrtErr(c, next, epsilon) + } + + def sqrt(c: Double): Double = { + require(c >= 0) + if (c == 0) 0 else sqrtErr(c, 1.0, 0.0001) + } + + /* Search Tree */ + + sealed abstract class Tree + case object Empty extends Tree + case class Node(l: Tree, d: Int, r: Tree) extends Tree + + def repOk(t: Tree): Boolean = { + def check(t: Tree, min: Int, max: Int): Boolean = t match { + case Empty => true + case Node(l, d, r) => + d >= min && d < max && check(l, min, d) && check(r, d, max) + } + check(t, Int.MinValue, Int.MaxValue) + } + + def insert(t: Tree, n: Int): Tree = t match { + case Empty => Node(Empty, n, Empty) + case Node(l, d, r) => + if (n < d) Node(insert(l, n), d, r) + else Node(l, d, insert(r, n)) + } + + def deleteMin(t: Tree): (Tree, Int) = { + require(t != Empty) + (t: @unchecked) match { + case Node(Empty, d, r) => (r, d) + case Node(l, d, r) => + val (l1, m) = deleteMin(l) + (Node(l1, d, r), m) + } + } + + def delete(t: Tree, n: Int): Tree = t match { + case Empty => Empty + case Node(l, d, r) => + if (n < d) Node(delete(l, n), d, r) + else if (n > d) Node(l, d, delete(r, n)) + else if (l == Empty) r + else if (r == Empty) l + else { + val (r1, min) = deleteMin(r) + Node(l, min, r1) + } + } + /* Evaluate the JavaScripty Calculator Language */ + + /* We import `jsy.lab1.ast._` so that we can make use of the Expr type defined + * there. Take a look at ast.scala to see what the Expr type looks like, as well + * some helper functions for defining values (`isValue`) and pretty-printing + * (`pretty`) that you are welcome to use. + */ + import jsy.lab1.ast._ + + def eval(e: Expr): Double = e match { + case N(n) => n + case Unary(Neg, e1) => -eval(e1) + case Binary(Plus, e1, e2) => eval(e1) + eval(e2) + case Binary(Minus, e1, e2) => eval(e1) - eval(e2) + case Binary(Times, e1, e2) => eval(e1) * eval(e2) + case Binary(Div, e1, e2) => eval(e1) / eval(e2) + } + + /* We also overload `eval` to take a String and parse it into an Expr and then + * evaluate it using your `eval` function defined above. + */ + def eval(e: String): Double = eval(Parser.parse(e)) +} diff --git a/lab1/src/main/scala/jsy/lab1/Lab1.worksheet.sc b/lab1/src/main/scala/jsy/lab1/Lab1.worksheet.sc new file mode 100644 index 0000000..a197f9a --- /dev/null +++ b/lab1/src/main/scala/jsy/lab1/Lab1.worksheet.sc @@ -0,0 +1,76 @@ +/* + * CSCI 3155: Lab 1 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab1.scala. + */ + +/* + * Example: Test-driven development of `plus` + */ + +/* Here we can write expressions to experiment with how we might implement + * something. The expression is evaluated interactively. + */ +1 + 1 +val n = 1 + 1 +n + 3 + +/* The worksheet is built with all of the project files, so we can call + * a function from your `jsy.lab1.Lab1` object (in Lab1.scala). + */ +//jsy.lab1.Lab1.plus(3, 4) + +/* We can imports all of the functions from your `jsy.lab1.Lab1` object. */ +import jsy.lab1.Lab1._ +//plus(3, 4) + +/* We can check the implementation here, though it better to write tests + * in Lab1Spec.scala. + */ +//assert(plus(1, 1) == 2) + +/* Braces {} can be used wherever parentheses () can be (but not the other + * way around). Braces {} introduce scope, while () do not. + */ +// assert { +// val two = 2 +// plus(1, 1) == two +// } + +/* Exercises */ + +//assert(repeat("a", 3) == "aaa") + +/* We import jsy.lab.ast._ to use the AST nodes. */ +import jsy.lab1.ast._ + +/* A parser defines how to translate concrete syntax (i.e., strings a programmer types) + * into an abstract syntax tree (AST) that we use to evaluate the program. A parser + * is given to you in jsy.lab1.Parser. You can use the parser to parse a String into + * an Expr. + * + * Here are some shortcuts to that parser for your reference. +* */ +import jsy.lab1.Parser +def parse(s: String): Expr = Parser.parse(s) +def parseFile(filename: String): Expr = Parser.parseFile(filename) + +/* Call the parser (from the provided library) on a string */ +parse("-4") + +val negFourAST = parse("-4") +assert { + negFourAST match { + case Unary(_, _) => true + case _ => false + } +} + +/* Evaluate that `negFourAST` expression. */ +//eval(negFourAST) + +/* For convenience, we also have an overloaded `jsy.lab1.Lab1.eval` function that takes + * a String, calls the parser, and then delegates to your `eval` function. + */ +//eval("1 + 1") diff --git a/lab1/src/main/scala/jsy/lab1/Parser.scala b/lab1/src/main/scala/jsy/lab1/Parser.scala new file mode 100644 index 0000000..b7b8133 --- /dev/null +++ b/lab1/src/main/scala/jsy/lab1/Parser.scala @@ -0,0 +1,153 @@ +package jsy.lab1 + +import jsy.lab1.ast._ +import scala.util.parsing.combinator._ +import scala.util.parsing.input.{StreamReader} +import java.io.{InputStreamReader,FileInputStream} +import java.io.InputStream +import java.io.File +import scala.util.parsing.input.Position +import scala.util.parsing.input.NoPosition + +trait JSTokens extends token.StdTokens { + case class FloatLiteral(chars: String) extends Token { + override def toString = chars + } +} + +class Lexer extends lexical.StdLexical with JSTokens { + override def token: this.Parser[Token] = + decimal ~ opt(exponent) ^^ { + case dec ~ exp => FloatLiteral(List(Some(dec), exp).flatten.mkString) + } | + super.token + + def decimal: this.Parser[String] = + rep1(digit) ~ opt('.' ~ rep(digit)) ^^ { + case ws ~ fs => + List(Some(ws), fs map { mkList }).flatten.flatten.mkString + } + + def exponent: this.Parser[String] = + (accept('e') | accept('E')) ~ opt(accept('+') | accept('-')) ~ rep1(digit) ^^ { + case exp ~ sign ~ digits => + List(Some(List(exp)), sign map { List(_) }, Some(digits)).flatten.flatten.mkString + } +} + + +trait TokenParser extends syntactical.StdTokenParsers { + type Tokens = JSTokens + val lexical = new Lexer + + import lexical.FloatLiteral + + def floatLit: Parser[String] = + elem("float", _.isInstanceOf[FloatLiteral]) ^^ (_.chars) +} + +object Parser extends TokenParser { + /* Lexer Set Up */ + lexical.delimiters ++= List("(", ")", "-", "+", "*", "/") + + def prog: this.Parser[Expr] = expr + + def expr: this.Parser[Expr] = binary(0) + + val binaryOperators: Vector[List[(String, (Expr, Expr) => Expr)]] = { + def createBinaryFunction(op: Bop): (Expr, Expr) => Expr = + { Binary(op, _, _) } + Vector() ++ List( + List("+" -> createBinaryFunction(Plus), + "-" -> createBinaryFunction(Minus)), + List("*" -> createBinaryFunction(Times), + "/" -> createBinaryFunction(Div)) + ) + } + + def binary(level: Int): this.Parser[Expr] = + if (level >= binaryOperators.length) + unary + else + binary(level + 1) * bop(level) + + def bop(level: Int): this.Parser[(Expr, Expr) => Expr] = { + def doBop(opf: (String, (Expr, Expr) => Expr)): this.Parser[(Expr, Expr) => Expr] = { + val (op, f) = opf + withpos(op) ^^ { case (pos, _) => ((e1, e2) => f(e1, e2) setPos pos) } + } + val bopf0 :: bopfrest = binaryOperators(level) + bopfrest.foldLeft(doBop(bopf0)) { (acc, bopf) => acc | doBop(bopf) } + } + + def unary: this.Parser[Expr] = + positioned(uop ~ unary ^^ { case op ~ e => op(e) }) | + term + + def uop: this.Parser[Expr => Expr] = + "-" ^^ (_ => (e: Expr) => Unary(Neg, e)) + + def term: this.Parser[Expr] = + positioned( + floatLit ^^ (s => N(s.toDouble)) + ) | + "(" ~> expr <~ ")" | + failure("expected an expression") + + def withpos[T](q: => this.Parser[T]): this.Parser[(Position, T)] = this.Parser { in => + q(in) match { + case Success(t, in1) => Success((in.pos,t), in1) + case ns: NoSuccess => ns + } + } + + def withposrep[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep(withpos(q)) + + def withposrep1[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep1(withpos(q)) + + private var parseSource: String = "<source>" + + def formatErrorMessage(pos: Position, kind: String, msg: String): String = + if (pos != NoPosition) + "%s\n%s:%s:%s: %s\n%s".format(kind, parseSource, pos.line, pos.column, msg, pos.longString) + else + "%s\n%s: %s".format(kind, parseSource, msg) + + class SyntaxError(msg: String, next: Input) extends Exception { + override def toString = formatErrorMessage(next.pos, "SyntaxError", msg) + } + + def parseTokens(tokens: lexical.Scanner): Expr = { + phrase(prog)(tokens) match { + case Success(e, _) => e + case Error(msg, next) => throw new SyntaxError(msg, next) + case Failure(msg, next) => throw new SyntaxError(msg, next) + } + } + + /*** External Interface ***/ + + def formatErrorMessage(e: Expr, kind: String, msg: String): String = + formatErrorMessage(e.pos, kind, msg) + + def parse(s: String): Expr = { + parseTokens(new lexical.Scanner(s)) + } + + def parse(in: InputStream): Expr = { + val reader = StreamReader(new InputStreamReader(in)) + parseTokens(new lexical.Scanner(reader)) + } + + def parseFile(filename: String): Expr = { + parseSource = filename + parse(new FileInputStream(filename)) + } + + def parseFile(file: File): Expr = { + parseSource = file.getName + parse(new FileInputStream(file)) + } +}
\ No newline at end of file diff --git a/lab1/src/main/scala/jsy/lab1/ast.scala b/lab1/src/main/scala/jsy/lab1/ast.scala new file mode 100644 index 0000000..b82b8b6 --- /dev/null +++ b/lab1/src/main/scala/jsy/lab1/ast.scala @@ -0,0 +1,48 @@ +package jsy.lab1 + +import scala.util.parsing.input.Positional + +/** + * @author Bor-Yuh Evan Chang + */ +object ast { + sealed trait Expr extends Positional // e ::= + + /* Literals */ + case class N(n: Double) extends Expr // n + + /* Unary and Binary Operators */ + case class Unary(uop: Uop, e1: Expr) extends Expr // | uop e1 + case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2 + + sealed trait Uop // uop ::= + case object Neg extends Uop // - + + sealed trait Bop // bop ::= + case object Plus extends Bop // + + case object Minus extends Bop // | - + case object Times extends Bop // | * + case object Div extends Bop // | / + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) => true + case _ => false + } + + /* + * Pretty-print values. + * + * We do not override the toString method so that the abstract syntax can be printed + * as-is. + */ + def pretty(v: Expr): String = { + require(isValue(v)) + (v: @unchecked) match { + case N(n) => prettyNumber(n) + } + } + + def prettyNumber(n: Double): String = + if (n.isWhole) "%.0f" format n else n.toString +}
\ No newline at end of file diff --git a/lab1/src/test/scala/jsy/lab1/Lab1Spec.scala b/lab1/src/test/scala/jsy/lab1/Lab1Spec.scala new file mode 100644 index 0000000..d64c511 --- /dev/null +++ b/lab1/src/test/scala/jsy/lab1/Lab1Spec.scala @@ -0,0 +1,251 @@ +package jsy.lab1 + +import org.scalatest.flatspec.AnyFlatSpec +import jsy.lab1.Parser.parse +import jsy.lab1.ast._ + +/* Import your Lab 1 code. */ +import Lab1._ + +/* + * We use a library called ScalaTest that makes it easy to write + * and run tests. + */ + + /** + * This is an empty test class that you may use to write your own tests. + */ +class Lab1StudentSpec extends AnyFlatSpec { +} + +/** + * Here is a test class with some existing tests for the Lab 1 assignment. + */ +class Lab1Spec extends AnyFlatSpec { + /* + * Example: Test-driven development of plus + * + * Test-driven development means that you first write a test before + * you write the code. This process makes it easier to guide you + * to implement just what you need correctly. + * + * Understandably, this feels overkill for this plus example and + * even for the Lab 1 assignment, but practicing this process now + * will definitely help later. + */ + + /* Define a single test case. The first string categorizes the test. + * By convention, we are using the function name. The second string + * gives an explanation for a test. For more information, go to + * http://scalatest.org/. + */ + + "plus" should "add 1 + 1 == 2" in { + /* Specify assertions here. */ + assert(plus(1, 1) == 2) + } + + it should "add 2 + 2 == 4" in { + /* It is convenient to distinguish the expected result from the code that + * you're testing, which affects the error messages when the test fails. + * + * You can also give an additional clue on test failure by providing an + * additional String argument. + */ + assertResult(2 + 2, "Recall addition.") { + plus(2, 2) + } + } + + /* Exercises */ + + "repeat" should "evaluate to repeated concatenation of a string" in { + assert(repeat("a", 3) == "aaa") + assert(repeat("abc", 3) == "abcabcabc") + assert(repeat("a", 1) == "a") + assert(repeat("abc", 1) == "abc") + assert(repeat("abc", 4) == "abcabcabcabc") + assert(repeat("", 5) == "") + } + + // it says make this test in the same category as the last one + it should "evaluate to an empty string when repeated zero times" in { + assert(repeat("abc", 0) == "") + assert(repeat("", 0) == "") + } + + // Check that repeat requires a non-negative repetition amount + + it should "throw an exception when a negative number of repetitions is expected" in { + intercept[java.lang.IllegalArgumentException] { + repeat("abc", -3) + } + } + + // Check that sqrt works. This requires steps for sqrtStep, sqrtN, and sqrtErr. + + "sqrtStep" should "evaluate to one iteration of Newton's method" in { + assert(sqrtStep(4, 1) == 2.5) + assert(sqrtStep(1, 1) == 1.0) + assert(sqrtStep(5, 8) == 4.3125) + } + + "sqrtN" should "perform several iterations of sqrtStep" in { + assert(sqrtN(4, 1, 2) == 2.05) + assert(sqrtN(4, 1, 6) == 2.0) + assert(sqrtN(4, 20, 2) == 5.248019801980198) + assert(sqrtN(4, 20, 6) == 2.0000105791285385) + } + + it should "evaluate to x0 if n is zero" in { + assert(sqrtN(4, 1, 0) == 1.0) + assert(sqrtN(4, 20, 0) == 20.0) + } + + "sqrtErr" should "perform iterations until the error is within epsilon" in { + assert(sqrtErr(4, 1, 0.1) == 2.000609756097561) + assert(sqrtErr(4, 1, 0.0001) == 2.0000000929222947) + assert(sqrtErr(4, 1, 0.00000001) == 2.000000000000002) + } + + // Make sure that the functions have the correct requires + + "sqrtN" should "throw an exception when n is negative" in { + intercept[java.lang.IllegalArgumentException] { + sqrtN(4, 1, -10) + } + } + + "sqrtErr" should "throw an exception when using a non-positive epsilon" in { + intercept[java.lang.IllegalArgumentException] { + sqrtErr(4, 1, -0.01) + } + intercept[java.lang.IllegalArgumentException] { + sqrtErr(4, 1, 0.0) + } + } + + // Have a few trees pre-made to test against, both valid and invalid + + val t1 = Node(Empty, 2, Empty) + val t2 = Node(t1, 4, Empty) + val t3 = Node(Empty, 4, t2) + val t4 = Node(t1, 4, Node(Empty, 4, Node(Empty, 5, Empty))) + val t5 = Node(Empty, 2, t1) + val t6 = Node(Empty, 4, Empty) + val t7 = Node(Empty, 2, Node(Empty, 4, Empty)) + val t8 = Node(Node(Empty, 1, Empty), 2, Node(Empty, 3, Empty)) + val t9 = Node(Empty, 2, Node(Empty, 3, Empty)) + val t10 = Node(Node(Empty, 1, Empty), 2, Empty) + val t11 = Node(Node(Empty, 1, Empty), 3, Empty) + + "repOk" should "ensure that a Tree is properly ordered" in { + assert(repOk(Empty)) + assert(repOk(t1)) + assert(repOk(t2)) + assert(!repOk(t3)) + assert(repOk(t4)) + assert(repOk(t5)) + } + + "insert" should "insert numbers as leaves in Trees at the proper position" in { + assert(insert(Empty, 2) == t1) + assert(insert(t1, 2) == t5) + assert(insert(t6, 2) == t2) + assert(insert(t1, 4) == t7) + } + + "deleteMin" should "remove the smallest value from a tree, and provide the resulting tree" in { + assert(deleteMin(t7) == (t6, 2)) + assert(deleteMin(t1) == (Empty, 2)) + assert(deleteMin(t5) == (t1, 2)) + assert( + deleteMin(t4) == (Node( + Empty, + 4, + Node(Empty, 4, Node(Empty, 5, Empty)) + ), 2) + ) + } + + "delete" should "remove a given value from a tree, if present" in { + assert(delete(t1, 2) == Empty) + assert(delete(t5, 2) == t1) + assert(delete(t8, 1) == t9) + assert(delete(t8, 3) == t10) + assert(delete(t8, 2) == t11) + assert(delete(t8, 4) == t8) + } + + // Some more testing code that uses the Scala List library. The function 'treeFromList' + // inserts all the elements in the list into the tree. It is likely the code + // will look quite mysterious now. We hope break it down eventually in the + // course, but you can try to figure it out by reading Scala documentation yourself. + // To get started, /: is an operator to corresponds to the 'foldLeft' method on + // lists. + + // Regardless, you can use this function to help test your code. + def treeFromList(l: List[Int]): Tree = l.foldLeft(Empty: Tree)(insert) + + "insert" should "produce trees that satisfy repOk" in { + assert(repOk(treeFromList(List(3, 4, 7, 2, 1, 10)))) + assert(repOk(treeFromList(List(1, 2, 3, 4, 5)))) + assert(repOk(treeFromList(List(9, 8, 7, 6, 5)))) + assert(repOk(treeFromList(List(1, 1, 1, 1)))) + } + + "insert-delete" should "produce trees that satisfy repOk" in { + val ins = (n: Int) => (t: Tree) => insert(t, n) + val del = (n: Int) => (t: Tree) => delete(t, n) + (List( + ins(2), + ins(6), + ins(10), + ins(22), + del(4), + del(6), + ins(4), + del(10), + del(4) + ).foldLeft(Empty: Tree)) { (t, f) => + { + val t1 = f(t) + assert(repOk(t1)) + t1 + } + } + } + + val evalTests = Map( + 1 -> ("1 + 1", 2), + 2 -> ("4 - 2", 2), + 3 -> ("4 * 2", 8), + 4 -> ("4 / 2", 2), + 5 -> ("4 / 0", Double.PositiveInfinity), + 6 -> ("-4 / 0", Double.NegativeInfinity), + 8 -> ("1 + 2 * 3", 7), + 9 -> ("1 + (2 - 3) * 4 / (-5)", 1.8) + ) + + def assertEvalTests(i: Int): Unit = { + val (s, v) = evalTests(i) + val ast = Parser.parse(s) + assertResult(v, s". Note that $s ⇓ $v (i.e., eval($ast) = $v)."){ eval(s) } + } + + /* We list tests individually instead of iterating over them for better IDE integration. */ + + "eval" should "evaluate evalTests(1) correctly" in { assertEvalTests(1) } + it should "evaluate evalTests(2) correctly" in { assertEvalTests(2) } + it should "evaluate evalTests(3) correctly" in { assertEvalTests(3) } + it should "evaluate evalTests(4) correctly" in { assertEvalTests(4) } + it should "evaluate evalTests(5) correctly" in { assertEvalTests(5) } + it should "evaluate evalTests(6) correctly" in { assertEvalTests(6) } + it should "evaluate 0 / 0 correctly" in { assert( eval("0 / 0").isNaN ) } + it should "evaluate evalTests(8) correctly" in { assertEvalTests(8) } + it should "evaluate evalTests(9) correctly" in { assertEvalTests(9) } + + + + +} |