aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:03:17 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:03:17 -0700
commitae554ab7d4d425fa821c1167e734db3425a881f6 (patch)
tree0962144c05070d5cf4303133c8e5ccd756d4cee9
parent08f9cae13d0dce99d40a6d93432a84cb075bebfc (diff)
downloadcsci3155-ae554ab7d4d425fa821c1167e734db3425a881f6.tar.gz
csci3155-ae554ab7d4d425fa821c1167e734db3425a881f6.zip
Unit 4
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--higher-order-functions-exercise.ipynb1576
-rw-r--r--lab4/build.sbt46
-rw-r--r--lab4/project/build.properties1
-rw-r--r--lab4/src/main/scala/jsy/lab4/Lab4.scala362
-rw-r--r--lab4/src/main/scala/jsy/lab4/Lab4.worksheet.sc39
-rw-r--r--lab4/src/main/scala/jsy/lab4/Lab4.worksheet.ts35
-rw-r--r--lab4/src/main/scala/jsy/lab4/Parser.scala437
-rw-r--r--lab4/src/main/scala/jsy/lab4/ast.scala240
-rw-r--r--lab4/src/main/scala/jsy/util/JsyApplication.scala191
-rw-r--r--lab4/src/test/resources/lab4/test4001_id.ans4
-rw-r--r--lab4/src/test/resources/lab4/test4001_id.jsy1
-rw-r--r--lab4/src/test/resources/lab4/test4002_multiparamfun.ans6
-rw-r--r--lab4/src/test/resources/lab4/test4002_multiparamfun.jsy1
-rw-r--r--lab4/src/test/resources/lab4/test4007_objliteral.ans4
-rw-r--r--lab4/src/test/resources/lab4/test4007_objliteral.jsy1
-rw-r--r--lab4/src/test/resources/lab4/test4010_deref.ans4
-rw-r--r--lab4/src/test/resources/lab4/test4010_deref.jsy1
-rw-r--r--lab4/src/test/resources/lab4/test4029_simplerec.ans11
-rw-r--r--lab4/src/test/resources/lab4/test4029_simplerec.jsy2
-rw-r--r--lab4/src/test/scala/jsy/lab4/Lab4Spec.scala217
-rw-r--r--lab4/src/test/scala/jsy/tester/JavascriptyTester.scala23
-rw-r--r--lab4/static-type-checking-lab.ipynb1106
22 files changed, 4308 insertions, 0 deletions
diff --git a/higher-order-functions-exercise.ipynb b/higher-order-functions-exercise.ipynb
new file mode 100644
index 0000000..454095c
--- /dev/null
+++ b/higher-order-functions-exercise.ipynb
@@ -0,0 +1,1576 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "c6d055b3",
+ "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": 51,
+ "id": "7d37a207",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n",
+ "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m"
+ ]
+ },
+ "execution_count": 51,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val NAME = \"Jack Sangdahl\"\n",
+ "val COLLABORATORS = \"N/A\""
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d2cb60f5",
+ "metadata": {},
+ "source": [
+ "---"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7e183df6-99f9-4b1a-9801-d9c76f2b1ae8",
+ "metadata": {},
+ "source": [
+ "# Exercise: Higher-Order Functions\n",
+ "\n",
+ "<!-- 3 Expressions -->\n",
+ "\n",
+ "<!-- 4 Binding and Scope -->\n",
+ "\n",
+ "<!-- 8 Recursion -->\n",
+ "\n",
+ "<!-- 9 Inductive Data Types -->\n",
+ "\n",
+ "<!-- 11 Concrete Syntax -->\n",
+ "\n",
+ "<!-- 12 Abstract Syntax and Parsing -->\n",
+ "\n",
+ "<!-- 13 Exercise: Syntax -->\n",
+ "\n",
+ "<!-- 14 Static Scoping -->\n",
+ "\n",
+ "<!-- 15 Judgments -->\n",
+ "\n",
+ "<!-- 16 Variables, Basic Values, and Judgments Lab -->\n",
+ "\n",
+ "<!-- 18 Operational Semantics -->\n",
+ "\n",
+ "<!-- 19 Functions and Dynamic Scoping -->\n",
+ "\n",
+ "<!-- 20 Big-Step Exercise -->\n",
+ "\n",
+ "<!-- 21 Evaluation Order -->\n",
+ "\n",
+ "### Learning Goals\n",
+ "\n",
+ "The primary learning goal of this exercise is to get experience\n",
+ "programming with higher-order functions.\n",
+ "\n",
+ "### Instructions\n",
+ "\n",
+ "This assignment asks you to write Scala code. There are restrictions\n",
+ "associated with how you can solve these problems. Please pay careful\n",
+ "heed to those. If you are unsure, ask the course staff.\n",
+ "\n",
+ "Note that `???` indicates that there is a missing function or code\n",
+ "fragment that needs to be filled in. Make sure that you remove the `???`\n",
+ "and replace it with the answer.\n",
+ "\n",
+ "Use the test cases provided to test your implementations. You are also\n",
+ "encouraged to write your own test cases to help debug your work.\n",
+ "However, please delete any extra cells you may have created lest they\n",
+ "break an autograder.\n",
+ "\n",
+ "### Imports"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "id": "7047114a",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "afc1ca0eb6ddf4e8f942a9b59b4d2e8e",
+ "grade": false,
+ "grade_id": "testing",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[32mimport \u001b[39m\u001b[36mRun this cell FIRST before testing.\n",
+ "import $ivy.$ , org.scalatest._, events._, flatspec._\n",
+ "\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mpassed\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
+ ]
+ },
+ "execution_count": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// Run this cell FIRST before testing.\n",
+ "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n",
+ "def report(suite: Suite): Unit = suite.execute(stats = true)\n",
+ "def assertPassed(suite: Suite): Unit =\n",
+ " suite.run(None, Args(new Reporter {\n",
+ " def apply(e: Event) = e match {\n",
+ " case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n",
+ " case _ => ()\n",
+ " }\n",
+ " }))\n",
+ "def passed(points: Int): Unit = {\n",
+ " require(points >=0)\n",
+ " if (points == 1) println(\"*** šŸŽ‰ Tests Passed (1 point) ***\")\n",
+ " else println(s\"*** šŸŽ‰ Tests Passed ($points points) ***\")\n",
+ "}\n",
+ "def test(suite: Suite, points: Int): Unit = {\n",
+ " report(suite)\n",
+ " assertPassed(suite)\n",
+ " passed(points)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6b6ea94a-7824-4ed5-9614-534a797b0cb0",
+ "metadata": {},
+ "source": [
+ "## Collections\n",
+ "\n",
+ "When working with and organizing data, we primarily use collections from\n",
+ "Scalaā€™s standard library. One of the most fundamental operations that\n",
+ "one needs to perform with a collection is to iterate over the elements.\n",
+ "Like many other languages with first-class functions (e.g., Python, ML),\n",
+ "the Scala library provides various iteration operations via\n",
+ "*higher-order functions*. Higher-order functions are functions that take\n",
+ "functions as parameters. The function parameters are often called\n",
+ "*callbacks*, and for collections, they typically specify what the\n",
+ "library client wants to do for each element. We have seen examples of\n",
+ "these functions in class. In the following questions, we practice both\n",
+ "writing such higher-order functions in a library and using them as a\n",
+ "client.\n",
+ "\n",
+ "### Lists\n",
+ "\n",
+ "First, we will implement functions that eliminate consecutive duplicates\n",
+ "of list elements. If a list contains repeated elements they should be\n",
+ "replaced with a single copy of the element. The order of the elements\n",
+ "should not be changed. For example, the following\n",
+ "`List(1, 2, 2, 3, 3, 3)` should be converted to `List(1,2,3)`.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 1 (5 points)**</span> Write a\n",
+ "function `compressRec` that implements this behavior. Implement the\n",
+ "function by direct recursion (e.g., pattern match on `l` and call\n",
+ "`compressRec` recursively). Do not call any `List` library methods.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 53,
+ "id": "ccffe3bf",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "92e68b3abc6873aeb3256c3a889785b9",
+ "grade": false,
+ "grade_id": "compress-rec-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mcompressRec\u001b[39m"
+ ]
+ },
+ "execution_count": 53,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def compressRec[A](l: List[A]): List[A] = l match {\n",
+ " case Nil | _ :: Nil => l\n",
+ " case h1 :: (t1 @ (h2 :: _)) => \n",
+ " if (h1 == h2) compressRec(t1)\n",
+ " else h1:: compressRec(t1)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "94a281c0-ccd2-4fb8-9daa-53a6e4e1dc9e",
+ "metadata": {},
+ "source": [
+ "#### Notes\n",
+ "\n",
+ "- This exercise is from [Ninety-Nine Scala\n",
+ " Problems](http://aperiodic.net/phil/scala/s-99/). Some sample\n",
+ " solutions are given there, which you are welcome to view. However,\n",
+ " we *strongly* recommend you attempt this exercise before looking\n",
+ " there. The purpose of the exercise is to get some practice for the\n",
+ " later part of this homework. Note that the solutions there do not\n",
+ " satisfy the requirements here, as they use library functions. If at\n",
+ " some point you feel like you need more practice with collections,\n",
+ " this site is a good resource.\n",
+ "\n",
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "id": "24666dbc",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "37105b713cdf2fd778ba04c25e81034b",
+ "grade": true,
+ "grade_id": "eval-compress-rec-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd54$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mcompressRec\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val l1 = List(1, 2, 2, 3, 3, 3)\n",
+ " val r1 = List(1, 2, 3)\n",
+ "\n",
+ " \"compressRec\" should \"Test Case 1\" in { assertResult( r1 ) { compressRec(l1) } }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a33fc3ee-b0ce-496f-acfb-960b0a2dc115",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 2 (5 points)**</span> Write a\n",
+ "different function `compressFold` that re-implements the behavior of\n",
+ "`compressRec` using the `foldRight` method from the `List` library. The\n",
+ "call to `foldRight` has been provided for you. Do not call\n",
+ "`compressFold` recursively or any other `List` library methods.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 55,
+ "id": "cfb2b5e2",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "3c8e6b1a366ae91df01dc1de5be522b2",
+ "grade": false,
+ "grade_id": "compress-fold-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mcompressFold\u001b[39m"
+ ]
+ },
+ "execution_count": 55,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def compressFold[A](l: List[A]): List[A] = l.foldRight(Nil: List[A]){ (h, acc) => \n",
+ " acc match {\n",
+ " case Nil => h :: Nil\n",
+ " case x :: _ =>\n",
+ " if (h != x) h :: acc\n",
+ " else acc\n",
+ " }\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "c0365e1b-8f3f-4069-96e0-e486d2a4ec01",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 56,
+ "id": "4b823624",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "1cc99e752a01d9179e59e4d37c41c8ee",
+ "grade": true,
+ "grade_id": "eval-compress-fold-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd56$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mcompressFold\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val l1 = List(1, 2, 2, 3, 3, 3)\n",
+ " val r1 = List(1, 2, 3)\n",
+ "\n",
+ " \"compressFold\" should \"Test Case 1\" in { assertResult( r1 ) { compressFold(l1) } }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "c11a6086-6902-40e5-8395-c4c604fb3675",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 3 (5 points)**</span> Explain in\n",
+ "1ā€“2 sentences the similarities and differences between your two\n",
+ "implementations: `compressRec` and `compressFold`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d056d0b1-eac0-4df7-a5a7-230719f41328",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "b62196190ebfcba2945446be01a232b6",
+ "grade": true,
+ "grade_id": "explain-compress",
+ "locked": false,
+ "points": 5,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "In terms of similarities, these functions both remove consecutive duplicates from a list. `compressRec` uses direct recursion to iterate through the list and construct the result, whereas `compressFold` uses a higher-order function `foldRight` to accumulate the result without explicit recursion."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7e27db0c-4a97-435c-b53e-c780ae1e1753",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 4 (5 points)**</span> Implement a\n",
+ "higher-order recursive function `mapFirst` that finds the first element\n",
+ "of `l: List[A]` where `f: A => Option[A]` applied to it returns\n",
+ "`Some(a)` for some value `a`. The function should replace that element\n",
+ "with `a` and leave `l` the same everywhere else. For example,\n",
+ "\n",
+ "``` scala\n",
+ "mapFirst(List(1,2,-3,4,-5)) { i => if (i < 0) Some(-i) else None } \n",
+ "```\n",
+ "\n",
+ "should result in `List[Int] = List(1, 2, 3, 4, -5)`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 57,
+ "id": "4490826a",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "c5bfc2453712c057957b0644045ede51",
+ "grade": false,
+ "grade_id": "map-first-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mmapFirst\u001b[39m"
+ ]
+ },
+ "execution_count": 57,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def mapFirst[A](l: List[A])(f: A => Option[A]): List[A] = l match {\n",
+ " case Nil => Nil\n",
+ " case h :: t => \n",
+ " f(h) match {\n",
+ " case None => h :: mapFirst(t)(f)\n",
+ " case Some(a) => a :: t\n",
+ " }\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "29a2b79b-d276-475e-a560-1a1330a16fd2",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 58,
+ "id": "e5973775",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "ae49d2319356b384b728df4baa3e61a2",
+ "grade": true,
+ "grade_id": "eval-map-first-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd58$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mmapFirst\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val l1 = List(1, 2, -3, 4, -5)\n",
+ " val r1 = List(1, 2, 3, 4, -5)\n",
+ "\n",
+ " \"mapFirst\" should \"Test Case 1\" in { \n",
+ " assertResult(r1) {\n",
+ " mapFirst(l1) { (i: Int) => if (i < 0) Some(-i) else None }\n",
+ " }\n",
+ " }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d3abe7ce-8cd8-47f4-a2c2-768c5c5fc69a",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 5 (5 points)**</span> Write a\n",
+ "function `composeMap` that sequentially applies a list of functions of\n",
+ "type `A => A` to all the elements of a `List[A]`. For example, if we\n",
+ "have a list of functions `List(f1, f2, f3)`, and a list `List(a, b)`, we\n",
+ "want to output `List(f3(f2(f1(a))), f3(f2(f1(b))))`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 59,
+ "id": "9afd3378",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "abeb90b3fb6318d3968957d5c4597d1f",
+ "grade": false,
+ "grade_id": "compose-map-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mcomposeMap\u001b[39m"
+ ]
+ },
+ "execution_count": 59,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def composeMap[A](functions: List[A => A])(l: List[A]): List[A] = {\n",
+ " l.map(h => functions.foldRight(h)( (f, e) => f(e)))\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "c5608fc2-a6dc-40d2-a530-13f0185e2286",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 60,
+ "id": "2fafb0b4",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "9adaca1df7b9f28b5ceba4853b61495e",
+ "grade": true,
+ "grade_id": "eval-compose-map-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd60$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mcomposeMap\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " def plusOne(x: Int): Int = x + 1\n",
+ " def square(x: Int): Int = x * x\n",
+ " def timesThree(x: Int): Int = x * 3\n",
+ "\n",
+ " val l1 = List(1, 2, 3)\n",
+ " val r1 = List(10, 37, 82)\n",
+ " val fs: List[Int => Int] = List(plusOne, square, timesThree)\n",
+ "\n",
+ " \"composeMap\" should \"Test Case 1\" in { assertResult(r1) { composeMap(fs)(l1) } }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "f799539c-e013-4c36-8f76-d5f9c2ac3358",
+ "metadata": {},
+ "source": [
+ "### Maps\n",
+ "\n",
+ "Recall the `Map[A, B]` data structure from class. Also, recall the\n",
+ "higher-order function `map`. To avoid confusion we will use the upper\n",
+ "case `Map` to refer to the type, and the lowercase `map` to refer to the\n",
+ "higher-order function.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 6 (5 points)**</span> Implement a\n",
+ "function `mapValues` that takes a `Map[A,B]` and a callback function\n",
+ "`f: B => C`, that applies `f` to all the values in the `Map`. Your\n",
+ "function should use the Scala collections `map` method. Do not use the\n",
+ "standard library method `mapValues` on `Map` (however, note that the\n",
+ "behavior of your function should be exactly the same as the `mapValues`\n",
+ "standard library method).\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 61,
+ "id": "1f6f4c15",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "943db2a02802c5f62c4a25aefb2e0fab",
+ "grade": false,
+ "grade_id": "update-map-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mmapValues\u001b[39m"
+ ]
+ },
+ "execution_count": 61,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def mapValues[A, B, C](m: Map[A, B])(f: B => C): Map[A, C] = m.map {\n",
+ " case (key, value) => key -> f(value)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "1d23b72e-12ed-4e87-8cc3-9f894517e08a",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 62,
+ "id": "6fbeb162",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "a4caabf134684fad42f83e85812648f4",
+ "grade": true,
+ "grade_id": "eval-update-map-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd62$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mmapValues\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val m1 = Map(\"a\" -> 1, \"b\" -> 2, \"c\" -> 3)\n",
+ " val r1 = Map(\"a\" -> 1, \"b\" -> 4, \"c\" -> 9)\n",
+ "\n",
+ " \"mapValues\" should \"Test Case 1\" in { \n",
+ " assertResult(r1) {\n",
+ " mapValues(m1) { (i: Int) => i * i }\n",
+ " }\n",
+ " }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a55bede4-74af-4a96-a943-97cb5e584e13",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 7 (5 points)**</span> As we\n",
+ "mentioned above, we just reimplemented `mapValues` using the `map`\n",
+ "method from the standard library. Earlier, we implemented higher-order\n",
+ "functions on `List`s recursively. Could we have implemented `mapValues`\n",
+ "on `Map`s recursively? If yes, give an example implementation. If no,\n",
+ "explain why we cannot, and what makes `Map` different from `List` in\n",
+ "this case.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d533e044-1102-4111-aca2-d89b56675e6b",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "345e3429a34b13ba9693f3f9a0978bcd",
+ "grade": true,
+ "grade_id": "explain-map",
+ "locked": false,
+ "points": 5,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "Yes, this could have been done recursively. The main difference between a `Map` and `List` is that a `Map` is an unordered key-value pair data structure, whereas a `List` is an ordered, linear sequence of elements. An example implementation is as follows:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 63,
+ "id": "08af9ccd-4e2c-4061-a92d-7bd663685013",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mmapValuesRecursive\u001b[39m"
+ ]
+ },
+ "execution_count": 63,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def mapValuesRecursive[A, B, C](m: Map[A, B])(f: B => C): Map[A, C] = {\n",
+ " if (m.isEmpty)\n",
+ " Map.empty\n",
+ " else {\n",
+ " val (k, v) = m.head\n",
+ " mapValuesRecursive(m.tail)(f) + (k -> f(v))\n",
+ " }\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4c81a60c-833e-402e-8729-262b1d3e1c85",
+ "metadata": {},
+ "source": [
+ "### Trees\n",
+ "\n",
+ "Recall the binary tree data type:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 64,
+ "id": "4b674bde",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mtrait\u001b[39m \u001b[36mTree\u001b[39m\n",
+ "defined \u001b[32mobject\u001b[39m \u001b[36mEmpty\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m"
+ ]
+ },
+ "execution_count": 64,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sealed trait Tree\n",
+ "case object Empty extends Tree\n",
+ "case class Node(l: Tree, d: Int, r: Tree) extends Tree"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "e6714a92-bf33-4a9f-bb50-60081f14bfce",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 8 (10 points)**</span> Implement\n",
+ "a higher-order function `foldLeft` that performs an in-order traversal\n",
+ "of the input `t: Tree`, calling the callback `f` starting with `z` to\n",
+ "accumulate a result. For example, suppose the in-order traversal of the\n",
+ "input tree `t` yields the sequence of data values: $d_1,d_2,\\dots,d_n$.\n",
+ "Then, `foldLeft(t)(z)(f)` yields\n",
+ "$f(f(\\dots(f(f(z,d_1),d_2))\\dots d_{n-1}),d_n)$\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 65,
+ "id": "e7faa101",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "01a7fd4c23093ca596c8f5efe2b8a86b",
+ "grade": false,
+ "grade_id": "tree-foldleft-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mfoldLeft\u001b[39m"
+ ]
+ },
+ "execution_count": 65,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def foldLeft[A](t: Tree)(z: A)(f: (A, Int) => A): A = {\n",
+ " def loop(acc: A, t: Tree): A = t match {\n",
+ " case Empty => acc\n",
+ " case Node(l, d, r) => \n",
+ " val leftAcc = loop(acc, l)\n",
+ " val currAcc = f(leftAcc, d)\n",
+ " loop(currAcc, r)\n",
+ " }\n",
+ " loop(z, t)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "45b0ef95-9430-4447-b091-c6e691310120",
+ "metadata": {},
+ "source": [
+ "We have provided a test client `sum` that computes the sum of all of the\n",
+ "data values in the tree using your `foldLeft` method, along with some\n",
+ "helper functions to build trees more easily. Feel free to use them to\n",
+ "write more test cases for your code."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 66,
+ "id": "d14dd60d",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "fd47c7f1d30d0afe0a08de165786fe94",
+ "grade": false,
+ "grade_id": "tree-foldleft-client",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36msum\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36minsert\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mtreeFromList\u001b[39m"
+ ]
+ },
+ "execution_count": 66,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// An example use of foldLeft\n",
+ "def sum(t: Tree): Int = foldLeft(t)(0){ (acc, d) => acc + d }\n",
+ "\n",
+ "// In-order insertion into a binary search tree\n",
+ "def insert(t: Tree, n: Int): Tree = t match {\n",
+ " case Empty => Node(Empty, n, Empty)\n",
+ " case Node(l, d, r) =>\n",
+ " if (n < d) Node(insert(l, n), d, r) else Node(l, d, insert(r, n))\n",
+ "}\n",
+ "\n",
+ "// Create a tree from a list. An example use of the List.foldLeft method.\n",
+ "def treeFromList(l: List[Int]): Tree =\n",
+ " l.foldLeft(Empty: Tree){ (acc, i) => insert(acc, i) }"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d3bc3e75-025a-4e5f-9618-ff3ef0055ccb",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 67,
+ "id": "ffaf0123",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "bd11a15eb82027b8f34c1cae8d4c29bc",
+ "grade": true,
+ "grade_id": "eval-fold-left-tester",
+ "locked": true,
+ "points": 10,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 3\u001b[0m\n",
+ "\u001b[32mcmd67$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mfoldLeft\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[32m- should Test Case 2\u001b[0m\n",
+ "\u001b[32m- should Test Case 3\u001b[0m\n",
+ "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 3\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (10 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val t1 = treeFromList(List(1, 2, 3))\n",
+ " \"foldLeft\" should \"Test Case 1\" in { assertResult(6) { sum(t1) } }\n",
+ "\n",
+ " val l2 = List(3, 4, 8, 2, 1, 7, 10)\n",
+ " val sortl2 = l2.sorted\n",
+ " val t2 = treeFromList(l2)\n",
+ "\n",
+ " def rev(acc: List[Int], x: Int): List[Int] = x :: acc\n",
+ " def prod(acc: Int, x: Int): Int = x * acc\n",
+ "\n",
+ " it should \"Test Case 2\" in {\n",
+ " assertResult( sortl2.foldLeft(Nil: List[Int])(rev) ) {\n",
+ " foldLeft(t2)(Nil: List[Int])(rev)\n",
+ " }\n",
+ " }\n",
+ "\n",
+ " it should \"Test Case 3\" in {\n",
+ " assertResult( l2.foldLeft(1)(prod) ) {\n",
+ " foldLeft(t2)(1)(prod)\n",
+ " }\n",
+ " }\n",
+ "\n",
+ "}, 10)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "f5b47cb0-9f83-4f25-857a-8d61bdc93ac3",
+ "metadata": {},
+ "source": [
+ "<span class=\"theorem-title\">**Exercise 9 (10 points)**</span> Using your\n",
+ "`foldLeft` function, write a client function `strictlyOrdered` that\n",
+ "checks if the data values of an in-order traversal of `t` are in\n",
+ "strictly ascending order. For example, suppose the in-order traversal of\n",
+ "the input tree `t` yields the sequence of data values:\n",
+ "$d_1,d_2,\\dots,d_n$, the `strictlyOrdered` should return `true` iff\n",
+ "$d_1 < d_2 < \\dots < d_n$.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 68,
+ "id": "6f839e9c",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "aebc268efefe554f4e2fb9721df67464",
+ "grade": false,
+ "grade_id": "tree-strictly-ordered-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mstrictlyOrdered\u001b[39m"
+ ]
+ },
+ "execution_count": 68,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def strictlyOrdered(t: Tree): Boolean = {\n",
+ " val (b, _) = foldLeft(t)((true, None: Option[Int])) {\n",
+ " case ((true, None), d) => (true, Some(d))\n",
+ " case ((true, Some(prev)), d) if d > prev => (true, Some(d))\n",
+ " case _ => (false, None)\n",
+ " }\n",
+ " b\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "33c18a55-90c0-4408-8074-f2f7c66668f6",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 69,
+ "id": "0a029a26",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "f5349c102e6a628f88e43c633f2b79d5",
+ "grade": true,
+ "grade_id": "eval-strictly-ordered-tester",
+ "locked": true,
+ "points": 10,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 5\u001b[0m\n",
+ "\u001b[32mcmd69$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mstrictlyOrdered\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[32m- should Test Case 2\u001b[0m\n",
+ "\u001b[32m- should Test Case 3\u001b[0m\n",
+ "\u001b[32m- should Test Case 4\u001b[0m\n",
+ "\u001b[32m- should Test Case 5\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 5\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 5, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (10 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " \"strictlyOrdered\" should \"Test Case 1\" in { assert(!strictlyOrdered(treeFromList(List(1,1,2)))) }\n",
+ " it should \"Test Case 2\" in { assert(strictlyOrdered(treeFromList(List(1,2)))) }\n",
+ " it should \"Test Case 3\" in { assert(!strictlyOrdered(treeFromList(List(-1,0,1,1,2)))) }\n",
+ " it should \"Test Case 4\" in { assert(!strictlyOrdered(treeFromList(List(2,1,2,3,4)))) }\n",
+ " it should \"Test Case 5\" in { assert(strictlyOrdered(treeFromList(List(1,2,3,4,5)))) }\n",
+ "}, 10)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a08913be-7d42-468a-a9f6-8ea4e86e7fe1",
+ "metadata": {},
+ "source": [
+ "Now, we will write a higher-order function that uses our recent\n",
+ "higher-order functions as a client.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 10 (5 points)**</span> Implement\n",
+ "a function `foldLeftTrees` that take as input a `lt: List[Tree]`, and\n",
+ "applies a callback `f` to all of their nodes in-order (of both the\n",
+ "`List` and the nested `Tree`s) starting with initial value `z` to\n",
+ "accumulate a result.\n",
+ "\n",
+ "For example, calling `foldLeftTrees` on\n",
+ "\n",
+ "``` scala\n",
+ "val lt = \n",
+ " List(\n",
+ " Node(Node(Empty, 1, Empty), 2, Node(Empty, 3, Empty)),\n",
+ " Node(Node(Empty, 4, Empty), 5, Node(Empty, 6, Empty))\n",
+ " )\n",
+ "```\n",
+ "\n",
+ "<pre><span class=\"ansi-cyan-fg\">lt</span>: <span class=\"ansi-green-fg\">List</span>[<span class=\"ansi-green-fg\">Node</span>] = <span class=\"ansi-yellow-fg\">List</span>(\n",
+ " <span class=\"ansi-yellow-fg\">Node</span>(\n",
+ " l = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">1</span>, r = Empty),\n",
+ " d = <span class=\"ansi-green-fg\">2</span>,\n",
+ " r = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">3</span>, r = Empty)\n",
+ " ),\n",
+ " <span class=\"ansi-yellow-fg\">Node</span>(\n",
+ " l = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">4</span>, r = Empty),\n",
+ " d = <span class=\"ansi-green-fg\">5</span>,\n",
+ " r = <span class=\"ansi-yellow-fg\">Node</span>(l = Empty, d = <span class=\"ansi-green-fg\">6</span>, r = Empty)\n",
+ " )\n",
+ ")</pre>\n",
+ "\n",
+ "and a function that sums integers should return `21`.\n",
+ "\n",
+ "Use only `foldLeft` on `Tree` that you have defined above and `foldLeft`\n",
+ "on `List[Tree]` provided in the Scala standard library.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 70,
+ "id": "d6e777bb",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "156a49fe3a557c401f58e63fddec2525",
+ "grade": false,
+ "grade_id": "reduce-trees-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mfoldLeftTrees\u001b[39m"
+ ]
+ },
+ "execution_count": 70,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def foldLeftTrees[B](lt: List[Tree])(z: B)(f: (B, Int) => B): B =\n",
+ " lt.foldLeft(z) {\n",
+ " (acc, t) => foldLeft(t)(acc)(f)\n",
+ " }"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "d994727e-2506-454a-aff4-60109f2943e3",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 71,
+ "id": "cb1dd3e8",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "882cdcfb3b78d41738ff798a0380050f",
+ "grade": true,
+ "grade_id": "eval-reduce-trees-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 2\u001b[0m\n",
+ "\u001b[32mcmd71$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mfoldLeftTrees\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[32m- should reverse and flatten\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 2\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " def sum(trees: List[Tree]): Int = foldLeftTrees(trees)(0){ (acc, d) => acc + d }\n",
+ "\n",
+ " val l1 = List(1, 2, 3)\n",
+ " val l2 = List(4, 5, 6)\n",
+ " val t1 = treeFromList(l1)\n",
+ " val t2 = treeFromList(l2)\n",
+ " val lt1 = List(t1, t2)\n",
+ "\n",
+ " val l1l2 = l1 ::: l2\n",
+ "\n",
+ " \"foldLeftTrees\" should \"Test Case 1\" in { assertResult(21){ sum(lt1) } }\n",
+ "\n",
+ " it should \"reverse and flatten\" in {\n",
+ " assertResult( l1l2.reverse ) { foldLeftTrees(lt1)(Nil: List[Int]){ (acc, i) => i :: acc } }\n",
+ " }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "3d685753-6dd5-4523-96dc-1a13b28b27a4",
+ "metadata": {},
+ "source": [
+ "## flatMap\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 11 (5 points)**</span> Recall the\n",
+ "`flatMap` function from class on `List`. Write a new function\n",
+ "`flatMapNoRec` that implements the same behavior without direct\n",
+ "recursion; instead, use `foldRight` and `:::`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 72,
+ "id": "d968e550",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "4735e78fbac810026d9023e023fd3c02",
+ "grade": false,
+ "grade_id": "flat-map-no-rec-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mflatMapNoRec\u001b[39m"
+ ]
+ },
+ "execution_count": 72,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def flatMapNoRec[A, B](l: List[A])(f: A => List[B]): List[B] = \n",
+ " l.foldRight(List.empty[B])((h, acc) => f(h) ::: acc)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8a421085-45ef-42e5-883b-3143d04b9c80",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 73,
+ "id": "9b48e422",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "df083491ef6efe52e1295103f5b27c11",
+ "grade": true,
+ "grade_id": "eval-flat-map-no-rec-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd73$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mflatMapNoRec\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 1 millisecond.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " def duplicate[A](l: List[A]) = flatMapNoRec(l) { a => List(a, a) }\n",
+ "\n",
+ " val l1 = List(1, 2, 3)\n",
+ " val r1 = List(1, 1, 2, 2, 3, 3)\n",
+ "\n",
+ " \"flatMapNoRec\" should \"Test Case 1\" in { assertResult(r1) { duplicate(l1) } }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "18ad4a5a-c8c7-42d0-a331-79942c8213a7",
+ "metadata": {},
+ "source": [
+ "Now, we will try to use `flatMap` to do something useful.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 12 (5 points)**</span> Write a\n",
+ "function `getAllWords` that takes in a `List[String]` of sentences and\n",
+ "returns a `List[String]` of all the words in the sentences. For\n",
+ "simplicity, our sentences will have no punctuation, and all words will\n",
+ "be separated by a single space. For example, given the input\n",
+ "`List(\"I love 3155\", \"Anish is the best TA\")`, the `getAllWords`\n",
+ "function should return\n",
+ "`List(\"I\", \"love\", \"3155\", \"Anish\", \"is\", \"the\", \"best\", \"TA\")`.\n",
+ "\n",
+ "Use the String method `split` to separate a sentence into its component\n",
+ "words:\n",
+ "\n",
+ "``` scala\n",
+ "\"Functions are values\".split(\" \").toList\n",
+ "```\n",
+ "\n",
+ "<pre><span class=\"ansi-cyan-fg\">res22</span>: <span class=\"ansi-green-fg\">List</span>[<span class=\"ansi-green-fg\">String</span>] = <span class=\"ansi-yellow-fg\">List</span>(<span class=\"ansi-green-fg\">\"Functions\"</span>, <span class=\"ansi-green-fg\">\"are\"</span>, <span class=\"ansi-green-fg\">\"values\"</span>)</pre>\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 74,
+ "id": "f36f72c6",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "72a81c102de3d1d14329753a39c80c17",
+ "grade": false,
+ "grade_id": "get-all-words-answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mgetAllWords\u001b[39m"
+ ]
+ },
+ "execution_count": 74,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def getAllWords(sentences: List[String]): List[String] = \n",
+ " sentences.flatMap(sentence => sentence.split(\" \").toList)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4c91d0b4-db4a-4520-8220-f8ee63a6ac77",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 75,
+ "id": "51f3b3c2",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "651dd0c46359dc33dde3983afbbe2606",
+ "grade": true,
+ "grade_id": "eval-get-all-words-tester",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 1\u001b[0m\n",
+ "\u001b[32mcmd75$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mgetAllWords\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[36mRun completed in 0 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 1\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** šŸŽ‰ Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val l1 = List(\"I love 3155\", \"Anish is the best TA\")\n",
+ " val r1 = List(\"I\", \"love\", \"3155\", \"Anish\", \"is\", \"the\", \"best\", \"TA\")\n",
+ "\n",
+ " \"getAllWords\" should \"Test Case 1\" in { assertResult(r1) { getAllWords(l1) } }\n",
+ "}, 5)"
+ ]
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Scala",
+ "language": "scala",
+ "name": "scala"
+ },
+ "language_info": {
+ "codemirror_mode": "text/x-scala",
+ "file_extension": ".sc",
+ "mimetype": "text/x-scala",
+ "name": "scala",
+ "nbconvert_exporter": "script",
+ "version": "2.13.14"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}
diff --git a/lab4/build.sbt b/lab4/build.sbt
new file mode 100644
index 0000000..6a180b6
--- /dev/null
+++ b/lab4/build.sbt
@@ -0,0 +1,46 @@
+name := "pppl-lab4"
+
+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.4.0",
+ "org.scalatest" %% "scalatest" % "3.2.19" % "test"
+ ),
+
+ // set logging to show only errors during runs
+ logLevel / run := Level.Error,
+ logLevel / runMain := Level.Error,
+ Global / excludeLintKeys += logLevel,
+
+ // JVM arguments: 8G heap size, 2M stack size
+ // javaOptions in Test += "-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 lab4 = (project in file("."))
+ .settings(commonSettings: _*)
diff --git a/lab4/project/build.properties b/lab4/project/build.properties
new file mode 100644
index 0000000..ee4c672
--- /dev/null
+++ b/lab4/project/build.properties
@@ -0,0 +1 @@
+sbt.version=1.10.1
diff --git a/lab4/src/main/scala/jsy/lab4/Lab4.scala b/lab4/src/main/scala/jsy/lab4/Lab4.scala
new file mode 100644
index 0000000..d3f16b2
--- /dev/null
+++ b/lab4/src/main/scala/jsy/lab4/Lab4.scala
@@ -0,0 +1,362 @@
+package jsy.lab4
+
+object Lab4 extends jsy.util.JsyApplication {
+ import ast._
+
+ /*
+ * CSCI 3155: Lab 4
+ * Jack Sangdahl
+ */
+
+ /* Helper functions */
+ def mapFirst[A](f: A => Option[A])(l: List[A]): List[A] = l match {
+ case Nil => l
+ case h :: t =>
+ f(h) match {
+ case Some(x) => x :: t
+ case None => h :: mapFirst(f)(t)
+ }
+ }
+
+ /*
+ * Helper function that implements the semantics of inequality
+ * operators Lt, Le, Gt, and Ge on values.
+ */
+ def doInequality(bop: Bop, v1: Expr, v2: Expr): Boolean = {
+ require(isValue(v1), s"doInequality: v1 ${v1} is not a value")
+ require(isValue(v2), s"doInequality: v2 ${v2} is not a value")
+ require(bop == Lt || bop == Le || bop == Gt || bop == Ge)
+ ((v1, v2): @unchecked) match {
+ case (S(s1), S(s2)) =>
+ (bop: @unchecked) match {
+ case Lt => s1 < s2
+ case Le => s1 <= s2
+ case Gt => s1 > s2
+ case Ge => s1 >= s2
+ }
+ case (N(n1), N(n2)) =>
+ (bop: @unchecked) match {
+ case Lt => n1 < n2
+ case Le => n1 <= n2
+ case Gt => n1 > n2
+ case Ge => n1 >= n2
+ }
+ }
+ }
+
+ /* Small-Step Interpreter */
+
+ /* Scope-respecting substitution substituting v for free uses of variable x iin e. */
+ def substitute(v: 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 (x == y) v else e
+ case ConstDecl(y, e1, e2) =>
+ if (x == y) ConstDecl(y, subst(e1), e2)
+ else ConstDecl(y, subst(e1), subst(e2))
+ case Fun(xopt, yts, tretopt, e1) =>
+ xopt match {
+ case Some(y) if (x == y) => e
+ case _ =>
+ if (yts.exists { case (y, _) => y == x })
+ Fun(xopt, yts, tretopt, e1)
+ else Fun(xopt, yts, tretopt, subst(e1))
+ }
+ case Call(e0, es) => Call(subst(e0), es.map(subst))
+ case Obj(fields) => Obj(fields.map { case (f, e1) => (f, subst(e1)) })
+ case GetField(e1, f) => GetField(subst(e1), f)
+ }
+ subst(e)
+ }
+
+ /* Type Inference */
+ type TEnv = Map[String, Typ]
+ def lookup[A](env: Map[String, A], x: String): A = env(x)
+ def extend[A](env: Map[String, A], x: String, a: A): Map[String, A] = {
+ env + (x -> a)
+ }
+
+ def hastype(env: TEnv, e: Expr): Typ = {
+ def err[T](tgot: Typ, e1: Expr): T = throw StaticTypeError(tgot, e1, e)
+
+ e match {
+ case Print(e1) => hastype(env, e1); TUndefined
+ case N(_) => TNumber
+ case B(_) => TBool
+ case Undefined => TUndefined
+ case S(_) => TString
+ case Var(x) => lookup(env, x)
+ 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, tgot2) => err(tgot1, e1)
+ }
+ case Binary(Minus | Times | Div, e1, e2) =>
+ (hastype(env, e1), hastype(env, e2)) match {
+ case (TNumber, TNumber) => TNumber
+ case (tgot1, tgot2) => err(tgot1, e1)
+ }
+ case Binary(Eq | Ne, e1, e2) =>
+ (hastype(env, e1), hastype(env, e2)) match {
+ case (TNumber, TNumber) => TBool
+ case (TString, TString) => TBool
+ case (tgot1, tgot2) => err(tgot1, e1)
+ }
+ case Binary(Lt | Le | Gt | Ge, e1, e2) =>
+ (hastype(env, e1), hastype(env, e2)) match {
+ case (TNumber, TNumber) => TBool
+ case (TString, TString) => TBool
+ case (tgot1, tgot2) => err(tgot1, e1)
+ }
+ case Binary(And | Or, e1, e2) =>
+ (hastype(env, e1), hastype(env, e2)) match {
+ case (TBool, TBool) => TBool
+ case (tgot1, tgot2) => err(tgot1, 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 ConstDecl(x, e1, e2) =>
+ val t1 = hastype(env, e1)
+ val env1 = extend(env, x, t1)
+ hastype(env1, e2)
+ 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 Fun(xopt, yts, tretopt, e1) => {
+ val env1 = (xopt, tretopt) match {
+ case (Some(fname), Some(tret)) =>
+ extend(
+ env,
+ fname,
+ TFun(yts.map { case (y, typ) => (y, typ) }, tret)
+ )
+ case _ => env
+ }
+ val env2 = yts.foldLeft(env1) { case (accEnv, (y, ty)) =>
+ extend(accEnv, y, ty)
+ }
+ val t1 = hastype(env2, e1)
+ tretopt match {
+ case Some(tret) =>
+ if (t1 == tret) TFun(yts.map { case (y, typ) => (y, typ) }, tret)
+ else err(t1, e1)
+ case None => TFun(yts.map { case (y, typ) => (y, typ) }, t1)
+ }
+ }
+ case Call(e0, args) =>
+ hastype(env, e0) match {
+ case TFun(params, tret) if (params.length == args.length) =>
+ (params zip args).foreach { case ((_, paramType), argExpr) =>
+ val argType = hastype(env, argExpr)
+ if (argType != paramType) err(argType, argExpr)
+ }
+ tret
+ case tgot => err(tgot, e0)
+ }
+
+ }
+ }
+
+ /* A small-step transition. */
+ def step(e: Expr): Expr = {
+ require(!isValue(e), s"step: e ${e} to step is a value")
+
+ e match {
+ case Print(v1) if isValue(v1) => println(pretty(v1)); Undefined
+ case Unary(Neg, N(n1)) => N(-n1)
+ case Unary(Not, B(b1)) => B(!b1)
+ case Binary(Seq, v1, e2) if isValue(v1) => e2
+ case Binary(Plus, S(s1), S(s2)) => S(s1 + s2)
+ case Binary(Plus, N(n1), N(n2)) => N(n1 + n2)
+ case Binary(bop @ (Lt | Le | Gt | Ge), v1, v2)
+ if isValue(v1) && isValue(v2) =>
+ B(doInequality(bop, v1, v2))
+ case Binary(Eq, v1, v2) if isValue(v1) && isValue(v2) => B(v1 == v2)
+ case Binary(Ne, v1, v2) if isValue(v1) && isValue(v2) => B(v1 != v2)
+ case Binary(And, B(b1), e2) => if (b1) e2 else B(false)
+ case Binary(Or, B(b1), e2) => if (b1) B(true) else e2
+ case ConstDecl(x, v1, e2) if isValue(v1) => substitute(v1, x, e2)
+ case Call(v1, args) if isValue(v1) && (args forall isValue) =>
+ v1 match {
+ case Fun(p, params, _, e1) => {
+ val e1p = (params, args).zipped.foldRight(e1) { case ((p, a), e1) =>
+ substitute(a, p._1, e1)
+ }
+ p match {
+ case None => e1p
+ case Some(x1) => substitute(v1, x1, e1p)
+ }
+ }
+ case _ => throw new StuckError(e)
+ }
+ case Binary(Minus, N(n1), N(n2)) => N(n1 - n2)
+ case Binary(Times, N(n1), N(n2)) => N(n1 * n2)
+ case Binary(Div, N(n1), N(n2)) => N(n1 / n2)
+ case If(B(true), e1, e2) => e1
+ case If(B(false), e1, e2) => e2
+ case Print(e1) => Print(step(e1))
+ case Unary(uop, e1) => Unary(uop, step(e1))
+ case Binary(bop, v1, e2) if isValue(v1) => Binary(bop, v1, step(e2))
+ case Binary(bop, e1, e2) => Binary(bop, step(e1), e2)
+ case If(e1, e2, e3) => If(step(e1), e2, e3)
+ case ConstDecl(x, e1, e2) => ConstDecl(x, step(e1), e2)
+ case Call(Fun(name, params, t, e1), args) if args.forall(isValue) => {
+ val x = name match {
+ case Some(y) => substitute(Fun(name, params, t, e1), y, e1)
+ case None => e1
+ }
+ params.zip(args).foldLeft(x) { (e2, t2) =>
+ substitute(t2._2, t2._1._1, e2)
+ }
+ }
+ case Call(Fun(name, params, t, e1), args) => {
+ Call(
+ Fun(name, params, t, e1),
+ mapFirst((arg: Expr) => {
+ if (isValue(arg)) None else Some(step(arg))
+ })(args)
+ )
+ }
+ case Call(func, args) => Call(step(func), args)
+ case GetField(obj, field) =>
+ obj match {
+ case Obj(f) =>
+ f.get(field) match {
+ case Some(x) => x
+ case None => throw new StuckError(e)
+ }
+ case e1 => GetField(step(e1), field)
+ }
+
+ /* Everything else is a stuck error. Should not happen if e is well-typed. */
+ case _ => throw StuckError(e)
+ }
+ }
+
+ /* External Interfaces */
+
+ /** Interface to run your type checker. */
+ def inferType(e: Expr): Typ = {
+ val t = hastype(Map.empty, e)
+ println(s"## ${e} : ${pretty(t)}")
+ t
+ }
+
+ /** 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): Expr = {
+ if (Some(n) == maxSteps) throw TerminationError(e, n)
+ if (isValue(e)) e
+ else {
+ println("## step %4d: %s".format(n, e))
+ loop(step(e), n + 1)
+ }
+ }
+ val v = loop(e, 0)
+ println(s"## value: %s".format(v))
+ v
+ }
+
+ /** Interface to type check from a string. This is convenient for unit
+ * testing.
+ */
+ def inferType(s: String): Typ = inferType(Parser.parse(s))
+
+ /** Interface to take a small-step from a string. This is convenient for unit
+ * testing.
+ */
+ def oneStep(s: String): Expr = step(Parser.parse(s))
+
+ /** Interface to run your small-step interpreter from a string. This is
+ * convenient for unit testing.
+ */
+ def iterateStep(s: String): Expr = iterateStep(Parser.parse(s))
+
+ // Interface for main
+
+ // this.debug = true // uncomment this if you want to 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
+
+ def processFile(file: java.io.File): Unit = {
+ if (debug) {
+ println("# ============================================================")
+ println("# File: " + file.getName)
+ println("# Parsing ...")
+ }
+
+ val exprin =
+ handle(None: Option[Expr]) {
+ Some {
+ Parser.parseFile(file)
+ }
+ } getOrElse {
+ return
+ }
+
+ val expr = exprin
+
+ 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 ...".format(expr))
+ }
+
+ handle(()) {
+ val v = iterateStep(expr)
+ println(pretty(v))
+ }
+ }
+
+}
diff --git a/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.sc b/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.sc
new file mode 100644
index 0000000..3e516a6
--- /dev/null
+++ b/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.sc
@@ -0,0 +1,39 @@
+/*
+ * CSCI 3155: Lab 4 Worksheet
+ *
+ * This worksheet demonstrates how you could experiment
+ * interactively with your implementations in Lab4.scala.
+ */
+
+// Imports the parse function from jsy.lab3.Parser
+import jsy.lab4.Parser.{parse, parseFile}
+
+// Imports the ast nodes
+import jsy.lab4.ast._
+
+// Imports all of the functions form jsy.student.Lab4 (your implementations in Lab4.scala)
+import jsy.lab4.Lab4._
+
+// Parse functions with possibly multiple parameters and type annotations.
+parse("function fst(x: number, y: number): number { return x }")
+parse("function (x: number) { return x }")
+parse("function (f: (y: number) => number, x: number) { return f(x) }")
+
+// Parse objects
+parse("{ f: 0, g: true }")
+parse("x.f")
+
+// Run your type checker
+// - inferType calls your typeof
+//inferType("1 + 2")
+
+// Run your small-step interpreter
+// - iterateStep calls your iterate and your step
+//iterateStep("1 + 2")
+
+// Parse the JavaScripty expression in your worksheet
+val worksheetJsy = parseFile("src/main/scala/jsy/lab4/Lab4.worksheet.ts")
+
+// Interpret the JavaScripty expression in your worksheet
+//inferType(worksheetJsy)
+//iterateStep(worksheetJsy) \ No newline at end of file
diff --git a/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.ts b/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.ts
new file mode 100644
index 0000000..0f212c3
--- /dev/null
+++ b/lab4/src/main/scala/jsy/lab4/Lab4.worksheet.ts
@@ -0,0 +1,35 @@
+/*
+ * CSCI 3155: Lab 4 TypeScript Worksheet
+ *
+ * This worksheet is a place to experiment with TypeScript expressions.
+ */
+
+// The new language features in Lab 4 are types, multi-parameter functions,
+// and objects.
+
+const id_number = ((x: number) => x);
+
+const plus = ((x: number) => (y: number) => x + y);
+const plus_uncurried = ((x: number, y: number) => x + y);
+const plus_pair = ((pair: { x: number; y: number }) => pair.x + pair.y);
+
+const fst = ((x: number, y: number) => x);
+const fst_alt = function (x: number, y: number): number { return x; };
+const fst_pair = ((pair: { x: number; y: number }) => pair.x);
+
+const inc = plus(1);
+
+const do_numfun = function (f: (y: number) => number, x: number) { return f(x); };
+
+console.log(id_number(3));
+
+console.log(plus(3)(4));
+console.log(plus_uncurried(3, 4));
+console.log(plus_pair({ x: 3, y: 4 }))
+console.log(plus_pair({ x: 1 + 2, y: 3 + 4 }))
+
+console.log(fst(5, 6));
+console.log(fst_alt(5, 6));
+console.log(fst_pair({ x: 5, y: 6 }));
+
+console.log(do_numfun(inc, 2)); \ No newline at end of file
diff --git a/lab4/src/main/scala/jsy/lab4/Parser.scala b/lab4/src/main/scala/jsy/lab4/Parser.scala
new file mode 100644
index 0000000..5db3b1f
--- /dev/null
+++ b/lab4/src/main/scala/jsy/lab4/Parser.scala
@@ -0,0 +1,437 @@
+/** */
+package jsy.lab4
+
+import jsy.lab4.ast._
+import scala.util.parsing.combinator._
+import scala.util.parsing.input.CharSequenceReader
+import scala.util.parsing.combinator.syntactical.StandardTokenParsers
+import scala.util.parsing.input.{StreamReader, Reader}
+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.TreeMap
+
+trait JSTokens extends token.StdTokens {
+ case class FloatLiteral(chars: String) extends Token {
+ override def toString = chars
+ }
+}
+
+class Lexer extends lexical.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
+ val lexical = new Lexer
+
+ import lexical.FloatLiteral
+
+ def floatLit: this.Parser[String] =
+ elem("float", _.isInstanceOf[FloatLiteral]) ^^ (_.chars)
+}
+
+object Parser extends TokenParser {
+ /* 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(
+ "-",
+ "!",
+ ";",
+ ",",
+ "+",
+ "*",
+ "/",
+ "=",
+ "===",
+ "!==",
+ "<",
+ "<=",
+ ">",
+ ">=",
+ "&&",
+ "||",
+ "(",
+ ")",
+ ".",
+ "{",
+ "}",
+ "?",
+ ":",
+ "=>"
+ )
+
+ /* 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 ::= seq
+ * seq ::= cond{,cond}
+ * noseq ::= arrow
+ * arrow ::= x => noseq | cond
+ * cond ::= binary [? cond : cond]
+ * binary ::= unary{bop(_)unary}
+ * unary ::= uop unary | call
+ * call ::= term{(expr)}
+ * 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] =
+ ("const" ~> ident) ~ withpos("=" ~> expr) ^^ {
+ case x ~ ((pos,e1)) => ((e2: Expr) => ConstDecl(x, e1, e2) setPos pos)
+ }
+
+ 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] =
+ cond
+
+ 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
+ }
+
+ // def funblock: this.Parser[Expr] =
+ // ("{" ~> stmts ~ ret <~ rep(empty_stmt) <~ "}") ^^ { case stmts ~ ret =>
+ // stmts(Some(ret))
+ // }
+
+ // def ret: this.Parser[Expr] =
+ // "return" ~> expr
+
+ // 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))
+
+ 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) |
+ ("jsy" ~ "." ~ "print") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) |
+ ("console" ~ "." ~ "log") ~> "(" ~> expr <~ ")" ^^ (e => Print(e)) |
+ function |
+ record(",", Obj, noseq)
+ ) |
+ "(" ~> expr <~ ")" |
+ "{" ~> "{" ~> prog <~ "}" <~ "}" |
+ failure("atomic expression expected")
+
+ def function: this.Parser[Expr] =
+ ("function" ~> opt(ident)) ~ ("(" ~> repsep(
+ colonpair(ty),
+ ","
+ ) <~ ")") ~ 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(ty), ",") <~ ")") ~ (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: Map[String, A] => A,
+ q: => this.Parser[A]
+ ): this.Parser[A] = {
+ lazy val p = q
+ "{" ~> repsep(colonpair(p), sep) <~ (opt(",") ~ "}") ^^ { flist =>
+ val fmap = flist.foldLeft(TreeMap.empty: TreeMap[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] =
+ "number" ^^ (_ => TNumber) |
+ "bool" ^^ (_ => TBool) |
+ "string" ^^ (_ => TString) |
+ "Undefined" ^^ (_ => TUndefined) |
+ record(";", TObj, ty) |
+ tyfun |
+ failure("type expected")
+
+ def tyfun: this.Parser[Typ] =
+ ("(" ~> repsep(colonpair(ty), ",") <~ ")") ~ ("=>" ~> ty) ^^ {
+ case params ~ t2 => TFun(params, t2)
+ }
+
+ 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))
+
+ private 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)
+
+ class SyntaxError(msg: String, next: Input) extends Exception {
+ override def toString =
+ formatErrorMessage(next.pos, "SyntaxError", msg, true)
+ }
+
+ def parseTokens(tokens: lexical.Scanner): Expr = {
+ phrase(prog)(tokens) match {
+ case Success(e, _) => e
+ case NoSuccess(msg, next) => throw new SyntaxError(msg, next)
+ case Error(msg, next) => throw new SyntaxError(msg, next)
+ case Failure(msg, next) => throw new SyntaxError(msg, next)
+ }
+ }
+
+ def parseTypTokens(tokens: lexical.Scanner): Typ = {
+ phrase(ty)(tokens) match {
+ case Success(t, _) => t
+ case NoSuccess(msg, next) => throw new SyntaxError(msg, next)
+ case Error(msg, next) => throw new SyntaxError(msg, next)
+ case Failure(msg, next) => throw new SyntaxError(msg, next)
+ }
+ }
+
+ /** * 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
+ }
+}
diff --git a/lab4/src/main/scala/jsy/lab4/ast.scala b/lab4/src/main/scala/jsy/lab4/ast.scala
new file mode 100644
index 0000000..c4c3f83
--- /dev/null
+++ b/lab4/src/main/scala/jsy/lab4/ast.scala
@@ -0,0 +1,240 @@
+package jsy.lab4
+
+import scala.util.parsing.input.Positional
+
+/** @author
+ * Bor-Yuh Evan Chang
+ */
+object ast {
+ sealed trait Expr extends Positional // e ::=
+
+ /* Literals */
+ case class N(n: Double) extends Expr // e ::= n
+ case class B(b: Boolean) extends Expr // e ::= b
+ case class S(str: String) extends Expr // e ::= str
+ case object Undefined extends Expr // e ::= undefined
+
+ /* Unary and Binary Expressions */
+ case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1
+ case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // e ::= e1 bop e2
+
+ sealed trait Uop
+ case object Neg extends Uop /* -e1 */
+ case object Not extends Uop /* !e1 */
+
+ sealed trait Bop
+ /* Numbers */
+ 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 */
+ /* Booleans */
+ case object And extends Bop /* e1 && e2 */
+ case object Or extends Bop /* e1 || e2 */
+
+ /* Intraprocedural Control */
+ case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3
+
+ /* Side-Effects */
+ case class Print(e1: Expr) extends Expr // e ::= console.log(e1)
+ case object Seq extends Bop // bop ::= ,
+
+ /* Variables */
+ case class Var(x: String) extends Expr // e ::= x
+ case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // e ::= const x = e1; e2
+
+ /* Functions */
+ case class Fun(
+ xopt: Option[String],
+ yts: List[(String, Typ)],
+ tretopt: Option[Typ],
+ e1: Expr
+ ) extends Expr // e::= xopt(yts)tretopt => e1
+ case class Call(e0: Expr, es: List[Expr]) extends Expr // e ::= e1([args])
+
+ /* Objects */
+ case class Obj(fes: Map[String, Expr]) extends Expr
+ case class GetField(e1: Expr, f: String) extends Expr
+
+ /* Types */
+ sealed trait 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, Typ)], 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(fts: Map[String, Typ]) extends Typ
+
+ /* Define values. */
+ def isValue(e: Expr): Boolean = e match {
+ case N(_) | B(_) | Undefined | S(_) | Fun(_, _, _, _) => true
+ case Obj(fields) if (fields forall { case (_, ei) => isValue(ei) }) => true
+ case _ => false
+ }
+
+ /*
+ * Pretty-print values.
+ *
+ * We do not override the toString method so that the abstract syntax can be printed
+ * as is.
+ */
+ def pretty(v: Expr): String = {
+ require(isValue(v))
+ (v: @unchecked) match {
+ case N(n) => n.toString
+ case B(b) => b.toString
+ case Undefined => "undefined"
+ case S(s) => s
+ case Fun(p, _, _, _) =>
+ "[Fun%s]".format(p match {
+ case None => ""
+ case Some(s) => ": " + s
+ })
+ case Obj(fields) =>
+ val pretty_fields =
+ fields map {
+ case (f, S(s)) => f + ": '" + s + "'"
+ case (f, v) => f + ": " + pretty(v)
+ } reduceRightOption { (s, acc) =>
+ s + ",\n " + acc
+ }
+ "{ %s }".format(pretty_fields.getOrElse(""))
+ }
+ }
+
+ /*
+ * Pretty-print types.
+ *
+ * We do not override the toString method so that the abstract syntax can be printed
+ * as is.
+ */
+ def pretty(t: Typ): String = t match {
+ 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(""), pretty(tret))
+ }
+ case TObj(tfields) =>
+ val pretty_fields: Option[String] =
+ tfields map { case (f, t) =>
+ "%s: %s".format(f, pretty(t))
+ } reduceRightOption { (s, acc) =>
+ s + "; " + acc
+ }
+ "{ %s }".format(pretty_fields.getOrElse(""))
+ }
+
+
+ /* Get the free variables of e. */
+ def freeVarsVar(e: Expr): Set[Var] = {
+ def fv(e: Expr): Set[Var] = e match {
+ case vr @ Var(x) => Set(vr)
+ case ConstDecl(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(_) => 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)
+ }
+ fv(e)
+ }
+ 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) }
+ }
+
+ /*
+ * 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}"
+ )
+ }
+}
diff --git a/lab4/src/main/scala/jsy/util/JsyApplication.scala b/lab4/src/main/scala/jsy/util/JsyApplication.scala
new file mode 100644
index 0000000..46b658d
--- /dev/null
+++ b/lab4/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/lab4/src/test/resources/lab4/test4001_id.ans b/lab4/src/test/resources/lab4/test4001_id.ans
new file mode 100644
index 0000000..b0ea4bc
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4001_id.ans
@@ -0,0 +1,4 @@
+## Call(Fun(None,List((x,TNumber)),None,Var(x)),List(N(4.0))) : number
+## step 0: Call(Fun(None,List((x,TNumber)),None,Var(x)),List(N(4.0)))
+## value: N(4.0)
+4.0
diff --git a/lab4/src/test/resources/lab4/test4001_id.jsy b/lab4/src/test/resources/lab4/test4001_id.jsy
new file mode 100644
index 0000000..3402469
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4001_id.jsy
@@ -0,0 +1 @@
+function(x: number) {return x } (4)
diff --git a/lab4/src/test/resources/lab4/test4002_multiparamfun.ans b/lab4/src/test/resources/lab4/test4002_multiparamfun.ans
new file mode 100644
index 0000000..302ccae
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4002_multiparamfun.ans
@@ -0,0 +1,6 @@
+## Call(Fun(None,List((x,TNumber), (y,TBool)),None,If(Var(y),Binary(Plus,Var(x),N(1.0)),Binary(Minus,Var(x),N(1.0)))),List(N(4.0), B(true))) : number
+## step 0: Call(Fun(None,List((x,TNumber), (y,TBool)),None,If(Var(y),Binary(Plus,Var(x),N(1.0)),Binary(Minus,Var(x),N(1.0)))),List(N(4.0), B(true)))
+## step 1: If(B(true),Binary(Plus,N(4.0),N(1.0)),Binary(Minus,N(4.0),N(1.0)))
+## step 2: Binary(Plus,N(4.0),N(1.0))
+## value: N(5.0)
+5.0
diff --git a/lab4/src/test/resources/lab4/test4002_multiparamfun.jsy b/lab4/src/test/resources/lab4/test4002_multiparamfun.jsy
new file mode 100644
index 0000000..9c38c07
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4002_multiparamfun.jsy
@@ -0,0 +1 @@
+function (x: number, y: bool) { return y ? x + 1 : x - 1 } (4, true)
diff --git a/lab4/src/test/resources/lab4/test4007_objliteral.ans b/lab4/src/test/resources/lab4/test4007_objliteral.ans
new file mode 100644
index 0000000..4b4cc1b
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4007_objliteral.ans
@@ -0,0 +1,4 @@
+## Obj(TreeMap(a -> N(5.0), b -> N(2.0))) : { a: number; b: number }
+## value: Obj(TreeMap(a -> N(5.0), b -> N(2.0)))
+{ a: 5.0,
+ b: 2.0 }
diff --git a/lab4/src/test/resources/lab4/test4007_objliteral.jsy b/lab4/src/test/resources/lab4/test4007_objliteral.jsy
new file mode 100644
index 0000000..b98f88d
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4007_objliteral.jsy
@@ -0,0 +1 @@
+{a: 5, b: 2} \ No newline at end of file
diff --git a/lab4/src/test/resources/lab4/test4010_deref.ans b/lab4/src/test/resources/lab4/test4010_deref.ans
new file mode 100644
index 0000000..69a991f
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4010_deref.ans
@@ -0,0 +1,4 @@
+## GetField(Obj(TreeMap(f -> N(3.0))),f) : number
+## step 0: GetField(Obj(TreeMap(f -> N(3.0))),f)
+## value: N(3.0)
+3.0
diff --git a/lab4/src/test/resources/lab4/test4010_deref.jsy b/lab4/src/test/resources/lab4/test4010_deref.jsy
new file mode 100644
index 0000000..83418ef
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4010_deref.jsy
@@ -0,0 +1 @@
+{ f: 3 }.f
diff --git a/lab4/src/test/resources/lab4/test4029_simplerec.ans b/lab4/src/test/resources/lab4/test4029_simplerec.ans
new file mode 100644
index 0000000..b773df9
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4029_simplerec.ans
@@ -0,0 +1,11 @@
+## ConstDecl(n,N(1.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(N(1.0)))) : number
+## step 0: ConstDecl(n,N(1.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(N(1.0))))
+## step 1: Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(N(1.0)))
+## step 2: If(Binary(Eq,N(1.0),N(0.0)),N(0.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(Binary(Minus,N(1.0),N(1.0)))))
+## step 3: If(B(false),N(0.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(Binary(Minus,N(1.0),N(1.0)))))
+## step 4: Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(Binary(Minus,N(1.0),N(1.0))))
+## step 5: Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(N(0.0)))
+## step 6: If(Binary(Eq,N(0.0),N(0.0)),N(0.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(Binary(Minus,N(0.0),N(1.0)))))
+## step 7: If(B(true),N(0.0),Call(Fun(Some(f),List((n,TNumber)),Some(TNumber),If(Binary(Eq,Var(n),N(0.0)),N(0.0),Call(Var(f),List(Binary(Minus,Var(n),N(1.0)))))),List(Binary(Minus,N(0.0),N(1.0)))))
+## value: N(0.0)
+0.0
diff --git a/lab4/src/test/resources/lab4/test4029_simplerec.jsy b/lab4/src/test/resources/lab4/test4029_simplerec.jsy
new file mode 100644
index 0000000..61b2787
--- /dev/null
+++ b/lab4/src/test/resources/lab4/test4029_simplerec.jsy
@@ -0,0 +1,2 @@
+const n = 1;
+(function f(n: number): number { return n === 0 ? 0 : f(n - 1) })(1) \ No newline at end of file
diff --git a/lab4/src/test/scala/jsy/lab4/Lab4Spec.scala b/lab4/src/test/scala/jsy/lab4/Lab4Spec.scala
new file mode 100644
index 0000000..0c05aab
--- /dev/null
+++ b/lab4/src/test/scala/jsy/lab4/Lab4Spec.scala
@@ -0,0 +1,217 @@
+package jsy.lab4
+
+import org.scalatest.flatspec.AnyFlatSpec
+import Parser.parse
+import ast._
+import Lab4._
+
+class Lab4StudentSpec extends AnyFlatSpec {
+}
+
+class Lab4Spec extends AnyFlatSpec {
+
+ /***** hastype Tests *****/
+ {
+ val xtype = TNumber
+ val tenvx = extend(Map.empty, "x", xtype)
+
+ "TypeVar" should "perform TypeVar" in {
+ assertResult(xtype) {
+ hastype(tenvx, Var("x"))
+ }
+ }
+
+ "hastype/call-non-fun" should "yield a static type error" in {
+ for (e <- List(
+ ("3(4)"),
+ ("3(true)"),
+ ("(10 + 4 + 7 - true * 3)(true)"),
+ ("((function (x: number) { return 0 })(10))(true)")
+ )) {
+ intercept[StaticTypeError] {
+ inferType(e)
+ }
+ }
+ }
+
+ "hastype/arithmetic" should "type check JavaScripty arithmetic expressions according to the lab spec" in {
+ for ((e,t) <- List(
+ ("3 <= 4", TBool),
+ ("'3' < '4'", TBool),
+ ("3 + 4", TNumber),
+ ("'3' + '4'", TString),
+ ("3 - 4", TNumber),
+ ("3 * 4 + 1 - 4 / 12", TNumber),
+ ("undefined", TUndefined)
+ )) {
+ assertResult(t){ inferType(e) }
+ }
+ }
+
+ "hastype/functions-objects" should "type check JavaScripty function-object expressions according to the lab spec" in {
+ val f1 = parse("function (x: number) { return x }")
+ val o1 = parse("{f: 3, g: true, h: undefined}")
+ for ((e,t) <- List(
+ (f1, TFun(List(("x", TNumber)), TNumber)),
+ (o1, TObj(Map("f" -> TNumber, "g" -> TBool, "h" -> TUndefined))),
+ (Call(f1, List(N(3))), TNumber),
+ (GetField(o1, "g"), TBool)
+ )) {
+ assertResult(t){ inferType(e) }
+ }
+ }
+
+ "hastype/simple-programs" should "type check JavaScripty programs according to the lab spec" in {
+ assertResult(TNumber) { inferType(
+ """
+ const w = function w(y: number): number { return y === 0 ? 0.1 : y + w(y - 1) };
+ w(3)
+ """
+ )}
+ assertResult(TNumber) { inferType(
+ """
+ const x = 1;
+ const g = function(y: number) { return x; };
+ const h = function(x: number) { return g(2); };
+ h(3)
+ """
+ )}
+ }
+
+ "hastype/recursive-programs" should "type check recursive JavaScripty programs according to the lab spec" in {
+ assertResult(TNumber) { inferType(
+ """
+ const factorial = function f(n: number): number {
+ return n === 0 ? 1 : n * f(n - 1)
+ }
+ factorial(4)
+ """
+ )}
+ }
+ }
+
+
+ /***** substitute Tests *****/
+ {
+ "substitute" should "substitute a value for uses of a variable" in {
+ for ((r,e,v,x) <- List(
+ ("const x = 3; x", "const x = x; x", "3", "x"),
+ ("function (x: number) { return x + y }", "function (x: number) { return x + y }", "3", "x"),
+ ("function x(y: number) { return x + y }", "function x(y: number) { return x + y }", "3", "x")
+ )) {
+ assertResult(parse(r)){ substitute(parse(v), x, parse(e)) }
+ }
+ }
+ }
+
+
+ /***** step Tests *****/
+ {
+ "step" should "perform one step of evaluation according to the lab spec" in {
+ for ((r, s) <- List (
+ ("1", "4 - 3"),
+ ("3 + 4", "1, 3 + 4"),
+ ("(3) + 3", "(1 + 2) + 3"),
+ ("(2) + (3 / 4)", "(1 * 2) + (3 / 4)"),
+ ("(2 + 4)", "true ? (2 + 4) : (1 + 1)"),
+ ("const x = 2; x", "const x = 1 + 1; x"),
+ ("2", "const x = 2; x"),
+ ("3 + 3 + 4 + 5", "1 + 2 + 3 + 4 + 5"),
+ ("3", "(function (x: number) { return x })(3)"),
+// ("3 + 1", "(function (x: number) { return x })(3 + 1)")
+ )) {
+ assertResult(parse(r)){oneStep(s)}
+ }
+ }
+
+ "step/call-non-fun" should "yield a stuck error" in {
+ for (e <- List(
+ ("3(4)"),
+ ("3(true)"),
+ ("((function (x: number) { return 0 })(10))(true)")
+ )) {
+ intercept[StuckError] { iterateStep(e) }
+ }
+ }
+
+ "step/simple-programs" should "evaluate JavaScripty programs according to the lab spec" in {
+ assertResult(N(6.1)) { iterateStep(
+ """
+ const w = function w(y: number) { return y === 0 ? 0.1 : y + w(y - 1) }
+ w(3)
+ """
+ )}
+ assertResult(N(1)) { iterateStep(
+ """
+ const x = 1;
+ const g = function(y: number) { return x; };
+ const h = function(x: number) { return g(2); };
+ h(3)
+ """
+ )}
+ assertResult(N(1.1)) { iterateStep(
+ """
+ const g = function(x: number) { return function(y: number) { return x - y } };
+ g(1)(0) + 0.1
+ """
+ )}
+ assertResult(N(6)) { iterateStep(
+ """
+ const plus = function(x: number, y: number) { return x + y };
+ plus(1 + 2, 3)
+ """
+ )}
+ assertResult(N(6)) { iterateStep(
+ """
+ const plus = function(x: number) { return function(y: number) { return x + y } };
+ plus(1 + 2)(3)
+ """
+ )}
+ }
+
+ "step/recursive-programs" should "evaluate recursive JavaScripty programs according to the lab spec" in {
+ assertResult(N(6)) { iterateStep(
+ """
+ const factorial = function f(n: number) {
+ return n === 0 ? 1 : n * f(n - 1)
+ }
+ factorial(3)
+ """
+ )}
+ assertResult(S("aaa")) { iterateStep(
+ """
+ const repeat = function(s: string) {
+ return function loop(n: number) {
+ return n === 0 ? "" : s + loop(n - 1)
+ }
+ }
+ repeat("a")(3)
+ """
+ )}
+ }
+
+ "step/objects" should "evaluate JavaScripty objects according to the lab spec" in {
+ assertResult(N(7.0)) { iterateStep(
+ """
+ const pair = function(x: number, y: number) {
+ return {x: x, y: y}
+ };
+ const p = pair(3, 4);
+ p.x + p.y
+ """
+ )}
+ assertResult(N(5.0)) { iterateStep(
+ """
+ const suspension = function(f: (a: number) => number, n: number) {
+ return {f: f, n: n}
+ };
+ const s = suspension((a: number) => a + 1, 4);
+ s.f(s.n)
+ """
+ )}
+ }
+ }
+
+}
+
+class Lab4JsyTests extends jsy.tester.JavascriptyTester(None, "lab4", Lab4)
diff --git a/lab4/src/test/scala/jsy/tester/JavascriptyTester.scala b/lab4/src/test/scala/jsy/tester/JavascriptyTester.scala
new file mode 100644
index 0000000..48e789c
--- /dev/null
+++ b/lab4/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)
+ }
+ }
+}
diff --git a/lab4/static-type-checking-lab.ipynb b/lab4/static-type-checking-lab.ipynb
new file mode 100644
index 0000000..7850004
--- /dev/null
+++ b/lab4/static-type-checking-lab.ipynb
@@ -0,0 +1,1106 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "f37a2723",
+ "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": "79519ef5",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "val NAME = \"\"\n",
+ "val COLLABORATORS = \"\""
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "630bdcba",
+ "metadata": {},
+ "source": [
+ "---"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "2485cb19-a0d3-4305-b6e0-a5c61282d0b3",
+ "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: Static Type Checking\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",
+ "<!-- 25 Static Type Checking -->\n",
+ "\n",
+ "<!-- 26 Objects -->\n",
+ "\n",
+ "<!-- 27 Static Type Checking Lab -->\n",
+ "\n",
+ "### Learning Goals\n",
+ "\n",
+ "The primary goals of this lab are:\n",
+ "\n",
+ "- Programming with higher-order functions.\n",
+ "- Static type checking and understanding the interplay between type\n",
+ " checking and evaluation.\n",
+ "\n",
+ "Functional Programming Skills \n",
+ "Higher-order functions with collections and callbacks.\n",
+ "\n",
+ "Programming Language Ideas \n",
+ "Static type checking and type safety. Records.\n",
+ "\n",
+ "### Instructions\n",
+ "\n",
+ "A version of project files for this lab resides in the public\n",
+ "[pppl-lab4](https://github.com/csci3155/pppl-lab4) 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 `Lab4.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 `Lab4Spec.scala` file. In the\n",
+ "`Lab4Spec.scala`, there is empty test class `Lab4StudentSpec` that you\n",
+ "can use to separate your tests from the given tests in the `Lab4Spec`\n",
+ "class. You are also likely to edit `Lab4.worksheet.sc` for any scratch\n",
+ "work. You can also use `Lab4.worksheet.ts` to write and experiment in a\n",
+ "JavaScript file that you can then parse into a TypeScripty AST (see\n",
+ "`Lab4.worksheet.sc`).\n",
+ "\n",
+ "If you like, you may use this notebook for experimentation. However,\n",
+ "**please make sure your code is in `Lab4.scala`; code in this notebook\n",
+ "will not graded.**\n",
+ "\n",
+ "## Static Typing: TypeScripty: Functions and Objects\n",
+ "\n",
+ "#### Static Typing\n",
+ "\n",
+ "As we have seen in the prior labs, dealing with coercions and checking\n",
+ "for dynamic type errors complicate the interpreter implementation (i.e.,\n",
+ "`step`). Some languages restrict the possible programs that it will\n",
+ "execute to ones that it can guarantee will not result in a dynamic type\n",
+ "error. This restriction of programs is enforced with an analysis phase\n",
+ "after parsing but before evalation known as *type checking*. Such\n",
+ "languages are called *statically-typed*. In this lab, we implement a\n",
+ "statically-typed version of JavaScripty that we affectionately call\n",
+ "TypeScripty. We will not permit *any* type coercions and simultaneously\n",
+ "guarantee the absence of dynamic type errors.\n",
+ "\n",
+ "#### Multi-Parameter Recursive Functions\n",
+ "\n",
+ "Using our skills working with higher-order functions on collections from\n",
+ "previous assignments, we now consider functions with zero-or-more\n",
+ "parameters (instead of exactly one):\n",
+ "\n",
+ "$$\n",
+ "\\begin{array}{rrrl}\n",
+ " \\text{types} & \\tau& \\mathrel{::=}& \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau'\n",
+ " \\\\\n",
+ " \\text{values} & v& \\mathrel{::=}& x^{?}\\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n",
+ " \\\\\n",
+ " \\text{expressions} & e& \\mathrel{::=}& \n",
+ " x^{?}\\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e_1\n",
+ " \\mid e_1\\texttt{(}e_2\\texttt{)}\n",
+ " \\\\\n",
+ " \\text{optional variables} & x^{?}& \\mathrel{::=}& x\\mid\\varepsilon \\\\\n",
+ " \\text{optional type annotations} & \\tau^{?}& \\mathrel{::=}& \\texttt{:}\\,\\tau \\mid\\varepsilon\n",
+ "\\end{array}\n",
+ "$$\n",
+ "\n",
+ "We write a sequence of things using either an overbar or dots (e.g.,\n",
+ "$\\overline{y}$ or $y_1, \\ldots, y_n$ for a sequence of variables).\n",
+ "Functions can now take any number of parameters\n",
+ "$\\overline{y\\texttt{:}\\,\\tau}$. We have a language of types $\\tau$ and\n",
+ "function parameters $\\overline{y}$ are annotated with types\n",
+ "$\\overline{\\tau}$.\n",
+ "\n",
+ "Functions can be named or unnamed $x^{?}$ and can be annotated with a\n",
+ "return type or unannotated $\\tau^{?}$. To define recursive functions,\n",
+ "the function needs to be named *and* annotated with a return type.\n",
+ "\n",
+ "To represent an arbitrary number of function parameters or function call\n",
+ "arguments in Scala, we use an appropriate `List`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "f5304f2a",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "trait Typ // t\n",
+ "case class TFun(yts: List[(String,Typ)], tret: Typ) extends Typ // t ::= (yts) => tret\n",
+ "\n",
+ "trait Expr // e\n",
+ "case class Fun(xopt: Option[String], yts: List[(String,Typ)], tretopt: Option[Typ], e1: Expr) extends Expr // e ::= xopt(yts)tretopt => e1\n",
+ "case class Call(e0: Expr, es: List[Expr]) extends Expr // e ::= e0(es)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "75c5ea82-615b-49d1-8c09-53c06ef581a6",
+ "metadata": {},
+ "source": [
+ "#### Immutable Objects (Records)\n",
+ "\n",
+ "Similarly, we now consider immutable objects that can have an arbitrary\n",
+ "number of fields: $$\n",
+ "\\begin{array}{rrrl}\n",
+ " \\text{types} & \\tau& \\mathrel{::=}&\n",
+ " \\texttt{\\{} \\overline{ f\\texttt{:}\\,\\tau } \\texttt{\\}} \n",
+ " \\\\\n",
+ " \\text{values} & v& \\mathrel{::=}&\n",
+ " \\texttt{\\{} \\overline{ f\\texttt{:}\\,v } \\texttt{\\}} \n",
+ " \\\\\n",
+ " \\text{expressions} & e& \\mathrel{::=}& \n",
+ " \\texttt{\\{} \\overline{ f\\texttt{:}\\,e } \\texttt{\\}} \n",
+ " \\mid e_1\\texttt{.}f\n",
+ "\\end{array}\n",
+ "$$\n",
+ "\n",
+ "An object literal expression $$\n",
+ "\\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,e_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_n\\texttt{:}\\,e_n\n",
+ "\\texttt{\\}}\n",
+ "$$ is a comma-separated sequence of field names with initialization\n",
+ "expressions surrounded by braces. Objects here are more like records in\n",
+ "other programming languages compared to actual JavaScript objects, as we\n",
+ "do not have any form of mutation or dynamic extension. Fields here\n",
+ "correspond to what JavaScript calls properties but which can be\n",
+ "dynamically added or removed from objects. We use the term fields to\n",
+ "emphasize that they are fixed based on their type: $$\n",
+ "\\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,e_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_n\\texttt{:}\\,e_n\n",
+ "\\texttt{\\}}\n",
+ "\\quad:\\quad\n",
+ "\\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,\\tau_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_n\\texttt{:}\\,\\tau_n\n",
+ "\\texttt{\\}}\n",
+ "$$\n",
+ "\n",
+ "Note that an object value is an object literal expression where each\n",
+ "field is a value:\n",
+ "\n",
+ "$$\n",
+ "\\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,v_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_n\\texttt{:}\\,v_n\n",
+ "\\texttt{\\}}\n",
+ "$$\n",
+ "\n",
+ "The field read expression $e_1\\texttt{.}f$ evaluates $e_1$ to an object\n",
+ "value and then looks up the field named $f$.\n",
+ "\n",
+ "To represent object types and object literal expressions in Scala, we\n",
+ "use an appropriate `Map`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "86680ee5",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "case class TObj(fts: Map[String, Typ]) extends Typ // t ::= { fts }\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": "bf3c7de8-bf8d-484a-a711-f072c8a00266",
+ "metadata": {},
+ "source": [
+ "Otherwise, we consider our base JavaScripty language that has numbers\n",
+ "with arithmetic expressions, booleans with logic and comparison\n",
+ "expressions, strings with concatenation, $\\mathbf{undefined}$ with\n",
+ "printing, and $\\mathbf{const}$-variable declarations. In summary, the\n",
+ "type language $\\tau$ includes base types for numbers, booleans, strings,\n",
+ "and $\\mathbf{undefined}$, as well as constructed types for functions and\n",
+ "objects described above:\n",
+ "\n",
+ "$$\n",
+ "\\begin{array}{rrrl}\n",
+ " \\text{types} & \\tau& \\mathrel{::=}&\n",
+ " \\texttt{number}\n",
+ " \\mid\\texttt{bool}\n",
+ " \\mid\\texttt{string}\n",
+ " \\mid\\texttt{Undefined}\n",
+ " \\\\\n",
+ " & & \\mid&\n",
+ " \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau'\n",
+ " \\mid\\texttt{\\{} \\overline{ f\\texttt{:}\\,\\tau } \\texttt{\\}} \n",
+ "\\end{array}\n",
+ "$$\n",
+ "\n",
+ "As an aside, we have chosen a concrete syntax that is compatible with\n",
+ "the TypeScript language that adds typing to JavaScript. TypeScript is a\n",
+ "proper superset of JavaScript, so it is not as strictly typed as\n",
+ "TypeScripty is here in this lab.\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",
+ "$e \\longrightarrow e'$ on closed expressions. Because of the static type\n",
+ "checking, the reduction-step cases can be greatly simplified: we\n",
+ "eliminate performing all coercions, and whatā€™s cool is that we no longer\n",
+ "need to represent the possibility of a dynamic $\\mathsf{typeerror}$\n",
+ "(e.g., with a `Either[DynamicTypeError,Expr]`).\n",
+ "\n",
+ "We can use the more basic type signature for `step`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "d2d56168",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def step(e: Expr): Expr = ???"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "3a30f916-aa9c-4099-92ed-997b0ffa2257",
+ "metadata": {},
+ "source": [
+ "corresponding to the more basic judgment form $e \\longrightarrow e'$\n",
+ "(given in the subsequent sections).\n",
+ "\n",
+ "To make easier to identify implementation bugs, we introduce another\n",
+ "Scala exception type to throw when there is no possible next step."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "beefdd74",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "case class StuckError(e: Expr) extends Exception"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "ebecfd73-18ee-452c-aeff-1ba82e8042bc",
+ "metadata": {},
+ "source": [
+ "However, the intent of this exception is that it should get thrown at\n",
+ "run-time! If it does get thrown, that signals a bug in our interpreter\n",
+ "implementation rather than an error in the TypeScripty test input.\n",
+ "\n",
+ "In particular, if the TypeScripty expression `e` passed into `step` is\n",
+ "closed and well-typed (i.e., `inferType(e)` does not throw\n",
+ "`StaticTypeError`), then `step` should never throw a `StuckError`. This\n",
+ "property is *type safety*.\n",
+ "\n",
+ "Recall that to implement `step`, we need to implement a substitution\n",
+ "function `substitute` corresponding to ${}[v/x]e$ that we use to eagerly\n",
+ "apply variable bindings:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "79fd9c7b",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def substitute(v: Expr, x: String, e: Expr) = ???"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "dda62743-2c2a-456d-af69-18870ec54198",
+ "metadata": {},
+ "source": [
+ "#### Static Type Checking\n",
+ "\n",
+ "We implement a static type checker that up front rules out programs that\n",
+ "would get stuck in taking reduction steps. This type checker is very\n",
+ "similar to a big-step interpreter. Instead of computing the value of an\n",
+ "expression by recursively computing the value of each sub-expression, we\n",
+ "infer the type of an expression, by recursively inferring the type of\n",
+ "each sub-expression. An expression is *well-typed* if we can infer a\n",
+ "type for it.\n",
+ "\n",
+ "Given its similarity to big-step evaluation, we formalize a type\n",
+ "inference algorithm in a similar way. That is, we define the judgment\n",
+ "form $\\Gamma \\vdash e : \\tau$, which says, ā€œIn type environment\n",
+ "$\\Gamma$, expression $e$ has type $\\tau$.ā€ We then implement a function\n",
+ "`hastype`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "1d81aea1",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type TEnv = Map[String, Typ]\n",
+ "def hastype(tenv: TEnv, e: Expr): Typ = ???"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "c387e9c0-734d-4f96-bf23-adb03d0f6159",
+ "metadata": {},
+ "source": [
+ "that corresponds directly to this judgment form. It takes as input a\n",
+ "type environment `tenv: TEnv` ($\\Gamma$) and an expression `e: Expr`\n",
+ "($e$) to return a type `Typ` ($\\tau$). It is informative to compare the\n",
+ "rules defining typing with a big-step operational semantics.\n",
+ "\n",
+ "To signal a type error, we will use a Scala exception"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "68e6db00",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "case class StaticTypeError(tbad: Typ, esub: Expr, e: Expr) extends Exception"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "81f3fb8b-7772-41a0-91fb-5e284e7a46d3",
+ "metadata": {},
+ "source": [
+ "where `tbad` is the type that is inferred sub-expression `esub` of input\n",
+ "expression `e`. These arguments are used to construct a useful error\n",
+ "message. We also provide a helper function `err` to simplify throwing\n",
+ "this exception.\n",
+ "\n",
+ "While it is possible to implement iterative reduction via `step` and\n",
+ "type inference via`hastype` independently, it is generally easier to\n",
+ "ā€œincrementally grow the languageā€ by going language-feature\n",
+ "by-language-feature for all functions rather than function-by-function.\n",
+ "In the subsequent steps, we describe the small-step operational\n",
+ "semantics and the static typing semantics together incrementally by\n",
+ "language feature.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "For testing your implementation, there are some interface functions\n",
+ "defined that calls your `step` and `hastype` implementations with some\n",
+ "debugging information:\n",
+ "\n",
+ "- The `iterateStep: Expr => Expr` function repeatedly calls your\n",
+ " `step` implementation until reaching a value.\n",
+ "- The `inferType: Expr => Typ` function calls your `hastype` function\n",
+ " with an empty type environment.\n",
+ "\n",
+ "Note that the provided tests are minimal. **You will want to add your\n",
+ "own tests to cover most language features.**\n",
+ "\n",
+ "## 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 from previous assignments and\n",
+ "remove all coercions.\n",
+ "\n",
+ "$\\fbox{$e \\longrightarrow e'$}$\n",
+ "\n",
+ "$\\inferrule[DoNeg]{\n",
+ " n' = - n_1\n",
+ "}{\n",
+ " \\mathop{\\texttt{-}} n_1 \\longrightarrow n'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoArith]{\n",
+ " n' = n_1 \\mathbin{\\mathit{bop}}n_2\n",
+ " \\and\n",
+ " \\mathit{bop}\\in \\left\\{ \\texttt{+}, \\texttt{-}, \\texttt{*}, \\texttt{/} \\right\\}\n",
+ "}{\n",
+ " n_1 \\mathbin{\\mathit{bop}}n_2 \\longrightarrow n'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoPlusString]{\n",
+ " \\mathit{str}' = \\mathit{str}_1 \\mathit{str}_2\n",
+ "}{\n",
+ " \\mathit{str}_1 \\mathbin{\\texttt{+}} \\mathit{str}_2 \\longrightarrow\\mathit{str}'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoInequalityNumber]{\n",
+ " b' = n_1 \\mathbin{\\mathit{bop}}n_2\n",
+ " \\and\n",
+ " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n",
+ "}{\n",
+ " n_1 \\mathbin{\\mathit{bop}}n_2 \\longrightarrow b'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoInequalityString]{\n",
+ " b' = \\mathit{str}_1 \\mathbin{\\mathit{bop}}\\mathit{str}_2\n",
+ " \\and\n",
+ " \\mathit{bop}\\in \\left\\{ \\texttt{<}, \\texttt{<=}, \\texttt{>}, \\texttt{>=} \\right\\}\n",
+ "}{\n",
+ " \\mathit{str}_1 \\mathbin{\\mathit{bop}}\\mathit{str}_2 \\longrightarrow b'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoEquality]{\n",
+ " b' = (v_1 \\mathbin{\\mathit{bop}}v_2)\n",
+ " \\and\n",
+ " \\mathit{bop}\\in \\left\\{ \\texttt{===}, \\texttt{!==} \\right\\}\n",
+ "}{\n",
+ " v_1 \\mathbin{\\mathit{bop}}v_2 \\longrightarrow b'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoNot]{\n",
+ " b' = \\neg b_1\n",
+ "}{\n",
+ " \\mathop{\\texttt{!}} b_1 \\longrightarrow b'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoAndTrue]{\n",
+ "}{\n",
+ " \\mathbf{true} \\mathbin{\\texttt{\\&\\&}} e_2 \\longrightarrow e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoAndFalse]{\n",
+ "}{\n",
+ " \\mathbf{false} \\mathbin{\\texttt{\\&\\&}} e_2 \\longrightarrow v_1\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoOrTrue]{\n",
+ "}{\n",
+ " \\mathbf{true} \\mathbin{\\texttt{||}} e_2 \\longrightarrow v_1\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoOrFalse]{\n",
+ "}{\n",
+ " \\mathbf{false} \\mathbin{\\texttt{||}} e_2 \\longrightarrow e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoIfTrue]{\n",
+ "}{\n",
+ " \\mathbf{true}\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoIfFalse]{\n",
+ "}{\n",
+ " \\mathbf{false}\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_3\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoSeq]{\n",
+ "}{\n",
+ " v_1 \\mathbin{\\texttt{,}} e_2 \\longrightarrow e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoPrint]{\n",
+ " \\text{$v_1$ printed}\n",
+ "}{\n",
+ " \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}v_1\\texttt{)} \\longrightarrow\\mathbf{undefined}\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoConst]{\n",
+ "}{\n",
+ " \\mathbf{const}\\;x\\;\\texttt{=}\\;v_1\\texttt{;}\\;e_2 \\longrightarrow[v_1/x]e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchUnary]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " \\mathop{\\mathit{uop}}e_1 \\longrightarrow\\mathop{\\mathit{uop}}e_1'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchBinary1]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " e_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow e_1' \\mathbin{\\mathit{bop}}e_2\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchBinary2]{\n",
+ " e_2 \\longrightarrow e_2'\n",
+ "}{\n",
+ " v_1 \\mathbin{\\mathit{bop}}e_2 \\longrightarrow v_1 \\mathbin{\\mathit{bop}}e_2'\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchIf]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3 \\longrightarrow e_1'\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchPrint]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)} \\longrightarrow\\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1'\\texttt{)}\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchConst]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 \\longrightarrow\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1'\\texttt{;}\\;e_2 \n",
+ "}$\n",
+ "\n",
+ "FigureĀ 1: 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-lab-base-smallstep\"\n",
+ "class=\"quarto-xref\">FigureĀ 1</a> defining the reduction-step judgment\n",
+ "form $e \\longrightarrow e'$.\n",
+ "\n",
+ "Note that your task here is simpler than what you have done before in\n",
+ "previous assignments. There are no judgment forms or rules defining\n",
+ "coercions (e.g., `toBoolean`) or stepping to a $\\mathsf{typeerror}$\n",
+ "result (e.g., `Left(DynamicTypeError(e))`).\n",
+ "\n",
+ "You will need to implement a helper function `substitute` for base\n",
+ "TypeScripty to perform scope-respecting substitution ${}[v/x]e$ as in\n",
+ "previous assignments.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- You may use (or ignore) the provided helper function `doInequality`\n",
+ " to implement the $\\TirName{DoInequalityNumber}$ and\n",
+ " $\\TirName{DoInequalityString}$ rules.\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 declarations.\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[TypeVar]{\n",
+ "}{\n",
+ " \\Gamma \\vdash x : \\Gamma(x)\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[TypeConstDecl]{\n",
+ " \\Gamma \\vdash e_1 : \\tau_1\n",
+ " \\and\n",
+ " \\Gamma, x : \\tau_1 \\vdash e_2 : \\tau_2\n",
+ "}{\n",
+ " \\Gamma \\vdash \\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2 : \\tau_2\n",
+ "}$\n",
+ "\n",
+ "FigureĀ 2: 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}$-variable declarations.\n",
+ "\n",
+ "Observe how closely the $\\TirName{Type}$ rules align with the\n",
+ "$\\TirName{Do}$ rules in <a href=\"#fig-typescripty-lab-base-smallstep\"\n",
+ "class=\"quarto-xref\">FigureĀ 1</a>, except for having a big-step\n",
+ "evaluation structure with types.\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-lab-base-typing\"\n",
+ "class=\"quarto-xref\">FigureĀ 2</a> defining the typing judgment form\n",
+ "$\\Gamma \\vdash e : \\tau$."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "id": "ff9b4265",
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "type TEnv = Map[String, Typ]\n",
+ "def hastype(tenv: TEnv, e: Expr): Typ = ???"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5a767128-f0b7-4693-bd1a-03770652f972",
+ "metadata": {},
+ "source": [
+ "## Immutable Objects (Records)\n",
+ "\n",
+ "Next, we extend our interpreter implementation for immutable objects. We\n",
+ "consider the implementation for immutable objects next, as it is a bit\n",
+ "simpler than that for multi-parameter functions.\n",
+ "\n",
+ "### Small-Step Reduction\n",
+ "\n",
+ "We extend the reduction-step judgment form $e \\longrightarrow e'$ for\n",
+ "immutable objects:\n",
+ "\n",
+ "$\\fbox{$e \\longrightarrow e'$}$\n",
+ "\n",
+ "$\\inferrule[DoGetField]{\n",
+ "}{\n",
+ " \\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,v_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_i\\texttt{:}\\,v_i\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_n\\texttt{:}\\,v_n \\texttt{\\}}\n",
+ " \\texttt{.}f_i\n",
+ " \\longrightarrow\n",
+ " v_i\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchObject]{\n",
+ " e_i \\longrightarrow e_i'\n",
+ " \\and\n",
+ " e_j = v_j\n",
+ " \\and\n",
+ " \\text{for all $j < i$}\n",
+ "}{\n",
+ " \\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,e_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_i\\texttt{:}\\,e_i\\texttt{,}\n",
+ " \\ldots\n",
+ " \\texttt{\\}}\n",
+ " \\longrightarrow\n",
+ " \\texttt{\\{}\n",
+ " f_1\\texttt{:}\\,e_1\\texttt{,}\n",
+ " \\ldots\\texttt{,}\n",
+ " f_i \\mathbin{\\texttt{:}} e_i'\\texttt{,}\n",
+ " \\ldots\n",
+ " \\texttt{\\}}\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[SearchGetField]{\n",
+ " e_1 \\longrightarrow e_1'\n",
+ "}{\n",
+ " e_1\\texttt{.}f\n",
+ " \\longrightarrow\n",
+ " e_1'\\texttt{.}f\n",
+ "}$\n",
+ "\n",
+ "FigureĀ 3: Small-step operational semantics of TypeScripty with immutable\n",
+ "objects.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 3 (Small-Step Reduction for\n",
+ "Immutable Objects)**</span> Implement the cases in `step` for reducing\n",
+ "immutable object expressions using the rules given in\n",
+ "<a href=\"#fig-typescripty-lab-objects-smallstep\"\n",
+ "class=\"quarto-xref\">FigureĀ 3</a> for the reduction-step judgment form\n",
+ "$e \\longrightarrow e'$.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- Field names $f$ are different than variable names $x$, even though\n",
+ " they are both represented in Scala with a `String`. Object\n",
+ " expressions are not variable binding constructsā€”what does that mean\n",
+ " about `substitute` for them?\n",
+ "\n",
+ "- For $\\TirName{SearchObject}$, you should make the reduction step\n",
+ " apply to the first non-value as given by the left-to-right iteration\n",
+ " of the collection using the `find` method on `Map`s:\n",
+ "\n",
+ " ``` scala\n",
+ " (m: Map[K,V]).find(f: ((K,V)) => Boolean): Option[(K,V)]\n",
+ " ```\n",
+ "\n",
+ "- Other helpful Scala library methods not previously mentioned to use\n",
+ " here include the following:\n",
+ "\n",
+ " ``` scala\n",
+ " (m: Map[K,V]).get(k: K): Option[V]\n",
+ " ```\n",
+ "\n",
+ "### Static Type Checking\n",
+ "\n",
+ "We extend the static typing judgment form $\\Gamma \\vdash e : \\tau$ for\n",
+ "immutable objects:\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Ā 4: Typing of TypeScripty with immutable objects.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 4 (Static Type Checking for\n",
+ "Immutable Objects)**</span> Implement the cases in `hastype` for typing\n",
+ "immutable object expressions using the rules given in\n",
+ "<a href=\"#fig-typescripty-lab-objects-typing\"\n",
+ "class=\"quarto-xref\">FigureĀ 4</a> defining the typing judgment form\n",
+ "$\\Gamma \\vdash e : \\tau$.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- Other helpful Scala library methods not previously mentioned to use\n",
+ " here include the following:\n",
+ "\n",
+ " ``` scala\n",
+ " (m: Map[K,V]).map(f: ((K,V)) => (J,U)): Map[J,U]\n",
+ " ```\n",
+ "\n",
+ "## Multi-Parameter Recursive Functions\n",
+ "\n",
+ "Finally, we extend our interpreter implementation for multi-parameter\n",
+ "recursive functions.\n",
+ "\n",
+ "### Small-Step Reduction\n",
+ "\n",
+ "We extend the reduction-step judgment form $e \\longrightarrow e'$ for\n",
+ "multi-paramter recursive functions:\n",
+ "\n",
+ "$\\fbox{$e \\longrightarrow e'$}\n",
+ "\\quad$\n",
+ "\n",
+ "$\\inferrule[DoCall]{\n",
+ "}{ (\\texttt{(} y_1\\texttt{:}\\,\\tau_1\\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\,\\tau_n \\texttt{)}\\tau^{?} \\mathrel{\\texttt{=}\\!\\texttt{>}} e)\n",
+ " \\texttt{(}v_1, \\ldots v_n\\texttt{)}\n",
+ " \\longrightarrow\n",
+ " [v_n/y_n]\\cdots[v_1/y_1]e\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[DoCallRec]{\n",
+ " v= (x\\texttt{(} y_1\\texttt{:}\\,\\tau_1\\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\,\\tau_n \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e)\n",
+ "}{\n",
+ " v\\texttt{(}v_1, \\ldots v_n\\texttt{)}\n",
+ " \\longrightarrow\n",
+ " [v/x][v_n/y_n]\\cdots[v_1/y_1]e\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",
+ "$\\inferrule[SearchCall2]{\n",
+ " e_i \\longrightarrow e_i'\n",
+ " \\and\n",
+ " e_j = v_j\n",
+ " \\and\n",
+ " \\text{for all $j < i$}\n",
+ "}{\n",
+ " v\\texttt{(}e_1, \\ldots, e_i, \\ldots, e_n\\texttt{)}\n",
+ " \\longrightarrow\n",
+ " v\\texttt{(}e_1, \\ldots, e_i', \\ldots, e_n\\texttt{)}\n",
+ "}$\n",
+ "\n",
+ "FigureĀ 5: Small-step operational semantics for TypeScripty with\n",
+ "multi-parameter recursive functions.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 5 (Small-Step Reduction for\n",
+ "Multi-Parameter Recursive Functions)**</span> Implement the cases in\n",
+ "`step` for reducing multi-parameter recursive functions using the rules\n",
+ "given in <a href=\"#fig-typescripty-lab-functions-smallstep\"\n",
+ "class=\"quarto-xref\">FigureĀ 5</a> for the reduction-step judgment form\n",
+ "$e \\longrightarrow e'$.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- Other helpful Scala library methods not previously mentioned to use\n",
+ " here include the following:\n",
+ "\n",
+ " ``` scala\n",
+ " (l: List[A]).map(f: A => B): List[B]\n",
+ " (l: List[A]).exists(f: A => Boolean): Boolean\n",
+ " (la: List[A]).zip(lb: List[B]): List[(A,B)]\n",
+ " (l: List[A]).forall(f: A => Boolean): Boolean\n",
+ " (l: List[A]).foldRight(f: (A,B) => B): B\n",
+ " ```\n",
+ "\n",
+ " - You may want to use the `zip` method for the $\\TirName{DoCall}$\n",
+ " and $\\TirName{DoCallRec}$ cases to match up formal parameters\n",
+ " and actual arguments.\n",
+ "\n",
+ "- You might want to use your `mapFirst` function from Homework 4 here.\n",
+ "\n",
+ "### Static Type Checking\n",
+ "\n",
+ "We extend the static typing judgment form $\\Gamma \\vdash e : \\tau$ for\n",
+ "multi-parameter recursive functions:\n",
+ "\n",
+ "$\\inferrule[TypeCall]{\n",
+ " \\Gamma \\vdash e : \\texttt{(} y_1\\texttt{:}\\,\\tau_1\\texttt{,}\\ldots\\texttt{,}y_n\\texttt{:}\\,\\tau_n \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau \n",
+ " \\and\n",
+ " \\Gamma \\vdash e_1 : \\tau_1\n",
+ " \\quad\\cdots\\quad\n",
+ " \\Gamma \\vdash e_n : \\tau_n\n",
+ "}{\n",
+ " \\Gamma \\vdash e\\texttt{(}e_1, \\ldots, e_n\\texttt{)} : \\tau\n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[TypeFunction]{\n",
+ " \\Gamma, y_1 : \\tau_1, \\cdots, , y_n : \\tau_n \\vdash e' : \\tau'\n",
+ "}{\n",
+ " \\Gamma \\vdash \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[TypeFunctionAnn]{\n",
+ " \\Gamma, y_1 : \\tau_1, \\cdots, , y_n : \\tau_n \\vdash e' : \\tau'\n",
+ "}{\n",
+ " \\Gamma \\vdash \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n",
+ "}$\n",
+ "\n",
+ "$\\inferrule[TypeFunctionRec]{\n",
+ " \\Gamma, x : \\tau_x , y_1 : \\tau_1, \\cdots, , y_n : \\tau_n \\vdash e' : \\tau'\n",
+ " \\and\n",
+ " \\tau_x = \\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\mathrel{\\texttt{=}\\!\\texttt{>}} \\tau' \n",
+ "}{\n",
+ " \\Gamma \\vdash x\\texttt{(} \\overline{y\\texttt{:}\\,\\tau} \\texttt{)} \\texttt{:}\\,\\tau' \\mathrel{\\texttt{=}\\!\\texttt{>}} e' : \\tau_x \n",
+ "}$\n",
+ "\n",
+ "FigureĀ 6: Typing of TypeScripty with multi-parameter recursive\n",
+ "functions.\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 6 (Static Type Checking for\n",
+ "Immutable Objects)**</span> Implement the cases in `hastype` for typing\n",
+ "multi-parameter recursive function expressions using the rules given in\n",
+ "<a href=\"#fig-typescripty-lab-functions-typing\"\n",
+ "class=\"quarto-xref\">FigureĀ 6</a> defining the typing judgment form\n",
+ "$\\Gamma \\vdash e : \\tau$.\n",
+ "\n",
+ "#### Notes\n",
+ "\n",
+ "- Other helpful Scala library methods not previously mentioned to use\n",
+ " here include the following:\n",
+ "\n",
+ " ``` scala\n",
+ " (l: List[A]).foldLeft(f: (B,A) => B): B\n",
+ " (l: List[A]).foreach(f: A => Unit): Unit\n",
+ " (l: List[A]).length: Int\n",
+ " (m1: Map[K,V]).++(m2: Map[K,V]): Map[K,V]\n",
+ " ```\n",
+ "\n",
+ " - The `++` method on `Map`s appends two `Map`s together."
+ ]
+ }
+ ],
+ "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
+}