notebooks/Expressions_as_Classes_chapter.ipynb

{"nbformat": 4, "nbformat_minor": 0, "metadata": {"colab": {"name": "Expressions_as_Classes_chapter.ipynb", "provenance": [], "collapsed_sections": []}, "kernelspec": {"name": "python3", "display_name": "Python 3"}}, "cells": [{"cell_type": "markdown", "metadata": {"id": "yWPsbcfHnC66"}, "source": ["# Expressions as Classes\n", "\n", "Copyright Luca de Alfaro, 2019-21. \n", "License: [CC-BY-NC-ND](https://creativecommons.org/licenses/by-nc-nd/4.0/)."]}, {"cell_type": "markdown", "metadata": {"id": "672b91807e32439d", "colab_type": "text"}, "source": "\nPrepared on: Wed Sep 29 14:52:19 2021\n\nThis is a book chapter; it is not a homework assignment.  \nDo not submit it as a solution to a homework assignment; you would receive no credit.\n"}, {"cell_type": "markdown", "metadata": {"id": "pM46DjaZQ4u7"}, "source": ["We will now describe a more sophisticated representation for an expression, based on a hierarchy of classes.  First, let us give an example of what we want to do. \n", "\n", "We want to be able to create a variable simply like this: \n", "\n", "    x = V(value=3)\n", "\n", "This creates a variable with value 3, and assigns it to `x`.  We can change the value of a variable, via: \n", "\n", "    x.assign(4)\n", "\n", "Once we have variables, we want to create expressions using the usual notation: \n", "\n", "    e = x + 1\n", "\n", "should create an expression, and so should: \n", "\n", "    e = (x + 1) * 5\n", "\n", "Of course, we should be able to create multiple variables: \n", "\n", "    y = V(value=2)\n", "\n", "and mix them in expressions: \n", "\n", "    e = (x + 1) * y\n", "\n", "We also want to be able to evaluate expressions: \n", "\n", "    e.eval()\n", "\n", "and derivate expressions with respect to variables: \n", "\n", "    e.derivate(x)\n", "\n", "This is the goal. \n"]}, {"cell_type": "markdown", "metadata": {"id": "ae-mJ_IFy0i9"}, "source": ["To achieve our goal, we will create a hierarchy of classes. \n", "\n", "The class **Expr** is the generic class denoting an expression.  It is an _abstract_ class: only its subclasses will be instantiated.  The class hierarchy will be: \n", "\n", "`Expr`\n", "* `Plus`\n", "* `Minus`\n", "* `Multiply`\n", "* `Divide`\n", "* `Negative`\n", "* `V`, representing variables. \n", "\n", "Numerical constants will be just represented by numbers, and not by subclasses of `Expr`. \n", "\n", "## The `Expr` class\n", "\n", "The `Expr` class implements the various [methods used to emulate numerical types](https://docs.python.org/3/reference/datamodel.html?#emulating-numeric-types), such as `__add__`, `__sub__`, and so forth.  In this way, we can build an expression simply by writing\n", "\n", "    x = V()\n", "    e = x + 1\n", "\n", "In the above, `V()` creates a variable (an object of class `V`), and assigns it to `x`.  Then, \n", "\n", "    x + 1\n", "\n", "will call the `__add__` method of `Expr` with argument 1.  This will generates a `Plus` expression, with as children `x` and 1. \n", "\n", "In other words, the methods of `Expr`: \n", "\n", "* `__add__` and `__radd__` will generate `Plus` expressions; \n", "* `__sub__` and `__rsub__` will generate `Minus` expressions; \n", "\n", "and so forth. To make this work, we will define the [`__add__`](https://docs.python.org/3/reference/datamodel.html#object.__add__) method of `Expr` so that it produces a `Plus` object, with as children the two operands being added. \n", "\n", "Similarly, \n", "\n", "    x * 3 / 2\n", "\n", "will create an object of class `Divide`, with as left child the `Multiply` node for `x * 3`, and as right child, the number 2.  Thus, the [`__truediv__`](https://docs.python.org/3/reference/datamodel.html#object.__truediv__) method of `Expr` will create a `Divide` node. \n"]}, {"cell_type": "markdown", "metadata": {"id": "8EzJCNOBbbL-"}, "source": ["## Benefits of class-based representation \n", "\n", "Compared with the representation of expressions seen in the previous chapter, this class-based representation offers several advantages.  \n", "\n", "First, we can build expressions in a natural way as shown above, via the over-riding of the usual arithmetic operators.  \n", "\n", "Second, if we introduce a new operator, all we need is provide the implementation of the new operator: we do not need to modify the shared code that traverses the tree, and add one more case to a long case-analysis.  In other words, the code is far more modular.  This may seem a small point, but if one were to extend the representation of expressions to involve tensors (matrices) and operations on tensors, as is done in the symbolic representation of expressions used in machine-learning, the number of operators could easily grow to a hundred or more, making a modular approach the only reasonable one. \n", "\n", "Third, it becomes possible to attach methods to the expression objects, and as we will see in the next chapter, this can be very useful to implement machine learning frameworks.  But later about that. "]}, {"cell_type": "markdown", "metadata": {"id": "-Elx6LBjcKky"}, "source": ["## Defining an expression class\n", "\n", "We define an abstract class `Expr`, representing a generic expression.  This generic class has as subclasses the classes that represent the various operators, such as `Plus`, `Minus`, `Multiply`, as well as the variable class `V`.  Here is our basic implementation.  "]}, {"cell_type": "code", "metadata": {"id": "Fb58SLJwm649"}, "source": ["class Expr(object):\n", "    \"\"\"Abstract class representing expressions\"\"\"\n", "\n", "    name = \"expr\" # Not used, but just to define it.\n", "\n", "    def __init__(self, *args):\n", "        \"\"\"An object is created by passing to the constructor the children\"\"\"\n", "        self.children = args\n", "        self.value = None # The value of the expression\n", "        self.child_values = None # The values of the children; useful to have\n", "\n", "    def eval(self):\n", "        \"\"\"Evaluates the expression.\"\"\"\n", "        # First, we evaluate the children.\n", "        self.child_values = [c.eval() if isinstance(c, Expr) else c\n", "                             for c in self.children]\n", "        # Then, we evaluate the expression itself.\n", "        self.value = self.op(*self.child_values)\n", "        return self.value\n", "\n", "    def op(self):\n", "        \"\"\"This operator must be implemented in subclasses; it should\n", "        compute self.value from self.values, thus implementing the\n", "        operator at the expression node.\"\"\"\n", "        raise NotImplementedError()\n", "\n", "    def __repr__(self):\n", "        \"\"\"Represents the expression in a somewhat readable way.\"\"\"\n", "        if len(self.children) == 1:\n", "            # Unary operators\n", "            return \"({}{})\".format(self.__class__.name, self.children[0])\n", "        elif len(self.children) == 2:\n", "            return \"({} {} {})\".format(\n", "                self.children[0], self.__class__.name, self.children[1]\n", "            )\n", "        # Catch-all.\n", "        return \"{}({})\".format(self.__class__.__name__,\n", "                                ', '.join(repr(c) for c in self.children))\n", "\n", "    # Expression constructors\n", "\n", "    def __add__(self, other):\n", "        return Plus(self, other)\n", "\n", "    def __radd__(self, other):\n", "        return Plus(self, other)\n", "\n", "    def __sub__(self, other):\n", "        return Minus(self, other)\n", "\n", "    def __rsub__(self, other):\n", "        return Minus(other, self)\n", "\n", "    def __mul__(self, other):\n", "        return Multiply(self, other)\n", "\n", "    def __rmul__(self, other):\n", "        return Multiply(other, self)\n", "\n", "    def __truediv__(self, other):\n", "        return Divide(self, other)\n", "\n", "    def __rtruediv__(self, other):\n", "        return Divide(other, self)\n", "\n", "    def __neg__(self):\n", "        return Negative(self)\n"], "execution_count": 1, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "sxTM1NIFiPzn"}, "source": ["Variables are created specifying a name, and an initial value.  If nothing is specified, variables have random initial values.  You can assign a value to a variable using the `assign` method.  The `eval` method of a variable simply returns its value. "]}, {"cell_type": "code", "metadata": {"id": "CCe9Unc_xut7"}, "source": ["import random\n", "import string\n", "\n", "class V(Expr):\n", "    \"\"\"Variable.\"\"\"\n", "\n", "    def __init__(self, value=None):\n", "        super().__init__()\n", "        self.children = []\n", "        self.value = random.gauss(0, 1) if value is None else value\n", "        self.name = ''.join(\n", "            random.choices(string.ascii_letters, k=4))\n", "\n", "    def eval(self):\n", "        return self.value\n", "\n", "    def assign(self, value):\n", "        self.value = value\n", "\n", "    def __repr__(self):\n", "        return \"V({}, value={})\".format(self.name, self.value)\n"], "execution_count": 2, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "L2wCL8Tri_Do"}, "source": ["Here are the constructors for the other operators; for them, we just need to provide an implementation for `op`, since all the rest is inherited from `Expr`.  We actually also define a name, as a class attribute, that we use in the representation method."]}, {"cell_type": "code", "metadata": {"id": "2qX-ifoniOhb"}, "source": ["class Plus(Expr):\n", "    name = \"+\"\n", "    def op(self, x, y):\n", "        return x + y\n", "\n", "class Minus(Expr):\n", "    name = \"-\"\n", "    def op(self, x, y):\n", "        return x - y\n", "\n", "class Multiply(Expr):\n", "    name = \"*\"\n", "    def op(self, x, y):\n", "        return x * y\n", "\n", "class Divide(Expr):\n", "    name = \"/\"\n", "    def op(self, x, y):\n", "        return x / y\n", "\n", "class Negative(Expr):\n", "    name = \"-\"\n", "    def op(self, x):\n", "        return -x\n"], "execution_count": 3, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "nKXX5211nC8i"}, "source": ["We can build and evaluate expressions quite simply."]}, {"cell_type": "code", "metadata": {"id": "UICuOHDkkeQo"}, "source": ["e = V(2) + 3\n", "print(e)\n", "print(e.eval())\n"], "execution_count": 4, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["(V(mrQd, value=2) + 3)\n", "5\n"]}]}, {"cell_type": "code", "metadata": {"id": "XbLPMBvSwTR2"}, "source": ["e = (V() + V(2)) * (2 + V(1))\n", "print(e)\n", "print(e.eval())\n"], "execution_count": 5, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["((V(nWYb, value=0.7655535337259683) + V(kHCv, value=2)) * (V(RrtO, value=1) + 2))\n", "8.296660601177905\n"]}]}, {"cell_type": "markdown", "metadata": {"id": "Vxoyr5x6g3IW"}, "source": ["If we want to be able to assign values to variables, or refer to them in our code later, we need to assign our variable objects to Python variables: "]}, {"cell_type": "code", "metadata": {"id": "zFoRNWM-hAN8"}, "source": ["x = V()\n", "y = V()\n", "e = x + y\n", "\n", "print(e.eval()) # This uses the initial random values.\n", "\n", "x.assign(2)\n", "y.assign(3)\n", "print(e.eval())\n"], "execution_count": 6, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["-0.08674300760895848\n", "5\n"]}]}, {"cell_type": "markdown", "metadata": {"id": "MYLJcyJw5OpJ"}, "source": ["### Defining Expression Equality"]}, {"cell_type": "markdown", "metadata": {"id": "C_XASNjw6UHa"}, "source": ["If we test equality between expressions, we are in for a surprise."]}, {"cell_type": "code", "metadata": {"id": "Mfk7LXik6hcQ"}, "source": ["x = V()\n", "e1 = x + 4\n", "e2 = x + 4\n", "e1 == e2\n"], "execution_count": 7, "outputs": [{"output_type": "execute_result", "data": {"text/plain": ["False"]}, "metadata": {}, "execution_count": 7}]}, {"cell_type": "markdown", "metadata": {"id": "OFsFrqTb6inQ"}, "source": ["Why is the result False? \n", "\n", "Python knows how to compare objects that belong to its own types.  So you can do comparisons between strings, numbers, tuples, and more, and it all works as expected.  This is why we could check equality of expressions represented as trees: those expression trees are composed entirely of standard Python types, namely, strings, numbers, and tuples. \n", "\n", "However, `Expr`, `V`, etc, are classes we defined, and Python has no idea of what it means for objects of user-defined classes to be equal.  \n", "In this case, Python defaults to considering equal two objects if they are the _same_ object. \n", "The two expressions _e1_ and _e2_ above are not the same object: they are two distinct objects, which just happen to represent the same expression. \n", "\n", "If we want to have a notion of expression equality that represents our idea that \"two expression objects are equal if they represent the same expression\", we need to define equality ourselves. \n", "This can be easily done, by defining an _ _ eq _ _ method.  This method [has the form](https://docs.python.org/3/reference/datamodel.html#object.__eq__):\n", "\n", "    def __eq__(self, other):\n", "        ...\n", "        return <True/False>\n", "        \n", "Here, self is the object on which the method is called, and other is another object -- any other object.  Our job is to define when the object self is equal to the object other.  This can be easily done; using again our way of adding methods to existing classes, we write:"]}, {"cell_type": "code", "metadata": {"id": "wwJQq10g5UuT"}, "source": ["def expr_eq(self, other):\n", "    if isinstance(other, Expr):\n", "        # The operators have to be the same\n", "        if self.__class__ != other.__class__:\n", "            return False\n", "        # and their corresponding children need to be equal\n", "        if len(self.children) != len(other.children):\n", "            return False\n", "        for c1, c2 in zip(self.children, other.children):\n", "            if c1 != c2: return False\n", "        return True\n", "    else:\n", "        return False\n", "\n", "Expr.__eq__ = expr_eq\n"], "execution_count": 8, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "SN5W_KEQip-C"}, "source": ["If we did not define equality for variables, two variables would be considered equal according to `Expr.__eq__`, since `V` is a subclass of `Expr`.  This would yield non-intended consequences (all variables would be considered equal).\n", "\n", "Thus, we define equality for variables to be the basic equality for objects: two variables are equal iff they are the same object.  In the definition below, `object.__eq__` is this primitive notion of equality, defined over the class `object` of Python, which is the base class for all classes. \n"]}, {"cell_type": "code", "metadata": {"id": "MLAWdunvkCsL"}, "source": ["V.__eq__  = object.__eq__\n"], "execution_count": 9, "outputs": []}, {"cell_type": "code", "metadata": {"id": "F5vqB_INkLcq"}, "source": ["x = V()\n", "y = V()\n", "z = x\n", "print(x == y)\n", "print(x == z)\n"], "execution_count": 10, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["False\n", "True\n"]}]}, {"cell_type": "markdown", "metadata": {"id": "mGnoXqG89RNj"}, "source": ["Once expression equality is thus defined, we get the expected result when we compare expressions:"]}, {"cell_type": "code", "metadata": {"id": "HvzllR-S6Ei_"}, "source": ["x = V()\n", "e1 = x + 4\n", "e2 = x + 4\n", "e1 == e2\n"], "execution_count": 11, "outputs": [{"output_type": "execute_result", "data": {"text/plain": ["True"]}, "metadata": {}, "execution_count": 11}]}, {"cell_type": "markdown", "metadata": {"id": "3f_lWOn78vG_"}, "source": ["Having to define equality \"by hand\" is very pedantic, but it does give us the flexibility of defining precisely what it means for two expressions to be equal."]}, {"cell_type": "markdown", "metadata": {"id": "d5wim01MlBAo"}, "source": ["## Variable Occurrence\n", "\n", "Let us define occurrence of a variable in an expression, so that for an expression `e` and a variable `x` we can ask \n", "\n", "    x in e\n", "\n", "and get a True/False answer.  To do this, we need to define the `__contains__` methods of expressions.  First we define it for a variable: of course, a variable occurs in itself only if the variable is the same as the one whose occurrence we are checking."]}, {"cell_type": "code", "metadata": {"id": "Hprnupy0mW3n"}, "source": ["# Variable occurrence in a variable\n", "\n", "def v_contains(self, var):\n", "    \"\"\"Returns True of var is the same as self, and False otherwise.\"\"\"\n", "    return self == var\n", "\n", "V.__contains__ = v_contains\n"], "execution_count": 12, "outputs": []}, {"cell_type": "code", "metadata": {"id": "FFtCTw0Tnz46"}, "source": ["x = V()\n", "y = V()\n", "print(x in x)\n", "print(x in y)\n"], "execution_count": 13, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["True\n", "False\n"]}]}, {"cell_type": "markdown", "metadata": {"id": "VSR1LLLKoV5M"}, "source": ["Once we define occurrence of a variable in a variable, we can define occurrence in a variable in a general expression. Of course, a variable appears in an expression if it appears in some of its children.  "]}, {"cell_type": "code", "metadata": {"id": "P_Qx0JNcqRF_"}, "source": ["# Occurrence of a variable in an expression\n", "\n", "def expr_contains(self, var):\n", "    return any([var in c for c in self.children if isinstance(c, Expr)])\n", "\n", "Expr.__contains__ = expr_contains\n"], "execution_count": 14, "outputs": []}, {"cell_type": "code", "metadata": {"id": "ldAQWojlqpvJ"}, "source": ["x = V()\n", "y = V()\n", "z = V()\n", "e = x + (2 * y)\n", "\n", "print(x in e)\n", "print(y in e)\n", "print(z in e)\n"], "execution_count": 15, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["True\n", "True\n", "False\n"]}]}, {"cell_type": "code", "metadata": {"id": "-rF3N98-q7mQ"}, "source": ["x = V()\n", "y = V()\n", "z = V()\n", "e = x + (2 * y)\n", "\n", "print(x in e)\n", "print(y in e)\n", "print(z in e)\n"], "execution_count": 16, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["True\n", "True\n", "False\n"]}]}, {"cell_type": "markdown", "metadata": {"id": "ObNxYfdwsEpG"}, "source": ["## Variable Replacement\n", "\n", "Another fun thing we can do is replace a variable with an expression.  Suppose you define an expression: \n", "\n", "    x = V()\n", "    y = V()\n", "    e = (x + 1) * (y + 1)\n", "\n", "Suppose you also have another expression: \n", "\n", "    z = V()\n", "    f = y + z\n", "\n", "Then, you can replace all occurrences of variable `x` in `e` with expression `f`: \n", "\n", "    new_e = e.replace(x, f)\n", "\n", "and `new_e` should be then equal to: \n", "\n", "    ((x + z) + 1) * (y + 1)\n", "\n", "Let us implement variable substitution.  Let us begin by defining variable substitution for variables. "]}, {"cell_type": "code", "metadata": {"id": "7F2LHglCs67_"}, "source": ["### Variable replacement in variables\n", "\n", "def v_replace(self, x, e):\n", "    \"\"\"If self is x, replaces all occurrences of x with e.\"\"\"\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "V.replace = v_replace\n"], "execution_count": 17, "outputs": []}, {"cell_type": "code", "metadata": {"id": "dObUjQUQvkeZ"}, "source": ["x = V()\n", "y = V()\n", "z = V()\n", "print(x == x.replace(x, x))\n", "print(y == x.replace(x, y))\n", "print(x == x.replace(y, z))\n"], "execution_count": 18, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["True\n", "True\n", "True\n"]}]}, {"cell_type": "code", "metadata": {"id": "OlDuGEdxwACw", "cellView": "form"}, "source": ["# @title Tests for variable replacement in variables.\n", "x = V()\n", "y = V()\n", "z = V()\n", "assert x == x.replace(x, x)\n", "assert y == x.replace(x, y)\n", "assert x == x.replace(y, z)\n", "assert x.replace(x, y).replace(y, z) == z\n", "\n"], "execution_count": 19, "outputs": []}, {"cell_type": "code", "metadata": {"id": "h2sHjxkgxPba", "cellView": "form"}, "source": ["# @title Other tests for variable replacement.\n", "\n", "x = V()\n", "y = V()\n", "\n", "e = x.replace(x, y + 3 * x)\n", "\n", "x.assign(2)\n", "y.assign(3)\n", "assert e.eval() == 9\n", "\n"], "execution_count": 20, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "HBdMHTwGsEbv"}, "source": ["We now define variable replacement for expressions. Consider a simple expression:"]}, {"cell_type": "code", "metadata": {"id": "d6bgF-TXwvr7"}, "source": ["x = V()\n", "y = V()\n", "z = V()\n", "e = x + y\n"], "execution_count": 21, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "IvuXcrRww1B7"}, "source": ["Suppose we want to return `e.replace(x, z)`.  The idea is: \n", "\n", "* carry out the replacement for each child (via a recursive call, as usual),  \n", "* then return an expression built out of the replacements. \n", "\n", "For instance, consider `e = x + y`.  To compute \n", "\n", "    e.replace(x, z)\n", "\n", "we first replace `x` with `z`, and then we return `Plus(z, y)`. \n", "\n", "The problem is exactly in the last sentence.  A `Plus` object, after carrying out the replacement in the children, should return a `Plus` object with the new children.  Similarly, a `Minus` object should return a `Minus` object, a `Multiply` object should return a `Multiply` object, and so forth.  If we implement this in the straightforward way, we need to add a `replace` method to all of these classes, so that they can return an object of the appropriate type.   This is a lot of work. \n", "\n", "Is there a better way?  It turns out, yes.  In an object, \n", "\n", "    self.__class__\n", "\n", "is the class of the object.  So if you want to return a new object of the same class, created say with arguments `x` and `y`, all you need to do is: \n", "\n", "    self.__class__(x, y)\n", "\n", "In this way, if you are in a `Plus` object, `self.__class__` is `Plus`, and everything works. \n", "Using this idea, we, that is, you, can implement the replacement method directly for the `Expr` class. \n", "\n"]}, {"cell_type": "code", "metadata": {"id": "eavp1lD0w0jX"}, "source": ["### Replacement for expressions\n", "\n", "def expr_replace(self, x, e):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "Expr.replace = expr_replace\n"], "execution_count": 22, "outputs": []}, {"cell_type": "code", "metadata": {"id": "RBR5WRsp6bwu", "cellView": "form"}, "source": ["# @title Tests for expression replacement\n", "\n", "x = V()\n", "y = V()\n", "z = V()\n", "\n", "e = (1 + x) * (1 + y)\n", "f = e.replace(x, x + z)\n", "assert f == (1 + (x + z)) * (1 + y)\n", "\n", "x.assign(1)\n", "y.assign(2)\n", "z.assign(3)\n", "assert e.eval() == 6\n", "assert f.eval() == 15\n", "\n", "e = (x + y) / (x - y)\n", "f = e.replace(x, 2 * x).replace(y, 3 * y)\n", "assert f.eval() == (2 + 6) / (2 - 6)\n", "\n"], "execution_count": 23, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "kg60qkeg-u48"}, "source": ["\n", "## Expression Derivation\n", "\n", "We will develop here a method `derivate` such that, for an expression `e`, the method call `e.derivate(x)` returns the derivative of the expression with respect to the variable `x`.  As in the previous chapter, we use the following derivation formulas: \n", "\n", "* For a constant $c$, $\\partial c / \\partial x = 0$.\n", "* For a variable $y \\neq x$,  $\\partial y / \\partial x = 0$.\n", "* $\\partial x / \\partial x = 1$.\n", "\n", "For operators, we can use:\n", "\n", "$$\n", " \\begin{align*}\n", " \\frac{\\partial}{\\partial x}(f \\pm g) & = \\frac{\\partial f}{\\partial x} \\pm \\frac  {\\partial g}{\\partial x}, \\\\[1ex]\n", " \\frac{\\partial}{\\partial x}(f \\cdot g) & = \\frac{\\partial f}{\\partial x} \\cdot g + f \\cdot \\frac{\\partial g}{\\partial x}, \\\\[1ex]\n", " \\frac{\\partial}{\\partial x}\\left(\\frac{f}{g}\\right) & = \\frac{\\frac\n", "  {\\partial f}{\\partial x} \\cdot g - f \\cdot \\frac{\\partial g}{\\partial x}}{g^2}. \n", "\\end{align*}\n", "$$\n", "\n", "Let us begin with implementing derivation for variables. \n"]}, {"cell_type": "code", "metadata": {"id": "8d_hxl5e-PF4"}, "source": ["### Derivation of variables\n", "\n", "def v_derivate(self, x):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "V.derivate = v_derivate\n"], "execution_count": 24, "outputs": []}, {"cell_type": "code", "metadata": {"id": "JKF2mgHjAFFf"}, "source": ["x = V()\n", "y = V()\n", "print(x.derivate(x))\n", "print(x.derivate(y))\n"], "execution_count": 25, "outputs": [{"output_type": "stream", "name": "stdout", "text": ["1\n", "0\n"]}]}, {"cell_type": "code", "metadata": {"id": "fpwuZVCFAMMh"}, "source": ["## Tests for variable derivation\n", "\n", "x = V()\n", "y = V()\n", "assert x.derivate(x) == 1\n", "assert x.derivate(y) == 0\n", "\n"], "execution_count": 26, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "ByOnggtMAZ53"}, "source": ["### Derivation for expressions\n", "\n", "This time, there is no clever trick to implement `derivate` as a method of `Expr`, because the derivative behaves in a different way for the different operators.  Hence, we will need to implement `derivate` for each individual operator.  We let you do it.  There are two things to be careful about: \n", "\n", "* Children of an operator may not be expressions; they can also be constants such as 2.3 or 4.1.\n", "* If the _new_ children of an expression are all numbers, return the numerical result of the expression rather than a symbolic expression.  For example, do not return `Plus(1, 0)`; rather, just return `1`.  Note that, if you put the derivatives of the two children in, say, `df` and `dg`, you can simplify automatically by returning `df + dg`, which will return an expression if one of `df` or `dg` is an expression, and a number otherwise. \n", "\n", "We give you the solution for `Plus`, mainly because it might be difficult to believe that the solution is this simple. "]}, {"cell_type": "code", "metadata": {"id": "A_lKdxMghE4W"}, "source": ["from numbers import Number\n", "\n", "def plus_derivate(self, x):\n", "    f, g = self.children\n", "    df = f.derivate(x) if isinstance(f, Expr) else 0\n", "    dg = g.derivate(x) if isinstance(g, Expr) else 0\n", "    return df + dg\n", "\n", "Plus.derivate = plus_derivate\n"], "execution_count": 27, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "Y-LUJiJBhZXn"}, "source": ["You can now work out the case for Minus, which is very similar. "]}, {"cell_type": "code", "metadata": {"id": "tUhIoNCoA2D0"}, "source": ["### Derivative of Minus\n", "\n", "def minus_derivate(self, x):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "Minus.derivate = minus_derivate\n"], "execution_count": 28, "outputs": []}, {"cell_type": "code", "metadata": {"id": "DUtdcqwIBf1F", "cellView": "form"}, "source": ["# @title Tests for derivatives of Plus and Minus\n", "\n", "x = V()\n", "y = V()\n", "z = V()\n", "\n", "e = x + y\n", "assert e.derivate(x) == 1\n", "f = x - y\n", "assert f.derivate(x) == 1\n", "assert f.derivate(y) == -1\n", "\n", "h = e + f\n", "assert h.derivate(x) == 2\n", "\n", "u = x + 4\n", "assert u.derivate(x) == 1\n", "v = 3 - y\n", "assert v.derivate(x) == 0\n", "assert v.derivate(y) == -1\n", "\n"], "execution_count": 29, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "yVXlFhiGDs2g"}, "source": ["Since we are at it, let us take care of unary minus, or `Negative`. "]}, {"cell_type": "code", "metadata": {"id": "pmhMocJ-BtIP"}, "source": ["### Derivative of Negative\n", "\n", "def negative_derivate(self, x):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "Negative.derivate = negative_derivate\n"], "execution_count": 30, "outputs": []}, {"cell_type": "code", "metadata": {"id": "cWL6Q2-FE5Th", "cellView": "form"}, "source": ["# @title Tests for negative.\n", "\n", "x = V()\n", "y = V()\n", "e = -x\n", "assert e.derivate(x) == -1\n", "assert e.derivate(y) == 0\n", "\n", "\n"], "execution_count": 31, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "JJ8iMyT5FIzG"}, "source": ["Now for multiplication and divisions.  Be careful to use the formulas exactly as given, otherwise the result may not match.  E.g. use \n", "\n", "$$\n", "\\frac{\\partial}{\\partial x}(f \\cdot g) = \\frac{\\partial f}{\\partial x} \\cdot g + f \\cdot \\frac{\\partial g}{\\partial x}\n", "$$\n", "\n", "and _not_, for instance, $\\frac{\\partial}{\\partial x}(f \\cdot g) = g \\cdot \\frac{\\partial f}{\\partial x} + f \\cdot \\frac{\\partial g}{\\partial x}$ (note the swap of the factors in the first term).\n", "\n", "We would like you to return simplified expressions.  You can again use the trick that, if you have two expressions `df` and `g` (or similar), then `df * g` will be an expression if one of `df` and `g` are expressions, and a number if both `df` and `g` are numbers. "]}, {"cell_type": "code", "metadata": {"id": "gO0Yy0NEFEJy"}, "source": ["### Derivative of multiplication.\n", "\n", "def multiply_derivate(self, x):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "Multiply.derivate = multiply_derivate\n"], "execution_count": 32, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "fvaj48ZwO73t"}, "source": ["If you did the above right, it will be 4-5 lines wrong.  If you wrote much more than that, please think at it again.  The solution is quite simple; you can just trust that the operators `*` and `+` will build it. "]}, {"cell_type": "code", "metadata": {"id": "ys3gwfUTLoph", "cellView": "form"}, "source": ["# @title Tests for derivative of multiplication.\n", "\n", "x = V()\n", "y = V(value=2)\n", "\n", "e = x * y\n", "# This is ugly.  It is.  We have not implemented 0, 1 simplifications.\n", "assert e.derivate(x) == 1 * y + x * 0\n", "\n", "# To remedy ugliness, we now test numerically.\n", "f = x * x\n", "x.assign(3)\n", "assert f.derivate(x).eval() == 6\n", "x.assign(4)\n", "assert f.derivate(x).eval() == 8\n", "\n", "h = 3 * x\n", "assert h.derivate(x).eval() == 3\n", "u = x * 3\n", "assert u.derivate(x).eval() == 3\n", "\n"], "execution_count": 33, "outputs": []}, {"cell_type": "markdown", "metadata": {"id": "_wOFiKXuPdRx"}, "source": ["For division, the expression is: \n", "\n", "$$\n", " \\frac{\\partial}{\\partial x}\\left(\\frac{f}{g}\\right) = \\frac{\\frac\n", "  {\\partial f}{\\partial x} \\cdot g - f \\cdot \\frac{\\partial g}{\\partial x}}{g^2}. \n", "$$\n", "\n", "Note that you can obtain the denominator just by doing `g * g`, if `g` is the second child.  Again, the correct solution is quite short. "]}, {"cell_type": "code", "metadata": {"id": "S05hj9IzLzVP"}, "source": ["### Derivative of division\n", "\n", "def divide_derivate(self, x):\n", "    ### BEGIN SOLUTION\n", "    raise NotImplementedError()\n", "    ### END SOLUTION\n", "\n", "Divide.derivate = divide_derivate\n"], "execution_count": 34, "outputs": []}, {"cell_type": "code", "metadata": {"id": "VlGmfr9Nh26n"}, "source": ["x = V()\n", "y = V()\n", "e = x / 2\n", "f = e.derivate(x)\n", "x.assign(3)\n", "assert f.eval() == 1/2\n", "\n", "g = 1 / x\n", "assert g.derivate(x).eval() == - 1 / 9\n", "assert g.derivate(y).eval() == 0\n", "\n"], "execution_count": 35, "outputs": []}, {"cell_type": "code", "metadata": {"id": "KNxI8PtWoyhL"}, "source": ["x = V(value=2)\n", "y = V(value=3)\n", "\n", "f = (x + 1) * (y + 1) / (x - 1) * (y - 1)\n", "df = f.derivate(x)\n", "\n", "assert df.eval() == -16\n", "\n", "x.assign(0.5)\n", "y.assign(0.5)\n", "assert df.eval() == 6\n", "\n"], "execution_count": 36, "outputs": []}, {"cell_type": "code", "metadata": {"id": "CWvmuAXVqDnS"}, "source": ["x = V(value=0)\n", "\n", "f = (3 * x * x + 2 * x + 4) / (5 * x * x - 7 * x + 12)\n", "\n", "df = f.derivate(x)\n", "assert abs(df.eval() - 0.3611) < 0.01\n", "x.assign(1)\n", "assert df.eval() == 0.53\n", "x.assign(1000)\n", "assert abs(df.eval()) < 0.001\n", "x.assign(-0.5)\n", "assert abs(df.eval() - 0.1) < 0.01\n", "\n"], "execution_count": 37, "outputs": []}]}