diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:58 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:02:58 -0700 |
commit | 08f9cae13d0dce99d40a6d93432a84cb075bebfc (patch) | |
tree | 5714d73c616b511d8fa5ea8a0ef1d8405f13ce90 /big-step-exercise.ipynb | |
parent | 0d13c649bdabafde59233609be7bd88e273c7ae6 (diff) | |
download | csci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.tar.gz csci3155-08f9cae13d0dce99d40a6d93432a84cb075bebfc.zip |
Unit 3
Signed-off-by: Jack Sangdahl <[email protected]>
Diffstat (limited to 'big-step-exercise.ipynb')
-rw-r--r-- | big-step-exercise.ipynb | 2342 |
1 files changed, 2342 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 +} |