CSCI3155_Assignment3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. **Restart the kernel and run all cells** (in the menubar, select Kernel$\\rightarrow$Restart & Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE ???` or \"YOUR ANSWER HERE\", as well as your name below:\n",
    "\n",
    "---\n",
    "\n",
    "__Lucas Laughlin__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ab627712e1367302c90741029d2963fb",
     "grade": false,
     "grade_id": "cell-224ca5a0097f63b5",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CSCI 3155: Assignment 3 \n",
    "\n",
    "Topics covered: ASTs, pattern matching, higher order functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7f1326e22a77065e280ecdfc467fd178",
     "grade": false,
     "grade_id": "cell-7e3b987db2733a1c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mpassed\u001b[39m"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// TEST HELPER\n",
    "def passed(points: Int) {\n",
    "    require(points >=0)\n",
    "    if (points == 1) print(s\"\\n*** Tests Passed (1 point) ***\\n\")\n",
    "    else print(s\"\\n*** Tests Passed ($points points) ***\\n\")\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "26ace7386cc85ea26d596eaae182efc4",
     "grade": false,
     "grade_id": "cell-a3d45980c5a3961a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Problem 1 (15 points)\n",
    "\n",
    "Develop a switch statement for the `mython` (var) language developed in class. \n",
    "The syntax for the to be added switch statement is given in terms of additional rules that\n",
    "add to the existing definitions in the class notes.\n",
    "\n",
    "$$\\begin{array}{rcl}\n",
    "\\mathbf{Statement} & \\rightarrow & \\text{Switch}(\\mathbf{Expr},  \\mathbf{Case}* ) \\\\[5pt]\n",
    "\\mathbf{Case} & \\rightarrow & \\text{SwitchCase}(\\mathbf{Expr}, \\mathbf{Statement}* ) \\\\[5pt]\n",
    "& | & \\text{DefaultCase}(\\mathbf{Statement}*) \\\\\n",
    "\\end{array}$$\n",
    "\n",
    "The existing scala language definitions for `mython` are recalled for below from the class notes.\n",
    "\n",
    "\n",
    "Augment the definitions by adding the extra definitions to support switch statements. Please use\n",
    "the same constructor names as in the grammar: `Switch` for the switch statement and \n",
    "`SwitchCase` and `DefaultCase` for the two rules corresponding to the __Case__ specifications.\n",
    "\n",
    "For your convenience, the definitions used in the class are given. Add your solution at the end.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "35baabf92d3f5edf2b3565a2d45dcb73",
     "grade": false,
     "grade_id": "cell-a3a78387d2a93841",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConst\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIdent\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMinus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMult\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mDiv\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNegate\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mLog\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mExp\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSine\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCosine\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mCondExpr\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mConstTrue\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mConstFalse\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mGeq\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mLeq\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mEq\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mAnd\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mOr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNot\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mDeclaration\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mStatement\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mMythonProgram\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mProgram\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mVarDecl\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mAssignStmt\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mWhileStmt\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIfThenElseStmt\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mReturnStmt\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mCase\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSwitch\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSwitchCase\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mDefaultCase\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr\n",
    "case class Const(d: Double) extends Expr \n",
    "// 1. We cheated a bit and allowed all floating point numbers\n",
    "// Also, this deviates from the grammar\n",
    "case class Ident(s: String) extends Expr\n",
    "// 2. We allow any string to be an identifier for now instead of the regular expression shown in the grammar.\n",
    "case class Plus(e1: Expr, e2: Expr ) extends Expr\n",
    "case class Minus(e1: Expr, e2: Expr) extends Expr\n",
    "case class Mult(e1: Expr, e2: Expr) extends Expr\n",
    "case class Div(e1: Expr, e2: Expr) extends Expr\n",
    "case class Negate(e: Expr) extends Expr\n",
    "case class Log(e: Expr) extends Expr\n",
    "case class Exp(e: Expr) extends Expr\n",
    "case class Sine(e: Expr) extends Expr\n",
    "case class Cosine(e: Expr) extends Expr\n",
    "\n",
    "sealed trait CondExpr\n",
    "case object ConstTrue extends CondExpr\n",
    "case object ConstFalse extends CondExpr\n",
    "case class Geq(e1: Expr, e2: Expr) extends CondExpr\n",
    "case class Leq(e1: Expr, e2: Expr) extends CondExpr\n",
    "case class Eq(e1: Expr, e2: Expr) extends CondExpr\n",
    "case class And(c1: CondExpr, c2: CondExpr) extends CondExpr\n",
    "case class Or(c1: CondExpr, c2: CondExpr) extends CondExpr\n",
    "case class Not(c: CondExpr) extends CondExpr\n",
    "\n",
    "sealed trait Declaration\n",
    "sealed trait Statement\n",
    "sealed trait MythonProgram\n",
    "\n",
    "case class Program(decls: List[Declaration], stmts: List[Statement], returnAtEnd: Expr) extends MythonProgram // We stripped the ReturnStmt tag since it is redundant\n",
    "case class VarDecl(identifier: String, rhsExpr: Expr) extends Declaration\n",
    "case class AssignStmt(identifier: String, rhsExpr: Expr) extends Statement\n",
    "case class WhileStmt(cond: CondExpr, stmts: List[Statement]) extends Statement\n",
    "case class IfThenElseStmt(cond: CondExpr, stmtsThen: List[Statement], stmtsElse: List[Statement]) extends Statement\n",
    "case class ReturnStmt(retExpr: Expr) extends Statement\n",
    "\n",
    "sealed trait Case\n",
    "case class Switch(e: Expr, cases: List[Case]) extends Statement\n",
    "case class SwitchCase(e: Expr, stmts: List[Statement]) extends Case\n",
    "case class DefaultCase(stmts: List[Statement]) extends Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "2fa788028c84d1f03efa6f3f385a2f2f",
     "grade": true,
     "grade_id": "cell-b4433298fac96b06",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (5 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m))))\n",
       ")\n",
       "\u001b[36mstmt1\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n",
       "  \u001b[32m\"x\"\u001b[39m,\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       ")\n",
       "\u001b[36mcond1\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m))\n",
       "\u001b[36mstmt2\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mcond2\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m))\n",
       "\u001b[36mstmt3\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mifStmt\u001b[39m: \u001b[32mIfThenElseStmt\u001b[39m = \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "  \u001b[33mList\u001b[39m()\n",
       ")\n",
       "\u001b[36mwhileStmt\u001b[39m: \u001b[32mWhileStmt\u001b[39m = \u001b[33mWhileStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "    \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "      \u001b[33mList\u001b[39m()\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mallstmts\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mProduct\u001b[39m with \u001b[32mSerializable\u001b[39m with \u001b[32mStatement\u001b[39m] = \u001b[33mList\u001b[39m(\n",
       "  \u001b[33mAssignStmt\u001b[39m(\n",
       "    \u001b[32m\"x\"\u001b[39m,\n",
       "    \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "  ),\n",
       "  \u001b[33mWhileStmt\u001b[39m(\n",
       "    \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "    \u001b[33mList\u001b[39m(\n",
       "      \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "      \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "        \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "        \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "        \u001b[33mList\u001b[39m()\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mretExpr\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))\n",
       "\u001b[36mc1\u001b[39m: \u001b[32mSwitchCase\u001b[39m = \u001b[33mSwitchCase\u001b[39m(\n",
       "  \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\n",
       "      \u001b[32m\"x\"\u001b[39m,\n",
       "      \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "    ),\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "  )\n",
       ")\n",
       "\u001b[36mc3\u001b[39m: \u001b[32mSwitchCase\u001b[39m = \u001b[33mSwitchCase\u001b[39m(\n",
       "  \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\n",
       "      \u001b[32m\"x\"\u001b[39m,\n",
       "      \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "    ),\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "    \u001b[33mWhileStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "        \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "          \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "          \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "          \u001b[33mList\u001b[39m()\n",
       "        )\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e1 = Plus(Ident(\"y\"), Plus( Ident(\"z\"), Exp( Minus(Ident(\"x\"), Ident(\"y\")) ) )) // y + z + exp(x - y)\n",
    "val stmt1 = AssignStmt(\"x\", e1) // x = y + z + exp(x - y)\n",
    "// Let us make up the parts of the while statement\n",
    "val cond1 = Leq(Ident(\"y\"), Const(15.0f)) // y <= 15\n",
    "// The assignment inside the while\n",
    "val stmt2 = AssignStmt(\"y\", Minus(Ident(\"y\"), Ident(\"x\"))) // y = y - x\n",
    "// The condition for the if statement\n",
    "val cond2 = Leq(Ident(\"x\"), Const(0.0f)) // x <= 0.0\n",
    "val stmt3 = AssignStmt(\"x\", Minus(Const(0.0f), Ident(\"x\"))) // x= 0 - x\n",
    "val ifStmt = IfThenElseStmt(cond2, List(stmt3), List()) // if ( x <= 0) x = -x else nothing\n",
    "val whileStmt = WhileStmt(cond1, List(stmt2, ifStmt)) // while loop \n",
    "val allstmts = List(stmt1, whileStmt)\n",
    "val retExpr = Minus(Ident(\"y\"), Ident(\"x\")) // y - x to be returned\n",
    "\n",
    "val c1 = SwitchCase(Const(2.0), List(stmt1, stmt3))\n",
    "val c3 = SwitchCase(Ident(\"y\"), List(stmt1, stmt2, whileStmt))\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1cc4d3e81ad743eabdf4b80d7b42ef9b",
     "grade": true,
     "grade_id": "cell-590403a05cbd399c",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (5 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m))))\n",
       ")\n",
       "\u001b[36mstmt1\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n",
       "  \u001b[32m\"x\"\u001b[39m,\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       ")\n",
       "\u001b[36mcond1\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m))\n",
       "\u001b[36mstmt2\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mcond2\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m))\n",
       "\u001b[36mstmt3\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mifStmt\u001b[39m: \u001b[32mIfThenElseStmt\u001b[39m = \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "  \u001b[33mList\u001b[39m()\n",
       ")\n",
       "\u001b[36mwhileStmt\u001b[39m: \u001b[32mWhileStmt\u001b[39m = \u001b[33mWhileStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "    \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "      \u001b[33mList\u001b[39m()\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mallstmts\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mProduct\u001b[39m with \u001b[32mSerializable\u001b[39m with \u001b[32mStatement\u001b[39m] = \u001b[33mList\u001b[39m(\n",
       "  \u001b[33mAssignStmt\u001b[39m(\n",
       "    \u001b[32m\"x\"\u001b[39m,\n",
       "    \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "  ),\n",
       "  \u001b[33mWhileStmt\u001b[39m(\n",
       "    \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "    \u001b[33mList\u001b[39m(\n",
       "      \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "      \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "        \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "        \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "        \u001b[33mList\u001b[39m()\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mretExpr\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))\n",
       "\u001b[36mc2\u001b[39m: \u001b[32mDefaultCase\u001b[39m = \u001b[33mDefaultCase\u001b[39m(\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "      \u001b[33mList\u001b[39m()\n",
       "    )\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e1 = Plus(Ident(\"y\"), Plus( Ident(\"z\"), Exp( Minus(Ident(\"x\"), Ident(\"y\")) ) )) // y + z + exp(x - y)\n",
    "val stmt1 = AssignStmt(\"x\", e1) // x = y + z + exp(x - y)\n",
    "// Let us make up the parts of the while statement\n",
    "val cond1 = Leq(Ident(\"y\"), Const(15.0f)) // y <= 15\n",
    "// The assignment inside the while\n",
    "val stmt2 = AssignStmt(\"y\", Minus(Ident(\"y\"), Ident(\"x\"))) // y = y - x\n",
    "// The condition for the if statement\n",
    "val cond2 = Leq(Ident(\"x\"), Const(0.0f)) // x <= 0.0\n",
    "val stmt3 = AssignStmt(\"x\", Minus(Const(0.0f), Ident(\"x\"))) // x= 0 - x\n",
    "val ifStmt = IfThenElseStmt(cond2, List(stmt3), List()) // if ( x <= 0) x = -x else nothing\n",
    "val whileStmt = WhileStmt(cond1, List(stmt2, ifStmt)) // while loop \n",
    "val allstmts = List(stmt1, whileStmt)\n",
    "val retExpr = Minus(Ident(\"y\"), Ident(\"x\")) // y - x to be returned\n",
    "\n",
    "val c2 = DefaultCase(List(ifStmt))\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "43a3e70de1440c8faa2e2a8f398ea890",
     "grade": true,
     "grade_id": "cell-73f9de24de44bb2f",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (5 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m))))\n",
       ")\n",
       "\u001b[36mstmt1\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n",
       "  \u001b[32m\"x\"\u001b[39m,\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       ")\n",
       "\u001b[36mcond1\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m))\n",
       "\u001b[36mstmt2\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mcond2\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m))\n",
       "\u001b[36mstmt3\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "\u001b[36mifStmt\u001b[39m: \u001b[32mIfThenElseStmt\u001b[39m = \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "  \u001b[33mList\u001b[39m()\n",
       ")\n",
       "\u001b[36mwhileStmt\u001b[39m: \u001b[32mWhileStmt\u001b[39m = \u001b[33mWhileStmt\u001b[39m(\n",
       "  \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "    \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "      \u001b[33mList\u001b[39m()\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mallstmts\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mProduct\u001b[39m with \u001b[32mSerializable\u001b[39m with \u001b[32mStatement\u001b[39m] = \u001b[33mList\u001b[39m(\n",
       "  \u001b[33mAssignStmt\u001b[39m(\n",
       "    \u001b[32m\"x\"\u001b[39m,\n",
       "    \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "  ),\n",
       "  \u001b[33mWhileStmt\u001b[39m(\n",
       "    \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "    \u001b[33mList\u001b[39m(\n",
       "      \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "      \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "        \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "        \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "        \u001b[33mList\u001b[39m()\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mretExpr\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))\n",
       "\u001b[36mc1\u001b[39m: \u001b[32mSwitchCase\u001b[39m = \u001b[33mSwitchCase\u001b[39m(\n",
       "  \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\n",
       "      \u001b[32m\"x\"\u001b[39m,\n",
       "      \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "    ),\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "  )\n",
       ")\n",
       "\u001b[36mc3\u001b[39m: \u001b[32mSwitchCase\u001b[39m = \u001b[33mSwitchCase\u001b[39m(\n",
       "  \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mAssignStmt\u001b[39m(\n",
       "      \u001b[32m\"x\"\u001b[39m,\n",
       "      \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "    ),\n",
       "    \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "    \u001b[33mWhileStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "        \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "          \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "          \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "          \u001b[33mList\u001b[39m()\n",
       "        )\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mc2\u001b[39m: \u001b[32mDefaultCase\u001b[39m = \u001b[33mDefaultCase\u001b[39m(\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "      \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "      \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "      \u001b[33mList\u001b[39m()\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36mv1\u001b[39m: \u001b[32mSwitch\u001b[39m = \u001b[33mSwitch\u001b[39m(\n",
       "  \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m))))),\n",
       "  \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mSwitchCase\u001b[39m(\n",
       "      \u001b[33mConst\u001b[39m(\u001b[32m2.0\u001b[39m),\n",
       "      \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mAssignStmt\u001b[39m(\n",
       "          \u001b[32m\"x\"\u001b[39m,\n",
       "          \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "        ),\n",
       "        \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n",
       "      )\n",
       "    ),\n",
       "    \u001b[33mDefaultCase\u001b[39m(\n",
       "      \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "          \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "          \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "          \u001b[33mList\u001b[39m()\n",
       "        )\n",
       "      )\n",
       "    ),\n",
       "    \u001b[33mSwitchCase\u001b[39m(\n",
       "      \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m),\n",
       "      \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mAssignStmt\u001b[39m(\n",
       "          \u001b[32m\"x\"\u001b[39m,\n",
       "          \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m), \u001b[33mExp\u001b[39m(\u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))))\n",
       "        ),\n",
       "        \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "        \u001b[33mWhileStmt\u001b[39m(\n",
       "          \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n",
       "          \u001b[33mList\u001b[39m(\n",
       "            \u001b[33mAssignStmt\u001b[39m(\u001b[32m\"y\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))),\n",
       "            \u001b[33mIfThenElseStmt\u001b[39m(\n",
       "              \u001b[33mLeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m)),\n",
       "              \u001b[33mList\u001b[39m(\u001b[33mAssignStmt\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mMinus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m0.0\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))),\n",
       "              \u001b[33mList\u001b[39m()\n",
       "            )\n",
       "..."
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val e1 = Plus(Ident(\"y\"), Plus( Ident(\"z\"), Exp( Minus(Ident(\"x\"), Ident(\"y\")) ) )) // y + z + exp(x - y)\n",
    "val stmt1 = AssignStmt(\"x\", e1) // x = y + z + exp(x - y)\n",
    "// Let us make up the parts of the while statement\n",
    "val cond1 = Leq(Ident(\"y\"), Const(15.0f)) // y <= 15\n",
    "// The assignment inside the while\n",
    "val stmt2 = AssignStmt(\"y\", Minus(Ident(\"y\"), Ident(\"x\"))) // y = y - x\n",
    "// The condition for the if statement\n",
    "val cond2 = Leq(Ident(\"x\"), Const(0.0f)) // x <= 0.0\n",
    "val stmt3 = AssignStmt(\"x\", Minus(Const(0.0f), Ident(\"x\"))) // x= 0 - x\n",
    "val ifStmt = IfThenElseStmt(cond2, List(stmt3), List()) // if ( x <= 0) x = -x else nothing\n",
    "val whileStmt = WhileStmt(cond1, List(stmt2, ifStmt)) // while loop \n",
    "val allstmts = List(stmt1, whileStmt)\n",
    "val retExpr = Minus(Ident(\"y\"), Ident(\"x\")) // y - x to be returned\n",
    "\n",
    "val c1 = SwitchCase(Const(2.0), List(stmt1, stmt3))\n",
    "val c3 = SwitchCase(Ident(\"y\"), List(stmt1, stmt2, whileStmt))\n",
    "val c2 = DefaultCase(List(ifStmt))\n",
    "\n",
    "val v1 = Switch(e1, List(c1, c2, c3))\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ab035bd7e4e05ac892118672e45c155f",
     "grade": false,
     "grade_id": "cell-55543ed7e443b655",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Problem 2 (15 Points)\n",
    "\n",
    "Add list manipulation expressions to the allowed expressions in the `mython` language. \n",
    "\n",
    "We allow list expressions (use a new non terminal called __ListExpr__) that can do the following:\n",
    "- the empty list: use constructor symbol `EmptyList`\n",
    "- explicitly create a list of arithmetic expressions: use constructor symbol `NewList`\n",
    "- Cons an arithmetic expression to the front of a list: use constructor symbol `Cons`\n",
    "- Concatenate two lists defined by list expressions: use constructor symbol `Concat`\n",
    "\n",
    "Next, we add to conditional expressions the following:\n",
    "- A condition expression to check if a list is empty:  Use constructor `IsEmptyList`\n",
    "\n",
    "Finally, we add a special foreach loop statement over the elements of a list.\n",
    "\n",
    "`foreach (x in list_expr) begin  .. list of statements...  end `\n",
    "\n",
    "- Add a statement to loop over the elements of a list: use constructor`ForEach`\n",
    "\n",
    "Write down the extra grammar rules that you would add to the overall \n",
    "`mython` grammar to create these functionalities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "10c1c3648bc72d60b80f2cb28419e223",
     "grade": true,
     "grade_id": "cell-76cfd1d2c6a5898d",
     "locked": false,
     "points": 15,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "$$\\begin{array}{rcl}\n",
    "\\mathbf{ListExpr} & \\rightarrow & \\text{EmptyList}\\\\\n",
    "                  & | & \\text{NewList}(\\mathbf{Expr}*) \\\\\n",
    "                  & | & \\text{Cons}(\\mathbf{Int}, \\mathbf{ListExpr}) \\\\\n",
    "                  & | & \\text{Concat}(\\mathbf{ListExpr},\\mathbf{ListExpr}) \\\\\n",
    "\\mathbf{CondExpr} & \\rightarrow & \\text{IsEmptyList}(\\mathbf{ListExpr})\\\\\n",
    "\\mathbf{Statement} & \\rightarrow & \\text{ForEach}(\\mathbf{Identifier}, \\mathbf{ListExpr}, \\mathbf{Statement}*)\\\\\n",
    "\\end{array}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d5b9773df6ee387cd526e827fd5cd65",
     "grade": false,
     "grade_id": "cell-33da7cb13bb6465f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Problem 3 (20 points)\n",
    "\n",
    "### A (5 points)\n",
    "We defined lists in the class. Write a recursive procedure to get the nth element of the list or throw an `IllegalArgumentException` if $n < 0$ or $n >= length of list $. Assume $n=0$ obtains the very first element\n",
    "and $n = length of list -1$ yields very last element. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f2754a20b9fac98c0caa07981ed4ceee",
     "grade": false,
     "grade_id": "cell-724b4ca89445ceaf",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNumList\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNil\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCons\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mgetNthElement\u001b[39m"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NumList\n",
    "case object Nil extends NumList\n",
    "case class Cons(n: Int, l: NumList) extends NumList \n",
    "\n",
    "def getNthElement(lst: NumList, n: Int): Int = {\n",
    "    if (n<0) throw new IllegalArgumentException\n",
    "\n",
    "    lst match {\n",
    "        case Nil => throw new IllegalArgumentException\n",
    "        case Cons(firstElement, restOfList) if(n==0) => return firstElement\n",
    "        case Cons(firstElement, restOfList) if (n>=1) => getNthElement(restOfList, n-1)  \n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "321689af0bcc9697fa137ba165fbf419",
     "grade": true,
     "grade_id": "cell-2bc6d5ee94793b48",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (5 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\u001b[39m: \u001b[32mNil\u001b[39m = Nil\n",
       "\u001b[36ml2\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m-1\u001b[39m, Nil))\n",
       "\u001b[36ml3\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m2\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m-1\u001b[39m, Nil))))\n",
       "\u001b[36ml4\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m4\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m8\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m2\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m-1\u001b[39m, Nil)))))))\n",
       "\u001b[36mtest1\u001b[39m: \u001b[32mAny\u001b[39m = \u001b[32m\"OK\"\u001b[39m\n",
       "\u001b[36mtest2\u001b[39m: \u001b[32mAny\u001b[39m = \u001b[32m\"OK\"\u001b[39m"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = Nil\n",
    "val l2 = Cons(1, Cons(-1, Nil))\n",
    "val l3 = Cons(1, Cons(2, l2))\n",
    "val l4 = Cons(0, Cons(4, Cons(8, l3)))\n",
    "\n",
    "val test1 = try {\n",
    "    getNthElement(Nil, 3);\n",
    "    assert(false, \"Test 1 : getNthElement(Nil, 3) should raise an IllegalArgumentException. Your code did not.\")\n",
    "} catch {\n",
    "    case e: IllegalArgumentException => \"OK\"\n",
    "} \n",
    "\n",
    "assert(getNthElement(l2, 0) == 1, \"Test2: getNthElement(l2, 0)  failed (expected answer = 1)\")\n",
    "assert(getNthElement(l3, 3) == -1, \"Test3: getNthElement(l3, 3)  failed (expected answer = -1)\")\n",
    "assert(getNthElement(l4, 2) == 8, \"Test4: getNthElement(l4, 2)  failed (expected answer = 8)\")\n",
    "\n",
    "val test2 = try {\n",
    "    getNthElement(l4, 8);\n",
    "    assert(false, \"Test 5 : getNthElement(l4, 8) should raise an IllegalArgumentException. Your code did not.\")\n",
    "} catch {\n",
    "    case e: IllegalArgumentException => \"OK\"\n",
    "}\n",
    "\n",
    "passed(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f4a061c4891d5c2002006c5db21ac0fc",
     "grade": false,
     "grade_id": "cell-f33dba0762a43adc",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### B (7 points)\n",
    "Write a recursive procedure that returns true if the list has the Fibonacci property. I.e, every element at position $i \\geq 2$ is the sum of the two preceding elements. Note that the property is trivially true for lists of sizes $0$ and $1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "5c56fada9b3460964d0236f3c3113433",
     "grade": false,
     "grade_id": "cell-eedd55e1f86bd6c6",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36misFibonacciList\u001b[39m"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def isFibonacciList(lst: NumList): Boolean = {\n",
    "    lst match{\n",
    "        case Nil => return true\n",
    "        case Cons(first, Nil) => return true\n",
    "        case Cons(first, Cons(second, Nil)) => return true\n",
    "        case Cons(first, Cons(second, Cons(third, restOfList))) if (first+second==third)=>isFibonacciList(Cons(second, Cons(third, restOfList))) \n",
    "        case Cons(first, Cons(second, Cons(third, restOfList))) if (first+second!=third)=>return false\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "879829d77809a3a0b1e862b063345838",
     "grade": true,
     "grade_id": "cell-33a4f21c01f0c7c4",
     "locked": true,
     "points": 7,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (7 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m12\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m25\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m37\u001b[39m, Nil)))\n",
       "\u001b[36ml2\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m14\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m-1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m13\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m12\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m25\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m37\u001b[39m, Nil))))))\n",
       "\u001b[36ml3\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\n",
       "  \u001b[32m7\u001b[39m,\n",
       "  \u001b[33mCons\u001b[39m(\u001b[32m7\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m14\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m-1\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m13\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m12\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m25\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m37\u001b[39m, Nil)))))))\n",
       ")\n",
       "\u001b[36ml4\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, Nil))))))"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = Cons(12, Cons(25, Cons(37, Nil)))\n",
    "assert(isFibonacciList(l1), \n",
    "       \"Test case 1 :  isFibonacciList(l1) -- should return true\")\n",
    "\n",
    "val l2 = Cons(14, Cons(-1, Cons(13, l1 )))\n",
    "assert(isFibonacciList(l2), \n",
    "       \"Test case 2 :  isFibonacciList(l2) -- should return true\")\n",
    "\n",
    "val l3 = Cons(7, Cons(7, l2))\n",
    "\n",
    "assert(!isFibonacciList(l3), \n",
    "       \"Test case 3 :  isFibonacciList(l3) -- should return false\")\n",
    "\n",
    "val l4 = Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Nil))))))\n",
    "assert(isFibonacciList(l2), \n",
    "       \"Test case 4:  isFibonacciList(l4) -- should return true\")\n",
    "\n",
    "passed(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9a1a2912b9bdbdbf2f3bcfabb5cbdd76",
     "grade": false,
     "grade_id": "cell-d4f6c640c40f9924",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### C (8 points)\n",
    "Write a recursive function `filterNumList(l: NumList, f: Int => Boolean): NumList` that takes in a `NumList` and a function `f: Int => Boolean`. \n",
    "\n",
    "1. It should return a new list that consist of all elements of the list `l` that return `true` when the function `f` is called on them.\n",
    "2. The returned list elements must preserve the same order as in the original list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "5da2d93bb68bbf460bf404ffbfd66253",
     "grade": false,
     "grade_id": "cell-0f9f5a51ae34b3bb",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterNumList\u001b[39m"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def filterNumList(l: NumList, f: Int => Boolean): NumList = {\n",
    "    l match{\n",
    "        case Nil => return Nil\n",
    "        case Cons(first, restOfList) if (f(first)) => return Cons(first, filterNumList(restOfList, f))\n",
    "        case Cons(first, restOfList) if (!f(first)) => return filterNumList(restOfList, f)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1c91eea3f54e5c50f2f9109f162130e0",
     "grade": true,
     "grade_id": "cell-a2549ef77f3f9bb0",
     "locked": true,
     "points": 8,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "*** Tests Passed (8 points) ***\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m12\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m25\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m37\u001b[39m, Nil)))\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mf1\u001b[39m\n",
       "\u001b[36ml2\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m22\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m135\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m137\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m12\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m25\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m37\u001b[39m, Nil))))))\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mf2\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mf3\u001b[39m\n",
       "\u001b[36ml4\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, \u001b[33mCons\u001b[39m(\u001b[32m0\u001b[39m, Nil))))))\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mf4\u001b[39m"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = Cons(12, Cons(25, Cons(37, Nil)))\n",
    "def f1(j: Int): Boolean =  j <= 25 && j >= 12\n",
    "assert(filterNumList(l1, f1) == Cons(12, Cons(25, Nil)), \"Test 1 failed.\")\n",
    "\n",
    "\n",
    "val l2 = Cons(22, Cons(135, Cons(137, l1)))\n",
    "def f2(j: Int): Boolean =  j % 5 == 0\n",
    "assert(filterNumList(l2, f2) == Cons(135, Cons(25, Nil)), \"Test 2 failed.\")\n",
    "\n",
    "def f3(j: Int): Boolean =  j >= 210\n",
    "assert(filterNumList(l2, f3) == Nil, \"Test 3 failed.\")\n",
    "assert(filterNumList(Nil, f3) == Nil, \"Test 4 failed.\")\n",
    "\n",
    "val l4 = Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Nil))))))\n",
    "\n",
    "def f4(j: Int): Boolean =  j <= 0\n",
    "assert(filterNumList(l4, f4) == l4, \"Test 5 failed\")\n",
    "\n",
    "passed(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.12.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}