aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:02:58 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:02:58 -0700
commit08f9cae13d0dce99d40a6d93432a84cb075bebfc (patch)
tree5714d73c616b511d8fa5ea8a0ef1d8405f13ce90
parent0d13c649bdabafde59233609be7bd88e273c7ae6 (diff)
downloadcsci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.tar.gz
csci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.zip
Unit 3
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--big-step-exercise.ipynb2342
-rw-r--r--lab3/build.sbt46
-rw-r--r--lab3/project/build.properties1
-rw-r--r--lab3/small-step-lab.ipynb1335
-rw-r--r--lab3/src/main/scala/jsy/lab3/Lab3.scala360
-rw-r--r--lab3/src/main/scala/jsy/lab3/Lab3.worksheet.js24
-rw-r--r--lab3/src/main/scala/jsy/lab3/Lab3.worksheet.sc51
-rw-r--r--lab3/src/main/scala/jsy/lab3/Parser.scala284
-rw-r--r--lab3/src/main/scala/jsy/lab3/ast.scala106
-rw-r--r--lab3/src/main/scala/jsy/util/JsyApplication.scala191
-rw-r--r--lab3/src/test/resources/lab3/test3004_call.ans8
-rw-r--r--lab3/src/test/resources/lab3/test3004_call.jsy2
-rw-r--r--lab3/src/test/resources/lab3/test3006_curry.ans8
-rw-r--r--lab3/src/test/resources/lab3/test3006_curry.jsy2
-rw-r--r--lab3/src/test/resources/lab3/test3008_call.ans48
-rw-r--r--lab3/src/test/resources/lab3/test3008_call.jsy2
-rw-r--r--lab3/src/test/scala/jsy/lab3/Lab3Spec.scala150
-rw-r--r--lab3/src/test/scala/jsy/tester/JavascriptyTester.scala23
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)
+ }
+ }
+}