diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:58 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:58 -0700 |
commit | 08f9cae13d0dce99d40a6d93432a84cb075bebfc (patch) | |
tree | 5714d73c616b511d8fa5ea8a0ef1d8405f13ce90 | |
parent | 0d13c649bdabafde59233609be7bd88e273c7ae6 (diff) | |
download | csci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.tar.gz csci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.zip |
Unit 3
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | big-step-exercise.ipynb | 2342 | ||||
-rw-r--r-- | lab3/build.sbt | 46 | ||||
-rw-r--r-- | lab3/project/build.properties | 1 | ||||
-rw-r--r-- | lab3/small-step-lab.ipynb | 1335 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.scala | 360 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js | 24 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc | 51 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/Parser.scala | 284 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/lab3/ast.scala | 106 | ||||
-rw-r--r-- | lab3/src/main/scala/jsy/util/JsyApplication.scala | 191 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3004_call.ans | 8 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3004_call.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3006_curry.ans | 8 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3006_curry.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3008_call.ans | 48 | ||||
-rw-r--r-- | lab3/src/test/resources/lab3/test3008_call.jsy | 2 | ||||
-rw-r--r-- | lab3/src/test/scala/jsy/lab3/Lab3Spec.scala | 150 | ||||
-rw-r--r-- | lab3/src/test/scala/jsy/tester/JavascriptyTester.scala | 23 |
18 files changed, 4983 insertions, 0 deletions
diff --git a/big-step-exercise.ipynb b/big-step-exercise.ipynb new file mode 100644 index 0000000..d0e415d --- /dev/null +++ b/big-step-exercise.ipynb @@ -0,0 +1,2342 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "bd949a01", + "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": 1, + "id": "f45214a1", + "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": 1, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val NAME = \"Jack Sangdahl\"\n", + "val COLLABORATORS = \"N/A\"" + ] + }, + { + "cell_type": "markdown", + "id": "8d26413f", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "efa5d5cf-c495-440c-8f26-17e20cad2a3f", + "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", + "# Exercise: Big-Step Operational Semantics\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", + "<!-- 17 Operational Semantics -->\n", + "\n", + "<!-- 18 Functions and Dynamic Scoping -->\n", + "\n", + "<!-- 19 Big-Step Exercise -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- how to read a formal specification of a language semantics;\n", + "- how dynamic scoping arises; and\n", + "- big-step interpretation.\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": 2, + "id": "88052e49", + "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": 2, + "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": "markdown", + "id": "35a9dcee-4c64-4cdb-8ea2-aaca684dda00", + "metadata": {}, + "source": [ + "## A Big-Step Javascripty Interpreter\n", + "\n", + "We now have the formal tools to specify exactly how a JavaScripty\n", + "program should behave. Unless otherwise specified, we continue to try to\n", + "match JavaScript semantics, though we are no longer beholden to it.\n", + "Thus, it is still useful to write little test JavaScript programs and\n", + "see how the test should behave.\n", + "\n", + "In this exercise, we extend JavaScripty with functions. We try to\n", + "implement the `eval` function in the most straightforward way. What we\n", + "will discover is that we have made a historical mistake and have ended\n", + "up with a form of *dynamic scoping*.\n", + "\n", + "For the purpose of this exercise, we will limit the scope of JavaScripty\n", + "by restricting expression forms and simplifying semantics as appropriate\n", + "for pedagogical purposes. In particular, we simplify the semantics by no\n", + "longer performing implicit type coercions.\n", + "\n", + "### Syntax\n", + "\n", + "We consider the following *abstract syntax* for this exercise. Note that\n", + "new constructs for functions are $\\color{red}\\text{highlighted}$.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + " \\text{expressions} & e& \\mathrel{::=}&\n", + " n\n", + " \\mid b\n", + " \\mid e_1 \\mathbin{\\mathit{bop}}e_2\n", + " \\mid e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + " \\mid x\n", + " \\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 \\\\ \n", + " && \\color{red}\\mid& \\color{red}\n", + " \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\mid e_1\\texttt{(}e_2\\texttt{)}\n", + " \\\\\n", + " \\text{values} & v& \\mathrel{::=}&\n", + " n\n", + " \\mid b\n", + " \\color{red}\n", + " \\mid\\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\\\\n", + " \\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + " \\texttt{+}\n", + " \\mid\\texttt{===}\n", + " \\mid\\texttt{!==}\n", + " \\\\\n", + " \\text{variables} & x\n", + " \\\\\n", + " \\text{numbers} & n\n", + " \\\\\n", + " \\text{booleans} & b\n", + "\\end{array}\n", + "$$\n", + "\n", + "Observe that we consider only base values numbers $n$ and booleans $b$\n", + "and have significantly reduced the number of expression forms we\n", + "consider.\n", + "\n", + "Like in the book chapter, all functions are one argument functions for\n", + "simplicity.\n", + "\n", + "## Dynamic Scoping Test\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (5 points)**</span> Write a\n", + "JavaScript program that behaves differently under dynamic scoping versus\n", + "static scoping (and does not crash). This will get us used to the\n", + "syntax, while providing a crucial test case for our interpreter.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "70a3be6f-d318-40af-b9e6-b1dd9638319c", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "61ecbdea151ec78eedf98d1336ed1dc2", + "grade": true, + "grade_id": "dynamic-scoping-test", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "name": "stderr", + "output_type": "stream", + "text": [ + "cmd20.sc:1: not found: value const\n", + "val res20_0 = const x = 10;\n", + " ^\n", + "cmd20.sc:2: not found: value const\n", + "val res20_1 = const f = (a) => {\n", + " ^\n", + "cmd20.sc:6: not found: value const\n", + "val res20_2 = const g = (b) => {\n", + " ^\n", + "cmd20.sc:10: not found: value console\n", + "val res20_3 = console.log(f(-1))\n", + " ^\n", + "cmd20.sc:10: not found: value f\n", + "val res20_3 = console.log(f(-1))\n", + " ^\n", + "cmd20.sc:1: postfix operator x needs to be enabled\n", + "by making the implicit value scala.language.postfixOps visible.\n", + "This can be achieved by adding the import clause 'import scala.language.postfixOps'\n", + "or by setting the compiler option -language:postfixOps.\n", + "See the Scaladoc for value scala.language.postfixOps for a discussion\n", + "why the feature needs to be explicitly enabled.\n", + "val res20_0 = const x = 10;\n", + " ^\n", + "cmd20.sc:2: postfix operator f needs to be enabled\n", + "by making the implicit value scala.language.postfixOps visible.\n", + "val res20_1 = const f = (a) => {\n", + " ^\n", + "cmd20.sc:6: postfix operator g needs to be enabled\n", + "by making the implicit value scala.language.postfixOps visible.\n", + "val res20_2 = const g = (b) => {\n", + " ^\n", + "Compilation Failed" + ] + } + ], + "source": [ + "const x = 10;\n", + "const f = (a) => {\n", + " return x + a;\n", + "}\n", + "\n", + "const g = (b) => {\n", + " const x = 20;\n", + " return f(b);\n", + "}\n", + "console.log(f(-1))" + ] + }, + { + "cell_type": "markdown", + "id": "1bd2d1c9-5101-4b29-8090-40482c978974", + "metadata": {}, + "source": [ + "Explain in 1-2 sentences why you think this program would behave\n", + "differently under dynamic scoping versus static scoping.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "cd4d28fb-9209-4946-b934-9d4d089d2469", + "metadata": {}, + "source": [ + "With **static scoping**, when `f` is called from inside `g`, the value of `x` inside `f` is based on where `f` is *defined*. Since here, `f` is defined in the global scope, which is 10, calling `f(-1)` will evaluate to $10 + (-1) = 9$. With **dynamic scoping**, the value of `x` will be based on the current context of the program. In `g`, the value of `x` is 20, which is the value that will be used in `f`. Meaning `f(-1)` will evaluate to $20 + (-1) = 19$." + ] + }, + { + "cell_type": "markdown", + "id": "178c4974-726e-4a67-a922-8b658644f327", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- We are using $\\mathbf{const}$ to *name* functions, that is, we are\n", + " binding an expression, which is a function, to a variable. This\n", + " binding allows us to get it later, but it *does not* allow us call\n", + " it inside the function definition (i.e., recursion).\n", + "- We are providing a throw-away parameter to our function because\n", + " according to our syntax functions have exactly one parameter.\n", + "- As noted above, we are simplifying some semantics in this exercise\n", + " compared with the previous lab: implicit type coercions work in\n", + " JavaScript and in the previous lab, but you will not include them in\n", + " your implementation on this homework. Therefore, *your test case\n", + " cannot have any implicit type conversions*.\n", + "- In order to execute the program, you will need to switch your kernal\n", + " to Deno, the Javascript kernel for Jupyter.\n", + "\n", + "## Reading an Operational Semantics\n", + "\n", + "In this homework, we start to see specifications of programming language\n", + "semantics. A big-step operational semantics of this small fragment of\n", + "JavaScripty is given below. Except perhaps for the assigned reading,\n", + "this figure\n", + "(<a href=\"#fig-javascripty-numbers-booleans-variables-limited\"\n", + "class=\"quarto-xref\">FigureĀ 1</a>) may be one of the first times that you\n", + "are reading a formal semantics of a programming language. It may seem\n", + "daunting at first, but it will be become easier with practice. This\n", + "homework is such an opportunity to practice.\n", + "\n", + "$\\fbox{$E \\vdash e \\Downarrow v$}$\n", + "\n", + "$\\inferrule[EvalVar]{\n", + " \\phantom{\\Downarrow}\n", + "}{\n", + " E \\vdash x \\Downarrow E(x) \n", + "}$\n", + "\n", + "$\\inferrule[EvalConstDecl]{\n", + " E \\vdash e_1 \\Downarrow v_1 \n", + " \\and\n", + " E[\\mathop{}x \\mapsto v_1] \\vdash e_2 \\Downarrow v_2 \n", + "}{\n", + " E \\vdash \n", + " \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + " \\Downarrow v_2 \n", + "}$\n", + "\n", + "$\\inferrule[EvalVal]{\n", + " \\phantom{ \\Downarrow}\n", + "}{\n", + " E \\vdash v \\Downarrow v\n", + "}$\n", + "\n", + "$\\inferrule[EvalPlusNumber]{\n", + " E \\vdash e_1 \\Downarrow n_1 \n", + " \\and\n", + " E \\vdash e_2 \\Downarrow n_2 \n", + "}{\n", + " E \\vdash \n", + " e_1 \\mathbin{\\texttt{+}} e_2\n", + " \\Downarrow n_1 \\mathbin{+} n_2 \n", + "}$\n", + "\n", + "$\\inferrule[EvalEquality]{\n", + " E \\vdash e_1 \\Downarrow v_1 \n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2 \n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{===}, \\texttt{!==} \\right\\}\n", + "}{\n", + " E \\vdash \n", + " e_1 \\mathbin{\\mathit{bop}} e_2\n", + " \\Downarrow v_1 \\mathbin{\\mathit{bop}} v_2 \n", + "}$\n", + "\n", + "$\\inferrule[EvalIfTrue]{\n", + " E \\vdash e_1 \\Downarrow \\mathbf{true}\n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2 \n", + "}{\n", + " E \\vdash \n", + " e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + " \\Downarrow v_2 \n", + "}$\n", + "\n", + "$\\inferrule[EvalIfFalse]{\n", + " E \\vdash e_1 \\Downarrow \\mathbf{false}\n", + " \\and\n", + " E \\vdash e_3 \\Downarrow v_3 \n", + "}{\n", + " E \\vdash \n", + " e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + " \\Downarrow v_3 \n", + "}$\n", + "\n", + "FigureĀ 1: A big-step operational semantics of a fragment of JavaScripty\n", + "with some arithmetic and logic expressions, as well as variable binding.\n", + "We define the judgment form $E \\vdash e \\Downarrow v$, which says\n", + "informally, āIn value environment $E$, expression $e$ evaluates to value\n", + "$v$.ā This relation has three parameters: $E$, $e$, and $v$. You can see\n", + "the other parts of the judgment form as simply punctuation.\n", + "\n", + "A value environment $E$ is a finite map from variables $x$ to values $v$\n", + "that we write as follows: $$\n", + "\\begin{array}{rrrl}\n", + " \\text{value environments} & E, \\mathit{env}& \\mathrel{::=}& \\cdot \\mid E[\\mathop{}x \\mapsto v]\n", + "\\end{array}\n", + "$$\n", + "\n", + "We write $\\cdot$ for the empty environment and $E[\\mathop{}x \\mapsto v]$\n", + "as the environment that maps $x$ to $v$ but is otherwise the same as $E$\n", + "(i.e., extends $E$ with mapping $x$ to $v$). Additionally, we write\n", + "$E(x)$ for looking up the value of $x$ in environment $E$.\n", + "\n", + "A formal semantics enables us to describe the semantics of a programming\n", + "language clearly and concisely. The initial barrier is getting used to\n", + "the meta-language of judgment forms and inference rules. However, once\n", + "you cross that barrier, you will see that we are telling you exactly how\n", + "to implement the interpreterāit will almost feel like cheating!\n", + "\n", + "### Strings\n", + "\n", + "<span class=\"theorem-title\">**Exercise 2 (5 points)**</span> Suppose\n", + "that we extend the above language with strings $\\mathit{str}$ and a\n", + "string concatenation $e_1 \\mathbin{\\texttt{+}} e_2$ expression (like in\n", + "JavaScript). Consider the following inference rule for the evaluation\n", + "judgment form:\n", + "\n", + "$\\inferrule[EvalPlusString1]{\n", + " E \\vdash e_1 \\Downarrow \\mathit{str}_1 \n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2 \n", + " \\and\n", + " v_2 \\rightsquigarrow \\mathit{str}_2\n", + "}{\n", + " E \\vdash \n", + " e_1 \\mathbin{\\texttt{+}} e_2\n", + " \\Downarrow \\mathit{str}_1 \\mathit{str}_2 \n", + "}$\n", + "\n", + "Explain in 1-2 sentences what $\\TirName{EvalPlusString1}$ is stating.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "779388e9-f998-4212-976b-7251afdf1d86", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "533a1dfacd45dd6e555b71fee3c790b4", + "grade": true, + "grade_id": "evalplusstring1", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "$\\TirName{EvalPlusString1}$ states that if an expression $e_1$ evaluates to a string $str_1$, and another expression $e_2$ evaluates to a value $v_2$ that can be coerced into a string $str_2$, then the combined expression of $e_1 + e_2$ evalutes to the concated string of $str_1\\:str_2$." + ] + }, + { + "cell_type": "markdown", + "id": "e03fe09c-8deb-4eb0-a399-c28b25955d63", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- The $v \\rightsquigarrow \\mathit{str}$ judgment form says that value\n", + " $v$ coerces to string $\\mathit{str}$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3 (5 points)**</span> Let us\n", + "define rules that specify evaluation of the expression\n", + "$e_1 \\mathbin{\\texttt{+}} e_2$ just like in JavaScript. Give the other\n", + "rule $\\TirName{EvalPlusString\\(_2\\)}$ that concatenates strings in the\n", + "case that $e_2$ evaluates to a string.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "497dd69b-2a86-428c-8f3d-4529239a9458", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "b9a3806decfd219a093fa6b2226c5967", + "grade": true, + "grade_id": "evalplusstring2", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "$\\inferrule[EvalPlusString1]{\n", + " E\\vdash e_1 \\Downarrow v_1\n", + " \\and\n", + " v_1 \\rightsquigarrow \\mathit{str}_1\n", + " \\and\n", + " E \\vdash e_2 \\Downarrow \\mathit{str}_2\n", + "} {\n", + " E \\vdash\n", + " e_1 \\mathbin{\\texttt{+}} e_2\n", + " \\Downarrow \\mathit{str}_1 \\mathit{str}_2\n", + "}$" + ] + }, + { + "cell_type": "markdown", + "id": "164e0114-96fb-4f98-9e5e-7072d9a18d22", + "metadata": {}, + "source": [ + "Explain in 1-2 sentences why you need $\\TirName{EvalPlusString\\(1\\)}$\n", + "and $\\TirName{EvalPlusString\\(2\\)}$ together for interpreting string\n", + "concatenation like in JavaScript.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "289081c1-65cf-4d54-a523-cbc77103f62f", + "metadata": {}, + "source": [ + "Both $EvalPlusSTring1$ and $EvalPlusString2$ are required to handle different cases of string concatenation. $EvalPlusString1$ handles the cases where $e_1$ is a string and $e_2$ is coerced into one string, while $EvalPlusString2$ handles when both $e_1$ and $e_2$ are already a string." + ] + }, + { + "cell_type": "markdown", + "id": "3a977bdd-a125-4411-ab29-ae1f94fd8db5", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "You may give the rule in LaTeX math or as plain text (ascii art)\n", + "approximating the math rendering. For example,\n", + "\n", + " EvalPlusString1\n", + " E |- e1 vv str1 E |- e2 vv v2 v2 ~~> str2\n", + " -----------------------------------------------\n", + " E |- e1 + e2 vv str1 str2\n", + "\n", + "The LaTeX code for the rendered $\\TirName{EvalPlusString1}$ rule above\n", + "is as follows:\n", + "\n", + "``` latex\n", + "\\inferrule[EvalPlusString1]{\n", + " E \\vdash e_1 \\Downarrow \\mathit{str}_1\n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2\n", + " \\and\n", + " v_2 \\rightsquigarrow \\mathit{str}_2\n", + "}{\n", + " E \\vdash e_1 \\mathbin{\\texttt{+}} e_2 \\Downarrow \\mathit{str}_1 \\mathit{str}_2\n", + "}\n", + "```\n", + "\n", + "### Functions\n", + "\n", + "The inference rule defining evaluation of a function call (that\n", + "accidentally results in dynamic scoping) is as follows:\n", + "\n", + "$\\inferrule[EvalCall]{\n", + " E \\vdash e_1 \\Downarrow \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e' \n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2 \n", + " \\and\n", + " E[\\mathop{}x \\mapsto v_2] \\vdash e' \\Downarrow v' \n", + "}{\n", + " E \\vdash \n", + " e_1\\texttt{(}e_2\\texttt{)}\n", + " \\Downarrow v' \n", + "}$\n", + "\n", + "FigureĀ 2\n", + "\n", + "<span class=\"theorem-title\">**Exercise 4 (5 points)**</span> To continue\n", + "this warm up and guide our implementation of these inference rules,\n", + "write out what $\\TirName{EvalCall}$ is stating.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "6127815b-8e44-4a33-bf84-56eae852758b", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "b72bfbe88815393d455a52eb4aeeedfb", + "grade": true, + "grade_id": "3_3", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "$\\TirName{EvalCall}$ shows how to evaluate a function $e_1$, where $e_2$ is an argument passed to the function. First, we evaluate $e_2$ to a value $v_2$, and substitute the function's parameter $x$ with $v_2$ in the function $e_1$." + ] + }, + { + "cell_type": "markdown", + "id": "32627385-8210-4977-9b4c-ffd188150e6b", + "metadata": {}, + "source": [ + "## Implementing from Inference Rules\n", + "\n", + "### Abstract Syntax\n", + "\n", + "In the following, we build up to implementing an `eval` function:\n", + "\n", + "``` scala\n", + "def eval(env: Env, e: Expr): Expr\n", + "```\n", + "\n", + "This `eval` function directly corresponds the the evaluation judgment:\n", + "$E \\vdash e \\Downarrow v$, which is the operational semantics defined\n", + "above. It takes as input a value environment $E$ and an expression $e$\n", + "and returns a value $v$.\n", + "\n", + "Below is the `Expr` type defining our abstract syntax tree in Scala. If\n", + "you havenāt already, switch back to the Scala kernel and then run the\n", + "two cells below." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "id": "29c86c42", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mVar\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mConstDecl\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mN\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mB\u001b[39m\n", + "defined \u001b[32mtrait\u001b[39m \u001b[36mBop\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mBinary\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mPlus\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mEq\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mNe\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mIf\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mFun\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mCall\u001b[39m" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "trait Expr // e ::=\n", + "\n", + "case class Var(x: String) extends Expr // e ::= x\n", + "case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2\n", + "\n", + "case class N(n: Double) extends Expr // e ::= n\n", + "case class B(b: Boolean) extends Expr // e ::= b\n", + "\n", + "trait Bop // bop ::=\n", + "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop b2\n", + "\n", + "case object Plus extends Bop // bop ::= +\n", + "case object Eq extends Bop // bop ::= ===\n", + "case object Ne extends Bop // bop ::= !==\n", + "\n", + "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3\n", + "\n", + "case class Fun(x: String, e1: Expr) extends Expr // e ::= (x) => e1\n", + "case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2)" + ] + }, + { + "cell_type": "markdown", + "id": "c893fd56-f5f0-4023-b032-3b1edf5af9d2", + "metadata": {}, + "source": [ + "Numbers $n$, booleans $b$, and functions\n", + "$\\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1$ are values,\n", + "and we represent a value environment $E$ as a `Map[String, Expr]`:" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "id": "7ad1df6c", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36misValue\u001b[39m\n", + "defined \u001b[32mtype\u001b[39m \u001b[36mEnv\u001b[39m\n", + "\u001b[36mempty\u001b[39m: \u001b[32mEnv\u001b[39m = \u001b[33mMap\u001b[39m()\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mlookup\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mextend\u001b[39m" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | Fun(_, _) => true\n", + " case _ => false\n", + "}\n", + "\n", + "type Env = Map[String, Expr]\n", + "val empty: Env = Map()\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": "09e8e0df-3209-49f6-85d0-03bae67db850", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 5 (5 points)**</span> Now that we\n", + "have the AST type `Expr` defined, take your JavaScripty test program\n", + "from\n", + "<a href=\"#exr-dynamic-scoping-test\" class=\"quarto-xref\">ExerciseĀ 1</a>\n", + "and write out the AST it would parse to. This will serve as a test for\n", + "your implementation." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "id": "4499a45e", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "d6ce40f7aa1f7978936bcf6b0553fc21", + "grade": false, + "grade_id": "dynamic-scoping-test-ast", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mtestAST\u001b[39m" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def testAST: Expr = ConstDecl(\n", + " \"x\",\n", + " N(10),\n", + " ConstDecl(\n", + " \"f\",\n", + " Fun(\n", + " \"a\",\n", + " Binary(Plus, Var(\"x\"), Var(\"a\"))\n", + " ),\n", + " ConstDecl(\n", + " \"g\",\n", + " Fun(\n", + " \"b\",\n", + " ConstDecl(\n", + " \"x\",\n", + " N(20),\n", + " Call(Var(\"f\"), Var(\"b\"))\n", + " )\n", + " ),\n", + " Call(Var(\"g\"), N(-1))\n", + " )\n", + " )\n", + ")" + ] + }, + { + "cell_type": "markdown", + "id": "bb6ee383-7fee-40a8-9a5a-aec145db17c5", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Recall the difference between concrete and abstract syntax. Your AST\n", + " here will use the abstract syntax and be of type `Expr` defined\n", + " above. Therefore, the AST nodes you write in can only be\n", + " constructors of `Expr`. For example, the $\\mathbf{return}$ keyword\n", + " is in the concrete syntax but not a constructor of `Expr`.\n", + "\n", + "### Variables, Numbers, and Booleans\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6 (10 points)**</span> Implement\n", + "`eval` the evaluation judgment form $E \\vdash e \\Downarrow v$ for all\n", + "rules except $\\TirName{EvalCall}$ shown in\n", + "<a href=\"#fig-javascripty-numbers-booleans-variables-limited\"\n", + "class=\"quarto-xref\">FigureĀ 1</a>. It should be noted that this\n", + "implementation should very similar to your implementation of `eval` in\n", + "previous lab." + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "9210e992", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "0a25c2c80a37b211092a4a7e7596a6c0", + "grade": false, + "grade_id": "eval-numbers-booleans-variables-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = e match {\n", + " // EvalVar\n", + " case Var(x) => env(x)\n", + "\n", + " // EvalConstDecl\n", + " case ConstDecl(x, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val env2 = extend(env, x, v1)\n", + " eval(env2, e2)\n", + "\n", + " // EvalVal\n", + " case v if isValue(v) => v\n", + "\n", + " // EvalPlusNumber\n", + " case Binary(Plus, e1, e2) =>\n", + " val N(n1) = eval(env, e1)\n", + " val N(n2) = eval(env, e2)\n", + " N(n1 + n2)\n", + "\n", + " // EvalEquality\n", + " case Binary(bop, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val v2 = eval(env, e2)\n", + " bop match {\n", + " case Eq => B(v1 == v2)\n", + " case Ne => B(v1 != v2)\n", + " }\n", + "\n", + " // EvalIfTrue\n", + " // EvalIfFalse\n", + " case If(e1, e2, e3) => \n", + " eval(env, e1) match {\n", + " case B(true) => eval(env, e2)\n", + " case B(false) => eval(env, e3)\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "13e78183-7978-4bb2-8d93-a0ca52b443d3", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- It is most beneficial to first implement `eval` from scratch by\n", + " referencing the rules shown in\n", + " <a href=\"#fig-javascripty-numbers-booleans-variables-limited\"\n", + " class=\"quarto-xref\">FigureĀ 1</a>.\n", + "- After you implement `eval` here by following the rules, it may then\n", + " be informative to compare with your implementation from the previous\n", + " lab (that was for a larger language and with implicit type\n", + " coercions).\n", + "- You will have unmatched cases (i.e., there are no corresponding\n", + " rules), which you can leave unimplemented with `???` or the\n", + " potential for `MatchError`.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "id": "fb80bad7", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "3695ddb83d88e8f4d480e36ccd180022", + "grade": true, + "grade_id": "eval-numbers-booleans-tester", + "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: 8\u001b[0m\n", + "\u001b[32mcmd7$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[32m- should Test Case 6\u001b[0m\n", + "\u001b[32m- should Test Case 7\u001b[0m\n", + "\u001b[32m- should Test Case 8\u001b[0m\n", + "\u001b[36mRun completed in 65 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 8\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 8, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (10 points) ***\n" + ] + }, + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "val testExercise3 = test(new AnyFlatSpec {\n", + " val testcase1 = {\n", + " val e1 = N(1)\n", + " val e2 = N(2)\n", + " evalTest(Binary(Plus, e1, e2))\n", + " }\n", + " val testcase2 = {\n", + " val e1 = N(5)\n", + " val e2 = N(5)\n", + " evalTest(Binary(Eq, e1, e2)) \n", + " }\n", + " val testcase3 = {\n", + " val e1 = N(5)\n", + " val e2 = N(7)\n", + " evalTest(Binary(Eq, e1, e2))\n", + " }\n", + " val testcase4 = {\n", + " val e1 = N(5)\n", + " val e2 = N(7)\n", + " evalTest(Binary(Ne, e1, e2))\n", + " }\n", + " val testcase5 = {\n", + " val e1 = N(5)\n", + " val e2 = N(5)\n", + " evalTest(Binary(Ne, e1, e2))\n", + " }\n", + " val testcase6 = {\n", + " val e1 = N(3)\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " evalTest(ConstDecl(\"x\", e1, e2)) \n", + " }\n", + " val testcase7 = {\n", + " val e1 = Binary(Plus, N(3), N(2))\n", + " val e2 = Binary(Plus, N(1), N(1))\n", + " evalTest(If(B(true), e1, e2)) \n", + " }\n", + " val testcase8 = {\n", + " val e1 = Binary(Plus, N(3), N(2))\n", + " val e2 = Binary(Plus, N(1), N(1))\n", + " evalTest(If(B(false), e1, e2)) \n", + "\n", + " }\n", + " \n", + " it should \"Test Case 1\" in { assertResult( N(3) ) { testcase1 } }\n", + " it should \"Test Case 2\" in { assertResult( B(true) ) { testcase2 } }\n", + " it should \"Test Case 3\" in { assertResult( B(false) ) { testcase3 } }\n", + " it should \"Test Case 4\" in { assertResult( B(true) ) { testcase4 } }\n", + " it should \"Test Case 5\" in { assertResult( B(false) ) { testcase5 } }\n", + " it should \"Test Case 6\" in { assertResult( N(4) ) { testcase6 } }\n", + " it should \"Test Case 7\" in { assertResult( N(5) ) { testcase7 } }\n", + " it should \"Test Case 8\" in { assertResult( N(2) ) { testcase8 } }\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "0c8c160e-7429-46c4-91b0-be6c868100e4", + "metadata": {}, + "source": [ + "### Functions\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7 (10 points)**</span> Extend\n", + "your implementation with functions. On function calls, you need to\n", + "extend the environment for the formal parameter. Begin with what you\n", + "have from <a href=\"#exr-eval-numbers-booleans-variables\"\n", + "class=\"quarto-xref\">ExerciseĀ 6</a>." + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "id": "088b0ba2", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "98be44a3e7d41eca8854a8bccd400d3a", + "grade": false, + "grade_id": "eval-functions-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = e match {\n", + " // EvalVar\n", + " case Var(x) => env(x)\n", + "\n", + " // EvalConstDecl\n", + " case ConstDecl(x, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val env2 = extend(env, x, v1)\n", + " eval(env2, e2)\n", + "\n", + " // EvalVal\n", + " case v if isValue(v) => v\n", + "\n", + " // EvalPlusNumber\n", + " case Binary(Plus, e1, e2) =>\n", + " val N(n1) = eval(env, e1)\n", + " val N(n2) = eval(env, e2)\n", + " N(n1 + n2)\n", + "\n", + " // EvalEquality\n", + " case Binary(bop, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val v2 = eval(env, e2)\n", + " bop match {\n", + " case Eq => B(v1 == v2)\n", + " case Ne => B(v1 != v2)\n", + " }\n", + "\n", + " // EvalIfTrue\n", + " // EvalIfFalse\n", + " case If(e1, e2, e3) => \n", + " eval(env, e1) match {\n", + " case B(true) => eval(env, e2)\n", + " case B(false) => eval(env, e3)\n", + " }\n", + "\n", + " case Fun(x, e1) => Fun(x, e1)\n", + "\n", + " // EvalCall\n", + " case Call(e1, e2) => \n", + " eval(env, e1) match {\n", + " case Fun(x, e_) => \n", + " val v2 = eval(env, e2)\n", + " eval(extend(env, x, v2),e_)\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "4f776771-a0e1-4391-a514-ff044aadc445", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- This question is asking you to implement $\\TirName{EvalCall}$.\n", + "- Do not worry yet about dynamic type errors, so this will still have\n", + " some `???`s or have the possibility of `MatchError`s.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "id": "1d49dca6", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ebf02bf658d2c9645b2d1df72d32d49a", + "grade": true, + "grade_id": "eval-functions-tester", + "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: 9\u001b[0m\n", + "\u001b[32mcmd9$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[32m- should Test Case 6\u001b[0m\n", + "\u001b[32m- should Test Case 7\u001b[0m\n", + "\u001b[32m- should Test Case 8\u001b[0m\n", + "\u001b[32m- should Test Case 9\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 9\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 9, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (10 points) ***\n" + ] + }, + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "test(new AnyFlatSpec {\n", + " val testcase1 = {\n", + " val x = \"x\"\n", + " val e1 = Fun(x, Binary(Plus, Var(x), N(1)))\n", + " val e2 = N(2)\n", + " evalTest(Call(e1, e2))\n", + " }\n", + " val testcase2 = {\n", + " val x = \"x\"\n", + " val e1 = Fun(x, If(Binary(Eq, Var(x), N(0)), N(1), N(0)))\n", + " val e2 = N(0)\n", + " evalTest(Call(e1, e2))\n", + " }\n", + " val testcase3 = {\n", + " val x = \"x\"\n", + " val e1 = Fun(x, If(Binary(Eq, Var(x), N(0)), N(1), N(0)))\n", + " val e2 = N(1)\n", + " evalTest(Call(e1, e2))\n", + " }\n", + " val testcase4 = {\n", + " val x = \"x\"\n", + " val e1 = Fun(x, If(Binary(Ne, Var(x), N(0)), N(1), N(0)))\n", + " val e2 = N(1)\n", + " evalTest(Call(e1, e2))\n", + " }\n", + " val testcase5 = {\n", + " val a = \"a\"\n", + " val e1 = N(3)\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " val e3 = ConstDecl(\"x\", e1, e2)\n", + " val e4 = Fun(a, e3)\n", + " evalTest(Call(e4, N(1)))\n", + " }\n", + " val testcase6 = {\n", + " val a = \"a\"\n", + " val e1 = Binary(Plus, N(3), Var(a))\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " val e3 = ConstDecl(\"x\", e1, e2)\n", + " val e4 = Fun(a, e3)\n", + " evalTest(Call(e4, N(2)))\n", + " }\n", + " val testcase7 = {\n", + " val a = \"a\"\n", + " val f = \"f\"\n", + " val e1 = Binary(Plus, N(3), Var(a))\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " val e3 = ConstDecl(\"x\", e1, e2)\n", + " val e4 = Fun(a, e3)\n", + " val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))\n", + " evalTest(e5)\n", + " }\n", + " val testcase8 = {\n", + " val f = \"f\"\n", + " val a = \"a\"\n", + " val e1 = Binary(Plus, Var(a), Var(a))\n", + " val e2 = Fun(a, e1)\n", + " val e3 = Fun(f, Call(Var(f), N(5)))\n", + " evalTest(Call(e3, e2))\n", + " }\n", + " val testcase9 = {\n", + " val a1 = \"a1\"\n", + " val a2 = \"a2\"\n", + " val x = \"x\"\n", + " val e1 = Fun(a1, Var(x))\n", + " val e2 = ConstDecl(x, N(20), Call(e1, N(-1))) \n", + " val e3 = Fun(a2, e2)\n", + " val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))\n", + " evalTest(e4)\n", + " }\n", + "\n", + " it should \"Test Case 1\" in { assertResult( N(3) ) { testcase1 } }\n", + " it should \"Test Case 2\" in { assertResult( N(1) ) { testcase2 } }\n", + " it should \"Test Case 3\" in { assertResult( N(0) ) { testcase3 } }\n", + " it should \"Test Case 4\" in { assertResult( N(1) ) { testcase4 } }\n", + " it should \"Test Case 5\" in { assertResult( N(4) ) { testcase5 } }\n", + " it should \"Test Case 6\" in { assertResult( N(6) ) { testcase6 } }\n", + " it should \"Test Case 7\" in { assertResult( N(6) ) { testcase7 } }\n", + " it should \"Test Case 8\" in { assertResult( N(10) ) { testcase8 } }\n", + " it should \"Test Case 9\" in { assertResult( N(20) ) { testcase9 } }\n", + " \n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "ecbbe931-a561-4031-a057-ab565507f11b", + "metadata": {}, + "source": [ + "### Dynamic Typing\n", + "\n", + "In the previous lab, all expressions could be evaluated to something\n", + "(because of conversions). With functions, we encounter one of the very\n", + "few run-time errors in JavaScript: trying to call something that is not\n", + "a function. In JavaScript and in JavaScripty, calling a non-function\n", + "raises a run-time error. Such a run-time error is known as a dynamic\n", + "type error. Languages are called *dynamically typed* when they allow all\n", + "syntactically valid programs to run and check for type errors during\n", + "execution.\n", + "\n", + "We define a Scala exception" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "id": "7150ac39", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mclass\u001b[39m \u001b[36mDynamicTypeError\u001b[39m" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "case class DynamicTypeError(e: Expr) extends Exception {\n", + " override def toString = s\"TypeError: in expression $e\"\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "1a1008b1-c83d-4604-a59d-e1c0f53c816c", + "metadata": {}, + "source": [ + "to signal this case. In other words, when your interpreter discovers a\n", + "dynamic type error, it should throw this exception using the following\n", + "Scala code:\n", + "\n", + "``` scala\n", + "throw DynamicTypeError(e)\n", + "```\n", + "\n", + "The argument should be the input expression `e` to `eval` where the type\n", + "error was detected. That is, the expression where there is no possible\n", + "rule to continue. For example, in the case of calling a non-function,\n", + "the type error should be reported on the `Call` node and not any\n", + "sub-expression.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (10 points)**</span> Add\n", + "support for checking for all dynamic type errors. You should have no\n", + "possibility for a `MatchError` or a `NotImplementedError`. Start with\n", + "what you have from\n", + "<a href=\"#exr-eval-functions\" class=\"quarto-xref\">ExerciseĀ 7</a>." + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "id": "8c104880", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "f4cd95ddb270a0c91ec29e3253cfcc38", + "grade": false, + "grade_id": "eval-dynamic-typing-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m" + ] + }, + "execution_count": 11, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = e match {\n", + " // EvalVar\n", + " case Var(x) => env(x)\n", + "\n", + " // EvalConstDecl\n", + " case ConstDecl(x, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val env2 = extend(env, x, v1)\n", + " eval(env2, e2)\n", + "\n", + " // EvalVal\n", + " case v if isValue(v) => v\n", + "\n", + " // EvalPlusNumber\n", + " case Binary(Plus, e1, e2) =>\n", + " (eval(env, e1), eval(env, e2)) match {\n", + " case (N(n1), N(n2)) => N(n1+ n2)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " // EvalEquality\n", + " case Binary(bop, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val v2 = eval(env, e2)\n", + " bop match {\n", + " case Eq => B(v1 == v2)\n", + " case Ne => B(v1 != v2)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " // EvalIfTrue\n", + " // EvalIfFalse\n", + " case If(e1, e2, e3) => \n", + " eval(env, e1) match {\n", + " case B(true) => eval(env, e2)\n", + " case B(false) => eval(env, e3)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " case Fun(x, e1) => Fun(x, e1)\n", + "\n", + " // EvalCall\n", + " case Call(e1, e2) => \n", + " eval(env, e1) match {\n", + " case Fun(x, e_) => \n", + " val v2 = eval(env, e2)\n", + " eval(extend(env, x, v2),e_)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "01f6fc90-6a86-44b5-8003-60c3e881f115", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "id": "672aa11d", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "2828b9ff89630db9b066df03618b875d", + "grade": true, + "grade_id": "eval-dynamic-typing-tester", + "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: 8\u001b[0m\n", + "\u001b[32mcmd12$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[32m- should Test Case 6\u001b[0m\n", + "\u001b[32m- should Test Case 7\u001b[0m\n", + "\u001b[32m- should Test Case 8\u001b[0m\n", + "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 8\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 8, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (10 points) ***\n" + ] + }, + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "test(new AnyFlatSpec {\n", + " val testcase1 = {\n", + " val e1 = Binary(Plus, N(3), N(2))\n", + " val e2 = Binary(Plus, N(1), N(1))\n", + " evalTest(If(B(true), e1, e2)) \n", + " }\n", + " val testcase2 = {\n", + " val e1 = Binary(Plus, N(3), N(2))\n", + " val e2 = Binary(Plus, N(1), N(1))\n", + " evalTest(If(B(false), e1, e2)) \n", + "\n", + " }\n", + " val testcase3 = {\n", + " val a = \"a\"\n", + " val f = \"f\"\n", + " val e1 = Binary(Plus, N(3), Var(a))\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " val e3 = ConstDecl(\"x\", e1, e2)\n", + " val e4 = Fun(a, e3)\n", + " val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))\n", + " evalTest(e5)\n", + " }\n", + " val testcase4 = {\n", + " val f = \"f\"\n", + " val a = \"a\"\n", + " val e1 = Binary(Plus, Var(a), Var(a))\n", + " val e2 = Fun(a, e1)\n", + " val e3 = Fun(f, Call(Var(f), N(5)))\n", + " evalTest(Call(e3, e2))\n", + " }\n", + " val testcase5 = {\n", + " val a1 = \"a1\"\n", + " val a2 = \"a2\"\n", + " val x = \"x\"\n", + " val e1 = Fun(a1, Var(x))\n", + " val e2 = ConstDecl(x, N(20), Call(e1, N(-1))) \n", + " val e3 = Fun(a2, e2)\n", + " val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))\n", + " evalTest(e4)\n", + " }\n", + " val testcase6 = {\n", + " Binary(Plus, N(4), B(true))\n", + " }\n", + " val testcase7 = {\n", + " Call(N(4), N(2))\n", + " }\n", + " val testcase8 = {\n", + " Call(N(4), B(true))\n", + " }\n", + " \n", + " it should \"Test Case 1\" in { assertResult( N(5) ) { testcase1 } }\n", + " it should \"Test Case 2\" in { assertResult( N(2) ) { testcase2 } }\n", + " it should \"Test Case 3\" in { assertResult( N(6) ) { testcase3 } }\n", + " it should \"Test Case 4\" in { assertResult( N(10) ) { testcase4 } }\n", + " it should \"Test Case 5\" in { assertResult( N(20) ) { testcase5 } }\n", + " it should \"Test Case 6\" in { intercept[DynamicTypeError] {evalTest(testcase6)} }\n", + " it should \"Test Case 7\" in { intercept[DynamicTypeError] {evalTest(testcase7)} }\n", + " it should \"Test Case 8\" in { intercept[DynamicTypeError] {evalTest(testcase8)} }\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "8190241b-e967-44a0-a78a-37f727b85dee", + "metadata": {}, + "source": [ + "### Dynamic Scoping\n", + "\n", + "<span class=\"theorem-title\">**Exercise 9 (5 points)**</span> Below is a\n", + "cell that runs the AST from the test case you wrote in\n", + "<a href=\"#exr-dynamic-scoping-test-ast\"\n", + "class=\"quarto-xref\">ExerciseĀ 5</a> with your interpreter implementation." + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "id": "cdbae7a0", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m\n", + "\u001b[36mres13_1\u001b[39m: \u001b[32mExpr\u001b[39m = \u001b[33mN\u001b[39m(n = \u001b[32m19.0\u001b[39m)" + ] + }, + "execution_count": 13, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "evalTest(testAST)" + ] + }, + { + "cell_type": "markdown", + "id": "6845ef4c-e83b-4097-94a5-036e0bf8ae6f", + "metadata": {}, + "source": [ + "Does it evaluate to what your excepted? The evaluation output above\n", + "should be different from what it would evaluate to with a JavaScript\n", + "interpreter, such as Deno. Ensure that the results are different and\n", + "write below what each interpreter evaluates to.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "15aabbfc-2b58-4493-bf6a-45427c5f558a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "385ebf880935ca1bad2f2af35b2a3c98", + "grade": true, + "grade_id": "3_8_1", + "locked": false, + "points": 1, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "Yes, the value calcuated by the Scala AST implemented in exercise 5 differs from the JavaScript function implemented in exercise 1." + ] + }, + { + "cell_type": "markdown", + "id": "18749b90-2bc0-401e-b6d0-c223e32ab4f6", + "metadata": {}, + "source": [ + "It seems like we implemented dynamic scoping instead of static scoping.\n", + "Explain the failed test case and how your interpreter behaves\n", + "differently compared to a JavaScript interpreter. Furthermore, think\n", + "about why this is the case and explain in 1-2 sentences *why* your\n", + "interpreter behaves differently.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "0d4befe8-ffbf-4eda-be18-5a634ef592fb", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "691ba88661c76c567302965e44648ff8", + "grade": true, + "grade_id": "3_8_2", + "locked": false, + "points": 4, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "YOUR ANSWER HERE" + ] + }, + { + "cell_type": "markdown", + "id": "0f7201df-c431-4b7f-acad-998e2da4d029", + "metadata": {}, + "source": [ + "### Closures\n", + "\n", + "In order to fix our dynamic scoping issue, we will implement explicit\n", + "closures. That is, when functions are evaluated, they will use the value\n", + "environment in which they were defined.\n", + "\n", + "Here are the updates to our abstract syntax.\n", + "\n", + "$$\n", + "\\begin{array}{rrrll}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + "\\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + "\\mid e_1\\texttt{(}e_2\\texttt{)}\n", + "\\\\\n", + "\\text{values} & v& \\mathrel{::=}& \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1[E]\n", + "\\\\\n", + "\\text{variables} & x\n", + "\\end{array}\n", + "$$\n", + "\n", + "Notice that now, closures are values (and functions are not), while\n", + "functions are still expressions.\n", + "\n", + "We also add the $\\TirName{EvalFun}$ rule to our operational semantics,\n", + "and edit the $\\TirName{EvalCall}$ rule, seen below.\n", + "\n", + "$\\fbox{$E \\vdash e \\Downarrow v$}$\n", + "\n", + "$\\inferrule[EvalFun]{\n", + "}{\n", + " E \\vdash \n", + " \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e\n", + " \\Downarrow\n", + " \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e [ E]\n", + " {\n", + " }\n", + "}$\n", + "\n", + "$\\inferrule[EvalCall]{\n", + " E \\vdash e_1 \\Downarrow \\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e'[E'] \n", + " \\and\n", + " E \\vdash e_2 \\Downarrow v_2 \n", + " \\and\n", + " E'[\\mathop{}x \\mapsto v_2] \\vdash e' \\Downarrow v' \n", + "}{\n", + " E \\vdash \n", + " e_1\\texttt{(}e_2\\texttt{)}\n", + " \\Downarrow v' \n", + "}$\n", + "\n", + "In order to implement this, we will add `Closure` to our `Expr` type,\n", + "and edit other helper functions as needed." + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "id": "896b02a7", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mclass\u001b[39m \u001b[36mClosure\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36misValue\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mextend\u001b[39m" + ] + }, + "execution_count": 14, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "case class Closure(fun: Fun, env: Env) extends Expr \n", + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | Closure(_, _) => true\n", + " case _ => false\n", + "}\n", + "def extend(env: Env, x: String, v: Expr): Env = {\n", + " require(isValue(v))\n", + " env + (x -> v)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "740f737e-0e78-483e-88d5-a867e41f8251", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 10 (10 points)**</span> With the\n", + "above, implement a new version of `eval` that uses closures to enforce\n", + "static scoping. Begin with what you have from\n", + "<a href=\"#exr-eval-dynamic-typing\" class=\"quarto-xref\">ExerciseĀ 8</a>." + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "id": "ab078f65", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "323612cac66795535f6a9e1e66b84bd8", + "grade": false, + "grade_id": "eval-closures-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = e match {\n", + " // EvalVar\n", + " case Var(x) => env(x)\n", + "\n", + " // EvalConstDecl\n", + " case ConstDecl(x, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val env2 = extend(env, x, v1)\n", + " eval(env2, e2)\n", + "\n", + " // EvalVal\n", + " case v if isValue(v) => v\n", + "\n", + " // EvalPlusNumber\n", + " case Binary(Plus, e1, e2) =>\n", + " (eval(env, e1), eval(env, e2)) match {\n", + " case (N(n1), N(n2)) => N(n1+ n2)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " // EvalEquality\n", + " case Binary(bop, e1, e2) =>\n", + " val v1 = eval(env, e1)\n", + " val v2 = eval(env, e2)\n", + " (v1, v2) match {\n", + " case (B(b1), B(b2)) => bop match {\n", + " case Eq => B(b1 == b2)\n", + " case Ne => B(b1 != b2)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + " case (N(n1), N(n2)) => bop match {\n", + " case Eq => B(n1 == n2)\n", + " case Ne => B(n1 != n2)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " // EvalIfTrue\n", + " // EvalIfFalse\n", + " case If(e1, e2, e3) => \n", + " eval(env, e1) match {\n", + " case B(true) => eval(env, e2)\n", + " case B(false) => eval(env, e3)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "\n", + " case Fun(x, e1) => Closure(Fun(x, e1), env)\n", + " \n", + " // EvalCall\n", + " case Call(e1, e2) => \n", + " eval(env, e1) match {\n", + " case Closure(Fun(x, e_), closureEnv) => \n", + " val v2 = eval(env, e2)\n", + " eval(extend(closureEnv, x, v2), e_)\n", + " case _ => throw DynamicTypeError(e)\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "14520cd2-7937-447a-9b26-9fd0807bd8ef", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "a57c1165", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "6f434a07eee475c3bcb3ca595c71cbcf", + "grade": true, + "grade_id": "eval-closures-tester", + "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: 6\u001b[0m\n", + "\u001b[32mcmd19$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[32m- should Test Case 6\u001b[0m\n", + "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 6\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (10 points) ***\n" + ] + }, + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m" + ] + }, + "execution_count": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "test(new AnyFlatSpec {\n", + " val testcase1 = {\n", + " val a = \"a\"\n", + " val f = \"f\"\n", + " val e1 = Binary(Plus, N(3), Var(a))\n", + " val e2 = Binary(Plus, Var(\"x\"), N(1))\n", + " val e3 = ConstDecl(\"x\", e1, e2)\n", + " val e4 = Fun(a, e3)\n", + " val e5 = ConstDecl(f, e4, Call(Var(f), N(2)))\n", + " evalTest(e5)\n", + " }\n", + " val testcase2 = {\n", + " val a1 = \"a1\"\n", + " val a2 = \"a2\"\n", + " val x = \"x\"\n", + " val e1 = Fun(a1, Var(x))\n", + " val e2 = ConstDecl(x, N(40), Call(e1, N(-1))) \n", + " val e3 = Fun(a2, e2)\n", + " val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))\n", + " evalTest(e4)\n", + " }\n", + " val testcase3 = {\n", + " val f = \"f\"\n", + " val a = \"a\"\n", + " val e1 = Binary(Plus, Var(a), Var(a))\n", + " val e2 = Fun(a, e1)\n", + " val e3 = Fun(f, Call(e2, N(5)))\n", + " evalTest(Call(e3, e2))\n", + " }\n", + " val testcase4 = {\n", + " Call(N(4), B(true))\n", + " }\n", + " val testcase5 = {\n", + " Binary(Ne, B(false), Fun(\"a\", N(2)))\n", + " }\n", + " val testcase6 = {\n", + " evalTest(ConstDecl( \"x\", N(30), ConstDecl(\"f\", Fun(\"a\", Var(\"x\")), ConstDecl(\"g\", Fun( \"b\", ConstDecl(\"x\", N(20), Call(Var(\"f\"), N(-1)))),Call(Var(\"g\"), N(-1))))))\n", + " }\n", + " it should \"Test Case 1\" in { assertResult( N(6) ) { testcase1 } }\n", + " it should \"Test Case 2\" in { assertResult( N(40) ) { testcase2 } }\n", + " it should \"Test Case 3\" in { assertResult( N(10) ) { testcase3 } }\n", + " it should \"Test Case 4\" in { intercept[DynamicTypeError] {evalTest(testcase4)} }\n", + " it should \"Test Case 5\" in { intercept[DynamicTypeError] {evalTest(testcase5)} }\n", + " it should \"Test Case 6\" in { assertResult( N(30) ) { testcase6 } }\n", + "}, 10)" + ] + }, + { + "cell_type": "markdown", + "id": "e3845b97-e1d3-4000-863e-b8a89c9ee8f0", + "metadata": {}, + "source": [ + "This code tests your new implementation against the dynamic scoping test\n", + "case you wrote:" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "id": "91685c58", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mevalTest\u001b[39m\n", + "\u001b[36mres17_1\u001b[39m: \u001b[32mExpr\u001b[39m = \u001b[33mN\u001b[39m(n = \u001b[32m9.0\u001b[39m)" + ] + }, + "execution_count": 17, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "evalTest(testAST)" + ] + }, + { + "cell_type": "markdown", + "id": "475e61c7-1151-4e8b-8657-70427db65b45", + "metadata": {}, + "source": [ + "If youāre implementation is correct, it should evaluate to what a\n", + "JavaScript interpreter evaluates it to.\n", + "\n", + "## Implementing Recursive Functions (Accelerated)\n", + "\n", + "The remaining exercises are for those who want to go deeper and take an\n", + "āacceleratedā version of this course.\n", + "\n", + "We begin by extending our abstract syntax to allow for recursive\n", + "functions. To call a function within itself, we permit functions to have\n", + "a variable identifier to refer to itself. If the identifier is present,\n", + "then it can be used for recursion.\n", + "\n", + "$$\\begin{array}{rlrll}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + "x^{?}\\texttt{(}y\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + "\\mid e_1\\texttt{(}e_2\\texttt{)}\n", + "\\\\\n", + "\\text{optional variables} & x^{?}& \\mathrel{::=}& x\\mid\\varepsilon\n", + "\\\\\n", + "\\text{variables} & x\n", + "\\end{array}$$\n", + "\n", + "### Defining Inference Rules\n", + "\n", + "<span class=\"theorem-title\">**Exercise 11 (10 points)**</span> To allow\n", + "for recursion, at a function call, we must bind the function identifier\n", + "to the function value when evaluating the function body. Give a\n", + "inference rule called $\\TirName{EvalCallRec}$ that describes this\n", + "semantics.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "ad4ad55f-d27a-4157-8f06-6aed2fd50e0a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "d306618c54a8f200a10728d1ea2b2305", + "grade": true, + "grade_id": "3_10", + "locked": false, + "points": 5, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "YOUR ANSWER HERE" + ] + }, + { + "cell_type": "markdown", + "id": "1a99119f-80e5-42eb-891d-f1ec6b1d4d12", + "metadata": {}, + "source": [ + "### Writing a Test Case\n", + "\n", + "<span class=\"theorem-title\">**Exercise 12 (1 point)**</span> Write a\n", + "function `sumOneToN` that computes the sum from `1` to `n` using the\n", + "fragment of JavaScripty in this assignment.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "667f4cf9-6405-4a29-8cf5-ee5b3ce50a16", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "0a8e3b9d2ad3e3621c5e8ee66a8170c4", + "grade": true, + "grade_id": "3_11_1", + "locked": false, + "points": 1, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "function sumOneToN(n) \n", + " ???" + ] + }, + { + "cell_type": "markdown", + "id": "c6fe0d18-fcb6-4eb6-af25-e8372058523c", + "metadata": {}, + "source": [ + "In order to allow for recursive, we must edit our `Fun` constructor to\n", + "accept an optional variable. (We must also re-run the other constructor\n", + "and helper functions that rely on `Fun`.)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5bc4fe97", + "metadata": {}, + "outputs": [], + "source": [ + "case class Fun(xopt: Option[String], y: String, e1: Expr) extends Expr \n", + "case class Closure(fun: Fun, env: Env) extends Expr \n", + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | Closure(_, _) => true\n", + " case _ => false\n", + "}\n", + "def extend(env: Env, x: String, v: Expr): Env = {\n", + " require(isValue(v))\n", + " env + (x -> v)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "b361c93d-5c0b-4cea-8515-d798783521ea", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 13 (4 points)**</span> Now that\n", + "we have an abstract syntax tree node to write recursive functions,\n", + "create an `Expr` that is a recursive function which computes the sum\n", + "from `1` to a parameter `n`. This will be used in a test case for an\n", + "updated version of `eval`. Write out the AST that your `sumOneToN`\n", + "function will be parsed to.\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "142ec74a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "0c1c0102d524a6597926587b45dfbd78", + "grade": true, + "grade_id": "recursive-functions-test-ast", + "locked": false, + "points": 4, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "val recTestAST: Expr = \n", + " ???" + ] + }, + { + "cell_type": "markdown", + "id": "52ce45fd-d258-4ced-aa1c-f1cf0812fc54", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 14 (10 points)**</span> Rewrite\n", + "your `eval` function to handle recursive functions." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "685ecd67", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "05f4d8036bb004554dd00637c099d8c1", + "grade": false, + "grade_id": "eval-recursive-functions-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "def eval(env: Env, e: Expr): Expr = \n", + " ???" + ] + }, + { + "cell_type": "markdown", + "id": "612e3300-ea45-4a6a-9567-d5d530620036", + "metadata": {}, + "source": [ + "This cell tests your implementation against your test case `sumOneToN`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "a878557b", + "metadata": {}, + "outputs": [], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "test(new AnyFlatSpec {\n", + " val yourSumOneToN = evalTest(Call(recTestAST, N(10)))\n", + " it should \"Compute 1 to N of 10 correctly\" in { assertResult( N(55) ) { yourSumOneToN } }\n", + "}, 5)" + ] + }, + { + "cell_type": "markdown", + "id": "e14f1826-f968-40ad-a96c-20a4e266da27", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "cf27f9fb", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "433dad759b222d03c1d3f041cfe9a2f6", + "grade": true, + "grade_id": "evall-recursive-functions-tester", + "locked": true, + "points": 10, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [], + "source": [ + "def evalTest(e: Expr): Expr = {\n", + " eval(empty, e)\n", + "}\n", + "test(new AnyFlatSpec {\n", + " val testcase1 = {\n", + " val f = \"f\"\n", + " val x = \"x\"\n", + " val fbody = If(\n", + " Binary(Eq, Var(x), N(10)),\n", + " Var(x),\n", + " Binary(Plus, Var(x), Call(Var(f), Binary(Plus, Var(x), N(1))))\n", + " )\n", + " val e1 = Fun(Some(f), x, fbody)\n", + " val e2 = N(3) \n", + " evalTest(Call(e1, e2)) \n", + " }\n", + " val testcase2 = {\n", + " val a1 = \"a1\"\n", + " val a2 = \"a2\"\n", + " val x = \"x\"\n", + " val e1 = Fun(None, a1, Var(x))\n", + " val e2 = ConstDecl(x, N(40), Call(e1, N(-1))) \n", + " val e3 = Fun(None, a2, e2)\n", + " val e4 = ConstDecl(x, N(10), Call(e3, N(-1)))\n", + " evalTest(e4)\n", + " }\n", + " \n", + " it should \"Test Case 1\" in { assertResult( N(52) ) { testcase1 } }\n", + " it should \"Test Case 2\" in { assertResult( N(40) ) { testcase2 } }\n", + "\n", + "}, 5)" + ] + } + ], + "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/lab3/build.sbt b/lab3/build.sbt new file mode 100644 index 0000000..4d86186 --- /dev/null +++ b/lab3/build.sbt @@ -0,0 +1,46 @@ +name := "pppl-lab3" + +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: _*)
\ No newline at end of file diff --git a/lab3/project/build.properties b/lab3/project/build.properties new file mode 100644 index 0000000..ee4c672 --- /dev/null +++ b/lab3/project/build.properties @@ -0,0 +1 @@ +sbt.version=1.10.1 diff --git a/lab3/small-step-lab.ipynb b/lab3/small-step-lab.ipynb new file mode 100644 index 0000000..4d5ffab --- /dev/null +++ b/lab3/small-step-lab.ipynb @@ -0,0 +1,1335 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "7ec161ff", + "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": null, + "id": "3d65dedf", + "metadata": {}, + "outputs": [], + "source": [ + "val NAME = \"\"\n", + "val COLLABORATORS = \"\"" + ] + }, + { + "cell_type": "markdown", + "id": "74474148", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "4d8f8547-4bad-42d0-8621-75e17d4b6741", + "metadata": {}, + "source": [ + "$\\newcommand{\\TirName}[1]{\\text{#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: Small-Step Operational Semantics\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", + "<!-- 18 Operational Semantics -->\n", + "\n", + "<!-- 19 Functions and Dynamic Scoping -->\n", + "\n", + "<!-- 20 Big-Step Exercise -->\n", + "\n", + "<!-- 21 Evaluation Order -->\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 a big-step and a small-step operational\n", + " semantics;\n", + "- evaluation order; and\n", + "- substitution and program transformation.\n", + "\n", + "Functional Programming Skills \n", + "Iteration. Introduction to higher-order functions.\n", + "\n", + "Programming Language Ideas \n", + "Semantics: evaluation order. Small-step operational semantics.\n", + "Substitution and program transformation.\n", + "\n", + "### Instructions\n", + "\n", + "A version of project files for this lab resides in the public\n", + "[pppl-lab3](https://github.com/csci3155/pppl-lab3) 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 `Lab3.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 `Lab3Spec.scala` file. In the\n", + "`Lab3Spec.scala`, there is empty test class `Lab3StudentSpec` that you\n", + "can use to separate your tests from the given tests in the `Lab3Spec`\n", + "class. You are also likely to edit `Lab3.worksheet.sc` for any scratch\n", + "work. You can also use `Lab3.worksheet.js` to write and experiment in a\n", + "JavaScript file that you can then parse into a JavaScripty AST (see\n", + "`Lab3.worksheet.sc`).\n", + "\n", + "If you like, you may use this notebook for experimentation. However,\n", + "**please make sure your code is in `Lab3.scala`; code in this notebook\n", + "will not graded.**\n", + "\n", + "Note that there is a section with concept exercises\n", + "(<a href=\"#sec-concept-exercises-small-step-lab\"\n", + "class=\"quarto-xref\">SectionĀ 6</a>). Make sure to complete the concept\n", + "exercises in that section and **turn in this file as part of your\n", + "submission for the concept exercises**. However, all code and testing\n", + "exercises from other sections are submitted in `Lab3.scala` or\n", + "`Lab3Spec.scala`.\n", + "\n", + "Recall that you need to switch kernels between running JavaScript and\n", + "Scala cells.\n", + "\n", + "## Small-Step Interpreter: JavaScripty Functions\n", + "\n", + "We consider the same JavaScripty variant as in the previous exercise on\n", + "big-step operational semantics (**?@sec-big-step-interpreter-exercise**)\n", + "where the interesting language feature are first-class functions:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "52da72d3", + "metadata": {}, + "outputs": [], + "source": [ + "trait Expr\n", + "case class Fun(xopt: Option[String], y: String, e1: Expr) extends Expr // e ::= x?(y) => e1\n", + "case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2) " + ] + }, + { + "cell_type": "markdown", + "id": "8fcd8270-9c1f-45de-a144-5658d132eeb9", + "metadata": {}, + "source": [ + "We consider a `Fun` constructor for representing JavaScripty function\n", + "literals. This version of `Fun` allows for named functions. When a\n", + "function expression\n", + "$x\\texttt{(}y\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e'$ has a name,\n", + "then it is can be recursive. As noted previously about recursive\n", + "functions (**?@sec-recursive-functions**), variable $x$ is an additional\n", + "formal parameter, and the function body $e'$ may have free variable uses\n", + "of $x$. The variable $x$ gets bound to itself (i.e., the function value\n", + "for $x\\texttt{(}y\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e'$) on a\n", + "function call.\n", + "\n", + "In the abstract syntax representation, the `xopt: Option[String]`\n", + "parameter in our `Fun` constructor is `None` if there is no identifier\n", + "present (cannot be used recursively), or `Some(x: String)` if there is\n", + "an identifier, `x`, present (can be used recursively).\n", + "\n", + "In this lab, we will do two things. First, we will move to implementing\n", + "a small-step interpreter with a function `step` that takes an `e: Expr`\n", + "and returns a one-step reduction of `e`. A small-step interpreter makes\n", + "explicit the evaluation order of expressions. Second, we will remove\n", + "environments and instead use a language semantics based on substitution.\n", + "This change will result in static, lexical scoping without needing\n", + "closures, thus demonstrating another way to fix dynamical scoping.\n", + "\n", + "These two changes are orthogonal, that is, one could implement a\n", + "big-step interpreter using substitution (as in\n", + "**?@sec-big-step-substitution**) or a small-step interpreter using\n", + "environments. Substitution is a fairly simple way to get lexical\n", + "scoping, but in practice, it is rarely used because it is not the most\n", + "efficient implementation.\n", + "\n", + "## Static Scoping\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (Substitute)**</span> Since our\n", + "implementation requires substitution, we begin by implementing\n", + "`substitute`, which substitutes value `v` for all *free* occurrences of\n", + "variable `x` in expression `e`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2b7556f9", + "metadata": {}, + "outputs": [], + "source": [ + "def substitute(e: Expr, v: Expr, x: String): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "55d4fa8c-6cbc-4798-9f06-477ebfc236fc", + "metadata": {}, + "source": [ + "We advise defining `substitute` by induction on `e`. The cases to be\n", + "careful about are `ConstDecl` and `Fun` because these are the variable\n", + "binding constructs (as discussed in the reading on substitution in\n", + "**?@sec-substitution**). In particular, calling `substitute` on\n", + "expression\n", + "\n", + "``` typescript\n", + "a; { const a = 4; a }\n", + "```\n", + "\n", + "with value `3` for variable `a` should return\n", + "\n", + "``` typescript\n", + "3; { const a = 4; a }\n", + "```\n", + "\n", + "not\n", + "\n", + "``` typescript\n", + "3; { const a = 4; 3 }\n", + "```\n", + "\n", + "This function is a helper for the `step` function, but you might want to\n", + "implement all of the cases of `step` that do not require `substitute`\n", + "first.\n", + "\n", + "## Iteration\n", + "\n", + "Our `step` performs a single reduction step. We may want to test it by\n", + "repeatedly calling it with an expression until reducing to value. Thus,\n", + "from a software engineering standpoint, you might want to evolve the\n", + "`iterate` function described below together with your implementation of\n", + "`step`.\n", + "\n", + "This idea of repeatedly performing an action until some condition is\n", + "satisfied is a loop or iteration. We have seen that we can iterate with\n", + "a tail-recursive helper function. For example, consider the `sumTo`\n", + "function that sums the integers from `0` to `n`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4c8c6cd3", + "metadata": {}, + "outputs": [], + "source": [ + "def sumTo(n: Int): Int = {\n", + " def loop(acc: Int, i: Int): Int = {\n", + " require(n >= 0)\n", + " if (i > n) acc\n", + " else loop(acc + i, i + 1)\n", + " }\n", + " loop(0, 0)\n", + "}\n", + "sumTo(100)" + ] + }, + { + "cell_type": "markdown", + "id": "8add8f1e-fc70-4f2e-8198-76fbfd8b00b0", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 2 (Iterate with Error\n", + "Side-Effects)**</span> Because this pattern is so common, we want to get\n", + "practice refactoring this pattern into a higher-order function. We are\n", + "implementing a library function that a client like `sumTo` can use:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "79d0ad51", + "metadata": {}, + "outputs": [], + "source": [ + "def iterateBasic[A](acc0: A)(stepi: (A, Int) => Option[A]): A = {\n", + " def loop(acc: A, i: Int): A = ???\n", + " loop(acc0, 0)\n", + "}\n", + "\n", + "def sumTo(n: Int) = {\n", + " iterate(0) { case (acc, i) =>\n", + " require(n >= 0)\n", + " if (i > n) None\n", + " else Some(acc + i)\n", + " }\n", + "}\n", + "sumTo(100)" + ] + }, + { + "cell_type": "markdown", + "id": "5bbddb8d-9f02-4123-b7da-6427b0f8fbef", + "metadata": {}, + "source": [ + "The `iterate` function calls iterates (i.e., repeatedly calls) the\n", + "callback `stepi` until it returns `None` starting from `acc0: A`. Note\n", + "that `iterate` is a generic in the accumulation type `A`. The `stepi`\n", + "callback takes the current accumulator of type `A` and the iteration\n", + "number as an `Int` and indicates continuing by returning `Some(acc)` for\n", + "some next accumulator value `acc`. We see how `sumTo` can use `iterate`.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3 (Iterate with Error\n", + "Values)**</span> One unfortunate aspect of the above is that `sumTo`\n", + "āexits `iterate` with an errorā by throwing an exception (i.e., with the\n", + "`require(n >= 0)`). Let us refactor `iterate` to allow for explicit\n", + "error values using `Either[Err, A]`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "cd23905f", + "metadata": {}, + "outputs": [], + "source": [ + "def iterate[Err, A](acc0: A)(stepi: (A, Int) => Option[Either[Err, A]]): Either[Err, A] = {\n", + " def loop(acc: A, i: Int): Either[Err, A] = ???\n", + " loop(acc0, 0)\n", + "}\n", + "\n", + "def sumTo(n: Int): Either[IllegalArgumentException, Int] = {\n", + " iterate(0) { case (acc, i) =>\n", + " if (n < 0) Some(Left(new IllegalArgumentException(\"requirement failed\")))\n", + " else if (i > n) None\n", + " else Some(Right(acc + i))\n", + " }\n", + "}\n", + "sumTo(100)\n", + "sumTo(-1)" + ] + }, + { + "cell_type": "markdown", + "id": "bbbe0657-2fe0-4c51-b135-b7a1a6969049", + "metadata": {}, + "source": [ + "The `iterate` is now parametrized by an error type `Err` and returns an\n", + "`Either[Err, A]`. The `stepi` callback should return `None` if it wants\n", + "to stop normally, `Some(Left(err))` if it wants to stop with an error,\n", + "and `Some(Right(acc)` if it wants to continue with an accumulator value\n", + "`acc`.\n", + "\n", + "We can imagine that we can imagine how we can use `iterate` as a library\n", + "function to iterate your `step` implementation. In particular, this is\n", + "how `iterate` will be used to iterate `step` while adding some debugging\n", + "output:\n", + "\n", + "``` scala\n", + "def iterateStep(e: Expr) = {\n", + " require(closed(e), s\"iterateStep: ${e} not closed\")\n", + " if (debug) {\n", + " println(\"------------------------------------------------------------\")\n", + " println(\"Evaluating with step ...\")\n", + " }\n", + " val v = iterate(e) { (e: Expr, n: Int) =>\n", + " if (debug) { println(s\"Step $n: $e\") }\n", + " if (isValue(e)) None else Some(step(e))\n", + " }\n", + " if (debug) { println(\"Value: \" + v) }\n", + " v\n", + "}\n", + "```\n", + "\n", + "Of particular interest is the anonymous function passed to `iterate`\n", + "that calls your implementation of `step`.\n", + "\n", + "## Small-Step Interpreter\n", + "\n", + "In this section, we implement the one-step evaluation judgment form\n", + "$e \\longrightarrow r$ that says, āExpression $e$ can take one step of\n", + "evaluation to a step-result $r$.ā\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{step-results} & r& \\mathrel{::=}& \\mathop{\\mathsf{typeerror}}e \\mid e'\n", + "\\end{array}\n", + "$$\n", + "\n", + "A step-result $r$ is either a $\\mathop{\\mathsf{typeerror}}e$ indicating\n", + "a dynamic type error in attempting to reduce $e$ or a successful\n", + "one-step reduction to an expression $e'$.\n", + "\n", + "We represent a step-result $r$ in Scala using a type\n", + "`Either[DynamicTypeError, Expr]`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "25bea4a5", + "metadata": {}, + "outputs": [], + "source": [ + "case class DynamicTypeError(e: Expr) {\n", + " override def toString = s\"TypeError: in expression $e\"\n", + "}\n", + "type Result = Either[DynamicTypeError, Expr] // r ::= typeerror e | e" + ] + }, + { + "cell_type": "markdown", + "id": "45af4baf-ce37-41a5-9eaf-4f12c47627d7", + "metadata": {}, + "source": [ + "Note that unlike before, `DynamicTypeError` is not an `Exception`, so it\n", + "cannot be `throw`n.\n", + "\n", + "The small-step semantics that we should implement are given in the\n", + "section below (<a href=\"#sec-small-step-operational-semantics\"\n", + "class=\"quarto-xref\">SectionĀ 5</a>). The language we implement is\n", + "JavaScripty with numbers, booleans, strings, $\\mathbf{undefined}$,\n", + "printing, and first-class functions. It is a simpler language than the\n", + "previous lab because we remove type coercions (except to booleans) and\n", + "replace most coercion cases with dynamic type error\n", + "$\\mathop{\\mathsf{typeerror}}e$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 4 (Step without Dynamic Type\n", + "Checking)**</span> We advise first implementing the cases restricted to\n", + "judgments of the form $e \\longrightarrow e'$, that is, implement the\n", + "$\\TirName{Do}$ and $\\TirName{Search}$ rules while ignoring the\n", + "$\\TirName{TypeError}$ and $\\TirName{Propagate}$ rules. Start with\n", + "implementing a `stepBasic` function with type:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2fa3e363", + "metadata": {}, + "outputs": [], + "source": [ + "def stepBasic(e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "706787b6-5fe2-406f-9a50-0d6ad8ea04ea", + "metadata": {}, + "source": [ + "That is, just crash with a `MatchError` exception if your `step`\n", + "encounters any ill-typed expression `e`.\n", + "\n", + "The suggested practice here is to read some rules, write a few tests for\n", + "those rules, and implement the cases for those tests.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 5 (Step with Dynamic Type\n", + "Checking)**</span> Then, copy your code from `stepBasic` to `stepCheck`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "d7aa264c", + "metadata": {}, + "outputs": [], + "source": [ + "def stepCheck(e: Expr): Either[DynamicTypeError, Expr] = ???" + ] + }, + { + "cell_type": "markdown", + "id": "1ba099a1-963d-4319-b463-73f302d883d4", + "metadata": {}, + "source": [ + "to then add dynamic type checking. You will likely need to refactor your\n", + "code to satisfy the new types before implementing the\n", + "$\\TirName{TypeError}$ and $\\TirName{Propagate}$ rules.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6 (To Boolean)**</span> You will\n", + "need to implement a `toBoolean` function to convert JavaScripty values\n", + "to booleans, following the $\\TirName{ToBoolean}$ rules in\n", + "<a href=\"#sec-small-step-operational-semantics\"\n", + "class=\"quarto-xref\">SectionĀ 5</a>." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "681e068d", + "metadata": {}, + "outputs": [], + "source": [ + "def toBoolean(e: Expr): Boolean = ???" + ] + }, + { + "cell_type": "markdown", + "id": "4b64c82f-2cc5-4520-b729-10c8aca232c4", + "metadata": {}, + "source": [ + "However, you will not need any other type coercion functions here.\n", + "\n", + "#### Notes\n", + "\n", + "- Note that the tests call the `step` function that is originally\n", + " defined as:\n", + "\n", + " ``` scala\n", + " //def step(e: Expr): Either[DynamicTypeError, Expr] = Right(stepBasic(e))\n", + " def step(e: Expr): Either[DynamicTypeError, Expr] = stepCheck(e)\n", + " ```\n", + "\n", + " You can first test `stepBasic` by uncommenting the first line and\n", + " commenting out the second line.\n", + "\n", + "- Note that the provided tests are minimal. You will want to add your\n", + " own tests to cover most language features.\n", + "\n", + "## Small-Step Operational Semantics\n", + "\n", + "In this section, we give the small-step operational semantics for\n", + "JavaScripty with numbers, booleans, strings, $\\mathbf{undefined}$,\n", + "printing, and first-class functions. We have type coercions to booleans\n", + "but otherwise use dynamic type error for other cases.\n", + "\n", + "We write ${}[v/x]e$ for substituting value $v$ for all free occurrences\n", + "of the variable $x$ in expression $e$ (i.e., a call to `substitute`).\n", + "\n", + "It is informative to compare the small-step semantics used in this lab\n", + "and the big-step semantics from last homework.\n", + "\n", + "### Do Rules\n", + "\n", + "$\\fbox{$e \\longrightarrow e'$}$\n", + "\n", + "$\\inferrule[DoNeg]{\n", + " n' = - n_1\n", + "}{\n", + " \\mathop{\\texttt{-}} n_1 \\longrightarrow n'\n", + "}$\n", + "\n", + "$\\inferrule[DoArith]{\n", + " n' = n_1 \\mathbin{\\mathit{bop}}n_2\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{-}, \\texttt{*}, \\texttt{/} \\right\\}\n", + "}{\n", + " n_1 \\mathbin{\\mathit{bop}}n_2 \\longrightarrow n'\n", + "}$\n", + "\n", + "$\\inferrule[DoPlusString]{\n", + " \\mathit{str}' = \\mathit{str}_1 \\mathit{str}_2\n", + "}{\n", + " \\mathit{str}_1 \\mathbin{\\texttt{+}} \\mathit{str}_2 \\longrightarrow\\mathit{str}'\n", + "}$\n", + "\n", + "$\\inferrule[DoInequalityNumber]{\n", + " b' = n_1 \\mathbin{\\mathit{bop}}n_2\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " n_1 \\mathbin{\\mathit{bop}}n_2 \\longrightarrow b'\n", + "}$\n", + "\n", + "$\\inferrule[DoInequalityString]{\n", + " b' = \\mathit{str}_1 \\mathbin{\\mathit{bop}}\\mathit{str}_2\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " \\mathit{str}_1 \\mathbin{\\mathit{bop}}\\mathit{str}_2 \\longrightarrow b'\n", + "}$\n", + "\n", + "$\\inferrule[DoEquality]{\n", + " b' = (v_1 \\mathbin{\\mathit{bop}}v_2)\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{===}, \\texttt{!==} \\right\\}\n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}}v_2 \\longrightarrow b'\n", + "}$\n", + "\n", + "$\\inferrule[DoNot]{\n", + " v_1 \\rightsquigarrow b_1\n", + "}{\n", + " \\mathop{\\texttt{!}} v_1 \\longrightarrow\\neg b_1\n", + "}$\n", + "\n", + "$\\inferrule[DoAndTrue]{\n", + " v_1 \\rightsquigarrow \\mathbf{true}\n", + "}{\n", + " v_1 \\mathbin{\\texttt{\\&\\&}} e_2 \\longrightarrow e_2\n", + "}$\n", + "\n", + "$\\inferrule[DoAndFalse]{\n", + " v_1 \\rightsquigarrow \\mathbf{false}\n", + "}{\n", + " v_1 \\mathbin{\\texttt{\\&\\&}} e_2 \\longrightarrow v_1\n", + "}$\n", + "\n", + "$\\inferrule[DoOrTrue]{\n", + " v_1 \\rightsquigarrow \\mathbf{true}\n", + "}{\n", + " v_1 \\mathbin{\\texttt{||}} e_2 \\longrightarrow v_1\n", + "}$\n", + "\n", + "$\\inferrule[DoOrFalse]{\n", + " v_1 \\rightsquigarrow \\mathbf{false}\n", + "}{\n", + " v_1 \\mathbin{\\texttt{||}} e_2 \\longrightarrow e_2\n", + "}$\n", + "\n", + "$\\inferrule[DoIfTrue]{\n", + " v_1 \\rightsquigarrow \\mathbf{true}\n", + "}{\n", + " v_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_2\n", + "}$\n", + "\n", + "$\\inferrule[DoIfFalse]{\n", + " v_1 \\rightsquigarrow \\mathbf{false}\n", + "}{\n", + " v_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_3\n", + "}$\n", + "\n", + "$\\inferrule[DoSeq]{\n", + "}{\n", + " v_1 \\mathbin{\\texttt{,}} e_2 \\longrightarrow e_2\n", + "}$\n", + "\n", + "$\\inferrule[DoPrint]{\n", + " \\text{$v_1$ printed}\n", + "}{\n", + " \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}v_1\\texttt{)} \\longrightarrow\\mathbf{undefined}\n", + "}$\n", + "\n", + "$\\inferrule[DoConst]{\n", + "}{\n", + " \\mathbf{const}\\;x\\;\\texttt{=}\\;v_1\\texttt{;}\\;e_2 \\longrightarrow[v_1/x]e_2\n", + "}$\n", + "\n", + "$\\inferrule[DoCall]{\n", + "}{\n", + " (\\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1) \\texttt{(}v_2\\texttt{)} \\longrightarrow{}[v_2/x]e_1\n", + "}$\n", + "\n", + "$\\inferrule[DoCallRec]{\n", + " v_1 = (x_1\\texttt{(}x_2\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1)\n", + "}{\n", + " v_1\\texttt{(}v_2\\texttt{)} \\longrightarrow {}[v_1/x_1] {}[v_2/x_2]e_1 \n", + "}$\n", + "\n", + "FigureĀ 1: The $\\TirName{Do}$ rules for JavaScripty with numbers,\n", + "booleans, strings, $\\mathbf{undefined}$, printing, and first-class\n", + "functions.\n", + "\n", + "### Search Rules\n", + "\n", + "$\\fbox{$e \\longrightarrow e'$}$\n", + "\n", + "$\\inferrule[SearchUnary]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " \\mathop{\\mathit{uop}}e_1 \\longrightarrow\\mathop{\\mathit{uop}}e_1'\n", + "}$\n", + "\n", + "$\\inferrule[SearchBinary1]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " e_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow e_1' \\mathbin{\\mathit{bop}}e_2\n", + "}$\n", + "\n", + "$\\inferrule[SearchBinary2]{\n", + " e_2 \\longrightarrow e_2'\n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow v_1 \\mathbin{\\mathit{bop}}e_2'\n", + "}$\n", + "\n", + "$\\inferrule[SearchIf]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_1'\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + "}$\n", + "\n", + "$\\inferrule[SearchPrint]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)} \\longrightarrow\\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1'\\texttt{)}\n", + "}$\n", + "\n", + "$\\inferrule[SearchConst]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 \\longrightarrow\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1'\\texttt{;}\\;e_2 \n", + "}$\n", + "\n", + "$\\inferrule[SearchCall1]{\n", + " e_1 \\longrightarrow e_1'\n", + "}{\n", + " e_1\\texttt{(}e_2\\texttt{)} \\longrightarrow e_1'\\texttt{(}e_2\\texttt{)}\n", + "}$\n", + "\n", + "$\\inferrule[SearchCall2]{\n", + " e_2 \\longrightarrow e_2'\n", + "}{\n", + " v_1 \\texttt{(}e_2\\texttt{)} \\longrightarrow v_1 \\texttt{(}e_2'\\texttt{)}\n", + "}$\n", + "\n", + "FigureĀ 2: The $\\TirName{Search}$ rules for JavaScripty with numbers,\n", + "booleans, strings, $\\mathbf{undefined}$, printing and first-class\n", + "functions.\n", + "\n", + "### Coercing to Boolean\n", + "\n", + "$\\fbox{$v \\rightsquigarrow b$}$\n", + "\n", + "$\\inferrule[ToBooleanNumFalse]{\n", + " n= 0.0 \\lor n= -0.0 \\lor n= \\mathsf{NaN}\n", + "}{\n", + " n \\rightsquigarrow \\mathbf{false}\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanNumTrue]{\n", + " n\\neq 0.0 \\and n\\neq -0.0 \\and n\\neq \\mathsf{NaN}\n", + "}{\n", + " n \\rightsquigarrow \\mathbf{true}\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanBoolean]{\n", + "}{\n", + " b \\rightsquigarrow b\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanStrFalse]{\n", + "}{\n", + " \\texttt{\"\"} \\rightsquigarrow \\mathbf{false}\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanStrTrue]{\n", + " \\mathit{str}\\neq \\texttt{\"\"}\n", + "}{\n", + " \\mathit{str} \\rightsquigarrow \\mathbf{true}\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanUndefined]{\n", + "}{\n", + " \\mathbf{undefined} \\rightsquigarrow \\mathbf{false}\n", + "}$\n", + "\n", + "$\\inferrule[ToBooleanFun]{\n", + "}{\n", + " x^{?}\\texttt{(}y\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e \\rightsquigarrow \\mathbf{true}\n", + "}$\n", + "\n", + "FigureĀ 3: The $\\TirName{ToBoolean}$ rules for JavaScripty with numbers,\n", + "booleans, strings, $\\mathbf{undefined}$, and first-class functions.\n", + "\n", + "### Dynamic Typing Rules\n", + "\n", + "$\\fbox{$e \\longrightarrow r$}$\n", + "\n", + "$\\inferrule[TypeErrorNeg]{\n", + " v_1 \\neq n_1\n", + "}{\n", + " \\mathop{\\texttt{-}} n_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}(\\mathop{\\texttt{-}} n_1) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorNot]{\n", + " v_1 \\neq n_1\n", + "}{\n", + " \\mathop{\\texttt{!}} n_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}(\\mathop{\\texttt{!}} n_1) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorArith2]{\n", + " v_2 \\neq n_2\n", + " \\and \n", + " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{-}, \\texttt{*}, \\texttt{/} \\right\\}\n", + "}{\n", + " n_1 \\mathbin{\\mathit{bop}}v_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(n_1 \\mathbin{\\mathit{bop}}v_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorArith1]{\n", + " v_1 \\neq n_1\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{-}, \\texttt{*}, \\texttt{/} \\right\\}\n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(v_1 \\mathbin{\\mathit{bop}}e_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorPlusString2]{\n", + " v_2 \\neq \\mathit{str}_2\n", + "}{\n", + " \\mathit{str}_1 \\mathbin{\\texttt{+}} v_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(\\mathit{str}_1 \\mathbin{\\texttt{+}} v_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorPlusString1]{\n", + " v_1 \\neq \\mathit{str}_1\n", + "}{\n", + " v_1 \\mathbin{\\texttt{+}} e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(v_1 \\mathbin{\\texttt{+}} e_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorInequalityNumber2]{\n", + " v_2 \\neq n_2\n", + " \\and \n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " n_1 \\mathbin{\\mathit{bop}}v_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(n_1 \\mathbin{\\mathit{bop}}v_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorInequalityNumber1]{\n", + " v_1 \\neq n_1\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(v_1 \\mathbin{\\mathit{bop}}e_2) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorInequalityString2]{\n", + " v_2 \\neq \\mathit{str}_2\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " \\mathit{str}_1 \\mathbin{\\mathit{bop}}v_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(\\mathit{str}_1 \\mathbin{\\mathit{bop}}v_2 ) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorInequalityString1]{\n", + " v_1 \\neq \\mathit{str}_1\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}(v_1 \\mathbin{\\mathit{bop}}e_2 ) \n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorCall]{\n", + " v_1 \\neq x^{?}\\texttt{(}x\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + "}{\n", + " v_1\\texttt{(}e_2\\texttt{)} \\longrightarrow \\mathop{\\mathsf{typeerror}} (v_1\\texttt{(}e_2\\texttt{)}) \n", + "}$\n", + "\n", + "$\\inferrule[PropagateUnary]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " \\mathop{\\mathit{uop}} e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateBinary1]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " e_1 \\mathbin{\\mathit{bop}} e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateBinary2]{\n", + " e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " v_1 \\mathbin{\\mathit{bop}} e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateIf]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagatePrint]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)} \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateConst]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateCall1]{\n", + " e_1 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " e_1\\texttt{(}e_2\\texttt{)} \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "$\\inferrule[PropagateCall2]{\n", + " e_2 \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}{\n", + " v_1\\texttt{(}e_2\\texttt{)} \\longrightarrow \\mathop{\\mathsf{typeerror}}e \n", + "}$\n", + "\n", + "FigureĀ 4: The $\\TirName{TypeError}$ and $\\TirName{Propagate}$ rules for\n", + "JavaScripty with numbers, booleans, strings, $\\mathbf{undefined}$,\n", + "printing, and first-class functions.\n", + "\n", + "## Concept Exercises\n", + "\n", + "Make sure to complete the concept exercises in this section and turn in\n", + "this file as part of your submission. However, all code and testing\n", + "exercises from other sections are submitted in `Lab3.scala` or\n", + "`Lab3Spec.scala`.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7 (Evaluation Order)**</span>\n", + "Consider the small-step operational semantics shown in\n", + "<a href=\"#sec-small-step-operational-semantics\"\n", + "class=\"quarto-xref\">SectionĀ 5</a>. What is the evaluation order for\n", + "$e_1 \\mathbin{\\texttt{+}} e_2$? Explain.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "7f776bde-b6d9-4fda-9a42-a1bd2d05357f", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "f6430bd4-aa33-4d31-8ab2-08c78eaa3390", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 8 (Changing Evaluation\n", + "Order)**</span> How do we change the rules to obtain the opposite\n", + "evaluation order?\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "27e97fb3-e0b7-45c3-8cf2-9b9603719076", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "0db10e5a-00cb-4360-9e6b-b3ad88719fed", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 9 (Using Short-Circuit\n", + "Evaluation)**</span> Give an example that illustrates the usefulness of\n", + "short-circuit evaluation. Explain your example.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "323a2822-45d2-48f0-9e08-a44a717af6c3", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "1b84a9cd-025f-4e6b-8451-88700db1c441", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 10 (Removing Short-Circuit\n", + "Evaluation)**</span> Consider the small-step operational semantics shown\n", + "in <a href=\"#sec-small-step-operational-semantics\"\n", + "class=\"quarto-xref\">SectionĀ 5</a>. Does\n", + "$e_1 \\mathbin{\\texttt{\\&\\&}} e_2$ short circuit? Explain. If\n", + "$e_1 \\mathbin{\\texttt{\\&\\&}} e_2$ short circuits, give rules to\n", + "eliminatesshort circuiting. If it does not short circuit, give the\n", + "short-circuiting rules.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "ef2e3b86-efd9-44e8-ada5-fd6d123e737c", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6fd4e9a9-fc95-42de-ab66-90aa6f6daa4e", + "metadata": {}, + "source": [ + "## Testing\n", + "\n", + "This section has some space to write some tests in our subset of\n", + "JavaScript. You might want to work on these tests while you are\n", + "implementing `step`. As before, you will add your tests to\n", + "`Lab3StudentSpec`. Your interpreter will run the tests against the\n", + "expected result you provide. We will write three tests, all of these\n", + "tests must properly parse.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 11 (Test 1: Higher-Order\n", + "Function)**</span> Write a test case that has a function that takes a\n", + "function value as an argument (i.e., is a higher order function):" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1adbdab3-bdfa-4f5a-86e0-761adc7c1501", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "1555b8553ead2a857b18c9afd0b6db41", + "grade": false, + "grade_id": "test1-higher-order-function", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "7e138cea-488d-4395-a908-9721db43e4fe", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 12 (Test 2: Recursion)**</span>\n", + "Write a test case that uses recursion" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7b8788b0-fddc-4221-9d04-dfb9e6cb407c", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "914962b49a6beefb2f6d7313b0b52a87", + "grade": false, + "grade_id": "test2-recursion", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6afa15bb-a8cc-493b-923b-8e345b60047e", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 13 (Test 3: Any Test in this\n", + "variant of JavaScripty)**</span> Write another test" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "a7d9f58b-858f-4af6-967b-3c91a58fba92", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "3fca668afe5d69ccb211d30b0571ee11", + "grade": false, + "grade_id": "test3-anytest", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "a66dc716-10f3-400d-9248-fe3bc26e144a", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Remember to add these to `Lab3StudentSpec` in `Lab3Spec.scala`.\n", + "- Add the JavaScripty code as a string in `jsyStr` and the expected\n", + " result in `answer`.\n", + "\n", + "## Accelerated Component\n", + "\n", + "For the accelerated component of this lab, we will give rules and\n", + "implement the behavior that enables us to match JavaScript semantics. In\n", + "particular, we will give rules and implement type coercions for numbers\n", + "and strings, and we will update our small-step operational semantics to\n", + "use them.\n", + "\n", + "### Additional Type Coercions\n", + "\n", + "<span class=\"theorem-title\">**Exercise 14**</span> Give the inference\n", + "rules defining the judgment form for coercing a value to a number\n", + "$v \\rightsquigarrow n$\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "eae0bbfd-22bd-4716-9735-82b855628fa6", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6030af49-acee-4600-be79-a3475b3c3a2e", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 15**</span> Give the inference\n", + "rules defining the judgment form for coercing a value to a string\n", + "$v \\rightsquigarrow \\mathit{str}$\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "a709b005-1042-48a4-b9b7-0dbd52ceed1c", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "0a6d8753-a62e-4c3f-a4d9-cdea983e3486", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 16**</span> Implement the\n", + "`toNumber` and `toStr`coercions." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1287f427", + "metadata": {}, + "outputs": [], + "source": [ + "def toNumber(v: Expr): Double = ???\n", + "def toStr(v: Expr): String = ???" + ] + }, + { + "cell_type": "markdown", + "id": "e350fa53-d98f-4ec7-b3e7-dc9f09943ce3", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- If your recall Lab 2, we implemented these functions. They will be\n", + " the same here, except we must add the rules for functions.\n", + "\n", + "### Updating the Small-Step Operational Semantics\n", + "\n", + "Now that we are allowing type coersions, our operational semantics will\n", + "change. For example, consider the following $\\TirName{Do}$ rule:\n", + "\n", + "$\\inferrule[DoNeg]{\n", + " v \\rightsquigarrow n\n", + "}{\n", + " \\mathop{\\texttt{-}} v \\longrightarrow-n\n", + "}$\n", + "\n", + "This is a new rule for $\\TirName{DoNeg}$, which is read as if $v$\n", + "coerces to $n$, then $\\mathop{\\texttt{-}} v$ steps to $-n$. Now that we\n", + "are allowing non-numbers to be coerced and then negated, we no longer\n", + "have our $\\TirName{TypeErrorNeg}$ rule.\n", + "\n", + "Note that we only need to update $\\TirName{Do}$ rules with coercions and\n", + "remove $\\TirName{TypeError}$ rules. We do not need to update the\n", + "$\\TirName{Search}$ or $\\TirName{Propagage}$ rules.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 17**</span> Explain why we only\n", + "need to update the $\\TirName{Do}$ rules with coercions and remove\n", + "$\\TirName{TypeError}$ rules, and we do not need to update the\n", + "$\\TirName{Search}$ or $\\TirName{Propagage}$ rules.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "dab04724-501e-43b6-9e8b-42a98f57a8ed", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "27f17dc9-86e6-4b9e-89fb-831e377080a5", + "metadata": {}, + "source": [ + "One rule of particular interest is $\\TirName{DoArith}$, which we need to\n", + "split to account for $e_1 \\mathbin{\\texttt{+}} e_2$ being overloaded for\n", + "numbers and strings. Given this, we need to rewrite $\\TirName{DoArith}$\n", + "so it does not include $\\texttt{+}$ (and adds coersions), add the rule\n", + "$\\TirName{DoPlusNumber}$, and alter $\\TirName{DoPlusString}$ to become\n", + "two rules.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 18**</span> Give these new\n", + "$\\TirName{Do}$ rules\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "45b4dc5e-15b8-40e0-8c64-678055a78564", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "71bab51c-f791-418b-a9bc-852fe06aa1ff", + "metadata": {}, + "source": [ + "Similar to this, our $\\TirName{DoInequalityNumber}$ rule must be split\n", + "into two and altered:\n", + "\n", + "<span class=\"theorem-title\">**Exercise 19**</span> Give the two new\n", + "$\\TirName{DoInequalityNumber\\(_1\\)}$ and\n", + "$\\TirName{DoInequalityNumber\\(_2\\)}$ rules:\n", + "\n", + "***Edit this cell:***" + ] + }, + { + "cell_type": "markdown", + "id": "c7ca71c0-6f30-48a6-85e8-91f018d723ac", + "metadata": {}, + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "64400b28-73e0-43ee-a733-01036957fa13", + "metadata": {}, + "source": [ + "Once we have all of these rules defined, we notice that most of our\n", + "$\\mathsf{typeerror}$ rules no longer result in type errors. Therefore,\n", + "most of them should be deleted. In fact, the only non-propagate rule\n", + "left for type errors is $\\TirName{TypeErrorCall}$, since we are still\n", + "not allowed to call something that is not a function (in JavaScript).\n", + "\n", + "### Update Step\n", + "\n", + "<span class=\"theorem-title\">**Exercise 20**</span> Now that we have our\n", + "type conversion functions implemented and our new rules defined, we are\n", + "ready to update `step`. Implement `stepCoerce` by first copying your\n", + "code from `stepCheck` and then update based on your new rules." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "bd11e062", + "metadata": {}, + "outputs": [], + "source": [ + "def stepCoerce(e: Expr): Either[DynamicTypeError,Expr] = ???" + ] + }, + { + "cell_type": "markdown", + "id": "0677bd36-105b-499b-9e07-97ee98f41f82", + "metadata": {}, + "source": [ + "As before, let the rules guide your implementation.\n", + "\n", + "### Notes\n", + "\n", + "- None of your other functions should need to be altered.\n", + "\n", + "## Submission\n", + "\n", + "If you are a University of Colorado Boulder student, we use Gradescope\n", + "for assignment submission. In summary,\n", + "\n", + "- [ ] Create a private GitHub repository by clicking on a GitHub\n", + " Classroom link from the corresponding Canvas assignment entry.\n", + "- [ ] Clone your private GitHub repository to your development\n", + " environment (using the `<> Code` button on GitHub to get the\n", + " repository URL).\n", + "- [ ] Work on this lab from your cloned repository. Use Git to save\n", + " versions on GitHub (e.g., `git add`, `git commit`, `git push` on the\n", + " command line or via VSCode).\n", + "- [ ] Submit to the corresponding Gradescope assignment entry for\n", + " grading by choosing GitHub as the submission method.\n", + "\n", + "You need to have a GitHub identity and must have your full name in your\n", + "GitHub profile in case we need to associate you with your submissions." + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala", + "path": "/Users/bec/Library/Jupyter/kernels/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 +} diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.scala b/lab3/src/main/scala/jsy/lab3/Lab3.scala new file mode 100644 index 0000000..4660c6d --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.scala @@ -0,0 +1,360 @@ +package jsy.lab3 +import scala.util.Try + +object Lab3 extends jsy.util.JsyApplication { + import ast._ + + /* + * CSCI 3155: Lab 3 + * Jack Sangdahl + */ + + /** *************************************************** + */ + /** ************** Regular Section ******************** + */ + /** *************************************************** + */ + + /* Static Scoping */ + + def substitute(v: Expr, x: String, e: Expr): Expr = { + require(isValue(v), s"substitute: v ${v} to substitute is not a value") + def subst(e: Expr): Expr = substitute(v, x, e) + e match { + case Print(e1) => Print(subst(e1)) + case Unary(uop, e1) => Unary(uop, subst(e1)) + case Binary(bop, e1, e2) => Binary(bop, subst(e1), subst(e2)) + case If(e1, e2, e3) => If(subst(e1), subst(e2), subst(e3)) + case Call(e1, e2) => Call(subst(e1), subst(e2)) + case Var(y) => if (x == y) v else e + case Fun(xopt, y, e1) if (x != y) => Fun(xopt, y, subst(e1)) + case ConstDecl(y, e1, e2) if (x != y) => + ConstDecl(y, subst(e1), subst(e2)) + case _ => e + } + } + + /* Iteration */ + + def iterateBasic[A](acc0: A)(stepi: (A, Int) => Option[A]): A = { + def loop(acc: A, i: Int): A = stepi(acc, i) match { + case Some(acc1) => loop(acc1, i + 1) + case None => acc + } + loop(acc0, 0) + } + + def iterate[Err, A]( + acc0: A + )(stepi: (A, Int) => Option[Either[Err, A]]): Either[Err, A] = { + def loop(acc: A, i: Int): Either[Err, A] = stepi(acc, i) match { + case Some(Right(acc1)) => loop(acc1, i + 1) + case Some(Left(err)) => Left(err) + case None => Right(acc) + } + loop(acc0, 0) + } + + /* Small-Step Interpreter with Static Scoping */ + + def toBoolean(v: Expr): Boolean = { + require(isValue(v)) + (v: @unchecked) match { + case B(b) => b + case S(s) => s != "" + case N(n) => n != 0 + case Fun(_, _, _) => true + } + } + + def stepBasic(e: Expr): Expr = (e: @unchecked) match { + + case Print(v1) if isValue(v1) => println(pretty(v1)); Undefined + case Print(e1) => Print(stepBasic(e1)) + + case Binary(Seq, e1, e2) if !isValue(e1) => Binary(Seq, stepBasic(e1), e2) + case Binary(Seq, e1, e2) if isValue(e1) => stepBasic(e2) + + case If(e1, e2, e3) if !isValue(e1) => If(stepBasic(e1), e2, e3) + case If(e1, e2, e3) => { + if (toBoolean(e1)) + if (isValue(e2)) e2 else stepBasic(e2) + else + if (isValue(e3)) e3 else stepBasic(e3) + } + + case ConstDecl(y, e1, e2) if !isValue(e1) => ConstDecl(y, stepBasic(e1), e2) + case ConstDecl(y, e1, e2) => substitute(e1, y, e2) + + case Call(e1, e2) if !isValue(e2) => Call(e1, stepBasic(e2)) + case Call(Fun(xopt, y, e1), e2) => { + val noVarsBody = substitute(e2, y, e1) + xopt match { + case Some(x) => substitute(Fun(xopt, y, e1), x, noVarsBody) + case None => noVarsBody + } + } + + case Binary(Plus, N(x), N(y)) => N(x + y) + case Binary(Plus, e1, N(e2)) => Binary(Plus, stepBasic(e1), N(e2)) + case Binary(Plus, N(e1), e2) => Binary(Plus, N(e1), stepBasic(e2)) + + case Binary(Minus, N(x), N(y)) => N(x - y) + case Binary(Minus, e1, N(e2)) => Binary(Minus, stepBasic(e1), N(e2)) + case Binary(Minus, N(e1), e2) => Binary(Minus, N(e1), stepBasic(e2)) + + case Binary(Eq, x, y) if isValue(x) && isValue(y) => B(x == y) + case Binary(Eq, e1, e2) if !isValue(e1) => Binary(Eq, stepBasic(e1), e2) + case Binary(Eq, e1, e2) if !isValue(e2) => Binary(Eq, e1, stepBasic(e2)) + + /* Cases that should never match. Your cases above should ensure this. */ + case Var(_) => + throw new AssertionError( + s"Gremlins: internal error, not closed expression $e." + ) + case v if isValue(v) => + throw new AssertionError( + s"Gremlins: internal error, step should not be called on values $v." + ) + } + + def stepCheck(e: Expr): Either[DynamicTypeError, Expr] = e match { + + case Print(v1) if isValue(v1) => println(pretty(v1)); Right(Undefined) + case Print(e1) => stepCheck(e1).map(Print) + + case Binary(Seq, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Seq, e1, e2)) + case Binary(Seq, e1, e2) if isValue(e1) => stepCheck(e2) + + case If(e1, e2, e3) if !isValue(e1) => + stepCheck(e1).map(e1 => If(e1, e2, e3)) + case If(e1, e2, e3) => { + if (toBoolean(e1)) + if (isValue(e2)) Right(e2) else stepCheck(e2) + else + if (isValue(e3)) Right(e3) else stepCheck(e3) + } + + case ConstDecl(y, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => ConstDecl(y, e1, e2)) + case ConstDecl(y, e1, e2) => Right(substitute(e1, y, e2)) + + case Call(e1, e2) if !isValue(e1) => stepCheck(e1).map(e1 => Call(e1, e2)) + case Call(e1, e2) if !isValue(e2) => stepCheck(e2).map(e2 => Call(e1, e2)) + case Call(Fun(xopt, y, e1), e2) => { + val noVarsBody = substitute(e2, y, e1) + xopt match { + case Some(x) => Right(substitute(Fun(xopt, y, e1), x, noVarsBody)) + case None => Right(noVarsBody) + } + } + case Call(e1, e2) => Left(DynamicTypeError(Call(e1, e2))) + + case Binary(Plus, N(x), N(y)) => Right(N(x + y)) + case Binary(Plus, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Plus, e1, e2)) + case Binary(Plus, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Plus, e1, e2)) + case Binary(Plus, e1, e2) => Left(DynamicTypeError(Binary(Plus, e1, e2))) + + case Binary(Minus, N(x), N(y)) => Right(N(x - y)) + case Binary(Minus, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Minus, e1, e2)) + case Binary(Minus, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Minus, e1, e2)) + case Binary(Minus, e1, e2) => Left(DynamicTypeError(Binary(Minus, e1, e2))) + + case Binary(Times, N(x), N(y)) => Right(N(x * y)) + case Binary(Times, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Times, e1, e2)) + case Binary(Times, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Times, e1, e2)) + case Binary(Times, e1, e2) => Left(DynamicTypeError(Binary(Times, e1, e2))) + + case Binary(Div, N(x), N(y)) => Right(N(x / y)) + case Binary(Div, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Div, e1, e2)) + case Binary(Div, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e1 => Binary(Div, e1, e2)) + case Binary(Div, e1, e2) => Left(DynamicTypeError(Binary(Div, e1, e2))) + + case Binary(Eq, x, y) if isValue(x) && isValue(y) => Right(B(x == y)) + case Binary(Eq, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Eq, e1, e2)) + case Binary(Eq, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Eq, e1, e2)) + case Binary(Eq, e1, e2) => Left(DynamicTypeError(Binary(Eq, e1, e2))) + + case Binary(Ne, x, y) if isValue(x) && isValue(y) => Right(B(x != y)) + case Binary(Ne, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Ne, e1, e2)) + case Binary(Ne, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Ne, e1, e2)) + case Binary(Ne, e1, e2) => Left(DynamicTypeError(Binary(Ne, e1, e2))) + + case Binary(Lt, N(x), N(y)) => Right(B(x < y)) + case Binary(Lt, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Lt, e1, e2)) + case Binary(Lt, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Lt, e1, e2)) + case Binary(Lt, e1, e2) => Left(DynamicTypeError(Binary(Lt, e1, e2))) + + case Binary(Le, N(x), N(y)) => Right(B(x <= y)) + case Binary(Le, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Le, e1, e2)) + case Binary(Le, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Le, e1, e2)) + case Binary(Le, e1, e2) => Left(DynamicTypeError(Binary(Le, e1, e2))) + + case Binary(Gt, N(x), N(y)) => Right(B(x > y)) + case Binary(Gt, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Gt, e1, e2)) + case Binary(Gt, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Gt, e1, e2)) + case Binary(Gt, e1, e2) => Left(DynamicTypeError(Binary(Gt, e1, e2))) + + case Binary(Ge, N(x), N(y)) => Right(B(x >= y)) + case Binary(Ge, e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(Ge, e1, e2)) + case Binary(Ge, e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(Ge, e1, e2)) + case Binary(Ge, e1, e2) => Left(DynamicTypeError(Binary(Ge, e1, e2))) + + case Unary(Neg, N(x)) => Right(N(-x)) + case Unary(Neg, e1) if !isValue(e1) => + stepCheck(e1).map(e1 => Unary(Neg, e1)) + case Unary(Neg, e1) => Left(DynamicTypeError(Unary(Neg, e1))) + + case Binary(And, e1, e2) => { + (e1, e2) match { + case (e1, e2) if !isValue(e1) => + stepCheck(e1).map(e1 => Binary(And, e1, e2)) + case (e1, e2) if !isValue(e2) => + stepCheck(e2).map(e2 => Binary(And, e1, e2)) + case (e1, e2) => + if (!toBoolean(e1)) Right(e1) else Right(e2) + } + } + + /* Cases that should never match. Your cases above should ensure this. */ + case Var(_) => + throw new AssertionError( + s"Gremlins: internal error, not closed expression $e." + ) + case v if isValue(v) => + throw new AssertionError( + s"Gremlins: internal error, step should not be called on values $v." + ) + } + + /* IMPORTANT: Choose which version of step to use for testing by choosing one of the lines. You will pick one version to submit. */ + // def step(e: Expr): Either[DynamicTypeError, Expr] = Right(stepBasic(e)) + def step(e: Expr): Either[DynamicTypeError, Expr] = stepCheck(e) + + /** *************************************************** + */ + /** ********** End Regular Section ******************** + */ + /** *************************************************** + */ + + /** *************************************************** + */ + /** ********** Accelerated Section ******************** + */ + /** *************************************************** + */ + + def toNumber(v: Expr): Double = { + require(isValue(v)) + ??? + } + + def toStr(v: Expr): String = { + require(isValue(v)) + ??? + } + + def stepCoerce(e: Expr): Either[DynamicTypeError, Expr] = ??? + + /* Choose to use this version of step for testing uncommenting this line and commenting the definition of step above. */ + // def step(e: Expr): Either[DynamicTypeError, Expr] = stepCoerce(e) + + /** *************************************************** + */ + /** ********** End Accelerated Section **************** + */ + /** *************************************************** + */ + + /* External Interfaces */ + + // this.debug = true // comment this out or set to false if you don't want print debugging information + this.maxSteps = Some( + 1000 + ) // comment this out or set to None to not bound the number of steps. + this.keepGoing = + true // comment this out if you want to stop at first exception when processing a file + + /** Interface to take a small-step from a string. This is convenient for unit + * testing. + */ + def oneStep(s: String): Either[DynamicTypeError, Expr] = step(Parser.parse(s)) + + /** Interface to run your small-step interpreter and print out the steps of + * evaluation if debugging. + */ + def iterateStep(e: Expr): Either[DynamicTypeError, Expr] = { + require(closed(e), s"iterateStep: ${e} not closed") + if (debug) { + println("------------------------------------------------------------") + println("Evaluating with step ...") + } + val v = iterate(e) { (e: Expr, n: Int) => + if (debug) { println(s"Step $n: $e") } + if (isValue(e)) None else Some(step(e)) + } + if (debug) { println("Value: " + v) } + v + } + + /** Interface to run your small-step interpreter from a string. This is + * convenient for unit testing. + */ + def iterateStep(s: String): Either[DynamicTypeError, Expr] = iterateStep( + Parser.parse(s) + ) + + /** Interface for main for JsyApplication */ + def processFile(file: java.io.File): Unit = { + if (debug) { + println("============================================================") + println("File: " + file.getName) + println("Parsing ...") + } + + val e1 = + handle(None: Option[Expr]) { + Some { + Parser.parseFile(file) + } + } getOrElse { + return + } + + handle(()) { + println("# Stepping ...") + def loop(e: Expr, n: Int): Either[DynamicTypeError, Expr] = { + println("## %4d: %s".format(n, e)) + if (isValue(e)) Right(e) else step(e) flatMap { e1 => loop(e1, n + 1) } + } + loop(e1, 0) match { + case Right(v1) => println(pretty(v1)) + case Left(err) => println(err) + } + } + } + +} diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js new file mode 100644 index 0000000..8d4d9ce --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js @@ -0,0 +1,24 @@ +/* + * CSCI 3155: Lab 3 JavaScript Worksheet + * + * This worksheet is a place to experiment with JavaScript expressions. + */ + +// The new language feature in Lab 3 is first-class functions. + +const id = function (x) { + return x; +}; + +const plus = (x) => (y) => x + y; + +const j = plus(3)(4); + +id("Hello, ") + j; + +const factorial = function f(n) { + return n === 0 ? 1 : n * f(n - 1); +}; + +const factorial3 = factorial(3); +factorial3; diff --git a/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc new file mode 100644 index 0000000..e5744ec --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc @@ -0,0 +1,51 @@ +/* + * CSCI 3155: Lab 3 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab3.scala. + */ + +// Imports the parse function from jsy.lab3.Parser +import jsy.lab3.Parser.{parse, parseFile} + +// Imports the ast nodes +import jsy.lab3.ast._ + +// Imports all of the functions form jsy.student.Lab3 (your implementations in Lab3.scala) +import jsy.lab3.Lab3._ + +// The new language feature in Lab 3 is first-class functions. + +// In JavaScript, functions can be written in a number of different +// ways. Here, we write the same identity function with different +// concrete syntax that all get parsed to the same abstract. +parse("x => x") +parse("x => { return x }") +parse("x => { return x; }") +parse("(x) => x") +parse("function (x) { return x }") + +// Functions can optionally have a name, which we use for declaring +// potentially recursive functions. +parse("function id(x) { return x }") + +// To simplify your implementation, we only allow single parameter +// functions. But we can get the effect of multi-parameter functions +// through currying (i.e., having a function that returns another +// function). +parse("const plus = x => y => x + y") + +// Here are some more function expressions. +parse("x => { const z = 3; return x + z }") +parse("function (x) { const z = 3; return x + z }") + +// Run your small-step interpreter +//iterateStep("1 + 2") +//iterateStep("x => y => x + y") +//iterateStep("const plus = x => y => x + y; plus(3)(4)") + +// Parse the JavaScripty expression in your worksheet +val worksheetJsy = parseFile("src/main/scala/jsy/lab3/Lab3.worksheet.js") + +// Eval the JavaScripty expression in your worksheet +//iterateStep(worksheetJsy)
\ No newline at end of file diff --git a/lab3/src/main/scala/jsy/lab3/Parser.scala b/lab3/src/main/scala/jsy/lab3/Parser.scala new file mode 100644 index 0000000..e044311 --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/Parser.scala @@ -0,0 +1,284 @@ +/** + * + */ +package jsy.lab3 + +import jsy.lab3.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} + * noseq ::= arrow + * arrow ::= x => noseq | cond + * cond ::= binary [? cond : cond] + * binary ::= unary{bop(_)unary} + * unary ::= uop unary | call + * call ::= term{(expr)} + * 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] = + arrow + + def arrow: this.Parser[Expr] = + (opt("(") ~ ident ~ opt(")")) ~ (withpos("=>" ~> (noseq | funblock))) ^^ { + case _ ~ x ~ _ ~ ((pos,body)) => Fun(None, x, body) setPos pos + } | + cond + + def funblock: this.Parser[Expr] = + ("{" ~> stmts ~ ret <~ rep(empty_stmt) <~ "}") ^^ { + case stmts ~ ret => stmts(Some(ret)) + } + + def ret: this.Parser[Expr] = + "return" ~> expr + + 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) }) | + call + + def uop: this.Parser[Expr => Expr] = + "-" ^^ (_ => (e: Expr) => Unary(Neg, e)) | + "!" ^^ (_ => (e: Expr) => Unary(Not, e)) + + def call: this.Parser[Expr] = + term ~ rep(callop) ^^ { case e0 ~ calls => (calls.foldLeft(e0)){ case (acc, mk) => mk(acc) } } + + def callop: this.Parser[Expr => Expr] = + withpos("(" ~> expr <~ ")") ^^ { case (pos, arg) => (e0 => Call(e0, arg) setPos pos) } + + 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)) | + function + ) | + "(" ~> expr <~ ")" | + "{" ~> "{" ~> prog <~ "}" <~ "}" | + failure("atomic expression expected") + + def function: this.Parser[Expr] = + ("function" ~> opt(ident)) ~ ("(" ~> ident <~ ")") ~ funblock ^^ { + case f ~ x ~ body => Fun(f, x, body) + } + + 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/lab3/src/main/scala/jsy/lab3/ast.scala b/lab3/src/main/scala/jsy/lab3/ast.scala new file mode 100644 index 0000000..eb15400 --- /dev/null +++ b/lab3/src/main/scala/jsy/lab3/ast.scala @@ -0,0 +1,106 @@ +package jsy.lab3 + +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 + + /* Functions */ + case class Fun(p: Option[String], x: String, e1: Expr) extends Expr // e::= p(x) => e1 + case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2) + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) | B(_) | Undefined | S(_) | Fun(_, _, _) => 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 Undefined => "undefined" + case S(s) => s + case Fun(p, _, _) => + "[Function%s]".format(p match { case None => "" case Some(s) => ": " + s }) + } + } + + 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 Fun(None, x, e1) => freeVars(e1) - x + case Fun(Some(x1), x2, e1) => freeVars(e1) - x2 - x1 + 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 Call(e1, e2) => freeVars(e1) | freeVars(e2) + case Print(e1) => freeVars(e1) + } + + /* Check closed expressions. */ + def closed(e: Expr): Boolean = freeVars(e).isEmpty + + /* typeerror e */ + case class DynamicTypeError(e: Expr) { + override def toString = s"TypeError: in expression $e" + } +} diff --git a/lab3/src/main/scala/jsy/util/JsyApplication.scala b/lab3/src/main/scala/jsy/util/JsyApplication.scala new file mode 100644 index 0000000..46b658d --- /dev/null +++ b/lab3/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/lab3/src/test/resources/lab3/test3004_call.ans b/lab3/src/test/resources/lab3/test3004_call.ans new file mode 100644 index 0000000..cedff5b --- /dev/null +++ b/lab3/src/test/resources/lab3/test3004_call.ans @@ -0,0 +1,8 @@ +# Stepping ... +## 0: ConstDecl(w,Fun(None,y,Binary(Minus,Var(y),N(7.0))),Print(Call(Var(w),N(4.3)))) +## 1: Print(Call(Fun(None,y,Binary(Minus,Var(y),N(7.0))),N(4.3))) +## 2: Print(Binary(Minus,N(4.3),N(7.0))) +## 3: Print(N(-2.7)) +-2.7 +## 4: Undefined +undefined diff --git a/lab3/src/test/resources/lab3/test3004_call.jsy b/lab3/src/test/resources/lab3/test3004_call.jsy new file mode 100644 index 0000000..4054060 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3004_call.jsy @@ -0,0 +1,2 @@ +const w = function (y) { return y - 7 } +console.log(w(4.3)) diff --git a/lab3/src/test/resources/lab3/test3006_curry.ans b/lab3/src/test/resources/lab3/test3006_curry.ans new file mode 100644 index 0000000..8a00bc5 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3006_curry.ans @@ -0,0 +1,8 @@ +# Stepping ... +## 0: ConstDecl(g,Fun(None,x,Fun(None,y,Binary(And,Var(x),Var(y)))),Binary(Plus,Call(Call(Var(g),N(1.0)),N(0.0)),N(0.1))) +## 1: Binary(Plus,Call(Call(Fun(None,x,Fun(None,y,Binary(And,Var(x),Var(y)))),N(1.0)),N(0.0)),N(0.1)) +## 2: Binary(Plus,Call(Fun(None,y,Binary(And,N(1.0),Var(y))),N(0.0)),N(0.1)) +## 3: Binary(Plus,Binary(And,N(1.0),N(0.0)),N(0.1)) +## 4: Binary(Plus,N(0.0),N(0.1)) +## 5: N(0.1) +0.1 diff --git a/lab3/src/test/resources/lab3/test3006_curry.jsy b/lab3/src/test/resources/lab3/test3006_curry.jsy new file mode 100644 index 0000000..2e87562 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3006_curry.jsy @@ -0,0 +1,2 @@ +const g = function(x) { return function(y) { return x && y } }; +g(1)(0) + 0.1 diff --git a/lab3/src/test/resources/lab3/test3008_call.ans b/lab3/src/test/resources/lab3/test3008_call.ans new file mode 100644 index 0000000..3e34395 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3008_call.ans @@ -0,0 +1,48 @@ +# Stepping ... +## 0: ConstDecl(f,Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Plus,Call(Var(f),N(8.0)),N(0.1))) +## 1: Binary(Plus,Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(8.0)),N(0.1)) +## 2: Binary(Plus,If(Binary(Eq,N(8.0),N(0.0)),N(1.0),Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0))))),N(0.1)) +## 3: Binary(Plus,If(B(false),N(1.0),Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0))))),N(0.1)) +## 4: Binary(Plus,Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(8.0),N(1.0)))),N(0.1)) +## 5: Binary(Plus,Binary(Times,N(8.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(7.0))),N(0.1)) +## 6: Binary(Plus,Binary(Times,N(8.0),If(Binary(Eq,N(7.0),N(0.0)),N(1.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0)))))),N(0.1)) +## 7: Binary(Plus,Binary(Times,N(8.0),If(B(false),N(1.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0)))))),N(0.1)) +## 8: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(7.0),N(1.0))))),N(0.1)) +## 9: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(6.0)))),N(0.1)) +## 10: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),If(Binary(Eq,N(6.0),N(0.0)),N(1.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0))))))),N(0.1)) +## 11: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),If(B(false),N(1.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0))))))),N(0.1)) +## 12: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(6.0),N(1.0)))))),N(0.1)) +## 13: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(5.0))))),N(0.1)) +## 14: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),If(Binary(Eq,N(5.0),N(0.0)),N(1.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0)))))))),N(0.1)) +## 15: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),If(B(false),N(1.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0)))))))),N(0.1)) +## 16: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(5.0),N(1.0))))))),N(0.1)) +## 17: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(4.0)))))),N(0.1)) +## 18: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),If(Binary(Eq,N(4.0),N(0.0)),N(1.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0))))))))),N(0.1)) +## 19: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),If(B(false),N(1.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0))))))))),N(0.1)) +## 20: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(4.0),N(1.0)))))))),N(0.1)) +## 21: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(3.0))))))),N(0.1)) +## 22: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),If(Binary(Eq,N(3.0),N(0.0)),N(1.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0)))))))))),N(0.1)) +## 23: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),If(B(false),N(1.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0)))))))))),N(0.1)) +## 24: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(3.0),N(1.0))))))))),N(0.1)) +## 25: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(2.0)))))))),N(0.1)) +## 26: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),If(Binary(Eq,N(2.0),N(0.0)),N(1.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0))))))))))),N(0.1)) +## 27: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),If(B(false),N(1.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0))))))))))),N(0.1)) +## 28: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(2.0),N(1.0)))))))))),N(0.1)) +## 29: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(1.0))))))))),N(0.1)) +## 30: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),If(Binary(Eq,N(1.0),N(0.0)),N(1.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0)))))))))))),N(0.1)) +## 31: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),If(B(false),N(1.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0)))))))))))),N(0.1)) +## 32: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(1.0),N(1.0))))))))))),N(0.1)) +## 33: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),N(0.0)))))))))),N(0.1)) +## 34: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),If(Binary(Eq,N(0.0),N(0.0)),N(1.0),Binary(Times,N(0.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(0.0),N(1.0))))))))))))),N(0.1)) +## 35: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),If(B(true),N(1.0),Binary(Times,N(0.0),Call(Fun(Some(f),x,If(Binary(Eq,Var(x),N(0.0)),N(1.0),Binary(Times,Var(x),Call(Var(f),Binary(Minus,Var(x),N(1.0)))))),Binary(Minus,N(0.0),N(1.0))))))))))))),N(0.1)) +## 36: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),Binary(Times,N(1.0),N(1.0))))))))),N(0.1)) +## 37: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),Binary(Times,N(2.0),N(1.0)))))))),N(0.1)) +## 38: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),Binary(Times,N(3.0),N(2.0))))))),N(0.1)) +## 39: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),Binary(Times,N(4.0),N(6.0)))))),N(0.1)) +## 40: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),Binary(Times,N(5.0),N(24.0))))),N(0.1)) +## 41: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),Binary(Times,N(6.0),N(120.0)))),N(0.1)) +## 42: Binary(Plus,Binary(Times,N(8.0),Binary(Times,N(7.0),N(720.0))),N(0.1)) +## 43: Binary(Plus,Binary(Times,N(8.0),N(5040.0)),N(0.1)) +## 44: Binary(Plus,N(40320.0),N(0.1)) +## 45: N(40320.1) +40320.1 diff --git a/lab3/src/test/resources/lab3/test3008_call.jsy b/lab3/src/test/resources/lab3/test3008_call.jsy new file mode 100644 index 0000000..0ec8239 --- /dev/null +++ b/lab3/src/test/resources/lab3/test3008_call.jsy @@ -0,0 +1,2 @@ +const f = function f(x) { return x === 0 ? 1 : x * f(x - 1) }; +f(8) + 0.1 diff --git a/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala b/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala new file mode 100644 index 0000000..1b40c01 --- /dev/null +++ b/lab3/src/test/scala/jsy/lab3/Lab3Spec.scala @@ -0,0 +1,150 @@ +package jsy.lab3 + +import org.scalatest.flatspec.AnyFlatSpec +import Parser.parse +import ast._ +import Lab3._ + +class Lab3StudentSpec extends AnyFlatSpec { + + "StudentSpec" should "evaluate a higher order function" in { + val jsyStr: String = + "(function f(g) { return g(g)}) (function g(x) { return x }) (5);" + val answer: Either[DynamicTypeError, Expr] = Right(N(5)) + assert(answer === iterateStep(parse(jsyStr))) + } + + it should "evaluate a recursive function" in { + val jsyStr: String = + "(function f(x) { return x <= 1 ? 1 : x * f(x - 1)}) (3);" + val answer: Either[DynamicTypeError, Expr] = Right(N(6)) + assert(answer === iterateStep(parse(jsyStr))) + } + + it should "evaluate your test case" in { + val jsyStr: String = "1 + 1" + val answer: Either[DynamicTypeError, Expr] = Right(N(2)) + assert(answer === iterateStep(parse(jsyStr))) + } + +} + +class Lab3Spec extends AnyFlatSpec { + + "substitute" should "perform syntatic substitution respecting shadowing" in { + val xplus1 = parse("x + 1") + val twoplus1 = parse("2 + 1") + assert(substitute(N(2), "x", xplus1) === twoplus1) + val constx3 = parse("const x = 3; x") + val shadowx = Binary(Plus, constx3, Var("x")) + assert(substitute(N(2), "x", shadowx) === Binary(Plus, constx3, N(2))) + } + + "iterateBasic" should "work for sumTo(100)" in { + def sumTo(n: Int) = { + iterateBasic(0) { case (acc, i) => + require(n >= 0) + if (i > n) None + else Some(acc + i) + } + } + + assertResult(5050) { sumTo(100) } + } + + { + def sumTo(n: Int): Either[String, Int] = { + iterate(0) { case (acc, i) => + if (n < 0) Some(Left("requirement failed")) + else if (i > n) None + else Some(Right(acc + i)) + } + } + + "iterate" should "work for sumTo(100)" in { + assertResult(Right(5050)) { sumTo(100) } + } + + "iterate" should "work for sumTo(-1)" in { + assertResult(Left("requirement failed")) { sumTo(-1) } + } + + val one = parse("1") + + it should "stop if the callback body returns None" in { + assertResult(Right(one)) { + iterate(one) { (_, _) => None } + } + } + + it should "increment the loop counter on each iteration and use e if the callback body returns Some(e)" in { + assertResult(Right(parse("--1"))) { + iterate(one) { (e: Expr, n: Int) => + if (n == 2) None else Some(Right(Unary(Neg, e))) + } + } + } + } + + "step/call" should "evaluate a function using small-step semantics" in { + val f = "f" + val x = "x" + val e1 = Fun(None, x, Binary(Plus, Var(x), N(1))) + val e2 = N(2) + val e3 = iterateStep(Call(e1, e2)) + assert(e3 === Right(N(3))) + } + + it should "handle recursive functions using small-step semantics" in { + val f = "f" + val x = "x" + val fbody = If( + Binary(Eq, Var(x), N(0)), + Var(x), + Binary(Plus, Var(x), Call(Var(f), Binary(Minus, Var(x), N(1)))) + ) + val e1 = Fun(Some(f), x, fbody) + val e2 = N(3) + val e3 = iterateStep(Call(e1, e2)) + assert(e3 === Right(N(6))) + } + + /* Some tests based on rules */ + + { + val xval = N(2) + val varx = Var("x") + + val e1 = parse("2 - 1 - 1") + val e1p = parse("1 - 1") + val e2 = parse("3 - 1 - 1") + val e2p = parse("2 - 1") + val v1 = N(0) + val v2 = N(1) + + val vidfunction = parse("function (x) { return x }") + + "DoNeg" should "perform DoNeg" in { + val np = -0 + assertResult(Right(N(np))) { + step(Unary(Neg, v1)) + } + } + + "SearchUnary" should "perform SearchUnary" in { + assertResult(Right(Unary(Neg, e1p))) { + step(Unary(Neg, e1)) + } + } + + val e_callerror = Call(N(1), N(2)) + + "TypeErrorCall" should "perform TypeErrorCall" in { + assertResult(Left(DynamicTypeError(e_callerror))) { + step(e_callerror) + } + } + } +} + +class Lab3JsyTests extends jsy.tester.JavascriptyTester(None, "lab3", Lab3) diff --git a/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala new file mode 100644 index 0000000..48e789c --- /dev/null +++ b/lab3/src/test/scala/jsy/tester/JavascriptyTester.scala @@ -0,0 +1,23 @@ +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) + } + } +} |