diff options
author | Jack Sangdahl <[email protected]> | 2024-12-12 21:03:17 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-12 21:03:17 -0700 |
commit | ae554ab7d4d425fa821c1167e734db3425a881f6 (patch) | |
tree | 0962144c05070d5cf4303133c8e5ccd756d4cee9 | |
parent | 08f9cae13d0dce99d40a6d93432a84cb075bebfc (diff) | |
download | csci3155-ae554ab7d4d425fa821c1167e734db3425a881f6.tar.gz csci3155-ae554ab7d4d425fa821c1167e734db3425a881f6.zip |
Unit 4
Signed-off-by: Jack Sangdahl <[email protected]>
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 +} |