aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:01:58 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:01:58 -0700
commit532be33588fd033fc7f814e725372923cf79a6c4 (patch)
treeaadebd96897ed3c2979a4986b30bbd7df4ddc657
downloadcsci3155-532be33588fd033fc7f814e725372923cf79a6c4.tar.gz
csci3155-532be33588fd033fc7f814e725372923cf79a6c4.zip
Unit 1
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--data-types-exercise.ipynb1633
-rw-r--r--lab1/build.sbt47
-rw-r--r--lab1/inductive-data-types-lab.ipynb825
-rw-r--r--lab1/project/build.properties1
-rw-r--r--lab1/src/main/scala/jsy/lab1/Lab1.scala115
-rw-r--r--lab1/src/main/scala/jsy/lab1/Lab1.worksheet.sc76
-rw-r--r--lab1/src/main/scala/jsy/lab1/Parser.scala153
-rw-r--r--lab1/src/main/scala/jsy/lab1/ast.scala48
-rw-r--r--lab1/src/test/scala/jsy/lab1/Lab1Spec.scala251
9 files changed, 3149 insertions, 0 deletions
diff --git a/data-types-exercise.ipynb b/data-types-exercise.ipynb
new file mode 100644
index 0000000..9ef72b4
--- /dev/null
+++ b/data-types-exercise.ipynb
@@ -0,0 +1,1633 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "3d02434f",
+ "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": 47,
+ "id": "8a89a7aa",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n",
+ "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m"
+ ]
+ },
+ "execution_count": 47,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val NAME = \"Jack Sangdahl\"\n",
+ "val COLLABORATORS = \"N/A\""
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d009c835",
+ "metadata": {},
+ "source": [
+ "---"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "9d34c7c8-c787-4f41-bd3a-5628797aa728",
+ "metadata": {},
+ "source": [
+ "# Exercise: Expressions and Data Types\n",
+ "\n",
+ "<!-- 3 Expressions -->\n",
+ "\n",
+ "<!-- 4 Binding and Scope -->\n",
+ "\n",
+ "The purpose of this assignment is to warm-up with Scala.\n",
+ "\n",
+ "### Learning Goals\n",
+ "\n",
+ "The primary learning goals of this assignment are to build intuition for\n",
+ "the following:\n",
+ "\n",
+ "- thinking in terms of types, values, and expressions; and\n",
+ "- imperative iteration.\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. In Scala, it is also an expression\n",
+ "that throws a `NotImplementedError` exception. Make sure that you remove\n",
+ "the `???` 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",
+ "## Type Checking\n",
+ "\n",
+ "In the following, I have left off the return type of function `g`. The\n",
+ "body of `g` is well-typed if we can come up with a valid return type. In\n",
+ "this question, we will reason for ourselves that `g` is indeed\n",
+ "well-typed."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "id": "0db88593",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m"
+ ]
+ },
+ "execution_count": 48,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def g(x: Int) = /*e1*/({\n",
+ " // env1\n",
+ " val (a, b) = /*e2*/(\n",
+ " // env2\n",
+ " (1, (x, 3))\n",
+ " )\n",
+ " /*e3*/(\n",
+ " // env3\n",
+ " if (x == 0) (b, 1) else (b, a + 2)\n",
+ " )\n",
+ "})"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "27d6ff35-074c-4171-a7f5-a035015e7b83",
+ "metadata": {},
+ "source": [
+ "We have added parentheses around 3 key sub-expressions of the body of\n",
+ "`g` (e.g., `/*e1*/(`$\\ldots$`)`) and noted that there are corresponding\n",
+ "environments (e.g., `// env1` for each sub-expression).\n",
+ "\n",
+ "### Q1.1: What is the type environment `env1`? Briefly explain.\n",
+ "\n",
+ "Use either format shown in the notes (e.g.,\n",
+ "$[ x_1 : \\tau_1, \\ldots, x_n : \\tau_n ]$)."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "672c616d-04fb-41cf-aad5-6f025548b7b7",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "e41ca86f62e024565d1f2956f3950f48",
+ "grade": true,
+ "grade_id": "q1_1",
+ "locked": false,
+ "points": 2,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "The type environment of `env1` alone is $[\\:\\mathtt{env1} \\mapsto\\mathtt{Int}\\:]$. At this point, the only variable in scope is the parameter `x: Int`, so `env1` also maps to `Int`."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d577d0ca-7375-4e10-a89f-6a9f067a8f9f",
+ "metadata": {},
+ "source": [
+ "### Q1.2: What is the type environment `env2`? Briefly explain."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "62ae6788-7ed6-4acd-9d5c-40192d303dc9",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "4660b9558a8195d26712214909a62db2",
+ "grade": true,
+ "grade_id": "q1_2",
+ "locked": false,
+ "points": 2,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "The type environment of `env2` is $[\\:\\mathtt{env2} \\mapsto\\mathtt{Int}\\:]$. `env2` references the known type of `x: Int`, which also maps `env2` to `Int`."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "93547002-40ae-42f1-a910-38131a7d26f6",
+ "metadata": {},
+ "source": [
+ "### Q1.3: Derive the type of expression `e2`.\n",
+ "\n",
+ "Showing the type for each sub-expression of `e2`; stop when you reach\n",
+ "literals or variable uses."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4114c6c1-7098-466c-bf92-69aa4a321664",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "315ba92969984b267763af81ebd0f5d0",
+ "grade": true,
+ "grade_id": "q1_3",
+ "locked": false,
+ "points": 10,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "```scala\n",
+ "(1, (x, 3)): (Int, (Int, Int))\n",
+ "- if 1: Int\n",
+ "- if (x, 3): (Int, Int)\n",
+ " - if x: Int\n",
+ " - if 3: Int\n",
+ "```"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "934b39f4-9eb5-4186-8e8d-f05f24d0f578",
+ "metadata": {},
+ "source": [
+ "#### Notes\n",
+ "\n",
+ "Use the format shown in the notes. Here’s such a derivation for the type\n",
+ "of the expression `(1 + 2) + (3 + 4)`.\n",
+ "\n",
+ "``` scala\n",
+ "(1 + 2) + (3 + 4): Int\n",
+ "- if 1 + 2: Int\n",
+ " - if 1: Int\n",
+ " - if 2: Int\n",
+ "- if 3 + 4: Int\n",
+ " - if 3: Int\n",
+ " - if 4: Int\n",
+ "```\n",
+ "\n",
+ "### Q1.4: What is the type environment `env3`? Briefly explain."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "2e94876a-32b9-477c-9aa1-91253dde0d30",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "e5b9bc3f55c403acbbb1e709d2b68f12",
+ "grade": true,
+ "grade_id": "q1_4",
+ "locked": false,
+ "points": 2,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "The type environment of `env3` alone is $[\\:\\mathtt{env3} \\mapsto\\mathtt{x: Int, a: Int, b: (Int, Int)}\\:]$. At this point, `env3` includes the variables `x`, `a`, and `b`. We know `x: Int` from the function argument, `a: Int` from the tuple deconstruction, and `b: (Int, Int)` also from the tuple deconstruction."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7faf5604-c103-44b1-a711-334dfdab5d6c",
+ "metadata": {},
+ "source": [
+ "### Q1.5: Derive the type of expression `e3`."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ceae2d55-bef9-4cc5-a3dc-cfd11db90e43",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "52869852b70e53b19066a880678a23b7",
+ "grade": true,
+ "grade_id": "q1_5",
+ "locked": false,
+ "points": 2,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "```scala\n",
+ "if (x == 0) (b, 1) else (b, a + 2): ((Int, Int), Int)\n",
+ "- if x == 0: Boolean\n",
+ " - if (b, 1): Int\n",
+ " - if b: Int\n",
+ " - if 1: Int\n",
+ " - if (b, a + 2): Int\n",
+ " - if b: Int\n",
+ " - if a + 2: Int\n",
+ " - if a: Int\n",
+ " - if 2: Int\n",
+ "```"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "bab903c4-188f-46ed-86dd-9495e781ff51",
+ "metadata": {},
+ "source": [
+ "### Q1.6: Confirm your derivations by adding type assertions to each sub-expression of `g` and adding the return type of `g`.\n",
+ "\n",
+ "That is, replace sub-expressions $e$ of `g` with expressions $e$ `:`\n",
+ "$\\tau$. You may need to add some parentheses—`(` $e$ `:` $\\tau$ `)`—to\n",
+ "preserve the syntactic structure. Skip adding typing assertions for\n",
+ "literals and variable uses.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "id": "b472b0a7",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "c4abe7222641b8ec119ec31036e39b95",
+ "grade": true,
+ "grade_id": "q1_6",
+ "locked": false,
+ "points": 9,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mg\u001b[39m"
+ ]
+ },
+ "execution_count": 6,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def g(x: Int) = /*e1*/({\n",
+ " // env1\n",
+ " val (a: Int, b: (Int, Int)) = /*e2*/(\n",
+ " // env2\n",
+ " (1, (x, 3)): (Int, (Int, Int))\n",
+ " )\n",
+ " /*e3*/(\n",
+ " // env3\n",
+ " if (x == 0: Boolean) (b, 1): ((Int, Int), Int) else (b, a + 2): ((Int, Int), Int)\n",
+ " ): ((Int, Int), Int)\n",
+ "}): ((Int, Int), Int) "
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d5e75af2-a72c-4fed-a247-aa90d3f8f0ad",
+ "metadata": {},
+ "source": [
+ "*Hint*: There are 8 sub-expressions that are not literals nor variable\n",
+ "uses that need typing assertions (i.e., $e$ `:` $\\tau$), plus 1 more\n",
+ "annotation for the return type of `g`.\n",
+ "\n",
+ "## Unit Testing\n",
+ "\n",
+ "When starting to program in the large, it is useful to use a testing\n",
+ "framework to manage tests and integrate with IDEs. One that is commonly\n",
+ "used in Scala is [ScalaTest](https://www.scalatest.org/).\n",
+ "\n",
+ "While it is somewhat overkill for testing small exercises like the ones\n",
+ "to come, we practice here writing tests using ScalaTest.\n",
+ "\n",
+ "To load the ScalaTest library, run the following cell:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "id": "8fea5968",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "bdf4aa1ba5caa128e0dbcd6cc1ad5766",
+ "grade": false,
+ "grade_id": "testing",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[32mimport \u001b[39m\u001b[36mRUN this cell FIRST before testing\n",
+ "import $ivy.$ , org.scalatest._, events._, flatspec._\n",
+ "\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
+ ]
+ },
+ "execution_count": 50,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// RUN this cell FIRST before testing\n",
+ "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n",
+ "def report(suite: Suite) = suite.execute(stats = true)\n",
+ "def assertPassed(suite: Suite) =\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 test(suite: Suite) = {\n",
+ " report(suite)\n",
+ " assertPassed(suite)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "67ac4efd-c505-4a4f-a6f5-91610f977849",
+ "metadata": {},
+ "source": [
+ "### Q2.1: Unit Test `plus`\n",
+ "\n",
+ "For this question, **edit the next two code cells** to fix the\n",
+ "implementation of `plus` and add the appropriate assertion for the third\n",
+ "test case `\"add (3,4) == 7\"`.\n",
+ "\n",
+ "Our goal is unit test the following complicated function (that we’ve\n",
+ "gotten wrong!):"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 51,
+ "id": "6bc42853",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mplus\u001b[39m"
+ ]
+ },
+ "execution_count": 51,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def plus(n: Int, m: Int): Int = n + m"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "2fd19eae-bb49-4616-94f4-e2383aad90c9",
+ "metadata": {},
+ "source": [
+ "To use ScalaTest, we create “Spec” objects using ScalaTest methods like\n",
+ "`should` that define an embedded domain-specific language (DSL) for\n",
+ "defining tests:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "id": "1255cbba",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
+ "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mplus\u001b[0m\n",
+ "\u001b[32m- should add 1 + 1 == 2\u001b[0m\n",
+ "\u001b[32m- should add 2 + 2 == 4\u001b[0m\n",
+ "\u001b[32m- should add 3 + 4 == 7\u001b[0m\n",
+ "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mplusSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd52$Helper$$anon$1"
+ ]
+ },
+ "execution_count": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val plusSuite = new AnyFlatSpec {\n",
+ " // Define a *subject* to test (e.g., \"plus\").\n",
+ " // After `should`, name a test (e.g, \"add (1, 1) == 2\").\n",
+ " // After `in`, specify assertions (e.g., `assert(plus(1,1) == 2))\n",
+ " \"plus\" should \"add 1 + 1 == 2\" in {\n",
+ " // Specify assertions here.\n",
+ " assert(plus(1,1) == 2)\n",
+ " }\n",
+ "\n",
+ " it should \"add 2 + 2 == 4\" in {\n",
+ " // It is convenient to distinguish the expected result from the code that\n",
+ " // you're testing, which affects the error messages when the test fails.\n",
+ " assertResult(2 + 2) {\n",
+ " plus(2,2)\n",
+ " }\n",
+ " }\n",
+ " it should \"add 3 + 4 == 7\" in {\n",
+ " assertResult(3 + 4) {\n",
+ " plus(3, 4)\n",
+ " }\n",
+ " }\n",
+ "}\n",
+ "report(plusSuite)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 53,
+ "id": "27368277",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "8ac2636aa17b31fca777bf3064b8d491",
+ "grade": true,
+ "grade_id": "q2_1",
+ "locked": true,
+ "points": 3,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres53\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@48f724de"
+ ]
+ },
+ "execution_count": 53,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "assertPassed(plusSuite)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "be1d876b-25dc-451a-86db-ed1cf1fed54e",
+ "metadata": {},
+ "source": [
+ "## Run-Time Library\n",
+ "\n",
+ "Most languages come with a standard library with support for things like\n",
+ "data structures, mathematical operators, string processing, etc.\n",
+ "Standard library functions may be implemented in the object language\n",
+ "(perhaps for portability) or the meta language (perhaps for\n",
+ "implementation efficiency).\n",
+ "\n",
+ "For this question, we will implement some library functions in Scala,\n",
+ "our meta language, that we can imagine will be part of the run-time for\n",
+ "our object language interpreter. In actuality, the main purpose of this\n",
+ "exercise is to warm-up with Scala programming.\n",
+ "\n",
+ "### Q3.1: Write and test a function `abs`\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "id": "3f001698",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "d1bacc19634bfb1bf864bd58b41906c4",
+ "grade": false,
+ "grade_id": "q3_1_code",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mabs\u001b[39m"
+ ]
+ },
+ "execution_count": 54,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def abs(n: Double): Double = ({\n",
+ " if (n < 0) {\n",
+ " -n\n",
+ " } else {\n",
+ " n\n",
+ " }\n",
+ "})"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "71c5328d-b26d-497d-adaf-6ef22d22688f",
+ "metadata": {},
+ "source": [
+ "that returns the absolute value of `n`. This a function that takes a\n",
+ "value of type `Double` and returns a value of type `Double`. This\n",
+ "function corresponds to the JavaScript library function `Math.abs`.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- Do not use any Scala library functions.\n",
+ "\n",
+ "#### Tests\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 55,
+ "id": "d913e614",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
+ "\u001b[32mcmd55$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mabs\u001b[0m\n",
+ "\u001b[32m- should abs(2) == 2\u001b[0m\n",
+ "\u001b[32m- should abs(-2) == 2\u001b[0m\n",
+ "\u001b[32m- should abs(0) == 0\u001b[0m\n",
+ "\u001b[32m- should abs(1) == 1\u001b[0m\n",
+ "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mabsSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd55$Helper$$anon$1"
+ ]
+ },
+ "execution_count": 55,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val absSuite = new AnyFlatSpec {\n",
+ " \"abs\" should \"abs(2) == 2\" in {\n",
+ " assert(abs(2) == 2)\n",
+ " }\n",
+ " it should \"abs(-2) == 2\" in {\n",
+ " assert(abs(-2) == 2)\n",
+ " }\n",
+ " it should \"abs(0) == 0\" in {\n",
+ " assert(abs(0) === 0)\n",
+ " }\n",
+ " it should \"abs(1) == 1\" in {\n",
+ " assert(abs(1) === 1)\n",
+ " }\n",
+ "}\n",
+ "report(absSuite)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 56,
+ "id": "1956942b",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "8ae14654f39c831149cca3cd7bc9901f",
+ "grade": true,
+ "grade_id": "q3_1",
+ "locked": true,
+ "points": 4,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres56\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@4fd24e85"
+ ]
+ },
+ "execution_count": 56,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "assertPassed(absSuite)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "21898c2c-2b50-42c1-85f9-df4be93e8284",
+ "metadata": {},
+ "source": [
+ "### Q3.2: Write and test a function `xor`\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 57,
+ "id": "3c119212",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "ac179e4aa90d501026fc34ffbf524ab7",
+ "grade": false,
+ "grade_id": "q3_2_code",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mxor\u001b[39m"
+ ]
+ },
+ "execution_count": 57,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def xor(a: Boolean, b: Boolean): Boolean = a ^ b"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5b47755a-a0e7-44ee-acc5-10a06d925697",
+ "metadata": {},
+ "source": [
+ "that returns the exclusive-or of `a` and `b`. The exclusive-or returns\n",
+ "`true` if and only if exactly one of `a` or `b` is `true`.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- For practice, do not use the Boolean operators. Instead, only use\n",
+ " the `if`- expression and the Boolean literals (i.e., `true` or\n",
+ " `false`).\n",
+ "\n",
+ "#### Tests\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 58,
+ "id": "f723c395",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n",
+ "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mxor\u001b[0m\n",
+ "\u001b[32m- should !xor(true, true)\u001b[0m\n",
+ "\u001b[32m- should xor(true, false)\u001b[0m\n",
+ "\u001b[32m- should xor(false, true)\u001b[0m\n",
+ "\u001b[32m- should !xor(false, false)\u001b[0m\n",
+ "\u001b[36mRun completed in 11 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 4\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mxorSuite\u001b[39m: \u001b[32mAnyFlatSpec\u001b[39m = cmd58$Helper$$anon$1"
+ ]
+ },
+ "execution_count": 58,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val xorSuite = new AnyFlatSpec {\n",
+ " \"xor\" should \"!xor(true, true)\" in {\n",
+ " assert(!xor(true, true))\n",
+ " }\n",
+ " it should \"xor(true, false)\" in {\n",
+ " assert(xor(true, false))\n",
+ " }\n",
+ " it should \"xor(false, true)\" in {\n",
+ " assert(xor(false, true))\n",
+ " }\n",
+ " it should \"!xor(false, false)\" in {\n",
+ " assert(!xor(false, false))\n",
+ " }\n",
+ "}\n",
+ "report(xorSuite)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 59,
+ "id": "5fc09530",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "475a7a4bd08579befea92b998fc9a712",
+ "grade": true,
+ "grade_id": "q3_2",
+ "locked": true,
+ "points": 4,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres59\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@2780f927"
+ ]
+ },
+ "execution_count": 59,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "assertPassed(xorSuite)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4b0a894d-67f5-480a-bbcb-2abe33b45784",
+ "metadata": {},
+ "source": [
+ "## Imperative Iteration and Complexity\n",
+ "\n",
+ "### Q4.1: Write a function `filterPairsByBound`\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 60,
+ "id": "a9436132",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "ed640d35faac5ce44926effc28995737",
+ "grade": false,
+ "grade_id": "q4_1_code",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBound\u001b[39m"
+ ]
+ },
+ "execution_count": 60,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def filterPairsByBound(list: List[(Int, Int)], k: Int): List[(Int, Int)] =\n",
+ " list.filter { // iterate through the tuples in list\n",
+ " case (n1, n2) => // for each pair (n1, n2)...\n",
+ " // return appropriate value when leq k \n",
+ " // using our abs() function from Q3.1\n",
+ " abs(n1 - n2) <= k\n",
+ " }"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d95cdad4-4de8-440e-8a25-b1f9d901091a",
+ "metadata": {},
+ "source": [
+ "that given a list of pairs of integers, for example,"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 61,
+ "id": "15116cf9",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36minput1_l\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m(\n",
+ " (\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m),\n",
+ " (\u001b[32m2\u001b[39m, \u001b[32m7\u001b[39m),\n",
+ " (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m),\n",
+ " (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m),\n",
+ " (\u001b[32m14\u001b[39m, \u001b[32m28\u001b[39m),\n",
+ " (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m),\n",
+ " (\u001b[32m35\u001b[39m, \u001b[32m24\u001b[39m)\n",
+ ")"
+ ]
+ },
+ "execution_count": 61,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val input1_l = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "46a2bbe6-ac0c-4fd1-a4e2-15f66b895bf8",
+ "metadata": {},
+ "source": [
+ "output a list consisting of just those pairs $(n_1, n_2)$ in the\n",
+ "original list wherein $|n_1 - n_2| \\leq k$ where $k$ is an integer given\n",
+ "as input. Ensure that the order of the elements in the output list is\n",
+ "the same as that in the input list.\n",
+ "\n",
+ "For the list `input1`, the expected output, with `k == 1`, the expected\n",
+ "output is as follows:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 62,
+ "id": "c378241a",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36minput1_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m1\u001b[39m\n",
+ "\u001b[36moutput1\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))"
+ ]
+ },
+ "execution_count": 62,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val input1_k = 1\n",
+ "val output1 = List( (15,14), (18,19), (0,0) )\n",
+ "assert(filterPairsByBound(input1_l, input1_k) == output1)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "b55b49e4-2a4b-4dc6-80de-c600151fcf5a",
+ "metadata": {},
+ "source": [
+ "With `k == 4`, the expected output is as follows:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 63,
+ "id": "d05fe5b9",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36minput2_k\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m4\u001b[39m\n",
+ "\u001b[36moutput2\u001b[39m: \u001b[32mList\u001b[39m[(\u001b[32mInt\u001b[39m, \u001b[32mInt\u001b[39m)] = \u001b[33mList\u001b[39m((\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m), (\u001b[32m15\u001b[39m, \u001b[32m14\u001b[39m), (\u001b[32m18\u001b[39m, \u001b[32m19\u001b[39m), (\u001b[32m0\u001b[39m, \u001b[32m0\u001b[39m))"
+ ]
+ },
+ "execution_count": 63,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val input2_k = 4\n",
+ "val output2 = List( (1, 5), (15, 14), (18, 19), (0,0) )\n",
+ "assert(filterPairsByBound(input1_l, input2_k) == output2)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "984c452b-5302-48a6-8fe1-e1a1ff22cbaa",
+ "metadata": {},
+ "source": [
+ "#### Notes\n",
+ "\n",
+ "- Your function must be called `filterPairsByBound` with two\n",
+ " arguments: (1) a list of pairs of integers, and (2) the $k$ value.\n",
+ " It must return a list of pairs of integers.\n",
+ "- You can use `for`-loops (or `foreach`) and the following operators\n",
+ " for concatenating elements to a list:\n",
+ " - `:+` appends an element to the back of a list.\n",
+ " - `:::` concatenates two lists together.\n",
+ " - `::` prepends an element to the front of a list.\n",
+ "- You can use the `List` API method `reverse`. You may also use the\n",
+ " `Int` `abs` method to obtain the absolute value of an integer (or\n",
+ " use your `abs` function above).\n",
+ "- You should not use any other `List` API functions including\n",
+ " `filter`, `map`, `foldLeft`, `foldRight`, etc. Plenty of time to\n",
+ " learn them properly later on.\n",
+ "- Do not try to convert your list to an array or vector so that you\n",
+ " can mutate it.\n",
+ "- If you are unable to solve the problem without violating the\n",
+ " restrictions or unsure, ask us.\n",
+ "- You will need to use `var` given the above restrictions.\n",
+ "\n",
+ "#### Hints\n",
+ "\n",
+ "- In Scala, pairs of integers have the type `(Int, Int)`.\n",
+ "- A list containing pairs of integers has the type `List[(Int, Int)]`.\n",
+ "- Recall from the notes, here is how one iterates over the elements of\n",
+ " a list in Scala:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 64,
+ "id": "757f5f83",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1\n",
+ "2\n",
+ "3\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)"
+ ]
+ },
+ "execution_count": 64,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val list = List(1, 2, 3)\n",
+ "\n",
+ "for (elt <- list) {\n",
+ " // do stuff with elt\n",
+ " println(elt)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "e8155fd8-8f76-4131-86e7-3d9bc3f583b4",
+ "metadata": {},
+ "source": [
+ "- Append an element to the end of a list and update a `var`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 65,
+ "id": "d20926f0",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/html": [
+ "<div class=\"jp-RenderedText\">\n",
+ "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n",
+ "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
+ "</div>"
+ ],
+ "text/plain": [
+ "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n",
+ "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "var resultList = List(1, 2, 3)\n",
+ "val elt = 42\n",
+ "\n",
+ "resultList = resultList :+ elt"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5143c58d-3849-4d7c-ad58-7021e92a1a92",
+ "metadata": {},
+ "source": [
+ "- Or, append an element to the end of a list using list concatenation\n",
+ " and update a `var`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 66,
+ "id": "6b76748c",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/html": [
+ "<div class=\"jp-RenderedText\">\n",
+ "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>)\n",
+ "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
+ "</div>"
+ ],
+ "text/plain": [
+ "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m42\u001b[39m)\n",
+ "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "var resultList = List(1, 2, 3)\n",
+ "val elt = 42\n",
+ "\n",
+ "resultList = resultList ::: List(elt)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "0cf8d689-25e9-4899-b369-228fb4a60c06",
+ "metadata": {},
+ "source": [
+ "- Prepend an element and update a `var`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 67,
+ "id": "a223964a",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/html": [
+ "<div class=\"jp-RenderedText\">\n",
+ "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">resultList</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">List</span></span>[<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span>] = <span style=\"color: yellow\"><span class=\"ansi-yellow-fg\">List</span></span>(<span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">1</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">2</span></span>, <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3</span></span>)\n",
+ "<span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">elt</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Int</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">42</span></span></code></pre>\n",
+ "</div>"
+ ],
+ "text/plain": [
+ "\u001b[36mresultList\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m42\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m3\u001b[39m)\n",
+ "\u001b[36melt\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m42\u001b[39m"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "var resultList = List(1, 2, 3)\n",
+ "val elt = 42\n",
+ "\n",
+ "resultList = elt :: resultList"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7cadcb01-c735-4b13-8c34-ed06fefe0e39",
+ "metadata": {},
+ "source": [
+ "- *Warning*: The `:+`, `:::`, or other operations appending operations\n",
+ " take linear $O(n)$ time where $n$ is the length of the (left) list.\n",
+ " Thus, we will often try to avoid using these operations, but it is\n",
+ " ok to use it for this particular part.\n",
+ "\n",
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 68,
+ "id": "40a6d538",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "c9601d100de72d011a23f82aa2e58a37",
+ "grade": true,
+ "grade_id": "q4_1",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n",
+ "\u001b[32mcmd68$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mfilterPairsByBound\u001b[0m\n",
+ "\u001b[32m- should test1\u001b[0m\n",
+ "\u001b[32m- should test2\u001b[0m\n",
+ "\u001b[32m- should test3\u001b[0m\n",
+ "\u001b[32m- should test4\u001b[0m\n",
+ "\u001b[32m- should test5\u001b[0m\n",
+ "\u001b[32m- should test6\u001b[0m\n",
+ "\u001b[36mRun completed in 9 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 6\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres68\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@d75bc07"
+ ]
+ },
+ "execution_count": 68,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " \"filterPairsByBound\" should \"test1\" in {\n",
+ " val lst1 = List((1,1), (-1,1), (1,-1))\n",
+ " assertResult( List((1,1)) ){ filterPairsByBound(lst1,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test2\" in {\n",
+ " val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n",
+ " assertResult( lst2 ){ filterPairsByBound(lst2,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test3\" in {\n",
+ " val lst3 = List((1,5), (5,1))\n",
+ " assertResult( Nil ){ filterPairsByBound(lst3,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test4\" in {\n",
+ " val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n",
+ " assertResult( List((1,2), (-5,-4)) ){ filterPairsByBound(lst4,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test5\" in {\n",
+ " val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n",
+ " assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBound(lst5,4) }\n",
+ " }\n",
+ "\n",
+ " it should \"test6\" in {\n",
+ " val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n",
+ " assertResult( List((1,1)) ){ filterPairsByBound(lst6,0) }\n",
+ " }\n",
+ "})"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5712b57c-1bd3-41a8-9c55-722b85829805",
+ "metadata": {},
+ "source": [
+ "### Q4.2: Write a function `filterPairsByBoundLinearTime`\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 69,
+ "id": "fadb020d",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "8725d2da34598302b7ff7ab5876da03b",
+ "grade": false,
+ "grade_id": "q4_2_code",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterPairsByBoundLinearTime\u001b[39m"
+ ]
+ },
+ "execution_count": 69,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def filterPairsByBoundLinearTime(list: List[(Int, Int)], k: Int): List[(Int, Int)] = {\n",
+ " // helper function to recursively process appropriate elements in list\n",
+ " def filterHelper(remaining: List[(Int, Int)], result: List[(Int, Int)]): List[(Int, Int)] = remaining match {\n",
+ " case Nil => // Nil represents empty set - do nothing\n",
+ " result\n",
+ " // iterate through list beginning at start (or rather current) element\n",
+ " case (n1, n2) :: tail =>\n",
+ " if (abs(n1 - n2) <= k)\n",
+ " // if necessary condition is met, prepend to result\n",
+ " filterHelper(tail, (n1, n2) :: result)\n",
+ " else\n",
+ " // otherwise continue to next element\n",
+ " filterHelper(tail, result)\n",
+ " }\n",
+ " filterHelper(list, Nil).reverse\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "0fa83488-63be-43d5-9905-3f2b4706318d",
+ "metadata": {},
+ "source": [
+ "If you followed the hint and ignored the linear-time warning in the\n",
+ "previous part\n",
+ "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n",
+ "then you would have used the `:+` or `:::` operation to append an\n",
+ "element to the end of a list at each step.\n",
+ "\n",
+ "``` scala\n",
+ "for (... <- list) {\n",
+ " // iterate over a loop\n",
+ " ...\n",
+ " newList = newList :+ newElement // This takes O(length of newList).\n",
+ "}\n",
+ "```\n",
+ "\n",
+ "Each `:+` or `:::` operation requires a full list traversal to find the\n",
+ "end of `newList` and then append to it. The overall algorithm thus\n",
+ "requires $O(n^2)$ time where is the length of the original `list` (also\n",
+ "the number of loop iterations).\n",
+ "\n",
+ "To illustrate, cut-and-paste and then run this code in a new test cell.\n",
+ "Just remember to delete that cell before you submit. It will take a long\n",
+ "time to run.\n",
+ "\n",
+ "``` scala\n",
+ "// Create a list of 1,000,000 pairs\n",
+ "val longTestList = (1 to 1000000).map(x => (x, x - 1)).toList\n",
+ "// Run the function you wrote\n",
+ "filterPairsByBound(longTestList, 1)\n",
+ "// This will take a long time to finish.\n",
+ "```\n",
+ "\n",
+ "In this problem, we wish to implement a function\n",
+ "`filterPairsByBoundLinearTime` that solves the exact same problem as the\n",
+ "previous part\n",
+ "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>\n",
+ "but takes time linear in the size of the input list.\n",
+ "\n",
+ "To do so, we would like you to use the `::` (read “cons”) operator on a\n",
+ "list that prepends an element to the front of a list, instead of `:+` or\n",
+ "`:::` that appends to the back of a list.\n",
+ "\n",
+ "You will want to use the `List` `reverse` API method:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 70,
+ "id": "e3731008",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mlist\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m8\u001b[39m)\n",
+ "\u001b[36mr\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m8\u001b[39m, \u001b[32m7\u001b[39m, \u001b[32m6\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m1\u001b[39m)"
+ ]
+ },
+ "execution_count": 70,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val list = List(1, 2, 5, 6, 7, 8)\n",
+ "val r = list.reverse"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6f9f4725-99b1-41e4-88a5-174ad8818a50",
+ "metadata": {},
+ "source": [
+ "The `r` has the reverse of `list`, and it works in linear time in the\n",
+ "length of `list`.\n",
+ "\n",
+ "The restrictions remain the same as the previous part\n",
+ "<a href=\"#sec-filterPairsByBound\" class=\"quarto-xref\">Section 4.1</a>,\n",
+ "but we would like you to focus on ensuring that your solution runs in\n",
+ "linear time.\n",
+ "\n",
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 71,
+ "id": "90d2d800",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "c1afc073bb37fd79685ece1caf82e854",
+ "grade": true,
+ "grade_id": "q4_2",
+ "locked": true,
+ "points": 7,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 6\u001b[0m\n",
+ "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mfilterPairsByBoundLinearTime\u001b[0m\n",
+ "\u001b[32m- should test1\u001b[0m\n",
+ "\u001b[32m- should test2\u001b[0m\n",
+ "\u001b[32m- should test3\u001b[0m\n",
+ "\u001b[32m- should test4\u001b[0m\n",
+ "\u001b[32m- should test5\u001b[0m\n",
+ "\u001b[32m- should test6\u001b[0m\n",
+ "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 6\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres71\u001b[39m: \u001b[32mStatus\u001b[39m = org.scalatest.CompositeStatus@41a47f32"
+ ]
+ },
+ "execution_count": 71,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " \"filterPairsByBoundLinearTime\" should \"test1\" in {\n",
+ " val lst1 = List((1,1), (-1,1), (1,-1))\n",
+ " assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst1,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test2\" in {\n",
+ " val lst2 = List((1,2), (2,1), (1,0), (0,1), (1,1))\n",
+ " assertResult( lst2 ){ filterPairsByBoundLinearTime(lst2,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test3\" in {\n",
+ " val lst3 = List((1,5), (5,1))\n",
+ " assertResult( Nil ){ filterPairsByBoundLinearTime(lst3,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test4\" in {\n",
+ " val lst4 = List((2,5), (1,2), (-5,-4), (4,1))\n",
+ " assertResult( List((1,2), (-5,-4)) ){ filterPairsByBoundLinearTime(lst4,1) }\n",
+ " }\n",
+ "\n",
+ " it should \"test5\" in {\n",
+ " val lst5 = List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) )\n",
+ " assertResult( List((1, 5), (15, 14), (18, 19), (0,0)) ){ filterPairsByBoundLinearTime(lst5,4) }\n",
+ " }\n",
+ "\n",
+ " it should \"test6\" in {\n",
+ " val lst6 = List((1, 2), (2, 1), (1,0), (0,1), (1,1))\n",
+ " assertResult( List((1,1)) ){ filterPairsByBoundLinearTime(lst6,0) }\n",
+ " }\n",
+ "})"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "9c75c291-9711-4901-92f6-ef093fb92a6a",
+ "metadata": {},
+ "source": [
+ "## Submission\n",
+ "\n",
+ "#### Submission Instructions\n",
+ "\n",
+ "If you are a University of Colorado Boulder student, we use Gradescope\n",
+ "for assignment submission. In summary,\n",
+ "\n",
+ "- [ ] Work on a copy of this Jupyter notebook.\n",
+ "- [ ] Submit it to the corresponding Gradescope assignment entry for\n",
+ " grading.\n",
+ "\n",
+ "#### GitHub and Gradescope\n",
+ "\n",
+ "We use GitHub Classroom for assignment distribution, which gives you a\n",
+ "private GitHub repository to work on your assignment. While using GitHub\n",
+ "is perhaps overkill for this assignment, it does give you the ability to\n",
+ "version and save incremental progress on GitHub (lest your laptop fails)\n",
+ "and makes it easier to get help from the course staff. It will also\n",
+ "become particularly useful when more files are involved, and it is never\n",
+ "too early to get used to the workflow professional software engineers\n",
+ "use with Git.\n",
+ "\n",
+ "To use use GitHub and Gradescope,\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 the copy of this Jupyter notebook from your cloned\n",
+ " repository. Use Git to save versions on GitHub (e.g., `git add`,\n",
+ " `git commit`, `git push` on the command line, via JupyterLab, or via\n",
+ " 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/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) }
+
+
+
+
+}