{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lecture 4: Inductive Definitions and Inductively Defined Structures\n", "\n", "Originally by Sriram Sankaranarayanan \n", "\n", "Modified by Ravi Mangal \n", "\n", "Last Modified: Feb 5, 2025." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this lecture, we will study inductive definitions: a very important form that can be used to define a lot of _rich_ structures. In turn, we can use inductive definitions to design and implement programming languages. \n", "\n", "We will use inductive definitions for a variety of purposes starting from \n", "defining *numbers*, *lists*, *trees*, *expressions*, *syntax trees*, and \n", "so on. Learning how to define these and implement various important \n", "operations on them will be at the absolute core of this class.\n", "\n", "\n", "## Natural Numbers\n", "\n", "The set of natural numbers $\\mathbb{N} = \\{ 0, 1, 2, \\ldots, \\}$ has an inductive definition that we will state in three different ways.\n", "\n", "### Inductive Definition in English\n", "\n", "Natural numbers are defined inductively using the following rules:\n", "\n", " - **R0:** The symbol $\\text{Z}$ is a natural number (side note: it stands for the number *zero*)\n", " - **R1:** If $s$ is a natural number then $\\text{succ}(s)$ is a natural number (side note: *succ* stands for the act of adding one to a number giving us its *succ*essor).\n", " - **R2:** Nothing else is a natural number.\n", " \n", "This definition provides us a handle to generate the set of natural numbers $\\mathbb{N}$ in \n", "countably-many stages.\n", "\n", "Rule **R0** tells us that $N_0 = \\{ Z \\}$. \n", "\n", "Now we can apply the rule **R1** to derive more natural numbers.\n", "\n", "$\\begin{array}{rl}\n", "N_0: & \\{ Z \\} \\\\\n", "N_1: & \\{ Z, \\text{succ}(Z) \\}\\\\\n", "N_2: & \\{Z, \\text{succ}(Z), \\text{succ}(\\text{succ}(Z)) \\} \\\\\n", "N_3: & \\{Z, \\text{succ}(Z), \\text{succ}(\\text{succ}(Z)), \\text{succ}^{3}(Z) \\} \\\\\n", "\\vdots & \\\\\n", "N_k: & \\{ Z, \\text{succ}(Z), \\text{succ}(\\text{succ}(Z)), \\cdots, \\text{succ}^{k}(Z) \\} \\\\\n", "\\vdots & \n", "\\end{array}$\n", "\n", "Here $\\text{succ}^k(Z)$ is simply the application of $\\text{succ}$ $k$-times to the symbol $Z$. \n", "\n", "The strings Z, succ(Z), succ(succ(Z)), succ(succ(succ(Z))) are called __terms__.\n", "\n", "\n", "If we iterate this process forever, _in the limit_ we obtain the set $\\mathbb{N}$ defined as \n", "\n", "$$ \\mathbb{N} = N_0 \\cup N_1 \\cup N_2 \\cup N_3 \\cup \\cdots \\cup N_{j} \\cup \\cdots = \\bigcup_{j=0}^{\\infty} N_j \\,.$$\n", "\n", "\n", "\n", "This looks nothing like the natural numbers $0,1, 2,3, \\ldots$ that we learned in grade school (and appreciated dearly ever since!). Nevertheless, we can identify every number $k$ with the term $\\text{succ}^{k}(Z)$.\n", "\n", "### Inductive Definition as a Generative Grammars\n", "\n", "The English definition will soon be cumbersome to write down. Therefore, we define a _generative grammar_ that\n", "generates the same definition as a convenient mathematical shorthand. The grammar is as follows. \n", "\n", " $$\\begin{array}{ccc}\n", " \\textbf{Number} & \\rightarrow & \\text{Z}\\\\\n", " \\textbf{Number} & \\rightarrow& succ(\\textbf{Number}) \\\\ \n", " \\end{array}$$ \n", "\n", "Let us help you make sense of a grammar by giving names to every part.\n", " - Nonterminal: The symbol __Number__ is a non terminal for the grammar. \n", " - Terminals: The symbols *Z, succ* are called terminals for the grammar. \n", " - Rules: There are two rules in the grammar: __Number__ -> Z and __Number__ -> succ(__Number__). If we translate them into plain English, what do we get:\n", " - **R0** The term consisting of just the symbol Z is a __Number__.\n", " - **R1** If the term t is a __Number__ then succ(t) is also a __Number__.\n", " - Starting Symbol (Nonterminal): We designate one of the nonterminals of the grammar as starting. Here there is just one such non terminal __Number__ and therefore it is the starting symbol.\n", " \n", " \n", "__Definition (Generative Grammar)__ \n", "A generative grammar is defined by three components: (1) A set of nonterminals, (2) A set of terminals, and (C) A set of rules.\n", "\n", "Each rule has the form: \n", "\n", "__NonTerminalSymbol__ -> _(a term involving terminal and non terminal symbols)_\n", "\n", "Instead of writing out each rule, we collect rules with a common left hand side and use the OR symbol `|` to separate them. For example, we can write the very same grammar for natural numbers as:\n", "\n", "$$\\begin{array}{ccccc}\n", "\\textbf{Number} & \\rightarrow & {Z} &\\ |\\ & succ(\\textbf{Number}) \\\\\n", "\\end{array}$$\n", "\n", "\n", "#### Derivations\n", "\n", "\n", "Every term generated by the grammar is derived from the starting symbol by the application of grammar rules. Here are some examples of derivations: \n", "\n", " - succ(Z) \n", " - __Number__ -> succ(__Number__) -> succ(Z)\n", " - succ(succ(succ(Z)))\n", " - __Number__ -> succ(__Number__) -> succ(succ(__Number__)) -> succ(succ(succ(__Number__))) -> succ(succ(succ(Z)))\n", "\n", "### Inductive Definition in Scala\n", "\n", "Scala (and indeed many other languages) have a way for us to provide inductive definitions. We do so in Scala using the class inheritence mechanism as follows." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mNumber\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mZ\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mSucc\u001b[39m" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait Number \n", "// sealed tells Scala that everything else that inherits from \n", "// the trait \"Number\" will need to be in the same file. Thus, classes defined in a \n", "// different file cannot extend Number.\n", "//\n", "// A trait in Scala is like an abstract class: you cannot \n", "// create an instance of it but you are welcome to write \n", "// classes that inherit from it.\n", "\n", "case class Z() extends Number \n", "// The symbol Z is a class that extends number. \n", "// This models the grammar rule Number-> Z\n", "// We write case class instead of just class. \n", "// This is again a convenient practice. \n", "// case classes come with a predefined \"equals\" method.\n", "// Additionally, \"toString\" method and \"hashCode\" method are also predefined.\n", "// That way we do not have to write these ourselves.\n", "// Constructing an object of a case class does not require the new keyword\n", "\n", "case class Succ(n : Number) extends Number \n", "// This models the production rule Number -> Succ(Number)\n", "// Succ should be capitalized because it is a Scala convention that all class names are capitalized\n", "// Note the argument n: Number." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mzero\u001b[39m: \u001b[32mZ\u001b[39m = Z()" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val zero = Z()" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mfive\u001b[39m: \u001b[32mSucc\u001b[39m = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = Z())))))" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val five = Succ(Succ(Succ(Succ(Succ(zero)))))" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mten\u001b[39m: \u001b[32mSucc\u001b[39m = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = Z()))))))\n", " )\n", " )\n", " )\n", ")" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val ten = Succ(Succ(Succ(Succ(Succ(five)))))" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36meleven\u001b[39m: \u001b[32mSucc\u001b[39m = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = \u001b[33mSucc\u001b[39m(n = Z()))))))\n", " )\n", " )\n", " )\n", " )\n", ")" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val eleven = Succ(ten)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36meqtest1\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val eqtest1 = Succ(ten) == eleven // This is why case classes are cool. \n", " // The == operator is predefined for us." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36meqtest2\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val eqtest2 = Succ(Succ(Succ(five))) == eleven" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(Five = ,Succ(Succ(Succ(Succ(Succ(Z()))))))" ] } ], "source": [ "print(\"Five = \", five)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us write a function that randomly generates terms of type **Number**" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mgenNumber\u001b[39m" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def genNumber(rand: scala.util.Random): Number = {\n", " val randInt = rand.nextInt(100)\n", " if (randInt < 10) {\n", " return Z()\n", " }\n", " return Succ(genNumber(rand))\n", "}" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mrand\u001b[39m: \u001b[32mscala\u001b[39m.\u001b[32mutil\u001b[39m.\u001b[32mRandom\u001b[39m = scala.util.Random@6f1e93b0" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val rand = new scala.util.Random()" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mres34\u001b[39m: \u001b[32mNumber\u001b[39m = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = \u001b[33mSucc\u001b[39m(\n", " n = Z()\n", " )\n", " )\n", "..." ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "genNumber(rand)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## List of Numbers\n", "\n", "We can now extend our inductive definition to define lists of numbers. We will directly write down a grammar for it.\n", "\n", "$$\\begin{array}{ccccc}\n", "\\textbf{NumList} & \\rightarrow & Nil &\\ |\\ & Cons(\\textbf{Num}, \\textbf{NumList}) \\\\\n", "\\textbf{Num} & \\rightarrow & 0 \\ |\\ 1\\ |\\ 2\\ |\\ 3\\ |\\ 4\\ |\\ \\cdots \\\\\n", "\\end{array}$$\n", "\n", "The grammar has two non terminals __NumList__ and __Num__. We are only interested in terms that are produced starting from __NumList__. There are two important terminals *Nil, Cons* that stand for the empty list and the appending of a number to the front of a list. Then there are infinitely many non terminals that are just natural numbers $0, 1, 2, \\ldots$. These represent the elements that we can add to the list. Note that there are infinitely many rules which express that __Num__ can be any natural number. But the interesting rules for us include __NumList__ -> *Nil* and\n", "__NumList__ -> *Cons*(__Num__, __NumList__). \n", "\n", "Let us generate examples of valid lists from this rule.\n", "\n", "The simplest list we can generate is the empty list _Nil_. However, applying the rules, we can generate other lists\n", "such as\n", "\n", " - *Cons(3, Nil)*. \n", " - **NumList** -> *Cons*(**Num**, **NumList**) -> *Cons*(3, **NumList**) -> *Cons*(3, *Nil*)\n", " - *Cons(3, Cons(7, Nil))*\n", " - **NumList** -> *Cons*(**Num**, **NumList**) -> *Cons*(3, **NumList**) -> *Cons*(3, *Cons*(**Num**, **NumList**)) -> *Cons*(3, *Cons*(7, **NumList**)) -> *Cons(3, Cons(7, Nil))*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Practice Exercises:\n", " - Can you find out how to generate *Cons(4, Cons(4, Cons(4, Nil)))* ?\n", " - Write down the term that corresponds to the Scala list: `List(1, 2, 3, 4)`.\n", " - What is the Scala list corresponding to *Cons(3, Cons(7, Nil))*?" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mNumList\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mNil\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mCons\u001b[39m" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait NumList \n", "// We defined a trait for NumList -- The symbol that generates the list \n", "\n", "case object Nil extends NumList \n", "// We made a subtle change from \"class\" to \"object\"\n", "// In Scala a \"class\" defines a type that we can generate new instances of.\n", "// object simply tells scala that there is exactly one instance of Nil\n", "// that we will ever need to create.\n", "// As a benefit, I do not have to write () \n", "// after the Nil (name of object) now :-)\n", "\n", "case class Cons(hd: Int, tl: NumList) extends NumList \n", "// This tells us that Cons applies to a native Scala \n", "// integer (I deviated from the definition in the grammar in this regard)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mempList\u001b[39m: \u001b[32mNil\u001b[39m.type = Nil\n", "\u001b[36ml1\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(hd = \u001b[32m3\u001b[39m, tl = Nil)\n", "\u001b[36ml2\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(hd = \u001b[32m3\u001b[39m, tl = \u001b[33mCons\u001b[39m(hd = \u001b[32m7\u001b[39m, tl = Nil))\n", "\u001b[36ml3\u001b[39m: \u001b[32mCons\u001b[39m = \u001b[33mCons\u001b[39m(hd = \u001b[32m7\u001b[39m, tl = \u001b[33mCons\u001b[39m(hd = \u001b[32m3\u001b[39m, tl = Nil))\n", "\u001b[36meq1\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m\n", "\u001b[36meq2\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val empList = Nil\n", "val l1 = Cons(3, Nil)\n", "val l2 = Cons(3, Cons(7, Nil))\n", "val l3 = Cons(7, l1)\n", "val eq1 = (l2 == l1)\n", "val eq2 = (l2 == l3)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "list l1 is Cons(3,Nil)\n", "list l2 is Cons(3,Cons(7,Nil))\n", "list l3 is Cons(7,Cons(3,Nil))\n" ] } ], "source": [ "println(s\"list l1 is $l1\")\n", "println(s\"list l2 is $l2\")\n", "println(s\"list l3 is $l3\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us write a function that randomly generates terms of type **NumList**" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mgenNum\u001b[39m\n", "defined \u001b[32mfunction\u001b[39m \u001b[36mgenNumList\u001b[39m" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def genNum(rand: scala.util.Random): Int = {\n", " val randInt = rand.nextInt()\n", " if (randInt >= 0) {\n", " return randInt\n", " } else {\n", " return genNum(rand)\n", " }\n", "}\n", "\n", "def genNumList(rand: scala.util.Random): NumList = {\n", " val randInt = rand.nextInt(100)\n", " if (randInt < 25) {\n", " return Nil\n", " }\n", " return Cons(genNum(rand),genNumList(rand))\n", "}" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cons(1357292515,Cons(284469111,Cons(2024295345,Cons(582638565,Cons(1073987414,Cons(179912475,Cons(209175924,Cons(283232174,Cons(2015310476,Cons(1901331717,Cons(2129319759,Cons(300187615,Cons(2116615329,Cons(1006702655,Cons(827546627,Cons(1336002258,Cons(973035345,Cons(449741254,Cons(1953434674,Cons(1530258264,Nil))))))))))))))))))))\n" ] } ], "source": [ "println(genNumList(rand))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Side Note: Terms as Trees\n", "\n", "We will now introduce the concept of visualizing terms as trees to make it easy to see what is happening.\n", "\n", "Consider a term *Cons(3, Cons( 7, Cons( 17, Nil) ) )*.\n", "Such a term can be viewed as a tree:\n", "\n", "\"Term" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Alternative Grammar for Lists of Numbers\n", "\n", "We can connect the grammar for __NumList__ with the grammar for __Numbers__ we wrote previously as follows:\n", "\n", "\n", "$$\\begin{array}{ccccc}\n", "\\textbf{NumList} & \\rightarrow & Nil &\\ |\\ & Cons(\\textbf{Num}, \\textbf{NumList}) \\\\\n", "\\textbf{Num} & \\rightarrow & Z & | & succ(\\textbf{Num}) \\\\\n", "\\end{array}$$\n", "\n", "Of course, this produces lists such as\n", " - *Nil*, *Cons(succ(Z), Nil)*, *Cons(succ(succ(succ(Z))), Cons( succ(succ(succ(succ(Z)))), Nil))* instead of\n", " - *Nil*, *Cons(1, Nil)*, *Cons(3, Cons(4, Nil))*\n", " \n", " \n", "The grammar with _infinitely many_ terminals turns out to be more human readable! But mathematically, we say they are the same up to a _bijection_.\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Binary Tree of Numbers\n", "\n", "~~~\n", "I think that I shall never see,\n", "A poem lovely as a tree.\n", "\n", " - Joyce Kilmer (Trees, 1913).\n", "~~~\n", "\n", "Trees are a very important inductively defined structure. We will write a grammar to define a simple binary tree of numbers as follows:\n", "\n", "$$\\begin{array}{rclclcl}\n", "\\textbf{NumTree} & \\rightarrow & Leaf & \\ |\\ & Node(\\textbf{Num}, \\textbf{NumTree}, \\textbf{NumTree}) \\\\\n", "\\textbf{Num} & \\rightarrow & 0 \\ |\\ 1\\ |\\ 2\\ | \\ 3 \\ |\\ \\cdots \\\\\n", "\\end{array}$$\n", "\n", "The simplest tree is denoted by the terminal _Leaf_\n", "\n", "A tree can then be constructed as a node denoted by the terminal *Node*, which has a number **Num** associated with it and two subtrees that form the arguments.\n", "\n", "Let us now see some examples of trees pictorially and the associated terms in the grammar.\n", "\n", "\n", "#### Node(5, Leaf, Leaf)\n", "\"Tree \n", "\n", "#### Node(4, Node(8, Leaf, Leaf), Leaf)\n", "\n", "\"Tree \n", "\n", "#### Node(4, Node(8, Leaf, Leaf), Node(9, Leaf, Node(4, Leaf, Leaf)))\n", "\n", "\"Tree \n" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mNumTree\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mLeaf\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait NumTree\n", "case object Leaf extends NumTree\n", "case class Node(n: Int, left: NumTree, right: NumTree) extends NumTree" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36mt1\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(n = \u001b[32m5\u001b[39m, left = Leaf, right = Leaf)\n", "\u001b[36mt2\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(\n", " n = \u001b[32m4\u001b[39m,\n", " left = \u001b[33mNode\u001b[39m(n = \u001b[32m8\u001b[39m, left = Leaf, right = Leaf),\n", " right = Leaf\n", ")\n", "\u001b[36mt3\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(\n", " n = \u001b[32m4\u001b[39m,\n", " left = \u001b[33mNode\u001b[39m(n = \u001b[32m8\u001b[39m, left = Leaf, right = Leaf),\n", " right = \u001b[33mNode\u001b[39m(\n", " n = \u001b[32m9\u001b[39m,\n", " left = Leaf,\n", " right = \u001b[33mNode\u001b[39m(n = \u001b[32m4\u001b[39m, left = Leaf, right = Leaf)\n", " )\n", ")" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val t1 = Node(5, Leaf, Leaf)\n", "val t2 = Node(4, Node(8, Leaf, Leaf), Leaf)\n", "val t3 = Node(4, Node(8, Leaf, Leaf), Node(9, Leaf, Node(4, Leaf, Leaf)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us write a function that randomly generates terms of type **NumTree**" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mfunction\u001b[39m \u001b[36mgenNumTree\u001b[39m" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def genNumTree(rand: scala.util.Random): NumTree = {\n", " val randInt = rand.nextInt(100)\n", " if (randInt < 50) {\n", " return Leaf\n", " }\n", " return Node(genNum(rand),genNumTree(rand),genNumTree(rand))\n", "}" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Node(1917176086,Node(1445628765,Leaf,Node(746255514,Node(1753547497,Node(1123055995,Node(38291853,Node(1249593927,Node(1076567107,Node(473869990,Leaf,Leaf),Node(1070476264,Node(2140548796,Leaf,Node(2141758311,Leaf,Leaf)),Node(699981950,Node(1375530514,Node(115490075,Leaf,Leaf),Node(2037239017,Node(186076290,Node(986229231,Leaf,Node(1347351441,Leaf,Node(79630349,Leaf,Leaf))),Leaf),Node(1377640766,Node(516642747,Node(1451171448,Leaf,Leaf),Node(1090734611,Leaf,Leaf)),Node(1926672771,Node(234810607,Leaf,Node(1087959537,Node(2018653150,Leaf,Node(739166449,Leaf,Node(951693520,Node(1912022816,Node(277202794,Node(345561249,Node(1614557468,Leaf,Node(1545247902,Leaf,Leaf)),Node(2113943981,Node(2044381015,Node(1176477303,Node(430573642,Node(1407640556,Node(1195243710,Node(1604078759,Leaf,Node(1062437941,Node(1999559147,Leaf,Node(1835963147,Leaf,Leaf)),Node(1140449105,Leaf,Leaf))),Leaf),Leaf),Leaf),Leaf),Node(553891083,Leaf,Node(338036822,Node(618363816,Node(747357350,Leaf,Node(2015727801,Leaf,Leaf)),Leaf),Node(2141325245,Leaf,Node(1804435286,Node(43908157,Node(10862979,Leaf,Node(1523864155,Leaf,Leaf)),Leaf),Node(1854677573,Leaf,Leaf)))))),Node(1064945468,Leaf,Leaf))),Node(1097112528,Leaf,Leaf)),Node(93823506,Node(1448849624,Leaf,Node(1628808117,Node(1041392086,Leaf,Leaf),Node(274775066,Leaf,Leaf))),Node(453319489,Node(748474249,Leaf,Node(1991706148,Leaf,Node(962876896,Leaf,Leaf))),Node(1957357931,Leaf,Leaf)))),Leaf))),Node(50337427,Node(1358418799,Node(1996809816,Leaf,Leaf),Node(39305336,Leaf,Node(529960195,Leaf,Node(68345161,Node(1241040339,Leaf,Node(1947704898,Node(888449018,Leaf,Node(1208223852,Node(1298166899,Leaf,Leaf),Node(1796227388,Leaf,Node(1737206201,Node(9748065,Node(1244314977,Leaf,Leaf),Node(906218609,Node(642518315,Node(699388441,Leaf,Leaf),Node(432075003,Leaf,Leaf)),Node(1567707479,Node(1707666440,Node(1537991081,Leaf,Node(1930840432,Leaf,Node(2139589392,Leaf,Leaf))),Leaf),Node(960011675,Leaf,Leaf)))),Leaf)))),Leaf)),Node(661880194,Node(1995410026,Leaf,Leaf),Node(1289243403,Leaf,Leaf)))))),Node(694326297,Leaf,Leaf)))),Node(501803332,Node(1693355428,Leaf,Leaf),Leaf))))),Leaf))),Node(1944461071,Node(336905491,Node(999775328,Node(347607324,Node(920665807,Node(1690217747,Node(527557142,Node(445489093,Node(1178791353,Node(1961044254,Node(2083996938,Leaf,Leaf),Leaf),Leaf),Node(739898391,Node(2042455420,Node(138153241,Node(752385655,Node(208395733,Leaf,Node(1405557904,Node(1718996046,Node(139357659,Leaf,Node(2130407764,Node(2018789520,Node(293555456,Leaf,Node(917336557,Node(1411277916,Node(1915426397,Node(1742699137,Leaf,Node(2038300886,Node(1127519737,Leaf,Leaf),Node(1982578946,Leaf,Leaf))),Node(874287515,Node(1142132263,Node(125251633,Node(342710289,Node(102589284,Leaf,Leaf),Node(1577122393,Node(384394579,Node(540780286,Leaf,Leaf),Node(1892631993,Node(930170813,Node(402736746,Node(750179282,Leaf,Node(48451770,Leaf,Node(666513347,Node(917276712,Node(699519180,Leaf,Leaf),Leaf),Node(1182706368,Node(1351249791,Node(796598837,Leaf,Leaf),Leaf),Leaf)))),Leaf),Leaf),Leaf)),Node(1341205351,Leaf,Node(1106881288,Node(1584892910,Node(2083911718,Node(1893704050,Leaf,Leaf),Node(1930318316,Leaf,Leaf)),Node(2014637339,Leaf,Leaf)),Node(45616928,Leaf,Leaf))))),Node(1044881625,Leaf,Node(847624229,Node(981811913,Node(959030936,Leaf,Leaf),Node(888045724,Node(598670312,Leaf,Leaf),Node(1858222587,Leaf,Leaf))),Leaf))),Node(241865325,Leaf,Leaf)),Node(447897867,Leaf,Leaf))),Leaf),Leaf)),Leaf),Leaf)),Leaf),Node(879192756,Node(1623570405,Node(683392684,Node(203395187,Leaf,Node(505635439,Leaf,Node(1841020678,Leaf,Leaf))),Node(1117319958,Leaf,Leaf)),Leaf),Node(226277723,Node(1811696780,Node(296031874,Leaf,Leaf),Node(1259632926,Leaf,Node(277499413,Node(382099280,Node(146481458,Leaf,Leaf),Node(629221936,Node(895462740,Node(32117592,Leaf,Node(194542736,Node(1910089126,Node(1056131651,Leaf,Leaf),Node(1427848831,Node(269116714,Leaf,Node(1232408924,Node(1362185764,Leaf,Node(1158306493,Leaf,Leaf)),Node(1808506962,Leaf,Leaf))),Node(22917761,Leaf,Node(863331679,Leaf,Node(870655722,Node(333411882,Node(1848135124,Leaf,Node(1675333843,Leaf,Leaf)),Node(1881089839,Node(1184464876,Leaf,Leaf),Leaf)),Leaf))))),Leaf)),Leaf),Node(1691844555,Leaf,Node(1275029655,Node(585211425,Node(1922991885,Leaf,Leaf),Node(1492568171,Node(918919439,Node(229350485,Node(1475470465,Leaf,Node(639531863,Node(1339502493,Leaf,Leaf),Node(821980158,Leaf,Leaf))),Leaf),Node(949523537,Leaf,Node(888724092,Node(191727167,Node(1155422934,Node(2083126072,Leaf,Leaf),Node(235616295,Leaf,Leaf)),Leaf),Leaf))),Leaf)),Node(1517295560,Node(1501594836,Leaf,Node(179352089,Leaf,Node(2079836125,Leaf,Leaf))),Leaf))))),Node(42953024,Node(352933693,Leaf,Node(395573983,Leaf,Leaf)),Leaf)))),Leaf)))),Leaf),Leaf),Leaf),Leaf)),Leaf),Leaf),Node(777039978,Leaf,Leaf)),Node(135339096,Leaf,Node(1377457960,Node(206105148,Leaf,Leaf),Node(677106954,Leaf,Node(656962080,Leaf,Node(62466151,Node(1512878953,Node(777886838,Leaf,Node(1456997252,Leaf,Node(1570546754,Leaf,Leaf))),Node(1762218562,Node(474643987,Node(2074192332,Node(1350078875,Node(1998211310,Leaf,Leaf),Node(1881946529,Leaf,Node(121962180,Node(813644287,Node(1027054439,Node(29771815,Node(264822160,Node(691949580,Node(1362008478,Node(2001117972,Node(1687050163,Leaf,Leaf),Node(1782686368,Leaf,Leaf)),Leaf),Leaf),Node(1118894343,Node(1324333625,Leaf,Node(1147213592,Leaf,Leaf)),Node(176949964,Node(1515653024,Leaf,Node(1294550618,Node(434008033,Node(1053174881,Leaf,Node(1206605290,Leaf,Node(163354770,Node(822971470,Node(858727504,Leaf,Leaf),Leaf),Leaf))),Leaf),Leaf)),Node(499664126,Leaf,Node(973659227,Node(1030694129,Node(45584570,Node(69369918,Leaf,Node(1167987330,Node(589580230,Node(587491777,Leaf,Node(213370439,Leaf,Node(487854318,Node(1255396387,Node(1235359754,Node(1958299565,Leaf,Leaf),Node(353195407,Leaf,Leaf)),Leaf),Node(1067023009,Leaf,Leaf)))),Node(1149248779,Leaf,Leaf)),Leaf)),Node(1868956675,Leaf,Leaf)),Node(1798299114,Leaf,Node(444023314,Node(398870557,Leaf,Node(841907274,Leaf,Leaf)),Leaf))),Leaf))))),Node(235438067,Node(31288121,Node(533469225,Leaf,Node(1277813228,Node(648648211,Node(1139167660,Leaf,Node(60700537,Node(1899747683,Leaf,Leaf),Leaf)),Node(1541943285,Node(1601657818,Node(735413710,Leaf,Leaf),Node(31530115,Leaf,Node(207606302,Node(1450276163,Node(1189621384,Node(1902014438,Leaf,Node(617324209,Leaf,Node(1816377273,Node(1660588410,Leaf,Leaf),Leaf))),Node(243274144,Node(241871097,Leaf,Node(1770078726,Leaf,Leaf)),Leaf)),Leaf),Node(770556097,Leaf,Node(1965579506,Node(856718836,Leaf,Node(1521061450,Leaf,Leaf)),Node(1511441475,Node(1096137115,Leaf,Leaf),Leaf)))))),Leaf)),Leaf)),Leaf),Leaf)),Leaf),Node(1076168840,Leaf,Node(1112617242,Leaf,Leaf))),Node(2050525148,Node(843710453,Leaf,Node(2011456036,Node(424610080,Node(132066304,Node(1776663434,Leaf,Node(1792429288,Leaf,Node(1810594793,Leaf,Leaf))),Node(438824820,Leaf,Leaf)),Node(2106913993,Leaf,Leaf)),Leaf)),Leaf)))),Leaf),Leaf),Node(2094188649,Leaf,Leaf))),Leaf)))))),Leaf),Node(438058877,Leaf,Leaf)),Node(1115560626,Leaf,Node(544833571,Node(1144066435,Leaf,Node(1535483275,Node(845115662,Node(548066541,Leaf,Node(1236102956,Node(313421543,Node(1983731659,Node(1732936797,Leaf,Node(769737863,Leaf,Leaf)),Node(968140522,Node(668279634,Leaf,Leaf),Leaf)),Node(1750625744,Node(707809587,Node(1418448648,Node(1788201012,Leaf,Leaf),Node(761325346,Node(538680091,Node(4200917,Node(1739234442,Leaf,Leaf),Node(1829431520,Node(371636398,Node(1513733974,Leaf,Leaf),Leaf),Node(960180587,Leaf,Leaf))),Leaf),Leaf)),Leaf),Node(1258944474,Node(284506350,Node(1604148055,Leaf,Leaf),Leaf),Node(572773065,Leaf,Node(1994494908,Leaf,Leaf))))),Node(1116796400,Node(262402614,Leaf,Node(1468107681,Node(1737540216,Node(706531568,Leaf,Node(1070116568,Node(1275511413,Node(322320451,Leaf,Leaf),Leaf),Node(274276772,Leaf,Leaf))),Node(757244022,Node(1020447034,Node(1280555444,Leaf,Leaf),Node(2026715438,Node(1549660987,Leaf,Leaf),Node(1170210956,Leaf,Node(1456225412,Node(56543199,Node(377796072,Leaf,Leaf),Leaf),Node(1464273097,Node(846443248,Node(906801677,Node(238576817,Leaf,Leaf),Node(290195999,Node(1191258206,Leaf,Node(1603493001,Leaf,Leaf)),Leaf)),Leaf),Node(689294302,Node(796049616,Node(1795464979,Node(965442012,Leaf,Node(755638092,Leaf,Leaf)),Leaf),Leaf),Leaf)))))),Node(1732152785,Node(2140620837,Node(776508042,Leaf,Leaf),Node(1435259543,Leaf,Node(1588964121,Node(413561528,Node(776243445,Node(592459731,Leaf,Leaf),Leaf),Node(1817844250,Node(516380281,Leaf,Leaf),Node(1548113722,Leaf,Leaf))),Leaf))),Leaf))),Leaf)),Node(1185096050,Node(1029106350,Node(184510866,Leaf,Node(362036585,Leaf,Node(128296240,Node(1627269506,Leaf,Node(2090879802,Leaf,Node(333215613,Leaf,Node(1079004105,Node(1848155577,Node(487968546,Leaf,Leaf),Leaf),Node(1875234777,Leaf,Node(338672486,Leaf,Node(1839586541,Node(1931499884,Node(1536443597,Leaf,Leaf),Leaf),Node(1617641784,Node(1097407653,Leaf,Node(670654883,Node(903759730,Node(2127361801,Node(537860498,Node(915878817,Node(1805082922,Leaf,Node(1398840082,Leaf,Leaf)),Node(1522849047,Node(1175060183,Leaf,Node(683428407,Node(1583974996,Node(1857827066,Node(774086142,Node(1626586886,Node(1770186721,Node(1015458616,Node(392136894,Node(1565231547,Leaf,Node(1660264617,Leaf,Node(1205224131,Node(168021039,Node(2140404856,Node(1224551409,Node(1923712572,Node(74554756,Leaf,Node(430570262,Leaf,Leaf)),Node(1704365822,Leaf,Node(39940561,Leaf,Node(372275546,Leaf,Node(196870242,Leaf,Node(1143075178,Leaf,Node(515970163,Node(27775711,Node(2120536517,Node(109223634,Leaf,Node(495015125,Node(1866380327,Node(1729627355,Leaf,Node(447501544,Leaf,Node(1823884930,Node(653753331,Node(1111509701,Node(37822220,Node(16217851,Node(212486938,Node(1787208701,Leaf,Leaf),Node(1529785121,Node(1390053023,Leaf,Node(1732608793,Node(646276574,Leaf,Node(244992842,Leaf,Leaf)),Node(1780823801,Node(1329160647,Leaf,Leaf),Node(1299673046,Node(985992918,Leaf,Leaf),Leaf)))),Node(1538420698,Node(339401341,Node(483863045,Node(755607764,Node(743323124,Node(62245130,Node(1632277381,Node(536336535,Leaf,Leaf),Node(1240517523,Leaf,Leaf)),Leaf),Node(1207681004,Leaf,Leaf)),Node(1995954809,Leaf,Node(1298495617,Node(1904850566,Node(1503444790,Leaf,Node(398087678,Node(996436761,Node(1088393031,Node(63857362,Leaf,Leaf),Leaf),Node(1561517718,Node(980861102,Leaf,Leaf),Leaf)),Leaf)),Leaf),Node(222547379,Leaf,Node(504243911,Node(120802801,Node(2065289081,Node(1285657710,Node(644338662,Leaf,Leaf),Leaf),Node(670224912,Leaf,Node(694902580,Node(406984210,Leaf,Node(40533007,Leaf,Leaf)),Leaf))),Node(555272564,Leaf,Node(727206632,Node(2146187695,Leaf,Leaf),Node(2014738059,Node(1190951615,Node(1591136840,Leaf,Leaf),Node(816409335,Leaf,Leaf)),Leaf)))),Node(1843123397,Leaf,Leaf)))))),Leaf),Leaf),Node(514295781,Node(1191918781,Leaf,Node(1304944810,Leaf,Node(1149023706,Node(1717045566,Leaf,Leaf),Leaf))),Leaf)))),Node(1462424655,Leaf,Node(2075517652,Node(1023003579,Leaf,Leaf),Node(487175817,Leaf,Leaf)))),Leaf),Node(1783806778,Node(1478758314,Leaf,Node(1763473933,Leaf,Node(1956068189,Node(812476009,Leaf,Leaf),Leaf))),Leaf)),Node(219522495,Node(1127216871,Node(806904836,Leaf,Node(1601879278,Node(143257247,Leaf,Leaf),Node(1507308397,Node(1953280636,Node(713573709,Leaf,Leaf),Leaf),Node(1552741802,Node(1944016172,Node(1955649558,Leaf,Leaf),Node(633125608,Leaf,Node(1807788596,Leaf,Node(1357275668,Leaf,Node(580244683,Leaf,Node(788498371,Leaf,Leaf)))))),Node(260147343,Leaf,Leaf))))),Node(1955418221,Node(1458433221,Node(2142064570,Node(572650584,Node(1181226696,Node(678461782,Node(1291617828,Node(1784831915,Leaf,Leaf),Leaf),Leaf),Leaf),Node(2011026612,Leaf,Node(223182838,Node(683416471,Node(1223260320,Leaf,Node(88360722,Node(1034231407,Leaf,Node(1813066925,Leaf,Leaf)),Leaf)),Leaf),Leaf))),Leaf),Node(1648247995,Leaf,Leaf)),Leaf)),Node(37693793,Leaf,Leaf))),Leaf))),Node(1704012229,Leaf,Node(1481129441,Leaf,Node(919355921,Leaf,Leaf)))),Leaf)),Node(920449746,Leaf,Node(711567005,Node(94618134,Node(1081474443,Node(1270892933,Leaf,Leaf),Leaf),Node(1318925142,Node(231162742,Node(181536558,Node(42959855,Node(1898933505,Leaf,Node(1165421706,Node(2081597116,Node(199727501,Node(666156955,Node(1000649537,Leaf,Leaf),Node(1460145137,Node(2026822667,Node(1492707543,Node(1100980548,Node(1662464460,Leaf,Node(1207084556,Node(625750321,Node(1314028159,Node(1739113024,Leaf,Leaf),Node(1333700584,Leaf,Node(1633506902,Leaf,Node(1523364725,Leaf,Node(1947039077,Leaf,Leaf))))),Leaf),Leaf)),Leaf),Node(9240481,Node(670197562,Node(287265766,Node(917303961,Leaf,Leaf),Node(289185197,Node(733348638,Leaf,Leaf),Leaf)),Leaf),Node(545085842,Node(1004046321,Node(356322631,Node(1211633089,Leaf,Node(1408905411,Leaf,Node(1570587071,Leaf,Leaf))),Node(82378094,Node(1739907096,Node(1049539255,Node(1719517040,Node(1483888124,Node(1026684207,Leaf,Leaf),Node(1291452034,Node(575411443,Leaf,Node(322054739,Leaf,Node(1383488186,Leaf,Node(1487293428,Leaf,Node(131484127,Node(619231793,Leaf,Node(2106403651,Node(720989860,Leaf,Leaf),Leaf)),Leaf))))),Leaf)),Node(1628848327,Leaf,Node(1130023210,Leaf,Node(475868590,Leaf,Leaf)))),Node(1009414412,Node(850414598,Node(517398013,Leaf,Node(730750056,Node(565641202,Leaf,Leaf),Leaf)),Leaf),Node(1341066365,Node(253085045,Leaf,Node(1242991805,Leaf,Node(889096311,Node(1464241562,Leaf,Node(1138301918,Leaf,Node(505737755,Leaf,Leaf))),Node(572791337,Node(1270844184,Leaf,Leaf),Node(1051379051,Node(358384728,Node(144781143,Leaf,Leaf),Node(1241448701,Leaf,Node(1461649629,Node(561311822,Node(2050770948,Leaf,Leaf),Node(1365570984,Leaf,Node(1513348772,Node(2128051292,Leaf,Node(112732794,Node(709021312,Leaf,Leaf),Node(965928431,Leaf,Node(2137569750,Node(611139171,Leaf,Node(1518838287,Node(1538128229,Leaf,Node(1627401238,Leaf,Node(1483782696,Leaf,Node(432297178,Leaf,Node(1576622729,Leaf,Leaf))))),Node(1926273097,Leaf,Node(31893274,Node(556499418,Node(488736857,Leaf,Leaf),Node(124406252,Leaf,Leaf)),Node(67950455,Node(647889174,Node(384845133,Leaf,Node(609811378,Leaf,Leaf)),Node(790888106,Node(726237244,Node(135221021,Node(751256640,Node(1634153137,Leaf,Node(1299461488,Node(2027908487,Node(1413673452,Leaf,Node(2068400465,Leaf,Node(1507112642,Node(1982773238,Leaf,Leaf),Leaf))),Node(104912770,Leaf,Leaf)),Node(1260032231,Leaf,Node(1739958808,Leaf,Node(975909874,Leaf,Node(261234700,Leaf,Leaf)))))),Node(479582997,Node(1051031299,Leaf,Leaf),Leaf)),Node(172944823,Leaf,Node(89205285,Leaf,Node(1688726810,Node(688061985,Node(1616337826,Leaf,Leaf),Node(292124382,Leaf,Leaf)),Node(911579760,Leaf,Leaf))))),Leaf),Node(824998114,Leaf,Node(939639958,Node(234354806,Leaf,Leaf),Node(1739238105,Node(1803591830,Node(1696126029,Leaf,Node(956189731,Node(1666399952,Leaf,Leaf),Node(1319155766,Node(1608131901,Node(2046147472,Node(842994355,Leaf,Leaf),Leaf),Node(1823023871,Leaf,Node(521734254,Node(1786125688,Node(681741507,Leaf,Leaf),Leaf),Node(90124836,Node(66197444,Leaf,Leaf),Node(1268634685,Leaf,Node(1956164058,Leaf,Node(764557972,Leaf,Leaf))))))),Leaf))),Node(2099278852,Node(628324478,Node(1859953139,Node(1762128727,Leaf,Node(497666184,Leaf,Node(1981472867,Leaf,Leaf))),Node(1941791634,Node(1550678417,Leaf,Leaf),Leaf)),Leaf),Node(1869101843,Node(668550825,Node(910282587,Leaf,Node(752653966,Node(1304257385,Leaf,Leaf),Leaf)),Leaf),Leaf))),Leaf))))),Node(340629895,Leaf,Node(1785315526,Leaf,Node(1544236995,Node(369442224,Leaf,Node(1045400946,Node(890398677,Leaf,Leaf),Leaf)),Leaf)))))))),Node(788419368,Node(421722021,Leaf,Leaf),Node(1232660608,Node(798230129,Leaf,Leaf),Leaf)))))),Leaf))),Leaf))),Node(435673325,Node(655485784,Leaf,Leaf),Node(1256540462,Leaf,Node(798289281,Node(1455551574,Leaf,Leaf),Leaf)))))))),Leaf))),Leaf),Leaf)),Leaf),Leaf))),Node(819724459,Leaf,Leaf)),Leaf)),Node(1757614078,Node(612454561,Leaf,Node(1063132795,Node(327130009,Node(931114064,Leaf,Leaf),Node(170101599,Node(1310167864,Node(302888499,Node(321181183,Leaf,Node(999989665,Node(1982382246,Node(1541527486,Leaf,Node(258880472,Node(798130218,Leaf,Node(241057842,Leaf,Leaf)),Node(1348891791,Node(489410251,Leaf,Node(303099825,Leaf,Leaf)),Node(950367160,Node(147091652,Leaf,Node(105382514,Leaf,Node(911857864,Node(392893529,Leaf,Node(195111093,Leaf,Leaf)),Leaf))),Node(228164271,Leaf,Node(481851008,Node(1508481474,Node(355876700,Leaf,Leaf),Leaf),Leaf)))))),Node(436799485,Leaf,Leaf)),Node(1751614386,Leaf,Node(1541933600,Leaf,Node(566214400,Leaf,Node(287788294,Node(1053006300,Leaf,Node(1851461044,Node(1880934875,Leaf,Leaf),Leaf)),Node(1384879134,Node(845511303,Leaf,Leaf),Node(640231111,Leaf,Node(523428363,Leaf,Node(1371668680,Leaf,Leaf)))))))))),Leaf),Leaf),Node(2118508591,Leaf,Leaf))),Leaf)),Node(1545364702,Node(1786854534,Node(1576451211,Leaf,Leaf),Leaf),Node(2026860659,Node(427385307,Node(224613198,Node(1412707929,Leaf,Leaf),Leaf),Leaf),Leaf)))),Node(2042646107,Leaf,Node(579492798,Node(1118884534,Node(1768637683,Leaf,Node(596898378,Leaf,Node(1116365052,Leaf,Leaf))),Node(46748155,Leaf,Node(1527898359,Node(1066487851,Leaf,Node(2029791352,Node(243945686,Leaf,Node(601441852,Leaf,Leaf)),Leaf)),Node(1916545467,Leaf,Leaf)))),Leaf))),Node(2029548150,Node(502947918,Leaf,Node(828091537,Node(119697231,Node(304687820,Node(1978292438,Leaf,Leaf),Node(2076384865,Node(677689191,Leaf,Node(1497479628,Node(833317247,Leaf,Leaf),Leaf)),Node(1048045469,Node(1892723798,Leaf,Leaf),Node(1332792251,Node(721566040,Leaf,Node(612977888,Leaf,Leaf)),Leaf)))),Leaf),Leaf)),Leaf))),Node(2131115526,Node(865806232,Leaf,Leaf),Leaf)),Leaf),Node(1750558766,Node(919733138,Leaf,Node(1823671379,Leaf,Node(1573980803,Leaf,Node(1860500452,Leaf,Leaf)))),Leaf)),Node(1595771906,Leaf,Leaf))),Node(1448329905,Node(2008065382,Node(2014020891,Leaf,Leaf),Node(1407038962,Node(451409856,Node(695025434,Node(1336069439,Leaf,Node(1238313110,Node(544424603,Node(387493514,Leaf,Node(286289806,Leaf,Node(2054453997,Leaf,Leaf))),Leaf),Node(242805967,Node(1106268656,Node(350846774,Node(1350327373,Leaf,Leaf),Node(1977473610,Leaf,Leaf)),Node(2070168702,Leaf,Leaf)),Leaf))),Node(1315408362,Node(754442337,Leaf,Node(1646782673,Node(1228739751,Node(1518693251,Leaf,Node(684323869,Node(1492949203,Leaf,Leaf),Node(1012029005,Leaf,Node(1086461998,Leaf,Leaf)))),Leaf),Leaf)),Node(235917988,Node(1816982736,Node(630986509,Leaf,Node(1662024668,Node(1793813754,Node(1949400783,Node(112166246,Node(1625398929,Leaf,Leaf),Leaf),Leaf),Node(1264306787,Leaf,Node(301722162,Leaf,Node(1981100883,Node(551781513,Node(1721443107,Node(957108088,Node(743832602,Node(156937181,Node(2001645738,Node(1331656112,Leaf,Node(1830831640,Node(1489110160,Leaf,Node(750674043,Leaf,Leaf)),Node(1595980592,Leaf,Leaf))),Node(1001904220,Leaf,Leaf)),Leaf),Leaf),Leaf),Node(1179245095,Leaf,Leaf)),Node(583556179,Node(1868797771,Node(240206648,Node(627382349,Node(1556155001,Leaf,Node(1160517188,Leaf,Node(444424358,Node(1817333894,Leaf,Node(1807580431,Leaf,Node(2019244362,Leaf,Node(1048621711,Leaf,Leaf)))),Node(1021138713,Leaf,Leaf)))),Node(590000894,Leaf,Leaf)),Leaf),Leaf),Node(1000930789,Leaf,Leaf))),Node(248537844,Node(11689359,Node(1895680449,Leaf,Leaf),Leaf),Leaf))))),Leaf)),Node(2028270761,Leaf,Leaf)),Node(1855528887,Leaf,Leaf)))),Node(1353341393,Node(1241740284,Node(2109918760,Leaf,Node(1399299675,Leaf,Leaf)),Node(1399095892,Node(1176197953,Node(1670441243,Node(1770206701,Leaf,Leaf),Leaf),Leaf),Node(144705547,Leaf,Leaf))),Node(1152412993,Leaf,Leaf))),Leaf)),Leaf)))),Node(106927405,Leaf,Node(663610520,Leaf,Node(1263515402,Leaf,Node(1162951701,Node(962287078,Node(2069521176,Leaf,Leaf),Node(1263720784,Node(1522681012,Leaf,Node(1798530581,Node(2036544459,Leaf,Leaf),Leaf)),Node(1134396934,Node(961905142,Leaf,Leaf),Node(464201627,Leaf,Node(1241773751,Node(1677551577,Node(1116808993,Leaf,Leaf),Leaf),Node(1585684001,Leaf,Node(583702297,Node(1508693397,Leaf,Node(1787017032,Node(985855386,Leaf,Node(174717771,Node(2057668840,Node(370656407,Leaf,Leaf),Leaf),Leaf)),Node(518312258,Leaf,Leaf))),Leaf))))))),Node(1070875401,Leaf,Leaf)))))),Node(1516814311,Node(1175513833,Node(627264700,Node(1217695332,Leaf,Node(1903134145,Node(128946260,Leaf,Node(281838375,Leaf,Leaf)),Leaf)),Leaf),Node(900791999,Leaf,Leaf)),Leaf)))))))),Node(2127561919,Node(1862770946,Node(1352238870,Leaf,Node(742825353,Node(776247301,Leaf,Leaf),Leaf)),Node(1227164831,Leaf,Node(992055142,Node(1999107528,Node(425097523,Node(314025380,Leaf,Leaf),Leaf),Leaf),Node(1004296068,Node(890541927,Leaf,Leaf),Leaf)))),Node(808483395,Node(1051029126,Node(457094718,Node(766420837,Leaf,Leaf),Leaf),Leaf),Leaf))),Leaf),Node(185786674,Node(665046594,Node(1310413580,Node(2090333047,Leaf,Node(969402952,Leaf,Node(804154574,Node(1248652215,Node(1841002305,Leaf,Leaf),Node(117353301,Node(1538526132,Leaf,Node(1855012044,Leaf,Node(207455519,Leaf,Leaf))),Leaf)),Node(683680906,Node(1171780949,Leaf,Node(1972666082,Node(1084139886,Leaf,Leaf),Leaf)),Node(659809448,Node(1788509564,Node(261691616,Node(1894676976,Leaf,Node(779560838,Node(2079766368,Leaf,Node(1538452795,Leaf,Leaf)),Leaf)),Node(1939591829,Leaf,Leaf)),Leaf),Node(1668191806,Node(444024,Node(1553863922,Leaf,Leaf),Node(1955791142,Leaf,Leaf)),Node(2131108134,Node(851217252,Node(628049143,Leaf,Node(1579834469,Leaf,Leaf)),Node(735395169,Leaf,Node(664831352,Node(1288344828,Node(2088572513,Leaf,Leaf),Leaf),Leaf))),Node(1709268940,Leaf,Leaf)))))))),Leaf),Node(1277099184,Leaf,Leaf)),Node(1811353066,Leaf,Node(240380942,Node(420533507,Leaf,Node(1935999197,Leaf,Node(961764998,Leaf,Leaf))),Node(1368438462,Leaf,Leaf))))),Node(1459156866,Node(508593921,Leaf,Node(1342055918,Node(1235088858,Leaf,Leaf),Node(303695683,Leaf,Leaf))),Node(1673563416,Leaf,Node(299150770,Node(864735606,Leaf,Node(1619649735,Node(732082945,Leaf,Leaf),Node(1603619157,Node(1644506216,Node(489870855,Leaf,Node(1271792315,Leaf,Node(1085710395,Leaf,Leaf))),Leaf),Node(1605352201,Node(752104380,Node(1404438744,Node(1177920202,Node(1521787147,Node(1381512936,Node(1753216667,Leaf,Leaf),Leaf),Leaf),Leaf),Node(1829870976,Leaf,Leaf)),Node(778923833,Node(676642451,Node(1213460054,Leaf,Leaf),Node(423330336,Node(352496254,Leaf,Leaf),Node(1034493811,Leaf,Leaf))),Node(186346797,Node(2032506759,Node(488751679,Leaf,Leaf),Node(396537299,Node(1989745033,Leaf,Leaf),Node(125870416,Leaf,Leaf))),Node(1678489975,Leaf,Node(720634326,Leaf,Node(2100431330,Leaf,Node(1098392986,Leaf,Node(1767948256,Leaf,Leaf)))))))),Node(1386288615,Leaf,Leaf))))),Leaf)))))),Leaf),Leaf),Leaf),Leaf),Node(1343271357,Node(271096516,Node(1715665742,Node(1840370136,Leaf,Node(787470736,Leaf,Leaf)),Node(1332015792,Leaf,Node(627800234,Node(1310748464,Node(1034109571,Node(1623299996,Leaf,Node(790790005,Leaf,Node(2080820518,Leaf,Node(601709648,Leaf,Node(1688962583,Leaf,Leaf))))),Leaf),Leaf),Leaf))),Leaf),Node(1916676825,Leaf,Leaf))),Leaf),Leaf),Node(2030181240,Leaf,Leaf))),Node(274994169,Node(591272349,Node(48165818,Node(320791571,Node(957042650,Leaf,Leaf),Leaf),Leaf),Leaf),Node(617600893,Leaf,Node(1046009482,Leaf,Leaf))))),Leaf),Leaf),Leaf),Leaf)),Node(1876494173,Leaf,Node(1816931660,Node(1029219109,Node(683860295,Leaf,Leaf),Node(2003277882,Node(1934664273,Leaf,Leaf),Leaf)),Leaf)))))))))),Node(1144234632,Node(798720331,Leaf,Node(310669294,Node(1126578702,Leaf,Node(546936599,Leaf,Node(1166806376,Node(102446987,Node(1345267125,Leaf,Leaf),Leaf),Node(1616211490,Node(2068455016,Leaf,Node(82225179,Node(1454572739,Leaf,Leaf),Leaf)),Leaf)))),Leaf)),Node(795038581,Leaf,Leaf))))),Leaf),Node(414803235,Node(1204944669,Leaf,Node(171621516,Leaf,Node(2085407485,Node(120713093,Node(1084102736,Node(119013833,Leaf,Node(1479340200,Leaf,Node(302604169,Node(1808746192,Node(2068504974,Leaf,Leaf),Leaf),Node(1003147779,Node(348811462,Leaf,Node(472815309,Node(953748319,Leaf,Leaf),Leaf)),Leaf)))),Leaf),Node(1521927796,Node(183853645,Leaf,Leaf),Leaf)),Leaf))),Leaf))))),Node(1910562605,Leaf,Node(2134797781,Leaf,Node(693328957,Leaf,Node(583098534,Leaf,Leaf))))),Leaf)),Leaf)))),Node(1352018430,Node(490388481,Node(1760754833,Node(193137870,Node(2084101942,Leaf,Leaf),Node(1187914523,Leaf,Node(1610064500,Node(1810590643,Leaf,Leaf),Node(1921617932,Leaf,Leaf)))),Node(93945657,Node(244776866,Leaf,Node(1603842811,Leaf,Leaf)),Leaf)),Node(1888574252,Leaf,Leaf)),Node(913577425,Leaf,Node(75114207,Leaf,Node(1948276244,Leaf,Leaf))))),Leaf),Leaf),Node(1944580542,Node(1216477531,Leaf,Node(731885741,Node(117858180,Node(55665558,Node(1467318932,Node(1994573049,Node(1485409662,Leaf,Node(271303064,Leaf,Node(230702125,Node(1530980277,Leaf,Node(976166448,Leaf,Node(1562174698,Leaf,Leaf))),Leaf))),Node(3948466,Leaf,Node(493758894,Leaf,Node(981580415,Leaf,Leaf)))),Node(1177595825,Leaf,Node(408575086,Leaf,Node(541799477,Leaf,Node(1231465867,Leaf,Node(1034465034,Leaf,Leaf)))))),Leaf),Leaf),Leaf)),Leaf))),Node(1499720720,Leaf,Node(1246677348,Leaf,Node(1185405949,Leaf,Leaf))))\n" ] } ], "source": [ "println(genNumTree(rand))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Arithmetic Expression Grammar\n", "\n", "Let us now examine a grammar for arithmetic expressions involving operators like `+`, `*`, `/` and even functions like log, exp, sine and cosine.\n", "\n", "$$\\begin{array}{rcc}\n", "\\textbf{Expr} & \\rightarrow & Const(\\textbf{Integer}) \\\\\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{Integer} & \\rightarrow & \\cdots\\ |\\ -2\\ |\\ -1\\ |\\ 0\\ |\\ 1\\ |\\ 2\\ |\\ \\cdots \\\\\n", "\\textbf{Identifier} & \\rightarrow & [a-z\\ A-Z][a-z\\ A-Z\\ 0-9\\ \\_]*\n", "\\end{array}$$\n", "\n", "We will clarify a few things first. The non terminal **Identifier** stands for a string that\n", "represents a variable name like `x`, `y`, `velocity`, `s_29109_12xyZ` and so on. We wrote a regular expression as a stand in for all possible legal variable names that can appear.\n", "\n", "The start symbol is **Expr**. \n", "\n", "Let us look at some examples of expressions that can be created this way.\n", "\n", "1. $ x^2 + 5$ is expressed as Plus(Mult( Ident(\"x\"), Ident(\"x\")), Const(5))\n", "2. $ \\sin(x) + \\cos(x)$ is expressed as Plus(Sine(Ident(\"x\")), Cosine(Ident(\"x\")))\n", "3. $e^{e^{xy}}$ is expressed as Exp(Exp(Mult( Ident(\"x\"), Ident(\"y\") ) ))\n", "\n", "You can guess from the context what the symbols *Plus, Minus, Mult, Div, Log,\n", "Exp, Sine* and *Cosine* should mean. The symbols *Const* and *Ident* seem superfluous here. After all, \n", "if there is a string \"x\" it can only refer to an identifier and if there is an integer 10, it can only\n", "be a constant. However, for Scala (or any other programming language) \"x\" is a string and 10 is an integer.\n", "We need a means to tell the Scala interpreter to *promote* a number 10 to an expression 10 or a string \"x_25\" to \n", "the expression \"x_25\". The easiest way to achieve this is to wrap these inside a symbol such as *Const* or\n", "*Ident* that makes it easy for\n", "the Scala interpreter to undertand what is going on.\n", "\n" ] }, { "cell_type": "code", "execution_count": 21, "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": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait Expr\n", "\n", "// We cheated a bit and allowed all double precision numbers in Scala.\n", "case class Const(d: Double) extends Expr \n", "\n", "// We allow any string to be an identifier for now instead of the regular \n", "// expression shown in the grammar.\n", "case class Ident(s: String) extends Expr\n", "\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": "code", "execution_count": 22, "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[36mv\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(e1 = \u001b[33mCosine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m)), e2 = \u001b[33mSine\u001b[39m(e = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m)))" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val x = Ident(\"x\")\n", "val y = Ident(\"y\")\n", "val v = Plus(Cosine(x), Sine(y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The syntax tree for the term *Plus(Cosine(Ident(x)), Sine(Ident(y)))* is \n", "\n", "\"Term\n", "\n", "Note how *Plus* has two children but *Cosine*, *Sine* and *Ident* have one child.\n", "\n", "Finally, you can also see how a pre-order traversal of this tree gives us the \"flat\" representation of the term\n", "*Plus(Cosine(Ident(x)), Sine(Ident(y)))*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise**: Write a function that randomly generates terms of type **Expr**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Conditional Expressions\n", "\n", "We just saw a grammar for arithmetic expressions. Let us build a grammar on top of that to define conditional statements such as \n", "\n", "$$ x^2 \\geq y + 3 \\ \\&\\&\\ x + y - e^z \\leq 0 $$\n", "\n", "The grammar is going to refer to the non terminal __Expr__ from the previous grammar. \n", "\n", "$$\\begin{array}{rclll}\n", "\\textbf{CondExpr} & \\rightarrow & ConstTrue & \\mbox{constant boolean true}\\\\\n", "& | & ConstFalse & \\mbox{constant boolean false} \\\\\n", "& | & Geq( \\textbf{Expr} ,\\textbf{Expr}) & \\ e_1 \\geq e_2 \\\\\n", "& | & Leq (\\textbf{Expr}, \\textbf{Expr}) & \\ e_1 \\leq e_2 \\\\\n", "& | & Eq(\\textbf{Expr} , \\textbf{Expr}) & e_1 == e_2 \\\\\n", "& | & And(\\textbf{CondExpr}, \\textbf{CondExpr}) & \\ c_1\\ \\mbox{and}\\ c_2 \\\\\n", "& | & Or(\\textbf{CondExpr}, \\textbf{CondExpr}) & \\ c_1\\ \\mbox{or}\\ c_2 \\\\\n", "& | & Not(\\textbf{CondExpr}) & \\ \\mbox{not}\\ c_1 \\\\\n", "\\end{array}$$\n", "\n", "Let us take the example above and see how the grammar expresses them?\n", "\n", "#### 1. $ x^2 \\geq y + 3 $\n", "\n", "*Geq*( *Mult*( *Ident*(\"x\"), *Ident*(\"x\") ), *Plus*( *Ident*(\"y\"), *Const*(3) ) ))\n", "\n", "#### 2. $ x + y - e^z \\leq 0$\n", "\n", "*Leq*( *Plus*( *Ident*(\"x\"), *Minus* ( *Ident*(\"y\"), *Exp*( *Ident*(\"z\") ) ) ), *Const* (0) )\n", "\n", "#### 3. $ x^2 \\geq y + 3 \\ \\land\\ x + y - e^z \\leq 0$\n", "\n", "*And*( *Geq*( *Mult*( *Ident*(\"x\"), *Ident*(\"x\") ), *Plus*( *Ident*(\"y\"), *Const*(3) ) )), *Leq*( *Plus*( *Ident*(\"x\"), *Minus* ( *Ident*(\"y\"), *Exp*( *Ident*(\"z\") ) ) ), *Const* (0) ))\n", "\n" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mCondExpr\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mConstTrue\u001b[39m\n", "defined \u001b[32mobject\u001b[39m \u001b[36mConstFalse\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mGeq\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mLeq\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mEq\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mAnd\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mOr\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mNot\u001b[39m" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait CondExpr\n", "case object ConstTrue extends CondExpr\n", "case object ConstFalse extends CondExpr\n", "case class Geq(e1: Expr, e2: Expr) extends CondExpr\n", "case class Leq(e1: Expr, e2: Expr) extends CondExpr\n", "case class Eq(e1: Expr, e2: Expr) extends CondExpr\n", "case class And(c1: CondExpr, c2: CondExpr) extends CondExpr\n", "case class Or(c1: CondExpr, c2: CondExpr) extends CondExpr\n", "case class Not(c: CondExpr) extends CondExpr" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise**: Write a function that randomly generates terms of type **CondExpr**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Syntax for a Simple While Programming Language\n", "\n", "Now we will examine a more complex grammar that inductively defines a simple *While* programming language. Writing and understanding this grammar is _crucial_ since you will need to see how a program can be viewed systematically top down from the program as a whole to individual code blocks, control statements, down to the basic assignments.\n", "\n", "\n", "We would like a grammar that defines simple programs that include (a) variables that take on floating point values, (b) variable declarations, (c) assignment statements, (d) if then else, (e) while loops and (f) return statement.\n", "\n", "\n", "Here is an example program we would like to express:\n", "\n", "~~~\n", "var x = 5;\n", "var y = 15;\n", "var z = 25 + y - x;\n", "x = y + z + exp(x - y);\n", "while ( y <= 15) \n", " begin\n", " y = y + 3 + x/5;\n", " if (x <= 0)\n", " begin\n", " x = -x; \n", " end\n", " end\n", "return (y - x)\n", "~~~\n", "\n", "Let us make up some rules for our *While* language (we will also make up new rules as we go along :-)\n", "\n", " - All identifiers must be declared at the very beginning of the program.\n", " - Each declaration must consist of variable being declared and its initial value must be an expression.\n", " - Variables can be used in the RHS of an expression only after they are declared.\n", " - The language has assignments that allow a declared variable to be assigned an expression involving declared expressions.\n", " - While statements have the structure of `while` keyword followed by a condition, followed by a code block encapsulated within a begin/end\n", " - If statements have the structure of `if` keyword followed by a condition followed by a code block encapsulated within a begin/end and optionally `else` keyword followed by a code block (begin/end)\n", " - Return statements must be `return` keyword followed by an expression.\n", " - A return can occur anywhere in the program. However, the very last statement must (also) be a return statement.\n", "\n", "Let us write the grammar in parts starting from the high level structure of the program.\n", "\n", "$$\\begin{array}{rcll}\n", "\\textbf{Program} & \\rightarrow & \\textbf{Declaration}^*\\ \\textbf{Statement}^*\\ ReturnStmt(\\textbf{Expr}) \\\\\n", "\\end{array}$$\n", "\n", "We have placed a $*$ on top of __Declaration__ and __Statement__. This is called the _Kleene Star_. Whenever we have a symbol __X__ (be it terminal or nonterminal), __X__ * denotes zero or more occurrences of __X__. We are\n", "saying that a __Program__ is made up of _zero or more instances of_ __Declaration__, followed by _zero or more instances of_ __Statement__ and finally a return statement at the very end denoted as _ReturnStmt_ (__Expr__)\n", "\n", "By the way notice that __Expr__ has already been defined previously. We get to reuse all of it here!\n", "\n", "\n", "Next, let us tackle what it means to be a declaration. We know a declaration looks like this\n", "\n", "~~~\n", "var x = 2 * y - z \n", "~~~\n", "\n", "Ignore the \"syntactic junk\" like the keyword var or the =, they are for humans like us. What is important here for a computer? \n", " - First that the variable being declared is \"x\"\n", " - Second that it is initialized to a RHS expression (`2 * y - z`)\n", " - There is a third thing that `y` and `z` must have been previously declared. Let us take a rain check on this requirement for now. I promise we will tackle it later.\n", "\n", "\n", "$$ \\begin{array}{rcll}\n", "\\textbf{Declaration} & \\rightarrow & VarDecl( \\textbf{Identifier}, \\textbf{Expr} )\n", "\\end{array} $$\n", "\n", "We take the two important bits of information from above and encapsulate it inside a nice \"tag\" called _VarDecl_.\n", "Now it is clear to a computer (and perhaps even to us humans).\n", "\n", "Next, let us write a grammar for statements. A statement can be of many types in our language.\n", " - It can be an assignment statement: example `x = y + 5`. \n", " - What information about an assignment statement is relevant here?\n", " - Left hand side : the variable being assigned.\n", " - Right hand side: the expression it is being assigned to.\n", " - All variables involved must be previously declared. We have to take a _rain check_ on this one for now and revisit later.\n", " - A while statement: example `while (x <= y && y <= z) begin .. list of statements .. end `\n", " - The condition for continuing the loop.\n", " - The list of statements inside the loop.\n", " - A if-then-else statement and a variant (a simple if then statement)\n", " `if (condition) begin .. list of statements .. end else begin .. list of statments .. end`\n", " - The condition for the if statement.\n", " - List of statements for the then part\n", " - List of statements for the else part (make it empty if there is no else part)\n", " - A return statement: `return (2 * x + 3 * y) `\n", " - The expression that is being returned.\n", " \n", "With these in mind, we are ready to continue with our grammar.\n", "\n", "$$\\begin{array}{rcll}\n", "\\textbf{Statement} & \\rightarrow & Assign( \\textbf{Identifier}, \\textbf{Expr} ) & \\mbox{assign identifier to expression} \\\\\n", "& | & While(\\textbf{CondExpr}, \\textbf{Statement}^*) & \\mbox{the condition and the list of statements: note the Kleene star} \\\\\n", "& | & IfThenElse(\\textbf{CondExpr}, \\textbf{Statement}^*, \\textbf{Statement}^*) & \\mbox{can you interpret this rule as an exercise?}\\\\\n", "& | & ReturnStmt(\\textbf{Expr}) & \\mbox{return an expression: we already saw this.}\n", "\\end{array}$$\n", "\n", "Note that we have already defined __Expr__, __CondExpr__ and therefore, our grammar is complete. \n", "\n", "Here is the whole grammar at a glance for you:\n", "\n", "$$\\begin{array}{rcll}\n", "\\textbf{Program} & \\rightarrow & \\textbf{Declaration}^*\\ \\textbf{Statement}^*\\ ReturnStmt(\\textbf{Expr}) \\\\[5pt]\n", "\\textbf{Declaration} & \\rightarrow & VarDecl( \\textbf{Identifier}, \\textbf{Expr} )\\\\[5pt]\n", "\\textbf{Statement} & \\rightarrow & Assign( \\textbf{Identifier}, \\textbf{Expr} ) & \\mbox{assign identifier to expression} \\\\\n", "& | & While(\\textbf{CondExpr}, \\textbf{Statement}^*) & \\mbox{the condition and the list of statements: note the Kleene star} \\\\\n", "& | & IfThenElse(\\textbf{CondExpr}, \\textbf{Statement}^*, \\textbf{Statement}^*) & \\mbox{can you interpret this rule as an exercise?}\\\\\n", "& | & ReturnStmt(\\textbf{Expr}) & \\mbox{return an expression: we already saw this.} \\\\[5pt]\n", "\\textbf{CondExpr} & \\rightarrow & ConstTrue & \\mbox{constant boolean true}\\\\\n", "& | & ConstFalse & \\mbox{constant boolean false} \\\\\n", "& | & Geq( \\textbf{Expr} ,\\textbf{Expr}) & \\ e_1 \\geq e_2 \\\\\n", "& | & Leq (\\textbf{Expr}, \\textbf{Expr}) & \\ e_1 \\leq e_2 \\\\\n", "& | & Eq(\\textbf{Expr} , \\textbf{Expr}) & e_1 == e_2 \\\\\n", "& | & And(\\textbf{CondExpr}, \\textbf{CondExpr}) & \\ c_1\\ \\mbox{and}\\ c_2 \\\\\n", "& | & Or(\\textbf{CondExpr}, \\textbf{CondExpr}) & \\ c_1\\ \\mbox{or}\\ c_2 \\\\\n", "& | & Not(\\textbf{CondExpr}) & \\ \\mbox{not}\\ c_1 \\\\[5pt]\n", "\\textbf{Expr} & \\rightarrow & Const(\\textbf{Integer}) \\\\\n", "& | & Ident(\\textbf{Identifier}) \\\\\n", "& | & Plus( \\textbf{Expr}, \\textbf{Expr}^+) & \\textbf{Expr}^+ \\text{denotes one or more occurrences of an expression}\\\\\n", "& | & Minus( \\textbf{Expr}, \\textbf{Expr}^+) & e_1 - e_2 - e_3 - e_4 \\cdots \\\\\n", "& | & Mult(\\textbf{Expr}, \\textbf{Expr}^+) & e_1 * e_2 * e_3 * \\cdots \\\\\n", "& | & Div(\\textbf{Expr}, \\textbf{Expr}) \\\\\n", "& | & Log(\\textbf{Expr}) \\\\\n", "& | & Exp(\\textbf{Expr}) \\\\\n", "& | & Sine(\\textbf{Expr}) \\\\\n", "& | & Cosine(\\textbf{Expr}) \\\\[5pt]\n", "\\textbf{Integer} & \\rightarrow & \\cdots\\ |\\ -2\\ |\\ -1\\ |\\ 0\\ |\\ 1\\ |\\ 2\\ |\\ \\cdots \\\\\n", "\\textbf{Identifier} & \\rightarrow & [a-z\\ A-Z][a-z\\ A-Z\\ 0-9\\ \\_]*\n", "\\end{array}$$\n", "\n", "This was a simple grammar for a toy language. Want to see what the specification for a more complex language like C looks like - see here https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm\n", "\n", "Here is a similar spec for python:\n", "https://docs.python.org/3/reference/grammar.html\n", "\n", "And Scala: \n", "https://www.scala-lang.org/files/archive/spec/2.11/13-syntax-summary.html\n", "\n", "Let us now express this in Scala but at the same time reuse what we have already defined previously such as Expr and CondExpr." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "defined \u001b[32mtrait\u001b[39m \u001b[36mDeclaration\u001b[39m\n", "defined \u001b[32mtrait\u001b[39m \u001b[36mStatement\u001b[39m\n", "defined \u001b[32mtrait\u001b[39m \u001b[36mWhileProgram\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mProgram\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mVarDecl\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mAssignStmt\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mWhileStmt\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mIfThenElseStmt\u001b[39m\n", "defined \u001b[32mclass\u001b[39m \u001b[36mReturnStmt\u001b[39m" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sealed trait Declaration\n", "sealed trait Statement\n", "sealed trait WhileProgram\n", "\n", "case class Program(decls: List[Declaration], stmts: List[Statement], returnAtEnd: Expr) extends WhileProgram // We stripped the ReturnStmt tag since it is redundant\n", "case class VarDecl(identifier: String, rhsExpr: Expr) extends Declaration\n", "case class AssignStmt(identifier: String, rhsExpr: Expr) extends Statement\n", "case class WhileStmt(cond: CondExpr, stmts: List[Statement]) extends Statement\n", "case class IfThenElseStmt(cond: CondExpr, stmtsThen: List[Statement], stmtsElse: List[Statement]) extends Statement\n", "case class ReturnStmt(retExpr: Expr) extends Statement\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Do we want to try and translate this program over into the grammar?\n", "\n", "~~~\n", "var x = 5;\n", "var y = 15;\n", "var z = 25 + y - x;\n", "x = y + z + exp(x - y);\n", "while ( y <= 15) \n", " begin\n", " y = y - x ;\n", " if (x <= 0)\n", " begin\n", " x = -x; \n", " end\n", " end\n", "return (y - x)\n", "~~~\n", "\n", "It is not going to be pretty but we can do it nevertheless by building up sub parts to make up the big program.\n", "It is instructive to do it once and rely on a program to do it.\n" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[36md1\u001b[39m: \u001b[32mVarDecl\u001b[39m = \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"x\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m5.0\u001b[39m))\n", "\u001b[36md2\u001b[39m: \u001b[32mVarDecl\u001b[39m = \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"y\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m))\n", "\u001b[36md3\u001b[39m: \u001b[32mVarDecl\u001b[39m = \u001b[33mVarDecl\u001b[39m(\n", " identifier = \u001b[32m\"z\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m25.0\u001b[39m),\n", " e2 = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", ")\n", "\u001b[36mdecls\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mVarDecl\u001b[39m] = \u001b[33mList\u001b[39m(\n", " \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"x\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m5.0\u001b[39m)),\n", " \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"y\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m)),\n", " \u001b[33mVarDecl\u001b[39m(\n", " identifier = \u001b[32m\"z\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m25.0\u001b[39m),\n", " e2 = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " )\n", ")\n", "\u001b[36me1\u001b[39m: \u001b[32mPlus\u001b[39m = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"z\"\u001b[39m),\n", " e2 = \u001b[33mExp\u001b[39m(e = \u001b[33mMinus\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", ")\n", "\u001b[36mstmt1\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"z\"\u001b[39m),\n", " e2 = \u001b[33mExp\u001b[39m(e = \u001b[33mMinus\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", " )\n", ")\n", "\u001b[36mcond1\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m))\n", "\u001b[36mstmt2\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"y\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", ")\n", "\u001b[36mcond2\u001b[39m: \u001b[32mLeq\u001b[39m = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m))\n", "\u001b[36mstmt3\u001b[39m: \u001b[32mAssignStmt\u001b[39m = \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", ")\n", "\u001b[36mifStmt\u001b[39m: \u001b[32mIfThenElseStmt\u001b[39m = \u001b[33mIfThenElseStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m)),\n", " stmtsThen = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " ),\n", " stmtsElse = \u001b[33mList\u001b[39m()\n", ")\n", "\u001b[36mwhileStmt\u001b[39m: \u001b[32mWhileStmt\u001b[39m = \u001b[33mWhileStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m)),\n", " stmts = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"y\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " ),\n", " \u001b[33mIfThenElseStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m)),\n", " stmtsThen = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " ),\n", " stmtsElse = \u001b[33mList\u001b[39m()\n", " )\n", " )\n", ")\n", "\u001b[36mallstmts\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mProduct\u001b[39m with \u001b[32mStatement\u001b[39m with \u001b[32mSerializable\u001b[39m] = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"z\"\u001b[39m),\n", " e2 = \u001b[33mExp\u001b[39m(e = \u001b[33mMinus\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", " )\n", " ),\n", " \u001b[33mWhileStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m)),\n", " stmts = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"y\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " ),\n", " \u001b[33mIfThenElseStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m)),\n", " stmtsThen = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " ),\n", " stmtsElse = \u001b[33mList\u001b[39m()\n", " )\n", " )\n", " )\n", ")\n", "\u001b[36mretExpr\u001b[39m: \u001b[32mMinus\u001b[39m = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", "\u001b[36mprogram\u001b[39m: \u001b[32mProgram\u001b[39m = \u001b[33mProgram\u001b[39m(\n", " decls = \u001b[33mList\u001b[39m(\n", " \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"x\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m5.0\u001b[39m)),\n", " \u001b[33mVarDecl\u001b[39m(identifier = \u001b[32m\"y\"\u001b[39m, rhsExpr = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m)),\n", " \u001b[33mVarDecl\u001b[39m(\n", " identifier = \u001b[32m\"z\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m25.0\u001b[39m),\n", " e2 = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " )\n", " ),\n", " stmts = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m),\n", " e2 = \u001b[33mPlus\u001b[39m(\n", " e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"z\"\u001b[39m),\n", " e2 = \u001b[33mExp\u001b[39m(e = \u001b[33mMinus\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", " )\n", " ),\n", " \u001b[33mWhileStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m15.0\u001b[39m)),\n", " stmts = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"y\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"y\"\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " ),\n", " \u001b[33mIfThenElseStmt\u001b[39m(\n", " cond = \u001b[33mLeq\u001b[39m(e1 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m), e2 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m)),\n", " stmtsThen = \u001b[33mList\u001b[39m(\n", " \u001b[33mAssignStmt\u001b[39m(\n", " identifier = \u001b[32m\"x\"\u001b[39m,\n", " rhsExpr = \u001b[33mMinus\u001b[39m(e1 = \u001b[33mConst\u001b[39m(d = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mIdent\u001b[39m(s = \u001b[32m\"x\"\u001b[39m))\n", " )\n", " ),\n", " stmtsElse = \u001b[33mList\u001b[39m()\n", "..." ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "val d1 = VarDecl(\"x\", Const(5.0f)) // var x = 5\n", "val d2 = VarDecl(\"y\", Const(15.0f)) // var y = 15\n", "val d3 = VarDecl(\"z\", Plus(Const(25.0f), Minus(Ident(\"y\"), Ident(\"x\")))) // var z = 25 + y - x\n", "val decls = List(d1, d2, d3)\n", "val e1 = Plus(Ident(\"y\"), Plus( Ident(\"z\"), Exp( Minus(Ident(\"x\"), Ident(\"y\")) ) )) // y + z + exp(x - y)\n", "val stmt1 = AssignStmt(\"x\", e1) // x = y + z + exp(x - y)\n", "// Let us make up the parts of the while statement\n", "val cond1 = Leq(Ident(\"y\"), Const(15.0f)) // y <= 15\n", "// The assignment inside the while\n", "val stmt2 = AssignStmt(\"y\", Minus(Ident(\"y\"), Ident(\"x\"))) // y = y - x\n", "// The condition for the if statement\n", "val cond2 = Leq(Ident(\"x\"), Const(0.0f)) // x <= 0.0\n", "val stmt3 = AssignStmt(\"x\", Minus(Const(0.0f), Ident(\"x\"))) // x= 0 - x\n", "val ifStmt = IfThenElseStmt(cond2, List(stmt3), List()) // if ( x <= 0) x = -x else nothing\n", "val whileStmt = WhileStmt(cond1, List(stmt2, ifStmt)) // while loop \n", "val allstmts = List(stmt1, whileStmt)\n", "val retExpr = Minus(Ident(\"y\"), Ident(\"x\")) // y - x to be returned\n", "val program = Program(decls, allstmts, retExpr )\n", "// This produces a big mess of symbols below but it is really how a computer sees the program you enter." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is much more informative to view the this program as a tree, making the connection between the original program and this tree much clearer.\n", "\n", "**TODO: Draw a tree for the program above**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Parsing: The Stuff we will not talk about." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We should now address an important gap that you may have already spotted. We write a program in our language\n", "as a text file \n", "\n", "~~~ \n", "var x = 5;\n", "var y = 15;\n", "var z = 25 + y - x;\n", "x = y + z + exp(x - y);\n", "while ( y <= 15) \n", " begin\n", " y = y - x ;\n", " if (x <= 0)\n", " begin\n", " x = -x; \n", " end\n", " end\n", "return (y - x)\n", "~~~ \n", "\n", "a) How is this related to the term representation below?\n", "\n", "\n", "~~~\n", "Program(List(VarDecl(x,Const(5.0)), VarDecl(y,Const(15.0)), VarDecl(z,Plus(Const(25.0),Minus(Ident(y),Ident(x))))),List(AssignStmt(x,Plus(Ident(y),Plus(Ident(z),Exp(Minus(Ident(x),Ident(y)))))), WhileStmt(Leq(Ident(y),Const(15.0)),List(AssignStmt(y,Minus(Ident(y),Ident(x))), IfThenElseStmt(Leq(Ident(x),Const(0.0)),List(AssignStmt(x,Minus(Const(0.0),Ident(x)))),List())))),Minus(Ident(y),Ident(x)))\n", "~~~\n", "\n", "\n", "b) How do we get from the text file to the Scala representation?\n", "\n", "\n", "The answers are simple: a) the Scala representation has all the essential information needed to reproduce the text of the same program upto some loss in spacing, comments, indentation and so on; b) the text file can be converted to the Scala representation and vice-versa by an algorithm called the _parser_. \n", "\n", "The parser takes in the human readable program text and produces the internal representation shown by the term. The term is often called the _abstract syntax tree_ of the program.\n", "\n", "Parsing requires to go in depth into context free grammars and a special type called LALR grammars. As such, it is the subject of a different class called __Compilers__ (CS453). We will not be focusing on building parsers in this class. Therefore, for the purposes of this class, we will assume there is a parser that can take a program as entered by the user and build an abstract syntax tree representation as shown here.\n", "\n" ] } ], "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 }