{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ef88843b66adc91569384659597bfa0d",
     "grade": false,
     "grade_id": "cell-3f061ea27f528fcf",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Part 3: Reverse Mode Automatic Differentiation\n",
    "\n",
    "Dynamic Reverse mode AD can be implemented by declaring a class to represent a value and the child expressions that the value depends on. We've provided the implementation that was shown in the lecture slides as a basis below, but it's missing some parts that will make it useful.\n",
    "\n",
    "__Tasks:__\n",
    "\n",
    "- Addition (`__add__`) is incomplete - can you finish it? \n",
    "- Can you also implement division (`__truediv__`), subtraction (`__sub__`) and power (`__pow__`)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2644b153f82b6e872e63cb5ead2d529f",
     "grade": false,
     "grade_id": "cell-b23d219550cd2934",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class Var:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.children = []\n",
    "        self.grad_value = None\n",
    "\n",
    "    def grad(self):\n",
    "        if self.grad_value is None:\n",
    "            self.grad_value = sum(weight * var.grad()\n",
    "                                  for weight, var in self.children)\n",
    "        return self.grad_value\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self.value)\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        z = Var(self.value * other.value)\n",
    "        self.children.append((other.value, z))\n",
    "        other.children.append((self.value, z))\n",
    "        return z\n",
    "\n",
    "    def __add__(self, other):\n",
    "        #TODO: finish me\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "\n",
    "    # TODO: add missing methods\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "afce3f80a9f8278e0ea2815a23a09c95",
     "grade": true,
     "grade_id": "cell-d2124fb6ca76110f",
     "locked": true,
     "points": 2,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Tests\n",
    "\n",
    "Var(1) + Var(1) / Var(1) - Var(1)**Var(1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "136e5e779ef4c951e75380a1554d1543",
     "grade": false,
     "grade_id": "cell-7a8d45cf51fc131f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Implementing math functions\n",
    "\n",
    "Just like when we were looking at Forward Mode AD, we also need to implement some core math functions. Here's the sine function for a `Var`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "53148f99532fa882690bcced1654894b",
     "grade": false,
     "grade_id": "cell-1a2d833d58b9a2ec",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def sin(x):\n",
    "    z = Var(math.sin(x.value))\n",
    "    x.children.append((math.cos(x.value), z))\n",
    "    return z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f733095db7ef9f78d62daf4d675492d3",
     "grade": false,
     "grade_id": "cell-71185787c3ab6312",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "__Task:__ can you implement the _cosine_ (`cos`), _tangent_ (`tan`), and _exponential_ (`exp`) functions in the code block below?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "6421b25426b2b125fa6de8358a1e1475",
     "grade": false,
     "grade_id": "cell-29e8985bf1eae001",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# TODO: implement additional math functions on Var instances\n",
    "\n",
    "def cos(x):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "\n",
    "def tan(x):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "\n",
    "def exp(x):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "70274a378e4b56b0b6dc2147ee44cb3d",
     "grade": true,
     "grade_id": "cell-0ed03787817557e8",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Tests\n",
    "assert cos(Var(0)).value == 1\n",
    "assert tan(Var(0)).value == 0\n",
    "assert exp(Var(0)).value == 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Time to try it out\n",
    "\n",
    "We're now in a position to try our implementation.\n",
    "\n",
    "__Tasks:__ \n",
    "\n",
    "- Try running the following code to compute the value of the function $z=x\\cdot y+sin(x)$ given $x=0.5$ and $y=4.2$, together with the derivative $\\partial z/\\partial x$ at that point. \n",
    "- Verify that the result is correct by hand-differentiating the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Var(0.5)\n",
    "y = Var(4.2)\n",
    "z = x * y + sin(x)\n",
    "print('z:', z)\n",
    "\n",
    "z.grad_value = 1.0 #Note that we have to 'seed' the gradient of z to 1 (e.g. ∂z/∂z=1) before computing grads\n",
    "print('∂z/∂x:',x.grad())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task:__ Now use the code block below to compute the derivative $\\partial z/\\partial y$ of the above expression (at the same point $x=0.5, y=4.2$ as above). Store the resultant gradient in the variable `dzdy`. Verify by hand that the result is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4e1272f80f811e792100c3fd78b912f0",
     "grade": false,
     "grade_id": "cell-ab12803572df9248",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "\n",
    "print('∂z/∂y:', dzdy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f9dd2f1466c7bcbd950c8a25d9af7a00",
     "grade": true,
     "grade_id": "cell-6b295b43c928fc86",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert dzdy\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Differentiating Algorithms\n",
    "\n",
    "Now, let's look at doing something wacky: differentiate an algorithm. For this example, we'll use an algorithm that is in a sense static (in this particular case the upper limit of the for loop is predetermined). However, it is not difficult to see that AD is much more general, and could even be applied to stochastic algorithms (say if we replaced the upper limit of the loop below with `Math.floor(Math.random() * 10)` for example).\n",
    "\n",
    "__Task:__ Consider the following algorithm and in the box below it manually compute the value of $z$ and the gradient $\\partial z/\\partial x$ at the end of execution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Var(0.5)\n",
    "z = Var(1)\n",
    "for i in range(0,2):\n",
    "    z = (z + Var(i)) * x * x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "a5058b059e97e150c869316d58034822",
     "grade": true,
     "grade_id": "cell-b0d4a79348257124",
     "locked": false,
     "points": 4,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task__: Now use the code block below to print out the gradient computed by our reverse AD by storing the result in a variable called `grad`. Does it match?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "26e9bd08a28f421e4dc79eebe8e028e8",
     "grade": false,
     "grade_id": "cell-d177505b72fe0811",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "\n",
    "print(grad)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c6ad226117e30b08f0fdf48b929029e7",
     "grade": true,
     "grade_id": "cell-e87a4e1621ed1d18",
     "locked": true,
     "points": 2,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Tests\n",
    "assert grad\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Task:__ Finally, use the code block below to experiment and test the other math functions and methods you created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "59055cd24350e996850ec1b2aa532ea6",
     "grade": true,
     "grade_id": "cell-bf3e00ed03ace059",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}