diff options
Diffstat (limited to 'lab2/variables-values-lab.ipynb')
-rw-r--r-- | lab2/variables-values-lab.ipynb | 1336 |
1 files changed, 1336 insertions, 0 deletions
diff --git a/lab2/variables-values-lab.ipynb b/lab2/variables-values-lab.ipynb new file mode 100644 index 0000000..0a7619a --- /dev/null +++ b/lab2/variables-values-lab.ipynb @@ -0,0 +1,1336 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "e5c7e407-80c5-4211-9055-d94737de0b8d", + "metadata": {}, + "source": [ + "$\\newcommand{\\TirName}[1]{\\text{\\small #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: Basic Values, Variables, and Judgments\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", + "### Learning Goals\n", + "\n", + "The primary learning goals of this assignment are to build intuition for\n", + "the following:\n", + "\n", + "- the distinction between concrete and abstract syntax;\n", + "- the relationship between judgment forms/inference rules/judgments\n", + " and implementation code;\n", + "- using a reference implementation as a definition of semantics;\n", + "- variable binding and variable environments.\n", + "\n", + "Functional Programming Skills \n", + "Recursion over abstract syntax. Representation invariants.\n", + "\n", + "Programming Language Ideas \n", + "Inductive definitions (grammars/productions/sentences and judgment\n", + "forms/inference rules/judgments). Semantics (via detective work).\n", + "\n", + "### Instructions\n", + "\n", + "A version of project files for this lab resides in the public\n", + "[pppl-lab2](https://github.com/csci3155/pppl-lab2) 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 `Lab2.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 `Lab2Spec.scala` file. In the\n", + "`Lab2Spec.scala`, there is empty test class `Lab2StudentSpec` that you\n", + "can use to separate your tests from the given tests in the `Lab2Spec`\n", + "class. You are also likely to edit `Lab2.worksheet.sc` for any scratch\n", + "work. You can also use `Lab2.worksheet.js` to write and experiment in a\n", + "JavaScript file that you can then parse into a JavaScripty AST (see\n", + "`Lab2.worksheet.sc`).\n", + "\n", + "If you like, you may use this notebook for experimentation. However,\n", + "**please make sure your code is in `Lab2.scala`; this notebook will not\n", + "graded.**\n", + "\n", + "Recall that you need to switch kernels between running JavaScript and\n", + "Scala cells.\n", + "\n", + "## Interpreter: JavaScripty Calculator\n", + "\n", + "In this lab, we extend JavaScripty with additional value types and\n", + "variable binding. That is, the culmination of the lab is to implement an\n", + "interpreter for the subset of JavaScript with numbers, booleans,\n", + "strings, the undefined value, and variable binding." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "id": "fc23196d", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Expr</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">N</span>\n", + "defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()</pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "trait Expr // e ::=\n", + "case class N(n: Double) extends Expr // n\n", + "\n", + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "id": "3615c99b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "a2f3b886-b8d3-482d-aac1-088e998593d0", + "metadata": {}, + "source": [ + "We leave the `Expr` inductive data type mostly undefined for the moment\n", + "to focus on the type of `eval`.\n", + "\n", + "First, observe that the return type of `eval` is an `Expr` (versus\n", + "`Double` in the previous lab), as we now have more value types. However,\n", + "`eval` should return an `Expr` that is a JavaScripty value (i.e., is an\n", + "$e$ `: Expr` such that `isValue(` $e$ `)` returns `true`). The need for\n", + "the object-language versus meta-language distinction is even more\n", + "salient here than in the previous lab. For example, it is critical to\n", + "keep straight that `N(1.0)` is the Scala value representing the\n", + "JavaScripty value `1.0`.\n", + "\n", + "Second, observe that the `eval` function takes a JavaScripty value\n", + "environment `env: Env` to give meaning to free JavaScripty variables in\n", + "`e`.\n", + "\n", + "These ideas take unpacking, so let us start from the arithmetic\n", + "sub-language of JavaScripty:" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "id": "9088c943", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Unary</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Binary</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Uop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Neg</span>\n", + "defined <span class=\"ansi-green-fg\">trait</span> <span class=\"ansi-cyan-fg\">Bop</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Plus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Minus</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Times</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Div</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Unary(uop: Uop, e1: Expr) extends Expr // e ::= uop e1\n", + "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2\n", + "\n", + "trait Uop // uop ::=\n", + "case object Neg extends Uop // -\n", + "\n", + "trait Bop // bop ::=\n", + "case object Plus extends Bop // +\n", + "case object Minus extends Bop // | -\n", + "case object Times extends Bop // | *\n", + "case object Div extends Bop // | /" + ] + }, + { + "cell_type": "markdown", + "id": "44fff901-f124-48fc-bd1d-906b79120db5", + "metadata": {}, + "source": [ + "Thus far, we have considered only one type of value in our JavaScripty\n", + "object language: numbers $n$ (which we have considered double-precision\n", + "floating-point numbers). Specifically, we have stated the following:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& v\n", + "\\\\\n", + "\\text{values} & v& \\mathrel{::=}& n\n", + "\\end{array}\n", + "$$\n", + "\n", + "Recall from our preliminary discussion about evaluation\n", + "(**?@sec-evaluation-preliminaries**) that the computational model is a\n", + "rewriting or reduction of expressions until reaching values. A value is\n", + "simply an expression that cannot be reduced any further. Thus, we can\n", + "also consider a unary judgment form $e\\;\\mathsf{value}$ that judges when\n", + "an expression is a value. $$\n", + "\\infer[NumVal]{\n", + "}{\n", + " n\\;\\mathsf{value}\n", + "}\n", + "$$\n", + "\n", + "This judgment form corresponds to the `isValue` function:" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "id": "bbf7152f", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "8dade6b2-d9fb-47a9-91fd-0e2b6aff8f0a", + "metadata": {}, + "source": [ + "From our discussion on grammars and inference rules\n", + "(**?@sec-grammars-and-inference-rules**), we can see this unary judgment\n", + "form $e\\;\\mathsf{value}$ as defining a syntactic category values $v$.\n", + "Thus, we freely write grammar productions for $v$ to define the judgment\n", + "form $e\\;\\mathsf{value}$.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 1**</span> For this part of the\n", + "lab, implement `eval` for the calculator language above (which is the\n", + "same language as in the previous lab) but now with type\n", + "`(Env, Expr) => Expr`." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "id": "4c173e3a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "aa64c2db-875f-4d68-a8e9-61eb3951c890", + "metadata": {}, + "source": [ + "You will not use the `env` parameter yet. You will want to check that\n", + "your implementation returns JavaScripty values. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "id": "f88d8980", + "metadata": {}, + "outputs": [], + "source": [ + "val e_oneplustwo = Binary(Plus, N(1), N(2))\n", + "assert( isValue( eval(empty, e_oneplustwo) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "9bffa2f5-4fec-43f1-a871-322dd100c795", + "metadata": {}, + "source": [ + "## Coercions: Basic Values\n", + "\n", + "### Booleans, Strings, and Undefined\n", + "\n", + "Like most other languages, JavaScript has other basic value types. Let\n", + "us extend JavaScripty with Booleans, strings, and the\n", + "$\\mathbf{undefined}$ value:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{values} & v& \\mathrel{::=}&\n", + "b\n", + " \\mid\\mathit{str}\n", + " \\mid\\mathbf{undefined}\n", + "\\\\\n", + "\\text{booleans} & b\n", + "\\\\\n", + "\\text{strings} & \\mathit{str}\n", + "\\end{array}\n", + "$$\n", + "\n", + "Boolean values $b$ are the literals $\\mathbf{true}$ and\n", + "$\\mathbf{false}$. String values $\\mathit{str}$ are string literals like\n", + "`\"hi\"` that we do not explicitly define here.\n", + "\n", + "The $\\mathbf{undefined}$ literal is a distinguished value that is\n", + "different than all other values. It is like the unit literal `()` in\n", + "Scala." + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "id": "67096a6c", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">B</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">S</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Undefined</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class B(b: Boolean) extends Expr // e ::= b\n", + "case class S(str: String) extends Expr // | str\n", + "case object Undefined extends Expr // | undefined" + ] + }, + { + "cell_type": "markdown", + "id": "e9e4fe7c-4dd9-4b7f-85ab-fcbe72cb0292", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hello\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> \"Hola\"\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> undefined\n", + "> ```\n", + "\n", + "We update our `isValue` function appropriately:" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "id": "11b7ec3b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">isValue</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def isValue(e: Expr): Boolean = e match {\n", + " case N(_) | B(_) | S(_) | Undefined => true\n", + " case _ => false\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "2e5c680f-3806-4f25-a0e0-c568a6935a69", + "metadata": {}, + "source": [ + "A good exercise here is to reflect on what this code translates to in\n", + "terms of additional inference rules for the $e\\;\\mathsf{value}$ judgment\n", + "form.\n", + "\n", + "### Expressions\n", + "\n", + "Each value type comes with some operations. Our abstract syntax tree has\n", + "two constructors for unary and binary expressions that are parametrized\n", + "by unary $\\mathit{uop}$ and binary $\\mathit{bop}$ operators,\n", + "respectively:\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}&\n", + " \\mid\\mathop{\\mathit{uop}} e_1\n", + " \\mid e_1 \\mathrel{\\mathit{bop}} e_2\n", + "\\end{array}\n", + "$$\n", + "\n", + "#### Numbers\n", + "\n", + "For example, numbers has\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}& \\texttt{-}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{+}\\mid\\texttt{-}\\mid\\texttt{*}\\mid\\texttt{/}\n", + "\\end{array}\n", + "$$\n", + "\n", + "that we considered previously.\n", + "\n", + "#### Booleans\n", + "\n", + "For booleans, we add unary negation $\\texttt{!}$ and binary conjunction\n", + "$\\texttt{\\&\\&}$ and disjunction $\\texttt{||}$. $$\n", + "\\begin{array}{rrrl}\n", + "\\text{unary operators} & \\mathit{uop}& \\mathrel{::=}&\n", + "\\texttt{!}\n", + "\\\\\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{\\&\\&}\n", + "\\mid\\texttt{||}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "id": "88028ed8", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Not</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">And</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Or</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Not extends Uop // uop ::= !\n", + "case object And extends Bop // bop ::= &&\n", + "case object Or extends Bop // | ||" + ] + }, + { + "cell_type": "markdown", + "id": "f21da0e4-59c4-4f78-bd80-ac09e77fa224", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> !true\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true && false\n", + "> ```\n", + ">\n", + "> ``` js\n", + "> true || false\n", + "> ```\n", + "\n", + "We also expect to be able to elimate booleans with a conditional\n", + "if-then-else expression: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& e_1\\;\\texttt{?}\\;e_2\\;\\texttt{:}\\;e_3\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "id": "05ea3d8a", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">If</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class If(e1: Expr, e2: Expr, e3: Expr) extends Expr // e ::= e1 ? e2 : e3" + ] + }, + { + "cell_type": "markdown", + "id": "6fe0176b-eb8a-4882-bd33-aa6e6065df6d", + "metadata": {}, + "source": [ + "We also expect to be able to compare values for equality and disquality\n", + "and numbers for inequality: $$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}&\n", + "\\texttt{===}\n", + "\\mid\\texttt{!==}\n", + "\\mid\\texttt{<}\n", + "\\mid\\texttt{<=}\n", + "\\mid\\texttt{>}\n", + "\\mid\\texttt{>=}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "id": "47b3dc58", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Eq</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ne</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Lt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Le</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Gt</span>\n", + "defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Ge</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Eq extends Bop // bop ::= ===\n", + "case object Ne extends Bop // | !==\n", + "case object Lt extends Bop // | <\n", + "case object Le extends Bop // | <=\n", + "case object Gt extends Bop // | >\n", + "case object Ge extends Bop // | >=" + ] + }, + { + "cell_type": "markdown", + "id": "ebd33875-524f-4966-96f9-2c1614fef714", + "metadata": {}, + "source": [ + "#### Strings\n", + "\n", + "The one string operation we support in JavaScripty is string\n", + "concatenation. In JavaScript, string concatenation is written with the\n", + "binary operator `+`, so we do not need to extend the syntax.\n", + "\n", + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> \"Hello\" + \", \" + \"World\" + \"!\"\n", + "> ```\n", + "\n", + "#### Undefined\n", + "\n", + "As $\\mathbf{undefined}$ corresponds to unit `()` in Scala and is\n", + "uninteresting in itself, we add a side-effecting expression that prints\n", + "to console.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& \\texttt{console}\\texttt{.}\\texttt{log}\\texttt{(}e_1\\texttt{)}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "id": "226c53fa", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Print</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Print(e1: Expr) extends Expr // e ::= console.log(e1)" + ] + }, + { + "cell_type": "markdown", + "id": "afc77e07-23e1-4c34-9f2e-1a4c7c5f5b4e", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> console.log(\"Hello, World!\")\n", + "> ```\n", + "\n", + "If we now have side-effecting expressions, then we would expect to have\n", + "a way to sequence executing expressions for their effects.\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{binary operators} & \\mathit{bop}& \\mathrel{::=}& \\texttt{,}\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "id": "4c211bca", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">object</span> <span class=\"ansi-cyan-fg\">Seq</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case object Seq extends Bop // bop ::= ," + ] + }, + { + "cell_type": "markdown", + "id": "579a39c5-348a-46e4-b706-a86e0fbfc617", + "metadata": {}, + "source": [ + "> **Examples**\n", + ">\n", + "> ``` js\n", + "> undefined, 3\n", + "> ```\n", + "\n", + "### Semantics Detective: JavaScript is Bananas\n", + "\n", + "In the above, we have carefully specified the abstract syntax of the\n", + "object language of interest and informally discussed its semantics. But\n", + "if we are to implement an interpreter in the `eval` function, we also\n", + "need to define its semantics! And we give a precise definition as\n", + "follows:\n", + "\n", + "> **Important**\n", + ">\n", + "> In this lab, the semantics of a JavaScripty expression $e$ is defined\n", + "> by the evaluation of it as a JavaScript program.\n", + "\n", + "Given the careful specification of the abstract syntax, a natural\n", + "question to ask is whether all abstract syntax trees of type `Expr` in\n", + "the above are valid expressions and have a semantics in JavaScript (and\n", + "hence JavaScripty). Is `3 + true` a valid expression?" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3e3c4c0b-3d04-40c6-b11a-8ab618b54796", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "3 + true" + ] + }, + { + "cell_type": "markdown", + "id": "7af09a5d-90d7-4284-b408-51098a6bc898", + "metadata": {}, + "source": [ + "We try it out and see that yes it is. One aspect that makes the\n", + "JavaScript specification interesting is the presence of implicit\n", + "coercions (e.g., non-numeric values, such as booleans or strings, may be\n", + "implicitly converted to numeric values depending on the context in which\n", + "they are used).\n", + "\n", + "You might guess that defining coercions between value types can lead to\n", + "some interesting semantics. It is because of these coercions that we\n", + "have the meme that “JavaScript is bananas.”" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0bbdf44a-efd4-42e7-ab8b-3e58b85414dd", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "\"b\" + \"a\" + \"n\" + - \"a\" + \"a\" + \"s\"" + ] + }, + { + "cell_type": "markdown", + "id": "a614770c-4f97-4e4b-8ffa-83c4ee7a535b", + "metadata": {}, + "source": [ + "Armed with knowledge that in JavaScript, numbers are floating-point\n", + "numbers, the `+` operator in JavaScript is overloaded for strings and\n", + "numbers, and coercions happen between value types, see if you can\n", + "explain what is happening in the “bananas” expression above.\n", + "\n", + "#### Coercions\n", + "\n", + "Our `eval` function interpreter will need to make use of three helper\n", + "functions for converting values to numbers, booleans, and strings:" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "id": "76e48b08", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toNumber</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toBoolean</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">toStr</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def toNumber(v: Expr): Double = ???\n", + "def toBoolean(v: Expr): Boolean = ???\n", + "def toStr(v: Expr): String = ???" + ] + }, + { + "cell_type": "markdown", + "id": "877ad7ab-c025-46d1-8597-a2dc7960e167", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 2**</span> Write at least 1\n", + "JavaScript expression that shows a coercion from a non-numeric value to\n", + "a number and see what the result should be:" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ecf717e2-a8a2-4163-a2fc-626d3c32614c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "markdown", + "id": "c2e075a3-d8c2-4d4d-b50c-3b05446e7138", + "metadata": {}, + "source": [ + "Then, translate this JavaScript expression (written in concrete syntax)\n", + "into an `Expr` value (i.e., a JavaScripty abstract syntax tree)." + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "id": "f2373c38", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "15ae65f0-171c-439e-8391-55db52bc29c7", + "metadata": {}, + "source": [ + "Finally, use this `Expr` as a unit test for `toNumber` in the\n", + "`Lab2StudentSpec` class in the `Lab2Spec.scala` file.\n", + "\n", + "``` scala\n", + "val e_toNumber_test1 = ???\n", + "\"toNumber\" should s\"${e_toNumber_test1}\" in {\n", + " assertResult(???) { toNumber(e_toNumber_test1) }\n", + "}\n", + "```\n", + "\n", + "<span class=\"theorem-title\">**Exercise 3**</span> Do the same to create\n", + "a `toBoolean` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-boolean value to a boolean, see what the result\n", + "should be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2028060d-7a15-4b27-9153-4acb2911dcce", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "id": "2eb72698", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "6e8628d8-49de-4749-8c8c-c3e9a5ae2569", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 4**</span> Do the same to create\n", + "a `toStr` test. Write at least 1 JavaScript expression that shows a\n", + "coercion from a non-string value to a string, see what the result should\n", + "be, translate it to an `Expr` value, and add it as test in\n", + "`Lab2StudentSpec`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "09a51a9d-f222-4462-b99e-2237d3d7e76c", + "metadata": {}, + "outputs": [ + { + "data": {}, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "// YOUR CODE HERE\n", + "undefined" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "id": "2b0d83e9", + "metadata": {}, + "outputs": [], + "source": [ + "???" + ] + }, + { + "cell_type": "markdown", + "id": "b0804229-2e80-4c50-b10d-45bae14ac467", + "metadata": {}, + "source": [ + "<span class=\"theorem-title\">**Exercise 5**</span> Implement `toNumber`,\n", + "`toBoolean`, and `toStr` in `Lab2.scala` (using test-driven development\n", + "with the test cases you have written above).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 6**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "booleans, strings, the undefined value, and printing." + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "id": "d4af7b6b", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "59a41a5f-f9c2-472c-a3e8-ed1d1511985c", + "metadata": {}, + "source": [ + "You still will not use the `env` parameter yet. You again will want to\n", + "check that your implementation returns JavaScripty values using the\n", + "latest `isValue`. For example," + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "2913288e", + "metadata": {}, + "outputs": [], + "source": [ + "val e_nottrue = Unary(Not, B(true))\n", + "assert( isValue( eval(empty, e_nottrue) ) )" + ] + }, + { + "cell_type": "markdown", + "id": "5d9adaaa-44a9-4020-a559-e61e98217282", + "metadata": {}, + "source": [ + "## Interpreter: JavaScripty Variables\n", + "\n", + "The final piece of this lab is to extend our interpreter with variable\n", + "uses and binding (cf. **?@sec-static-scoping**).\n", + "\n", + "$$\n", + "\\begin{array}{rrrl}\n", + "\\text{expressions} & e& \\mathrel{::=}& x\\mid\\mathbf{const}\\;x\\;\\texttt{=}\\;e_1\\texttt{;}\\;e_2\n", + "\\end{array}\n", + "$$" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "id": "9c0ab5cd", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">Var</span>\n", + "defined <span class=\"ansi-green-fg\">class</span> <span class=\"ansi-cyan-fg\">ConstDecl</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "case class Var(x: String) extends Expr // e ::= x\n", + "case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // | const x = e1; e2" + ] + }, + { + "cell_type": "markdown", + "id": "3753b5f9-3d1e-4ef3-9ca6-b016448b3fed", + "metadata": {}, + "source": [ + "Note that the above is the abstract syntax we consider for `ConstDecl`,\n", + "which is more flexible the concrete syntax for `const` allowed by\n", + "JavaScript (cf. )\n", + "\n", + "In this lab, we define a value environment as a map from variable names\n", + "to JavaScripty values, which we represent in Scala as a value of type\n", + "`Map[String, Expr]`. Note that representing variable names as Scala\n", + "`String`s here, and it is a representation invariant that the `Expr`s\n", + "must correspond to JavaScripty values." + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "id": "74452c05", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">type</span> <span class=\"ansi-cyan-fg\">Env</span>\n", + "<span class=\"ansi-cyan-fg\">empty</span>: <span class=\"ansi-green-fg\">Env</span> = <span class=\"ansi-yellow-fg\">Map</span>()\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">lookup</span>\n", + "defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">extend</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "type Env = Map[String, Expr]\n", + "val empty: Env = Map.empty\n", + "\n", + "def lookup(env: Env, x: String): Expr = env(x)\n", + "def extend(env: Env, x: String, v: Expr): Env = {\n", + " require(isValue(v))\n", + " env + (x -> v)\n", + "}" + ] + }, + { + "cell_type": "markdown", + "id": "abf51752-104b-4fe7-b3bb-56f2b30c651d", + "metadata": {}, + "source": [ + "We provide the above value and function bindings to interface with the\n", + "Scala standard library for `Map[String, Expr]` and maintain this\n", + "representation invariant. You may use the Scala standard library\n", + "directly if you wish, but we recommend that you just use these\n", + "interfaces, as they are all that you need and give you the safety of\n", + "enforcing the representation invariant. The `empty` value represents an\n", + "empty value environment, the `lookup` function gets the value bound to\n", + "the variable named by a given string, and the `extend` function extends\n", + "a given environment with a new variable binding.\n", + "\n", + "<span class=\"theorem-title\">**Exercise 7**</span> For this part of the\n", + "lab, extend your `eval` from\n", + "<a href=\"#exr-numbers-eval\" class=\"quarto-xref\">Exercise 1</a> for\n", + "variable uses (i.e., `Var`) and variable binding (i.e., `ConstDecl`). We\n", + "suggest you start by adding tests with variables uses and `const`\n", + "bindings to be able do test-driven development (see below)." + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "id": "cc90dc11", + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<pre>defined <span class=\"ansi-green-fg\">function</span> <span class=\"ansi-cyan-fg\">eval</span></pre>" + ] + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "def eval(env: Env, e: Expr): Expr = ???" + ] + }, + { + "cell_type": "markdown", + "id": "2bb3563b-1d34-4f4b-9feb-2b2c8b6f28df", + "metadata": {}, + "source": [ + "### Testing\n", + "\n", + "In this lab, we have carefully defined the syntax of the JavaScripty\n", + "variant of interest, and we have defined its semantics to be defined to\n", + "be the same as JavaScript. Thus, you can write any JavaScript program\n", + "within the syntax defined above to create test cases for your `eval`\n", + "function. Any of the above JavaScript examples could be used as test\n", + "cases. In some cases, you may want to write abstract syntax trees\n", + "directly in Scala (i.e., values of type `Expr`). In other cases, you can\n", + "use the provided JavaScripty parser to translate concrete syntax (i.e.,\n", + "values of type `String`) into abstract syntax (i.e., values of type\n", + "`Expr`).\n", + "\n", + "<span class=\"theorem-title\">**Exercise 8 (Optional)**</span> We give\n", + "some exercises below to explore this subset of JavaScripty that you can\n", + "then use as test cases that you add to your `Lab2StudentSpec`.\n", + "\n", + "#### Basic Arithmetic Operations" + ] + }, + { + "cell_type": "markdown", + "id": "a2c70244-56b8-4945-b53d-4be38c6ed6e3", + "metadata": {}, + "source": [ + "This program defines two constants, `x` and `y`, and calculates their\n", + "sum. It then logs the result `sum` to the console." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "862e000e-d1a1-4a25-b8bb-1983badfb81e", + "metadata": {}, + "outputs": [], + "source": [ + "const x = 10;\n", + "const y = 5;\n", + "const sum = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";\n", + "console.log(sum);" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5db48d42-a357-4957-bdd2-4436e69d521a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(sum === 15)" + ] + }, + { + "cell_type": "markdown", + "id": "369b9301-1017-497b-8175-0654a035b32e", + "metadata": {}, + "source": [ + "#### Conditional Expressions" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b8ae58be-e5bd-4d13-a6eb-6d6fffbd7f2a", + "metadata": {}, + "outputs": [], + "source": [ + "const a = 10;\n", + "const b = 20;\n", + "const max = \n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "fe6cbe1e-fc0b-4965-a09a-38adcee24776", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(max === 20)" + ] + }, + { + "cell_type": "markdown", + "id": "32479c1c-d55e-4d89-a4aa-89f58c7397a3", + "metadata": {}, + "source": [ + "#### Unary and Binary Operations\n", + "\n", + "This program checks if a number is positive using a unary negation `-`\n", + "and a binary relational operator." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "01bed277-7e0a-4ebb-8f85-3bc60ca4637f", + "metadata": {}, + "outputs": [], + "source": [ + "const num = -5;\n", + "const isPositive =\n", + " // YOUR CODE HERE (replace undefined)\n", + " undefined\n", + ";" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2547e992-8b43-4944-bce3-045f9a03807a", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(isPositive === false)" + ] + }, + { + "cell_type": "markdown", + "id": "36cab120-2f06-4f1b-a68a-e51ca556cf97", + "metadata": {}, + "source": [ + "#### Undefined\n", + "\n", + "This program demonstrates the correspondence between `undefined` in\n", + "JavaScript and `()`." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1896f8d4-2fe1-4204-8405-a1a678c70ffe", + "metadata": {}, + "outputs": [], + "source": [ + "const r = console.log(\"Hello\");" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b4138580-25dc-4101-9f30-968ad136a1ee", + "metadata": {}, + "outputs": [], + "source": [ + "console.assert(r === undefined)" + ] + }, + { + "cell_type": "markdown", + "id": "b97d1faf-fb1f-4626-b1c6-405e1fc11ee8", + "metadata": {}, + "source": [ + "## Submission\n", + "\n", + "If you are a University of Colorado Boulder student, we use Gradescope\n", + "for assignment submission. In summary,\n", + "\n", + "- [ ] Create a private GitHub repository by clicking on a GitHub\n", + " Classroom link from the corresponding Canvas assignment entry.\n", + "- [ ] Clone your private GitHub repository to your development\n", + " environment (using the `<> Code` button on GitHub to get the\n", + " repository URL).\n", + "- [ ] Work on this lab from your cloned repository. Use Git to save\n", + " versions on GitHub (e.g., `git add`, `git commit`, `git push` on the\n", + " command line or via VSCode).\n", + "- [ ] Submit to the corresponding Gradescope assignment entry for\n", + " grading by choosing GitHub as the submission method.\n", + "\n", + "You need to have a GitHub identity and must have your full name in your\n", + "GitHub profile in case we need to associate you with your submissions." + ] + } + ], + "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.4" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |