{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e98ccbc6",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_09_the_engine.ipynb)\n\n",
    "# Lab 9: The Engine\n",
    "\n",
    "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "946034e2",
   "metadata": {},
   "source": [
    "*The capstone. You build backpropagation from nothing — sixty lines — verify it against the calculus by hand and against finite differences by machine, then train a tiny model end to end with your own engine to prove it is real. Then numpy arrives as the scale instrument, the name model trains until it speaks, and the parrot exam from Chapter 8 returns with teeth: you watch the training loss fall while the held-out loss begins to climb, and you name the moment they part. Everything in nine chapters has been parts on a workbench. This is the build.*\n",
    "\n",
    "## 1. The number that remembers\n",
    "\n",
    "A plain number forgets its history. Build one that doesn't — the `Value`, learned in pieces. Start with the skeleton and the two core operations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5428b71",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math, random\n",
    "\n",
    "class Value:\n",
    "    def __init__(self, data, parents=()):\n",
    "        self.data = data\n",
    "        self.grad = 0.0\n",
    "        self._parents = set(parents)\n",
    "        self._backward = lambda: None\n",
    "\n",
    "    def __add__(self, other):\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        out = Value(self.data + other.data, (self, other))\n",
    "        def _backward():\n",
    "            self.grad += out.grad\n",
    "            other.grad += out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        out = Value(self.data * other.data, (self, other))\n",
    "        def _backward():\n",
    "            self.grad += other.data * out.grad\n",
    "            other.grad += self.data * out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "a = Value(2.0)\n",
    "b = Value(-3.0)\n",
    "c = a * b\n",
    "print(c.data, c._parents)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15499ebf",
   "metadata": {},
   "source": [
    "`Value(2.0)` builds a number-that-remembers; `c = a * b` builds a *new* one that remembers a and b as parents. The `isinstance` guard lets you write `a + 1` (it wraps the bare `1` into a Value). Each operation's `_backward` is a tiny function holding that operation's *derivative* — addition passes blame whole, multiplication scales it by the other factor. Confirm `c` knows its parents before moving on.\n",
    "\n",
    "## 2. The backward sweep\n",
    "\n",
    "History recorded forward; now price it backward. The sweep is Chapter 5's depth-first traversal, walked in reverse:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5135a6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "    def backward(self):\n",
    "        order = []\n",
    "        visited = set()\n",
    "        def build(v):\n",
    "            if v not in visited:\n",
    "                visited.add(v)\n",
    "                for parent in v._parents:\n",
    "                    build(parent)\n",
    "                order.append(v)\n",
    "        build(self)\n",
    "        self.grad = 1.0\n",
    "        for v in reversed(order):\n",
    "            v._backward()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27161ceb",
   "metadata": {},
   "source": [
    "Add this method inside the `Value` class (same indentation as `__add__`). Then the moment of truth — build a small expression, sweep, and check against calculus you can do by hand:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3aae7ccc",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = Value(2.0)\n",
    "b = Value(-3.0)\n",
    "c = Value(7.0)\n",
    "L = (a * b + c) * (a * b + c)        # L = (ab + c)^2\n",
    "L.backward()\n",
    "print(\"L    =\", L.data, \"  (expect 1)\")\n",
    "print(\"a.grad =\", a.grad, \"  (expect -6)\")\n",
    "print(\"b.grad =\", b.grad, \"  (expect  4)\")\n",
    "print(\"c.grad =\", c.grad, \"  (expect  2)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8abd5ea",
   "metadata": {},
   "source": [
    "By hand: ab + c = 1, so L = 1; the outer square contributes 2·(ab+c) = 2; then ∂L/∂a = 2·b = −6, ∂L/∂b = 2·a = 4, ∂L/∂c = 2. The engine should agree exactly. It does — and you have just watched blame flow from one number out to three, through a graph the computation recorded itself.\n",
    "\n",
    "## 3. More operations, tested against reality\n",
    "\n",
    "The model needs squashing and probabilities. Add these inside the class, each three lines, each just its derivative:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "315aff4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "    def __pow__(self, p):\n",
    "        out = Value(self.data ** p, (self,))\n",
    "        def _backward():\n",
    "            self.grad += p * (self.data ** (p - 1)) * out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "    def tanh(self):\n",
    "        t = math.tanh(self.data)\n",
    "        out = Value(t, (self,))\n",
    "        def _backward():\n",
    "            self.grad += (1 - t * t) * out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "    def exp(self):\n",
    "        e = math.exp(self.data)\n",
    "        out = Value(e, (self,))\n",
    "        def _backward():\n",
    "            self.grad += e * out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "    def log(self):\n",
    "        out = Value(math.log(self.data), (self,))\n",
    "        def _backward():\n",
    "            self.grad += (1 / self.data) * out.grad\n",
    "        out._backward = _backward\n",
    "        return out\n",
    "\n",
    "    def __truediv__(self, other):\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        return self * other ** -1\n",
    "\n",
    "    def __neg__(self): return self * -1\n",
    "    def __sub__(self, other):\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        return self + (-other)\n",
    "    def __radd__(self, other): return self + other\n",
    "    def __rmul__(self, other): return self * other"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c486c2d6",
   "metadata": {},
   "source": [
    "Now verify the *whole engine* the way professionals verify gradients: against **finite differences**. Calculus says the derivative is the limit of (f(x+h) − f(x−h)) / 2h; compute that numerically and check the engine matches:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e7934925",
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(av, bv, cv):\n",
    "    return (math.tanh(av * bv) + cv ** 2) * (av + cv)\n",
    "\n",
    "a = Value(0.5); b = Value(1.3); c = Value(-0.7)\n",
    "out = ((a * b).tanh() + c ** 2) * (a + c)\n",
    "out.backward()\n",
    "\n",
    "h = 1e-6\n",
    "ga = (f(0.5 + h, 1.3, -0.7) - f(0.5 - h, 1.3, -0.7)) / (2 * h)\n",
    "print(\"a.grad engine:\", round(a.grad, 5), \"  finite diff:\", round(ga, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "097ee91e",
   "metadata": {},
   "source": [
    "They agree to five decimals — your sixty lines compute the same derivatives the limit does, on an expression you'd never want to differentiate by hand. This is the test that makes the engine *trustworthy*: not a proof, but the check every practitioner actually runs.\n",
    "\n",
    "## 4. A tiny model, trained by your own engine\n",
    "\n",
    "Before numpy, prove the engine can *learn* — train a tiny next-letter model with nothing but Values and your backward sweep. Small enough to be pure Value, real enough to work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b41adc19",
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(0)\n",
    "names = [\"ada\", \"gauss\", \"euler\", \"abel\", \"nash\", \"hardy\", \"klein\", \"peano\", \"boole\", \"bayes\"]\n",
    "chars = sorted(set(\"\".join(names))) + [\".\"]\n",
    "stoi = {c: i for i, c in enumerate(chars)}\n",
    "V = len(chars)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}