diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:03:45 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:03:45 -0700 |
commit | 8bb81e391405554d02ec36574db2ca58300c89c4 (patch) | |
tree | 2e6e16ea68cefc63466b4cc3a56352843ec6a92c | |
parent | ae554ab7d4d425fa821c1167e734db3425a881f6 (diff) | |
download | csci3155-8bb81e391405554d02ec36574db2ca58300c89c4.tar.gz csci3155-8bb81e391405554d02ec36574db2ca58300c89c4.zip |
Unit 5
Signed-off-by: Jack Sangdahl <[email protected]>
30 files changed, 6164 insertions, 0 deletions
diff --git a/encapsulating-effects-exercise.ipynb b/encapsulating-effects-exercise.ipynb new file mode 100644 index 0000000..5a027ff --- /dev/null +++ b/encapsulating-effects-exercise.ipynb @@ -0,0 +1,2715 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "71c6cfda", + "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": 37, + "id": "4313a4e4", + "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\"\"\u001b[39m" + ] + }, + "execution_count": 37, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "val NAME = \"Jack Sangdahl\"\n", + "val COLLABORATORS = \"N/A\"" + ] + }, + { + "cell_type": "markdown", + "id": "f9e75639-fa29-4bcb-a412-bd8ece4194ce", + "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", + "# Exercise: Programming with Encapsulated Effects\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", + "<!-- 26 Static Type Checking -->\n", + "\n", + "<!-- 27 Objects -->\n", + "\n", + "<!-- 27 Static Type Checking Lab -->\n", + "\n", + "<!-- 30 Mutable State -->\n", + "\n", + "<!-- Encapsulating Effects Exercise -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary learning goal of this exercise is to get experience\n", + "programming with encapsulated effects.\n", + "\n", + "We will also consider the idea of transforming code represented as an\n", + "abstract syntax tree to make it easier to implement subsequent passes\n", + "like 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": 38, + "id": "0d92d0c2", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "f54ea3fcefbe483a990582ef3ecd2a1d", + "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._, matchers.should._\n", + "\u001b[39m\n", + "\u001b[32mimport \u001b[39m\u001b[36m$ivy.$ , org.scalatestplus.scalacheck._\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": 38, + "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._, matchers.should._\n", + "import $ivy.`org.scalatestplus::scalacheck-1-18:3.2.19.0`, org.scalatestplus.scalacheck._\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": "a662e14f-b397-418e-a640-0dd8f91e9fc1", + "metadata": {}, + "source": [ + "## TypeScripty: Numbers, Booleans, and Functions\n", + "\n", + "### Syntax\n", + "\n", + "In this assignment, we consider a simplified TypeScripty with numbers,\n", + "booleans, and functions types.\n", + "\n", + "Function literals\n", + "$x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1$\n", + "have exactly one parameter, are always named, and must have a return\n", + "type annotation. The name may be used to define recursive functions.\n", + "\n", + "The expressions include variable uses $x$, variable binding\n", + "$\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2$, unary\n", + "$\\mathop{\\mathit{uop}} e_1$ and binary $e_1 \\mathbin{\\mathit{bop}} e_2$\n", + "expressions, if-then-else $e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3$, and\n", + "function call $e_1\\texttt{(}e_2\\texttt{)}$. The unary operators are\n", + "limited to number negation $\\texttt{-}$ and boolean negation\n", + "$\\texttt{!}$, and the binary operators are limited to number addition\n", + "$\\texttt{+}$, number times $\\texttt{*}$, and equality $\\texttt{===}$:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + " \\text{types} & \\tau& \\mathrel{::=}&\n", + " \\texttt{number}\n", + " \\mid\\texttt{bool}\n", + " \\mid\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau'\n", + " \\\\\n", + " \\text{values} & v& \\mathrel{::=}&\n", + " n\n", + " \\mid b\n", + " \\mid x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\\\\n", + " \\text{expressions} & e& \\mathrel{::=}&\n", + " x\n", + " \\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + " \\\\\n", + " & & \\mid& n\n", + " \\mid\\mathop{\\mathit{uop}} e_1\n", + " \\mid e_1 \\mathbin{\\mathit{bop}} e_2\n", + " \\\\\n", + " & & \\mid& b\n", + " \\mid e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + " \\\\\n", + " & & \\mid& x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\mid e_1\\texttt{(}e_2\\texttt{)}\n", + " \\\\\n", + " \\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{-}\\mid\\texttt{!}\n", + " \\\\\n", + " \\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{+}\\mid\\texttt{*}\\mid\\texttt{===}\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 1: Syntax of TypeScripty with recursive functions and limited\n", + "arithmetic-logical expressions.\n", + "\n", + "We give a Scala representation of the abstract syntax, along with an\n", + "implementation of computing the free variables of an expression and\n", + "determining an expression is closed:" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "id": "eb35c7e6", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mtrait\u001b[39m \u001b[36mTyp\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mTNumber\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mTBool\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mTFun\u001b[39m\n", + "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[36mUnary\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mBinary\u001b[39m\n", + "defined \u001b[32mclass\u001b[39m \u001b[36mB\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\n", + "defined \u001b[32mtrait\u001b[39m \u001b[36mUop\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mNeg\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mNot\u001b[39m\n", + "defined \u001b[32mtrait\u001b[39m \u001b[36mBop\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mPlus\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mTimes\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mEq\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mfreeVars\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36misClosed\u001b[39m" + ] + }, + "execution_count": 39, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "trait Typ // t\n", + "case object TNumber extends Typ // t ::= number\n", + "case object TBool extends Typ // t ::= bool\n", + "case class TFun(yt: (String,Typ), tret: Typ) extends Typ // t ::= (y: t) => tret\n", + "\n", + "trait Expr // e\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 Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1\n", + "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop b2\n", + "\n", + "case class B(b: Boolean) extends Expr // e ::= b\n", + "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3\n", + "\n", + "case class Fun(x: String, yt: (String, Typ), tret: Typ, e1: Expr) extends Expr // e ::= x(y: t): tret => e1\n", + "case class Call(e1: Expr, e2: Expr) extends Expr // e ::= e1(e2)\n", + "\n", + "trait Uop // uop\n", + "case object Neg extends Uop // uop ::= -\n", + "case object Not extends Uop // uop ::= !\n", + "\n", + "trait Bop // bop\n", + "case object Plus extends Bop // bop ::= *\n", + "case object Times extends Bop // bop ::= *\n", + "case object Eq extends Bop // bop ::= ===\n", + "\n", + "def freeVars(e: Expr): Set[String] = e match {\n", + " case Var(x) => Set(x)\n", + " case ConstDecl(x, e1, e2) => freeVars(e1) | (freeVars(e2) - x)\n", + " case N(_) | B(_) => Set.empty\n", + " case Unary(_, e1) => freeVars(e1)\n", + " case Binary(_, e1, e2) => freeVars(e1) | freeVars(e2)\n", + " case If(e1, e2, e3) => freeVars(e1) | freeVars(e2) | freeVars(e3)\n", + " case Fun(x, (y, _), _, e1) => freeVars(e1) - x - y\n", + " case Call(e1, e2) => freeVars(e1) | freeVars(e2)\n", + "}\n", + "\n", + "def isClosed(e: Expr): Boolean = freeVars(e).isEmpty" + ] + }, + { + "cell_type": "markdown", + "id": "51fc43c3-617d-4e9b-9b52-144ff63d77c7", + "metadata": {}, + "source": [ + "### Static Type Checking\n", + "\n", + "The typing judgment $\\Gamma \\vdash e : \\tau$ says, āIn typing\n", + "environment $\\Gamma$, expression $e$ has type $\\tau$ā where the typing\n", + "environment $\\Gamma\\mathrel{::=}\\cdot\\mid\\Gamma, x : \\tau$ is a finite\n", + "map from variables to types, assigning types to the free variables of\n", + "$e$. We give the expected typing rules that we have seen before,\n", + "restricted to this simpler language:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeVar]{\n", + "}{\n", + " \\Gamma \\vdash x : \\Gamma(x)\n", + "}$\n", + "\n", + "$\\inferrule[TypeConstDecl]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\Gamma, x : \\tau_1 \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n", + "}$\n", + "\n", + "$\\inferrule[TypeNumber]{\n", + "}{\n", + " \\Gamma \\vdash n : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypeNeg]{\n", + " \\Gamma \\vdash e_1 : \\texttt{number}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypeArith]{\n", + " \\Gamma \\vdash e_1 : \\texttt{number}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{number}\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{*} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypeBool]{\n", + "}{\n", + " \\Gamma \\vdash b : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeEq]{\n", + " \\Gamma \\vdash e_1 : \\tau\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeIf]{\n", + " \\Gamma \\vdash e_1 : \\texttt{bool}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + " \\and\n", + " \\Gamma \\vdash e_3 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 : \\tau\n", + "}$\n", + "\n", + "$\\inferrule[TypeFunctionRec]{\n", + " \\Gamma, x : \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' , y : \\tau \\vdash e' : \\tau'\n", + "}{\n", + " \\Gamma \\vdash x\\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)}\\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n", + "}$\n", + "\n", + "$\\inferrule[TypeCall]{\n", + " \\Gamma \\vdash e_1 : \\texttt{(}y\\texttt{:}\\,\\tau\\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1\\texttt{(}e_2\\texttt{)} : \\tau'\n", + "}$\n", + "\n", + "FigureĀ 2: Typing of TypeScripty with recursive functions and limited\n", + "arithmetic-logical expressions.\n", + "\n", + "## Error Effects\n", + "\n", + "As we have seen, the most direct way to implement a type checker\n", + "following the typing judgment $\\Gamma \\vdash e : \\tau$ is a function\n", + "`hastype: (Map[String, Typ], Expr) => Typ` that takes an typing\n", + "environment $\\Gamma$ represented by a `Map[String, Typ]` and an\n", + "expression $e$ represented by a `Expr` and returns a type $\\tau$\n", + "represented by a `Typ`:\n", + "\n", + "``` scala\n", + "def hastype(tenv: Map[String, Typ], e: Expr): Typ = ???\n", + "```\n", + "\n", + "However, with this function signature for `hastype`, we necessarily have\n", + "to throw an exception or crash to indicate that an expression $e$ is\n", + "ill-typed. An expression is ill-typed when there are no rules that allow\n", + "us to derive a judgment $\\Gamma \\vdash e : \\tau$ for any $\\tau$ and\n", + "$\\Gamma$.\n", + "\n", + "In this exercise, we implement a version of `hastype` that makes\n", + "explicit the possibility of a type error.\n", + "\n", + "### Type-Error Result\n", + "\n", + "We first extend our typing judgment form $\\Gamma \\vdash e : r$ where a\n", + "type-checker result $r$ is either a type $\\tau$ or a type-error result\n", + "$\\mathit{typerr}$:\n", + "\n", + "<span class=\"text\">type-checker result</span>\n", + "$\\quad r \\mathrel{::=} \\mathit{typerr} \\mid \\tau$\n", + "\n", + "<span class=\"text\">type-error result</span>\n", + "$\\quad \\mathit{typerr} \\mathrel{::=} \\mathop{\\mathsf{typerr}}(e : \\tau)$\n", + "\n", + "This extended judgment form makes explicit when an expression is\n", + "ill-typed. A type-error result\n", + "\n", + "$$\n", + "\\mathop{\\mathsf{typerr}}(e : \\tau)\n", + "$$\n", + "\n", + "includes an expression $e$ with its inferred type $\\tau$ but is used in\n", + "a context another type is expected. We can consider such a type-error\n", + "result being used to give a descriptive error message to the programmer.\n", + "\n", + "We now give some rules that introduce type-error results and propagates\n", + "them:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : r$}$\n", + "\n", + "$\\inferrule[TypeErrorNeg]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\tau_1 \\neq \\texttt{number}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1) \n", + "}$\n", + "\n", + "$\\inferrule[PropagateNeg]{\n", + " \\Gamma \\vdash e_1 : \\mathit{typerr}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\mathit{typerr}\n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorEq]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau_2\n", + " \\and\n", + " \\tau_1 \\neq \\tau_2\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 : \\mathop{\\mathsf{typerr}}(e_2 : \\tau_2) \n", + "}$\n", + "\n", + "$\\inferrule[PropagateEq1]{\n", + " \\Gamma \\vdash e_1 : \\mathit{typerr}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 : \\mathit{typerr}\n", + "}$\n", + "\n", + "$\\inferrule[PropagateEq2]{\n", + " \\Gamma \\vdash e_2 : \\mathit{typerr}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{===}} e_2 : \\mathit{typerr}\n", + "}$\n", + "\n", + "Observe that the $\\TirName{TypeErrorEq}$ blames $e_2$: it infers the\n", + "type $\\tau_1$ for $e_1$ and then expects that $e_2$ has type $\\tau_1$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (4 points)**</span> Define the\n", + "$\\TirName{TypeErrorNot}$ rule that introduces a type-error result when\n", + "the boolean negation expression $\\mathop{\\texttt{!}} e_1$ is ill-typed:\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "f2d9795c-8c11-4fb7-9c86-9a55c1ccd663", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "cd79e4bdf75b953b4f599263415f45a5", + "grade": true, + "grade_id": "hastype-typeerror-not", + "locked": false, + "points": 4, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "If the type of `e1` is not a boolean, a type error should be raised. The $\\TirName{TypeErrorNot}$ rule can be implemented as such:\n", + "\n", + "$\\inferrule[TypeErrorNot]{\n", + " \\Gamma \\vdash e_1 : \\tau_1 \\and \\tau_1 \\neq \\texttt{boolean}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{!}} e_1 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1)\n", + "}$" + ] + }, + { + "cell_type": "markdown", + "id": "c636cad7-6a99-4a6d-b5eb-a95056b49ec1", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: Use $\\TirName{TypeErrorNeg}$ as a model.\n", + "- You may give the rule in LaTeX math or as plain text (ascii art)\n", + " approximating the math rendering. For example,\n", + "\n", + "<!-- -->\n", + "\n", + " TypeErrorNeg\n", + " Gamma |- e1 : tau1 tau1 != number\n", + " ------------------------------------------\n", + " Gamma |- -e1 : typerr(e1 : tau1 != number)\n", + "\n", + "The LaTeX code for the rendered $\\TirName{TypeErrorNeg}$ rule above is\n", + "as follows:\n", + "\n", + "``` tex\n", + "\\inferrule[TypeErrorNeg]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\tau_1 \\neq \\texttt{number}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1 \\neq \\texttt{number})\n", + "}\n", + "```\n", + "\n", + "<span class=\"theorem-title\">**Exercise 2 (8 points)**</span> Define\n", + "**two** $\\TirName{TypeErrorIf}$ rules that introduces a type-error\n", + "result when the if-then-else expression\n", + "$e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3$ is ill-typed:\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "1442119d-5f94-46a2-a5b5-98d138cf3ee4", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "c65bd4e71cb952a36967e8ce3c7846d8", + "grade": true, + "grade_id": "hastype-typeerror-if", + "locked": false, + "points": 8, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "The two types of errors that need to be fielded are if condition `e1` is nota boolean value, or if branches `e2` and `e2` do not have the same type. These rules can be implemented as such:\n", + "\n", + "$\\inferrule[TypeErrorIf1]{\n", + " \\Gamma \\vdash e_1 : \\tau_1 \\and \\tau_1 \\neq \\texttt{boolean}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathop{\\texttt{?}} e_2 : e_3 : \\mathop{\\mathsf{typerr}}(e_1 : \\tau_1)\n", + "}$\n", + "\n", + "$\\inferrule[TypeErrorIf2]{\n", + " \\Gamma \\vdash e_1 : \\texttt{boolean}\n", + " \\and \\Gamma \\vdash e_2 : \\tau_2\n", + " \\and \\Gamma \\vdash e_3 : \\tau_3\n", + " \\and \\tau_2 \\neq \\tau3\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathop{\\texttt{?}} e_2 : e_3 \\mathop{\\mathsf{typerr}}(e_2 : \\tau_2, e_3 : \\tau_3)\n", + "}$" + ] + }, + { + "cell_type": "markdown", + "id": "d8fa5d8f-f8e0-494f-a2c5-424f8676a458", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: Use $\\TirName{TypeErrorNeg}$ and $\\TirName{TypeErrorEq}$ as a\n", + " model for the two rules, respectively.\n", + "\n", + "### Implementation\n", + "\n", + "We represent a type-error result $r$ as an\n", + "`Either[StaticTypeError, Typ]`.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3 (26 points)**</span> Complete\n", + "the following implementation of\n", + "\n", + "`hastype: (Map[String, Typ], Expr) => Either[StaticTypeError, Typ]`\n", + "\n", + "corresponding to the judgment form $\\Gamma \\vdash e : r$.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "id": "14b2c8ce", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "d6ced05c47f1d78d16a5489ab77967f8", + "grade": false, + "grade_id": "hastype-typeerror-implementation", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mclass\u001b[39m \u001b[36mStaticTypeError\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36mhastype\u001b[39m\n", + "defined \u001b[32mfunction\u001b[39m \u001b[36minferType\u001b[39m" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "case class StaticTypeError(tbad: Typ, esub: Expr, e: Expr) {\n", + " override def toString = s\"StaticTypeError: invalid type $tbad for sub-expression $esub in $e\"\n", + "}\n", + "\n", + "def hastype(tenv: Map[String, Typ], e: Expr): Either[StaticTypeError, Typ] = {\n", + "\n", + " def err[T](esub: Expr, tgot: Typ): Either[StaticTypeError, T] =\n", + " Left(StaticTypeError(tgot, esub, e))\n", + "\n", + " def typecheck(tenv: Map[String, Typ], e: Expr, tshould: Typ): Either[StaticTypeError, Unit] =\n", + " hastype(tenv, e) flatMap { tgot =>\n", + " if (tgot == tshould)\n", + " Right(())\n", + " else err(e, tgot)\n", + " }\n", + "\n", + " e match {\n", + " case Var(x) => Right(tenv(x))\n", + " case ConstDecl(x, e1, e2) =>\n", + " hastype(tenv, e1) flatMap { t1 =>\n", + " hastype(tenv + (x -> t1), e2)\n", + " }\n", + " case N(_) => Right(TNumber)\n", + " case B(_) => Right(TBool)\n", + " case Unary(Neg, e1) => typecheck(tenv, e1, TNumber) map { _ => TNumber }\n", + " case Unary(Not, e1) => typecheck(tenv, e1, TBool) map { _ => TBool }\n", + " case Binary(Plus|Times, e1, e2) =>\n", + " typecheck(tenv, e1, TNumber) flatMap { _ =>\n", + " typecheck(tenv, e2, TNumber) map { _ => TNumber }\n", + " }\n", + " case Binary(Eq, e1, e2) =>\n", + " hastype(tenv, e1) flatMap { t1 =>\n", + " hastype(tenv, e2) flatMap { t2 =>\n", + " if (t1 == t2) Right(TBool) else err(e2, t2)\n", + " }\n", + " }\n", + " case If(e1, e2, e3) =>\n", + " typecheck(tenv, e1, TBool) flatMap { _ =>\n", + " hastype(tenv, e2) flatMap { t2 =>\n", + " hastype(tenv, e3) flatMap { t3 =>\n", + " if (t2 == t3) Right(t2) else err(e3, t3)\n", + " }\n", + " }\n", + " }\n", + " case Fun(x, yt @ (y, t), tret, e1) =>\n", + " val funcType = TFun(yt, tret)\n", + " hastype(tenv + (x -> funcType) + (y -> t), e1) flatMap { tbody =>\n", + " if (tbody == tret) Right(funcType)\n", + " else err(e1, tbody)\n", + " }\n", + " case Call(e1, e2) =>\n", + " hastype(tenv, e1) flatMap {\n", + " case TFun((_, targ), tret) => typecheck(tenv, e2, targ) map { _ => tret }\n", + " case tgot => err(e1, tgot)\n", + " }\n", + " }\n", + "}\n", + "\n", + "def inferType(e: Expr): Either[StaticTypeError, Typ] = {\n", + " require(isClosed(e), s\"$e should be closed\")\n", + " hastype(Map.empty, e)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "a2e96f44-91d8-41ef-ad03-1787239e8f56", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- The `err` helper function is simply a shortcut to construct\n", + " `StaticTypeError` with the input expression `e`.\n", + "- The `typecheck` helper function implements a common functionality\n", + " where we want to call `hastype` recursively with a sub-expression to\n", + " infer a type `tgot` and check it is equal to an expected type\n", + " `tshould`. If `tgot != tshould`, we return an `err`; otherwise, we\n", + " return success.\n", + "- Hint: Start by implementing the $\\TirName{Type}$ rules from\n", + " <a href=\"#fig-typescripty-minrecfun-typing\"\n", + " class=\"quarto-xref\">FigureĀ 2</a> without worrying about type errors.\n", + " Then, add $\\TirName{TypeError}$ and $\\TirName{Propagate}$ cases.\n", + "- Note that not all the $\\TirName{TypeError}$ and\n", + " $\\TirName{Propagate}$ rules are given, but they follow the patterns\n", + " given above. If you get stuck to implement the code for\n", + " $\\TirName{TypeError}$ for a particular construct, try writing out\n", + " the rule.\n", + "- It is fine to initially pattern match on\n", + " `Either[StaticTypeError, Expr]` values that result from calls to\n", + " `hastype` and `typecheck` (i.e., for `Left` and `Right` values).\n", + " However, challenge yourself to replace them with `map` or `flatMap`\n", + " calls to minimize your typing and opportunities for bugs to creep\n", + " in. It is possible to replace all pattern matches for `Left` and\n", + " `Right` values with calls to `map` and `flatMap` calls.\n", + "- Use the given cases (e.g., $\\TirName{TypeNeg}$,\n", + " $\\TirName{TypeErrorNeg}$, $\\TirName{PropagateNeg}$) as a model.\n", + " Identify how $\\TirName{TypeNeg}$, $\\TirName{TypeErrorNeg}$, and\n", + " $\\TirName{PropagateNeg}$ manifests in the code.\n", + "- For accelerated students, you can make the code even more compact\n", + " (and arguably more readable) by replacing `flatMap` and `map` calls\n", + " with `for`-`yield` expressions. Note that not all cases can be\n", + " implemented with `for`-`yield` expressions.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "id": "fd5d3dfc", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "410d74ebf1a362f169386234cef5a82a", + "grade": true, + "grade_id": "hastype-constdecl-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd41$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/ConstDecl\u001b[0m\n", + "\u001b[32m- should TypeConstDecl\u001b[0m\n", + "\u001b[32m- should PropagateConstDecl1\u001b[0m\n", + "\u001b[32m- should PropagateConstDecl2\u001b[0m\n", + "\u001b[36mRun completed in 6 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Binary(Plus, N(1), N(2)) \n", + " val e2 = Binary(Times, Var(\"a\"), N(3))\n", + "\n", + " val e3 = ConstDecl(\"a\", e1, e2)\n", + " \"hastype/ConstDecl\" should \"TypeConstDecl\" in {\n", + " assertResult(Right(TNumber)) {inferType(e1) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateConstDecl1\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(ConstDecl(\"a\", bade, N(1))) }\n", + " }\n", + "\n", + " it should \"PropagateConstDecl2\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(ConstDecl(\"a\", N(1), bade)) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "id": "3fedb1ca", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "2ccc667ac624a8997f777e6df3d695ca", + "grade": true, + "grade_id": "hastype-not-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd42$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/Unary/Not\u001b[0m\n", + "\u001b[32m- should TypeNot\u001b[0m\n", + "\u001b[32m- should TypeErrorNot\u001b[0m\n", + "\u001b[32m- should PropagateNot\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Unary(Not, B(true))\n", + " \"hastype/Unary/Not\" should \"TypeNot\" in {\n", + " assertResult(Right(TBool)) {inferType(e1) }\n", + " }\n", + "\n", + " val e2 = Unary(Not, N(1))\n", + " it should \"TypeErrorNot\" in {\n", + " assertResult(Left(StaticTypeError(TNumber, N(1), e2))) {inferType(e2) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateNot\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Unary(Not, bade)) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "id": "cfa09d18", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "62cfbcc928e347c29f53bbd95f940e3c", + "grade": true, + "grade_id": "hastype-plus-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd43$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/Binary/Plus|Times\u001b[0m\n", + "\u001b[32m- should TypeArith\u001b[0m\n", + "\u001b[32m- should TypeErrorArith\u001b[0m\n", + "\u001b[32m- should PropagateArith\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Binary(Plus, N(1), N(2))\n", + " \"hastype/Binary/Plus|Times\" should \"TypeArith\" in {\n", + " assertResult(Right(TNumber)) { inferType( Binary(Times, e1, N(2)) ) }\n", + " }\n", + "\n", + " val e2 = Binary(Plus, B(true), e1)\n", + " it should \"TypeErrorArith\" in {\n", + " assertResult(Left(StaticTypeError(TBool, B(true), e2))) { inferType(e2) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateArith\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Binary(Plus, bade, N(3))) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "id": "5fcb7d22", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "e0cd4dc1c6b8b6a646f4c974996f2dcf", + "grade": true, + "grade_id": "hastype-if-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 4\u001b[0m\n", + "\u001b[32mcmd44$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/If\u001b[0m\n", + "\u001b[32m- should TypeIf\u001b[0m\n", + "\u001b[32m- should TypeErrorIfGuard\u001b[0m\n", + "\u001b[32m- should TypeErrorIfBody\u001b[0m\n", + "\u001b[32m- should PropagateIf\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 4\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Binary(Plus, N(1), N(2))\n", + " \"hastype/If\" should \"TypeIf\" in {\n", + " assertResult(Right(TNumber)) { inferType( If(B(true), e1, N(3)) ) }\n", + " }\n", + "\n", + " val e2 = If(N(1), e1, e1)\n", + " it should \"TypeErrorIfGuard\" in {\n", + " assertResult(Left(StaticTypeError(TNumber, N(1), e2))) { inferType(e2) }\n", + " }\n", + "\n", + " val e3 = If(B(false), B(true), N(1))\n", + " it should \"TypeErrorIfBody\" in {\n", + " assertResult(Left(StaticTypeError(TNumber, N(1), e3))) { inferType(e3) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateIf\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(If(B(true), bade, N(3))) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "id": "449ea45d", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "40a19d9980eb789b6eca1d18553ef385", + "grade": true, + "grade_id": "hastype-fun-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n", + "\u001b[32mcmd45$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/Fun\u001b[0m\n", + "\u001b[32m- should TypeFun\u001b[0m\n", + "\u001b[32m- should PropagateFun\u001b[0m\n", + "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 2\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Binary(Times, Var(\"i\"), N(3))\n", + " def fun(e: Expr) = Fun(\"f\", (\"i\", TNumber), TNumber, e)\n", + " \"hastype/Fun\" should \"TypeFun\" in {\n", + " assertResult(Right(TFun((\"i\", TNumber), TNumber))) { inferType(fun(e1)) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateFun\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(fun(bade)) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 46, + "id": "73508956", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ec856ba1df491639a9800ab24b3a7a23", + "grade": true, + "grade_id": "hastype-call-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd46$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype/Call\u001b[0m\n", + "\u001b[32m- should TypeCall\u001b[0m\n", + "\u001b[32m- should TypeErrorCall\u001b[0m\n", + "\u001b[32m- should PropagateCall2\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val e1 = Binary(Times, Var(\"i\"), Call(Var(\"f\"), N(3)))\n", + " def fun(e: Expr) = Fun(\"f\", (\"i\", TNumber), TNumber, e)\n", + " val e2 = \n", + " \"hastype/Call\" should \"TypeCall\" in {\n", + " assertResult(Right(TNumber)) { inferType(Call(fun(e1), N(10))) }\n", + " }\n", + "\n", + " val e3 = Call(B(true), N(1))\n", + " it should \"TypeErrorCall\" in {\n", + " assertResult(Left(StaticTypeError(TBool, B(true), e3))) { inferType(e3) }\n", + " }\n", + "\n", + " val badesub = B(true)\n", + " val bade = Binary(Plus, N(1), badesub)\n", + " it should \"PropagateCall2\" in {\n", + " assertResult(Left(StaticTypeError(TBool, badesub, bade))) { inferType(Call(fun(e1),bade)) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 47, + "id": "c170737a", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "f7e3385fd933df313e764a9a55bd64c6", + "grade": true, + "grade_id": "hastype-all-tester", + "locked": true, + "points": 2, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd47$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mhastype\u001b[0m\n", + "\u001b[32m- should type check factorial\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (2 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val factorial = Fun(\"fact\", (\"n\", TNumber), TNumber,\n", + " If(Binary(Eq, Var(\"n\"), N(1)),\n", + " N(1),\n", + " Binary(Times, Var(\"n\"), Call(Var(\"fact\"), Binary(Plus, Var(\"n\"), N(-1)))))\n", + " )\n", + " \"hastype\" should \"type check factorial\" in {\n", + " assertResult(Right(TNumber)) { inferType(Call(factorial, N(4))) }\n", + " }\n", + "}, 2)" + ] + }, + { + "cell_type": "markdown", + "id": "c4896a74-23f0-4392-9488-da88ab020973", + "metadata": {}, + "source": [ + "## Mutation Effects\n", + "\n", + "### Defining Generic `DoWith` Methods\n", + "\n", + "Recall the idea of encapulating a state transforming function\n", + "`S => (S, A)` as a collection-like data type\n", + "(**?@sec-encapsulating-mutation-effects**), which we call a\n", + "`DoWith[S, A]`:" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "id": "6e523d01", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mclass\u001b[39m \u001b[36mDoWith\u001b[39m\n", + "defined \u001b[32mobject\u001b[39m \u001b[36mDoWith\u001b[39m\n", + "\u001b[32mimport \u001b[39m\u001b[36mDoWith._\u001b[39m" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "sealed class DoWith[S, A] private (doer: S => (S, A)) {\n", + " def map[B](f: A => B): DoWith[S, B] = new DoWith[S, B]({\n", + " (s: S) => {\n", + " val (s_, a) = doer(s)\n", + " (s_, f(a))\n", + " }\n", + " })\n", + "\n", + " def flatMap[B](f: A => DoWith[S, B]): DoWith[S, B] = new DoWith[S, B]({\n", + " (s: S) => {\n", + " val (s_, a) = doer(s)\n", + " f(a)(s_)\n", + " }\n", + " })\n", + "\n", + " def apply(s: S): (S, A) = doer(s)\n", + "}\n", + "\n", + "object DoWith {\n", + " def doget[S]: DoWith[S, S] = new DoWith[S, S]({ s => (s, s) })\n", + " def doput[S](s: S): DoWith[S, Unit] = new DoWith[S, Unit]({ _ => (s, ()) })\n", + "}\n", + "\n", + "import DoWith._" + ] + }, + { + "cell_type": "markdown", + "id": "db0a5acb-4f1a-47e9-86d4-b088e97537e5", + "metadata": {}, + "source": [ + "Consider a `DoWith[S,A]` as a ācollectionā holding an `A` somewhat like\n", + "`List[A]` or `Option[A]`. While `List[A]` encapsulates a sequence of\n", + "elements of type `A` elements and `Option[A]` encapsulates an optional\n", + "`A`, a `DoWith[S, A]` encapsulates a *computation* that results in an\n", + "`A`, using an input-output state `S` (i.e., a `S => (S, A)` function).\n", + "It is collection-like because it also has `map` and `flatMap` methods to\n", + "transform that computation.\n", + "\n", + "We also define two functions for a client to create a `DoWith[S, A]`\n", + "encapsulating particular `S => (S, A)`{.scala functions}:\n", + "\n", + "- The `doget[S]` method constructs a `DoWith[S, S]` that makes the\n", + " ācurrentā state the result (i.e., `s => (s, s)`). Intuitively, it\n", + " āgetsā the state.\n", + "- The `doput[S](s: S)` method constructs a `DoWith[S, Unit]` that\n", + " makes the given state `s` the ācurrentā state (i.e.,\n", + " `_ => (s, ())`). Intuitively, it āputsā `s` into the state.\n", + "\n", + "We require the client to create `DoWith[S, A]` values using only the\n", + "`doget` and `doput` constructors.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 4 (4 points)**</span> Read the\n", + "implementations `map[B]` and `flatMap[B]` methods of `DoWith[S, A]`\n", + "above. Explain how they transform the encapsulated `doer: S => (S, A)`\n", + "function. Compare and contrast themāwhat do they do that is same, and\n", + "what is the key difference between them?\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "markdown", + "id": "c74beb30-b33b-4209-9229-a75606fed770", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "markdown", + "checksum": "37061be7f5cd361ab5e98f4a5ee7970b", + "grade": true, + "grade_id": "map-flatMap-diff", + "locked": false, + "points": 4, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "source": [ + "### `map[B]` Method\n", + "This method transforms the result `A` into another result `B`, while leaving the state of `S` unchanged. In the context of the encapsulated function `doer: S => (S, A)`, `map` modifies the second element of the tuple produced by `doer`, applying `f` toget `B`.\n", + "\n", + "### `flatMap[B]` Method\n", + "This method chains a new `DoWith[S, B]` computation that depends on the result of the current one, which potentially alters the state of `S` again. In the context of the encapsulated function `doer: S => (S, A)`, the first computation of `flatMap` produces a new state and result `(S', A)`. Then, based on the value of `A`, a new computation `f(A)` is performed, which may further transform the state to `S''` and the resulting value in `B`.\n", + "\n", + "### Comparison\n", + "Both `map` and `flatMap` methods work with computations of type `S => (S, A)` and return new computations that transform the result. These methods differ in mutability ā `map` only transforms the resulting value while keeping the state intact, whereas `flatMap` can transform both the result and the state through chaining additional computations." + ] + }, + { + "cell_type": "markdown", + "id": "91c410d7-d065-4456-aaf0-c23faf60d85c", + "metadata": {}, + "source": [ + "As a `DoWith[S, A]` encapsulates any function of type `S => (S, A)`,\n", + "there are other commonly needed functions of this type. We implement\n", + "methods for constructing `DoWith[S, A]` encapsulating two more\n", + "commonly-needed computations in terms of `doget` and `doput`.\n", + "\n", + "- The `doreturn[S, A](a: A)` method constructs a `DoWith[S, A]` that\n", + " leaves the ācurrentā state as-is and returns the given result `a`\n", + " (i.e., `s => (s, a)`). It technically does not need to be given in\n", + " the library, as it can be defined in terms of `doget` and `map`.\n", + "- The `domodify[S](f: S => S)` method constructs a `DoWith[S, Unit]`\n", + " that āmodifiesā the state using the given function `f: S => S`\n", + " (i.e., `s => (f(s), ())`). It technically does not need to be given\n", + " in the library, as it can be defined in terms of `doget`, `doput`,\n", + " and `flatMap`.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 5 (4 points)**</span> Implement\n", + "`doreturn[S, A](a: A)` that creates a `DoWith[S, A]` that encapsulates\n", + "the computation `(s: S) => (s, a)` using `doget`, `doput`, `map`, and/or\n", + "`flatMap`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "id": "4a4287fc", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "97598cf8176538e585af2be753ebefc8", + "grade": false, + "grade_id": "doreturn-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mdoreturn\u001b[39m" + ] + }, + "execution_count": 49, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def doreturn[S, A](a: A): DoWith[S, A] = doget[S] flatMap { s => doput(s) map { _ => a } }" + ] + }, + { + "cell_type": "markdown", + "id": "8f8163f1-cf87-4beb-8dbd-324b849e1156", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "id": "a1c918c0", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "be56763277879729950e0129c6ef5703", + "grade": true, + "grade_id": "doreturn-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd50$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mdoreturn\u001b[0m\n", + "\u001b[32m- should Test1\u001b[0m\n", + "\u001b[32m- should Test2\u001b[0m\n", + "\u001b[32m- should Test3\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"doreturn\" should \"Test1\" in { assertResult( (0,1) ) { doreturn(1)(0) }}\n", + " it should \"Test2\" in { assertResult( (2,\"test\") ) { doreturn(\"test\")(2) }}\n", + " it should \"Test3\" in { assertResult( (2,List(1,2,3)) ) { doreturn(List(1,2,3))(2) }}\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "b168529d-126e-4a31-b290-59fc2e2b7a87", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 6 (4 points)**</span> Implement\n", + "`domodify[S](f: S => S)` that creates a `DoWith[S, Unit]` that\n", + "encapsulates the computation `(s: S) => (f(s), ())` using `doget`,\n", + "`doput`, `map`, and/or `flatMap`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "id": "fa1dec1a", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "fe4c1a7e4e4f25883a7446451c07f5b3", + "grade": false, + "grade_id": "domodify-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mdomodify\u001b[39m" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def domodify[S](f: S => S): DoWith[S, Unit] = doget[S] flatMap { s => doput(f(s)) }" + ] + }, + { + "cell_type": "markdown", + "id": "aa1a5947-0c35-44cc-865c-af026c9bc03e", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: To define `doreturn` and `domodify`, it might help first to do\n", + " type-directed programming where you ignore what a `DoWith[S, A]`\n", + " actually is and think of it as `Either[S, A]` or abstractly as\n", + " `M[S, A]` for an unknown type constructor `M`. There only limited\n", + " things you can do by composing `doget`, `doput`, `map`, and\n", + " `flatMap`.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 52, + "id": "93fe1d63", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "0c845d5a21bb4705b132ee18cb9b1d1e", + "grade": true, + "grade_id": "domodify-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n", + "\u001b[32mcmd52$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mdomodify\u001b[0m\n", + "\u001b[32m- should Test1\u001b[0m\n", + "\u001b[32m- should Test2\u001b[0m\n", + "\u001b[32m- should Test3\u001b[0m\n", + "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"domodify\" should \"Test1\" in { assertResult( (6,()) ) { domodify({a:Int => 2*a})(3) }}\n", + " it should \"Test2\" in { assertResult( (\"testtest\",()) ) { domodify({x:String => x+x})(\"test\") }}\n", + " it should \"Test3\" in { assertResult( (List(1,2,3,4),()) ) { domodify({l:List[Int] => l:+4})(List(1,2,3))}}\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "b6bf317b-a3b1-4aa5-8e04-aede510edc39", + "metadata": {}, + "source": [ + "### Renaming Bound Variables\n", + "\n", + "Recall that with static scoping, we see expressions as being equivalent\n", + "up to the renaming of bound variables\n", + "(**?@sec-renaming-bound-variables**). For example, we see the following\n", + "two expressions as being equivalent for the purposes of the language\n", + "implementation:\n", + "\n", + "``` js\n", + "const four = (2 + 2); (four + four)\n", + "```\n", + "\n", + "``` js\n", + "const x = (2 + 2); (x + x)\n", + "```\n", + "\n", + "even though the concrete syntax for the human user is different in their\n", + "choice of variable names.\n", + "\n", + "While being able to choose variable names that shadows another variable\n", + "is important for the human user, we have seen that clashing variable\n", + "names adds complexity to the language implementation. For example,\n", + "mishandling of clashing variable names results in accidental dynamic\n", + "scoping (**?@sec-dynamic-scoping**) and substitution has to account for\n", + "variable shadowing (**?@sec-substitution**).\n", + "\n", + "Observing that renaming bound variables preserves meaning for the\n", + "language implementation, one approach for simplifying the handling of\n", + "variable scope is to implement a *lowering* pass that renames bound\n", + "variables in a consistent manner so that variable names are globally\n", + "unique. For example, we could lower the following expression\n", + "\n", + "``` js\n", + "const a = ((a) => a)(1) + ((a) => a)(2); a\n", + "```\n", + "\n", + "by renaming bound variables to, for example,\n", + "\n", + "``` js\n", + "const a_0 = ((a_1) => a_1)(1) + ((a_2) => a_2)(2); a_0\n", + "```\n", + "\n", + "We will implement the above lowering pass in a few steps.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7 (4 points)**</span> Write a\n", + "function `freshVar(x: String)` that returns a function of type\n", + "`Int => (Int, String)`, which takes a current index-state `i: Int` and\n", + "returns the pair of the next index state `i + 1` and the string `x` with\n", + "the index appended and separated by `\"_\"` (specifically,\n", + "`s\"${x}_${i}\"`):\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 53, + "id": "70c8ba22", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4db7c0a40e8bdb85a7c6c1c88b86f075", + "grade": false, + "grade_id": "freshVar-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfreshVar\u001b[39m" + ] + }, + "execution_count": 53, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def freshVar(x: String): Int => (Int, String) = i => (i + 1, x + \"_\" + i)" + ] + }, + { + "cell_type": "markdown", + "id": "9c9387bd-f827-48f0-96b2-527fd727298a", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "id": "1eec1ec4", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8dbbc418bc069f4bf5cd578668e84d8f", + "grade": true, + "grade_id": "freshVar-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd54$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfreshVar\u001b[0m\n", + "\u001b[32m- should satisfy the property\u001b[0m\n", + "\u001b[36mRun completed in 6 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n", + " \"freshVar\" should \"satisfy the property\" in {\n", + " forAll (\"x\", \"i\") { (x: String, i: Int) =>\n", + " freshVar(x)(i) should be (i + 1, s\"${x}_${i}\")\n", + " }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "3de0aa9c-fd52-4178-8b57-643729b4c1d8", + "metadata": {}, + "source": [ + "Aside: Writing lots of tests is painful. In the above, we use an idea\n", + "called *property-based testing* to make it less painful and more\n", + "effective. A property-based testing library enables specifying a\n", + "property on inputs like in the above for `x: String` and `i: Int`, and\n", + "the library will choose lots of random inputs with which to check the\n", + "property. Importantly, the library also enables the client to specify\n", + "how to generate inputs (e.g., what range, what distribution), though we\n", + "do not do anything special to control the input generation in the above.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (4 points)**</span> Write a\n", + "function `freshVarWith(x: String): DoWith[Int, String]` that behaves\n", + "like `freshVar(x: String): Int => (Int, String)` in\n", + "<a href=\"#exr-freshVar\" class=\"quarto-xref\">ExerciseĀ 7</a>.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "id": "ebced2e2", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "2b383203a1ca61a750129f4e907efaed", + "grade": false, + "grade_id": "freshVarWith-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mfreshVarWith\u001b[39m" + ] + }, + "execution_count": 55, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def freshVarWith(x: String): DoWith[Int, String] =\n", + " doget[Int] flatMap { i => doput(i + 1) map { _ => x + \"_\" + i } }" + ] + }, + { + "cell_type": "markdown", + "id": "75c2997d-0121-449f-a524-ecc078970ad9", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: Remember that `DoWith[Int, String]` encapsulates a function of\n", + " type `Int => (Int, String)`. Use `freshVar` as a guide to creating\n", + " the `DoWith[Int, String]` using `doget`, `doput`, `map`, and/or\n", + " `flatMap`.\n", + "- For accelerated students, you may try to use a `for`-`yield`\n", + " expression to replace your `map` and `flatMap` calls.\n", + "\n", + "A lowering pass is a transformation function from `Expr => Expr`. To\n", + "rename bound variables in a consistent manner, we need an enviroment to\n", + "remember what the name should be for a free variable use in the input\n", + "`Expr`. Thus, we need to define a helper function\n", + "`rename(env: Map[String, String], e: Expr)` that takes as input an\n", + "`env: Map[String, String]` that maps original names to new names for the\n", + "free variable uses in `e`.\n", + "\n", + "We also need a way to choose how to rename bound variables so that they\n", + "are unique. The client of `rename` might want to rename variables\n", + "uniquely in different ways (e.g., using an integer counter, using the\n", + "original name with an integer counter). Thus, we add an additional\n", + "callback parameter\n", + "\n", + "`fresh: String => DoWith[S, String]`\n", + "\n", + "for the client to specify how they want to specify the fresh name given\n", + "the original name where they can choose a state type `S` to use through\n", + "renaming.\n", + "\n", + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "id": "59e121cb", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "95401071328374fd7d0acba7c0cc8be9", + "grade": true, + "grade_id": "freshVarWith-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd56$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mfreshVarWith\u001b[0m\n", + "\u001b[32m- should satisfy the property\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n", + " \"freshVarWith\" should \"satisfy the property\" in {\n", + " forAll (\"x\", \"i\") { (x: String, i: Int) =>\n", + " freshVarWith(x)(i) should be (i + 1, s\"${x}_${i}\")\n", + " }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "f3bfb9f2-fe61-41cf-9e92-5f128b5b2e74", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 9 (24 points)**</span> Implement\n", + "a function `rename` that renames variable names in `e` consistently\n", + "using the given callback to `fresh` to generate fresh names for bound\n", + "variables and `env` to rename free variable uses.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "id": "3ff17100", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "ece6ee45347070a85242d7d9307fd598", + "grade": false, + "grade_id": "rename-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mrename\u001b[39m" + ] + }, + "execution_count": 57, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def rename[S](env: Map[String, String], e: Expr)(fresh: String => DoWith[S, String]): DoWith[S, Expr] = {\n", + " def rename(env: Map[String, String], e: Expr): DoWith[S, Expr] = {\n", + " def r(e: Expr) = rename(env, e)\n", + " e match {\n", + " case N(_) => doreturn(e)\n", + " case B(_) => doreturn(e)\n", + "\n", + " case Var(x) =>\n", + " env.get(x) match {\n", + " case Some(newName) => doreturn(Var(newName))\n", + " case None => doreturn(e)\n", + " }\n", + "\n", + " case ConstDecl(x, e1, e2) =>\n", + " fresh(x) flatMap { x_ =>\n", + " r(e1) flatMap { e1Renamed =>\n", + " rename(env + (x -> x_), e2) map { e2Renamed =>\n", + " ConstDecl(x_, e1Renamed, e2Renamed)\n", + " }\n", + " }\n", + " }\n", + "\n", + " case Unary(uop, e1) => r(e1) map { e1Renamed => Unary(uop, e1Renamed) }\n", + "\n", + " case Binary(bop, e1, e2) =>\n", + " r(e1) flatMap { e1Renamed =>\n", + " r(e2) map { e2Renamed => Binary(bop, e1Renamed, e2Renamed) }\n", + " }\n", + "\n", + " case If(e1, e2, e3) =>\n", + " r(e1) flatMap { e1Renamed =>\n", + " r(e2) flatMap { e2Renamed =>\n", + " r(e3) map { e3Renamed => If(e1Renamed, e2Renamed, e3Renamed) }\n", + " }\n", + " }\n", + "\n", + " case Fun(x, (y, t), tret, e1) =>\n", + " fresh(x) flatMap { x_ =>\n", + " fresh(y) flatMap { y_ =>\n", + " rename(env ++ Seq(x -> x_, y -> y_), e1) map { e1Renamed =>\n", + " Fun(x_, (y_, t), tret, e1Renamed)\n", + " }\n", + " }\n", + " }\n", + "\n", + " case Call(e1, e2) =>\n", + " r(e1) flatMap { e1 =>\n", + " r(e2) map { e2 => Call(e1, e2) }\n", + " }\n", + " }\n", + " }\n", + " rename(env, e)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "e1785b12-6117-46a6-b5c1-8d084599d74d", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: Use the given cases for `N` and `Call` as models. The only\n", + " methods for manipulating `DoWith` objects needed in this exercise\n", + " are `doreturn`, `map`, and `flatMap`.\n", + "- **Accelerated**: You may try to use `for`-`yield` expressions to\n", + " replace your `map` and `flatMap` calls.\n", + "\n", + "### Test" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "id": "008eecc0", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "9efbe8c21276cc5893170648e4fe920f", + "grade": true, + "grade_id": "rename-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: 1\u001b[0m\n", + "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename\u001b[0m\n", + "\u001b[32m- should rename in a DoWith\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " \"rename\" should \"rename in a DoWith\" in {\n", + " val e1 = ConstDecl(\"a\", N(1), Var(\"a\"))\n", + " val e1p = ConstDecl(\"aa\", N(1), Var(\"aa\"))\n", + "\n", + " assertResult( (1, e1p) ) {\n", + " rename(Map.empty, e1){ x => domodify[Int](n => n + 1) map { _ => x + x } }(0)\n", + " }\n", + " }\n", + " }, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "id": "eb86e401", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "9f99fea0bf530561a08a1ac395976f96", + "grade": true, + "grade_id": "rename-b-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd59$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename/B\u001b[0m\n", + "\u001b[32m- should RenameB\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n", + " def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n", + " def r(e: Expr) = renv(Map.empty, e)\n", + "\n", + " \"rename/B\" should \"RenameB\" in {\n", + " assertResult( (0, B(true)) ) { r(B(true)) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 60, + "id": "fb51b0f2", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "a858edae6e7b668554c2450a11eb0c8e", + "grade": true, + "grade_id": "rename-var-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd60$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename/Var\u001b[0m\n", + "\u001b[32m- should RenameVar\u001b[0m\n", + "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n", + " def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n", + " def r(e: Expr) = renv(Map.empty, e)\n", + "\n", + " \"rename/Var\" should \"RenameVar\" in {\n", + " assertResult( (0, Var(\"y\")) ) { renv(Map(\"x\" -> \"y\"), Var(\"x\")) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "id": "0f91cc33", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4ee6c2e809e0b3da63081628038a320e", + "grade": true, + "grade_id": "rename-constdecl-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd61$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename/ConstDecl\u001b[0m\n", + "\u001b[32m- should RenameConstDecl\u001b[0m\n", + "\u001b[36mRun completed in 3 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n", + " def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n", + " def r(e: Expr) = renv(Map.empty, e)\n", + "\n", + " def e(x: String) = ConstDecl(x, N(1), Var(x))\n", + " \"rename/ConstDecl\" should \"RenameConstDecl\" in {\n", + " assertResult( (1, e(\"x0\")) ) { r(e(\"foo\")) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 62, + "id": "3043ad33", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8bf04f09f2e6ad7c3cf1b95420f2e42e", + "grade": true, + "grade_id": "rename-fun-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n", + "\u001b[32mcmd62$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename/Fun\u001b[0m\n", + "\u001b[32m- should RenameFun\u001b[0m\n", + "\u001b[36mRun completed in 4 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 1\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n", + " def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n", + " def r(e: Expr) = renv(Map.empty, e)\n", + "\n", + " def e(f: String, y: String) = Fun(f, (y, TNumber), TNumber, Call(Var(\"f\"), Var(\"y\")))\n", + " \"rename/Fun\" should \"RenameFun\" in {\n", + " assertResult( (2, e(\"x0\", \"x1\")) ) { r(e(\"foo\", \"bar\")) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "id": "13177ece", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "4e45cf96c86a87a489df4d6a67af2121", + "grade": true, + "grade_id": "rename-factorial-tester", + "locked": true, + "points": 4, + "schema_version": 3, + "solution": false, + "task": false + } + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n", + "\u001b[32mcmd63$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mrename\u001b[0m\n", + "\u001b[32m- should rename bound variables consistently for factorial\u001b[0m\n", + "\u001b[32m- should rename with a different fresh\u001b[0m\n", + "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 2\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " def fresh(s: String): DoWith[Int,String] = doget flatMap { i => doput(i + 1) map { _ => s\"x${i}\" } }\n", + " def renv(env: Map[String, String], e: Expr): (Int, Expr) = rename(env, e)(fresh)(0)\n", + " def r(e: Expr) = renv(Map.empty, e)\n", + "\n", + " def factorial(fact: String, n: String) = Fun(fact, (n, TNumber), TNumber,\n", + " If(Binary(Eq, Var(n), N(1)),\n", + " N(1),\n", + " Binary(Times, Var(n), Call(Var(fact), Binary(Plus, Var(n), N(-1)))))\n", + " )\n", + "\n", + " \"rename\" should \"rename bound variables consistently for factorial\" in {\n", + " assertResult( (2, factorial(\"x0\", \"x1\")) ) { r(factorial(\"fact\", \"n\")) }\n", + " }\n", + "\n", + " it should \"rename with a different fresh\" in {\n", + " assertResult( (4, factorial(\"fact0\", \"n2\")) ) {\n", + " val e = factorial(\"fact\", \"n\")\n", + " rename[Int](Map.empty, e)(x => doget flatMap { i => doput(i + 2) map { _ => s\"${x}${i}\" } })(0)\n", + " }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "88bdb153-d9bc-4772-86f5-aebe0a8b8429", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 10 (4 points)**</span> Finally,\n", + "implement the lowering-transformation function `uniquify: Expr => Expr`\n", + "on closed expressions using a call to `rename` to rename bound variables\n", + "consistently with the `freshVarWith: String => DoWith[Int, String]`\n", + "function defined above. Start the `Int` counter-state at `0`.\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "id": "24fa60ef", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "bb21762ce36cdb75c3b26c78ef37cb84", + "grade": false, + "grade_id": "uniquify-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36muniquify\u001b[39m" + ] + }, + "execution_count": 64, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def uniquify(e: Expr): Expr = {\n", + " require(isClosed(e), s\"$e should be closed\")\n", + " val counterState = 0\n", + " val freshVar: String => DoWith[Int, String] = freshVarWith\n", + " var renamedExpr: DoWith[Int, Expr] = rename(Map(), e)(freshVar)\n", + " renamedExpr(counterState)._2\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "04c11eb3-5299-4a78-a73a-cfb1690928ef", + "metadata": {}, + "source": [ + "#### Notes\n", + "\n", + "- Hint: The `rename` and `freshVarWith` functions constructs `DoWith`\n", + " objects. The `uniquify` finally uses a `DoWith[Int, String]` object.\n", + " How? By calling it with the initial state `0`.\n", + "\n", + "#### Test" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "id": "7dc1f2d2", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "338a55434d352c17fe37abfc4b18efaf", + "grade": true, + "grade_id": "uniquify-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: 2\u001b[0m\n", + "\u001b[32mcmd65$Helper$$anon$1:\u001b[0m\n", + "\u001b[32muniquify\u001b[0m\n", + "\u001b[32m- should work on the example\u001b[0m\n", + "\u001b[32m- should work another example\u001b[0m\n", + "\u001b[36mRun completed in 7 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 2\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec with Matchers with ScalaCheckPropertyChecks {\n", + " def idfun(f: String, y: String) =\n", + " Fun(f, (y, TNumber), TNumber, Var(y))\n", + " def aconst(x1: String, x2: String, x3: String, x4: String, x5: String) =\n", + " ConstDecl(x1, Binary(Plus, Call(idfun(x2, x3), N(1)), Call(idfun(x4, x5), N(2))), Var(x1))\n", + " def nm(x: String, i: Int) = s\"${x}_${i}\"\n", + "\n", + " \"uniquify\" should \"work on the example\" in {\n", + " forAll { (x1: String, x2: String, x3: String, x4: String, x5: String) =>\n", + " uniquify(aconst(x1, x2, x3, x4, x5)) should be {\n", + " aconst(nm(x1, 0), nm(x2, 1), nm(x3, 2), nm(x4, 3), nm(x5, 4))\n", + " }\n", + " }\n", + " }\n", + "\n", + " val e = ConstDecl(\"a\", ConstDecl(\"a\", N(1), Var(\"a\")), ConstDecl(\"b\",N(2), Var(\"b\")))\n", + " val exp = ConstDecl(\"a_0\", ConstDecl(\"a_1\", N(1), Var(\"a_1\")), ConstDecl(\"b_2\", N(2), Var(\"b_2\")))\n", + " it should \"work another example\" in {\n", + " assertResult(exp) { uniquify(e) }\n", + " }\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "fbd68990-6a54-4b7a-a803-41e9c2c76028", + "metadata": {}, + "source": [ + "### `DoWith` with Collections\n", + "\n", + "Recall the higher-order function `map` we considered previously for\n", + "`List`s." + ] + }, + { + "cell_type": "code", + "execution_count": 66, + "id": "9065e962", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmap\u001b[39m" + ] + }, + "execution_count": 66, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def map[A, B](l: List[A])(f: A => B): List[B] =\n", + " l.foldRight[List[B]](\n", + " Nil\n", + " ) { (h, acc) =>\n", + " f(h) :: acc\n", + " }" + ] + }, + { + "cell_type": "markdown", + "id": "a412e371-e057-4b12-bd63-eb2104c075c6", + "metadata": {}, + "source": [ + "We may want to use `DoWith` to encapsulate some stateful computation\n", + "with other data structures, like `List`s. For example, we want a version\n", + "of `map` that can take a stateful callback:\n", + "\n", + "<span class=\"theorem-title\">**Exercise 11 (4 points)**</span> Implement\n", + "a function `mapWith` for `List` that takes a stateful callback function\n", + "`f: A => DoWith[S, B]`:\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 67, + "id": "1bb63578", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "47940fa52b9ac6f17bc42ab1aabc5314", + "grade": false, + "grade_id": "mapWith-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapWith\u001b[39m" + ] + }, + "execution_count": 67, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapWith[S, A, B](l: List[A])(f: A => DoWith[S, B]): DoWith[S, List[B]] =\n", + " l.foldRight[DoWith[S, List[B]]](\n", + " doreturn(Nil)\n", + " ) { (h, acc) =>\n", + " f(h) flatMap { b =>\n", + " acc map { bs =>\n", + " b ::bs\n", + " }\n", + " }\n", + " }" + ] + }, + { + "cell_type": "markdown", + "id": "369fa030-18bb-44b1-9ac5-aed93363af2e", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 68, + "id": "2cc00334", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "8153b1fdc48b0960100f83d828aa0e35", + "grade": true, + "grade_id": "mapWith-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: 3\u001b[0m\n", + "\u001b[32mcmd68$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mmapWith\u001b[0m\n", + "\u001b[32m- should Test1\u001b[0m\n", + "\u001b[32m- should Test2\u001b[0m\n", + "\u001b[32m- should Test3\u001b[0m\n", + "\u001b[36mRun completed in 5 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 3\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l = List(1, 2, 3, 4, 5)\n", + " val r1 = l.map { i => i + 1 }\n", + "\n", + " def dowith1[W]: DoWith[W,List[Int]] = mapWith(l) { i: Int => doreturn(i + 1) }\n", + " \n", + " \"mapWith\" should \"Test1\" in { assertResult((true,r1)) { dowith1(true) } }\n", + " it should \"Test2\" in {assertResult((42,r1)) { dowith1(42) }}\n", + " it should \"Test3\" in {assertResult((2 * l.length + 1, r1)) {\n", + " val dw: DoWith[Int,List[Int]] = mapWith(l) { i: Int =>\n", + " domodify[Int](s => s + 2) map { _ => i + 1 }\n", + " }\n", + " dw(1)\n", + " }}\n", + "}, 4)" + ] + }, + { + "cell_type": "markdown", + "id": "2061336b-912b-4be5-82b7-bb4894c11ce5", + "metadata": {}, + "source": [ + "Also recall the `mapFirst` function we defined previously that replaces\n", + "the first element in `l` where `f` returns `Some(a)` with `a`:" + ] + }, + { + "cell_type": "code", + "execution_count": 69, + "id": "a523fa60", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirst\u001b[39m" + ] + }, + "execution_count": 69, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapFirst[A](l: List[A])(f: A => Option[A]): List[A] = l match {\n", + " case Nil => Nil\n", + " case h :: t =>\n", + " f(h) match {\n", + " case None => h :: mapFirst(t)(f)\n", + " case Some(h) => h :: t\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "b88d3328-5bf0-4ba9-84bd-8fb37b46b1d6", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 12 (4 points)**</span> Implement\n", + "a function `mapFirstWith` for `List` that instead takes a stateful\n", + "callback function `f: A => Option[DoWith[S, B]]`:\n", + "\n", + "**Edit this cell:**" + ] + }, + { + "cell_type": "code", + "execution_count": 70, + "id": "f22eb076", + "metadata": { + "deletable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "59cf107ce7934c9aa80564c7169349b0", + "grade": false, + "grade_id": "mapFirstWith-answer", + "locked": false, + "schema_version": 3, + "solution": true, + "task": false + } + }, + "outputs": [ + { + "data": { + "text/plain": [ + "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirstWith\u001b[39m" + ] + }, + "execution_count": 70, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "def mapFirstWith[S, A](l: List[A])(f: A => Option[DoWith[S, A]]): DoWith[S, List[A]] = l match {\n", + " case Nil => doreturn(Nil)\n", + " case h :: t =>\n", + " f(h) match {\n", + " case Some(doer) => doer map { newHead => newHead :: t }\n", + " case None => mapFirstWith(t)(f) map { tail => h :: tail }\n", + " }\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "424f6d6a-6f9c-47bc-ae6f-4a31259b985c", + "metadata": {}, + "source": [ + "#### Tests" + ] + }, + { + "cell_type": "code", + "execution_count": 71, + "id": "626bee45", + "metadata": { + "deletable": false, + "editable": false, + "nbgrader": { + "cell_type": "code", + "checksum": "9f8622d87ad3a7b701904166a0514993", + "grade": true, + "grade_id": "mapFirstWith-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: 4\u001b[0m\n", + "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n", + "\u001b[32mmapFirstWith\u001b[0m\n", + "\u001b[32m- should Test1\u001b[0m\n", + "\u001b[32m- should Test2\u001b[0m\n", + "\u001b[32m- should Test3\u001b[0m\n", + "\u001b[32m- should Test4\u001b[0m\n", + "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n", + "\u001b[36mTotal number of tests run: 4\u001b[0m\n", + "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n", + "\u001b[36mTests: succeeded 4, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n", + "\u001b[32mAll tests passed.\u001b[0m\n", + "*** š Tests Passed (4 points) ***\n" + ] + } + ], + "source": [ + "test(new AnyFlatSpec {\n", + " val l = List(1, 2, -3, 4, -5)\n", + " val r = List(1, 2, 3, 4, -5)\n", + " def dowith[W]: DoWith[W,List[Int]] = mapFirstWith(l) { (i: Int) => if (i < 0) Some(doreturn(-i)) else None }\n", + " \n", + " val w1 = true\n", + " val w2 = 10\n", + " val w3 = \"test_str\"\n", + " val w4 = List\n", + " \n", + " \"mapFirstWith\" should \"Test1\" in { assertResult((w1,r)){ dowith(w1) } }\n", + " it should \"Test2\" in {assertResult((w2,r)) { dowith(w2) }}\n", + " it should \"Test3\" in {assertResult((w3,r)) { dowith(w3) }}\n", + " it should \"Test4\" in {assertResult((w4,r)) { dowith(w4) }}\n", + "}, 4)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala" + }, + "language_info": { + "codemirror_mode": "text/x-scala", + "file_extension": ".sc", + "mimetype": "text/x-scala", + "name": "scala", + "nbconvert_exporter": "script", + "version": "2.13.14" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} diff --git a/lab5/build.sbt b/lab5/build.sbt new file mode 100644 index 0000000..c1f60ca --- /dev/null +++ b/lab5/build.sbt @@ -0,0 +1,48 @@ +lazy val commonSettings = Seq( + organization := "edu.colorado.cs", + version := "4.0.0", + + scalaVersion := "2.13.14", + scalacOptions ++= Seq( + "-unchecked", // Enable additional warnings where generated code depends on assumptions. + "-feature", // Emit warning for features that should be imported explicitly + "-Xcheckinit", // Wrap field accessors to throw an exception on uninitialized access + "-deprecation", // Emit warning and location for usages of deprecated APIs. + "-explaintypes", // Explain type errors in more detail. + "-Ywarn-extra-implicit", // more than one implicit parameter section is defined + "-Xlint:nullary-unit", // nullary methods return Unit + "-Xlint:inaccessible", // inaccessible types in method signatures + "-Xlint:infer-any", // a type argument is inferred to be Any + "-Xlint:missing-interpolator", // literal appears to be missing an interpolator id + "-Xlint:option-implicit", // apply used implicit view + "-Xlint:package-object-classes", // object defined in package object + "-Xlint:stars-align", // wildcard must align with sequence component + "-Xlint:constant", // a constant arithmetic expression results in an error + //"-Xfatal-warnings", // turn warnings into errors + ), + libraryDependencies ++= Seq( + "org.scala-lang.modules" %% "scala-parser-combinators" % "2.1.1", + "org.scalacheck" %% "scalacheck" % "1.16.0" % "test", + "org.scalactic" %% "scalactic" % "3.2.13", + "org.scalatest" %% "scalatest" % "3.2.13" % "test", + "org.scalatestplus" %% "scalacheck-1-16" % "3.2.13.0" % "test" + ), + + // set logging to show only errors during runs + run / logLevel := Level.Error, + runMain / logLevel := Level.Error, + Global / excludeLintKeys += logLevel, + + // JVM arguments: 8G heap size, 2M stack size + //Test / javaOptions += "-Xmx8G -Xss2M", + + // scoverage options: always build with coverage + //coverageEnabled := true, + + // scalatest options: -o standard output, D durations + // -e stderr + Test / testOptions += Tests.Argument("-e") +) + +lazy val lab5 = (project in file(".")). + settings(commonSettings: _*) diff --git a/lab5/imperative-computation-lab.ipynb b/lab5/imperative-computation-lab.ipynb new file mode 100644 index 0000000..b26fe3b --- /dev/null +++ b/lab5/imperative-computation-lab.ipynb @@ -0,0 +1,1522 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "8e3502cc", + "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": "a71e0446", + "metadata": {}, + "outputs": [], + "source": [ + "val NAME = \"\"\n", + "val COLLABORATORS = \"\"" + ] + }, + { + "cell_type": "markdown", + "id": "ac39c01f", + "metadata": {}, + "source": [ + "---" + ] + }, + { + "cell_type": "markdown", + "id": "d2d5fb3c-8d64-445f-9f8c-52390c9ce652", + "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: Imperative Computation\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", + "<!-- 26 Static Type Checking -->\n", + "\n", + "<!-- 27 Lazy Evaluation -->\n", + "\n", + "<!-- 28 Objects -->\n", + "\n", + "<!-- 28 Static Type Checking Lab -->\n", + "\n", + "<!-- 30 Mutable State -->\n", + "\n", + "<!-- Encapsulating Effects Exercise -->\n", + "\n", + "<!-- Imperative Lab -->\n", + "\n", + "### Learning Goals\n", + "\n", + "The primary goals of this lab are to understand the following:\n", + "\n", + "- imperative computation;\n", + "- mutation and aliasing;\n", + "- programming with encapsulated effects.\n", + "\n", + "Functional Programming Skills \n", + "Encapsulating computation in a data structure library.\n", + "\n", + "Programming Language Ideas \n", + "Imperative computation (e.g., memory, addresses, aliasing).\n", + "\n", + "### Instructions\n", + "\n", + "A version of project files for this lab resides in the public\n", + "[pppl-lab5](https://github.com/csci3155/pppl-lab5) 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 `Lab5.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 `Lab5Spec.scala` file. In the\n", + "`Lab5Spec.scala`, there is empty test class `Lab5StudentSpec` that you\n", + "can use to separate your tests from the given tests in the `Lab5Spec`\n", + "class. You are also likely to edit `Lab5.worksheet.sc` for any scratch\n", + "work. You can also use `Lab5.worksheet.ts` to write and experiment in a\n", + "JavaScript file that you can then parse into a TypeScripty AST (see\n", + "`Lab5.worksheet.sc`).\n", + "\n", + "If you like, you may use this notebook for experimentation. However,\n", + "**please make sure your code is in `Lab5.scala`; code in this notebook\n", + "will not graded.**\n", + "\n", + "## TypeScripty: Mutable Variables and Objects\n", + "\n", + "#### Imperative Computation\n", + "\n", + "In this lab, we build on all of the techniques throughout the course to\n", + "explore imperative computation. We consider the imperative core of\n", + "JavaScript that has mutable variables and dynamically-allocated mutable\n", + "objects.\n", + "\n", + "Concretely, we will see that supporting imperative programming language\n", + "features forces a global refactoring of our interpreter. To minimize the\n", + "impact of this refactoring, we will be use the functional programming\n", + "idea of encapsulating effects in a data type (known as a monad).\n", + "\n", + "Additionally, we consider parameter passing modes to illustrate\n", + "different possible language design decisions and how design decisions\n", + "manifest in the operational semantics. Call-by-value with pointer values\n", + "and call-by-reference are often confused, but with the operational\n", + "semantics, we can see clearly the distinction. JavaScript, like most\n", + "languages, fixes one parameter passing modeāall parameters are allocated\n", + "as mutable variables and arguments are passed by value. Other parameter\n", + "passing modes can be reasonably simulated with other language features,\n", + "so having different parameter passing modes can be seen as somewhat\n", + "exotic.\n", + "\n", + "#### Assignment\n", + "\n", + "We introduce an assignment expression\n", + "\n", + "$$\n", + "e_1 \\mathrel{\\texttt{=}}e_2\n", + "$$\n", + "\n", + "that writes the value of $e_2$ to a memory location named by expression\n", + "$e_1$. Note that we use the C and JavaScript-style assignment operator\n", + "$\\texttt{=}$, which unfortunately looks like mathematical equality but\n", + "is very different.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& e_1 \\mathrel{\\texttt{=}}e_2\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 1: Abstract syntax of JavaScripty with assignment." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f42708b7", + "metadata": {}, + "outputs": [], + "source": [ + "trait Expr // e\n", + "case class Assign(e1: Expr, e2: Expr) extends Expr // e ::= e1 = e2" + ] + }, + { + "cell_type": "markdown", + "id": "069961b2-918c-4338-9aa3-801953140900", + "metadata": {}, + "source": [ + "For the dynamic semantics, we define an auxiliary judgment form\n", + "$e\\;\\mathsf{location}$ to specify expression forms that specify memory\n", + "locations (i.e., *locations* or *l-values*)." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "18302934", + "metadata": {}, + "outputs": [], + "source": [ + "def isLValue(e: Expr): Boolean = ???" + ] + }, + { + "cell_type": "markdown", + "id": "75b1e7b2-21c7-4ebe-86ed-67a97f26c488", + "metadata": {}, + "source": [ + "#### Mutable Variable Allocation\n", + "\n", + "We introduce *mutable variables* declared as follows:\n", + "\n", + "$$\n", + "\\mathbf{var}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + "$$\n", + "\n", + "A $\\mathbf{var}$ declaration allocates a new mutable variable $x$,\n", + "assigns it an initial value from evaluating $e_1$, and whose scope is\n", + "$e_2$.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + "d\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + "\\mid x\n", + "\\\\\n", + "\\text{parameter modes} & d& \\mathrel{::=}& \\mathbf{const}\\mid\\mathbf{var}\n", + "\\\\\n", + "\\text{variables} & x\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 2: Abstract syntax of JavaScripty with $\\mathbf{const}$- and\n", + "$\\mathbf{var}$-variable declarations.\n", + "\n", + "Note that the concrete syntax of JavaScript has two mutable variable\n", + "declaration forms with `var` and `let` that differ in the scope of the\n", + "declared variable.\n", + "\n", + "For simplicity and uniformity, we consider a single abstract syntax form\n", + "for variable declarations $d\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2$ whose\n", + "scope is given as $e_2$. The $d$ may be $\\mathbf{const}$-mode that binds\n", + "the value of $e_1$ to variable $x$ for use in $e_2$ as before or now may\n", + "be $\\mathbf{var}$-mode that allocates a new mutable variable initialized\n", + "to the value of $e_1$ for use in $e_2$." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "73823007", + "metadata": {}, + "outputs": [], + "source": [ + "case class Decl(d: Mode, x: String, e1: Expr, e2: Expr) extends Expr // e ::= d x = e1; e2\n", + "case class Var(x: String) extends Expr // e ::= x\n", + "\n", + "trait Mode // d\n", + "case object MConst extends Mode // d ::= const\n", + "case object MVar extends Mode // d ::= var" + ] + }, + { + "cell_type": "markdown", + "id": "731e2bbc-c582-4d97-b581-0479ee0ac4c7", + "metadata": {}, + "source": [ + "We can think of a mutable variable as a box that can be filled with a\n", + "value, and then the value can be updated by filling the box with a new\n", + "value. A memory cell $[a \\mapsto v]$ is such a box that has an address\n", + "$a$ to reference that box. A memory $m$ is then a finite set of such\n", + "memory cells:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{memories} & m& \\mathrel{::=}& \\cdot\\mid m[a \\mapsto v]\n", + "\\\\\n", + "\\text{addresses} & a\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 3: Memories for JavaScripty with mutable variables.\n", + "\n", + "We add addresses $a$, as well as an address dereference operator\n", + "$\\mathord{\\texttt{*}}e_1$, to the expression language to use as\n", + "intermediate expressions during reduction:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + "a\n", + "\\mid\\mathop{\\mathit{uop}} e_1\n", + "\\\\\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{*}\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 4: Abstract syntax of JavaScripty with addresses and an address\n", + "dereference operator." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7350e1c0", + "metadata": {}, + "outputs": [], + "source": [ + "case class A(a: Int) extends Expr // e ::= a\n", + "case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1\n", + "\n", + "trait Uop // uop\n", + "case object Deref extends Uop // uop ::= *" + ] + }, + { + "cell_type": "markdown", + "id": "19ba9db1-c21e-47f9-abcb-3cef3957c7d9", + "metadata": {}, + "source": [ + "To formalize mutable variables in JavaScript, the address dereference\n", + "expression $\\mathord{\\texttt{*}}e_1$ is not strictly necessary, but it\n", + "helps us conceptually distinguish between the address $a$ from its use\n", + "in naming the memory cell $[a \\mapsto v]$. The $\\mathord{\\texttt{*}}e_1$\n", + "expression corresponds to the pointer-dereference expression in the C\n", + "and C++ languages.\n", + "\n", + "We state the $\\mathord{\\texttt{*}}a$ names a memory location for a\n", + "mutable variable (i.e., is an l-value):\n", + "\n", + "$\\fbox{$e\\;\\mathsf{location}$}$\n", + "\n", + "$\\inferrule[VarLocation]{\n", + "}{\n", + " \\mathord{\\texttt{*}}a \\;\\mathsf{location}\n", + "}$\n", + "\n", + "FigureĀ 5: Location values for JavaScripty with mutable variables." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c548d3bc", + "metadata": {}, + "outputs": [], + "source": [ + "def isLValue(e: Expr): Boolean = e match {\n", + " case Unary(Deref, A(_)) => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "04ed0f94-c328-4d37-8f08-13fc46c80227", + "metadata": {}, + "source": [ + "#### Dynamically-Allocated Mutable Objects\n", + "\n", + "We consider the expression syntax of objects but now implement them as\n", + "dynamically-allocated mutable objects as in JavaScript:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + " \\text{types} & \\tau& \\mathrel{::=}&\n", + " \\texttt{\\{} \\overline{ f\\texttt{:}\\,\\tau } \\texttt{\\}} \n", + " \\\\\n", + " \\text{values} & v& \\mathrel{::=}& a\n", + " \\\\[1ex]\n", + " \\text{expressions} & e& \\mathrel{::=}& \n", + " \\texttt{\\{} \\overline{ f\\texttt{:}\\,e } \\texttt{\\}} \n", + " \\mid e_1\\texttt{.}f\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 6: Abstract syntax of JavaScripty with pointers and objects." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "81a59003", + "metadata": {}, + "outputs": [], + "source": [ + "trait Typ\n", + "case class TObj(fts: Map[String, Typ]) extends Typ // t ::= { fts }\n", + "\n", + "case class Obj(fes: Map[String,Expr]) extends Expr // e ::= { fes }\n", + "case class GetField(e1: Expr, f: String) extends Expr // e ::= e1.f" + ] + }, + { + "cell_type": "markdown", + "id": "a571e116-507e-4a4a-9e20-d60b3c857fae", + "metadata": {}, + "source": [ + "The value of an object expression\n", + "$\\texttt{\\{} \\overline{ f\\texttt{:}\\,e } \\texttt{\\}}$ is address $a$ at\n", + "which the object is stored in memory (i.e., a *pointer* to the object is\n", + "its value).\n", + "\n", + "Memories for dynamically-allocated mutable objects store objects at\n", + "addresses:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{memories} & m& \\mathrel{::=}& \\cdot \\mid m[a \\mapsto \\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}} ]\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 7: Memories for JavaScripty with dynamically-allocated mutable\n", + "objects.\n", + "\n", + "A field of an object is an assignable memory location:\n", + "\n", + "$\\fbox{$e\\;\\mathsf{location}$}$\n", + "\n", + "$\\inferrule[FieldLocation]{\n", + "}{\n", + " a\\texttt{.}f \\;\\mathsf{location}\n", + "}$\n", + "\n", + "FigureĀ 8: Location values for JavaScripty with dynamically-allocated\n", + "mutable objects." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7e650a31", + "metadata": {}, + "outputs": [], + "source": [ + "def isLValue(e: Expr): Boolean = e match {\n", + " case Unary(Deref, A(_)) | GetField(A(_), _) => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "51d3ccbf-96c6-430e-8196-374cf7b88bb3", + "metadata": {}, + "source": [ + "With both mutable variables and mutable objects, we have two kinds of\n", + "memory cells and two forms of l-values.\n", + "\n", + "#### Location References\n", + "\n", + "Call-by-value with pointer values and call-by-reference are often\n", + "confused, so we formalize the notion of location *references*, that is,\n", + "sharing a memory location with a variable alias. *Aliasing* refers to\n", + "the concept that the same memory location may be referenced using two\n", + "different program expressions.\n", + "\n", + "In particular, on a procedure call, we may want a parameter of the\n", + "callee to alias a previously allocated memory location (i.e., a\n", + "call-by-reference parameter).\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{parameter modes} & d& \\mathrel{::=}& \\mathbf{ref}\n", + "\\\\[1ex]\n", + " \\text{types} & \\tau& \\mathrel{::=}& \\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau'\n", + " \\\\\n", + " \\text{values} & v& \\mathrel{::=}& x^{?}\\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\\\\n", + " \\text{expressions} & e& \\mathrel{::=}& \n", + " d\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + " \\mid x\n", + " \\mid x^{?}\\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n", + " \\mid e_0\\texttt{(} \\overline{e} \\texttt{)}\n", + "\\\\\n", + "\\text{variables} & x\n", + "\\\\\n", + "\\text{optional variables} & x^{?}& \\mathrel{::=}& x\\mid\\varepsilon\n", + "\\\\\n", + "\\text{optional type annotations} & \\tau^{?}& \\mathrel{::=}& \\texttt{:}\\,\\tau \\mid\\varepsilon\n", + "\\end{array}\n", + "$$\n", + "\n", + "FigureĀ 9: Abstract syntax of JavaScripty with $\\mathbf{ref}$-parameters." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "30c21c0c", + "metadata": {}, + "outputs": [], + "source": [ + "case object MRef extends Mode // mode ::= ref" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "852f5962", + "metadata": {}, + "outputs": [], + "source": [ + "case class MTyp(d: Mode, t: Typ) // d t\n", + "case class TFun(ydts: List[(String,MTyp)], tret: Typ) extends Typ // t ::= (ydts) => tret\n", + "\n", + "trait Expr // e\n", + "case class Fun(xopt: Option[String], ydts: List[(String,MTyp)], tretopt: Option[Typ], e1: Expr) extends Expr // e ::= xopt(ydts)tretopt => e1\n", + "case class Call(e0: Expr, es: List[Expr]) extends Expr // e ::= e0(es)" + ] + }, + { + "cell_type": "markdown", + "id": "016279fe-8a81-414c-9cb4-9cebe054a79a", + "metadata": {}, + "source": [ + "We extend parameter modes $d$ with $\\mathbf{ref}$ parameters. Note that\n", + "procedure parameters now have a mode annotation in the abstract syntax.\n", + "\n", + "We do not introduce first-class references (i.e., we do not have\n", + "reference values or reference types as in C++ or Rust).\n", + "\n", + "Note that in low-level languages, pointers and references both\n", + "correspond to memory addresses in implementation, so one source of\n", + "confusion may be that pointers are sometimes called references.\n", + "\n", + "## Interpreter Implementation\n", + "\n", + "We break our interpreter implementation into evaluation and type\n", + "checking.\n", + "\n", + "#### Small-Step Reduction\n", + "\n", + "For evaluation, we continue with implementing a small-step operational\n", + "semantics with a `step` that implements a single reduction step\n", + "\n", + "$$\n", + " \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle \n", + "$$\n", + "\n", + "on closed expressions that says informally, āExpression $e$ with memory\n", + "$m$ steps to a new configuration with expression $e'$ and memory $m'$.ā\n", + "The memory $m$ is a map from addresses $a$ to contents, which can be\n", + "values $v$ or objects $\\texttt{\\{}\\overline{f\\texttt{:}\\,v}\\texttt{\\}}$.\n", + "The presence of a memory $m$ that gets updated during evaluation is the\n", + "hallmark of *imperative computation*.\n", + "\n", + "To simplify the implementation (and minimize bugs), we implement `step`\n", + "using the following type signature:\n", + "\n", + "``` scala\n", + "def step(e: Expr): DoWith[Mem, Expr] = ???\n", + "```\n", + "\n", + "where `DoWith[Mem, Expr]` is a data type that encapsulates a function of\n", + "type `Mem => (Mem, Expr)`, which we can see corresponds to $m$, $m'$,\n", + "and $e'$, respectively, in the judgment form\n", + "$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $. The\n", + "main advantage of using the encapsulated computation type\n", + "`DoWith[Mem,Expr]` is that we can put this common-case threading into\n", + "the `DoWith` library.\n", + "\n", + "##### Memory\n", + "\n", + "We define `Mem` as an abstract data type to represent memories $m$ as a\n", + "wrapper around a Scala `Map[A, Expr]` (cf.Ā the Mutable State chapter\n", + "(**?@sec-implementation-memories**)).\n", + "\n", + "Some rules require allocating fresh addresses. In the implementation,\n", + "call `memalloc(k)` to get a fresh address with the memory cell\n", + "initialized to contents `k`:\n", + "\n", + "``` scala\n", + "def memalloc(k: Expr): DoWith[Mem, A]\n", + "```\n", + "\n", + "#### Static Type Checking\n", + "\n", + "As before, we define the judgment form $\\Gamma \\vdash e : \\tau$, which\n", + "says, āIn type environment $\\Gamma$, expression $e$ has type $\\tau$.ā\n", + "\n", + "Because we need to distinguish between assignable expressions that\n", + "specify memory locations (e.g., $x$ declared as $\\mathbf{var}$) versus\n", + "non-assignable expressions (e.g., $n$), type environments now map\n", + "variables $x$ to their mode $d$ and type $\\tau$: $$\n", + "\\begin{array}{rrrl}\n", + " \\text{type environments} & \\Gamma& \\mathrel{::=}& \\cdot\\mid\\Gamma, x : d\\,\\tau\n", + "\\end{array}\n", + "$$\n", + "\n", + "Note that it would be arguably cleaner to define type environments to\n", + "carry just the needed assumptions (i.e., āassignabilityā and type). For\n", + "our purposes, the mode $d$ is a placeholder for āassignability.ā\n", + "\n", + "We then implement a function `hastype`:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2e04c495", + "metadata": {}, + "outputs": [], + "source": [ + "def hastype(tenv: Map[String, MTyp], e: Expr): Typ = ???" + ] + }, + { + "cell_type": "markdown", + "id": "5b2e9eff-3747-42ed-ba9b-d043dca3f445", + "metadata": {}, + "source": [ + "that corresponds directly to this judgment form. It takes as input a\n", + "type environment `tenv: Map[String, MTyp]` ($\\Gamma$) and an expression\n", + "`e: Expr` ($e$) to return a type `Typ` ($\\tau$).\n", + "\n", + "#### Notes\n", + "\n", + "- Note that the provided tests are minimal. **You will want to add\n", + " your own tests to cover most language features.**\n", + "- As before, we recommend āincrementally grow the languageā by going\n", + " language-feature by-language-feature rather than\n", + " function-by-function in your implementation. In the subsequent\n", + " steps, we describe the small-step operational semantics and the\n", + " static typing semantics together incrementally by language feature.\n", + "\n", + "## Base TypeScripty\n", + "\n", + "### Small-Step Reduction\n", + "\n", + "We consider the base TypeScripty that has numbers with arithmetic\n", + "expressions, booleans with logic and comparison expressions, strings\n", + "with concatenation, $\\mathbf{undefined}$ with printing, and\n", + "$\\mathbf{const}$-variable declarations.\n", + "\n", + "$\\fbox{$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $}$\n", + "\n", + "$\\inferrule[DoNeg]{\n", + " n' = - n_1\n", + "}{\n", + " \\langle \\mathop{\\texttt{-}} n_1, m \\rangle \\longrightarrow \\langle n', m \\rangle \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", + " \\langle n_1 \\mathbin{\\mathit{bop}}n_2, m \\rangle \\longrightarrow \\langle n', m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoPlusString]{\n", + " \\mathit{str}' = \\mathit{str}_1 \\mathit{str}_2\n", + "}{\n", + " \\langle \\mathit{str}_1 \\mathbin{\\texttt{+}} \\mathit{str}_2, m \\rangle \\longrightarrow \\langle \\mathit{str}', m \\rangle \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", + " \\langle n_1 \\mathbin{\\mathit{bop}}n_2, m \\rangle \\longrightarrow \\langle b', m \\rangle \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", + " \\langle \\mathit{str}_1 \\mathbin{\\mathit{bop}}\\mathit{str}_2, m \\rangle \\longrightarrow \\langle b', m \\rangle \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", + " \\langle v_1 \\mathbin{\\mathit{bop}}v_2, m \\rangle \\longrightarrow \\langle b', m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoNot]{\n", + " b' = \\neg b_1\n", + "}{\n", + " \\langle \\mathop{\\texttt{!}} b_1, m \\rangle \\longrightarrow \\langle b', m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoAndTrue]{\n", + "}{\n", + " \\langle \\mathbf{true} \\mathbin{\\texttt{\\&\\&}} e_2, m \\rangle \\longrightarrow \\langle e_2, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoAndFalse]{\n", + "}{\n", + " \\langle \\mathbf{false} \\mathbin{\\texttt{\\&\\&}} e_2, m \\rangle \\longrightarrow \\langle v_1, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoOrTrue]{\n", + "}{\n", + " \\langle \\mathbf{true} \\mathbin{\\texttt{||}} e_2, m \\rangle \\longrightarrow \\langle v_1, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoOrFalse]{\n", + "}{\n", + " \\langle \\mathbf{false} \\mathbin{\\texttt{||}} e_2, m \\rangle \\longrightarrow \\langle e_2, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoIfTrue]{\n", + "}{\n", + " \\langle \\mathbf{true}\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3, m \\rangle \\longrightarrow \\langle e_2, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoIfFalse]{\n", + "}{\n", + " \\langle \\mathbf{false}\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3, m \\rangle \\longrightarrow \\langle e_3, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoSeq]{\n", + "}{\n", + " \\langle v_1 \\mathbin{\\texttt{,}} e_2, m \\rangle \\longrightarrow \\langle e_2, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoPrint]{\n", + " \\text{$v_1$ printed}\n", + "}{\n", + " \\langle \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}v_1\\texttt{)}, m \\rangle \\longrightarrow \\langle \\mathbf{undefined}, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoConstDecl]{\n", + "}{\n", + " \\langle \\mathbf{const}\\;x\\;\\texttt{=}\\;v_1\\texttt{;}\\;e_2, m \\rangle \\longrightarrow \\langle [v_1/x]e_2, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchUnary]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle \\mathop{\\mathit{uop}}e_1, m \\rangle \\longrightarrow \\langle \\mathop{\\mathit{uop}}e_1', m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchBinary1]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle e_1 \\mathbin{\\mathit{bop}}e_2, m \\rangle \\longrightarrow \\langle e_1' \\mathbin{\\mathit{bop}}e_2, m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchBinary2]{\n", + " \\langle e_2, m \\rangle \\longrightarrow \\langle e_2', m' \\rangle \n", + "}{\n", + " \\langle v_1 \\mathbin{\\mathit{bop}}e_2, m \\rangle \\longrightarrow \\langle v_1 \\mathbin{\\mathit{bop}}e_2', m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchIf]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3, m \\rangle \\longrightarrow \\langle e_1'\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3, m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchPrint]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)}, m \\rangle \\longrightarrow \\langle \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1'\\texttt{)}, m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchConstDecl]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2, m \\rangle \\longrightarrow \\langle \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1'\\texttt{;}\\;e_2, m' \\rangle \n", + "}$\n", + "\n", + "FigureĀ 10: Small-step operational semantics of base TypeScripty,\n", + "including numbers with arithmetic expressions, booleans with logic and\n", + "comparison expressions, strings with concatenation, $\\mathbf{undefined}$\n", + "with printing, and $\\mathbf{const}$-variable declarations.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1 (Small-Step Reduction for Base\n", + "TypeScripty)**</span> Implement `step` for base TypeScripty following\n", + "the small-step operational semantics in\n", + "<a href=\"#fig-typescripty-basemem-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 10</a> defining the reduction-step judgment\n", + "form $ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $.\n", + "\n", + "Note that your task here is essentially refactoring a `step` function\n", + "for the pure language features that do not use memory `Mem` to thread\n", + "it. Because we are implementing `step` with type\n", + "`Expr => DoWith[Mem, Expr]`, the code changes here is minimal and\n", + "type-directed.\n", + "\n", + "### Static Type Checking\n", + "\n", + "We define static typing with the judgment form $\\Gamma \\vdash e : \\tau$\n", + "of base TypeScripty that has numbers with arithmetic expressions,\n", + "booleans with logic and comparison expressions, strings with\n", + "concatenation, $\\mathbf{undefined}$ with printing, and\n", + "$\\mathbf{const}$-variable as before:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeNumber]{\n", + "}{\n", + " \\Gamma \\vdash n : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypeString]{\n", + "}{\n", + " \\Gamma \\vdash \\mathit{str} : \\texttt{string}\n", + "}$\n", + "\n", + "$\\inferrule[TypeNeg]{\n", + " \\Gamma \\vdash e_1 : \\texttt{number}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{-}} e_1 : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypeArith]{\n", + " \\Gamma \\vdash e_1 : \\texttt{number}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{number}\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{-}, \\texttt{*}, \\texttt{/} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{number}\n", + "}$\n", + "\n", + "$\\inferrule[TypePlusString]{\n", + " \\Gamma \\vdash e_1 : \\texttt{string}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{string}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{+}} e_2 : \\texttt{string}\n", + "}$\n", + "\n", + "$\\inferrule[TypeInequalityNumber]{\n", + " \\Gamma \\vdash e_1 : \\texttt{number}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{number}\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeInequalityString]{\n", + " \\Gamma \\vdash e_1 : \\texttt{string}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{string}\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeEquality]{\n", + " \\Gamma \\vdash e_1 : \\tau\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{===}, \\texttt{!==} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeBool]{\n", + "}{\n", + " \\Gamma \\vdash b : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeNot]{\n", + " \\Gamma \\vdash e_1 : \\texttt{bool}\n", + "}{\n", + " \\Gamma \\vdash \\mathop{\\texttt{!}} e_1 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeAndOr]{\n", + " \\Gamma \\vdash e_1 : \\texttt{bool}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\texttt{bool}\n", + " \\and\n", + " \\mathit{bop}\\in \\left\\{ \\texttt{\\&\\&}, \\texttt{||} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\mathit{bop}}e_2 : \\texttt{bool}\n", + "}$\n", + "\n", + "$\\inferrule[TypeIf]{\n", + " \\Gamma \\vdash e_1 : \\texttt{bool}\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + " \\and\n", + " \\Gamma \\vdash e_3 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 : \\tau\n", + "}$\n", + "\n", + "$\\inferrule[TypeUndefined]{\n", + "}{\n", + " \\Gamma \\vdash \\mathbf{undefined} : \\texttt{Undefined}\n", + "}$\n", + "\n", + "$\\inferrule[TypeSeq]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathbin{\\texttt{,}} e_2 : \\tau_2\n", + "}$\n", + "\n", + "$\\inferrule[TypePrint]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + "}{\n", + " \\Gamma \\vdash \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)} : \\texttt{Undefined}\n", + "}$\n", + "\n", + "$\\inferrule[TypeConstDecl]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\Gamma, x : \\mathbf{const}\\,\\tau_1 \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n", + "}$\n", + "\n", + "FigureĀ 11: Typing of base TypeScripty, including numbers with arithmetic\n", + "expressions, booleans with logic and comparison expressions, strings\n", + "with concatenation, $\\mathbf{undefined}$ with printing, and\n", + "$\\mathbf{const}$-varable declarations.\n", + "\n", + "We will maintain the invariant that a variable use $x$ corresponds to\n", + "its assumed type, regardless of its mode $d$, so we may generalize the\n", + "typing of all variable uses and declarations:\n", + "\n", + "$\\inferrule[TypeVar]{\n", + " x : d\\,\\tau \\in \\Gamma\n", + "}{\n", + " \\Gamma \\vdash x : \\tau\n", + "}$\n", + "\n", + "FigureĀ 12: Typing of variable uses.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 2 (Static Type Checking for Base\n", + "TypeScripty)**</span> Implement a function `hastype` for base TypeScript\n", + "following the static typing semantics in\n", + "<a href=\"#fig-typescripty-basemem-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 11</a> and\n", + "<a href=\"#fig-typescripty-declmem-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 12</a> defining the typing judgment form\n", + "$\\Gamma \\vdash e : \\tau$.\n", + "\n", + "## Mutable Variables\n", + "\n", + "### Small-Step Reduction\n", + "\n", + "A location value $\\mathord{\\texttt{*}}a$ specifies a memory cell\n", + "$[a \\mapsto v]$ corresponding to a mutable variable $x$. Observe that\n", + "$\\TirName{DoDeref}$ corresponds to reading a mutable variable,\n", + "$\\TirName{DoAssignVar}$ to assigning to a mutable variable, and\n", + "$\\TirName{DoVarDecl}$ to allocating a new mutable variable. See the\n", + "Mutable State chapter (**?@sec-javascripty-variables-smallstep**) for a\n", + "more in-depth discussion.\n", + "\n", + "$\\fbox{$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $}$\n", + "\n", + "$\\inferrule[DoDeref]{\n", + "}{\n", + " \\langle \\mathord{\\texttt{*}}a , m \\rangle \\longrightarrow \\langle m(a) , m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoAssignVar]{\n", + "}{\n", + " \\langle \\mathord{\\texttt{*}}a \\mathrel{\\texttt{=}} v , m \\rangle \\longrightarrow \\langle v, m[a \\mapsto v] \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchAssign2Var]{\n", + " \\langle e_2, m \\rangle \\longrightarrow \\langle e_2', m' \\rangle \n", + "}{\n", + " \\langle \\mathord{\\texttt{*}}a \\mathrel{\\texttt{=}} e_2 , m \\rangle \\longrightarrow \\langle \\mathord{\\texttt{*}}a \\mathrel{\\texttt{=}} e_2' , m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoVarDecl]{\n", + " a\\notin \\operatorname{dom}(m)\n", + "}{\n", + " \\langle \\mathbf{var}\\;x\\;\\texttt{=}\\;v_1\\texttt{;}\\;e_2 , m \\rangle \\longrightarrow \\langle {}[ \\mathord{\\texttt{*}}a /x]e_2 , m[a \\mapsto v_1] \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchVarDecl]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle \\mathbf{var}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 , m \\rangle \\longrightarrow \\langle \\mathbf{var}\\;x\\;\\texttt{=}\\;e_1'\\texttt{;}\\;e_2 , m' \\rangle \n", + "}$\n", + "\n", + "FigureĀ 13: Small-step operational semantics with mutable variables.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3 (Small-Step Reduction for\n", + "Mutable Variables)**</span> Implement the cases in `step` for reducing\n", + "mutable variables using the rules given in\n", + "<a href=\"#fig-typescripty-mutable-variables-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 13</a> for the reduction-step judgment form\n", + "$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $.\n", + "\n", + "### Static Type Checking\n", + "\n", + "We check that the left-handāside of assignment is an assignable, mutable\n", + "variable:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeAssignVar]{\n", + " x : \\mathbf{var}\\,\\tau \\in \\Gamma\n", + " \\and\n", + " \\Gamma \\vdash e : \\tau\n", + "}{\n", + " \\Gamma \\vdash x \\mathrel{\\texttt{=}}e : \\tau\n", + "}$\n", + "\n", + "$\\inferrule[TypeVarDecl]{\n", + " \\Gamma \\vdash e_1 : \\tau_1\n", + " \\and\n", + " \\Gamma, x : \\mathbf{var}\\,\\tau_1 \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash \\mathbf{var}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n", + "}$\n", + "\n", + "FigureĀ 14: Typing of assignment to and declaration of mutable variables.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 4 (Static Type Checking for\n", + "Mutable Variables)**</span> Implement the cases in `hastype` for typing\n", + "mutable variable expressions using the rules given in\n", + "<a href=\"#fig-typescripty-mutable-variables-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 14</a> defining the typing judgment form\n", + "$\\Gamma \\vdash e : \\tau$.\n", + "\n", + "## Dynamically-Allocated Mutable Objects\n", + "\n", + "### Small-Step Reduction\n", + "\n", + "The $\\TirName{DoObject}$ rule states that an object\n", + "$\\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}}$ is not a value and\n", + "steps an address (i.e., a pointer). In particular, it allocates a memory\n", + "address $a$, stores the object at that memory location\n", + "$[a \\mapsto \\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}} ]$, and\n", + "returns the pointer $a$ to the object\n", + "$\\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}}$ as its value. See\n", + "the section on Pointers (**?@sec-javascripty-pointers-smallstep**) for\n", + "further discussion.\n", + "\n", + "$\\fbox{$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $}$\n", + "\n", + "$\\inferrule[DoObject]{\n", + " a\\notin \\operatorname{dom}(m)\n", + "}{\n", + " \\langle \\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}} , m \\rangle \\longrightarrow \\langle a, m[a \\mapsto \\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}} ] \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoGetField]{\n", + " m(a) = \n", + " \\texttt{\\{} \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,v\\texttt{,}\n", + " \\ldots\n", + " \\texttt{\\}}\n", + "}{\n", + " \\langle a\\texttt{.}f , m \\rangle \\longrightarrow \\langle v, m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchObject]{\n", + " \\langle e_i, m \\rangle \\longrightarrow \\langle e_i', m' \\rangle \n", + "}{\n", + " \\langle \\texttt{\\{} \\ldots\\texttt{,}f_i\\texttt{:}\\,e_i\\texttt{,}\\ldots \\texttt{\\}} , m \\rangle \\longrightarrow \\langle \\texttt{\\{} \\ldots\\texttt{,}f_i\\texttt{:}\\,e_i'\\texttt{,}\\ldots \\texttt{\\}} , m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchGetField]{\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle e_1\\texttt{.}f , m \\rangle \\longrightarrow \\langle e_1'\\texttt{.}f , m' \\rangle \n", + "}$\n", + "\n", + "FigureĀ 15: Small-step operational semantics of allocating and reading\n", + "from dynamically-allocated mutable objects.\n", + "\n", + "The $\\TirName{DoAssignField}$ rule is as expectedāreplacing the value of\n", + "an object field given by a location value $a\\texttt{.}f$:\n", + "\n", + "$\\inferrule[DoAssignField]{\n", + " m(a) = \n", + " \\texttt{\\{} \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,v\\texttt{,}\n", + " \\ldots\n", + " \\texttt{\\}}\n", + "}{\n", + " \\langle a\\texttt{.}f \\mathrel{\\texttt{=}} v' , m \\rangle \\longrightarrow \\langle v' , m[a \\mapsto \\texttt{\\{} \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,v'\\texttt{,}\n", + " \\ldots\n", + " \\texttt{\\}} ] \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchAssign2]{\n", + " e_1\\;\\mathsf{location}\n", + " \\and\n", + " \\langle e_2, m \\rangle \\longrightarrow \\langle e_2', m' \\rangle \n", + "}{\n", + " \\langle e_1 \\mathrel{\\texttt{=}} e_2 , m \\rangle \\longrightarrow \\langle e_1 \\mathrel{\\texttt{=}} e_2' , m' \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchAssign1]{\n", + " \\nvdash e_1\\;\\mathsf{location}\n", + " \\and\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle e_1 \\mathrel{\\texttt{=}} e_2 , m \\rangle \\longrightarrow \\langle e_1' \\mathrel{\\texttt{=}} e_2 , m' \\rangle \n", + "}$\n", + "\n", + "FigureĀ 16: Small-step operational semantics of assigning to object\n", + "fields.\n", + "\n", + "However, now its possible that the left-handāside of assignment needs to\n", + "be reduced to a location value. With mutable variables, we knew and\n", + "assumed that the left-handāside would immediately by its location value\n", + "by substitution. We generalize the search rules for the assignment\n", + "expression $e_1 \\mathrel{\\texttt{=}}e_2$ to reduce $e_1$ to a location\n", + "value (i.e., satisfies $e_1\\;\\mathsf{location}$) with rule\n", + "$\\TirName{SearchAssign1}$. We write $\\nvdash e_1\\;\\mathsf{location}$ for\n", + "when $e_1$ is not a location value. The $\\TirName{SearchAssign2}$ rule\n", + "generalizes $\\TirName{SearchAssign2Var}$ above for reducing the\n", + "right-handāside of assignment to a value.\n", + "\n", + "In implementation, the judgment form $e_1\\;\\mathsf{location}$ is\n", + "specified by the `isLValue` function.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 5 (Small-Step Reduction for\n", + "Mutable Objects)**</span> Implement the cases in `step` for reducing\n", + "dynamically-allocated mutable objects using the rules given in\n", + "<a href=\"#fig-typescripty-mutable-objects-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 15</a> and\n", + "<a href=\"#fig-typescripty-field-assignment-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 16</a> for the reduction-step judgment form\n", + "$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $.\n", + "\n", + "### Static Type Checking\n", + "\n", + "Typing of object literals and reading from a field is unchanged because\n", + "allocation and reading from memory is a run-time consideration:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeObject]{\n", + " \\Gamma \\vdash e_i : \\tau_i\n", + " \\and\n", + " \\text{for all $i$}\n", + "}{\n", + " \\Gamma \\vdash \\texttt{\\{}\n", + " \\ldots\\texttt{,}\n", + " f_i\\texttt{:}\\,e_i\\texttt{,}\n", + " \\ldots \\texttt{\\}}\n", + " : \\texttt{\\{}\n", + " \\ldots\\texttt{,}\n", + " f_i\\texttt{:}\\,\\tau_i\\texttt{,}\n", + " \\ldots \\texttt{\\}} \n", + "}$\n", + "\n", + "$\\inferrule[TypeGetField]{\n", + " \\Gamma \\vdash e : \\texttt{\\{}\n", + " \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,\\tau\\texttt{,}\n", + " \\ldots \\texttt{\\}} \n", + "}{\n", + " \\Gamma \\vdash \n", + " e\\texttt{.}f\n", + " : \\tau\n", + "}$\n", + "\n", + "FigureĀ 17: Typing of object literals and field read.\n", + "\n", + "We also need to check that the left-handāside of assignment could be an\n", + "assignable field:\n", + "\n", + "$\\inferrule[TypeAssignField]{\n", + " \\Gamma \\vdash e_1 : \\texttt{\\{}\n", + " \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,\\tau\\texttt{,}\n", + " \\ldots \\texttt{\\}} \n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1\\texttt{.}f \\mathrel{\\texttt{=}}e_2 : \\tau\n", + "}$\n", + "\n", + "FigureĀ 18: Typing of assignment to object fields.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6 (Static Type Checking for\n", + "Mutable Objects)**</span> Implement the cases in `hastype` for typing\n", + "dynamically-allocated mutable object expressions using the rules given\n", + "in <a href=\"#fig-typescripty-mutable-objects-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 17</a> and\n", + "<a href=\"#fig-typescripty-field-assignment-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 18</a> defining the typing judgment form\n", + "$\\Gamma \\vdash e : \\tau$.\n", + "\n", + "## Location References\n", + "\n", + "### Small-Step Reduction\n", + "\n", + "A reference variable is one that uses a previously-allocated location:\n", + "\n", + "$\\fbox{$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $}$\n", + "\n", + "$\\inferrule[DoRefDecl]{\n", + " e_1\\;\\mathsf{location}\n", + "}{\n", + " \\langle \\mathbf{ref}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 , m \\rangle \\longrightarrow \\langle {}[ e_1 /x]e_2 , m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchRefDecl]{\n", + " \\nvdash e_1\\;\\mathsf{location}\n", + " \\and\n", + " \\langle e_1, m \\rangle \\longrightarrow \\langle e_1', m' \\rangle \n", + "}{\n", + " \\langle \\mathbf{ref}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 , m \\rangle \\longrightarrow \\langle \\mathbf{ref}\\;x\\;\\texttt{=}\\;e_1'\\texttt{;}\\;e_2 , m' \\rangle \n", + "}$\n", + "\n", + "FigureĀ 19: Small-step operational semantics of location references.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7 (Small-Step Reduction for\n", + "Location References)**</span> Implement the cases in `step` for reducing\n", + "location references using the rules given in\n", + "<a href=\"#fig-typescripty-locref-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 19</a> for the reduction-step judgment form\n", + "$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $.\n", + "\n", + "### Static Type Checking\n", + "\n", + "Examining the $\\TirName{DoRefDecl}$ rule in the operational semantics,\n", + "we see that we need to ensure that statically the binding expression\n", + "$e_1$ refers to a location (i.e., either a mutable variable or field).\n", + "We considered this case-by-case, but let us define a judgment form that\n", + "captures this concept:\n", + "\n", + "$$\n", + "\\Gamma \\vdash e \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau\n", + "$$\n", + "\n", + "says informally, āIn typing environment $\\Gamma$, expression $e$ is a\n", + "location expression whose contents have type $\\tau$.ā This judgment form\n", + "is the static analogue of the run-time judgment form\n", + "$e\\;\\mathsf{location}$.\n", + "\n", + "We implement this judgment form with the following Scala function:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "52d5e674", + "metadata": {}, + "outputs": [], + "source": [ + "def hasloctype(tenv: Map[String, MTyp], e: Expr): Option[Typ] = ???" + ] + }, + { + "cell_type": "markdown", + "id": "8c4b3445-2ab4-4f3e-bb69-5c53938352a5", + "metadata": {}, + "source": [ + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeRefDecl]{\n", + " \\Gamma \\vdash e_1 \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau_1\n", + " \\and\n", + " \\Gamma, x : \\mathbf{ref}\\,\\tau_1 \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash \\mathbf{ref}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n", + "}$\n", + "\n", + "$\\inferrule[TypeAssign]{\n", + " \\Gamma \\vdash e_1 \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau\n", + " \\and\n", + " \\Gamma \\vdash e_2 : \\tau\n", + "}{\n", + " \\Gamma \\vdash e_1 \\mathrel{\\texttt{=}}e_2 : \\tau\n", + "}$\n", + "\n", + "FigureĀ 20: Typing of declaration of location references and assignment.\n", + "\n", + "With this location-typing judgment form, we can replace\n", + "$\\TirName{TypeAssignVar}$ and $\\TirName{TypeAssignField}$ with the\n", + "$\\TirName{TypeAssign}$ rule given above. And we see that the\n", + "location-typing judgment form specifies that mutable variables or fields\n", + "are location expressions, which we had previously inlined:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau$}$\n", + "\n", + "$\\inferrule[LocTypeVar]{\n", + " x : d\\,\\tau \\in \\Gamma\n", + " \\and\n", + " d\\in \\left\\{ \\mathbf{var}, \\mathbf{ref} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash x \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau\n", + "}$\n", + "\n", + "$\\inferrule[LocTypeGetField]{\n", + " \\Gamma \\vdash e : \\texttt{\\{}\n", + " \\ldots\\texttt{,}\n", + " f\\texttt{:}\\,\\tau\\texttt{,}\n", + " \\ldots \\texttt{\\}} \n", + "}{\n", + " \\Gamma \\vdash e\\texttt{.}f \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau\n", + "}$\n", + "\n", + "FigureĀ 21: Location typing of mutable variables and object fields.\n", + "\n", + "We see here in the $\\TirName{LocTypeVar}$ rule that it would arguably be\n", + "clearer for the typing environment to carry location assumptions, rather\n", + "than the varable mode $d$ directly.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (Static Type Checking for\n", + "Mutable Variables)**</span> Implement the cases in `hastype` for typing\n", + "location reference expressions using the rules given in\n", + "<a href=\"#fig-typescripty-locref-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 20</a> defining the typing judgment form\n", + "$\\Gamma \\vdash e : \\tau$ and `hasloctype` for the location typing\n", + "judgment form $\\Gamma \\vdash e \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau$\n", + "using the rules given in <a href=\"#fig-typescripty-loctyping-lab\"\n", + "class=\"quarto-xref\">FigureĀ 21</a>.\n", + "\n", + "## Multi-Parameter Procedures with Parameter-Passing Modes (Extra Credit)\n", + "\n", + "For procedures, we want to support an arbitrary number of parameters\n", + "that may be individually declared with any parameter-passing mode. To\n", + "avoid re-encoding the case analysis of the $\\TirName{DoConstDecl}$,\n", + "$\\TirName{SearchConstDecl}$, $\\TirName{DoVarDecl}$,\n", + "$\\TirName{SearchVarDecl}$, and $\\TirName{DoRefDecl}$, and\n", + "$\\TirName{SearchRefDecl}$ rules, we define the $\\TirName{DoCall}$ and\n", + "$\\TirName{DoCallRec}$ rules to transform the parameter binding to a\n", + "variable binding expression $e'$.\n", + "\n", + "$\\fbox{$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $}$\n", + "\n", + "$\\inferrule[DoCall]{\n", + " e' =\n", + " d_1\\;y_1\\;\\texttt{=}\\;e_1\\texttt{;}\\; \\cdots\\texttt{;}d_n\\;y_n\\;\\texttt{=}\\;e_n\\texttt{;}\\; e \n", + "}{\n", + " \\langle (\\texttt{(} y_1\\texttt{:}\\, d_1\\,\\tau_1 \\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\, d_n\\,\\tau_n \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e) \\texttt{(}e_1\\texttt{,}\\ldots\\texttt{,}e_n\\texttt{)} , m \\rangle \\longrightarrow \\langle e' , m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[DoCallRec]{\n", + " v= (x\\texttt{(} y_1\\texttt{:}\\, d_1\\,\\tau_1 \\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\, d_n\\,\\tau_n \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e)\n", + " \\and\n", + " e' =\n", + " d_1\\;y_1\\;\\texttt{=}\\;e_1\\texttt{;}\\; \\cdots\\texttt{;}d_n\\;y_n\\;\\texttt{=}\\;e_n\\texttt{;}\\; e \n", + "}{\n", + " \\langle v\\texttt{(} e_1\\texttt{,}\\ldots\\texttt{,}e_n \\texttt{)} , m \\rangle \\longrightarrow \\langle {}[v/x]e' , m \\rangle \n", + "}$\n", + "\n", + "$\\inferrule[SearchCall1]{\n", + " e\\longrightarrow e'\n", + "}{\n", + " e\\texttt{(}e_1, \\ldots, e_n\\texttt{)}\n", + " \\longrightarrow\n", + " e'\\texttt{(}e_1, \\ldots, e_n\\texttt{)}\n", + "}$\n", + "\n", + "FigureĀ 22: Small-step operational semantics for multi-parameter\n", + "recursive procedures with parameter-passing modes.\n", + "\n", + "Observe that there is no $\\TirName{SearchCall2}$ rule that reduces the\n", + "arguments, as the appropriate reduction of those arguments happens via\n", + "the $\\TirName{SearchConstDecl}$, $\\TirName{SearchVarDecl}$, and\n", + "$\\TirName{SearchRefDecl}$ rules.\n", + "\n", + "### Small-Step Reduction\n", + "\n", + "<span class=\"theorem-title\">**Exercise 9 (Small-Step Reduction for\n", + "Parameter-Passing Modes)**</span> Implement the cases in `step` for\n", + "reducing procedures with parameter passing modes using the rules given\n", + "in <a href=\"#fig-typescripty-procedures-smallstep-lab\"\n", + "class=\"quarto-xref\">FigureĀ 22</a> for the reduction-step judgment form\n", + "$ \\langle e, m \\rangle \\longrightarrow \\langle e', m' \\rangle $.\n", + "\n", + "### Static Type Checking\n", + "\n", + "For typing, we similarly want to avoid re-encoding the case analysis of\n", + "the $\\TirName{TypeConstDecl}$, $\\TirName{TypeVarDecl}$, and\n", + "$\\TirName{TypeRefDecl}$. Let us define a judgment form that combines the\n", + "cases to state state when an expression is well-typed for a given mode:\n", + "\n", + "$$\n", + "\\Gamma \\vdash e : d\\,\\tau\n", + "$$\n", + "\n", + "saying, āIn type environment $\\Gamma$, expression $e$ has type $\\tau$\n", + "and can be bound to a variable with mode $d$.ā\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : d\\,\\tau$}$\n", + "\n", + "$\\inferrule[ValBindable]{\n", + " \\Gamma \\vdash e : \\tau\n", + " \\and\n", + " d\\in \\left\\{ \\mathbf{const}, \\mathbf{var} \\right\\}\n", + "}{\n", + " \\Gamma \\vdash e : d\\,\\tau\n", + "}$\n", + "\n", + "$\\inferrule[RefBindable]{\n", + " \\Gamma \\vdash e \\mathrel{\\mathord{:}\\mathord{\\&}} \\tau\n", + "}{\n", + " \\Gamma \\vdash e : \\mathbf{ref}\\,\\tau\n", + "}$\n", + "\n", + "FigureĀ 23: Typing with bindablity to a given variable mode.\n", + "\n", + "We implement this judgment form with the following Scala function:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "9df9c747", + "metadata": {}, + "outputs": [], + "source": [ + "def hasmodetype(tenv: Map[String, MTyp], e: Expr, d: Mode): Option[Typ] = ???" + ] + }, + { + "cell_type": "markdown", + "id": "ffabb1e9-bb0e-47d7-b365-167451899166", + "metadata": {}, + "source": [ + "We can then define the $\\TirName{TypeDecl}$ and $\\TirName{TypeCall}$\n", + "rules as follows:\n", + "\n", + "$\\fbox{$\\Gamma \\vdash e : \\tau$}$\n", + "\n", + "$\\inferrule[TypeDecl]{\n", + " \\Gamma \\vdash e_1 : d\\,\\tau_1\n", + " \\and\n", + " \\Gamma, x : d\\,\\tau_1 \\vdash e_2 : \\tau_2\n", + "}{\n", + " \\Gamma \\vdash d\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n", + "}$\n", + "\n", + "$\\inferrule[TypeCall]{\n", + " \\Gamma \\vdash e : \\texttt{(} y_1\\texttt{:}\\,d_1\\,\\tau_1\\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\,d_n\\,\\tau_n \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau \n", + " \\and\n", + " \\Gamma \\vdash e_1 : d_1\\,\\tau_1\n", + " \\quad\\cdots\\quad\n", + " \\Gamma \\vdash e_n : d_n\\,\\tau_n\n", + "}{\n", + " \\Gamma \\vdash e\\texttt{(}e_1, \\ldots, e_n\\texttt{)} : \\tau\n", + "}$\n", + "\n", + "FigureĀ 24: Typing of variable declarations and call with\n", + "parameter-passing modes.\n", + "\n", + "Note that we can use the $\\TirName{TypeDecl}$ rule to replace the\n", + "$\\TirName{TypeConstDecl}$, $\\TirName{TypeVarDecl}$, and\n", + "$\\TirName{TypeRefDecl}$ rules. You may optionally refactor your\n", + "implementation to use $\\TirName{TypeDecl}$.\n", + "\n", + "Typing of function literals remains essentially the same, except that\n", + "declared modes are also assumed in the typing environment:\n", + "\n", + "$\\inferrule[TypeFunction]{\n", + " \\Gamma, y_1 : d_1\\,\\tau_1, \\cdots , y_n : d_n\\,\\tau_n \\vdash e' : \\tau'\n", + "}{\n", + " \\Gamma \\vdash \\texttt{(} \\overline{y\\texttt{:}\\, d\\,\\tau } \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n", + "}$\n", + "\n", + "$\\inferrule[TypeFunctionAnn]{\n", + " \\Gamma, y_1 : d_1\\,\\tau_1, \\cdots, , y_n : d_n\\,\\tau_n \\vdash e' : \\tau'\n", + "}{\n", + " \\Gamma \\vdash \\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n", + "}$\n", + "\n", + "$\\inferrule[TypeFunctionRec]{\n", + " \\Gamma, x : \\tau_x , y_1 : d_1\\,\\tau_1, \\cdots, , y_n : d_n\\,\\tau_n \\vdash e' : \\tau'\n", + " \\and\n", + " \\tau_x = \\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n", + "}{\n", + " \\Gamma \\vdash x\\texttt{(} \\overline{y\\texttt{:}\\,d\\,\\tau} \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\tau_x \n", + "}$\n", + "\n", + "FigureĀ 25: Typing of multi-parameter recursive functions.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 10 (Static Type Checking for\n", + "Parameter-Passing Modes)**</span> Implement the cases in `hastype` for\n", + "typing procedures with parameter-passing modes using the rules given in\n", + "<a href=\"#fig-typescripty-modedecl-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 24</a> and\n", + "<a href=\"#fig-typescripty-procedures-typing-lab\"\n", + "class=\"quarto-xref\">FigureĀ 25</a> defining the typing judgment form\n", + "$\\Gamma \\vdash e : \\tau$ and `hasmodetype` for typing with bindablity to\n", + "a given variable mode in <a href=\"#fig-typescripty-mode-bindable-lab\"\n", + "class=\"quarto-xref\">FigureĀ 23</a>." + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Scala", + "language": "scala", + "name": "scala", + "path": "/Users/bec/Library/Jupyter/kernels/scala" + }, + "language_info": { + "codemirror_mode": "text/x-scala", + "file_extension": ".sc", + "mimetype": "text/x-scala", + "name": "scala", + "nbconvert_exporter": "script", + "version": "2.13.4" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} diff --git a/lab5/project/build.properties b/lab5/project/build.properties new file mode 100644 index 0000000..ee4c672 --- /dev/null +++ b/lab5/project/build.properties @@ -0,0 +1 @@ +sbt.version=1.10.1 diff --git a/lab5/src/main/scala/jsy/lab5/Lab5.scala b/lab5/src/main/scala/jsy/lab5/Lab5.scala new file mode 100644 index 0000000..ad62ef9 --- /dev/null +++ b/lab5/src/main/scala/jsy/lab5/Lab5.scala @@ -0,0 +1,410 @@ +package jsy.lab5 + +import scala.collection.immutable.SortedMap +import jsy.lab5.Parser.parse + +object Lab5 extends jsy.util.JsyApplication { + import jsy.lab5.ast._ + import jsy.util.DoWith + import jsy.util.DoWith._ + + /* + * CSCI 3155: Lab 5 + * Jack Sangdahl + */ + + /** * Type Inference ** + */ + def hasloctype(env: Map[String, MTyp], e: Expr): Option[Typ] = + try { Some(hastype(env, e)) } + catch { case _: StaticTypeError => None } + + def hasmodetype(env: Map[String, MTyp], e: Expr, d: Mode): Option[Typ] = + try { + val typ = hastype(env, e) + d match { + case MConst => Some(typ) + case MVar if typ != TUndefined => Some(typ) + case MRef if typ != TUndefined => Some(typ) + case _ => None + } + } catch { + case e: StaticTypeError => None + } + + def hastype(env: Map[String, MTyp], e: Expr): Typ = { + def err[T](tgot: Typ, e1: Expr): T = throw StaticTypeError(tgot, e1, e) + def errnotype[T](e1: Expr): T = err(TUndefined, e1) + + e match { + case Print(e1) => hastype(env, e1); TUndefined + case N(_) => TNumber + case B(_) => TBool + case Undefined => TUndefined + case S(_) => TString + case Var(x) => + env.get(x).map { case MTyp(_, typ) => typ }.getOrElse(errnotype(e)) + case Unary(Neg, e1) => + hastype(env, e1) match { + case TNumber => TNumber + case tgot => err(tgot, e1) + } + case Unary(Not, e1) => + hastype(env, e1) match { + case TBool => TBool + case tgot => err(tgot, e1) + } + case Binary(Plus, e1, e2) => + (hastype(env, e1), hastype(env, e2)) match { + case (TNumber, TNumber) => TNumber + case (TString, TString) => TString + case (tgot1, _) => err(tgot1, e1) + } + case Binary(Minus | Times | Div, e1, e2) => + (hastype(env, e1), hastype(env, e2)) match { + case (TNumber, TNumber) => TNumber + case (tgot1, _) => err(tgot1, e1) + } + case Binary(Eq | Ne, e1, e2) => + (hastype(env, e1), hastype(env, e2)) match { + case (t1, t2) if t1 == t2 => TBool + case (tgot1, _) => err(tgot1, e1) + } + case Binary(Lt | Le | Gt | Ge, e1, e2) => + (hastype(env, e1), hastype(env, e2)) match { + case (TNumber, TNumber) => TBool + case (tgot1, _) => err(tgot1, e1) + } + case Binary(And | Or, e1, e2) => + (hastype(env, e1), hastype(env, e2)) match { + case (TBool, TBool) => TBool + case (tgot, _) => err(tgot, e1) + } + case Binary(Seq, e1, e2) => + hastype(env, e1) + hastype(env, e2) + case If(e1, e2, e3) => + hastype(env, e1) match { + case (TBool) => + val t2 = hastype(env, e2) + val t3 = hastype(env, e3) + if (t2 == t3) t2 + else err(t2, e2) + case tgot => err(tgot, e1) + } + + case Obj(fields) => + TObj(fields.map { case (f, e1) => (f, hastype(env, e1)) }) + case GetField(e1, f) => + hastype(env, e1) match { + case TObj(fieldTypes) => + fieldTypes.getOrElse(f, err(TObj(fieldTypes), e1)) + case tgot => err(tgot, e1) + } + case Decl(m, x, e1, e2) => + val t1 = hastype(env, e1) + val newEnv = env + (x -> MTyp(m, t1)) + hastype(newEnv, e2) + + case Fun(xopt, params, tretopt, e1) => { + val env1 = (xopt, tretopt) match { + case (Some(x), Some(tret)) => + env + (x -> MTyp(MConst, TFun(params, tret))) + case (Some(x), None) => errnotype(e1) + case (None, Some(tret)) => env + case (None, None) => errnotype(e1) + } + val env2 = env1 ++ params.map { case (x, MTyp(m, t)) => + x -> MTyp(m, t) + } + val t1 = hastype(env2, e1) + tretopt match { + case Some(tret) if t1 == tret => TFun(params, tret) + case Some(tret) => err(t1, e1) + case None => TFun(params, t1) + } + } + + case Call(e1, args) => + hastype(env, e1) match { + case TFun(params, tret) if params.length == args.length => + (params zip args).foreach { case ((x, MTyp(_, paramType)), ex) => + val argType = hastype(env, ex) + if (paramType != argType) err(paramType, ex) + } + tret + case tgot => err(tgot, e1) + } + + case Assign(e1, e2) => + e1 match { + case Var(x) => + env.get(x) match { + case Some(MTyp(MConst, _)) => + errnotype(e1) + case Some(MTyp(MVar, t1)) => + val t2 = hastype(env, e2) + if (t1 == t2) t2 + else err(t1, e2) + case None => + errnotype(e1) + } + + case Unary(Deref, a @ A(_)) => + val t1 = hastype(env, e1) + val t2 = hastype(env, e2) + if (t1 == t2) t2 + else err(t1, e2) + + case GetField(e1Inner, f) => + hastype(env, e1Inner) match { + case TObj(fields) if fields.contains(f) => + val fieldType = fields(f) + val t2 = hastype(env, e2) + if (fieldType == t2) t2 + else err(fieldType, e2) + case tgot => + err(tgot, e1Inner) + } + + case _ => + errnotype(e1) + } + + /* Should not match: non-source expressions */ + case A(_) | Unary(Deref, _) => + throw new IllegalArgumentException( + "Gremlins: Encountered unexpected expression %s.".format(e) + ) + } + } + + /** * Small-Step Interpreter ** + */ + def substitute(with_e: Expr, x: String, e: Expr): Expr = { + def subst(e: Expr): Expr = e match { + case N(_) | B(_) | Undefined | S(_) => e + case Print(e1) => Print(subst(e1)) + case Unary(uop, e1) => Unary(uop, subst(e1)) + case Binary(bop, e1, e2) => Binary(bop, subst(e1), subst(e2)) + case If(e1, e2, e3) => If(subst(e1), subst(e2), subst(e3)) + case Var(y) => if (y == x) with_e else e + case Decl(d, y, e1, e2) => + if (y == x) Decl(d, y, subst(e1), e2) + else Decl(d, y, subst(e1), subst(e2)) + case Fun(xopt, params, tann, e1) => + if (xopt.contains(x) || params.exists(_._1 == x)) e + else Fun(xopt, params, tann, subst(e1)) + case Call(e1, args) => Call(subst(e1), args.map(subst)) + case Obj(fields) => Obj(fields.map { case (f, e1) => (f, subst(e1)) }) + case GetField(e1, f) => GetField(subst(e1), f) + case A(_) => e + case Assign(e1, e2) => Assign(subst(e1), subst(e2)) + } + subst(e) + } + + /* A small-step transition. */ + def step(e: Expr): DoWith[Mem, Expr] = { + require(!isValue(e), s"stepping on a value: ${e}") + e match { + case Print(v1) if isValue(v1) => + doget map { m => println(pretty(m, v1)); Undefined } + case Unary(Neg, v1) if isValue(v1) => + v1 match { + case N(n) => doreturn(N(-n)) + case _ => throw StuckError(e) + } + case Unary(Not, v1) if isValue(v1) => + v1 match { + case B(n) => doreturn(B(!n)) + case _ => throw StuckError(e) + } + + case Obj(fields) if (fields forall { case (_, vi) => isValue(vi) }) => + memalloc(e) + + case GetField(a @ A(_), f) => + doget map { m => + m.get(a) match { + case Some(Obj(fields)) => fields.getOrElse(f, throw StuckError(e)) + case _ => throw StuckError(e) + } + } + case Binary(Plus, v1, v2) if isValue(v1) && isValue(v2) => + (v1, v2) match { + case (N(n1), N(n2)) => doreturn(N(n1 + n2)) + case (S(s1), S(s2)) => doreturn(S(s1 + s2)) + case _ => throw StuckError(e) + } + + case Binary(Plus, e1, e2) if isValue(e1) => + step(e2) map { e2p => Binary(Plus, e1, e2p) } + + case Binary(Plus, e1, e2) => + step(e1) map { e1p => Binary(Plus, e1p, e2) } + + case Binary(Seq, v1, v2) if (isValue(v1)) => doreturn(v2) + case Binary(And, B(x), v2) => if (x) doreturn(v2) else doreturn(B(false)) + case Binary(Or, B(x), v2) => if (x) doreturn(B(true)) else doreturn(v2) + case Binary(Eq, v1, v2) if (isValue(v1) && isValue(v2)) => + doreturn(B(v1 == v2)) + case Binary(Ne, v1, v2) if (isValue(v1) && isValue(v2)) => + doreturn(B(v1 != v2)) + case Binary(Minus, N(x), N(y)) => doreturn(N(x - y)) + case Binary(Times, N(x), N(y)) => doreturn(N(x * y)) + case Binary(Div, N(x), N(y)) => doreturn(N(x / y)) + case If(B(true), v2, v3) => doreturn(v2) + case If(B(false), v2, v3) => doreturn(v3) + + case Decl(MConst, x, v1, e2) if isValue(v1) => + doreturn(substitute(v1, x, e2)) + case Decl(MVar, x, v1, e2) if isValue(v1) => + memalloc(v1) flatMap { a => + doreturn(substitute(Unary(Deref, a), x, e2)) + } + + case Decl(MRef, x, l1, e2) if isValue(l1) => + doreturn(substitute(l1, x, e2)) + + case Unary(Deref, a @ A(_)) => + doget[Mem] flatMap { m => doreturn(m(a)) } + + case Assign(Unary(Deref, a @ A(_)), v) if isValue(v) => + domodify[Mem] { m => + if (m.contains(a)) { m + (a -> v) } + else throw StuckError(e) + } flatMap { _ => doreturn(v) } + + case Assign(GetField(a @ A(_), f), v) if isValue(v) => + domodify[Mem] { m => + m.get(a) match { + case Some(Obj(fields)) => + val updatedFields = fields + (f -> v) + m + (a -> Obj(updatedFields)) + case _ => throw StuckError(e) + } + } flatMap { _ => doreturn(v) } + + case Call(v @ Fun(xopt, params, _, e), args) => { + val pazip = params zip args + val ep = pazip.foldRight(e) { + case (((x, MTyp(MConst, _)), arg), acc) => + substitute(arg, x, acc) + + case (((x, MTyp(MVar, _)), arg), acc) => + substitute(Unary(Deref, arg), x, acc) + + case (((x, MTyp(MRef, _)), arg), acc) => + substitute(arg, x, acc) + } + DoWith.doreturn(ep) + } + + case Print(e1) => step(e1) map { e1p => Print(e1p) } + case Unary(uop, e1) => step(e1) map { e1p => Unary(uop, e1p) } + case GetField(e1, f) => + step(e1) map { e1p => GetField(e1p, f) } + case Obj(fields) => + val (k, v) = fields.find { case (_, vi) => !isValue(vi) }.get + step(v) map { vp => Obj(fields + (k -> vp)) } + + case Decl(d, x, e1, e2) => + step(e1) map { e1p => Decl(d, x, e1p, e2) } + case Call(e1, args) => + step(e1) map { e1p => Call(e1p, args) } + + case Assign(e1, e2) if !isValue(e1) => + step(e1) map { e1p => Assign(e1p, e2) } + case Assign(e1, e2) if !isValue(e2) => + step(e2) map { e2p => Assign(e1, e2p) } + case Assign(e1, e2) => + step(e1) map { v1 => Assign(v1, e2) } + + /* Everything else is a stuck error. */ + case _ => throw StuckError(e) + } + } + + /** * External Interfaces ** + */ + /** Interface to run your small-step interpreter and print out the steps of + * evaluation if debugging. + */ + def iterateStep(e: Expr): Expr = { + require( + closed(e), + "input Expr to iterateStep is not closed: free variables: %s".format( + freeVars(e) + ) + ) + def loop(e: Expr, n: Int): DoWith[Mem, Expr] = + if (Some(n) == maxSteps) throw TerminationError(e, n) + else if (isValue(e)) doreturn(e) + else { + doget[Mem] flatMap { m => + println("## step %4d:%n## %s%n## %s".format(n, m, e)) + step(e) flatMap { ep => loop(ep, n + 1) } + } + } + val (m, v) = loop(e, 0)(memempty) + println("## result:%n## %s%n## %s".format(m, v)) + v + } + + // Convenience to pass in a jsy expression as a string. + def iterateStep(s: String): Expr = iterateStep(parse(s)) + + /** Interface to run your type checker. */ + def inferType(e: Expr): Typ = { + val t = hastype(Map.empty, e) + println(s"## type ${e} : ${pretty(t)}") + t + } + + // this.debug = true // comment this out or set to false if you don't want print debugging information + this.maxSteps = Some( + 1000 + ) // comment this out or set to None to not bound the number of steps. + this.keepGoing = + true // comment this out if you want to stop at first exception when processing a file + + // Interface for main + def processFile(file: java.io.File): Unit = { + if (debug) { + println("# ============================================================") + println("# File: " + file.getName) + println("# Parsing ...") + } + + val expr = + handle(None: Option[Expr]) { + Some { + jsy.lab5.Parser.parseFile(file) + } + } getOrElse { + return + } + + if (debug) { + println("# ------------------------------------------------------------") + println("# Type checking %s ...".format(expr)) + } + + val welltyped = handle(false) { + val t = inferType(expr) + true + } + if (!welltyped) return + + if (debug) { + println("# ------------------------------------------------------------") + println("# Stepping %s ...".format(expr)) + } + + handle(()) { + val v = iterateStep(expr) + println(pretty(v)) + } + } +} diff --git a/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.sc b/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.sc new file mode 100644 index 0000000..75689b5 --- /dev/null +++ b/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.sc @@ -0,0 +1,47 @@ +/* + * CSCI 3155: Lab 5 Worksheet + * + * This worksheet demonstrates how you could experiment + * interactively with your implementations in Lab5.scala. + */ +import jsy.lab5._ + +// Imports the parse function from Parser +import Parser.{parse,parseFile} + +// Imports the ast nodes +import ast._ + +// Imports all of the functions from Lab5 (your implementations in Lab5.scala) +import Lab5._ + +// Parse code with assignments +parse("var x = 1; x = 2; console.log(x)") +parse("const x = {f: 1}; x.f = 2; console.log(x.f)") + +// Parse code with null +// parse("null") +// parse("<Null>null") +// parse("<{f: number}>null") + +// Parse functions +parse("(x: number) => x") +parse("function (x: var number) { x = 0; return x }") +parse("var y = 1; (function (x: ref number) { x = 0; return x })(y)") +// parse("((x: name number) => 0)(console.log(100))") + +// Aliasing example +val aliasingex = parse(""" + const x = { f: 1 } + const y = x + x.f = 2 + console.log(y.f) +""") +//iterateStep(aliasingex) // uncomment when you are ready to test your step function. + +// Parse the JavaScripty expression in your worksheet +val worksheetJsy = parseFile("src/main/scala/jsy/lab5/Lab5.worksheet.ts") + +// Interpret the JavaScripty expression in your worksheet +//inferType(worksheetJsy) +//iterateStep(worksheetJsy)
\ No newline at end of file diff --git a/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.ts b/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.ts new file mode 100644 index 0000000..3fb3023 --- /dev/null +++ b/lab5/src/main/scala/jsy/lab5/Lab5.worksheet.ts @@ -0,0 +1,12 @@ +/* + * CSCI 3155: Lab 5 TypeScript Worksheet + * + * This worksheet is a place to experiment with TypeScript expressions. + */ + +// New language features in lab 5 are mutable parameters, and call-by-reference, along with objects +// Functional programming-wise, we work with higher-order functions + +const two_int = (a:number, b:number, f:(a:number,b:number)=>number) => f(a,b); +two_int(1,2, (a:number,b:number)=>a*b) + diff --git a/lab5/src/main/scala/jsy/lab5/Parser.scala b/lab5/src/main/scala/jsy/lab5/Parser.scala new file mode 100644 index 0000000..5517b2b --- /dev/null +++ b/lab5/src/main/scala/jsy/lab5/Parser.scala @@ -0,0 +1,359 @@ +/** + * + */ +package jsy.lab5 + +import jsy.lab5.ast._ +import scala.util.parsing.combinator._ +import scala.util.parsing.combinator.lexical.StdLexical +import scala.util.parsing.input.{StreamReader} +import java.io.{InputStreamReader,FileInputStream} +import java.io.InputStream +import java.io.File +import scala.util.parsing.input.Position +import scala.util.parsing.input.NoPosition +import scala.collection.immutable.SortedMap + +trait JSTokens extends token.StdTokens { + case class FloatLiteral(chars: String) extends Token { + override def toString = chars + } +} + +class Lexer extends StdLexical with JSTokens { + override def token: this.Parser[Token] = + decimal ~ opt(exponent) ^^ { + case dec ~ exp => FloatLiteral(List(Some(dec), exp).flatten.mkString) + } | + super.token + + def decimal: this.Parser[String] = + rep1(digit) ~ opt('.' ~ rep(digit)) ^^ { + case ws ~ fs => + List(Some(ws), fs map { mkList }).flatten.flatten.mkString + } + + def exponent: this.Parser[String] = + (accept('e') | accept('E')) ~ opt(accept('+') | accept('-')) ~ rep1(digit) ^^ { + case exp ~ sign ~ digits => + List(Some(List(exp)), sign map { List(_) }, Some(digits)).flatten.flatten.mkString + } +} + +trait TokenParser extends syntactical.StdTokenParsers { + type Tokens <: JSTokens + def floatLit: this.Parser[String] = + elem("float", _.isInstanceOf[lexical.FloatLiteral]) ^^ (_.chars) +} + +trait Parser { self: TokenParser => + /* Helpers */ + def seqExpr(e1: Expr, e2: Expr): Expr = Binary(Seq, e1, e2) + + /* EBNF + * + * prog ::= {stmt} + * stmt ::= block | decl | ; | expr + * block ::= '{' prog '}' + * decl ::= const x = expr + * expr ::= seoeq + * seq ::= cond{,cond} + * cond ::= binary [? cond : cond] + * binary ::= unary{bop(_)unary} + * unary ::= uop unary | term + * term ::= x | n | b | undefined | jsy.print(expr) | (expr) + */ + + sealed abstract class PStmt + case class ExprPStmt(e: Expr) extends PStmt + case class DeclPStmt(d: Expr => Expr) extends PStmt + case object EmpPStmt extends PStmt + + def prog: this.Parser[Expr] = + stmts ^^ (s => s(None)) + + def stmts: this.Parser[Option[Expr] => Expr] = + rep(stmt) ^^ { (stmts: List[PStmt]) => (body: Option[Expr]) => + (stmts foldRight body){ + case (EmpPStmt, eopt) => eopt + case (ExprPStmt(e), None) => Some(e) + case (ExprPStmt(e1), Some(e2)) => Some(seqExpr(e1, e2)) + case (DeclPStmt(d), None) => Some(d(Undefined)) + case (DeclPStmt(d), Some(e)) => Some(d(e)) + } match { + case None => Undefined + case Some(e) => e + } + } + + def stmt: this.Parser[PStmt] = + block ^^ ExprPStmt | + decl ^^ DeclPStmt | + expr ^^ ExprPStmt | + empty_stmt + + def empty_stmt: this.Parser[PStmt] = + ";" ^^ (_ => EmpPStmt) + + def block: this.Parser[Expr] = + "{" ~> prog <~ "}" + + def decl: this.Parser[Expr => Expr] = + (mode ~ ident) ~ withpos("=" ~> expr) ^^ { + case mode ~ x ~ ((pos,e1)) => ((e2: Expr) => Decl(mode, x, e1, e2) setPos pos) + } /*| + ("interface" ~> ident) ~ withpos(record(";", TObj, ty)) ^^ { + case tyvar ~ ((pos,ty)) => ((e: Expr) => InterfaceDecl(tyvar, ty, e) setPos pos) + }*/ + + def mode: this.Parser[Mode] = + "const" ^^ { _ => MConst } | + //"name" ^^ { _ => MName } | + "var" ^^ { _ => MVar } | + "ref" ^^ { _ => MRef } + + def expr: this.Parser[Expr] = + seq + + def seq: this.Parser[Expr] = + noseq ~ withposrep("," ~> noseq) ^^ { + case e0 ~ es => + (es foldRight (None: Option[(Position,Expr)])){ + case ((posi,ei), None) => Some(posi,ei) + case ((posi,ei), Some((pos,e))) => Some(posi, seqExpr(ei,e) setPos pos) + } match { + case None => e0 + case Some((pos,e)) => seqExpr(e0, e) setPos pos + } + } + + def noseq: this.Parser[Expr] = + assign + + def assign: this.Parser[Expr] = + cond ~ opt(withpos(("=" ~> assign))) ^^ { + case e1 ~ None => e1 + case e1 ~ Some((pos,e2)) => Assign(e1, e2) setPos pos + } + + def cond: this.Parser[Expr] = + binary(0) ~ opt(withpos(("?" ~> noseq) ~ (":" ~> noseq))) ^^ { + case e1 ~ None => e1 + case e1 ~ Some((pos, e2 ~ e3)) => If(e1, e2, e3) setPos pos + } + + val binaryOperators: Vector[List[(String, (Expr, Expr) => Expr)]] = { + def createBinaryFunction(op: Bop): (Expr, Expr) => Expr = + { Binary(op, _, _) } + Vector() ++ List( + List("||" -> createBinaryFunction(Or)), + List("&&" -> createBinaryFunction(And)), + List("===" -> createBinaryFunction(Eq), + "!==" -> createBinaryFunction(Ne)), + List("<" -> createBinaryFunction(Lt), + "<=" -> createBinaryFunction(Le), + ">" -> createBinaryFunction(Gt), + ">=" -> createBinaryFunction(Ge)), + List("+" -> createBinaryFunction(Plus), + "-" -> createBinaryFunction(Minus)), + List("*" -> createBinaryFunction(Times), + "/" -> createBinaryFunction(Div)) + ) + } + + def binary(level: Int): this.Parser[Expr] = + if (level >= binaryOperators.length) + unary + else + binary(level + 1) * bop(level) + + def bop(level: Int): this.Parser[(Expr, Expr) => Expr] = { + def doBop(opf: (String, (Expr, Expr) => Expr)): this.Parser[(Expr, Expr) => Expr] = { + val (op, f) = opf + withpos(op) ^^ { case (pos, _) => ((e1, e2) => f(e1, e2) setPos pos) } + } + val bopf0 :: bopfrest = binaryOperators(level) + (bopfrest.foldLeft(doBop(bopf0)))((acc, bopf) => acc | doBop(bopf)) + } + + def unary: this.Parser[Expr] = + positioned(uop ~ unary ^^ { case op ~ e => op(e) }) | + call + + def uop: this.Parser[Expr => Expr] = + "-" ^^ (_ => (e: Expr) => Unary(Neg, e)) | + "!" ^^ (_ => (e: Expr) => Unary(Not, e)) /*| + "<" ~> ty <~ ">" ^^ (t => (e: Expr) => Unary(Cast(t), e))*/ + + def call: this.Parser[Expr] = + term ~ rep(callop | derefop) ^^ { case e0 ~ callderefs => (callderefs.foldLeft(e0)){ case (acc, mk) => mk(acc) } } + + def callop: this.Parser[Expr => Expr] = + withpos("(" ~> repsep(noseq, ",") <~ ")") ^^ { case (pos, args) => (e0 => Call(e0, args) setPos pos) } + + def derefop: this.Parser[Expr => Expr] = + withpos("." ~> ident) ^^ { case (pos,f) => (e0 => GetField(e0, f) setPos pos) } + + def term: this.Parser[Expr] = + positioned( + ident ^^ (s => Var(s)) | + floatLit ^^ (s => N(s.toDouble)) | + stringLit ^^ (s => S(s)) | + "true" ^^ (_ => B(true)) | + "false" ^^ (_ => B(false)) | + "undefined" ^^ (_ => Undefined) | + //"null" ^^ (_ => Null) | + ("console" ~ "." ~ "log") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) | + function | + record(",", Obj, noseq) + ) | + "(" ~> expr <~ ")" | + "{" ~> "{" ~> prog <~ "}" <~ "}" | + failure("atomic expression expected") + + def jsy: this.Parser[Expr] = + "jsy" ~> "." ~> withpos("print") ~ ("(" ~> expr <~ ")") ^^ { + case ((pos, _)) ~ e => Print(e) setPos pos + } + + def function: this.Parser[Expr] = + ("function" ~> opt(ident)) ~ ("(" ~> repsep(colonpair(modety), ",") <~ ")") ~ opt(":" ~> ty) ~ ("{" ~> stmts ~ ret <~ rep(empty_stmt) <~ "}") ^^ { + case f ~ params ~ retty ~ (stmts ~ ret) => + val body = stmts(Some(ret)) + Fun(f, params, retty, body) + } | + ("(" ~> repsep(colonpair(modety), ",") <~ ")") ~ (withpos("=>" ~> noseq)) ^^ { + case params ~ ((pos, body)) => Fun(None, params, None, body) setPos pos + } + + def ret: this.Parser[Expr] = + "return" ~> expr + + def record[A](sep: String, node: SortedMap[String, A] => A, q: => this.Parser[A]): this.Parser[A] = { + lazy val p = q + "{" ~> repsep(colonpair(p), sep) <~ (opt(",") ~ "}") ^^ { flist => + val fmap = flist.foldLeft(SortedMap.empty: SortedMap[String, A]){ + case (fmap, (f, e)) => fmap + (f -> e) + } + node(fmap) + } + } + + def colonpair[A](q: => this.Parser[A]): this.Parser[(String, A)] = { + lazy val p = q + ident ~ (":" ~> p) ^^ { case f ~ e => (f, e) } + } + + def ty: this.Parser[Typ] = + ident ^^ TVar | + "number" ^^ (_ => TNumber) | + "bool" ^^ (_ => TBool) | + "string" ^^ (_ => TString) | + "Undefined" ^^ (_ => TUndefined) | + //"Null" ^^ (_ => TNull) | + record(";", TObj, ty) | + tyfunction | + failure("type expected") + + def tyfunction: this.Parser[Typ] = + ("(" ~> repsep(colonpair(modety), ",") <~ ")") ~ ("=>" ~> ty) ^^ { + case params ~ t2 => TFun(params, t2) + } + + def modety: this.Parser[MTyp] = + mode ~ ty ^^ { case mode ~ ty => MTyp(mode, ty) } | + ty ^^ { case ty => MTyp(MConst, ty) } + + def withpos[T](q: => this.Parser[T]): this.Parser[(Position, T)] = this.Parser { in => + q(in) match { + case Success(t, in1) => Success((in.pos,t), in1) + case ns: NoSuccess => ns + } + } + + def withposrep[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep(withpos(q)) + + def withposrep1[T](q: => this.Parser[T]): this.Parser[List[(Position,T)]] = + rep1(withpos(q)) + + protected var parseSource: String = "<source>" + + def formatErrorMessage(pos: Position, kind: String, msg: String, longString: Boolean = false): String = + if (pos != NoPosition) + if (longString) + "%s\n%s:%s:%s: %s\n%s".format(kind, parseSource, pos.line, pos.column, msg, pos.longString) + else + "%s\n%s:%s:%s: %s".format(kind, parseSource, pos.line, pos.column, msg) + else + "%s\n%s: %s".format(kind, parseSource, msg) + + case class SyntaxError(msg: String, pos: Position) extends Exception { + override def toString = formatErrorMessage(pos, "SyntaxError", msg, true) + } +} + +object Parser extends Parser with TokenParser { + type Tokens = JSTokens + val lexical = new Lexer + + /* Lexer Set Up */ + lexical.reserved ++= List("jsy", "undefined", "true", "false", "print", "console", "log", "const", "function", "return", "number", "bool", "string", "Undefined", "null", "Null", "interface", "var", "name", "ref", "RegExp") + lexical.delimiters ++= List("-", "!", ";", ",", "+", "*", "/", "=", "===", "!==", "<", "<=", ">", ">=", "&&", "||", "(", ")", ".", "{", "}", "?", ":", "=>") + + def parseTokens(tokens: lexical.Scanner): Expr = { + phrase(prog)(tokens) match { + case Success(e, _) => e + case NoSuccess(msg, next) => throw SyntaxError(msg, next.pos) + case Error(msg,next) => throw SyntaxError(msg, next.pos) + case Failure(msg, next) => throw SyntaxError(msg, next.pos) + } + } + + def parseTypTokens(tokens: lexical.Scanner): Typ = { + phrase(ty)(tokens) match { + case Success(t, _) => t + case NoSuccess(msg, next) => throw SyntaxError(msg, next.pos) + case Error(msg,next) => throw SyntaxError(msg, next.pos) + case Failure(msg, next) => throw SyntaxError(msg, next.pos) + } + } + + /*** External Interface ***/ + + def formatErrorMessage(e: Expr, kind: String, msg: String): String = + formatErrorMessage(e.pos, kind, msg) + + def parse(s: String): Expr = { + parseTokens(new lexical.Scanner(s)) + } + + def parseTyp(s: String): Typ = { + parseTypTokens(new lexical.Scanner(s)) + } + + def parse(in: InputStream): Expr = { + val reader = StreamReader(new InputStreamReader(in)) + parseTokens(new lexical.Scanner(reader)) + } + + def parseFile(filename: String): Expr = { + //parseSource = filename + parse(new FileInputStream(filename)) + } + + def parseFile(file: File): Expr = { + //parseSource = file.getName + parse(new FileInputStream(file)) + } + + implicit class StringExpr(s: String) { + val e = parse(s) + def a: Expr = e + } + + implicit class StringTyp(s: String) { + val typ = parseTyp(s) + def t: Typ = typ + } +}
\ No newline at end of file diff --git a/lab5/src/main/scala/jsy/lab5/ast.scala b/lab5/src/main/scala/jsy/lab5/ast.scala new file mode 100644 index 0000000..c5ecb99 --- /dev/null +++ b/lab5/src/main/scala/jsy/lab5/ast.scala @@ -0,0 +1,321 @@ +package jsy.lab5 + +import scala.collection.immutable.SortedMap +import scala.util.parsing.input.Positional +import jsy.util.DoWith +import jsy.util.Visitor + +/** + * @author Bor-Yuh Evan Chang + */ +class ast { + abstract class Expr extends Positional + + /* Variables */ + case class Var(x: String) extends Expr + + /* Declarations */ + case class Decl(m: Mode, x: String, e1: Expr, e2: Expr) extends Expr + + /* Literals and Values*/ + case class N(n: Double) extends Expr + case class B(b: Boolean) extends Expr + case object Undefined extends Expr + case class S(s: String) extends Expr + + /* Unary and Binary Operators */ + case class Unary(uop: Uop, e1: Expr) extends Expr + case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr + + sealed abstract class Uop + + case object Neg extends Uop /* -e1 */ + case object Not extends Uop /* !e1 */ + + sealed abstract class Bop + + case object Plus extends Bop /* e1 + e2 */ + case object Minus extends Bop /* e1 - e2 */ + case object Times extends Bop /* e1 * e2 */ + case object Div extends Bop /* e1 / e2 */ + case object Eq extends Bop /* e1 === e2 */ + case object Ne extends Bop /* e1 !=== e2 */ + case object Lt extends Bop /* e1 < e2 */ + case object Le extends Bop /* e1 <= e2 */ + case object Gt extends Bop /* e1 > e2 */ + case object Ge extends Bop /* e1 >= e2 */ + + case object And extends Bop /* e1 && e2 */ + case object Or extends Bop /* e1 || e2 */ + + case object Seq extends Bop /* , */ + + /* Intraprocedural Control */ + case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr + + /* Functions */ + case class Fun(p: Option[String], params: List[(String,MTyp)], tann: Option[Typ], e1: Expr) extends Expr + case class Call(e1: Expr, args: List[Expr]) extends Expr + + /* I/O */ + case class Print(e1: Expr) extends Expr + + /* Objects */ + case class Obj(fields: SortedMap[String, Expr]) extends Expr + case class GetField(e1: Expr, f: String) extends Expr + + /* Addresses and Mutation */ + case class Assign(e1: Expr, e2: Expr) extends Expr + case class A private[ast] (addr: Int) extends Expr + case object Deref extends Uop /* *e1 */ + + /* Types */ + abstract class Typ + case object TNumber extends Typ + case object TBool extends Typ + case object TString extends Typ + case object TUndefined extends Typ + case class TFun(params: List[(String,MTyp)], tret: Typ) extends Typ { + override def equals(other: Any) = other.isInstanceOf[TFun] && { + other match { + case TFun(oparams, otret) if otret == tret && oparams.length == params.length => + (oparams zip params).forall { case ((_, omt), (_, mt)) => omt == mt } + case _ => false + } + } + } + case class TObj(tfields: SortedMap[String, Typ]) extends Typ + case class TVar(tvar: String) extends Typ + + /* Parameter Modes */ + sealed abstract class Mode + case object MConst extends Mode + case object MVar extends Mode + case object MRef extends Mode + + /* Parameter Types */ + case class MTyp(m: Mode, t: Typ) + + /* Extension: Call-By-Name */ + //case object MName extends Mode + + /* Extension: Casting and Null */ + //case class Cast(t: Typ) extends Uop + //case object Null extends Expr + //case object TNull extends Typ + + /* Extension: Interfaces and Recursive Types */ + //case class InterfaceDecl(tvar: String, t: Typ, e: Expr) extends Expr + //case class TInterface(tvar: String, t: Typ) extends Typ + + /* + * Memory + * + * Note that the memempty and memalloc functions would idiomatically be in + * the companion object to this class, but we do not have a companion object to + * avoid introducing this feature. + */ + class Mem private[ast] (map: Map[A, Expr], nextAddr: Int) { + def apply(key: A): Expr = map(key) + def get(key: A): Option[Expr] = map.get(key) + def +(kv: (A, Expr)): Mem = new Mem(map + kv, nextAddr) + def contains(key: A): Boolean = map.contains(key) + + private[ast] def alloc(v: Expr): (Mem, A) = { + val fresha = A(nextAddr) + (new Mem(map + (fresha -> v), nextAddr + 1), fresha) + } + + override def toString: String = map.toString + } + + def memempty: Mem = new Mem(Map.empty, 1) + def memalloc(k: Expr): DoWith[Mem, A] = DoWith.doget flatMap { m => + val (mp, a) = m.alloc(k) + DoWith.doput(mp) map { _ => a } + } + + /* Define values. */ + def isValue(e: Expr): Boolean = e match { + case N(_) | B(_) | Undefined | S(_) | Fun(_, _, _, _) | A(_) /*| Null*/ => true + case _ => false + } + + def isLValue(e: Expr): Boolean = e match { + case Unary(Deref, A(_)) | GetField(A(_), _) => true + case _ => false + } + + /* + * Pretty-print values. + * + * We do not override the toString method so that the abstract syntax can be printed + * as is. + */ + protected def prettyVal: Visitor[Expr,String] = Visitor(rec => { + case N(n) => n.toString + case B(b) => b.toString + case Undefined => "undefined" + case S(s) => s + case Fun(xopt, _, _, _) => + "[Function%s]".format(xopt match { case None => " (anonymous)" case Some(s) => ": " + s }) + case Obj(fields) => + val pretty_fields = + fields map { + case (f, S(s)) => f + ": '" + s + "'" + case (f, v) => f + ": " + rec(v) + } reduceRightOption { + (s, acc) => s + ",\n " + acc + } + "{ %s }".format(pretty_fields.getOrElse("")) + //case Null => "null" + case A(i) => "0x%x".format(i) + }) + + def pretty(v: Expr): String = prettyVal(v) + + protected def prettyValMem: Visitor[Expr, Mem => String] = prettyVal flatMap { pv => Visitor(rec => { + case a @ A(_) => { m => if (m contains a) rec(m(a))(m) else pv(a) } + case Obj(fields) => { m => + val pretty_fields = + fields map { + case (f, S(s)) => f + ": '" + s + "'" + case (f, v) => f + ": " + rec(v)(m) + } reduceRightOption { + (s, acc) => s + ",\n " + acc + } + "{ %s }".format(pretty_fields.getOrElse("")) + } + case v => { _ => pv(v) } + })} + + def pretty(m: Mem, v: Expr): String = { + require(isValue(v)) + prettyValMem(v)(m) + } + + /* + * Pretty-print types. + * + * We do not override the toString method so that the abstract syntax can be printed + * as is. + */ + protected def prettyTyp: Visitor[Typ,String] = Visitor(rec => { + case TNumber => "number" + case TBool => "bool" + case TString => "string" + case TUndefined => "Undefined" + case TFun(params, tret) => { + val pretty_params = + params map { case (x,mt) => "%s: %s".format(x, pretty(mt)) } reduceRightOption { + (s, acc) => s + ", " + acc + } + "(%s) => %s".format(pretty_params.getOrElse(""), rec(tret)) + } + case TObj(tfields) => + val pretty_fields: Option[String] = + tfields map { case (f,t) => "%s: %s".format(f, rec(t)) } reduceRightOption { + (s, acc) => s + "; " + acc + } + "{ %s }".format(pretty_fields.getOrElse("")) + //case TNull => "Null" + case TVar(tvar) => tvar + //case TInterface(tvar, t1) => "Interface %s %s".format(tvar, rec(t1)) + }) + + def pretty(t: Typ): String = prettyTyp(t) + + + def pretty(mty: MTyp): String = mty match { + case MTyp(MConst, ty) => s"${pretty(ty)}" + case MTyp(mode, ty) => s"${pretty(mode)} ${pretty(ty)}" + } + + def pretty(mode: Mode): String = mode match { + case MConst => "const" + //case MName => "name" + case MVar => "var" + case MRef => "ref" + } + + /* Get the free variables of e. */ + protected def freeVarsVar: Visitor[Expr,Set[Var]] = Visitor(fv => { + case vr@Var(x) => Set(vr) + case Decl(_, x, e1, e2) => fv(e1) | (fv(e2) - Var(x)) + case Fun(p, params, _, e1) => { + val boundvars = (params map { case (x, _) => Var(x) }) ++ (p map Var) + fv(e1) -- boundvars + } + case N(_) | B(_) | Undefined | S(_) /*| Null*/ | A(_) => Set.empty + case Unary(_, e1) => fv(e1) + case Binary(_, e1, e2) => fv(e1) | fv(e2) + case If(e1, e2, e3) => fv(e1) | fv(e2) | fv(e3) + case Call(e1, args) => fv(e1) | args.foldLeft(Set.empty: Set[Var]) { + ((acc: Set[Var], ei) => acc | fv(ei)) + } + case Print(e1) => fv(e1) + case Obj(fields) => fields.foldLeft(Set.empty: Set[Var])({ case (acc, (_, ei)) => acc | fv(ei) }) + case GetField(e1, _) => fv(e1) + case Assign(e1, e2) => fv(e1) | fv(e2) + //case InterfaceDecl(_, _, e1) => fv(e1) + }) + + def freeVars(e: Expr): Set[String] = freeVarsVar(e) map { case Var(x) => x } + + /* Check closed expressions. */ + def closed(e: Expr): Boolean = freeVarsVar(e).isEmpty + + def checkClosed(e: Expr): Unit = { + freeVarsVar(e).headOption.foreach { x => throw new UnboundVariableError(x) } + } + /* Dynamic Type Error. Extends Expr for simplicity. */ + case class DynamicTypeError(e: Expr) extends Expr { + override def toString = Parser.formatErrorMessage(e.pos, "DynamicTypeError", "in evaluating " + e) + } + + /* Null Dereference Error exception. Extends Expr for simplicity. */ + case class NullDereferenceError(e: Expr) extends Expr { + override def toString = Parser.formatErrorMessage(e.pos, "NullDereferenceError", "in evaluating " + e) + } + + /* + * Unbound Variable Error exception. Throw this exception to signal an unbound variable. + */ + case class UnboundVariableError(x: Var) extends Exception { + override def toString = + Parser.formatErrorMessage(x.pos, "UnboundVariableError", "unbound variable %s".format(x.x)) + } + + /* + * Static Type Error exception. Throw this exception to signal a static + * type error. + * + * throw StaticTypeError(tbad, esub, e) + * + */ + case class StaticTypeError(tbad: Typ, esub: Expr, e: Expr) extends Exception { + override def toString = + Parser.formatErrorMessage(esub.pos, "StaticTypeError", "invalid type %s for sub-expression %s in %s".format(pretty(tbad), esub, e)) + } + + /* + * Stuck Error exception. Throw this exception to signal getting + * stuck in evaluation. This exception should not get raised if + * evaluating a well-typed expression. + * + * throw StuckError(e) + * + */ + case class StuckError(e: Expr) extends Exception { + override def toString = Parser.formatErrorMessage(e.pos, "StuckError", "in evaluating " + e) + } + + /* + * Termination Error exception. Throw this exception to signal exceeding maximum number of allowed steps. + */ + case class TerminationError(e: Expr, n: Int) extends Exception { + override def toString = Parser.formatErrorMessage(e.pos, "TerminationError", s"exceeded ${n} steps in evaluating ${e}") + } +} + +object ast extends ast
\ No newline at end of file diff --git a/lab5/src/main/scala/jsy/util/DoWith.scala b/lab5/src/main/scala/jsy/util/DoWith.scala new file mode 100644 index 0000000..08d2e3a --- /dev/null +++ b/lab5/src/main/scala/jsy/util/DoWith.scala @@ -0,0 +1,33 @@ +package jsy.util + +/* + * DoWith is a data structure that holds a function that returns a result of + * type R with a input-output state of type W. + * + * Aside: This is also known as the State monad. + */ +sealed class DoWith[W,+R] private (doer: W => (W,R)) { + def apply(w: W) = doer(w) + + def map[B](f: R => B): DoWith[W,B] = new DoWith[W,B]({ + (w: W) => { + val (wp, r) = doer(w) + (wp, f(r)) + } + }) + + def flatMap[B](f: R => DoWith[W,B]): DoWith[W,B] = new DoWith[W,B]({ + (w: W) => { + val (wp, r) = doer(w) + f(r)(wp) // same as f(a).apply(s) + } + }) +} + +object DoWith { + def doget[W]: DoWith[W, W] = new DoWith[W, W]({ w => (w, w) }) + def doput[W](w: W): DoWith[W, Unit] = new DoWith[W, Unit]({ _ => (w, ()) }) + def doreturn[W, R](r: R): DoWith[W, R] = new DoWith[W, R]({ w => (w, r) }) + def domodify[W](f: W => W): DoWith[W, Unit] = new DoWith[W, Unit]({ w => (f(w), ()) }) +} + diff --git a/lab5/src/main/scala/jsy/util/JsyApplication.scala b/lab5/src/main/scala/jsy/util/JsyApplication.scala new file mode 100644 index 0000000..46b658d --- /dev/null +++ b/lab5/src/main/scala/jsy/util/JsyApplication.scala @@ -0,0 +1,191 @@ +package jsy.util + +import java.io.{ByteArrayOutputStream, File} +import java.nio.file.Files + +trait JsyApplication { + var debug = false /* set to false to disable debugging output */ + var keepGoing = true /* set to true to keep going after exceptions */ + var maxSteps: Option[Int] = None /* set to a number to bound the number of execution steps */ + + /*** Implement this method to process a file. ***/ + def processFile(file: File): Unit + + var anonOption = ("input", + { case filename :: Nil => new File(filename) }: PartialFunction[List[String], File], + "A file containing a JavaScripty program or a directory with .jsy files.") + + var flagOptions = List( + ("debug", options.SetBool(b => debug = b, Some(b => debug == b)), "debugging"), + ("keep-going", options.SetBool(b => keepGoing = b, Some(b => keepGoing == b)), "keep going after exceptions"), + ("bound-steps", options.SetInt( + { i => maxSteps = i }, + Some({ + case true => maxSteps map { i => ": %d".format(i) } + case false => if (maxSteps == None) Some("") else None + })), + "bound for maximum number of execution steps before aborting") + ) + + def handle[T](default: T)(e: => T): T = + if (!keepGoing) e + else try e catch { + case exn: Throwable => println(exn.toString); default + } + + def testJsy(file: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + val jsyext = """[.]jsy$""".r + val ans: File = new File(jsyext.replaceAllIn(file.getPath, ".ans")) + k(file, ans, { + if (!ans.exists()) { + (false, s"Expected output file ${ans} does not exist.") + } + else { + val outstream = new ByteArrayOutputStream() + Console.withOut(outstream)(handle(()){ processFile(file)}) + + val encoding = java.nio.charset.StandardCharsets.UTF_8 + val ansstring = new String(Files.readAllBytes(ans.toPath), encoding) + + outstream.flush() + val outstring = new String(outstream.toString(encoding.toString)) + outstream.close() + + (ansstring == outstring, s"Computed output does not match expected output.\nComputed:\n${outstring}\nExpected:\n${ansstring}") + } + }) + } + + def isJsy(file: File): Boolean = { + val jsyext = """[.]jsy$""".r + jsyext findFirstIn file.getName match { + case Some(_) => true + case None => false + } + } + + def doFile(doit: File => Unit, file: File) = { + def loop(file: File): Unit = { + if (file.isFile) { + doit(file) + } + else if (file.isDirectory) { + file.listFiles filter { f => f.isDirectory || isJsy(f) } foreach loop + } + else { + throw new IllegalArgumentException("File %s does not exist.".format(file)) + } + } + loop(file) + } + + def test(fileordir: File)(k: (File, File, => (Boolean, String)) => Unit): Unit = { + doFile({ f => testJsy(f)(k) }, fileordir) + } + + def main(args: Array[String]): Unit = { + val opts = new options.Options("jsy", flagOptions, anonOption) + val file: File = opts.process(args) + doFile(processFile, file) + } +} + +object options { + sealed abstract class Spec + case class SetBool(setter: Boolean => Unit, default: Option[Boolean => Boolean]) extends Spec + case class SetInt(setter: Option[Int] => Unit, default: Option[Boolean => Option[String]]) extends Spec + + class Options[T](program: String, specs: List[(String, Spec, String)], anon: (String, PartialFunction[List[String], T], String)) { + val opts: Map[String, List[String] => Option[List[String]]] = + specs.foldLeft[Map[String, List[String] => Option[List[String]]]](Map.empty)((acc, spec) => spec match { + case (name, SetBool(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => setter(true); Some(t) }) + + (("--no-" + name) -> { (t: List[String]) => setter(false); Some(t) }) + case (name, SetInt(setter, _), _) => + acc + + (("--" + name) -> { (t: List[String]) => t match { + case arg :: t => + val argp: Int = try arg.toInt catch { case _: Throwable => usageErr() } + setter(Some(argp)); Some(t) + case _ => usageErr() + } }) + + (("--no-" + name) -> { (t: List[String]) => setter(None); Some(t) }) + }) + + val (anonName, anonDo, anonDesc) = anon + + val nameWidth: Int = opts.foldLeft(anonName.length){ case (acc, (n, _)) => acc max (n.length + 5) } + + def padRight(s: String, w: Int): String = { + val nspaces = (w - s.length) max 0 + s + (" " * nspaces) + } + + def optline(name: String, text: String): String = { + "%-2s".format("") + padRight(name, nameWidth) + " %s%n".format(text) + } + + val descriptions: String = { + (specs foldRight "")((spec, acc) => spec match { + case (name, SetBool(_, default), desc) => { + def defaultStr(b: Boolean): String = + default map (f => if (f(b)) " (default)" else "") getOrElse("") + optline("--" + name, "turn on %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "turn off %s".format(desc) + defaultStr(false)) + + acc + } + case (name, SetInt(_, default), desc) => { + def defaultStr(b: Boolean): String = { + val opt = + for { + f <- default + s <- f(b) + } yield " (default%s)".format(s) + opt.getOrElse("") + } + optline("--" + name + " <int>", "set %s".format(desc) + defaultStr(true)) + + optline("--no-" + name, "unset %s".format(desc) + defaultStr(false)) + + acc + } + }) + } + + val header = + """ +Usage: %s [options] %s + +""".format(program, anonName) + +optline(anonName, anonDesc) + """ +Options: +""" + + private var currentArgs: List[String] = List() + + def usageErr(): Nothing = { + val unprocessed = currentArgs match { + case Nil => "" + case _ => """ +Unprocessed Arguments: + """ + currentArgs.reduceRight({ _ + " " + _ }) + "%n".format() + } + print(header + descriptions + unprocessed) + sys.exit(1) + } + + def process(args: Array[String]): T = { + def loop(l: List[String]): List[String] = { + currentArgs = l + l match { + case Nil => Nil + case h :: t => opts.get(h) match { + case None => l + case Some(doit) => { val tp = doit(t).getOrElse(t); loop(tp) } + } + } + } + val err: PartialFunction[List[String], T] = { case _ => usageErr() } + (anonDo orElse err)(loop(args.toList)) + } + } +}
\ No newline at end of file diff --git a/lab5/src/main/scala/jsy/util/Visitor.scala b/lab5/src/main/scala/jsy/util/Visitor.scala new file mode 100644 index 0000000..a74ec70 --- /dev/null +++ b/lab5/src/main/scala/jsy/util/Visitor.scala @@ -0,0 +1,32 @@ +package jsy.util + +object Visitor { + def apply[E,R](visitant: (E => R) => PartialFunction[E,R]) = new Visitor(visitant) + + def visit[E,R](visitant: (E => R) => PartialFunction[E,R])(e: E): R = { + def rec(e: E): R = visitant(rec)(e) + rec(e) + } +} + +/** A visitor of type Visitor[E,R] is an abstraction of a recursive function + * on E of type E => R where E is an algebraic data type that might be extended. + * + * @param visitant + * @tparam E + * @tparam R + */ +class Visitor[E,R] private (val visitant: (E => R) => PartialFunction[E,R]) { + private lazy val rec: E => R = Visitor.visit(visitant) + def apply(e: E) = rec(e) + + def orElse(that: Visitor[E,R]): Visitor[E,R] = orElse(that.visitant) + def orElse(that: (E => R) => PartialFunction[E,R]): Visitor[E,R] = new Visitor( + (v: E => R) => visitant(v) orElse that(v) + ) + + def extendWith(that: Visitor[E,R]): Visitor[E,R] = that orElse this + def extendWith(that: (E => R) => PartialFunction[E,R]) = new Visitor(that).orElse(this) + + def flatMap[B](op: (E => R) => Visitor[E,B]): Visitor[E,B] = op(rec) +} diff --git a/lab5/src/test/resources/lab5/test5001_vardecl.ans b/lab5/src/test/resources/lab5/test5001_vardecl.ans new file mode 100644 index 0000000..ebd107d --- /dev/null +++ b/lab5/src/test/resources/lab5/test5001_vardecl.ans @@ -0,0 +1,11 @@ +## type Decl(MVar,x,N(1.0),Var(x)) : number +## step 0: +## Map() +## Decl(MVar,x,N(1.0),Var(x)) +## step 1: +## Map(A(1) -> N(1.0)) +## Unary(Deref,A(1)) +## result: +## Map(A(1) -> N(1.0)) +## N(1.0) +1.0 diff --git a/lab5/src/test/resources/lab5/test5001_vardecl.jsy b/lab5/src/test/resources/lab5/test5001_vardecl.jsy new file mode 100644 index 0000000..79c3a73 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5001_vardecl.jsy @@ -0,0 +1,2 @@ +var x = 1
+x
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5/test5002_assign.ans b/lab5/src/test/resources/lab5/test5002_assign.ans new file mode 100644 index 0000000..824cbca --- /dev/null +++ b/lab5/src/test/resources/lab5/test5002_assign.ans @@ -0,0 +1,29 @@ +## type Decl(MVar,x,N(2.0),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(2.0))),Decl(MConst,y,Binary(Plus,Var(x),N(2.0)),Undefined))) : Undefined +## step 0: +## Map() +## Decl(MVar,x,N(2.0),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(2.0))),Decl(MConst,y,Binary(Plus,Var(x),N(2.0)),Undefined))) +## step 1: +## Map(A(1) -> N(2.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,Unary(Deref,A(1)),N(2.0))),Decl(MConst,y,Binary(Plus,Unary(Deref,A(1)),N(2.0)),Undefined)) +## step 2: +## Map(A(1) -> N(2.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,N(2.0),N(2.0))),Decl(MConst,y,Binary(Plus,Unary(Deref,A(1)),N(2.0)),Undefined)) +## step 3: +## Map(A(1) -> N(2.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),N(4.0)),Decl(MConst,y,Binary(Plus,Unary(Deref,A(1)),N(2.0)),Undefined)) +## step 4: +## Map(A(1) -> N(4.0)) +## Binary(Seq,N(4.0),Decl(MConst,y,Binary(Plus,Unary(Deref,A(1)),N(2.0)),Undefined)) +## step 5: +## Map(A(1) -> N(4.0)) +## Decl(MConst,y,Binary(Plus,Unary(Deref,A(1)),N(2.0)),Undefined) +## step 6: +## Map(A(1) -> N(4.0)) +## Decl(MConst,y,Binary(Plus,N(4.0),N(2.0)),Undefined) +## step 7: +## Map(A(1) -> N(4.0)) +## Decl(MConst,y,N(6.0),Undefined) +## result: +## Map(A(1) -> N(4.0)) +## Undefined +undefined diff --git a/lab5/src/test/resources/lab5/test5002_assign.jsy b/lab5/src/test/resources/lab5/test5002_assign.jsy new file mode 100644 index 0000000..bd617e7 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5002_assign.jsy @@ -0,0 +1,3 @@ +var x = 2
+x = x + 2
+const y = x + 2
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5/test5015_objalias.ans b/lab5/src/test/resources/lab5/test5015_objalias.ans new file mode 100644 index 0000000..7efc35d --- /dev/null +++ b/lab5/src/test/resources/lab5/test5015_objalias.ans @@ -0,0 +1,51 @@ +## type Decl(MConst,obj,Obj(TreeMap(value -> N(15.0))),Binary(Seq,Print(Var(obj)),Decl(MConst,obj2,Var(obj),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(Var(obj)),Binary(Seq,Print(Var(obj2)),GetField(Var(obj),value)))))))) : number +## step 0: +## Map() +## Decl(MConst,obj,Obj(TreeMap(value -> N(15.0))),Binary(Seq,Print(Var(obj)),Decl(MConst,obj2,Var(obj),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(Var(obj)),Binary(Seq,Print(Var(obj2)),GetField(Var(obj),value)))))))) +## step 1: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Decl(MConst,obj,A(1),Binary(Seq,Print(Var(obj)),Decl(MConst,obj2,Var(obj),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(Var(obj)),Binary(Seq,Print(Var(obj2)),GetField(Var(obj),value)))))))) +## step 2: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Binary(Seq,Print(A(1)),Decl(MConst,obj2,A(1),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(Var(obj2)),GetField(A(1),value))))))) +{ value: 15.0 } +## step 3: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Binary(Seq,Undefined,Decl(MConst,obj2,A(1),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(Var(obj2)),GetField(A(1),value))))))) +## step 4: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Decl(MConst,obj2,A(1),Binary(Seq,Print(Var(obj2)),Binary(Seq,Assign(GetField(Var(obj2),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(Var(obj2)),GetField(A(1),value)))))) +## step 5: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Binary(Seq,Print(A(1)),Binary(Seq,Assign(GetField(A(1),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(A(1)),GetField(A(1),value))))) +{ value: 15.0 } +## step 6: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Binary(Seq,Undefined,Binary(Seq,Assign(GetField(A(1),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(A(1)),GetField(A(1),value))))) +## step 7: +## Map(A(1) -> Obj(TreeMap(value -> N(15.0)))) +## Binary(Seq,Assign(GetField(A(1),value),N(295.0)),Binary(Seq,Print(A(1)),Binary(Seq,Print(A(1)),GetField(A(1),value)))) +## step 8: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## Binary(Seq,N(295.0),Binary(Seq,Print(A(1)),Binary(Seq,Print(A(1)),GetField(A(1),value)))) +## step 9: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## Binary(Seq,Print(A(1)),Binary(Seq,Print(A(1)),GetField(A(1),value))) +{ value: 295.0 } +## step 10: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## Binary(Seq,Undefined,Binary(Seq,Print(A(1)),GetField(A(1),value))) +## step 11: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## Binary(Seq,Print(A(1)),GetField(A(1),value)) +{ value: 295.0 } +## step 12: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## Binary(Seq,Undefined,GetField(A(1),value)) +## step 13: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## GetField(A(1),value) +## result: +## Map(A(1) -> Obj(TreeMap(value -> N(295.0)))) +## N(295.0) +295.0 diff --git a/lab5/src/test/resources/lab5/test5015_objalias.jsy b/lab5/src/test/resources/lab5/test5015_objalias.jsy new file mode 100644 index 0000000..8802136 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5015_objalias.jsy @@ -0,0 +1,8 @@ +const obj = { value: 15 }
+console.log(obj)
+const obj2 = obj
+console.log(obj2)
+obj2.value = 295
+console.log(obj)
+console.log(obj2)
+obj.value
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5/test5040_constassign.ans b/lab5/src/test/resources/lab5/test5040_constassign.ans new file mode 100644 index 0000000..e47fba5 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5040_constassign.ans @@ -0,0 +1,2 @@ +StaticTypeError +<source>:2:1: invalid type Undefined for sub-expression Var(x) in Assign(Var(x),Binary(Plus,Var(x),N(23.0))) diff --git a/lab5/src/test/resources/lab5/test5040_constassign.jsy b/lab5/src/test/resources/lab5/test5040_constassign.jsy new file mode 100644 index 0000000..e32a675 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5040_constassign.jsy @@ -0,0 +1,3 @@ +const x = 0
+x = x + 23
+console.log(x + 45)
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5/test5041_varassign.ans b/lab5/src/test/resources/lab5/test5041_varassign.ans new file mode 100644 index 0000000..a3f3e4f --- /dev/null +++ b/lab5/src/test/resources/lab5/test5041_varassign.ans @@ -0,0 +1,30 @@ +## type Decl(MVar,x,N(0.0),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(23.0))),Print(Binary(Plus,Var(x),N(45.0))))) : Undefined +## step 0: +## Map() +## Decl(MVar,x,N(0.0),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(23.0))),Print(Binary(Plus,Var(x),N(45.0))))) +## step 1: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,Unary(Deref,A(1)),N(23.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(45.0)))) +## step 2: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,N(0.0),N(23.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(45.0)))) +## step 3: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),N(23.0)),Print(Binary(Plus,Unary(Deref,A(1)),N(45.0)))) +## step 4: +## Map(A(1) -> N(23.0)) +## Binary(Seq,N(23.0),Print(Binary(Plus,Unary(Deref,A(1)),N(45.0)))) +## step 5: +## Map(A(1) -> N(23.0)) +## Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))) +## step 6: +## Map(A(1) -> N(23.0)) +## Print(Binary(Plus,N(23.0),N(45.0))) +## step 7: +## Map(A(1) -> N(23.0)) +## Print(N(68.0)) +68.0 +## result: +## Map(A(1) -> N(23.0)) +## Undefined +undefined diff --git a/lab5/src/test/resources/lab5/test5041_varassign.jsy b/lab5/src/test/resources/lab5/test5041_varassign.jsy new file mode 100644 index 0000000..6926019 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5041_varassign.jsy @@ -0,0 +1,3 @@ +var x = 0
+x = x + 23
+console.log(x + 45)
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5/test5042_refassign.ans b/lab5/src/test/resources/lab5/test5042_refassign.ans new file mode 100644 index 0000000..9ba214d --- /dev/null +++ b/lab5/src/test/resources/lab5/test5042_refassign.ans @@ -0,0 +1,46 @@ +## type Decl(MVar,y,N(0.0),Decl(MRef,x,Var(y),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(23.0))),Binary(Seq,Print(Binary(Plus,Var(x),N(45.0))),Print(Binary(Plus,Var(y),N(67.0))))))) : Undefined +## step 0: +## Map() +## Decl(MVar,y,N(0.0),Decl(MRef,x,Var(y),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(23.0))),Binary(Seq,Print(Binary(Plus,Var(x),N(45.0))),Print(Binary(Plus,Var(y),N(67.0))))))) +## step 1: +## Map(A(1) -> N(0.0)) +## Decl(MRef,x,Unary(Deref,A(1)),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(23.0))),Binary(Seq,Print(Binary(Plus,Var(x),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0)))))) +## step 2: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,Unary(Deref,A(1)),N(23.0))),Binary(Seq,Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0))))) +## step 3: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,N(0.0),N(23.0))),Binary(Seq,Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0))))) +## step 4: +## Map(A(1) -> N(0.0)) +## Binary(Seq,Assign(Unary(Deref,A(1)),N(23.0)),Binary(Seq,Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0))))) +## step 5: +## Map(A(1) -> N(23.0)) +## Binary(Seq,N(23.0),Binary(Seq,Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0))))) +## step 6: +## Map(A(1) -> N(23.0)) +## Binary(Seq,Print(Binary(Plus,Unary(Deref,A(1)),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0)))) +## step 7: +## Map(A(1) -> N(23.0)) +## Binary(Seq,Print(Binary(Plus,N(23.0),N(45.0))),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0)))) +## step 8: +## Map(A(1) -> N(23.0)) +## Binary(Seq,Print(N(68.0)),Print(Binary(Plus,Unary(Deref,A(1)),N(67.0)))) +68.0 +## step 9: +## Map(A(1) -> N(23.0)) +## Binary(Seq,Undefined,Print(Binary(Plus,Unary(Deref,A(1)),N(67.0)))) +## step 10: +## Map(A(1) -> N(23.0)) +## Print(Binary(Plus,Unary(Deref,A(1)),N(67.0))) +## step 11: +## Map(A(1) -> N(23.0)) +## Print(Binary(Plus,N(23.0),N(67.0))) +## step 12: +## Map(A(1) -> N(23.0)) +## Print(N(90.0)) +90.0 +## result: +## Map(A(1) -> N(23.0)) +## Undefined +undefined diff --git a/lab5/src/test/resources/lab5/test5042_refassign.jsy b/lab5/src/test/resources/lab5/test5042_refassign.jsy new file mode 100644 index 0000000..bc22619 --- /dev/null +++ b/lab5/src/test/resources/lab5/test5042_refassign.jsy @@ -0,0 +1,5 @@ +var y = 0
+ref x = y
+x = x + 23
+console.log(x + 45)
+console.log(y + 67)
\ No newline at end of file diff --git a/lab5/src/test/resources/lab5xc/test5005_varparamassign.ans b/lab5/src/test/resources/lab5xc/test5005_varparamassign.ans new file mode 100644 index 0000000..d6c1fd2 --- /dev/null +++ b/lab5/src/test/resources/lab5xc/test5005_varparamassign.ans @@ -0,0 +1,56 @@ +## type Decl(MConst,f,Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),Decl(MConst,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Var(f),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z))))))) : Undefined +## step 0: +## Map() +## Decl(MConst,f,Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),Decl(MConst,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Var(f),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z))))))) +## step 1: +## Map() +## Decl(MConst,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z)))))) +## step 2: +## Map() +## Binary(Seq,Print(N(5.0)),Decl(MConst,z,Call(Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),List(N(5.0))),Binary(Seq,Print(N(5.0)),Print(Var(z))))) +5.0 +## step 3: +## Map() +## Binary(Seq,Undefined,Decl(MConst,z,Call(Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),List(N(5.0))),Binary(Seq,Print(N(5.0)),Print(Var(z))))) +## step 4: +## Map() +## Decl(MConst,z,Call(Fun(None,List((x,MTyp(MVar,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),List(N(5.0))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 5: +## Map() +## Decl(MConst,z,Decl(MVar,x,N(5.0),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Binary(Plus,Var(x),N(1.0)))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 6: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 7: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,N(5.0),N(1.0))),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 8: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),N(6.0)),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 9: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,Binary(Seq,N(6.0),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 10: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,Binary(Plus,Unary(Deref,A(1)),N(1.0)),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 11: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,Binary(Plus,N(6.0),N(1.0)),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 12: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,N(7.0),Binary(Seq,Print(N(5.0)),Print(Var(z)))) +## step 13: +## Map(A(1) -> N(6.0)) +## Binary(Seq,Print(N(5.0)),Print(N(7.0))) +5.0 +## step 14: +## Map(A(1) -> N(6.0)) +## Binary(Seq,Undefined,Print(N(7.0))) +## step 15: +## Map(A(1) -> N(6.0)) +## Print(N(7.0)) +7.0 +## result: +## Map(A(1) -> N(6.0)) +## Undefined +undefined diff --git a/lab5/src/test/resources/lab5xc/test5005_varparamassign.jsy b/lab5/src/test/resources/lab5xc/test5005_varparamassign.jsy new file mode 100644 index 0000000..497e58d --- /dev/null +++ b/lab5/src/test/resources/lab5xc/test5005_varparamassign.jsy @@ -0,0 +1,7 @@ +const f = function(x: var number): number { x = x + 1; return x + 1 }
+
+const y = 5
+console.log(y)
+const z = f(y)
+console.log(y)
+console.log(z)
diff --git a/lab5/src/test/resources/lab5xc/test5008_refparamassign.ans b/lab5/src/test/resources/lab5xc/test5008_refparamassign.ans new file mode 100644 index 0000000..3f9aefe --- /dev/null +++ b/lab5/src/test/resources/lab5xc/test5008_refparamassign.ans @@ -0,0 +1,59 @@ +## type Decl(MConst,f,Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),Decl(MVar,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Var(f),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z))))))) : Undefined +## step 0: +## Map() +## Decl(MConst,f,Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),Decl(MVar,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Var(f),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z))))))) +## step 1: +## Map() +## Decl(MVar,y,N(5.0),Binary(Seq,Print(Var(y)),Decl(MConst,z,Call(Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),List(Var(y))),Binary(Seq,Print(Var(y)),Print(Var(z)))))) +## step 2: +## Map(A(1) -> N(5.0)) +## Binary(Seq,Print(Unary(Deref,A(1))),Decl(MConst,z,Call(Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),List(Unary(Deref,A(1)))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z))))) +## step 3: +## Map(A(1) -> N(5.0)) +## Binary(Seq,Print(N(5.0)),Decl(MConst,z,Call(Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),List(Unary(Deref,A(1)))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z))))) +5.0 +## step 4: +## Map(A(1) -> N(5.0)) +## Binary(Seq,Undefined,Decl(MConst,z,Call(Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),List(Unary(Deref,A(1)))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z))))) +## step 5: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Call(Fun(None,List((x,MTyp(MRef,TNumber))),Some(TNumber),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),List(Unary(Deref,A(1)))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 6: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Decl(MRef,x,Unary(Deref,A(1)),Binary(Seq,Assign(Var(x),Binary(Plus,Var(x),N(1.0))),Var(x))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 7: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,Unary(Deref,A(1)),N(1.0))),Unary(Deref,A(1))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 8: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),Binary(Plus,N(5.0),N(1.0))),Unary(Deref,A(1))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 9: +## Map(A(1) -> N(5.0)) +## Decl(MConst,z,Binary(Seq,Assign(Unary(Deref,A(1)),N(6.0)),Unary(Deref,A(1))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 10: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,Binary(Seq,N(6.0),Unary(Deref,A(1))),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 11: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,Unary(Deref,A(1)),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 12: +## Map(A(1) -> N(6.0)) +## Decl(MConst,z,N(6.0),Binary(Seq,Print(Unary(Deref,A(1))),Print(Var(z)))) +## step 13: +## Map(A(1) -> N(6.0)) +## Binary(Seq,Print(Unary(Deref,A(1))),Print(N(6.0))) +## step 14: +## Map(A(1) -> N(6.0)) +## Binary(Seq,Print(N(6.0)),Print(N(6.0))) +6.0 +## step 15: +## Map(A(1) -> N(6.0)) +## Binary(Seq,Undefined,Print(N(6.0))) +## step 16: +## Map(A(1) -> N(6.0)) +## Print(N(6.0)) +6.0 +## result: +## Map(A(1) -> N(6.0)) +## Undefined +undefined diff --git a/lab5/src/test/resources/lab5xc/test5008_refparamassign.jsy b/lab5/src/test/resources/lab5xc/test5008_refparamassign.jsy new file mode 100644 index 0000000..70c39cd --- /dev/null +++ b/lab5/src/test/resources/lab5xc/test5008_refparamassign.jsy @@ -0,0 +1,7 @@ +const f = function(x: ref number): number { x = x + 1; return x }
+
+var y = 5
+console.log(y)
+const z = f(y)
+console.log(y)
+console.log(z)
diff --git a/lab5/src/test/scala/jsy/lab5/Lab5Spec.scala b/lab5/src/test/scala/jsy/lab5/Lab5Spec.scala new file mode 100644 index 0000000..2b42cb7 --- /dev/null +++ b/lab5/src/test/scala/jsy/lab5/Lab5Spec.scala @@ -0,0 +1,128 @@ +package jsy.lab5 + +import scala.collection.immutable.SortedMap +import jsy.lab5.ast._ +import jsy.lab5.Parser.parse +import jsy.tester.JavascriptyTester +import jsy.util.DoWith +import jsy.util.DoWith._ +import org.scalatest._ +import flatspec._ +import Lab5._ +import java.{util => ju} + +class Lab5StudentSpec extends AnyFlatSpec { +} + +class Lab5Spec extends AnyFlatSpec { + + "DoNeg" should "return the negation of a number value" in { + val e1 = N(5) + val e2 = Unary(Neg, e1) + assertResult( N(-5) ) { + val (_, r) = step(e2)(memempty) + r + } + } + + "DoPlus" should "Perform addition of two numbers" in { + val e1 = N(1) + val e2 = N(2) + val e = Binary(Plus, e1, e2) + assertResult( N(3) ) { + val (_, r) = step(e)(memempty) + r + } + } + + "Decl" should "Evaluate Decl" in { + val e1 = Binary(Plus, N(1), N(3)) + val e2 = Var("x") + val e = Decl(MVar, "x", Binary(Plus, e1, N(1)), e2) + val ep = Decl(MVar, "x", Binary(Plus, N(4), N(1)), e2) + assertResult( ep ) { + val (_, r) = step(e)(memempty) + r + } + } + + "DoDeref" should "Deref a Reference" in { + val e = Unary(Deref, A(1)) + assertResult(N(1)) { + val (_, r) = step(e)(memempty + (A(1) -> N(1))) + r + } + } + + "TypeofNeg" should "Return type TNumber" in { + val e1 = Binary(Plus, N(1), N(2)) + val e = Unary(Neg, e1) + assertResult(TNumber) { + hastype(Map.empty, e) + } + } + + "TypeofAnd" should "Return type TBool" in { + val e1 = B(false) + val e2 = Unary(Not, e1) + val e = Binary(And, e1, e2) + assertResult(TBool) { + hastype(Map.empty, e) + } + } + + "TypeofAssign" should "Return type TNumber" in { + val mp = Map("x" -> new MTyp(MVar, TNumber)) + val e1 = Binary(Plus, N(1), N(2)) + val e = Assign(Var("x"), e1) + assertResult(TNumber) { + hastype(mp, e) + } + } + + // "mapFirstDoWith" should "map the first element where f returns Some" in { + // val l1 = List(1, 2, -3, 4, -5) + // val gold1 = List(1, 2, 3, 4, -5) + // def dowith[W]: DoWith[W,List[Int]] = mapFirstWith(l1) { (i: Int) => if (i < 0) Some(doreturn(-i)) else None } + // assertResult((true,gold1)) { dowith(true) } + // assertResult((42,gold1)) { dowith(42) } + // } + + // "mapWith(List)" should "map the elements of a list in a DoWith" in { + // val l = List(1, 2, 3, 4, 5) + // val r1 = l.map { i => i + 1 } + + // def dowith1[W]: DoWith[W,List[Int]] = mapWith(l) { i: Int => doreturn(i + 1) } + // assertResult((true,r1)) { dowith1(true) } + // assertResult((42,r1)) { dowith1(42) } + + // assertResult((2 * l.length + 1, r1)) { + // val dw: DoWith[Int,List[Int]] = mapWith(l) { i: Int => + // domodify[Int](s => s + 2) map { _ => i + 1 } + // } + // dw(1) + // } + // } + + // "rename" should "rename in a DoWith" in { + // val e1 = parse("const a = 1 + a; a") + // val e1p = parse("const aa = 1 + a; aa") + + // assertResult((1,e1p)) { + // rename(empty, e1){ x => domodify[Int](n => n + 1) map { _ => x + x } }(0) + // } + // } + + // "CastOkNull" should "perform CastOkNull" in { + // assertResult(true) { + // castOk(TNull, TObj(SortedMap.empty)) + // } + // } + +} + + +// The next bit of code runs a test for each .jsy file in src/test/resources/lab5. +// The test expects a corresponding .ans file with the expected result. +class Lab5JsyTests extends JavascriptyTester(None, "lab5", Lab5) +class Lab5XCJsyTests extends JavascriptyTester(None, "lab5xc", Lab5)
\ No newline at end of file diff --git a/lab5/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab5/src/test/scala/jsy/tester/JavascriptyTester.scala new file mode 100644 index 0000000..48e789c --- /dev/null +++ b/lab5/src/test/scala/jsy/tester/JavascriptyTester.scala @@ -0,0 +1,23 @@ +package jsy.tester +import java.io.File +import jsy.util.JsyApplication +import org.scalatest._ +import flatspec._ + +/* + * A ScalaTest interface for running system tests. + */ +class JavascriptyTester(rootPrefix: Option[String], testDirectory: String, jsy: JsyApplication) extends AnyFlatSpec { + val testResources = s"src${File.separator}test${File.separator}resources" + val testPrefix = rootPrefix match { + case None => testResources + case Some(p) => s"${p}${File.separator}${testResources}" + } + val testPath = s"${testPrefix}${File.separator}${testDirectory}" + jsy.test(new File(testPath)) { case (in,ans,assertion) => + s"eval on ${in}" should s"match ${ans}" in { + val (b: Boolean, msg: String) = assertion + assert(b, msg) + } + } +} |