diff options
Diffstat (limited to 'lab5')
29 files changed, 3449 insertions, 0 deletions
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) + } + } +} |