aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:02:45 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:02:45 -0700
commit0d13c649bdabafde59233609be7bd88e273c7ae6 (patch)
tree69e3a615f5c3e6a95a752161136acf00c973184d
parent532be33588fd033fc7f814e725372923cf79a6c4 (diff)
downloadcsci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.tar.gz
csci3155-0d13c649bdabafde59233609be7bd88e273c7ae6.zip
Unit 2
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--abstract-syntax-exercise.ipynb1657
-rw-r--r--lab2/build.sbt47
-rw-r--r--lab2/project/build.properties1
-rw-r--r--lab2/src/main/scala/jsy/lab2/Lab2.scala150
-rw-r--r--lab2/src/main/scala/jsy/lab2/Lab2.worksheet.js21
-rw-r--r--lab2/src/main/scala/jsy/lab2/Lab2.worksheet.sc34
-rw-r--r--lab2/src/main/scala/jsy/lab2/Parser.scala255
-rw-r--r--lab2/src/main/scala/jsy/lab2/ast.scala92
-rw-r--r--lab2/src/main/scala/jsy/util/JsyApplication.scala191
-rw-r--r--lab2/src/test/resources/lab2/test2001_boolean.ans1
-rw-r--r--lab2/src/test/resources/lab2/test2001_boolean.jsy1
-rw-r--r--lab2/src/test/resources/lab2/test2002_undefined.ans1
-rw-r--r--lab2/src/test/resources/lab2/test2002_undefined.jsy1
-rw-r--r--lab2/src/test/resources/lab2/test2013_undefinedplusnumber.ans1
-rw-r--r--lab2/src/test/resources/lab2/test2013_undefinedplusnumber.jsy1
-rw-r--r--lab2/src/test/resources/lab2/test2036_variablelog.ans2
-rw-r--r--lab2/src/test/resources/lab2/test2036_variablelog.jsy3
-rw-r--r--lab2/src/test/scala/jsy/lab2/Lab2Spec.scala269
-rw-r--r--lab2/src/test/scala/jsy/tester/JavascriptyTester.scala27
-rw-r--r--lab2/variables-values-lab.ipynb1336
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
+}