{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 7: Operations on Arithmetic Expressions\n",
    "Originally by Sriram Sankaranarayanan <srirams@colorado>\n",
    "\n",
    "Modified by Ravi Mangal <ravi.mangal@colostate>\n",
    "\n",
    "Last Modified: Feb 13, 2025."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lecture, we will study some opeartions on the inductively defined arithmetic expressions. First, let us look at the grammar defining arithmetic expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arithmetic Expressions\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arithmetic expressions are generated by the grammar we saw before.\n",
    "\n",
    "$$\\begin{array}{rcll}\n",
    "\\textbf{Expr} & \\rightarrow & Const(\\textbf{Double}) & \\\\\n",
    "& |  & Ident(\\textbf{Identifier}) & \\\\\n",
    "& | & Plus( \\textbf{Expr}^+) & \\text{Note:}\\ A^+ \\ \\text{is one or more reps of}\\ A \\\\\n",
    "& | & Minus( \\textbf{Expr}, \\textbf{Expr}^+) & \\\\\n",
    "& | & Mult(\\textbf{Expr}^+) & \\\\\n",
    "& | & Div(\\textbf{Expr}, \\textbf{Expr}) & \\\\\n",
    "& | & Log(\\textbf{Expr}) & \\\\\n",
    "& | & Exp(\\textbf{Expr}) & \\\\\n",
    "& | & Sine(\\textbf{Expr}) & \\\\\n",
    "& | & Cosine(\\textbf{Expr}) &\\\\\\\\\n",
    "\\textbf{Double} & \\rightarrow & \\text{all double precision numbers in Scala} & \\\\\n",
    "\\textbf{Identifier} & \\rightarrow & [a-zA-Z][a-z\\ A-Z\\ 0-9\\ \\_]* & \\text{Note: All strings that begin with letters}\\\\\n",
    "&&& \\text{a-z or A-Z and subsequently can contain a-z, A-Z, 0-9 or \\_ chars}\n",
    "\\end{array}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "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[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"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr\n",
    "case class Const(f: Double) extends Expr \n",
    "case class Ident(s: String) extends Expr // We allow any string to be an identifier for now \n",
    "                                         // instead of the regular expression shown in the grammar.\n",
    "case class Plus( eList: List[Expr] ) extends Expr\n",
    "case class Minus(e1: Expr, eList: List[Expr]) extends Expr\n",
    "case class Mult(eList: List[Expr]) extends Expr\n",
    "case class Div(e1: Expr, e2: 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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest function we wish to write will collect all the variables that are used in a given expression inside a Set data structure. Read about Scala sets here: https://docs.scala-lang.org/overviews/collections/sets.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcollectAllVariables\u001b[39m"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def collectAllVariables(e: Expr): Set[String] = {\n",
    "    def helperFunction(eList: List[Expr], startValue: Set[String]): Set[String] = {\n",
    "        // Iterate through the list eList and collect set of variables for each expression in eList.\n",
    "        // Next: take the union of all the sets with the given set startValue.\n",
    "\n",
    "        // A nifty functional way to do this\n",
    "            eList.foldLeft (startValue) {\n",
    "                case (setSoFar: Set[String], newExpr:Expr) => { val v = collectAllVariables(newExpr)\n",
    "                                              setSoFar union v  // Same as setSoFar.union(v); Lookup Scala's infix notation \n",
    "                                                                // (https://docs.scala-lang.org/style/method-invocation.html)\n",
    "                                            }\n",
    "        \n",
    "            }\n",
    "        \n",
    "        // If you insist on a for loop, you have to use a var\n",
    "        // var setSoFar = startValue\n",
    "        // for (newExpr <- eList) {\n",
    "        //   setSoFar = setSoFar.union(collectAllVariables(newExpr))\n",
    "        //    }\n",
    "        // return setSoFar\n",
    "    }\n",
    "        \n",
    "    e match {\n",
    "        case Const(f) => Set() // Return the empty set\n",
    "        case Ident(s) => Set(s) // Return a singleton set with s in it.\n",
    "        case Plus(eList) => helperFunction(eList, Set())  //Union of all variables in eList\n",
    "        case Mult(eList) => helperFunction(eList, Set()) // Union of all variables in eList\n",
    "    \n",
    "        case Minus(e1, eList) => {\n",
    "            val e1Set = collectAllVariables(e1) // First collect variables in e1\n",
    "            helperFunction(eList, e1Set) // take union of all variables in eList with e1Set from prev. step\n",
    "        }\n",
    "    \n",
    "    \n",
    "        case Div(e1, e2) => {\n",
    "            (collectAllVariables(e1)) union (collectAllVariables(e2))\n",
    "        }\n",
    "        case Log(e1) => collectAllVariables(e1)\n",
    "        case Sine(e1) => collectAllVariables(e1)\n",
    "        case Cosine(e1) => collectAllVariables(e1)\n",
    "        case Exp(e1) => collectAllVariables(e1)\n",
    "        case _ => { assert(false); return Set()  } // This is the catch all. Should not happen but good coding practice\n",
    "    }\n",
    "}  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36my\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)\n",
       "\u001b[36mz\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"Zzz\"\u001b[39m)\n",
       "\u001b[36mexpr1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  eList = \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mCosine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)),\n",
       "    \u001b[33mSine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)),\n",
       "    \u001b[33mExp\u001b[39m(\n",
       "      e = \u001b[33mMinus\u001b[39m(\n",
       "        e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m),\n",
       "        eList = \u001b[33mList\u001b[39m(\u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"Zzz\"\u001b[39m))\n",
       "      )\n",
       "    )\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// cos(x) + sin(y) + e^{x - y - Zzz}\n",
    "val x = Ident(\"x\")\n",
    "val y = Ident(\"y\")\n",
    "val z = Ident(\"Zzz\")\n",
    "val expr1 = Plus(List(Cosine(x), Sine(y), Exp(Minus(x, List(y,z)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ms1\u001b[39m: \u001b[32mSet\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[32m\"y\"\u001b[39m, \u001b[32m\"Zzz\"\u001b[39m)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val s1 = collectAllVariables(expr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mexpr2\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n",
       "  eList = \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mExp\u001b[39m(e = \u001b[33mConst\u001b[39m(f = \u001b[32m1.5\u001b[39m)),\n",
       "    \u001b[33mSine\u001b[39m(e = \u001b[33mConst\u001b[39m(f = \u001b[32m2.0\u001b[39m)),\n",
       "    \u001b[33mCosine\u001b[39m(e = \u001b[33mMult\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mConst\u001b[39m(f = \u001b[32m1.2\u001b[39m), \u001b[33mConst\u001b[39m(f = \u001b[32m2.4\u001b[39m))))\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val expr2 = Plus(List(Exp(Const(1.5)), Sine(Const(2.0)), Cosine(Mult(List(Const(1.2), Const(2.4))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ms2\u001b[39m: \u001b[32mSet\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSet\u001b[39m()"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val s2 = collectAllVariables(expr2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another important function is pretty print. We would like to pretty print our expression to Latex so that we can cut and paste it in our documents.\n",
    "\n",
    "Latex allows you to type formulae and have them displayed. Eg., let us take the formula\n",
    "\n",
    "$$ \\frac{M c^2}{ 1 + \\frac{1}{1 + c^2}}$$\n",
    "\n",
    "You would write it as\n",
    "\n",
    "\\$ \\\\frac{M c^2}{ 1 + \\\\frac{1}{1 + c^2} \\$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtoLatex\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def toLatex (e: Expr): String = {\n",
    "    e match {\n",
    "        case Const(f) => \"%2.2f\".format(f) // easy way to convert f to a string.\n",
    "        case Ident(str) => str\n",
    "        case Plus(eList) => { val strList = eList map { e =>  toLatex(e) }\n",
    "                         \"\\\\left(\"+ strList.mkString (\" + \") + \"\\\\right)\" // Join each expression into a string separated by \" + \"\n",
    "                       }\n",
    "        case Minus(e, eList) => {\n",
    "            val s1 = toLatex(e)\n",
    "            val strList = eList map {e => toLatex(e)} \n",
    "             \"\\\\left(\"+ s1 + \" - \" + (strList mkString \" - \")+ \"\\\\right)\" \n",
    "            \n",
    "        }\n",
    "        case Mult(eList) => {  \"\\\\left(\" + (eList map {toLatex(_)} mkString (\"\\\\ \")) + \"\\\\right)\"  }\n",
    "        \n",
    "        case Div(e1, e2) => { \"\\\\frac{\" + (toLatex(e1)) + \"}{\" + (toLatex(e2)) + \"}\" }\n",
    "        case Log(e) => { \"\\\\log(\" + (toLatex(e)) + \")\" }\n",
    "        case Exp(e) => { \"e^{\" + (toLatex(e)) + \"}\"}\n",
    "        case Sine(e) => { \"\\\\sin\\\\left(\"+ toLatex(e) + \"\\\\right)\" }\n",
    "        case Cosine(e) => {\"\\\\cos\\\\left(\"+ toLatex(e) + \"\\\\right)\" }\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "$\\left(\\cos\\left(x\\right) + \\sin\\left(y\\right) + e^{\\left(x - y - Zzz\\right)}\\right)$"
     ]
    },
    {
     "data": {
      "text/latex": [
       "$\\left(\\cos\\left(x\\right) + \\sin\\left(y\\right) + e^{\\left(x - y - Zzz\\right)}\\right)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mstr1\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"$\\\\left(\\\\cos\\\\left(x\\\\right) + \\\\sin\\\\left(y\\\\right) + e^{\\\\left(x - y - Zzz\\\\right)}\\\\right)$\"\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val str1= \"$\"+toLatex(expr1)+\"$\"\n",
    "print(str1)\n",
    "latex(str1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\frac{\\left(\\left(w + \\left(x\\ y\\right) + \\left(1.20 + w\\right)\\right) - 1.50 - w - x\\right)}{2.30}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mw\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m)\n",
       "\u001b[36mexpr2\u001b[39m: \u001b[32mDiv\u001b[39m = \u001b[33mDiv\u001b[39m(\n",
       "  e1 = \u001b[33mMinus\u001b[39m(\n",
       "    e1 = \u001b[33mPlus\u001b[39m(\n",
       "      eList = \u001b[33mList\u001b[39m(\n",
       "        \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m),\n",
       "        \u001b[33mMult\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m))),\n",
       "        \u001b[33mPlus\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mConst\u001b[39m(f = \u001b[32m1.2\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m)))\n",
       "      )\n",
       "    ),\n",
       "    eList = \u001b[33mList\u001b[39m(\u001b[33mConst\u001b[39m(f = \u001b[32m1.5\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n",
       "  ),\n",
       "  e2 = \u001b[33mConst\u001b[39m(f = \u001b[32m2.3\u001b[39m)\n",
       ")"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val w = Ident(\"w\")\n",
    "val expr2 = Div(Minus( Plus(List(w, Mult(List(x, y)), \n",
    "                                Plus(List(Const(1.2), w))) ), \n",
    "                                     List(Const(1.5), w, x) ), Const(2.3))\n",
    "latex(\"$\"+ toLatex(expr2) + \"$\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### My First Eval Function\n",
    "\n",
    "Now we will write a very important operation called `eval`. This operation is the primary operation that an interpreter needs to carry out. \n",
    "\n",
    "But we will start small by writing an eval for our simple expression grammar. Before we do that, let us ask ourselves two questions: (a) what does it mean for the expressions to be evaluated? and (b) what is the missing information that we need before we can evaluate our arithmetic expressions defined above?\n",
    "The answers should be easy in this case:\n",
    "\n",
    "1. An arithmetic expression stands for a number which is the answer when we calculate it and \n",
    "2. Of course, the missing information is that we do not know what the valuations for the variables are to start with.\n",
    "\n",
    "Thus, we are ready to define the eval function.\n",
    "\n",
    "__Environment__ \n",
    "\n",
    "An environment $\\eta$ maps every identifier string to a numeric value. \n",
    "\n",
    "\n",
    "Example: \n",
    "\n",
    "$$ \\{ x \\mapsto 2, y \\mapsto 1.5, Zzz \\mapsto 2.8, w \\mapsto 15.2 \\}$$\n",
    "\n",
    "Scala has a Map data structure that is ideal for environments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmyEnvironment\u001b[39m: \u001b[32mMap\u001b[39m[\u001b[32mString\u001b[39m, \u001b[32mDouble\u001b[39m] = \u001b[33mHashMap\u001b[39m(\n",
       "  \u001b[32m\"x\"\u001b[39m -> \u001b[32m2.0\u001b[39m,\n",
       "  \u001b[32m\"y\"\u001b[39m -> \u001b[32m1.5\u001b[39m,\n",
       "  \u001b[32m\"Zzz\"\u001b[39m -> \u001b[32m2.8\u001b[39m,\n",
       "  \u001b[32m\"l\"\u001b[39m -> \u001b[32m129.3\u001b[39m,\n",
       "  \u001b[32m\"w\"\u001b[39m -> \u001b[32m15.2\u001b[39m\n",
       ")"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val myEnvironment: Map[String, Double] = Map(\"x\" -> 2.0, \"y\" -> 1.5, \"Zzz\" -> 2.8, \"w\" -> 15.2, \"l\" -> 129.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {\n",
    "    case Const (f) => f\n",
    "    case Ident (str) => { if (env.contains(str)){\n",
    "                                env(str)\n",
    "                            } else {\n",
    "        throw new IllegalArgumentException(s\"Environment does not contain mapping for $str\")\n",
    "    }\n",
    "                        }\n",
    "    case Plus(eList) => {\n",
    "        (eList map {evalExpr(_, env)}).sum\n",
    "    }\n",
    "    \n",
    "    case Minus(e, eList) => {\n",
    "        (evalExpr(e, env)) - ((eList map {evalExpr(_, env)}).sum )\n",
    "    }\n",
    "    \n",
    "    case Mult(eList) => {\n",
    "        (eList map {evalExpr(_, env)}).product\n",
    "    }\n",
    "    \n",
    "    case Div(e1, e2) => {\n",
    "        (evalExpr(e1, env)) / (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Log(e) => math.log(evalExpr(e, env))\n",
    "    \n",
    "    \n",
    "    case Exp(e) => math.exp( evalExpr(e, env))\n",
    "    \n",
    "    case Sine(e) => math.sin( evalExpr(e, env))\n",
    "    \n",
    "    case Cosine(e) => math.cos(evalExpr(e, env))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf1\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m0.6816069937797158\u001b[39m"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f1 = evalExpr(expr1, myEnvironment)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf2\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m6.913043478260868\u001b[39m"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f2 = evalExpr(expr2, myEnvironment)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\left(1.00 - \\left(\\sin\\left(x\\right)\\ \\sin\\left(x\\right)\\right) - \\left(\\cos\\left(x\\right)\\ \\cos\\left(x\\right)\\right)\\right)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mexpr3\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(\n",
       "  e1 = \u001b[33mConst\u001b[39m(f = \u001b[32m1.0\u001b[39m),\n",
       "  eList = \u001b[33mList\u001b[39m(\n",
       "    \u001b[33mMult\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mSine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)), \u001b[33mSine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)))),\n",
       "    \u001b[33mMult\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mCosine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)), \u001b[33mCosine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))))\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val expr3 = Minus(Const(1.0), List(\n",
    "    Mult(List(Sine(x), Sine(x))),\n",
    "    Mult(List(Cosine(x), Cosine(x)))\n",
    "))\n",
    "\n",
    "latex(\"$\"+toLatex(expr3)+\"$\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf3\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m0.0\u001b[39m"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f3 = evalExpr(expr3, myEnvironment) // Should be 0.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf4\u001b[39m: \u001b[32mLog\u001b[39m = \u001b[33mLog\u001b[39m(\n",
       "  e = \u001b[33mPlus\u001b[39m(\n",
       "    eList = \u001b[33mList\u001b[39m(\n",
       "      \u001b[33mConst\u001b[39m(f = \u001b[32m1.0\u001b[39m),\n",
       "      \u001b[33mMult\u001b[39m(eList = \u001b[33mList\u001b[39m(\u001b[33mConst\u001b[39m(f = \u001b[32m2.0\u001b[39m), \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)))\n",
       "    )\n",
       "  )\n",
       ")\n",
       "\u001b[36menv\u001b[39m: \u001b[32mMap\u001b[39m[\u001b[32mString\u001b[39m, \u001b[32mDouble\u001b[39m] = \u001b[33mMap\u001b[39m(\u001b[32m\"y\"\u001b[39m -> \u001b[32m1.2\u001b[39m)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f4 = Log(Plus(List(Const(1.0), Mult(List(Const(2.0), Ident(\"y\"))))))\n",
    "val env = Map(\"y\" -> 1.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf5\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.2237754316221157\u001b[39m"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f5 = evalExpr(f4,env )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We learned how to implement some operations on our inductive data structures.\n",
    "Now we are ready in the next step to learn about how to write an interpreter and start adding features to the interpreter. But you may have already sensed something important: we have developed the bad habit of writing\n",
    "lots of code to carry out various operations and using the code as the definition. This works for simple operations which are easy for us to understand. For a more complex beast like a program, we will need a disciplined approach to understanding and writing down the workings of the program outside of code and in a way that can be analyzed by people. We will learn these as operational semantics in the coming lectures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "(console):3:18 expected \")\"\n",
      "case class Match(String) extends Regex\n",
      "                 ^"
     ]
    }
   ],
   "source": [
    "sealed trait Regex\n",
    "case object Empty extends Regex\n",
    "case class Match(s: String) extends Regex\n",
    "case class Or(r1: Regex, r2: Regex) extends Regex\n",
    "case class Seq(r1: Regex, r2: Regex) extends Regex\n",
    "case class Star(r: Regex) extends Regex"
   ]
  },
  {
   "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": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}