{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lettuce: A Language With Let Bindings\n", "\n", "Originally by Sriram Sankaranarayanan \n", "\n", "Modified by Ravi Mangal \n", "\n", "Last Modified: Feb 19, 2025.\n", "\n", "---\n", "We will now introduce our first language called _Lettuce_, a language with let bindings. This language is inspired by an existing family of languages called `ML` (Meta Language), which has been implemented in general purpose langauges such as `SML`, `OCaml`, `Elm` and so on. The Lettuce language will illustrate the following important concepts:\n", "\n", "- Immutable data and environments.\n", "- Function calls, closures and recursive functions.\n", "- Mutable data through references.\n", "\n", "Read more about ML family of languages here : https://en.wikipedia.org/wiki/ML_(programming_language)\n", "\n", "Let's build some example programs to understand the central concept in our let language: the _let binding_.\n", "\n", "## Let Bindings in Lettuce\n", "\n", "Let bindings allow us to **bind** an identifier to a value and use it inside a body expression, using the syntax of the following form\n", "\n", "`let (symbolName) = (defining expression) in (body expression)`\n", "\n", "_Let's_ practice writing programs in Lettuce (no pun intended).\n", "\n", "#### Example 1\n", "\n", "~~~\n", "let x = 3.5 in x + x\n", "~~~\n", "\n", "First of all, it defines a symbol named `x`. The defining expression here is `3.5`, and thus evaluates to `3.5`.\n", "The body expression is `x + x`. With `x` bound to `3.5`, what does this evaluate to? The answer is `7.0`.\n", "\n", "Therefore the whole expression can be successively rewritten as follows:\n", "\n", "__eval__ ( \"let x = 3.5 in x + x\") -->  __eval__( 3.5 + 3.5 ) --> __eval__ (7.0) --> 7.0\n", "\n", "\n", "#### Example 2\n", "\n", "We can now nest let bindings as follows:\n", "\n", "~~~\n", "let x = 3.0 in \n", " let y = 4.5 - x in \n", " x + 2.0 * y\n", "~~~\n", "\n", "This has two let bindings:\n", "\n", "Outer binding:\n", "\n", "~~~\n", "let x = 3.0 in ((body expression # 1))\n", "~~~\n", "\n", "binds the symbol `x` to the defining expression `3.0` and the body\n", "expression \\# 1 is given by \n", "\n", "\n", "~~~\n", "let y = 4.5 in x + 2.0 * y\n", "~~~\n", "\n", "binds the symbol `y` to the defining expression `4.5 - x` and the body expression \\# 2 is\n", "given by ` x + 2.0 * y`.\n", "\n", "Now that we have picked it apart, let us evaluate this expression ourselves.\n", "\n", "\n", "__eval__(\"let x = 3.0 in let y = 4.5 - x in x + 2.0 * y\") --> __eval__ (\" let y = 4.5 - 3.0 in 3.0 + 2.0 * y \" ) \n", " --> __eval__(\"let y = 1.5 in 3.0 + 2.0 * y\") --> __eval__ (3.0 + 2.0 * 1.5) --> __eval__(6.0) --> 6.0 \n", "\n", "\n", "#### Example 3\n", "\n", "Let us do one more with a different nesting of let bindings.\n", "\n", "~~~\n", "let x = ( let y = 5 in y * y ) in \n", " let z = 15 * x in \n", " x - z \n", "~~~\n", "\n", "Thus far we saw body expressions having let bindings. Now we can allow let bindings for the defining expressions as well. \n", "\n", "~~~\n", "let x = (defining expression # 1) in (body expression # 1)\n", "~~~\n", "\n", "Defining expression \\# 1 itself is\n", "\n", "~~~\n", "let y = 5 in y * y\n", "~~~\n", "\n", "The body expression \\# 1 is \n", "\n", "~~~\n", "let z = 15 * x in x - z\n", "~~~\n", "\n", "\n", "How do we evaluate it? Now is a good time to break up the evaluation of a let binding \n", "\n", "~~~\n", "let sym = (defining expression) in (body expression)\n", "~~~\n", "\n", "as follows: \n", "\n", "1. Evaluate the defining expression : __eval__ (defining expression)\n", "2. Associate the symbol `sym` with the result from step 1.\n", "3. Evaluate the body expression but now remember the association from step 1.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Let Bindings in Scala\n", "\n", "Scala does not have let bindings with the same syntax but it has\n", "let bindings through the `val` declaration.\n", "\n", "~~~\n", "val x = 10\n", "val y = x + 10\n", "val z = y + 10\n", "(x + y + z)\n", "~~~\n", "\n", "Here we have assigned `x` to 10 and `y` to `x+10` and then `z` to `y + 10` with `x+y+z` being\n", "the overall value of our code fragment above.\n", "\n", "Compare with how we could write something similar in Lettuce\n", "\n", "~~~\n", "let x = 10 in \n", " let y = x + 10 in \n", " let z = y + 10 in \n", " x + y + z\n", "~~~\n", "\n", "\n", "Here is another example in Scala:\n", "\n", "~~~\n", "val z = { \n", " val x = 10 \n", " val y = 15\n", " x + y\n", " }\n", "return z + 10\n", "~~~\n", "\n", "In Lettuce, we would write\n", "\n", "~~~\n", "let z = ( \n", " let x = 10 in \n", " let y = 15 in \n", " x + y \n", " ) \n", " in \n", " z + 10\n", "~~~\n", "\n", "Now you appreciate how let bindings also arise in Scala without the `let id = defining-expr in body-expr` syntax.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Scoping in Lettuce\n", "\n", "It is now important to understand scoping rules. Scoping rules allow us to understand which let binding \n", "applies to a given identifier `x`.\n", "\n", "Consider the following program\n", "\n", "~~~\n", "let y = 15 in \n", " let x = 10 in x + y \n", "~~~\n", "\n", "Consider the expression `x + y`. You can understand which let binding has defined `x` and which let binding has\n", "defined `y`.\n", "\n", "However, consider the more complicated case:\n", "\n", "~~~\n", "let x = 10 in \n", "let x = x + 10 in \n", "let x = x + 10 in \n", " x + 10\n", "~~~\n", "\n", "Here we are repeatedly redefining `x` however the right hand sides refer back the left hand side. Is this allowed?\n", "The equivalent code in Scala raises an error since a statement like `val x = x + 10` in Scala is forbidden.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "cmd0.sc:2: x is already defined as value x\n", "val x = x + 10 \n", " ^cmd0.sc:3: x is already defined as value x\n", "val x = x + 10 \n", " ^Compilation Failed" ] }, { "ename": "", "evalue": "", "output_type": "error", "traceback": [ "Compilation Failed" ] } ], "source": [ "val x = 10\n", "val x = x + 10 \n", "val x = x + 10 \n", "x + 10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, this is a matter of definition. In Lettuce, we could pretend that the scoping rules allow the defining expression in a let binding to be evaluated first under previously defined let bindings.\n", "\n", "Therefore, the code fragment \n", "\n", "~~~\n", "let x = 10 in \n", " let x = x + 10 in \n", " let x = x + 10 in \n", " x + 10\n", "~~~\n", "\n", "is entirely equivalent to \n", "\n", "~~~\n", "let x0 = 10 in \n", " let x1 = x0 + 10 in \n", " let x2 = x1 + 10 in \n", " x2 + 10\n", "~~~\n", "\n", "\n", "How about this one?\n", "\n", "~~~\n", "let y = 15 in \n", " let x = ( let y = 10 in y + y ) in \n", " y + x \n", "~~~\n", "\n", "There are two places where y is being defined. So which binding of `y` matters for `y + x`? \n", "\n", "Answer is that this is entirely equal to \n", "\n", "~~~\n", "let y1 = 15 in \n", " let x1 = ( let y2 = 10 in y2 + y2) in \n", " y1 + x1 \n", "~~~\n", "\n", "Thus the value of `y` is `15` when evaluating `y + x` but equals `10` when evaluating `y + y`.\n", "\n", "Scoping is not intuitive but very important to understand.\n", "\n", "The same holds in Scala.\n", "\n", "~~~\n", "val y = 15\n", "val x = { \n", " val y = 10\n", " y + y\n", " }\n", "x + y\n", "~~~" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "y = 15, x + y = 35" ] }, { "data": { "text/plain": [ "\u001b[36my\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m15\u001b[39m\n", "\u001b[36mx\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m20\u001b[39m" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val y = 15\n", "val x = { \n", " val y = 10 // this overshadows the val y = 15 declaration\n", " y + y\n", " } // the scope for val y = 10 on line 3 ends here, the val y = 15 declaration comes back in scope.\n", "print(s\"y = $y, x + y = ${x+y}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic Types in Lettuce\n", "\n", "To begin with, we will allow variables in Lettuce to be double precision numbers and Booleans. Later, of course, we will add more types to the language. This enables to allow the entire grammar of expressions and conditional expressions we have previously defined into Lettuce.\n", "\n", "~~~\n", "let x = 25 in \n", " let y = exp(x) in \n", " let z = (x >= y) in \n", " if (z) \n", " then y \n", " else x\n", "~~~\n", "\n", "Here `x` is defined as a double precision value `25` and `y` computes the exponential of `x`. Finally, `z` is a Boolean that computes `true` if `x >= y` and `false` otherwise. Finally, the entire expression evaluates to `y` if `z` is true otherwise to x\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Function Calls in Lettuce\n", "\n", "We will allow definitions of functions and calls to them in Lettuce. All functions in Lettuce can have just one argument to them.\n", "\n", "~~~\n", "let w = 3.1415 in \n", "let f = function (x) \n", " let y = 2 * x - 5 in \n", " let z = 2 * w * x in \n", " y * sin(z)\n", " in \n", " w * w + f(1)\n", "~~~\n", "\n", "Here we have defined a function `f` using let bindings.\n", "\n", "~~~\n", "let = function () \n", " \n", " in \n", " \n", "~~~\n", "\n", "For the example above, the `` is `f`, the `` is `x`, \n", "the `` is \n", "~~~\n", "let y = 2 * x - 5 in \n", " let z = 2 * w * x in \n", " y * sin(z)\n", "~~~\n", "the other `` is ` w * w + f(1)`.\n", "\n", "It is important to understand scoping rules for a function call. First, the variable `x` inside the body of `f` \n", "refers to its formal parameter. What about the variable `w` inside the body of `f`? It must refer to the\n", "let binding `let w = 3.1415 in ` that immediately preceds it. If we made this choice, it is called\n", "_static scoping_. i.e., variables inside a function are resolved at the time of definition of the function.\n", "A different choice can be made called _dynamic scoping_ would resolve the variable not at the time when\n", "`f` is defined but when `f` is actually called.\n", "\n", "For instance, consider\n", "\n", "~~~\n", "let w = 3.1415 in \n", "let f = function (x) \n", " x * sin(2 * w * x) \n", " in \n", "let w = 3.1415/2.0 in \n", " w * w + f(1)\n", "~~~\n", "\n", "Under static scoping, the `w` inside the body of function `f` resolves to `3.1415`, whereas the `w` \n", "at the call to f `w * w + f(1)` resolves to `3.1415/2.0`. \n", "\n", "However, under dynamic scoping, the value of `w` inside the function `f` is bound to whatever value it takes\n", "when `f` is called. Thus, it would be bound to `3.1415/2.0` since that is what `w` is when we call `f(1)`.\n", "Dynamic scoping can be \"counter intuitive\" and hard to reason about. Modern programming languages typically use static scoping.\n", "\n", "What kind of scoping does Scala have? Can we try? First of all, Scala does not permit redefining a `val` inside the same scope. The program below will raise a syntax error (try it).\n", "\n", "~~~\n", "val w = 25\n", "def f(x: Int): Int = x + w\n", "val w = 50\n", "val z = f(30)\n", "~~~\n", "\n", "But we can run a program like this and conclude that Scala does static scoping as well.\n", " " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "From inside : w = 10" ] }, { "data": { "text/plain": [ "\u001b[36mw\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m10\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mf\u001b[39m\n", "\u001b[36mz\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m30\u001b[39m" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val w = 10\n", "def f(x: Int): Int = { print(s\"From inside : w = $w\"); x + w }\n", "val z = {\n", " val w = 20\n", " f(20)\n", "}\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Currying Functions\n", "\n", "Lettuce has just one argument functions. How do we do multiple argument funcitons in Lettuce? Simple, we can always use **currying** to define a function with multiple arguments.\n", "\n", "~~~\n", "let f = function (x) function (y) x + y in \n", " f (10) (20)\n", "~~~\n", "\n", "This defines a function of two arguments `f` as first a function that takes in `x` and returns\n", "a function that takes in `y` and adds ` x + y`.\n", "\n", "An equivalent way of writing would be\n", "\n", "~~~\n", "let f = function (x) \n", " let g = function (y) x + y in \n", " g\n", " in \n", " let y1 = f(10) in \n", " y1(20)\n", "~~~\n", "\n", "Currying is also supported in Scala. Let us take an example." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mf\u001b[39m\n", "\u001b[36mv1\u001b[39m: \u001b[32mInt\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd2$Helper$$Lambda$2135/0x0000000801605040@30726488\n", "\u001b[36mv2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m30\u001b[39m" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def f (x: Int) (y: Int) = x + y\n", "\n", "val v1: Int => Int = f(10)\n", "\n", "val v2 = v1(20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Currying is very useful in the following situation: \n", "- Apply some operations to your inputs and\n", "- Call a user defined function on the result.\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mmultiplyAndProcess\u001b[39m\n", "\u001b[36mv1\u001b[39m: (\u001b[32mInt\u001b[39m => \u001b[32mInt\u001b[39m) => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd2$Helper$$Lambda$2262/0x0000000100bec040@17ccb5f\n", "\u001b[36mv2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m400\u001b[39m" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def multiplyAndProcess(x: Int, y:Int) (f: Int => Int) = {\n", " f ( x* y)\n", "}\n", "\n", "val v1: (Int => Int) => Int = multiplyAndProcess(20, 10)\n", "val v2 = v1(x => 2 * x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Grammar for Lettuce\n", "\n", "We are now ready to define a grammar for Lettuce.\n", "\n", "$$\\begin{array}{rcll}\n", "\\mathbf{Program} & \\rightarrow & TopLevel(\\mathbf{Expr}) \\\\[5pt]\n", "\\mathbf{Expr} & \\rightarrow & Const(\\mathbf{Number}) \\\\\n", " & | & True \\\\\n", " & | & False \\\\\n", " & | & Ident(\\mathbf{Identifier}) \\\\\n", " & | & Plus(\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & Minus(\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & Mult (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & Div (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & Log (\\mathbf{Expr}) \\\\\n", " & | & Exp (\\mathbf{Expr}) \\\\\n", " & | & Sine (\\mathbf{Expr}) \\\\\n", " & | & Cosine (\\mathbf{Expr}) \\\\\n", " & | & Geq (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & Eq (\\mathbf{Expr}, \\mathbf{Expr}) \\\\\n", " & | & And ( \\mathbf{Expr}, \\mathbf{Expr} ) \\\\\n", " & | & Or ( \\mathbf{Expr}, \\mathbf{Expr} ) \\\\\n", " & | & Not ( \\mathbf{Expr}) \\\\\n", " & | & IfThenElse(\\mathbf{Expr}, \\mathbf{Expr}, \\mathbf{Expr}) & \\text{if (expr) then expr else expr} \\\\\n", " & | & Let( \\mathbf{Identifier}, \\mathbf{Expr}, \\mathbf{Expr}) & \\text{let identifier = expr in expr} \\\\\n", " & | & FunDef( \\mathbf{Identifier}, \\mathbf{Expr}) & \\text{function (identifier) expr } \\\\ \n", " & | & FunCall(\\mathbf{Expr}, \\mathbf{Expr}) & \\text{function call - identifier(expr)} \\\\[5pt]\n", " \\textbf{Number} & \\rightarrow & \\text{All double precision numbers in Scala}\\\\\n", "\\textbf{Identifier} & \\rightarrow & \\text{All strings in Scala}\\\\\n", "\\end{array}$$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It helps to how programs written in the concrete syntax translate into abstract syntax using the grammar.\n", "\n", "### Example 1\n", "\n", "~~~\n", "let x = 10 + 15 in \n", " let y = x >= 25 in \n", " if (y) \n", " then x \n", " else x - 35\n", "~~~\n", "\n", "will translate to \n", "\n", "~~~\n", "Let(\"x\", Plus(Const(10), Const(15)), \n", " Let(\"y\", Geq(Ident(\"x\"), Const(25)), \n", " IfThenElse( Ident(\"y\"), \n", " Ident(\"x\"), \n", " Minus(Ident(\"x\"), Const(35))\n", " )\n", " )\n", " )\n", "~~~\n", "\n", "### Example 2\n", "\n", "~~~\n", "let square = function (w) w * w in \n", " 25 + square(25)\n", "~~~\n", "\n", "will translate to \n", "\n", "~~~\n", "Let(\"square\", FunDef(\"w\", Mult(Ident(\"w\"), Ident(\"w\")) ),\n", " Plus(Const(25), FunCall(Ident(\"square\"), Const(25)))\n", "~~~\n", " " ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mProgram\u001b[39m\n", "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mTopLevel\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mConst\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mTrue\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mFalse\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\n", "defined \u001b[32mclass\u001b[39m \u001b[36mGeq\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[32mclass\u001b[39m \u001b[36mIfThenElse\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mLet\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mFunDef\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mFunCall\u001b[39m" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait Program\n", "sealed trait Expr\n", "\n", "case class TopLevel(e: Expr) extends Program\n", "\n", "case class Const(v: Double) extends Expr // Expr -> Const(v)\n", "case object True extends Expr // Expr -> True\n", "case object False extends Expr // Expr -> False\n", "case class Ident(s: String) extends Expr // Expr -> Ident(s)\n", "\n", "// Arithmetic Expressions\n", "case class Plus(e1: Expr, e2: Expr) extends Expr // Expr -> Plus(Expr, Expr)\n", "case class Minus(e1: Expr, e2: Expr) extends Expr // Expr -> Minus(Expr, Expr)\n", "case class Mult(e1: Expr, e2: Expr) extends Expr // Expr -> Mult (Expr, Expr)\n", "case class Div(e1: Expr, e2: Expr) extends Expr // Expr -> Mult(Expr, 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", "// Boolean Expressions\n", "case class Geq(e1: Expr, e2:Expr) extends Expr\n", "case class Eq(e1: Expr, e2: Expr) extends Expr\n", "case class And(e1: Expr, e2: Expr) extends Expr\n", "case class Or(e1: Expr, e2: Expr) extends Expr\n", "case class Not(e: Expr) extends Expr\n", "\n", "//If then else\n", "case class IfThenElse(e: Expr, eIf: Expr, eElse: Expr) extends Expr\n", "\n", "//Let bindings\n", "case class Let(s: String, defExpr: Expr, bodyExpr: Expr) extends Expr\n", "\n", "//Function definition\n", "case class FunDef(param: String, bodyExpr: Expr) extends Expr\n", "\n", "// Function call\n", "case class FunCall(funCalled: Expr, argExpr: Expr) extends Expr\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp1\u001b[39m: \u001b[32mTopLevel\u001b[39m = \u001b[33mTopLevel\u001b[39m(\n", " \u001b[33mLet\u001b[39m(\n", " \u001b[32m\"x\"\u001b[39m,\n", " \u001b[33mPlus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m10.0\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m15.0\u001b[39m)),\n", " \u001b[33mLet\u001b[39m(\n", " \u001b[32m\"y\"\u001b[39m,\n", " \u001b[33mGeq\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m25.0\u001b[39m)),\n", " \u001b[33mIfThenElse\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mMinus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m35.0\u001b[39m)))\n", " )\n", " )\n", ")" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p1 = TopLevel(Let(\"x\", Plus(Const(10), Const(15)), \n", " Let(\"y\", Geq(Ident(\"x\"), Const(25)), \n", " IfThenElse( Ident(\"y\"), \n", " Ident(\"x\"), \n", " Minus(Ident(\"x\"), Const(35))\n", " )\n", " )\n", " ))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp2\u001b[39m: \u001b[32mTopLevel\u001b[39m = \u001b[33mTopLevel\u001b[39m(\n", " \u001b[33mLet\u001b[39m(\n", " \u001b[32m\"square\"\u001b[39m,\n", " \u001b[33mFunDef\u001b[39m(\u001b[32m\"w\"\u001b[39m, \u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"w\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"w\"\u001b[39m))),\n", " \u001b[33mPlus\u001b[39m(\u001b[33mConst\u001b[39m(\u001b[32m25.0\u001b[39m), \u001b[33mFunCall\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"square\"\u001b[39m), \u001b[33mConst\u001b[39m(\u001b[32m25.0\u001b[39m)))\n", " )\n", ")" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p2 = TopLevel(Let(\"square\", FunDef(\"w\", Mult(Ident(\"w\"), Ident(\"w\")) ), Plus(Const(25), FunCall(Ident(\"square\"), Const(25)))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Well Formed vs. Ill Formed Programs\n", "\n", "You may already note that the abstract syntax allows us to write all kinds of programs that should be clearly illegal. Here are some examples:\n", "\n", "~~~\n", "let x = y + z in y * z\n", "~~~\n", "\n", "`y` and `z` are undeclared at the time we are binding `y+z` to `x`, same problem when we evaluate `y * z`.\n", "\n", "~~~\n", "let y = 10 in \n", "let z = 15 in \n", "let x = y + (z >= 25) in \n", " false\n", "~~~\n", "\n", "We are trying to add a number `y` and a boolean expression `z >= 25` what is the meaning?\n", "\n", "~~~\n", "let y = 15 in \n", "let z = 25 + function (w) w * w in \n", " y(31)\n", "~~~\n", "\n", "Wow! where to begin? First of all, we are adding 25 to a function definition `function (w) w * w` and\n", "we are calling `y(31)` when `y` is not even a function.\n", "\n", "Programs like these are really confusing. Do we even allow them? Why can't we just forbid them in the abstract syntax tree?\n", "\n", "__Fact:__ Abstract Syntax Trees are built from Context Free Grammars. Unfortunately, due to limitations arising\n", "from context freedom (i.e, LHS of each rule is just a single nonterminal), we cannot really enforce rules like \n", "- Variables should be declared before use.\n", "- Boolean expressions cannot be added to integer expressions\n", "- Function calls can only be made over proper functions.\n", "\n", "Programming languages generally have different enforcement mechanisms:\n", "- Check if a program is _well-formed_ while parsing the program.\n", "- Check types of expressions after parsing (typically, during compilation of) the program (static type checking).\n", "- Check types of expressions while interpreting/evaluating the program (runtime typechecking).\n", "- A combination of above.\n", "\n", "Let us use Scala as an example. Certain issues are caught at compile time.\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "cmd7.sc:1: overloaded method value + with alternatives:\n", " (x: Int)Int \n", " (x: Char)Int \n", " (x: Short)Int \n", " (x: Byte)Int\n", " cannot be applied to (Boolean)\n", "def f(x: Int): Int = { x + (x >= 233) }\n", " ^Compilation Failed" ] }, { "ename": "", "evalue": "", "output_type": "error", "traceback": [ "Compilation Failed" ] } ], "source": [ "//Adding a number to a boolean, Scala will catch it right away\n", "def f(x: Int): Int = { x + (x >= 233) }\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "cmd7.sc:1: type mismatch;\n", " found : Int(233)\n", " required: String\n", "def comp(x: String): Boolean = x >= 233\n", " ^Compilation Failed" ] }, { "ename": "", "evalue": "", "output_type": "error", "traceback": [ "Compilation Failed" ] } ], "source": [ "//Comparing a string to a number?\n", "def comp(x: String): Boolean = x >= 233" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "cmd3.sc:2: Int does not take parameters\n", "def nonsense(x: Int): Int = x(355)\n", " ^\n", "Compilation Failed" ] } ], "source": [ "// Trying to call a number?\n", "def nonsense(x: Int): Int = x(355)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mincompleteCase\u001b[39m" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def incompleteCase(x: (Int, Int, Int)): Int = x match {\n", " case (i, j, k) if i == 0 => j - k\n", " case (i, j, k) if j > 0 => i - k\n", " case (i, j, k) if k > 0 => j - i\n", " // Clearly more cases are needed here. \n", " // Will Scala complain when compiling this?\n", "}" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7" ] }, { "ename": "", "evalue": "", "output_type": "error", "traceback": [ "\u001b[31mscala.MatchError: (2,-3,-5) (of class scala.Tuple3)\u001b[39m\n ammonite.$sess.cmd7$Helper.incompleteCase(\u001b[32mcmd7.sc\u001b[39m:\u001b[32m1\u001b[39m)\n ammonite.$sess.cmd8$Helper.(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m2\u001b[39m)\n ammonite.$sess.cmd8$.(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m7\u001b[39m)\n ammonite.$sess.cmd8$.(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m-1\u001b[39m)" ] } ], "source": [ "// RUNTIME CHECKING : scala will complain when running\n", "print(incompleteCase( (0, 2, -5) ))\n", "incompleteCase( (2, -3, -5) )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In that same vein, we can catch errors in Lettuce programs at compile time. \n", "- Variables should be declared before use (we can catch this using a special declare before use check).\n", "- Boolean expressions cannot be added to integer expressions (we will catch this when we do type checking).\n", "- Function calls can only be made over proper functions (we will catch this during type checking).\n", "\n", "## Example: Checking Whether Variables Are Declared Before Usage\n", "\n", "Let us define inference rules that will help us check if an expression is well-formed, i.e., contains no variables that have not been declared before use. To do so, we will define a set of currently declared variables that are in-scope called $S$. \n", "\n", "We will define inference rules for _judgements_ of the form: $WellFormed(\\texttt{e}, S)$ that says that expression `e` is _WellFormed_ under the set of declared in scope variables $S$.\n", "\n", "Constants are well formed under any set $S$. \n", "\n", "$$ \\begin{array}{c}\n", "\\\\\n", "\\hline\n", "WellFormed(\\texttt{Const(f)}, S) \\\\\n", "\\end{array} \\text{(const-rule)} $$\n", "\n", "The rules for `True` and `False` are similar.\n", "Identifiers are well formed only if they belong to $S$:\n", "\n", "$$\\begin{array}{c}\n", "x \\in S \\\\\n", "\\hline\n", "WellFormed(\\texttt{Ident(x)}, S) \\\\\n", "\\end{array} \\text{(ident-rule)} $$\n", "\n", "The rules for binary operator `Plus, Minus, Mult, Div, Geq, Eq, And, Or` are all very similar.\n", "\n", "$$ \\begin{array}{c}\n", "WellFormed(\\texttt{e1}, S) \\;\\;\\; WellFormed(\\texttt{e2}, S)\\;\\;\\; T \\in \\{ \\texttt{Plus}, \\texttt{Minus}, \\texttt{Mult}, \\texttt{Div}, \\texttt{Geq}, \\texttt{Eq}, \\texttt{And}, \\texttt{Or} \\} \\\\\n", "\\hline\n", "WellFormed(\\texttt{T(e1, e2)}, S) \\\\\n", "\\end{array} \\text{(binary-op-rule)} $$\n", "\n", "Likewise, for unary operators \n", "\n", "$$ \\begin{array}{c}\n", "WellFormed(\\texttt{e1}, S) \\;\\;\\; T \\in \\{ \\texttt{Log}, \\texttt{Exp}, \\texttt{Sine}, \\texttt{Cosine}, \\texttt{Not}, \\texttt{Eq} \\} \\\\\n", "\\hline\n", "WellFormed(\\texttt{T(e1)}, S) \\\\\n", "\\end{array} \\text{(unary-op-rule)} $$\n", "\n", "The main rule is for let bindings\n", "\n", "$$\\begin{array}{c}\n", "WellFormed(\\texttt{e1}, S) \\;\\;\\; WellFormed(\\texttt{e2}, S \\cup \\{ x\\} ) \\\\\n", "\\hline\n", "WellFormed(\\texttt{Let(x, e1, e2)}, S) \\\\\n", "\\end{array} \\text{(let-rule)} $$\n", "\n", "Suppose `e1` is well formed under $S$ and `e2` is well formed under $S$ with the identifier `x` added,\n", "then `let x = e1 in e2` is well formed under $S$, as well. \n", "- This is confusing when you first see it, but repeat the sentence above and match it with the rule, \n", "- Notice that the defining expression must be well formed under the original S but the body expression is allowed to be well formed under $S \\cup \\{ x\\} $.\n", "- Once you actualy get it, you can appreciate how delightfully _simple_ it is!\n", "\n", "The rule for if-then-else is as follows:\n", "\n", "$$\\begin{array}{c}\n", "WellFormed(\\texttt{e1}, S) \\;\\;\\; WellFormed(\\texttt{e2}, S) \\;\\;\\; WellFormed(\\texttt{e3}, S) \\\\\n", "\\hline\n", "WellFormed(\\texttt{IfThenElse(e1, e2, e3)}, S ) \\\\\n", "\\end{array} \\; \\text{(ifthenelse-rule)} $$\n", "\n", "We can also add the rules for function definition:\n", "\n", "$$\\begin{array}{c}\n", "WellFormed(\\texttt{e}, S \\cup \\{x\\}) \\\\\n", "\\hline\n", "WellFormed(\\texttt{FunDef(x, e)}, S ) \\\\\n", "\\end{array} \\; \\text{(fundef-rule)} $$\n", "\n", "Finally, function calls are very simple:\n", "\n", "$$ \\begin{array}{c}\n", "WellFormed(\\texttt{e1}, S),\\;\\;\\; WellFormed(\\texttt{e2}, S) \\\\\n", "\\hline\n", "WellFormed(\\texttt{FunCall(e1,e2)}, S ) \\\\\n", "\\end{array} \\text{(well-formed-funcall)} $$\n", "\n", "Lets say that the name of the function is `f`. Then the above rule in combination with the `ident-rule` dictates that `f` should be defined in the scope $S$ and the argument should be well-formed. Then\n", "we can say that the function call is well-formed\n", "\n", "With these rules, we can bravely write our first static check for Lettuce to catch programs that declare variables before use.\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36misWellFormedExpression\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36misWellFormedProgram\u001b[39m" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def isWellFormedExpression(e: Expr, S: Set[String]): Boolean = e match {\n", " case Const(_) | True | False => true\n", " case Ident(x) => {\n", " if (S contains x) \n", " { true } \n", " else \n", " { println(s\"Error: undeclared identifier: $x\");\n", " false }\n", " }\n", " case Plus(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Minus(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Mult(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Div(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Geq(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Eq(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case And(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Or(e1, e2) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S)\n", " case Log(e) => isWellFormedExpression(e, S) \n", " case Exp(e) => isWellFormedExpression(e, S) \n", " case Sine(e) => isWellFormedExpression(e, S) \n", " case Cosine(e) => isWellFormedExpression(e, S) \n", " case Not(e) => isWellFormedExpression(e, S) \n", " \n", " case IfThenElse(e1, e2, e3) => isWellFormedExpression(e1, S) && isWellFormedExpression(e2, S) && isWellFormedExpression(e3, S)\n", " \n", " case Let(x, e1, e2) => isWellFormedExpression(e1, S) && { \n", " val S1 = S + x \n", " isWellFormedExpression(e2, S1)\n", " }\n", " \n", " case FunDef(x, e) => isWellFormedExpression(e, S+x)\n", " \n", " case FunCall(f, e) => isWellFormedExpression(f, S) && isWellFormedExpression(e, S)\n", "}\n", "\n", "\n", "\n", "def isWellFormedProgram(p: Program ) = p match {\n", " case TopLevel(e) => isWellFormedExpression(e, Set())\n", "}\n", "\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres10\u001b[39m: \u001b[32mBoolean\u001b[39m = true" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isWellFormedProgram(p1)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres11\u001b[39m: \u001b[32mBoolean\u001b[39m = true" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isWellFormedProgram(p2)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp3\u001b[39m: \u001b[32mLet\u001b[39m = \u001b[33mLet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mPlus\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"z\"\u001b[39m)), \u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p3 = Let(\"x\", Plus(Ident(\"y\"), Ident(\"z\")), Mult(Ident(\"x\"), Ident(\"y\"))) " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error: undeclared identifier: y\n" ] }, { "data": { "text/plain": [ "\u001b[36mres13\u001b[39m: \u001b[32mBoolean\u001b[39m = false" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isWellFormedProgram(TopLevel(p3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Q:__ Why does the above program just print one error message about \"y\" being \n", "undeclared, and not three error messages that complain about \"y\" twice and \"z\" once?\n", "\n", "\n", "\n", "Let's try the program\n", "\n", "~~~\n", "let x = x in x * y\n", "~~~" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp4\u001b[39m: \u001b[32mLet\u001b[39m = \u001b[33mLet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)))" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p4 = Let(\"x\", Ident(\"x\"), Mult(Ident(\"x\"), Ident(\"y\"))) " ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Error: undeclared identifier: x\n" ] }, { "data": { "text/plain": [ "\u001b[36mres15\u001b[39m: \u001b[32mBoolean\u001b[39m = false" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "isWellFormedProgram(TopLevel(p4))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Writing an Eval for Lettuce (Without Functions)\n", "\n", "Let us try to write an `eval` function for Lettuce. We can work with the existing `eval` function that we already defined for expressions, right?\n", "\n", "To avoid tackling too much in one swoop, let us ignore function definitions and function calls for now. \n", "\n", "We are going to write an `eval` function that takes in a program $\\texttt{e}$ and an environment $\\sigma$.\n", "$$eval(\\texttt{e}, \\sigma) = v $$ \n", "\n", "**Note**: $eval(\\texttt{e}, \\sigma) = v $ is also written as $\\sigma \\models \\texttt{e} \\Downarrow v$ in programming languages literature.\n", "\n", "- $\\sigma$ refers to an environment that maps names of identifiers to their values.\n", "- $\\text{domain}(\\sigma)$ refers to the domain of $\\sigma$.\n", "- $\\phi$ will refer to the empty environment in which no identifier is defined.\n", "- If $\\sigma$ is an environment, then $\\sigma[x \\mapsto v]$ is a new environment in which the identifier $x$ is mapped to the value $v$.\n", "\n", "\n", "What are the values we need to have: \n", "- Real values belonging to the set $\\mathbb{R}$ (or Double precision numbers in Scala).\n", "- Boolean values `true, false` belonging to the set $\\mathbb{B}$.\n", "- The special value `error` belonging to the set $\\mathbb{Err}$.\n", "\n", "The rules for arithmetic and conditional expressions are mostly the same as before.\n", "\n", "$$\\begin{array}{c}\n", "\\\\\n", "\\hline\n", "eval(\\texttt{Const(v)}, \\sigma) = v \\\\\n", "\\end{array} \\text{(const-rule)} $$\n", "\n", "$$\\begin{array}{c}\n", "x \\in \\text{domain}(\\sigma) \\\\\n", "\\hline\n", "eval(\\texttt{Ident(x)}, \\sigma) = \\sigma(\\texttt{x}) \\\\\n", "\\end{array} \\text{(ident-ok-rule)}\\ \\;\\;\\; \\begin{array}{c}\n", "x \\not\\in \\text{domain}(\\sigma) \\\\\n", "\\hline\n", "eval(\\texttt{Ident(x)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array} \\text{(ident-nok-rule)} $$\n", "\n", "\n", " Q: If we checked that the expression is well-formed, then will we need (ident-nok-rule)?\n", "\n", "Rules for `Plus, Minus, Mult`. \n", "\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e1}, \\sigma) = v_1,\\; \\; eval(\\texttt{e2}, \\sigma) = v_2,\\ \\ v_1 \\in \\mathbb{R},\\ \\ v_2 \\in \\mathbb{R}, \\; \\; \\texttt{T} \\in \\{ \\texttt{Plus, Minus, Mult} \\} \\\\\n", "\\hline\n", "eval(\\texttt{T(e1, e2)}, \\sigma) = f_T(v_1, v_2) \\\\\n", "\\end{array} \\text{(arith-binop-ok-rule)}$$\n", "\n", "Note that the rule refers to $f_T$ for the operator $T$. \n", "Define these as $f_{Plus}(x,y) = x + y$, $f_{Mult} = x * y$ and $f_{Minus} (x, y) = x - y$.\n", "\n", "The `Div` operator needs special handling in exactly the same way we showed in our previous lectures.\n", " Write down the rules for `Div` as an exercise \n", "\n", "\n", "We can now handle the case when subexpressions of arithmetic expressions yield a non real value (these can be Booleans or even error).\n", "\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e1}, \\sigma) = v_1,\\; \\ v_1 \\not\\in \\mathbb{R},\\ ; \\; \\texttt{T} \\in \\{ \\texttt{Plus, Minus, Mult, Div} \\} \\\\\n", "\\hline\n", "eval(\\texttt{T(e1, e2)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array} \\text{(arith-binop-type-mismatch-rule-1)}\n", "$$\n", "$$\n", "\\begin{array}{c}\n", "eval(\\texttt{e1}, \\sigma) = v_1,\\; eval(\\texttt{e2}, \\sigma) = v_2,\\; \\ v_1 \\in \\mathbb{R},\\; \\; v_2 \\not\\in \\mathbb{R},\\ ; \\; \\texttt{T} \\in \\{ \\texttt{Plus, Minus, Mult, Div} \\} \\\\\n", "\\hline\n", "eval(\\texttt{T(e1, e2)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array} \\text{(arith-binop-type-mismatch-rule-2)}\n", "$$\n", "\n", "Unary arithmetic operators are also handled in the same way as in the previous lectures.\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e}, \\sigma) = v,\\;\\; v \\in \\mathbb{R} \\; \\; \\texttt{T} \\in \\{ \\texttt{Exp, Sine, Cosine} \\} \\\\\n", "\\hline\n", "eval(\\texttt{T(e)}, \\sigma) = f_T(v) \\\\\n", "\\end{array} \\text{(arith-unop-ok-rule)}$$\n", "\n", "Wherein $f_{Exp}(x) = e^x,\\ f_{Sine}(x) = \\sin(x), f_{Cosine}(x) = \\cos(x)$.\n", "Log needs special rule to deal with argument being positive vs. non-positive.\n", "\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e}, \\sigma) = v,\\;\\; v \\in \\mathbb{R},\\ v > 0 \\\\\n", "\\hline\n", "eval(\\texttt{Log(e)}, \\sigma) = \\log(v) \\\\\n", "\\end{array} \\text{(log-ok-rule)}\\;\\;\\;\n", "\\begin{array}{c}\n", "eval(\\texttt{e}, \\sigma) = v,\\;\\; v \\in \\mathbb{R},\\ v \\leq 0 \\\\\n", "\\hline\n", "eval(\\texttt{Log(e)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array} \\text{(log-nok-rule)}$$\n", "\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e}, \\sigma) = v,\\; \\ v \\not\\in \\mathbb{R},\\ ; \\; \\texttt{T} \\in \\{ \\texttt{Log, Sine, Cosine, Exp} \\} \\\\\n", "\\hline\n", "eval(\\texttt{T(e)}, \\sigma) = \\mathbf{error} \\\\\n", "\\end{array} \\text{(arith-unop-type-mismatch-rule)}$$\n", "\n", "#### Rules for Boolean Operators\n", "\n", "$$\\begin{array}{c} \n", "\\\\\n", "\\hline\n", "eval(\\texttt{True}, \\sigma) = true \\\\\n", "\\end{array} \\text{(true rule)} \\;\\;\\;\\;\n", "\\begin{array}{c} \n", "\\\\\n", "\\hline\n", "eval(\\texttt{False}, \\sigma) = false \\\\\n", "\\end{array}\\text{(false rule)}\n", "$$\n", "\n", "`And` and `Or` can be short circuited. We will write the rules for `And` and note that\n", "the rules of `Or` and `Not` are similar.\n", "\n", "$$\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = false\\\\\n", "\\hline\n", "eval(\\texttt{And}(e1, e2), \\sigma) = false\\\\\n", "\\end{array} \\text{(and-arg-1-ok-rule)} \\;\\;\\;\\;\n", "\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = v_1,\\ v_1 \\not\\in \\mathbb{B} \\\\\n", "\\hline\n", "eval(\\texttt{And}(e1, e2), \\sigma) = \\mathbf{error}\\\\\n", "\\end{array}\\text{(and-arg-1-nok-rule)}\n", "$$\n", "\n", "$$\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = true\\;\\; eval(\\texttt{e2}, \\sigma) = v_2,\\ \\;\\; v_2 \\in \\mathbb{B}\\\\\n", "\\hline\n", "eval(\\texttt{And}(e1, e2), \\sigma) = v_2\\\\\n", "\\end{array} \\text{(and-arg-2-ok-rule)} \\;\\;\\;\\;\n", "\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = true,\\ eval(\\texttt{e2}, \\sigma) = v_2,\\ \\;\\; v_2 \\not\\in \\mathbb{B} \\\\\n", "\\hline\n", "eval(\\texttt{And}(e1, e2), \\sigma) = \\mathbf{error}\\\\\n", "\\end{array}\\text{(and-arg-2-nok-rule)}\n", "$$\n", "\n", " As an exercise write rules for `Geq, Eq` . They are going to be very similar to those written thus far but without short circuit semantics for regular case and with short circuit for errors.\n", "\n", "#### Rule for Let Binding\n", "\n", "$$\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = v_1,\\ v_1 \\not= \\mathbf{error}\\;\\; eval(\\texttt{e2}, \\color{red}{\\sigma[x \\mapsto v_1]}) = v_2,\\ \\;\\; v_2 \\not= \\mathbf{error}\\\\\n", "\\hline\n", "eval(\\texttt{Let(x,e1, e2)}, \\sigma) = v_2\\\\\n", "\\end{array} \\text{(let-binding-ok)} $$\n", "\n", "The most important part of the rule above is notice that $\\texttt{e2}$ is being evaluated under\n", "$\\color{red}{\\sigma[ x \\mapsto v_1]}$, which is the environment $\\sigma$ extended with $x$ bound to $v_1$.\n", "\n", "$$\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = \\mathbf{error}\\\\\n", "\\hline\n", "eval(\\texttt{Let(x,e1, e2)}, \\sigma) = \\mathbf{error}\\\\\n", "\\end{array} \\text{(let-binding-nok-1)}\n", "\\begin{array}{c} \n", "eval(\\texttt{e1}, \\sigma) = v_1,\\; v_1 \\not= \\mathbf{error}\\; eval(\\texttt{e2}, \\sigma[x \\mapsto v_1]) = \\mathbf{error}\\\\\n", "\\hline\n", "eval(\\texttt{Let(x,e1, e2)}, \\sigma) = \\mathbf{error}\\\\\n", "\\end{array} \\text{(let-binding-nok-2)}$$\n", "\n", "\n", "Given these rules, the final rule is for `TopLevel`. We recall that $\\phi$ denotes the empty environment.\n", "\n", "$$\\begin{array}{c}\n", "eval(\\texttt{e}, \\phi) = v \\\\\n", "\\hline\n", "eval(\\texttt{TopLevel(e)}, \\phi) = v \\\\\n", "\\end{array} \\text{(toplevel-eval)} $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Implementing the Interpreter \n", "\n", "First let us implement what we will need as part of the value class." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mValue\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mNumValue\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mBoolValue\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mErrorValue\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mvalueToNumber\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mvalueToBoolean\u001b[39m" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "/* 1. Define the values */\n", "sealed trait Value \n", "case class NumValue(d: Double) extends Value\n", "case class BoolValue(b: Boolean) extends Value\n", "case object ErrorValue extends Value\n", "\n", "/*2. Operators on values */\n", "\n", "def valueToNumber(v: Value): Double = v match {\n", " case NumValue(d) => d\n", " case _ => throw new IllegalArgumentException(s\"Error: Asking me to convert Value: $v to a number\")\n", "}\n", "\n", "def valueToBoolean(v: Value): Boolean = v match {\n", " case BoolValue(b) => b\n", " case _ => throw new IllegalArgumentException(s\"Error: Asking me to convert Value: $v to a boolean\")\n", "}\n" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mevalProgram\u001b[39m" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def evalExpr(e: Expr, env: Map[String, Value]): Value = {\n", " \n", " /* Method to deal with binary arithmetic operations */\n", " \n", " def applyArith2 (e1: Expr, e2: Expr) (fun: (Double , Double) => Double) = {\n", " val v1 = valueToNumber(evalExpr(e1, env))\n", " val v2 = valueToNumber(evalExpr(e2, env))\n", " val v3 = fun(v1, v2)\n", " NumValue(v3)\n", " } /* -- We have deliberately curried the method --*/\n", " \n", " /* Helper method to deal with unary arithmetic */\n", " def applyArith1(e: Expr) (fun: Double => Double) = {\n", " val v = valueToNumber(evalExpr(e, env))\n", " val v1 = fun(v)\n", " NumValue(v1)\n", " }\n", " \n", " /* Helper method to deal with comparison operators */\n", " def applyComp(e1: Expr, e2: Expr) (fun: (Double, Double) => Boolean) = {\n", " val v1 = valueToNumber(evalExpr(e1, env))\n", " val v2 = valueToNumber(evalExpr(e2, env))\n", " val v3 = fun(v1, v2)\n", " BoolValue(v3)\n", " }\n", " \n", " \n", " e match {\n", " case Const(f) => NumValue(f)\n", " \n", " case Ident(x) => {\n", " if (env contains x) \n", " env(x)\n", " else \n", " throw new IllegalArgumentException(s\"Undefined identifier $x\")\n", " }\n", " \n", " case True => BoolValue(true)\n", " \n", " case False => BoolValue(false)\n", " \n", " case Plus(e1, e2) => applyArith2 (e1, e2) ( _ + _ )\n", " \n", " case Minus(e1, e2) => applyArith2(e1, e2) ( _ - _ )\n", " \n", " case Mult(e1, e2) => applyArith2(e1, e2) (_ * _)\n", " \n", " case Div(e1, e2) => applyArith2(e1, e2) {\n", " case (_, 0.0) => throw new IllegalArgumentException(s\"Divide by zero error in divisor ${e2}\")\n", " case (v1, v2) => v1/v2\n", " }\n", " \n", " case Log(e1) => applyArith1(e1) {\n", " case v if v > 0.0 => math.log(v)\n", " case v => throw new IllegalArgumentException(s\"Log of a negative number ${e} evaluates to ${v}!\")\n", " }\n", " \n", " case Exp(e1) => applyArith1(e1)(math.exp)\n", " \n", " case Sine(e1) => applyArith1(e1)(math.sin)\n", " \n", " case Cosine(e1) => applyArith1(e1)(math.cos)\n", " \n", " case Geq(e1, e2) => applyComp(e1, e2)(_ >= _)\n", " \n", " case Eq(e1, e2) => applyComp(e1, e2)(_ == _)\n", " \n", " case And(e1, e2) => { /* Short circuit eval of And */\n", " val v1 = evalExpr(e1, env)\n", " v1 match {\n", " case BoolValue(false) => BoolValue(false)\n", " case BoolValue(true) => {\n", " val v2 = evalExpr(e2, env)\n", " v2 match {\n", " case BoolValue(_) => v2\n", " case _ => throw new IllegalArgumentException(\n", " s\"And of a boolean and non-boolean expr: ${e2} which evaluated to ${v2}\") \n", " }\n", " }\n", " case _ => throw new IllegalArgumentException(s\"And of a non-boolean expr: ${e1} which evaluted to ${v1}\")\n", " }\n", " }\n", " \n", " case Or(e1, e2) => { /* Short circuit eval of OR*/\n", " val v1 = evalExpr(e1, env)\n", " v1 match {\n", " case BoolValue(true) => BoolValue(true)\n", " case BoolValue(false) => {\n", " val v2 = evalExpr(e2, env)\n", " v2 match {\n", " case BoolValue(_) => v2\n", " case _ => throw new IllegalArgumentException(\n", " s\"Or of a boolean and non-boolean expr: ${e2} which evaluated to ${v2}\") \n", " }\n", " }\n", " case _ => throw new IllegalArgumentException(s\"Or of a non-boolean expr: ${e1} which evaluted to ${v1}\")\n", " }\n", " }\n", " \n", " case Not(e1) => {\n", " val v = evalExpr(e1, env)\n", " v match {\n", " case BoolValue(b) => BoolValue(!b)\n", " case _ => throw new IllegalArgumentException(s\"Not of a non-boolean expr: ${e} which evaluated to ${v}\")\n", " }\n", " }\n", " \n", " case IfThenElse(e1, e2, e3) => {\n", " val v = evalExpr(e1, env)\n", " v match {\n", " case BoolValue(true) => evalExpr(e2, env)\n", " case BoolValue(false) => evalExpr(e3, env)\n", " case _ => throw new IllegalArgumentException(s\"If-then-else condition expr: ${e1} is non-boolean -- evaluates to ${v}\")\n", " }\n", " }\n", " \n", " case Let(x, e1, e2) => {\n", " val v1 = evalExpr(e1, env) // eval e1\n", " val env2 = env + (x -> v1) // create a new extended env\n", " evalExpr(e2, env2) // eval e2 under that.\n", " }\n", " \n", " case _:FunDef => throw new IllegalArgumentException(\"Function definitions not yet handled in this interpreter.\")\n", " \n", " case _:FunCall => throw new IllegalArgumentException(\"Function calls not yet handled in this interpreter.\")\n", " }\n", "}\n", "\n", "def evalProgram(p: Program) = {\n", " val m: Map[String, Value] = Map[String,Value]()\n", " p match { \n", " case TopLevel(e) => {\n", " try {\n", " evalExpr(e, m)\n", " } catch {\n", " case e: IllegalArgumentException => {\n", " println(s\"Error: $e\")\n", " ErrorValue\n", " }\n", " }\n", " }\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "TopLevel(Let(x,Plus(Const(10.0),Const(15.0)),Let(y,Geq(Ident(x),Const(25.0)),IfThenElse(Ident(y),Ident(x),Minus(Ident(x),Const(35.0))))))" ] }, { "data": { "text/plain": [ "\u001b[36mres18_1\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mNumValue\u001b[39m(\u001b[32m25.0\u001b[39m)" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print(p1)\n", "evalProgram(p1)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Let(x,Ident(x),Mult(Ident(x),Ident(y)))Error: java.lang.IllegalArgumentException: Undefined identifier x\n" ] }, { "data": { "text/plain": [ "\u001b[36mres19_1\u001b[39m: \u001b[32mValue\u001b[39m = ErrorValue" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "print(p4)\n", "evalProgram(TopLevel(p4))" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp5\u001b[39m: \u001b[32mTopLevel\u001b[39m = \u001b[33mTopLevel\u001b[39m(\u001b[33mLet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mConst\u001b[39m(\u001b[32m3.0\u001b[39m), \u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m))))" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p5 = TopLevel(Let(\"x\", Const(3.0), Mult(Ident(\"x\"), Ident(\"x\"))))" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres21\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mNumValue\u001b[39m(\u001b[32m9.0\u001b[39m)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "evalProgram(p5)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mp6\u001b[39m: \u001b[32mTopLevel\u001b[39m = \u001b[33mTopLevel\u001b[39m(\n", " \u001b[33mLet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[33mConst\u001b[39m(\u001b[32m3.0\u001b[39m), \u001b[33mGeq\u001b[39m(\u001b[33mMult\u001b[39m(\u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)), \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)))\n", ")" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val p6 = TopLevel(Let(\"x\", Const(3.0), Geq(Mult(Ident(\"x\"), Ident(\"x\")), Ident(\"x\"))))" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres23\u001b[39m: \u001b[32mValue\u001b[39m = \u001b[33mBoolValue\u001b[39m(true)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "evalProgram(p6)" ] } ], "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 }