aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:03:45 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:03:45 -0700
commit8bb81e391405554d02ec36574db2ca58300c89c4 (patch)
tree2e6e16ea68cefc63466b4cc3a56352843ec6a92c
parentae554ab7d4d425fa821c1167e734db3425a881f6 (diff)
downloadcsci3155-8bb81e391405554d02ec36574db2ca58300c89c4.tar.gz
csci3155-8bb81e391405554d02ec36574db2ca58300c89c4.zip
Unit 5
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--encapsulating-effects-exercise.ipynb2715
-rw-r--r--lab5/build.sbt48
-rw-r--r--lab5/imperative-computation-lab.ipynb1522
-rw-r--r--lab5/project/build.properties1
-rw-r--r--lab5/src/main/scala/jsy/lab5/Lab5.scala410
-rw-r--r--lab5/src/main/scala/jsy/lab5/Lab5.worksheet.sc47
-rw-r--r--lab5/src/main/scala/jsy/lab5/Lab5.worksheet.ts12
-rw-r--r--lab5/src/main/scala/jsy/lab5/Parser.scala359
-rw-r--r--lab5/src/main/scala/jsy/lab5/ast.scala321
-rw-r--r--lab5/src/main/scala/jsy/util/DoWith.scala33
-rw-r--r--lab5/src/main/scala/jsy/util/JsyApplication.scala191
-rw-r--r--lab5/src/main/scala/jsy/util/Visitor.scala32
-rw-r--r--lab5/src/test/resources/lab5/test5001_vardecl.ans11
-rw-r--r--lab5/src/test/resources/lab5/test5001_vardecl.jsy2
-rw-r--r--lab5/src/test/resources/lab5/test5002_assign.ans29
-rw-r--r--lab5/src/test/resources/lab5/test5002_assign.jsy3
-rw-r--r--lab5/src/test/resources/lab5/test5015_objalias.ans51
-rw-r--r--lab5/src/test/resources/lab5/test5015_objalias.jsy8
-rw-r--r--lab5/src/test/resources/lab5/test5040_constassign.ans2
-rw-r--r--lab5/src/test/resources/lab5/test5040_constassign.jsy3
-rw-r--r--lab5/src/test/resources/lab5/test5041_varassign.ans30
-rw-r--r--lab5/src/test/resources/lab5/test5041_varassign.jsy3
-rw-r--r--lab5/src/test/resources/lab5/test5042_refassign.ans46
-rw-r--r--lab5/src/test/resources/lab5/test5042_refassign.jsy5
-rw-r--r--lab5/src/test/resources/lab5xc/test5005_varparamassign.ans56
-rw-r--r--lab5/src/test/resources/lab5xc/test5005_varparamassign.jsy7
-rw-r--r--lab5/src/test/resources/lab5xc/test5008_refparamassign.ans59
-rw-r--r--lab5/src/test/resources/lab5xc/test5008_refparamassign.jsy7
-rw-r--r--lab5/src/test/scala/jsy/lab5/Lab5Spec.scala128
-rw-r--r--lab5/src/test/scala/jsy/tester/JavascriptyTester.scala23
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)
+ }
+ }
+}