{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lecture 8: Big Step Semantics For Arithmetic Expressions\n", "\n", "Originally by Sriram Sankaranarayanan \n", "\n", "Modified by Ravi Mangal \n", "\n", "Last Modified: Feb 17, 2025.\n", "\n", "We have thus far looked at the first eval function for `Expr` that denote arithmetic expressions.\n", "\n", "Recall their grammar from the previous lectures. We have simplified the grammer slightly: plus, minus and multiplication operate just over two expressions at a time.\n", "\n", "$$\\begin{array}{rcll}\n", "\\textbf{Expr} & \\rightarrow & Const(\\textbf{Double}) \\\\\n", "& | & Ident(\\textbf{Identifier}) \\\\\n", "& | & Plus( \\textbf{Expr}, \\textbf{Expr}) \\\\\n", "& | & Minus( \\textbf{Expr}, \\textbf{Expr}) \\\\\n", "& | & Mult(\\textbf{Expr}, \\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}$$\n", "\n", "Next we provided a translation of the very same grammar into scala abstract syntax definitions." ] }, { "cell_type": "code", "execution_count": 1, "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": 1, "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\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 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": [ "We wrote a simple and intuitive function `evalExpr` but how do we talk about what it does? A simple answer is that the code can be read by anyone who knows Scala and therefore can serve to document the meaning of expressions in terms of what they do. This is surely a path to disaster for more complicated languages. It is important therefore to use some kind of notation to explain how to understand the behavior of the `evalExpr` function at a high level and in a language independent fashion. We will use \"big step\" semantics to notate this process and see how the code we have written so far is simply a translation of the big step semantics into code.\n", "\n", "\n", "## Big Step Semantics\n", "\n", "Let us explain at a high level how an expression $ \\log(1.0 + 2.0 * y)$ (note $\\log$ is the natural log to the base $e$).\n", "\n", "`Log(Plus(Const(1.0), Mult(Const(2.0), Ident(\"y\"))))` \n", "\n", "under an environment that assignes `y` to `1.2` gets evaluated to a value `1.2237754316221157`.\n", "\n", "Without worrying about the order in which things happen, let us act as if we are ourselves working this out.\n", "\n", "- `Ident(\"y\")` gets evaluated to `1.2`\n", "- `Const(2.0)` gets evaluated to `2.0`\n", "- `Mult(Const(2.0), Ident(\"y\"))` can now get evaluated to `2.0 * 1.2 = 2.4` since each of its children have been evaluated\n", "- `Const(1.0)` gets evaluated to `1.0`.\n", "- `Plus(Const(1.0) , Mult(Const(2.0), Ident(\"y\")))` can be evaluated to `1.0 + 2.4` and thus to 3.4\n", "- `Log(...)` evaluates to $\\log(3.4) = 1.223775...$.\n", "\n", "What are the things we notice in this process?\n", "\n", "- Every rule takes an expression and tells us what it evaluates to.\n", "- The environment mapping variables to values is an input to this process and remains unchanged throughout.\n", "- The result of every evaluation is a double precision number.\n", "- Simple leaf expressions like `Const(f)` and `Identifier(y)` are evaluated directy to the double precision numbers either as the number `f` or whatever value the identifier `y` is mapped to in the given environment.\n", "- For any other expression using construtors `Plus`, `Minus`, `Mult`, `Div`, ..., if the children evaluate to double precision numbers, then the expression itself is ready to evaluate by applying the appropriate arithmetic operator on the values of its children.\n", "\n", "These observations are tedious to write down in English. We can provide a more succinct way to write it down using a notation: $\\mathbf{eval}(\\texttt{e}, \\sigma) = d$.\n", "It is a way of succinctly saying that \"under the enviroment $\\sigma$, the expression $\\texttt{e}$ evaluates to the value $d$\". \n", "\n", "$\\newcommand\\eval{\\mathbf{eval}}$\n", "### Examples\n", "\n", "- $ \\eval(\\texttt{Ident(\"y\")}, \\{y \\mapsto 1.0 \\})\\ = 1.0 $\n", "- $ \\eval(\\texttt{Mult(Const(1.2), Const(1.2))}, \\{ y \\mapsto 1.0 \\} ) = 1.44 $.\n", "- $ \\eval(\\texttt{Plus(Const(1.0) , Mult(Const(2.0), Ident(\"y\")))}, \\{y \\mapsto 1.2 \\})= 3.4 $\n", "\n", "\n", "## Inference Rules\n", "\n", "The value in the entire process is not in realizing individual instances such as \n", "\n", "$$ \\eval\\left(\\texttt{Log(Plus(Const(1.0) , Mult(Const(2.0), Ident(\"y\")))}, \\{y \\mapsto 1.2 \\} \\right) = 1.223775.. $$\n", "\n", "but in specifying how one systematically arrives at the result. If that is understood, then writing an interpreter is a cinch. Also, the rules will specify exactly how we will go about the process.\n", "\n", "Inference rules are always written like this.\n", "\n", "$$\\begin{array}{c}\n", "\\text{premises that must hold} \\\\\n", "\\hline\n", "\\text{conclusions that can be drawn} \\\\\n", "\\end{array}$$\n", "\n", "It must be read as __assuming premises must hold, then conclusion must hold__.\n", "\n", "As an example, let us see a rule for `Log`:\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e},\\sigma) = c \\\\\n", "\\hline \n", "\\eval(\\texttt{Log(e)}, \\sigma) = \\log(c) \\\\\n", "\\end{array}\\ \\text{(Log)}$$\n", "\n", "The rule says:\n", "- Assume: \"under the environment $\\sigma$, some expression `e` evaluates to $c$\"\n", "- Conclude: \"under the environment $\\sigma$, the expression `Log(e)` evalutes to $\\log(c)$\"\n", "\n", "#### Basic Inference Rules\n", "\n", "Let us actually dive into some basic inference rules:\n", "\n", "$$ \\begin{array}{c}\n", "\\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Const(f)}, \\sigma\\right) = f \\\\\n", "\\end{array}\\ \\text{(Const)} $$\n", "\n", "First note that the premises are empty, so no assumptions are needed for the conclusion.\n", "The inference rule above simply says the following:\n", "- Under any environment $\\sigma$, the expression `Const(f)` evaluates to `f`.\n", "\n", "Another basic inference rule is \n", "\n", "$$ \\begin{array}{c}\n", "\\\\\n", "\\hline\n", "\\eval(\\texttt{Ident(s)}, \\sigma) = \\sigma(s)\\\\\n", "\\end{array}\\ \\text{(Variable)} $$\n", "\n", "Under any environment $\\sigma$, the expression `Ident(s)` evaluates to $\\sigma(s)$. __But the reader may object__:\n", "what is $\\sigma$, what is $\\sigma(s)$ and what do we do if $\\sigma$ does not have a value for $s$. These\n", "are great questions. To resolve them, we must say what an environment is.\n", "\n", "### Environments\n", "\n", "An environment is a partial function from names of identifiers to their values.\n", "- Let $Domain(\\sigma)$ be the set of all variables defined in an environment.\n", "- Let $\\sigma(s)$ be the value mapped to by identifier $s$ if $s \\in Domain(\\sigma)$.\n", "\n", "\n", "### Basic Inferences (Continued)\n", "\n", "Resuming where we left off, we will now provide a refined rule \n", "\n", "$$\\begin{array}{c}\n", "s \\in \\text{Domain}(\\sigma)\\\\\n", "\\hline\n", "\\eval(\\texttt{Ident(s)},\\sigma) = \\sigma(s) \\\\\n", "\\end{array}\\ (\\text{Ident})$$\n", "\n", "Can you read this rule aloud for us?\n", "\n", "- Premise: the identifier $s$ belongs to $\\text{Domain}(\\sigma)$\n", "- Conclusion: $\\eval(\\texttt{Ident(s)},\\sigma) = \\sigma(s)$\n", "\n", "What about a rule for $s \\not \\in \\text{Domain}(\\sigma)$? Let us take a *raincheck* on it and get back to it in a short while.\n", "\n", "### Compound Inference\n", "\n", "Now that we have the basic rules for constants and identifiers, how do we proceed for the rest?\n", "\n", "#### Plus\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2\\\\\n", "\\hline\n", "\\eval\\left( \\texttt{Plus(e1,e2)}, \\sigma\\right) = (c_1 + c_2) \\\\\n", "\\end{array} (\\text{Plus}) $$\n", "\n", "\n", "#### Minus\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2 \\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Minus(e1, e2)}, \\sigma\\right) = (c_1 - c_2 ) \\\\\n", "\\end{array} (\\text{Minus}) $$\n", "\n", "#### Multiplication\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2 \\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Mult(e1, e2)}, \\sigma\\right) = (c_1 \\times c_2) \\\\\n", "\\end{array} (\\text{Mult}) $$\n", "\n", "#### Division\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2,\\ \\color{red}{c_2 \\not= 0}\\\\\n", "\\hline\n", "\\eval\\left( \\texttt{Div(e1, e2)}, \\sigma \\right) = (\\frac{c_1}{c_2} ) \\\\\n", "\\end{array} (\\text{Div}) $$\n", "\n", "Note the premise that $c_2 \\not= 0$. What happens if $c_2 = 0$? We will need to specify that under error handling.\n", "\n", "\n", "#### Other Rules\n", "We already saw an example for `Log`. Let's refine it by adding the condition that the argument of `Log` must always be positive.\n", "$$\\begin{array}{c}\n", "\\eval\\left( \\texttt{e}, \\sigma\\right) = c,\\ \\color{red}{c > 0} \\\\\n", "\\hline \n", "\\eval(\\texttt{Log(e)}, \\sigma) = \\log(c) \\\\\n", "\\end{array}\\ \\text{(Log)}$$\n", "\n", "Rather than a rule for each of Exp, Sine, Cosine: we can provide a single \"rule template\" -- a sort of macro that can be used for each of these rules.\n", "\n", "Before we do that let us define an association of each of these constructors with the functions they represent. Though it is obvious to us from the naming, it is not so to a computer. Therefore, we must pretend ignorance and specify the same.\n", "\n", "$$ f_{\\texttt{Exp}}(x) = e^x,\\ f_{\\texttt{Sine}}(x) = \\sin(x),\\ f_{\\texttt{Cosine}}(x) = \\cos(x) $$. \n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e}, \\sigma) = c,\\ T \\in \\{ \\texttt{Exp}, \\texttt{Sine}, \\texttt{Cosine} \\} \\\\\n", "\\hline\n", "\\eval\\left( \\texttt{T(e)}, \\sigma \\right) = f_{\\texttt{T}}(c)\n", "\\end{array} (\\text{InBuilt-Function-Application})$$\n", "\n", "## Handling Error\n", "\n", "Semantics is necessary not just to define the correct cases, but also to inform us what to do if there is an error.\n", "Often, we can distinguish between the types of errors that we would like to handle such as `DivideByZero`, `UndefinedVariable`, and `IllegalArgument`. Here, we will keep things simple and define just one error type __error__.\n", "\n", "So far, expressions could just take a value that was a double precision. We now augment it to take either \n", "a double precision value or a special value called __error__.\n", "\n", "The rules for producing double precision values have already been seen and recalled below once more.\n", "We will augment these rules to say that there is no error involved. The changes to the premises are highlighted in $\\color{red}{red}$ color.\n", "They mostly involve saying things like $c_i \\in \\mathbb{R}$ (i.e, a value $c_i$ is a real number).\n", "\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2,\\ \\color{red}{c_1\\in \\mathbb{R}, c_2 \\in \\mathbb{R}}\\\\\n", "\\hline\n", "\\eval\\left( \\texttt{Plus(e1, e2)}, \\sigma\\right) = (c_1 + c_2 ) \\\\\n", "\\end{array} (\\text{Plus}) $$\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2,\\ \\color{red}{c_1\\in \\mathbb{R}, c_2 \\in \\mathbb{R}} \\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Minus(e1,e2)}, \\sigma\\right) = (c_1 - c_2) \\\\\n", "\\end{array} (\\text{Minus}) $$\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e}, \\sigma) = c,\\ T \\in \\{ \\texttt{Exp}, \\texttt{Sine}, \\texttt{Cosine} \\}, \\color{red}{c \\in \\mathbb{R}}\\\\\n", "\\hline\n", "\\eval\\left( \\texttt{T(e)}, \\sigma \\right) = f_{\\texttt{T}}(c)\n", "\\end{array} (\\text{InBuilt-Function-Application})$$\n", "\n", "How about __error__? First we will summarize all situations that can produce a value __error__.\n", "\n", "$$ \\begin{array}{c}\n", " s \\not\\in \\text{Domain}(\\sigma) \\\\\n", " \\hline\n", " \\eval(\\texttt{Ident(s)}, \\sigma) = \\mathbf{error} \\\\\n", " \\end{array} (\\text{Ident-ERROR}) $$\n", "\n", "Other situations are also easy to see:\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = c_1,\\ \\eval(\\texttt{e2}, \\sigma) = c_2,\\ {c_1 \\in \\mathbb{R}, c_2 \\in \\mathbb{R}},\\ c_2 = 0\\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Div(e1, e2)}, \\sigma\\right) = \\mathbf{error} \\\\\n", "\\end{array} (\\text{Div-ERROR}) $$\n", "\n", "Another situation that comes to mind is `Log`.\n", "\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e}, \\sigma) = c,\\ {c \\in \\mathbb{R}},\\ {c \\leq 0} \\\\\n", "\\hline \n", "\\eval(\\texttt{Log(e)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array}\\ \\text{(Log-ERROR)}$$\n", "\n", "Now we need to write rules that say that once any child of an expression evaluates to an __error__ the expression itself evaluates to an error. This is very cumbersome to do in its fullest exquisite detail. Therefore, we will say so using appropriate notation to help us.\n", "\n", "Let us define the set of a __subterms__ of a given term inductively.\n", "- For expressions $e$ of the form `Plus(e1, e2)`, `Minus(e1, e2)`, and\n", "`Mult(e1, e2)` and `Div(e1, e2)`: \n", " $$ \\text{subterm(e)} = \\{ \\texttt{e1}, \\texttt{e2} \\} \\cup \\text{subterm}(\\texttt{e1}) \\cup \\text{subterm}(\\texttt{e2})$$.\n", "- For expressions $e$ of the form `T(e1)` where `T` can be `Log, Sine, Cosine, Exp`:\n", "$$\\text{subterm}(e) = \\{ \\texttt{e1} \\} \\cup \\text{subterm}(\\texttt{e1})$$\n", "\n", "__Example:__ Using the definintion, we can show that \n", "- subterm(`Plus(Const(1.0) , Mult(Const(2.0), Ident(\"y\"))`) is the set { `Const(1.0)`, `Mult(Const(2.0), Ident(\"y\"))`, `Const(2.0)`, `Ident(\"y\")` }\n", "\n", "\n", "Now we can write a single rule to deal with __error__:\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = \\mathbf{error},\\ \\texttt{e1} \\in \\text{subterm}(e) \\\\\n", "\\hline\n", "\\eval( \\texttt{e}, \\sigma) = \\mathbf{error} \\end{array} (\\text{Subterm-ERROR}) $$\n", "\n", "Let's interpret this rule:\n", "- Premise: under environment $\\sigma$ the expression `e1` evaluates to __error__ and `e1` is a subterm of `e`.\n", "- Conclusion: under environment $\\sigma$ the expression `e` evalutes to __error__.\n", "\n", "The bigstep semantics now clarify how some ambiguous function situations are to be handled. \n", "\n", "### Example \n", "\n", "- Consider the expression `Mult( Const(0.0), Div(Const(1.0), Const(0.0)))`. We are tempted to perform a `short circuit rule` as follows:\n", "\n", "$$\\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = 0.0,\\\\\n", "\\hline\n", "\\eval(\\texttt{Mult(e1, e2)}, \\sigma) = 0.0 \\end{array} (\\text{Shortciruit-Mult})$$\n", "\n", "\n", "This says that whenever the first argument of multiplication is a zero, let us short circuit the entire computation to zero without even examining them. As you can see this leads to a big problem. What if one of the unexamined terms\n", "causes an error? One can easily slip in such a statement in code for `evalExpr` and no one is any the wiser. The contradiction is only evident when\n", "we take the effort to write the big step semantics.\n", "\n", "\n", "- What about short circuiting error?\n", "\n", "$$ \\begin{array}{c}\n", "\\eval(\\texttt{e1}, \\sigma) = \\mathbf{error},\\\\\n", "\\hline\n", "\\eval\\left(\\texttt{Mult(e1, e2)}, \\sigma\\right) = \\mathbf{error} \\end{array} (\\text{Shortciruit-Mult-ERROR})$$\n", "\n", "This is subsumed by the Subterm-ERROR rule already stated. In fact, throwing an exception upon encountering an error seems consistent with the semantics written here especially if we map that exception to the value __error__. This will be entirely consistent with the Subterm-ERROR rule that states that if any subterm evaluates to __error__ the expression as a whole also evaluates to an error.\n", "\n", "\n", "\n", "\n", "## From Big-Step Semantics To Code\n", "\n", "Note that while big-step semantics are very good at expressing how expressions evaluate to their intended values at a high level, it is not good in expressing issues such as \n", "- What is the order of evaluation? For instance we would like to say that if we have an expression `Plus(e1,e2)` we evalute this from left to right, starting with `e1` and ending at `e2`.\n", "- How do we deal with side effects? (currently there are no side effects) and so this aspect of our discussion needs to await a future lecture.\n", "\n", "To nail down such issues, we may have to give something called _small step semantics_. However, we will skip small step semantics for now and await such a time when our language has some side effects and mutation, which are both non-issues at present.\n", "\n", "For now, let us see how the semantics we have expressed thus far can be translated faithfully into code. Let us make this methodical. We first systematically capture the possible values that an expression can produce. These include the special value `Error` or a `Number`" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mValue\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mError\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mNumber\u001b[39m" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait Value\n", "case object Error extends Value\n", "case class Number(c: Double) extends Value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First we define some convenient functions to compute expected operations over the newly defined values." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mobject\u001b[39m \u001b[36mEvalExprObject\u001b[39m" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// For convenience, we will package everything into an object. \n", "// This object has the main function evalExpr as well as the helper functions \n", "\n", "// Note: object in Scala is different from class. when you declare something as an object\n", "// then there can be exactly one instance of this in the memory and it will be\n", "// called by the same name EvalExprObject.\n", "// Therefore, a function foo in EvalExprObject will be called as EvalExprObject.foo(...)\n", "\n", "object EvalExprObject { \n", "\n", " \n", " // Function binaryOperation will take two sub-expressions\n", " // evaluate the subexpressions `e1`, `e2`\n", " // Check if they are error\n", " // If not apply a function `resFun` provided by the user to the values from \n", " // evaluating `e1`, `e2`\n", " def binaryOperation(e1: Expr, \n", " e2: Expr, \n", " resFun: (Double, Double) => Value, \n", " env: Map[String, Double] ) = {\n", " val v1 = this.evalExpr(e1, env) // Evaluate e1 --> recursive\n", " val v2 = this.evalExpr(e2, env) // Evaluate e2\n", " (v1, v2) match {\n", " case (_, Error) => Error // If either is Error then result is Error\n", " case (Error, _) => Error \n", " case (Number(f1), Number(f2)) => resFun(f1, f2) //Otherwise apply function\n", " }\n", " \n", " }\n", " \n", " // Compute Log if the value is not error \n", " def logValue(val0: Value): Value = val0 match {\n", " case Error => Error\n", " case Number(c1) if c1 > 0.0 => Number( math.log(c1) )\n", " case _ => Error\n", " }\n", " // compute exp if the value is not error\n", " def expValue(val0: Value): Value = val0 match {\n", " case Error => Error\n", " case Number(c1) => Number( math.exp(c1) )\n", " }\n", " // compute sine if the value is not error\n", " def sineValue(val0: Value): Value = val0 match {\n", " case Error => Error\n", " case Number(c1) => Number( math.sin(c1) )\n", " }\n", " // compute cosine if the value is not error \n", " def cosineValue(val0: Value): Value = val0 match {\n", " case Error => Error\n", " case Number(c1) => Number( math.cos(c1) )\n", " }\n", " def evalExpr (e: Expr, env: Map[String, Double]): Value = e match { \n", " // Split cases on what e can be\n", "\n", " case Const(f) => Number(f) // e is a constant\n", "\n", " // e is an identifier\n", " case Ident (str) => { if (env.contains(str)){ // str \\in domain(env) \n", " Number( env(str) ) //it is part of the environment\n", " } else {\n", " Error // it is not part of the environment\n", " }\n", " }\n", " \n", " // e is of the form Plus of two subexpressions\n", " case Plus(e1, e2) => {\n", " // Define the operation of adding two numbers\n", " def add2(x: Double, y: Double): Value = Number(x + y)\n", " // Use our helper function that was defined already\n", " this.binaryOperation(e1, e2, add2, env)\n", " }\n", "\n", " // e is of the form Minus of two subexpressions\n", " case Minus(e1, e2) => {\n", " def sub2(x: Double, y: Double): Value = Number(x - y)\n", " this.binaryOperation(e1, e2, sub2, env)\n", " }\n", "\n", " // e is of the form multiply two subexpressions\n", " case Mult(e1, e2) => {\n", " def mult2(x: Double, y: Double): Value = Number(x * y)\n", " this.binaryOperation(e1, e2, mult2, env)\n", " }\n", "\n", " // e is of the form division of two subexpressions\n", " case Div(e1, e2) => {\n", " // Carefully define division to handle divide by zero case as well.\n", " def div2(x: Double, y: Double): Value = \n", " { if (y != 0.0 ) Number(x/y) else Error }\n", " //Use the function already defined\n", " this.binaryOperation(e1, e2, div2, env)\n", " }\n", "\n", " case Log(e) => this.logValue(evalExpr(e, env))\n", "\n", " case Exp(e) => this.expValue( evalExpr(e, env))\n", "\n", " case Sine(e) => this.sineValue( evalExpr(e, env))\n", "\n", " case Cosine(e) => this.cosineValue(evalExpr(e, env))\n", " }\n", " \n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us create an environment that maps some variables names $x, y, Zzz, w, l$ to some values." ] }, { "cell_type": "code", "execution_count": 4, "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": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val myEnvironment: Map[String, Double] = Map(\"x\" -> 2.0, \n", " \"y\" -> 1.5, \n", " \"Zzz\" -> 2.8, \n", " \"w\" -> 15.2, \n", " \"l\" -> 129.3)" ] }, { "cell_type": "code", "execution_count": 5, "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", " e1 = \u001b[33mCosine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mSine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)),\n", " e2 = \u001b[33mExp\u001b[39m(\n", " e = \u001b[33mMinus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"Zzz\"\u001b[39m))\n", " )\n", " )\n", " )\n", ")" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x = Ident(\"x\")\n", "val y = Ident(\"y\")\n", "val z = Ident(\"Zzz\")\n", "// cos(x) + sin(y) + exp(x - (y+z))\n", "val expr1 = Plus(Cosine(x), Plus(Sine(y), Exp(Minus(x, Plus(y,z)))))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres6\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mNumber\u001b[39m(c = \u001b[32m0.6816069937797158\u001b[39m)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EvalExprObject.evalExpr(expr1, myEnvironment)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "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[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mExp\u001b[39m(e = \u001b[33mConst\u001b[39m(f = \u001b[32m1.5\u001b[39m)),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mSine\u001b[39m(e = \u001b[33mConst\u001b[39m(f = \u001b[32m2.0\u001b[39m)),\n", " e2 = \u001b[33mCosine\u001b[39m(e = \u001b[33mMult\u001b[39m(e1 = \u001b[33mConst\u001b[39m(f = \u001b[32m1.2\u001b[39m), e2 = \u001b[33mConst\u001b[39m(f = \u001b[32m2.4\u001b[39m)))\n", " )\n", ")\n", "\u001b[36mexpr3\u001b[39m: \u001b[32mDiv\u001b[39m = \u001b[33mDiv\u001b[39m(\n", " e1 = \u001b[33mDiv\u001b[39m(\n", " e1 = \u001b[33mMinus\u001b[39m(\n", " e1 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m),\n", " e2 = \u001b[33mMult\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m))\n", " ),\n", " e2 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(f = \u001b[32m1.2\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m))\n", " ),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mConst\u001b[39m(f = \u001b[32m1.5\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " ),\n", " e2 = \u001b[33mConst\u001b[39m(f = \u001b[32m2.3\u001b[39m)\n", ")" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val w = Ident(\"w\")\n", "// exp(1.5) + sin(2.0) + cos(1.2*2.4)\n", "val expr2 = Plus( \n", " Exp(Const(1.5)), \n", " Plus( Sine(Const(2.0)), \n", " Cosine( Mult( \n", " Const(1.2), \n", " Const(2.4))\n", " )\n", " )\n", " )\n", "//(((w+x*y) - (1.2+w))/(1.5+(w+x)))/2.3\n", "val expr3 = Div(Div(Minus( Plus(w, Mult(x, y)), Plus(Const(1.2), w)) , \n", " Plus(Const(1.5), Plus(w, x) )), Const(2.3))" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres8\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mNumber\u001b[39m(c = \u001b[32m4.4250071847657715\u001b[39m)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EvalExprObject.evalExpr(expr2, myEnvironment)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres9\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mNumber\u001b[39m(c = \u001b[32m0.04185073238781681\u001b[39m)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EvalExprObject.evalExpr(expr3, myEnvironment)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mexpr4\u001b[39m: \u001b[32mLog\u001b[39m = \u001b[33mLog\u001b[39m(\n", " e = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)),\n", " e2 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(f = \u001b[32m-18.7\u001b[39m))\n", " )\n", ")\n", "\u001b[36mres10_1\u001b[39m: \u001b[32mValue\u001b[39m = Error\n", "\u001b[36mexpr5\u001b[39m: \u001b[32mDiv\u001b[39m = \u001b[33mDiv\u001b[39m(\n", " e1 = \u001b[33mConst\u001b[39m(f = \u001b[32m1.0\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)),\n", " e2 = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"w\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(f = \u001b[32m-18.7\u001b[39m))\n", " )\n", ")\n", "\u001b[36mres10_3\u001b[39m: \u001b[32mValue\u001b[39m = Error" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val expr4 = Log(Plus(Plus(x, y), Plus(w, Const(-18.7))))\n", "EvalExprObject.evalExpr(expr4, myEnvironment)\n", "\n", "val expr5 = Div(Const(1.0), Plus(Plus(x, y), Plus(w, Const(-18.7))))\n", "EvalExprObject.evalExpr(expr5, myEnvironment)" ] } ], "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 }