csci3155

{
 "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
}