diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:45 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:45 -0700 |
commit | 0d13c649bdabafde59233609be7bd88e273c7ae6 (patch) | |
tree | 69e3a615f5c3e6a95a752161136acf00c973184d | |
parent | 532be33588fd033fc7f814e725372923cf79a6c4 (diff) | |
download | csci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.tar.gz csci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.zip |
Unit 2
Signed-off-by: Jack Sangdahl <[email protected]>
20 files changed, 4091 insertions, 0 deletions
diff --git a/abstract-syntax-exercise.ipynb b/abstract-syntax-exercise.ipynb new file mode 100644 index 0000000..c8a5be3 --- /dev/null +++ b/abstract-syntax-exercise.ipynb @@ -0,0 +1,1657 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "25085ca3", + "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": 19, + "id": "746e58f4", + "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": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val NAME = \"Jack Sangdahl\"\n", + "val COLLABORATORS = \"N/A\"" + ] + }, + { + "cell_type": "markdown", + "id": "bdb1d285", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "7428aa62-a2f8-45d6-a04d-568bbec79950", + "metadata": {}, + "source": [ + "# Exercise: Syntax\n", + "\n", + "<!-- 3 Expressions -->\n", + "\n", + "<!-- 4 Binding and Scope -->\n", + "\n", + "<!-- 8 Recursion -->\n", + "\n", + "<!-- 9 Inductive Data Types -->\n", + "\n", + "<!-- 11 Concrete Syntax -->\n", + "\n", + "<!-- 12 Abstract Syntax and Parsing -->\n", + "\n", + "<!-- 13 Exercise: Syntax -->\n", + "\n", + "<!-- 14 Static Scoping -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- working with abstract syntax trees;\n", + "- how grammars are used to specify the syntax of programming\n", + " languages; and\n", + "- the distinction between concrete and abstract syntax.\n", + "\n", + "### Instructions\n", + "\n", + "This assignment asks you to write Scala code. There are restrictions\n", + "associated with how you can solve these problems. Please pay careful\n", + "heed to those. If you are unsure, ask the course staff.\n", + "\n", + "Note that `???` indicates that there is a missing function or code\n", + "fragment that needs to be filled in. Make sure that you remove the `???`\n", + "and replace it with the answer.\n", + "\n", + "Use the test cases provided to test your implementations. You are also\n", + "encouraged to write your own test cases to help debug your work.\n", + "However, please delete any extra cells you may have created lest they\n", + "break an autograder.\n", + "\n", + "### Imports" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "id": "0c85487c", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "afc1ca0eb6ddf4e8f942a9b59b4d2e8e", + "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[36mpassed\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m" + ] + }, + "execution_count": 20, + "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): Unit = suite.execute(stats = true)\n", + "def assertPassed(suite: Suite): Unit =\n", + " suite.run(None, Args(new Reporter {\n", + " def apply(e: Event) = e match {\n", + " case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n", + " case _ => ()\n", + " }\n", + " }))\n", + "def passed(points: Int): Unit = {\n", + " require(points >=0)\n", + " if (points == 1) println(\"*** 🎉 Tests Passed (1 point) ***\")\n", + " else println(s\"*** 🎉 Tests Passed ($points points) ***\")\n", + "}\n", + "def test(suite: Suite, points: Int): Unit = {\n", + " report(suite)\n", + " assertPassed(suite)\n", + " passed(points)\n", + "}" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "id": "213c5736", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "3a42711f30a92ef63bef70549eb85bd2", + "grade": false, + "grade_id": "parser", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[32mimport \u001b[39m\u001b[36m$ivy.$\u001b[39m" + ] + }, + "execution_count": 21, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "// Run this cell FIRST before building your parser.\n", + "import $ivy.`org.scala-lang.modules::scala-parser-combinators:2.4.0`" + ] + }, + { + "cell_type": "markdown", + "id": "7e8272a2-d82f-4888-92d0-25fd120fd768", + "metadata": {}, + "source": [ + "## Abstract Syntax Trees\n", + "\n", + "Let us consider the (abstract) syntax of a language of Boolean\n", + "expressions:\n", + "\n", + "$$\\begin{array}{lrrl}\n", + " \\text{Boolean expressions} & e& \\mathrel{::=}& x\n", + " \\mid\\neg e_1\n", + " \\mid e_1 \\wedge e_2\n", + " \\mid e_1 \\vee e_2 \\\\\n", + " \\text{variables} & x\n", + "\\end{array}$$\n", + "\n", + "### Defining an Inductive Data Type\n", + "\n", + "We can write explicitly the above grammar with abstract syntax tree\n", + "nodes:\n", + "\n", + "$$\\begin{array}{rrrl}\n", + "\\text{Boolean expressions $\\texttt{BExpr}$} & e& \\mathrel{::=}&\n", + " \\texttt{Var(} x\\texttt{)} \\\\\n", + " & & \\mid& \\texttt{Not(}e_1\\texttt{)} \\\\\n", + " & & \\mid& \\texttt{And(}e_1\\texttt{,}\\;e_2\\texttt{)} \\\\\n", + " & & \\mid& \\texttt{Or(}e_1\\texttt{,}\\;e_2\\texttt{)} \\\\\n", + "\\end{array}$$\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (5 points)**</span> Define an\n", + "inductive data type `BExpr` in Scala following the above grammar. Use\n", + "the the names given above for the constructors, and use the Scala type\n", + "`String` to represent variable names.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "id": "c17f7690", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4fa8ce605b81e3837cc6f0a5eb8c87c0", + "grade": false, + "grade_id": "bexpr_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mtrait\u001b[39m \u001b[36mBExpr\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mVar\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mNot\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mAnd\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mOr\u001b[39m" + ] + }, + "execution_count": 22, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sealed trait BExpr\n", + "case class Var(x: String) extends BExpr\n", + "case class Not(e: BExpr) extends BExpr\n", + "case class And(e1: BExpr, e2: BExpr) extends BExpr\n", + "case class Or(e1: BExpr, e2: BExpr) extends BExpr" + ] + }, + { + "cell_type": "markdown", + "id": "6bb509ab-c5d2-4069-b322-a4455dc8528b", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "id": "e0b0d389", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "9d5a59b48e6c646390a761b3e2129439", + "grade": true, + "grade_id": "bexpr_tests", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "*** 🎉 Tests Passed (5 points) ***\n" + ] + }, + { + "data": { + "text/plain": [ + "\u001b[36ma\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)\n", + "\u001b[36mb\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m)\n", + "\u001b[36mc\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"C\"\u001b[39m)\n", + "\u001b[36mnot_b\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m))\n", + "\u001b[36mnot_a\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m))\n", + "\u001b[36me1\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m)))\n", + "\u001b[36me2\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)))\n", + "\u001b[36me3\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mOr\u001b[39m(\n", + " e1 = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m))),\n", + " e2 = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)))\n", + ")" + ] + }, + "execution_count": 23, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val a: BExpr = Var(\"A\")\n", + "val b: BExpr = Var(\"B\")\n", + "val c: BExpr = Var(\"C\")\n", + "val not_b: BExpr = Not(b)\n", + "val not_a: BExpr = Not(a)\n", + "val e1: BExpr = And(a,not_b)\n", + "val e2: BExpr = And(b, not_a)\n", + "val e3: BExpr = Or(e1,e2)\n", + "passed(5)" + ] + }, + { + "cell_type": "markdown", + "id": "f1a9c60a-f0d8-4ce7-9de1-e5a9bb0a5cc0", + "metadata": {}, + "source": [ + "### Converting to Negation Normal Form\n", + "\n", + "<span class=\"theorem-title\">**Exercise 2 (10 points)**</span> Write a\n", + "function `nnf` to convert Boolean formulas from the above grammar to\n", + "their Negation Normal Form (NNF). A Boolean formula is said to be in NNF\n", + "iff the negation operator $\\neg$ (i.e., $\\texttt{Not}$) is only applied\n", + "to the variables. For example, the following formula is in NNF because\n", + "negation is only applied to $A$ or $B$, or both of which are variables:\n", + "\n", + "$$\n", + "(A \\wedge \\neg B) \\vee (B \\land \\neg A) \\;.\n", + "$$\n", + "\n", + "On the other hand, the following formula is not in NNF as negation is\n", + "applied to a complex expression:\n", + "\n", + "$$\n", + "\\neg(A \\vee \\neg B) \\wedge (\\neg B \\vee C) \\;.\n", + "$$\n", + "\n", + "The negation normal form of the above formula is as follows:\n", + "\n", + "$$\n", + "(\\neg A \\wedge \\neg B) \\wedge (\\neg B \\vee C) \\;.\n", + "$$\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "id": "1d442d89", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "72a0f6bf19b244521a77d1989ad162d4", + "grade": false, + "grade_id": "nnf_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mnnf\u001b[39m" + ] + }, + "execution_count": 24, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def nnf(e: BExpr): BExpr = e match {\n", + " case Var(_) => e // variable already in nnf\n", + " case Not(Var(x)) => Not(Var(x)) // negated variable in nnf\n", + " case Not(Not(e1)) => nnf(e1) // double negation cancels out\n", + " case Not(And(e1, e2)) => Or(nnf(Not(e1)), nnf(Not(e2))) // apply de morgan law for and\n", + " case Not(Or(e1, e2)) => And(nnf(Not(e1)), nnf(Not(e2))) // apply de morgan law for or\n", + " case And(e1, e2) => And(nnf(e1), nnf(e2)) // recursively convert sub expression nnf\n", + " case Or(e1, e2) => Or(nnf(e1), nnf(e2)) // recursively convert sub expression nnf\n", + " case Not(e1) => Not(nnf(e1)) // handle negation in other cases\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "adb8d1a9-1114-46c5-ac33-7b5269666896", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "In general, a formula can be converted to NNF by applying three rules:\n", + "\n", + "Rule 1 \n", + "Double negation is cancelled: $\\neg(\\neg e) = e$ for any Boolean formula\n", + "$e$.\n", + "\n", + "Rule 2 \n", + "De Morgan’s Law for conjunction:\n", + "$\\neg(e_1 \\wedge e_2) = \\neg e_1 \\vee \\neg e_2$ for any two Boolean\n", + "formulas $e_1$ and $e_2$.\n", + "\n", + "Rule 3 \n", + "De Morgan’s Law for disjunction:\n", + "$\\neg(e_1 \\vee e_2) = \\neg e_1 \\wedge \\neg e_2$ for any two Boolean\n", + "formulas $e_1$ and $e_2$.\n", + "\n", + "The `nnf` function will have a case for each of the above rule. In\n", + "addition, the function will also need to handle the following cases:\n", + "\n", + "- A variable $x$ or its negation $\\neg x$ is already in NNF.\n", + "- An expression $e_1 \\wedge e_2$ is in NNF iff $e_1$ and $e_2$ are in\n", + " NNF.\n", + "- An expression $e_1 \\vee e_2$ is in NNF iff $e_1$ and $e_2$ are in\n", + " NNF.\n", + "- An expression $\\neg e_1$ is in NNF iff $e_1$ is in NNF and none of\n", + " the above 3 rules apply.\n", + "\n", + "If you handle all the 7 cases described above, then your `nnf` function\n", + "will likely be correct, though of course, you will want to test it.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "id": "70af5768", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "388fcf4fd08defa19603710f164045cb", + "grade": true, + "grade_id": "nnf_tests", + "locked": true, + "points": 10, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 7\u001b[0m\n", + "\u001b[32mcmd25$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mnnf\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[32m- should Test Case 2\u001b[0m\n", + "\u001b[32m- should Test Case 3\u001b[0m\n", + "\u001b[32m- should Test Case 4\u001b[0m\n", + "\u001b[32m- should Test Case 5\u001b[0m\n", + "\u001b[32m- should Test Case 6\u001b[0m\n", + "\u001b[32m- should Test Case 7\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 7\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 7, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** 🎉 Tests Passed (10 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val testcase1 = Var(\"A\")\n", + " val testcase2 = Not(Not(Var(\"B\")))\n", + " val testcase3 = And(Var(\"A\"), Or(Var(\"B\"), Var(\"C\")))\n", + " val testcase4 = Or(Var(\"A\"), And(Var(\"B\"), Var(\"C\")))\n", + " val testcase5 = Not(And(Var(\"A\"), Var(\"B\")))\n", + " val testcase6 = Not(Or(Var(\"A\"), Var(\"B\")))\n", + " val testcase7 = Or(And(testcase5,testcase6),testcase2)\n", + "\n", + " \"nnf\" should \"Test Case 1\" in { assertResult( Var(\"A\") ) { nnf(testcase1)} }\n", + " it should \"Test Case 2\" in { assertResult( Var(\"B\") ) { nnf(testcase2) } }\n", + " it should \"Test Case 3\" in { assertResult( And(Var(\"A\"), Or(Var(\"B\"), Var(\"C\"))) ) { nnf(testcase3) } }\n", + " it should \"Test Case 4\" in { assertResult( Or(Var(\"A\"), And(Var(\"B\"), Var(\"C\"))) ) { nnf(testcase4) } }\n", + " it should \"Test Case 5\" in { assertResult( Or(Not(Var(\"A\")), Not(Var(\"B\"))) ) { nnf(testcase5) } }\n", + " it should \"Test Case 6\" in { assertResult( And(Not(Var(\"A\")), Not(Var(\"B\"))) ) { nnf(testcase6) } }\n", + " it should \"Test Case 7\" in { assertResult( Or(And(Or(Not(Var(\"A\")), Not(Var(\"B\"))), And(Not(Var(\"A\")), Not(Var(\"B\")))), Var(\"B\")) ) { nnf(testcase7) } }\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "2e45d4e9-4d1a-474b-a3ae-115bd54edb56", + "metadata": {}, + "source": [ + "### Substitution\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3 (5 points)**</span> Write a\n", + "function `subst` that substitutes *in* a given Boolean expression *with*\n", + "another expression *for* a given variable name. For example,\n", + "substituting in $$\n", + "\\neg(A \\vee B) \\wedge (\\neg B \\vee C)\n", + "$$ with $D$ for $B$ yields $$\n", + "\\neg(A \\vee D) \\wedge (\\neg D \\vee C) \\;.\n", + "$$\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "id": "e4c5dda3", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "1f82f78050d59cbb7dd28d88085f4b63", + "grade": false, + "grade_id": "subst_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36msubst\u001b[39m" + ] + }, + "execution_count": 26, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def subst(in_e: BExpr, with_e: BExpr, for_x: String): BExpr = in_e match {\n", + " case Var(x) if x == for_x => with_e // variable matches? substitute with with_e\n", + " case Var(x) => Var(x) // if variable does not match, leavh unchanged\n", + " case Not(e1) => Not(subst(e1, with_e, for_x)) // recursively apply substitution inside not\n", + " case And(e1, e2) => And(subst(e1, with_e, for_x), subst(e2, with_e, for_x)) // recursively apply substitution inside and\n", + " case Or(e1, e2) => Or(subst(e1, with_e, for_x), subst(e2, with_e, for_x)) // recursively apply substitution inside Or\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "f454f19f-fb7c-4eeb-807f-7c3e39419d67", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 27, + "id": "b2176f6b", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "95cf8b324808d901baa863057040f86a", + "grade": true, + "grade_id": "subst_tests", + "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: 5\u001b[0m\n", + "\u001b[32mcmd27$Helper$$anon$1:\u001b[0m\n", + "\u001b[32m- should Test Case 1\u001b[0m\n", + "\u001b[32m- should Test Case 2\u001b[0m\n", + "\u001b[32m- should Test Case 3\u001b[0m\n", + "\u001b[32m- should Test Case 4\u001b[0m\n", + "\u001b[32m- should Test Case 5\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 5\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 5, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** 🎉 Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val testcase1 = Var(\"A\")\n", + " val testcase2 = Not(Var(\"B\"))\n", + " val testcase3 = Or(Var(\"A\"), Var(\"B\"))\n", + " val testcase4 = And(Not(Var(\"C\")), Or(Var(\"D\"), Var(\"E\")))\n", + " val testcase5 = Or(And(Var(\"X\"), Var(\"Y\")), Or(Var(\"Z\"), Var(\"X\")))\n", + "\n", + " it should \"Test Case 1\" in { assertResult( Var(\"X\") ) { subst(testcase1, Var(\"X\"), \"A\") } }\n", + " it should \"Test Case 2\" in { assertResult( Not(Var(\"Y\")) ) { subst(testcase2, Var(\"Y\"), \"B\") } }\n", + " it should \"Test Case 3\" in { assertResult( Or(Var(\"C\"), Var(\"B\")) ) { subst(testcase3, Var(\"C\"), \"A\") } }\n", + " it should \"Test Case 4\" in { assertResult( And(Not(Var(\"C\")), Or(Var(\"D\"), Var(\"F\"))) ) { subst(testcase4, Var(\"F\"), \"E\") } }\n", + " it should \"Test Case 5\" in { assertResult( Or(And(Var(\"W\"), Var(\"Y\")), Or(Var(\"Z\"), Var(\"W\"))) ) { subst(testcase5, Var(\"W\"), \"X\") } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "258e56f0-791c-487a-9bf5-44c3f5ad5f2b", + "metadata": {}, + "source": [ + "## Concrete Syntax\n", + "\n", + "### Precedence Detective\n", + "\n", + "Consider the Scala binary expressions $$\\begin{array}{rrrl}\n", + " \\text{expressions} & e& \\mathrel{::=}& n\\mid\n", + " e_1 \\mathrel{\\texttt{-}} e_2 \\mid\n", + " e_1 \\mathrel{\\texttt{<<}} e_2 \\\\\n", + " \\text{integers} & n\n", + "\\end{array}$$\n", + "\n", + "<span class=\"theorem-title\">**Exercise 4 (5 points)**</span> Write Scala\n", + "expressions to determine if $\\texttt{-}$ has higher precedence than\n", + "$\\texttt{<<}$ or vice versa. To do, write an expression bound to\n", + "`e_no_parens` that uses no parentheses. Then, bind to `e_higher_-` the\n", + "expression that adds parentheses to the `e_no_parens` expression\n", + "corresponding to the case if $\\texttt{-}$ has higher precedence than\n", + "$\\texttt{<<}$, and bind to `e_higher_<<` the expression adds parentheses\n", + "corresponding to the other case.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 28, + "id": "d8f3bfb9", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "7390f29f3e77d88a7e7062e2075f457f", + "grade": false, + "grade_id": "detective_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36me_no_parens\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m160\u001b[39m\n", + "\u001b[36me_higher_-\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m160\u001b[39m\n", + "\u001b[36me_higher_<<\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-305\u001b[39m" + ] + }, + "execution_count": 28, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val e_no_parens = 15 - 10 << 5\n", + "\n", + "val e_higher_- = (15 - 10) << 5\n", + "\n", + "val e_higher_<< = 15 - (10 << 5)" + ] + }, + { + "cell_type": "markdown", + "id": "5d01deab-3444-4389-a508-267ce2000ae1", + "metadata": {}, + "source": [ + "Make sure that you are checking for precedence and not for left or right\n", + "associativity.\n", + "\n", + "#### Assertions" + ] + }, + { + "cell_type": "code", + "execution_count": 29, + "id": "4ea4f3fa", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "aca8f5794f0463134ecc5a6431a927fc", + "grade": true, + "grade_id": "detective_tests", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "*** 🎉 Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "assert(e_no_parens == e_higher_- || e_no_parens == e_higher_<<)\n", + "assert(e_higher_- != e_higher_<<)\n", + "passed(5)" + ] + }, + { + "cell_type": "markdown", + "id": "e37dcbd3-7a37-40ee-8c38-f5cf4efe04e2", + "metadata": {}, + "source": [ + "#### Explanation\n", + "\n", + "<span class=\"theorem-title\">**Exercise 5 (5 points)**</span> Explain how\n", + "you arrived at the relative precedence of $\\texttt{-}$ and $\\texttt{<<}$\n", + "based on the output that you saw in the Scala interpreter.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "9863319c-1d77-42fd-b2e7-736986916592", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "14b2eda93b7713aad6035f40f587a675", + "grade": true, + "grade_id": "detective_explanation", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "1. `e_no_parens`: When written without parentheses, it is up to Scala interpreter to determine precedence between subtraction and left shift.\n", + "2. `e_higher_-`: This expresion will have parentheses to explicitly show that subtraction has higher precedence than left shift.\n", + "3. `e_higher_<<`: This expression will have parentheses to explicitly show that left shift has high precedence than subtraction." + ] + }, + { + "cell_type": "markdown", + "id": "6b00d249-372d-44df-9c44-aecd94bce0a4", + "metadata": {}, + "source": [ + "## Parse Trees\n", + "\n", + "Consider the following grammar:\n", + "\n", + "<span id=\"eq-ite-grammar\">$$\\begin{array}{rrrl}\n", + " \\text{expressions} & e& \\mathrel{::=}& x\\mid e\\;\\texttt{?}\\;e\\;\\texttt{:}\\;e \\\\\n", + " \\text{variables} & x& \\mathrel{::=}& \\texttt{a} \\mid\\texttt{b}\n", + "\\end{array} \\qquad(1)$$</span>\n", + "\n", + "Consider the following data type for representing parse trees:" + ] + }, + { + "cell_type": "code", + "execution_count": 30, + "id": "e0ff9277", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "0cda8ee79fbaceb83e15d3e0117e877c", + "grade": false, + "grade_id": "parsetree_types", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mtrait\u001b[39m \u001b[36mParseTree\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mLeaf\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m" + ] + }, + "execution_count": 30, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sealed trait ParseTree\n", + "case class Leaf(term: String) extends ParseTree\n", + "case class Node(nonterm: String, children: List[ParseTree]) extends ParseTree" + ] + }, + { + "cell_type": "markdown", + "id": "9b5b444d-6085-494d-8015-cd9f56a46003", + "metadata": {}, + "source": [ + "Observe that a `ParseTree` is just an $n$-ary tree containing `String`s.\n", + "A `Leaf` is a terminal containing the lexemes (i.e., letters from the\n", + "alphabet), while a `Node` is represents a non-terminal with a `String`\n", + "for the name of the non-terminal a list of `children` `ParseTree`s.\n", + "\n", + "For example, the following are `ParseTree`s for this grammar\n", + "(<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>):" + ] + }, + { + "cell_type": "code", + "execution_count": 31, + "id": "aebbb3d1", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "bdee80feebaa951f42684815b22c642d", + "grade": false, + "grade_id": "parsetree_examples", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mp1\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n", + "\u001b[36mp2\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n", + ")" + ] + }, + "execution_count": 31, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val p1 = Node(\"x\", Leaf(\"a\") :: Nil)\n", + "val p2 = Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)" + ] + }, + { + "cell_type": "markdown", + "id": "0df2099c-8f51-4cb1-9ce3-77895f8c7d24", + "metadata": {}, + "source": [ + "We provide a function that pretty-prints a `ParseTree` for *this\n", + "grammar* (<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>)." + ] + }, + { + "cell_type": "code", + "execution_count": 32, + "id": "9c07f06e", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "d45ba978ac101ae4f1409cf49329b416", + "grade": false, + "grade_id": "parsetree_pretty", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mpretty\u001b[39m\n", + "\u001b[36mres32_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a\"\u001b[39m)\n", + "\u001b[36mres32_2\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a\"\u001b[39m)" + ] + }, + "execution_count": 32, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def pretty(t: ParseTree): Option[String] = {\n", + " val alphabet = Set(\"a\", \"b\", \"?\", \":\")\n", + " t match {\n", + " // e ::= x\n", + " case Node(\"e\", (x @ Node(\"x\", _)) :: Nil) => pretty(x)\n", + " // e ::= e ? e : e\n", + " case Node(\"e\", (e1 @ Node(\"e\", _)) :: Leaf(\"?\") :: (e2 @ Node(\"e\", _)) :: Leaf(\":\") :: (e3 @ Node(\"e\", _)) :: Nil) =>\n", + " for { s1 <- pretty(e1); s2 <- pretty(e2); s3 <- pretty(e3) }\n", + " yield s\"$s1 ? $s2 : $s3\"\n", + " // x ::= a\n", + " case Node(\"x\", Leaf(\"a\") :: Nil) => Some(\"a\")\n", + " // x ::= b\n", + " case Node(\"x\", Leaf(\"b\") :: Nil) => Some(\"b\")\n", + " // failure\n", + " case _ => None\n", + " }\n", + "}\n", + "\n", + "pretty(p1)\n", + "pretty(p2)" + ] + }, + { + "cell_type": "markdown", + "id": "825bfb1e-0618-42ff-8ce7-8a99ffafbe82", + "metadata": {}, + "source": [ + "Since it is possible to have `ParseTree`s that are not recognized by\n", + "this grammar, the `pretty` function has return type `Option[String]`.\n", + "Calling `pretty` on `ParseTree`s that are not in this grammar return\n", + "`None`:" + ] + }, + { + "cell_type": "code", + "execution_count": 33, + "id": "f5778462", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4e383bc90701275803c2d59457e1ffdb", + "grade": false, + "grade_id": "parsetree_pretty_none", + "locked": true, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mres33_0\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m\n", + "\u001b[36mres33_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m\n", + "\u001b[36mres33_2\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m" + ] + }, + "execution_count": 33, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "pretty(Leaf(\"a\"))\n", + "pretty(Node(\"x\", Leaf(\"c\") :: Nil))\n", + "pretty(Node(\"y\", Leaf(\"a\") :: Nil))" + ] + }, + { + "cell_type": "markdown", + "id": "f487d822-bbb6-48c4-bdd8-510cb0fbe6a3", + "metadata": {}, + "source": [ + "Note that the `pretty` function makes use of Scala’s `for`-`yield`\n", + "expressions, which you do not need to understand for this exercise.\n", + "\n", + "#### Exercise\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6 (5 points)**</span> Give a\n", + "parse tree for the sentence in the grammar `a ? b : a`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 34, + "id": "e7d3515d", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "f4a6165e9338422805ad7a5697a15209", + "grade": false, + "grade_id": "parse_tree_1_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mparseTree1\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n", + " )\n", + " )\n", + ")" + ] + }, + "execution_count": 34, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val parseTree1: ParseTree =\n", + " Node(\"e\",\n", + " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Leaf(\"?\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n", + " :: Leaf(\":\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Nil\n", + " )" + ] + }, + { + "cell_type": "markdown", + "id": "32bcc28b-473e-4af8-b5a4-125b3e98718c", + "metadata": {}, + "source": [ + "#### Assertion" + ] + }, + { + "cell_type": "code", + "execution_count": 35, + "id": "60cc7566", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "235a3c106ebba2dd23cc05c34da836bf", + "grade": true, + "grade_id": "parsetree_tree_test", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "*** 🎉 Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "assert(pretty(parseTree1) == Some(\"a ? b : a\"))\n", + "passed(5)" + ] + }, + { + "cell_type": "markdown", + "id": "4127541f-87d2-49d5-8bae-045e20feac58", + "metadata": {}, + "source": [ + "#### Exercise\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7 (10 points)**</span> Show that\n", + "this grammar\n", + "(<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>) is\n", + "ambiguous by giving two parse trees for the sentence in the grammar\n", + "`a ? b : a ? b : a`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 36, + "id": "e0c46f00", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "fec8c17457a1f15c9d4eb305bc5193b9", + "grade": false, + "grade_id": "parse_tree_ambiguous_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mparseTree2\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n", + " )\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m)))\n", + " )\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n", + " )\n", + " )\n", + " )\n", + " )\n", + " )\n", + ")\n", + "\u001b[36mparseTree3\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n", + " )\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m)))\n", + " )\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\n", + " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n", + " )\n", + " )\n", + " )\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n", + " ),\n", + " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n", + " \u001b[33mNode\u001b[39m(\n", + " nonterm = \u001b[32m\"e\"\u001b[39m,\n", + " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n", + " )\n", + " )\n", + ")" + ] + }, + "execution_count": 36, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "// a ? b : (a ? b : a)\n", + "val parseTree2: ParseTree =\n", + " Node(\"e\",\n", + " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Leaf(\"?\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n", + " :: Leaf(\":\")\n", + " :: Node(\"e\",\n", + " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Leaf(\"?\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n", + " :: Leaf(\":\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Nil)\n", + " :: Nil\n", + " )\n", + "\n", + "// (a ? b : a) ? b : a\n", + "val parseTree3: ParseTree =\n", + " Node(\"e\",\n", + " Node(\"e\",\n", + " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Leaf(\"?\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n", + " :: Leaf(\":\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Nil)\n", + " :: Leaf(\"?\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n", + " :: Leaf(\":\")\n", + " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n", + " :: Nil\n", + " )" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "id": "789ba753", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "\u001b[36mres37_0\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a ? b : a ? b : a\"\u001b[39m)\n", + "\u001b[36mres37_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a ? b : a ? b : a\"\u001b[39m)" + ] + }, + "execution_count": 37, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "pretty(parseTree2)\n", + "pretty(parseTree3)" + ] + }, + { + "cell_type": "markdown", + "id": "b6096f88-0de5-4826-9599-d9c86f2b365e", + "metadata": {}, + "source": [ + "#### Assertions" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "id": "72197a91", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "1072c2352550ba63657d754309a8a368", + "grade": true, + "grade_id": "parsetree_ambiguous_test_1", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "*** 🎉 Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "assert(parseTree2 != parseTree3)\n", + "assert(pretty(parseTree2).isDefined)\n", + "assert(pretty(parseTree3).isDefined)\n", + "passed(5)" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "id": "084fbb3b", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "1843616ac2befc8ef5c950df69e798aa", + "grade": true, + "grade_id": "parsetree_ambiguous_test_2", + "locked": true, + "points": 5, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "*** 🎉 Tests Passed (5 points) ***\n" + ] + } + ], + "source": [ + "assert(pretty(parseTree2) == Some(\"a ? b : a ? b : a\"))\n", + "assert(pretty(parseTree3) == Some(\"a ? b : a ? b : a\"))\n", + "passed(5)" + ] + }, + { + "cell_type": "markdown", + "id": "558f8a4c-7af1-4eaa-bd10-99dae585dc75", + "metadata": {}, + "source": [ + "## Defining Grammars\n", + "\n", + "In this question, we define a BNF grammar for *floating-point numbers*\n", + "that are made up of a fraction (e.g., `5.6` or `3.123` or `-2.5`)\n", + "followed by an optional exponent (e.g., `E10` or `E-10`).\n", + "\n", + "More precisely for this exercise, our floating-point numbers\n", + "\n", + "- [x] must have a decimal point,\n", + "- [x] do not have leading zeros,\n", + "- [x] can have any number of trailing zeros,\n", + "- [x] non-zero exponents if it exists,\n", + "- [x] must have non-zero fraction to have an exponent, and\n", + "- [x] cannot have a ‘-’ in front of a zero number; also,\n", + "- [x] the exponent cannot have leading zeros.\n", + "\n", + "The exponent, if it exists, is the letter `E` followed by an integer.\n", + "For example, the following are floating-point numbers: `0.0`, `3.5E3`,\n", + "`3.123E30`, `-2.5E2`, `-2.5E-2`, `3.50`, and `3.01E2`.\n", + "\n", + "The following are examples of strings that are *not* floating-point\n", + "numbers by our definition: `0`, `-0.0`, `3.E3`, `E3`, `3.0E4.5`, and\n", + "`4E4`.\n", + "\n", + "For this exercise, let us assume that the tokens are characters in the\n", + "following alphabet $\\Sigma$:\n", + "\n", + "$\\Sigma \\stackrel{\\text{\\tiny def}}{=}\\{$ `0`, `1`, `2`, `3`, `4`, `5`,\n", + "`6`, `7`, `8`, `9`, `E`, `-`, `.` $\\}$\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (10 points)**</span> Translate\n", + "a grammar into a parser `FloatParser.float: Parser[String]` using the\n", + "Scala Parsing Combinator Library that recognizes the language of\n", + "floating-point numbers described above. Since we do not care about the\n", + "correctness of the grammar, we let parse result simply be the input\n", + "string.\n", + "\n", + "We suggest that you first use the scratch cell below to give a grammar\n", + "in BNF notation. Your grammar should be completely defined using the\n", + "alphabet above as the terminals (i.e., it should not count on a\n", + "non-terminal that it does not itself define)." + ] + }, + { + "cell_type": "markdown", + "id": "8c1ba46e-527e-4664-a32f-80e800bbfe7f", + "metadata": {}, + "source": [ + "SCRATCH CELL" + ] + }, + { + "cell_type": "markdown", + "id": "a15d3aab-2045-4565-87bd-46ce02998967", + "metadata": {}, + "source": [ + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "id": "1355139a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "2c18dc9a164093ed57559bc0bee3e557", + "grade": false, + "grade_id": "floatparser_answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mobject\u001b[39m \u001b[36mFloatParser\u001b[39m" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "object FloatParser extends scala.util.parsing.combinator.RegexParsers {\n", + " val concat2: String ~ String => String = { case s1 ~ s2 => s1 + s2 }\n", + " val concat3: String ~ String ~ String => String = { case s1 ~ s2 ~ s3 => s1 + s2 + s3 }\n", + " val concat4: String ~ String ~ String ~ String => String = { case s1 ~ s2 ~ s3 ~ s4 => s1 + s2 + s3 + s4 }\n", + " val concat5: String ~ String ~ String ~ String ~ String => String = { case s1 ~ s2 ~ s3 ~ s4 ~ s5 => s1 + s2 + s3 + s4 + s5 }\n", + "\n", + " def float: Parser[String] =\n", + " fraction ~ exponent ^^ concat2 |\n", + " sign ~ fraction ~ exponent ^^ concat3 |\n", + " fraction |\n", + " success(\"\")\n", + "\n", + " def fraction: Parser[String] =\n", + " anyOneToNine ~ \".\" ~ oneOrMoreDigits ^^ concat3 |\n", + " \"0\" ~ \".\" ~ zeroOrMoreDigits ^^ concat3\n", + "\n", + " def oneOrMoreDigits: Parser[String] =\n", + " digit ~ zeroOrMoreDigits ^^ concat2\n", + "\n", + " def exponent: Parser[String] =\n", + " \"E\" ~ sign ~ anyOneToNine ~ zeroOrMoreDigits ^^ concat4 |\n", + " \"E\" ~ anyOneToNine ~ zeroOrMoreDigits ^^ concat3\n", + " success(\"\")\n", + "\n", + " def zeroOrMoreDigits: Parser[String] =\n", + " digit ~ zeroOrMoreDigits ^^ concat2 |\n", + " success(\"\")\n", + "\n", + " def digit: Parser[String] = \"0\" | anyOneToNine\n", + "\n", + " def anyOneToNine: Parser[String] = \"1\" | \"2\" | \"3\" | \"4\" | \"5\" | \"6\" | \"7\" | \"8\" | \"9\"\n", + "\n", + " def sign: Parser[String] =\n", + " \"-\" |\n", + " success(\"\")\n", + "\n", + " def parse(str: String): Option[String] = parseAll(float, str) match {\n", + " case Success(str, _) => Some(str)\n", + " case Failure(_, _) | Error(_, _) => None\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "327ebd79-bbe0-4763-a6c4-b71a860f3a3a", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- The `success[A](a: A): Parser[A]` method corresponds to an\n", + " $\\varepsilon$ production in BNF. It returns a parser that is\n", + " successful without consuming any input yielding the parse result\n", + " `a`. If you use it in your parser, make sure it is the *last*\n", + " production for the non-terminal.\n", + "- We provide some helper functions\n", + " `concat2: String ~ String => String`,\n", + " `concat3: String ~ String ~ String => String`, etc. that simply\n", + " concatenate their input strings together. These helper functions are\n", + " the only semantic actions you need.\n", + "- We have provided some basic parsers `sign`, `anyOneToNine`, `digit`,\n", + " `zeroOrMoreDigits` that you may use if you like.\n", + "- You may edit the `parse` interface function that we have provided to\n", + " start from a different non-terminal while you’re developing, but\n", + " make sure it is `float` in the end and that your starting\n", + " non-terminal is `float`. Alternatively, you may add additional such\n", + " interface functions with a different name for your testing.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "id": "b1824177", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "66ebc679977f9e9d6d9450c594637910", + "grade": true, + "grade_id": "floatparser_tests", + "locked": true, + "points": 10, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 13\u001b[0m\n", + "\u001b[32mcmd41$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mFloatParser\u001b[0m\n", + "\u001b[32m- should parse 0.0\u001b[0m\n", + "\u001b[32m- should parse 3.5E3\u001b[0m\n", + "\u001b[32m- should parse 3.123E30\u001b[0m\n", + "\u001b[32m- should parse -2.5E2\u001b[0m\n", + "\u001b[32m- should parse -2.5E-2\u001b[0m\n", + "\u001b[32m- should parse 3.50\u001b[0m\n", + "\u001b[32m- should parse 3.01E2\u001b[0m\n", + "\u001b[32m- should fail to parse 0\u001b[0m\n", + "\u001b[32m- should fail to parse -0.0\u001b[0m\n", + "\u001b[32m- should fail to parse 3.E3\u001b[0m\n", + "\u001b[32m- should fail to parse E3\u001b[0m\n", + "\u001b[32m- should fail to parse 3.0E4.5\u001b[0m\n", + "\u001b[32m- should fail to parse 4E4\u001b[0m\n", + "\u001b[36mRun completed in 15 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 13\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 13, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** 🎉 Tests Passed (10 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val tests_positive = List(\n", + " \"0.0\",\n", + " \"3.5E3\",\n", + " \"3.123E30\",\n", + " \"-2.5E2\",\n", + " \"-2.5E-2\",\n", + " \"3.50\",\n", + " \"3.01E2\"\n", + " )\n", + "\n", + " behavior of \"FloatParser\"\n", + "\n", + " for (t <- tests_positive) {\n", + " it should s\"parse $t\" in {\n", + " assertResult( Some(t) ) {\n", + " FloatParser.parse(t)\n", + " }\n", + " }\n", + " }\n", + "\n", + " val tests_negative = List(\n", + " \"0\",\n", + " \"-0.0\",\n", + " \"3.E3\",\n", + " \"E3\",\n", + " \"3.0E4.5\",\n", + " \"4E4\"\n", + " )\n", + "\n", + " for (t <- tests_negative) {\n", + " it should s\"fail to parse $t\" in {\n", + " assertResult( None ) {\n", + " FloatParser.parse(t)\n", + " }\n", + " }\n", + " }\n", + "}, 10)" + ] + } + ], + "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/lab2/build.sbt b/lab2/build.sbt new file mode 100644 index 0000000..84ff83a --- /dev/null +++ b/lab2/build.sbt @@ -0,0 +1,47 @@ +name := "pppl-lab2" + +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/lab2/project/build.properties b/lab2/project/build.properties new file mode 100644 index 0000000..ee4c672 --- /dev/null +++ b/lab2/project/build.properties @@ -0,0 +1 @@ +sbt.version=1.10.1 diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.scala b/lab2/src/main/scala/jsy/lab2/Lab2.scala new file mode 100644 index 0000000..5788d74 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.scala @@ -0,0 +1,150 @@ +package jsy.lab2 + +object Lab2 extends jsy.util.JsyApplication { + import ast._ + /* + * CSCI 3155: Lab 2 + * Jack Sangdahl + */ + + def toNumber(v: Expr): Double = { + require(isValue(v)) + (v: @unchecked) match { + case N(n) => n + case B(b) => if (b) 1.0 else 0.0 + case S(s) => try { s.toDouble} catch { case _: NumberFormatException => Double.NaN } + case Undefined => Double.NaN + } + } + + def toBoolean(v: Expr): Boolean = { + require(isValue(v)) + (v: @unchecked) match { + case B(b) => b + case N(n) => n != 0 && !n.isNaN + case S(s) => s.nonEmpty + case Undefined => false + } + } + + def toStr(v: Expr): String = { + require(isValue(v)) + (v: @unchecked) match { + case S(s) => s + case N(n) => n.toString + case B(b) => b.toString + case Undefined => "undefined" + } + } + + /* We represent a variable environment as a map from a string of the + * variable name to the value to which it is bound. + * + * You may use the following provided helper functions to manipulate + * environments, which are just thin wrappers around the Map type + * in the Scala standard library. You can use the Scala standard + * library directly, but these are the only interfaces that you + * need. + */ + type Env = Map[String, Expr] + val empty: Env = Map() + def lookup(env: Env, x: String): Expr = env(x) + def extend(env: Env, x: String, v: Expr): Env = { + require(isValue(v)) + env + (x -> v) + } + + def eval(env: Env, e: Expr): Expr = { + e match { + // literals + case N(n) => N(n) + case B(b) => B(b) + case S(s) => S(s) + case Undefined => Undefined + + // unary ops + case Unary(Neg, e1) => N(-toNumber(eval(env, e1))) + case Unary(Not, e1) => B(!toBoolean(eval(env, e1))) + + // binary ops + case Binary(Plus, e1, e2) => N(toNumber(eval(env, e1)) + toNumber(eval(env, e2))) + case Binary(Minus, e1, e2) => N(toNumber(eval(env, e1)) - toNumber(eval(env, e2))) + case Binary(Times, e1, e2) => N(toNumber(eval(env, e1)) * toNumber(eval(env, e2))) + case Binary(Div, e1, e2) => N(toNumber(eval(env, e1)) / toNumber(eval(env, e2))) + + case Binary(And, e1, e2) => eval(env, e1) match { + case B(b1) if !b1 => B(false) + case N(n1) if n1 == 0 => N(0) + case Undefined => eval(env, e1) + case _ => eval(env, e2) + } + case Binary(Or, e1, e2) => eval(env, e1) match { + case B(b1) if b1 => B(true) + case N(n1) if n1 != 0 => N(n1) + case Undefined => eval(env, e2) + case _ => eval(env, e2) + } + + case Binary(Eq, e1, e2) => (eval(env, e1), eval(env, e2)) match { + case (N(n1), N(n2)) => B(n1 == n2) + case (B(b1), B(b2)) => B(b1 == b2) + case (S(s1), S(s2)) => B(s1 == s2) + case (Undefined, Undefined) => B(true) + case (Undefined, _) => B(false) + case (_, Undefined) => B(false) + case _ => B(false) + } + case Binary(Ne, e1, e2) => B(toNumber(eval(env, e1)) != toNumber(eval(env, e2))) + + case Binary(Lt, e1, e2) => B(toNumber(eval(env, e1)) < toNumber(eval(env, e2))) + case Binary(Le, e1, e2) => B(toNumber(eval(env, e1)) <= toNumber(eval(env, e2))) + case Binary(Gt, e1, e2) => B(toNumber(eval(env, e1)) > toNumber(eval(env, e2))) + case Binary(Ge, e1, e2) => B(toNumber(eval(env, e1)) >= toNumber(eval(env, e2))) + + case Binary(Seq, e1, e2) => + eval(env, e1) + eval(env, e2) + + case If(e1, e2, e3) => + if (toBoolean(eval(env, e1))) eval(env, e2) else eval(env, e3) + + case ConstDecl(x, e1, e2) => + val v1 = eval(env, e1) + eval(env + (x -> v1), e2) + + case Print(e1) => println(pretty(eval(env, e1))); Undefined + case Var(x) => env.getOrElse(x, throw new RuntimeException(s"Variable $x not found")) + } + } + + /* Interface to run your interpreter starting from an empty environment. This is convenient for unit testing. */ + def eval(e: Expr): Expr = { + require(closed(e)) + eval(empty, e) + } + + /* Interface to run your interpreter from a string. This is convenient for unit testing. */ + def eval(s: String): Expr = eval(Parser.parse(s)) + + // You may set this debug flag to true to get the debugging output below, but you need to turn it off to pass test cases. + // debug = true + + /* Interface to run your interpreter on an input file. This is for file-based integration tests (see Lab2JsyTests in Lab2Spec.scala). */ + def processFile(file: java.io.File): Unit = { + + if (debug) { println("Parsing ...") } + + val expr = Parser.parseFile(file) + + if (debug) { + println("\nExpression AST:\n " + expr) + println("------------------------------------------------------------") + } + + if (debug) { println("Evaluating ...") } + + val v = eval(expr) + + println(pretty(v)) + } +} diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js new file mode 100644 index 0000000..5a1cb50 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js @@ -0,0 +1,21 @@ +/* + * CSCI 3155: Lab 2 JavaScript Worksheet + * + * This worksheet is a place to experiment with JavaScript expressions. + */ + +const five = 5; + +five + "five"; + +console.log(five), console.log("five"); + +undefined - true; + +10 * false; + +10 * undefined; + +console.log(undefined ? "then" : "else"); + +console.log("" ? "then" : "else");
\ No newline at end of file diff --git a/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc new file mode 100644 index 0000000..3b401ee --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc @@ -0,0 +1,34 @@ +/* + * CSCI 3155: Lab 2 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab2.scala. + */ + +// Imports the parse and parseFile functions +import jsy.lab2.Parser.{parse, parseFile} + +// Imports the ast nodes +import jsy.lab2.ast._ + +// Imports all of the functions from your implementation +import jsy.lab2.Lab2._ + +// Call the JavaScripty parser (from the provided library) on a string +val negFourAST = parse("-4") + +// Construct an AST directly +val negFiveAST: Expr = Unary(Neg, N(5.0)) + +// Evaluate that JavaScripty expression. +//eval(negFourAST) + +// For convenience, we also have an eval function that takes a string, +// which calls the parser and then delegates to your eval function. +//eval("undefined + 1") + +// Parse the JavaScripty expression in your worksheet +val worksheetJsy = parseFile("src/main/scala/jsy/lab2/Lab2.worksheet.js") + +// Eval the JavaScripty expression in your worksheet +//eval(worksheetJsy)
\ No newline at end of file diff --git a/lab2/src/main/scala/jsy/lab2/Parser.scala b/lab2/src/main/scala/jsy/lab2/Parser.scala new file mode 100644 index 0000000..b4cf478 --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/Parser.scala @@ -0,0 +1,255 @@ +/** + * + */ +package jsy.lab2 + +import jsy.lab2.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: this.Parser[String] = + elem("float", _.isInstanceOf[FloatLiteral]) ^^ (_.chars) +} + +object Parser extends TokenParser { + /* Lexer Set Up */ + lexical.reserved ++= List("jsy", "undefined", "true", "false", "print", "console", "log", "const", "function", "return", "number", "bool", "string", "Undefined", "null", "Null", "interface", "var", "name", "ref", "RegExp") + lexical.delimiters ++= List("-", "!", ";", ",", "+", "*", "/", "=", "===", "!==", "<", "<=", ">", ">=", "&&", "||", "(", ")", ".", "{", "}", "?", ":", "=>") + + /* Helpers */ + def seqExpr(e1: Expr, e2: Expr): Expr = Binary(Seq, e1, e2) + + /* EBNF + * + * prog ::= {stmt} + * stmt ::= block | decl | ; | expr + * block ::= '{' prog '}' + * decl ::= const x = expr + * expr ::= seq + * seq ::= cond{,cond} + * cond ::= binary [? cond : cond] + * binary ::= unary{bop(_)unary} + * unary ::= uop unary | term + * term ::= x | n | b | undefined | jsy.print(expr) | (expr) + */ + + sealed abstract class PStmt + case class ExprPStmt(e: Expr) extends PStmt + case class DeclPStmt(d: Expr => Expr) extends PStmt + case object EmpPStmt extends PStmt + + def prog: this.Parser[Expr] = + stmts ^^ (s => s(None)) + + def stmts: this.Parser[Option[Expr] => Expr] = + rep(stmt) ^^ { (stmts: List[PStmt]) => (body: Option[Expr]) => + (stmts foldRight body){ + case (EmpPStmt, eopt) => eopt + case (ExprPStmt(e), None) => Some(e) + case (ExprPStmt(e1), Some(e2)) => Some(seqExpr(e1, e2)) + case (DeclPStmt(d), None) => Some(d(Undefined)) + case (DeclPStmt(d), Some(e)) => Some(d(e)) + } match { + case None => Undefined + case Some(e) => e + } + } + + def stmt: this.Parser[PStmt] = + block ^^ ExprPStmt | + decl ^^ DeclPStmt | + expr ^^ ExprPStmt | + empty_stmt + + def empty_stmt: this.Parser[PStmt] = + ";" ^^ (_ => EmpPStmt) + + def block: this.Parser[Expr] = + "{" ~> prog <~ "}" + + def decl: this.Parser[Expr => Expr] = + ("const" ~> ident) ~ withpos("=" ~> expr) ^^ { + case x ~ ((pos,e1)) => ((e2: Expr) => ConstDecl(x, e1, e2) setPos pos) + } + + def expr: this.Parser[Expr] = + seq + + def seq: this.Parser[Expr] = + noseq ~ withposrep("," ~> noseq) ^^ { + case e0 ~ es => + (es foldRight (None: Option[(Position,Expr)])){ + case ((posi,ei), None) => Some(posi,ei) + case ((posi,ei), Some((pos,e))) => Some(posi, seqExpr(ei,e) setPos pos) + } match { + case None => e0 + case Some((pos,e)) => seqExpr(e0, e) setPos pos + } + } + + def noseq: this.Parser[Expr] = + cond + + def cond: this.Parser[Expr] = + binary(0) ~ opt(withpos(("?" ~> noseq) ~ (":" ~> noseq))) ^^ { + case e1 ~ None => e1 + case e1 ~ Some((pos, e2 ~ e3)) => If(e1, e2, e3) setPos pos + } + + val binaryOperators: Vector[List[(String, (Expr, Expr) => Expr)]] = { + def createBinaryFunction(op: Bop): (Expr, Expr) => Expr = + { Binary(op, _, _) } + Vector() ++ List( + List("||" -> createBinaryFunction(Or)), + List("&&" -> createBinaryFunction(And)), + List("===" -> createBinaryFunction(Eq), + "!==" -> createBinaryFunction(Ne)), + List("<" -> createBinaryFunction(Lt), + "<=" -> createBinaryFunction(Le), + ">" -> createBinaryFunction(Gt), + ">=" -> createBinaryFunction(Ge)), + 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)) | + "!" ^^ (_ => (e: Expr) => Unary(Not, e)) + + def term: this.Parser[Expr] = + positioned( + ident ^^ (s => Var(s)) | + floatLit ^^ (s => N(s.toDouble)) | + stringLit ^^ (s => S(s)) | + "true" ^^ (_ => B(true)) | + "false" ^^ (_ => B(false)) | + "undefined" ^^ (_ => Undefined) | + ("jsy" ~ "." ~ "print") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) | + ("console" ~ "." ~ "log") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) + ) | + "(" ~> expr <~ ")" | + "{" ~> "{" ~> prog <~ "}" <~ "}" | + failure("atomic expression expected") + + 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 NoSuccess(msg, next) => throw new SyntaxError(msg, next) + 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)) + } + + implicit class StringExpr(s: String) { + val e = parse(s) + def a: Expr = e + } +} diff --git a/lab2/src/main/scala/jsy/lab2/ast.scala b/lab2/src/main/scala/jsy/lab2/ast.scala new file mode 100644 index 0000000..7c8fb5e --- /dev/null +++ b/lab2/src/main/scala/jsy/lab2/ast.scala @@ -0,0 +1,92 @@ +package jsy.lab2 + +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 // e ::= n + case class B(b: Boolean) extends Expr // e ::= b + case class S(str: String) extends Expr // e ::= str + case object Undefined extends Expr // e ::= undefined + + /* Unary and Binary Expressions */ + case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1 + case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop e2 + + sealed trait Uop // uop ::= + sealed trait Bop // bop ::= + + /* Numbers */ + case object Neg extends Uop // uop ::= - + + case object Plus extends Bop // bop ::= + + case object Minus extends Bop // bop ::= - + case object Times extends Bop // bop ::= * + case object Div extends Bop // bop ::= / + + /* Booleans */ + case object Not extends Uop // uop ::= ! + case object And extends Bop // bop ::= && + case object Or extends Bop // bop ::= || + + case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3 + + case object Eq extends Bop // bop ::= === + case object Ne extends Bop // bop ::= !== + case object Lt extends Bop // bop ::= < + case object Le extends Bop // bop ::= <= + case object Gt extends Bop // bop ::= > + case object Ge extends Bop // bop ::= >= + + /* Side-Effects */ + case class Print(e1: Expr) extends Expr // e ::= console.log(e1) + case object Seq extends Bop // bop ::= , + + /* Variables */ + case class Var(x: String) extends Expr // e ::= x + case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2 + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) | B(_) | S(_) | Undefined => 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) + case B(b) => b.toString + case S(str) => str + case Undefined => "undefined" + } + } + + def prettyNumber(n: Double): String = + if (n.isWhole) "%.0f" format n else n.toString + + /* Get the free variables of e. */ + def freeVars(e: Expr): Set[String] = e match { + case Var(x) => Set(x) + case ConstDecl(x, e1, e2) => freeVars(e1) | (freeVars(e2) - x) + case N(_) | B(_) | Undefined | S(_) => Set.empty + case Unary(_, e1) => freeVars(e1) + case Binary(_, e1, e2) => freeVars(e1) | freeVars(e2) + case If(e1, e2, e3) => freeVars(e1) | freeVars(e2) | freeVars(e3) + case Print(e1) => freeVars(e1) + } + + /* Check closed expressions. */ + def closed(e: Expr): Boolean = freeVars(e).isEmpty +} diff --git a/lab2/src/main/scala/jsy/util/JsyApplication.scala b/lab2/src/main/scala/jsy/util/JsyApplication.scala new file mode 100644 index 0000000..46b658d --- /dev/null +++ b/lab2/src/main/scala/jsy/util/JsyApplication.scala @@ -0,0 +1,191 @@ +package jsy.util + +import java.io.{ByteArrayOutputStream, File} +import java.nio.file.Files + +trait JsyApplication { + var debug = false /* set to false to disable debugging output */ + var keepGoing = true /* set to true to keep going after exceptions */ + var maxSteps: Option[Int] = None /* set to a number to bound the number of execution steps */ + + /*** Implement this method to process a file. ***/ + def processFile(file: File): Unit + + var anonOption = ("input", + { case filename :: Nil => new File(filename) }: PartialFunction[List[String], File], + "A file containing a JavaScripty program or a directory with .jsy files.") + + var flagOptions = List( + ("debug", options.SetBool(b => debug = b, Some(b => debug == b)), "debugging"), + ("keep-going", options.SetBool(b => keepGoing = b, Some(b => keepGoing == b)), "keep going after exceptions"), + ("bound-steps", options.SetInt( + { i => maxSteps = i }, + Some({ + case true => maxSteps map { i => ": %d".format(i) } + case false => if (maxSteps == None) Some("") else None + })), + "bound for maximum number of execution steps before aborting") + ) + + def handle[T](default: T)(e: => T): T = + if (!keepGoing) e + else try e catch { + case exn: Throwable => println(exn.toString); default + } + + def testJsy(file: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + val jsyext = """[.]jsy$""".r + val ans: File = new File(jsyext.replaceAllIn(file.getPath, ".ans")) + k(file, ans, { + if (!ans.exists()) { + (false, s"Expected output file ${ans} does not exist.") + } + else { + val outstream = new ByteArrayOutputStream() + Console.withOut(outstream)(handle(()){ processFile(file)}) + + val encoding = java.nio.charset.StandardCharsets.UTF_8 + val ansstring = new String(Files.readAllBytes(ans.toPath), encoding) + + outstream.flush() + val outstring = new String(outstream.toString(encoding.toString)) + outstream.close() + + (ansstring == outstring, s"Computed output does not match expected output.\nComputed:\n${outstring}\nExpected:\n${ansstring}") + } + }) + } + + def isJsy(file: File): Boolean = { + val jsyext = """[.]jsy$""".r + jsyext findFirstIn file.getName match { + case Some(_) => true + case None => false + } + } + + def doFile(doit: File => Unit, file: File) = { + def loop(file: File): Unit = { + if (file.isFile) { + doit(file) + } + else if (file.isDirectory) { + file.listFiles filter { f => f.isDirectory || isJsy(f) } foreach loop + } + else { + throw new IllegalArgumentException("File %s does not exist.".format(file)) + } + } + loop(file) + } + + def test(fileordir: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + doFile({ f => testJsy(f)(k) }, fileordir) + } + + def main(args: Array[String]): Unit = { + val opts = new options.Options("jsy", flagOptions, anonOption) + val file: File = opts.process(args) + doFile(processFile, file) + } +} + +object options { + sealed abstract class Spec + case class SetBool(setter: Boolean => Unit, default: Option[Boolean => Boolean]) extends Spec + case class SetInt(setter: Option[Int] => Unit, default: Option[Boolean => Option[String]]) extends Spec + + class Options[T](program: String, specs: List[(String, Spec, String)], anon: (String, PartialFunction[List[String], T], String)) { + val opts: Map[String, List[String] => Option[List[String]]] = + specs.foldLeft[Map[String, List[String] => Option[List[String]]]](Map.empty)((acc, spec) => spec match { + case (name, SetBool(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => setter(true); Some(t) }) + + (("--no-" + name) -> { (t: List[String]) => setter(false); Some(t) }) + case (name, SetInt(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => t match { + case arg :: t => + val argp: Int = try arg.toInt catch { case _: Throwable => usageErr() } + setter(Some(argp)); Some(t) + case _ => usageErr() + } }) + + (("--no-" + name) -> { (t: List[String]) => setter(None); Some(t) }) + }) + + val (anonName, anonDo, anonDesc) = anon + + val nameWidth: Int = opts.foldLeft(anonName.length){ case (acc, (n, _)) => acc max (n.length + 5) } + + def padRight(s: String, w: Int): String = { + val nspaces = (w - s.length) max 0 + s + (" " * nspaces) + } + + def optline(name: String, text: String): String = { + "%-2s".format("") + padRight(name, nameWidth) + " %s%n".format(text) + } + + val descriptions: String = { + (specs foldRight "")((spec, acc) => spec match { + case (name, SetBool(_, default), desc) => { + def defaultStr(b: Boolean): String = + default map (f => if (f(b)) " (default)" else "") getOrElse("") + optline("--" + name, "turn on %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "turn off %s".format(desc) + defaultStr(false)) + + acc + } + case (name, SetInt(_, default), desc) => { + def defaultStr(b: Boolean): String = { + val opt = + for { + f <- default + s <- f(b) + } yield " (default%s)".format(s) + opt.getOrElse("") + } + optline("--" + name + " <int>", "set %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "unset %s".format(desc) + defaultStr(false)) + + acc + } + }) + } + + val header = + """ +Usage: %s [options] %s + +""".format(program, anonName) + +optline(anonName, anonDesc) + """ +Options: +""" + + private var currentArgs: List[String] = List() + + def usageErr(): Nothing = { + val unprocessed = currentArgs match { + case Nil => "" + case _ => """ +Unprocessed Arguments: + """ + currentArgs.reduceRight({ _ + " " + _ }) + "%n".format() + } + print(header + descriptions + unprocessed) + sys.exit(1) + } + + def process(args: Array[String]): T = { + def loop(l: List[String]): List[String] = { + currentArgs = l + l match { + case Nil => Nil + case h :: t => opts.get(h) match { + case None => l + case Some(doit) => { val tp = doit(t).getOrElse(t); loop(tp) } + } + } + } + val err: PartialFunction[List[String], T] = { case _ => usageErr() } + (anonDo orElse err)(loop(args.toList)) + } + } +}
\ No newline at end of file diff --git a/lab2/src/test/resources/lab2/test2001_boolean.ans b/lab2/src/test/resources/lab2/test2001_boolean.ans new file mode 100644 index 0000000..27ba77d --- /dev/null +++ b/lab2/src/test/resources/lab2/test2001_boolean.ans @@ -0,0 +1 @@ +true diff --git a/lab2/src/test/resources/lab2/test2001_boolean.jsy b/lab2/src/test/resources/lab2/test2001_boolean.jsy new file mode 100644 index 0000000..27ba77d --- /dev/null +++ b/lab2/src/test/resources/lab2/test2001_boolean.jsy @@ -0,0 +1 @@ +true diff --git a/lab2/src/test/resources/lab2/test2002_undefined.ans b/lab2/src/test/resources/lab2/test2002_undefined.ans new file mode 100644 index 0000000..417b7b5 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2002_undefined.ans @@ -0,0 +1 @@ +undefined diff --git a/lab2/src/test/resources/lab2/test2002_undefined.jsy b/lab2/src/test/resources/lab2/test2002_undefined.jsy new file mode 100644 index 0000000..417b7b5 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2002_undefined.jsy @@ -0,0 +1 @@ +undefined diff --git a/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans new file mode 100644 index 0000000..736991a --- /dev/null +++ b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans @@ -0,0 +1 @@ +NaN diff --git a/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy new file mode 100644 index 0000000..0944dac --- /dev/null +++ b/lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy @@ -0,0 +1 @@ +undefined + 2.2 diff --git a/lab2/src/test/resources/lab2/test2036_variablelog.ans b/lab2/src/test/resources/lab2/test2036_variablelog.ans new file mode 100644 index 0000000..fed1126 --- /dev/null +++ b/lab2/src/test/resources/lab2/test2036_variablelog.ans @@ -0,0 +1,2 @@ +17.2 +13.1 diff --git a/lab2/src/test/resources/lab2/test2036_variablelog.jsy b/lab2/src/test/resources/lab2/test2036_variablelog.jsy new file mode 100644 index 0000000..8e0c0ad --- /dev/null +++ b/lab2/src/test/resources/lab2/test2036_variablelog.jsy @@ -0,0 +1,3 @@ +const x = 15.1; +console.log(x + 2.1) +x - 2
\ No newline at end of file diff --git a/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala b/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala new file mode 100644 index 0000000..b14d015 --- /dev/null +++ b/lab2/src/test/scala/jsy/lab2/Lab2Spec.scala @@ -0,0 +1,269 @@ +package jsy.lab2 + +import org.scalatest.flatspec.AnyFlatSpec +import Parser.parse +import ast._ + +/* Import your Lab 1 code. */ +import Lab2._ + +/** + * This is an empty test class that you may use to write your own tests. + */ +class Lab2StudentSpec extends AnyFlatSpec { + + val e_toNumber_test1 = N(3.0) + "toNumber" should s"${e_toNumber_test1}" in { + assertResult(3.0) { toNumber(e_toNumber_test1) } + } + + val e_toBoolean_test1 = B(true) + "toBoolean" should s"${e_toBoolean_test1}" in { + assertResult(true) { toBoolean(e_toBoolean_test1) } + } + + val e_toStr_test1 = S("hello") + "toStr" should s"${e_toStr_test1}" in { + assertResult("hello") { toStr(e_toStr_test1) } + } + +} + +/* + * This file contains a number of *Spec classes that define a set of + * tests. + */ +class Lab2Spec extends AnyFlatSpec { + + "And" should "return true only if both expressions are true" in { + val t = B(true) + val f = B(false) + assert(eval(Binary(And,t,t)) === t) + assert(eval(Binary(And,t,f)) === f) + assert(eval(Binary(And,f,t)) === f) + assert(eval(Binary(And,f,f)) === f) + } + + it should "return non-intuitive results from differing types" in { + val e1 = N(0) + val e2 = B(true) + val e3 = eval(Binary(And, e1, e2)) + assert(e3 === N(0)) + } + + "Or" should "return true if either or both expressions are true" in { + val t = B(true) + val f = B(false) + assert(eval(Binary(Or,t,t)) === t) + assert(eval(Binary(Or,f,t)) === t) + assert(eval(Binary(Or,t,f)) === t) + assert(eval(Binary(Or,f,f)) === f) + } + + it should "return non-intuitive results from differing types" in { + val e1 = N(5) + val e2 = B(false) + val e3 = eval(Binary(Or, e1, e2)) + assert(e3 === N(5)) + } + + "Plus" should "add two number values and return a number" in { + val e1 = N(1) + val e2 = N(2) + val e3 = eval(Binary(Plus, e1, e2)) + assert(e3 === N(3)) + } + + "Minus" should "subtract two number values and return a number" in { + val e1 = N(3) + val e2 = N(1) + val e3 = eval(Binary(Minus, e1, e2)) + assert(e3 === N(2)) + } + + "Times" should "multiply two number values and return a number" in { + val e1 = N(3) + val e2 = N(2) + val e3 = eval(Binary(Times, e1, e2)) + assert(e3 === N(6)) + } + + "Div" should "divide two number values and return a number" in { + val e1 = N(8) + val e2 = N(5) + val e3 = eval(Binary(Div, e1, e2)) + assert(e3 === N(1.6)) + } + + "Arithmetic Operators" should "produce non-intuitive solutions given differing expression types" in { + val e1 = B(true) + val e2 = N(7) + assert(eval(Binary(Plus,e1,e2)) == N(8)) + } + + "Eq" should "return true if two numerical values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Eq, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if two numerical values are not the same" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Eq, e1, e2)) + assert(e3 === B(false)) + } + + "Ne" should "return true if two numerical values are different" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Ne, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if two numerical values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Ne, e1, e2)) + assert(e3 === B(false)) + } + + "Lt" should "return true if the first expression is less than the second" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is not strictly less than the second" in { + val e1 = N(7) + val e2 = N(5) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(false)) + } + + it should "return false if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Lt, e1, e2)) + assert(e3 === B(false)) + } + + "Le" should "return true if the first expression is less than the second" in { + val e1 = N(5) + val e2 = N(7) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is greater than the second" in { + val e1 = N(7) + val e2 = N(5) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(false)) + } + + it should "return true if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Le, e1, e2)) + assert(e3 === B(true)) + } + + "Gt" should "return true if the first expression is greater than the second" in { + val e1 = N(8) + val e2 = N(7) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is not strictly greater than the second" in { + val e1 = N(4) + val e2 = N(5) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(false)) + } + + it should "return false if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Gt, e1, e2)) + assert(e3 === B(false)) + } + + "Ge" should "return true if the first expression is greater than the second" in { + val e1 = N(8) + val e2 = N(7) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(true)) + } + + it should "return false if the first expression is less than the second" in { + val e1 = N(4) + val e2 = N(5) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(false)) + } + + it should "return true if two number values are the same" in { + val e1 = N(5) + val e2 = N(5) + val e3 = eval(Binary(Ge, e1, e2)) + assert(e3 === B(true)) + } + + "Comparisons" should "produce non-intuitive results given the expressions given" in { + val e1 = N(5) + val e2 = Undefined + assert(eval(Binary(Eq,e1,e2)) === B(false)) + } + + "ConstDecl" should "extend the environment with the first expression results bound to the identifier, and then eval the second expression" in { + val e1 = N(3) + val e2 = Binary(Plus, Var("x"), N(1)) + val e3 = eval(ConstDecl("x", e1, e2)) + assert(e3 === N(4)) + } + + "If" should "eval the first expression if the conditional is true" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(If(B(true), e1, e2)) + assert(e3 === N(5)) + } + + it should "eval the second expression if the conditional is false" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(If(B(false), e1, e2)) + assert(e3 === N(2)) + } + + "Seq" should "execute the first expression, followed by the second, and should eval to the second expression" in { + val e1 = Binary(Plus, N(3), N(2)) + val e2 = Binary(Plus, N(1), N(1)) + val e3 = eval(Binary(Seq, e1, e2)) + assert(e3 === N(2)) + } + + "Neg" should "return the negation of a number value" in { + val e1 = N(5) + val e2 = eval(Unary(Neg, e1)) + assert(e2 === N(-5)) + } + + "Not" should "return the compliment of a boolean value" in { + val e1 = B(true) + val e2 = B(false) + val e3 = eval(Unary(Not, e1)) + val e4 = eval(Unary(Not, e2)) + assert(e3 === B(false)) + assert(e4 === B(true)) + } + +} + +// The next bit of code runs a test for each .jsy file in src/test/resources/lab2. +// The test expects a corresponding .ans file with the expected result. +class Lab2JsyTests extends jsy.tester.JavascriptyTester(None, "lab2", Lab2) diff --git a/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala new file mode 100644 index 0000000..ab611b9 --- /dev/null +++ b/lab2/src/test/scala/jsy/tester/JavascriptyTester.scala @@ -0,0 +1,27 @@ +package jsy.tester + +import java.io.File + +import jsy.util.JsyApplication +import org.scalatest._ +import flatspec._ + +/* + * A ScalaTest interface for running system tests. + */ +class JavascriptyTester(rootPrefix: Option[String], testDirectory: String, jsy: JsyApplication) extends AnyFlatSpec { + + val testResources = s"src${File.separator}test${File.separator}resources" + val testPrefix = rootPrefix match { + case None => testResources + case Some(p) => s"${p}${File.separator}${testResources}" + } + val testPath = s"${testPrefix}${File.separator}${testDirectory}" + jsy.test(new File(testPath)) { case (in,ans,assertion) => + s"eval on ${in}" should s"match ${ans}" in { + val (b: Boolean, msg: String) = assertion + assert(b, msg) + } + } + +} diff --git a/lab2/variables-values-lab.ipynb b/lab2/variables-values-lab.ipynb new file mode 100644 index 0000000..0a7619a --- /dev/null +++ b/lab2/variables-values-lab.ipynb @@ -0,0 +1,1336 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "e5c7e407-80c5-4211-9055-d94737de0b8d", + "metadata": {}, + "source": [ + "$\\newcommand{\\TirName}[1]{\\text{\\small #1}}\n", + "\\newcommand{\\inferrule}[3][]{\n", + " \\let\\and\\qquad\n", + " \\begin{array}{@{}l@{}}\n", + " \\TirName{#1}\n", + " \\\\\n", + " \\displaystyle\n", + " \\frac{#2}{#3}\n", + " \\end{array}\n", + "}\n", + "\\newcommand{\\infer}[3][]{\\inferrule[#1]{#2}{#3}}\n", + "$\n", + "\n", + "# Lab: Basic Values, Variables, and Judgments\n", + "\n", + "<!-- 3 Expressions -->\n", + "\n", + "<!-- 4 Binding and Scope -->\n", + "\n", + "<!-- 8 Recursion -->\n", + "\n", + "<!-- 9 Inductive Data Types -->\n", + "\n", + "<!-- 11 Concrete Syntax -->\n", + "\n", + "<!-- 12 Abstract Syntax and Parsing -->\n", + "\n", + "<!-- 13 Exercise: Syntax -->\n", + "\n", + "<!-- 14 Static Scoping -->\n", + "\n", + "<!-- 15 Judgments -->\n", + "\n", + "<!-- 16 Variables, Basic Values, and Judgments Lab -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- the distinction between concrete and abstract syntax;\n", + "- the relationship between judgment forms/inference rules/judgments\n", + " and implementation code;\n", + "- using a reference implementation as a definition of semantics;\n", + "- variable binding and variable environments.\n", + "\n", + "Functional Programming Skills \n", + "Recursion over abstract syntax. Representation invariants.\n", + "\n", + "Programming Language Ideas \n", + "Inductive definitions (grammars/productions/sentences and judgment\n", + "forms/inference rules/judgments). Semantics (via detective work).\n", + "\n", + "### Instructions\n", + "\n", + "A version of project files for this lab resides in the public\n", + "[pppl-lab2](https://github.com/csci3155/pppl-lab2) repository. Please\n", + "follow separate instructions to get a private clone of this repository\n", + "for your work.\n", + "\n", + "You will be replacing `???` or `case _ => ???` in the `Lab2.scala` file\n", + "with solutions to the coding exercises described below.\n", + "\n", + "**Your lab will not be graded if it does not compile**. You may check\n", + "compilation with your IDE, `sbt compile`, or with the “sbt compile”\n", + "GitHub Action provided for you. Comment out any code that does not\n", + "compile or causes a failing assert. Put in `???` as needed to get\n", + "something that compiles without error.\n", + "\n", + "You may add additional tests to the `Lab2Spec.scala` file. In the\n", + "`Lab2Spec.scala`, there is empty test class `Lab2StudentSpec` that you\n", + "can use to separate your tests from the given tests in the `Lab2Spec`\n", + "class. You are also likely to edit `Lab2.worksheet.sc` for any scratch\n", + "work. You can also use `Lab2.worksheet.js` to write and experiment in a\n", + "JavaScript file that you can then parse into a JavaScripty AST (see\n", + "`Lab2.worksheet.sc`).\n", + "\n", + "If you like, you may use this notebook for experimentation. However,\n", + "**please make sure your code is in `Lab2.scala`; this notebook will not\n", + "graded.**\n", + "\n", + "Recall that you need to switch kernels between running JavaScript and\n", + "Scala cells.\n", + "\n", + "## Interpreter: JavaScripty Calculator\n", + "\n", + "In this lab, we extend JavaScripty with additional value types and\n", + "variable binding. That is, the culmination of the lab is to implement an\n", + "interpreter for the subset of JavaScript with numbers, booleans,\n", + "strings, the undefined value, and variable binding." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "id": "fc23196d", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Expr</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">N</span>\n", + "defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()</pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "trait Expr // e ::=\n", + "case class N(n: Double) extends Expr // n\n", + "\n", + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "id": "3615c99b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "a2f3b886-b8d3-482d-aac1-088e998593d0", + "metadata": {}, + "source": [ + "We leave the `Expr` inductive data type mostly undefined for the moment\n", + "to focus on the type of `eval`.\n", + "\n", + "First, observe that the return type of `eval` is an `Expr` (versus\n", + "`Double` in the previous lab), as we now have more value types. However,\n", + "`eval` should return an `Expr` that is a JavaScripty value (i.e., is an\n", + "$e$ `: Expr` such that `isValue(` $e$ `)` returns `true`). The need for\n", + "the object-language versus meta-language distinction is even more\n", + "salient here than in the previous lab. For example, it is critical to\n", + "keep straight that `N(1.0)` is the Scala value representing the\n", + "JavaScripty value `1.0`.\n", + "\n", + "Second, observe that the `eval` function takes a JavaScripty value\n", + "environment `env: Env` to give meaning to free JavaScripty variables in\n", + "`e`.\n", + "\n", + "These ideas take unpacking, so let us start from the arithmetic\n", + "sub-language of JavaScripty:" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "id": "9088c943", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Unary</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Binary</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Uop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Neg</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Bop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Plus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Minus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Times</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Div</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1\n", + "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2\n", + "\n", + "trait Uop // uop ::=\n", + "case object Neg extends Uop // -\n", + "\n", + "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": "44fff901-f124-48fc-bd1d-906b79120db5", + "metadata": {}, + "source": [ + "Thus far, we have considered only one type of value in our JavaScripty\n", + "object language: numbers $n$ (which we have considered double-precision\n", + "floating-point numbers). Specifically, we have stated the following:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& v\n", + "\\\\\n", + "\\text{values} & v& \\mathrel{::=}& n\n", + "\\end{array}\n", + "$$\n", + "\n", + "Recall from our preliminary discussion about evaluation\n", + "(**?@sec-evaluation-preliminaries**) that the computational model is a\n", + "rewriting or reduction of expressions until reaching values. A value is\n", + "simply an expression that cannot be reduced any further. Thus, we can\n", + "also consider a unary judgment form $e\\;\\mathsf{value}$ that judges when\n", + "an expression is a value. $$\n", + "\\infer[NumVal]{\n", + "}{\n", + " n\\;\\mathsf{value}\n", + "}\n", + "$$\n", + "\n", + "This judgment form corresponds to the `isValue` function:" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "id": "bbf7152f", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "8dade6b2-d9fb-47a9-91fd-0e2b6aff8f0a", + "metadata": {}, + "source": [ + "From our discussion on grammars and inference rules\n", + "(**?@sec-grammars-and-inference-rules**), we can see this unary judgment\n", + "form $e\\;\\mathsf{value}$ as defining a syntactic category values $v$.\n", + "Thus, we freely write grammar productions for $v$ to define the judgment\n", + "form $e\\;\\mathsf{value}$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1**</span> For this part of the\n", + "lab, implement `eval` for the calculator language above (which is the\n", + "same language as in the previous lab) but now with type\n", + "`(Env, Expr) => Expr`." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "id": "4c173e3a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "aa64c2db-875f-4d68-a8e9-61eb3951c890", + "metadata": {}, + "source": [ + "You will not use the `env` parameter yet. You will want to check that\n", + "your implementation returns JavaScripty values. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "f88d8980", + "metadata": {}, + "outputs": [], + "source": [ + "val e_oneplustwo = Binary(Plus, N(1), N(2))\n", + "assert( isValue( eval(empty, e_oneplustwo) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "9bffa2f5-4fec-43f1-a871-322dd100c795", + "metadata": {}, + "source": [ + "## Coercions: Basic Values\n", + "\n", + "### Booleans, Strings, and Undefined\n", + "\n", + "Like most other languages, JavaScript has other basic value types. Let\n", + "us extend JavaScripty with Booleans, strings, and the\n", + "$\\mathbf{undefined}$ value:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{values} & v& \\mathrel{::=}&\n", + "b\n", + " \\mid\\mathit{str}\n", + " \\mid\\mathbf{undefined}\n", + "\\\\\n", + "\\text{booleans} & b\n", + "\\\\\n", + "\\text{strings} & \\mathit{str}\n", + "\\end{array}\n", + "$$\n", + "\n", + "Boolean values $b$ are the literals $\\mathbf{true}$ and\n", + "$\\mathbf{false}$. String values $\\mathit{str}$ are string literals like\n", + "`\"hi\"` that we do not explicitly define here.\n", + "\n", + "The $\\mathbf{undefined}$ literal is a distinguished value that is\n", + "different than all other values. It is like the unit literal `()` in\n", + "Scala." + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "id": "67096a6c", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">B</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">S</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Undefined</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class B(b: Boolean) extends Expr // e ::= b\n", + "case class S(str: String) extends Expr // | str\n", + "case object Undefined extends Expr // | undefined" + ] + }, + { + "cell_type": "markdown", + "id": "e9e4fe7c-4dd9-4b7f-85ab-fcbe72cb0292", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hello\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hola\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> undefined\n", + "> ```\n", + "\n", + "We update our `isValue` function appropriately:" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "id": "11b7ec3b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | S(_) | Undefined => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "2e5c680f-3806-4f25-a0e0-c568a6935a69", + "metadata": {}, + "source": [ + "A good exercise here is to reflect on what this code translates to in\n", + "terms of additional inference rules for the $e\\;\\mathsf{value}$ judgment\n", + "form.\n", + "\n", + "### Expressions\n", + "\n", + "Each value type comes with some operations. Our abstract syntax tree has\n", + "two constructors for unary and binary expressions that are parametrized\n", + "by unary $\\mathit{uop}$ and binary $\\mathit{bop}$ operators,\n", + "respectively:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + " \\mid\\mathop{\\mathit{uop}} e_1\n", + " \\mid e_1 \\mathrel{\\mathit{bop}} e_2\n", + "\\end{array}\n", + "$$\n", + "\n", + "#### Numbers\n", + "\n", + "For example, numbers has\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{-}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{+}\\mid\\texttt{-}\\mid\\texttt{*}\\mid\\texttt{/}\n", + "\\end{array}\n", + "$$\n", + "\n", + "that we considered previously.\n", + "\n", + "#### Booleans\n", + "\n", + "For booleans, we add unary negation $\\texttt{!}$ and binary conjunction\n", + "$\\texttt{\\&\\&}$ and disjunction $\\texttt{||}$. $$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}&\n", + "\\texttt{!}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{\\&\\&}\n", + "\\mid\\texttt{||}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "id": "88028ed8", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Not</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">And</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Or</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Not extends Uop // uop ::= !\n", + "case object And extends Bop // bop ::= &&\n", + "case object Or extends Bop // | ||" + ] + }, + { + "cell_type": "markdown", + "id": "f21da0e4-59c4-4f78-bd80-ac09e77fa224", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> !true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true && false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true || false\n", + "> ```\n", + "\n", + "We also expect to be able to elimate booleans with a conditional\n", + "if-then-else expression: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "id": "05ea3d8a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">If</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3" + ] + }, + { + "cell_type": "markdown", + "id": "6fe0176b-eb8a-4882-bd33-aa6e6065df6d", + "metadata": {}, + "source": [ + "We also expect to be able to compare values for equality and disquality\n", + "and numbers for inequality: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{===}\n", + "\\mid\\texttt{!==}\n", + "\\mid\\texttt{<}\n", + "\\mid\\texttt{<=}\n", + "\\mid\\texttt{>}\n", + "\\mid\\texttt{>=}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "id": "47b3dc58", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Eq</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ne</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Lt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Le</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Gt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ge</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Eq extends Bop // bop ::= ===\n", + "case object Ne extends Bop // | !==\n", + "case object Lt extends Bop // | <\n", + "case object Le extends Bop // | <=\n", + "case object Gt extends Bop // | >\n", + "case object Ge extends Bop // | >=" + ] + }, + { + "cell_type": "markdown", + "id": "ebd33875-524f-4966-96f9-2c1614fef714", + "metadata": {}, + "source": [ + "#### Strings\n", + "\n", + "The one string operation we support in JavaScripty is string\n", + "concatenation. In JavaScript, string concatenation is written with the\n", + "binary operator `+`, so we do not need to extend the syntax.\n", + "\n", + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> \"Hello\" + \", \" + \"World\" + \"!\"\n", + "> ```\n", + "\n", + "#### Undefined\n", + "\n", + "As $\\mathbf{undefined}$ corresponds to unit `()` in Scala and is\n", + "uninteresting in itself, we add a side-effecting expression that prints\n", + "to console.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "id": "226c53fa", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Print</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Print(e1: Expr) extends Expr // e ::= console.log(e1)" + ] + }, + { + "cell_type": "markdown", + "id": "afc77e07-23e1-4c34-9f2e-1a4c7c5f5b4e", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> console.log(\"Hello, World!\")\n", + "> ```\n", + "\n", + "If we now have side-effecting expressions, then we would expect to have\n", + "a way to sequence executing expressions for their effects.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{,}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "id": "4c211bca", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Seq</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Seq extends Bop // bop ::= ," + ] + }, + { + "cell_type": "markdown", + "id": "579a39c5-348a-46e4-b706-a86e0fbfc617", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> undefined, 3\n", + "> ```\n", + "\n", + "### Semantics Detective: JavaScript is Bananas\n", + "\n", + "In the above, we have carefully specified the abstract syntax of the\n", + "object language of interest and informally discussed its semantics. But\n", + "if we are to implement an interpreter in the `eval` function, we also\n", + "need to define its semantics! And we give a precise definition as\n", + "follows:\n", + "\n", + "> **Important**\n", + ">\n", + "> In this lab, the semantics of a JavaScripty expression $e$ is defined\n", + "> by the evaluation of it as a JavaScript program.\n", + "\n", + "Given the careful specification of the abstract syntax, a natural\n", + "question to ask is whether all abstract syntax trees of type `Expr` in\n", + "the above are valid expressions and have a semantics in JavaScript (and\n", + "hence JavaScripty). Is `3 + true` a valid expression?" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3e3c4c0b-3d04-40c6-b11a-8ab618b54796", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "3 + true" + ] + }, + { + "cell_type": "markdown", + "id": "7af09a5d-90d7-4284-b408-51098a6bc898", + "metadata": {}, + "source": [ + "We try it out and see that yes it is. One aspect that makes the\n", + "JavaScript specification interesting is the presence of implicit\n", + "coercions (e.g., non-numeric values, such as booleans or strings, may be\n", + "implicitly converted to numeric values depending on the context in which\n", + "they are used).\n", + "\n", + "You might guess that defining coercions between value types can lead to\n", + "some interesting semantics. It is because of these coercions that we\n", + "have the meme that “JavaScript is bananas.”" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0bbdf44a-efd4-42e7-ab8b-3e58b85414dd", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "\"b\" + \"a\" + \"n\" + - \"a\" + \"a\" + \"s\"" + ] + }, + { + "cell_type": "markdown", + "id": "a614770c-4f97-4e4b-8ffa-83c4ee7a535b", + "metadata": {}, + "source": [ + "Armed with knowledge that in JavaScript, numbers are floating-point\n", + "numbers, the `+` operator in JavaScript is overloaded for strings and\n", + "numbers, and coercions happen between value types, see if you can\n", + "explain what is happening in the “bananas” expression above.\n", + "\n", + "#### Coercions\n", + "\n", + "Our `eval` function interpreter will need to make use of three helper\n", + "functions for converting values to numbers, booleans, and strings:" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "id": "76e48b08", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toNumber</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toBoolean</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toStr</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def toNumber(v: Expr): Double = ???\n", + "def toBoolean(v: Expr): Boolean = ???\n", + "def toStr(v: Expr): String = ???" + ] + }, + { + "cell_type": "markdown", + "id": "877ad7ab-c025-46d1-8597-a2dc7960e167", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 2**</span> Write at least 1\n", + "JavaScript expression that shows a coercion from a non-numeric value to\n", + "a number and see what the result should be:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ecf717e2-a8a2-4163-a2fc-626d3c32614c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "markdown", + "id": "c2e075a3-d8c2-4d4d-b50c-3b05446e7138", + "metadata": {}, + "source": [ + "Then, translate this JavaScript expression (written in concrete syntax)\n", + "into an `Expr` value (i.e., a JavaScripty abstract syntax tree)." + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "id": "f2373c38", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "15ae65f0-171c-439e-8391-55db52bc29c7", + "metadata": {}, + "source": [ + "Finally, use this `Expr` as a unit test for `toNumber` in the\n", + "`Lab2StudentSpec` class in the `Lab2Spec.scala` file.\n", + "\n", + "``` scala\n", + "val e_toNumber_test1 = ???\n", + "\"toNumber\" should s\"${e_toNumber_test1}\" in {\n", + " assertResult(???) { toNumber(e_toNumber_test1) }\n", + "}\n", + "```\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3**</span> Do the same to create\n", + "a `toBoolean` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-boolean value to a boolean, see what the result\n", + "should be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2028060d-7a15-4b27-9153-4acb2911dcce", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "id": "2eb72698", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6e8628d8-49de-4749-8c8c-c3e9a5ae2569", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 4**</span> Do the same to create\n", + "a `toStr` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-string value to a string, see what the result should\n", + "be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "09a51a9d-f222-4462-b99e-2237d3d7e76c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "id": "2b0d83e9", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "b0804229-2e80-4c50-b10d-45bae14ac467", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 5**</span> Implement `toNumber`,\n", + "`toBoolean`, and `toStr` in `Lab2.scala` (using test-driven development\n", + "with the test cases you have written above).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "booleans, strings, the undefined value, and printing." + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "id": "d4af7b6b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "59a41a5f-f9c2-472c-a3e8-ed1d1511985c", + "metadata": {}, + "source": [ + "You still will not use the `env` parameter yet. You again will want to\n", + "check that your implementation returns JavaScripty values using the\n", + "latest `isValue`. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "2913288e", + "metadata": {}, + "outputs": [], + "source": [ + "val e_nottrue = Unary(Not, B(true))\n", + "assert( isValue( eval(empty, e_nottrue) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "5d9adaaa-44a9-4020-a559-e61e98217282", + "metadata": {}, + "source": [ + "## Interpreter: JavaScripty Variables\n", + "\n", + "The final piece of this lab is to extend our interpreter with variable\n", + "uses and binding (cf. **?@sec-static-scoping**).\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& x\\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "id": "9c0ab5cd", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Var</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">ConstDecl</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Var(x: String) extends Expr // e ::= x\n", + "case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // | const x = e1; e2" + ] + }, + { + "cell_type": "markdown", + "id": "3753b5f9-3d1e-4ef3-9ca6-b016448b3fed", + "metadata": {}, + "source": [ + "Note that the above is the abstract syntax we consider for `ConstDecl`,\n", + "which is more flexible the concrete syntax for `const` allowed by\n", + "JavaScript (cf. )\n", + "\n", + "In this lab, we define a value environment as a map from variable names\n", + "to JavaScripty values, which we represent in Scala as a value of type\n", + "`Map[String, Expr]`. Note that representing variable names as Scala\n", + "`String`s here, and it is a representation invariant that the `Expr`s\n", + "must correspond to JavaScripty values." + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "id": "74452c05", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">lookup</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">extend</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty\n", + "\n", + "def lookup(env: Env, x: String): Expr = env(x)\n", + "def extend(env: Env, x: String, v: Expr): Env = {\n", + " require(isValue(v))\n", + " env + (x -> v)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "abf51752-104b-4fe7-b3bb-56f2b30c651d", + "metadata": {}, + "source": [ + "We provide the above value and function bindings to interface with the\n", + "Scala standard library for `Map[String, Expr]` and maintain this\n", + "representation invariant. You may use the Scala standard library\n", + "directly if you wish, but we recommend that you just use these\n", + "interfaces, as they are all that you need and give you the safety of\n", + "enforcing the representation invariant. The `empty` value represents an\n", + "empty value environment, the `lookup` function gets the value bound to\n", + "the variable named by a given string, and the `extend` function extends\n", + "a given environment with a new variable binding.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "variable uses (i.e., `Var`) and variable binding (i.e., `ConstDecl`). We\n", + "suggest you start by adding tests with variables uses and `const`\n", + "bindings to be able do test-driven development (see below)." + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "id": "cc90dc11", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "2bb3563b-1d34-4f4b-9feb-2b2c8b6f28df", + "metadata": {}, + "source": [ + "### Testing\n", + "\n", + "In this lab, we have carefully defined the syntax of the JavaScripty\n", + "variant of interest, and we have defined its semantics to be defined to\n", + "be the same as JavaScript. Thus, you can write any JavaScript program\n", + "within the syntax defined above to create test cases for your `eval`\n", + "function. Any of the above JavaScript examples could be used as test\n", + "cases. In some cases, you may want to write abstract syntax trees\n", + "directly in Scala (i.e., values of type `Expr`). In other cases, you can\n", + "use the provided JavaScripty parser to translate concrete syntax (i.e.,\n", + "values of type `String`) into abstract syntax (i.e., values of type\n", + "`Expr`).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (Optional)**</span> We give\n", + "some exercises below to explore this subset of JavaScripty that you can\n", + "then use as test cases that you add to your `Lab2StudentSpec`.\n", + "\n", + "#### Basic Arithmetic Operations" + ] + }, + { + "cell_type": "markdown", + "id": "a2c70244-56b8-4945-b53d-4be38c6ed6e3", + "metadata": {}, + "source": [ + "This program defines two constants, `x` and `y`, and calculates their\n", + "sum. It then logs the result `sum` to the console." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "862e000e-d1a1-4a25-b8bb-1983badfb81e", + "metadata": {}, + "outputs": [], + "source": [ + "const x = 10;\n", + "const y = 5;\n", + "const sum = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";\n", + "console.log(sum);" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5db48d42-a357-4957-bdd2-4436e69d521a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(sum === 15)" + ] + }, + { + "cell_type": "markdown", + "id": "369b9301-1017-497b-8175-0654a035b32e", + "metadata": {}, + "source": [ + "#### Conditional Expressions" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b8ae58be-e5bd-4d13-a6eb-6d6fffbd7f2a", + "metadata": {}, + "outputs": [], + "source": [ + "const a = 10;\n", + "const b = 20;\n", + "const max = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "fe6cbe1e-fc0b-4965-a09a-38adcee24776", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(max === 20)" + ] + }, + { + "cell_type": "markdown", + "id": "32479c1c-d55e-4d89-a4aa-89f58c7397a3", + "metadata": {}, + "source": [ + "#### Unary and Binary Operations\n", + "\n", + "This program checks if a number is positive using a unary negation `-`\n", + "and a binary relational operator." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "01bed277-7e0a-4ebb-8f85-3bc60ca4637f", + "metadata": {}, + "outputs": [], + "source": [ + "const num = -5;\n", + "const isPositive =\n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2547e992-8b43-4944-bce3-045f9a03807a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(isPositive === false)" + ] + }, + { + "cell_type": "markdown", + "id": "36cab120-2f06-4f1b-a68a-e51ca556cf97", + "metadata": {}, + "source": [ + "#### Undefined\n", + "\n", + "This program demonstrates the correspondence between `undefined` in\n", + "JavaScript and `()`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1896f8d4-2fe1-4204-8405-a1a678c70ffe", + "metadata": {}, + "outputs": [], + "source": [ + "const r = console.log(\"Hello\");" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b4138580-25dc-4101-9f30-968ad136a1ee", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(r === undefined)" + ] + }, + { + "cell_type": "markdown", + "id": "b97d1faf-fb1f-4626-b1c6-405e1fc11ee8", + "metadata": {}, + "source": [ + "## 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.4" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |