diff options
Diffstat (limited to 'lab3/small-step-lab.ipynb')
-rw-r--r-- | lab3/small-step-lab.ipynb | 1335 |
1 files changed, 1335 insertions, 0 deletions
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 +} |