Automatic Differentiation

When using neural network packages, one of the most ubiquitous yet hidden feature is the automatic differentiation. Without diving too deep, especially in the performance optimization domain, the basic principle is worth understanding. But first, why not using one of the method of differentiation you already know:

  • symbolic: using symbolic variables everywhere, by opposition to ‘normal’ variable which stores only numbers, is theoretically possible, but in practice untractable in term of computation cost. Imagine deep neural networks, with millions of parameters.

  • numerical approximation: using local numerical slope suffers means that the entire network is evaluated with a forward pass for every parameter.

The automatic differentiation is both exact up to machine accuracy, and efficient accounting for the structure of the problem.

First order derivative

Even if it is not sufficient for our purpose, it is still useful to understand a simpler algorithm limited to first order differentiation. Two ingredients are introduced, first, the notion of computation graph, second, the concept of forward and backward sweeps.

There are two types of operations: unary or binary operations.

Unary operation

A unary operation represents taking a function of a variable, for example:

(1)\[\begin{split}u &= f(x) \\ v &= g(u)\end{split}\]

In this configuration, the derivatives can be obtained applying the chain rule:

\[\cfrac{\partial v}{\partial x} = \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{f'(x)}\]

For a specific \(f=\sin\) function and a specific \(x\) value one gets:

(2)\[\begin{split}x &= \cfrac{\pi}{6} \\ u &= \sin(x) = \cfrac{1}{2}\\ \cfrac{\partial v}{\partial x} &= \underbrace{\cfrac{\partial v}{\partial u}}_{\textrm{known}} \cos(x) = \cfrac{\partial v}{\partial u} \cfrac{\sqrt{3}}{2}\end{split}\]

This case can be symbolized by the two following graphs. The first represents the evaluation of the overall function \(u\), then \(v\), etc. This is the forward sweep from top to bottom. The circle nodes are variables; the double rectangular nodes are top the value and bottom the derivative value; the diamond nodes are applied functions.

unary forward

Forward sweep for a unary operation

The second represents the evaluation of the derivatives from bottom to top. The very last derivative represents the variation of the last variable with respect to itself; which is \(1\). The last derivative is then known, as a result, step by step one can backtrack all the successive derivatives.

unary backward

Backward sweep for a unary operation

Exercise (easy)

Draw the computation graph and calculate the derivative of \(\ln(\sin(x))\) at \(x=\cfrac{\pi}{3}\).

Correction

The symbolic calculation gives:

\[\cfrac{\partial }{\partial x} \ln(\sin(x)) = \cfrac{\cos(x)}{\sin(x)}\]
forward ln(sin(x))

Forward sweep

backward ln(sin(x))

Backward sweep

The second type of operation is binary. All the common calculus operator are binary: addition, multiplication, division, etc.

Binary: addition

(3)\[\begin{split}u &= x+y \\ v &= g(u)\end{split}\]

The derivatives can be obtained applying the chain rule:

(4)\[\begin{split}\cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=1} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=1}\end{split}\]
add forward

Forward sweep for the add operation

add backward

Backward sweep for the add operation

Binary: multiplication

(5)\[\begin{split}u &= x y \\ v &= g(u)\end{split}\]

The derivatives can be obtained applying the chain rule:

(6)\[\begin{split}\cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=y} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=x}\end{split}\]
multiplication forward

Forward sweep for the multiplication operation

multiplication backward

Backward sweep for the multiplication operation

Exercise (easy)

Draw the computational graph for the division operation.

Correction
(7)\[\begin{split}u &= \cfrac{x}{y} \\ v &= g(u)\end{split}\]

The derivatives can be obtained applying the chain rule:

(8)\[\begin{split}\cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=\cfrac{1}{y}} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=\cfrac{-x}{y^2}}\end{split}\]
division forward

Forward sweep for the division operation

division backward

Backward sweep for the division operation

Reverse order

Imagine the following computation graph:

order forward

Forward sweep (order)

The first step of the reverse sweep gives:

order backward first

Backward sweep (order, first step)

At this stage, there are two possibilities:

  • either, one continues upward with the right branch which leads temporarily to a \(3+3\) in the \(x\) derivative, then go back to where one stopped and continue up the left branch, which leads to a \(1+\exp(9)\) in the \(u\) derivative, and finally \((3+3) + (3(1+\exp(9)) + 3(1+\exp(9)))\) in the \(x\) derivative.

  • or, first one levels up the left branch and get a \(1+\exp(9)\) in the \(u\) derivative, then \(3(1+\exp(9)) + 3(1+\exp(9))\) in the \(x\) derivative.

Obviously, the second solution is the correct one if you check the symbolic derivative. It means that the traversal order of the computation graph is important, one needs to ensure that an intermediate derivative is fully calculated before propagating backward. This ordering has already been encountered in the traversal algorithm section, it is the topographic order.

order backward

Backward sweep (order)

Implementation

A simple implementation of a first order auto-differentiation can be based on the following data structure:

src
 1@dataclass
 2class Node:
 3    val: float
 4    parents: tuple[Self, ...] = field(default_factory=tuple)
 5    name: str = ""
 6    is_constant: bool = False
 7
 8    index: int = field(init=False)
 9
10    _counter: ClassVar[int] = 0
11
12    def __post_init__(self) -> None:
13        self.backward: Callable[[Self, Derivatives], None] = lambda _, __: None
14        self.index = self._counter
15        self._increment_counter()
16
17    def __hash__(self) -> int:
18        return self.index
19
20    @classmethod
21    def _increment_counter(cls):
22        cls._counter += 1

and the following function to obtain the first derivative:

src
 1def differentiate(node: Node) -> Derivatives:
 2    """after getting the topological order,
 3    computes the numerical values of every intermediate
 4    derivatives by calling the backward callbacks of every node.
 5
 6    If the node is declared constant, all the derivatives are zero.
 7    Using a defaultdict derivatives allows to return 0.0 if a key is not present.
 8
 9    It serves two purposes:
10    - first the cumulate operation in the backward callbacks is automatically valid
11    - if a node is not key, it means it is not part of the parent tree,
12      so the derivative should be 0.0"""
13    order: tuple[Node, ...] = topological_sort(node)
14    derivatives: Derivatives = defaultdict(float)
15
16    if node.is_constant:
17        return derivatives
18
19    derivatives[node] = 1.0
20    for current in order:
21        current.backward(current, derivatives)
22    return derivatives

The forward operations (addition, multiplication, etc) build a computation graph. Then, the reverse sweep starting from the final node and going backward in a topographic order executes all the backward operation described above.

Exercise (intermediate)

  1. The Node class is not commented on purpose. Explain briefly the role you imagine for every attributes and methods.

  2. Define a single forward unary operation the corresponding backward operation, such as \(\log\) for example. Use it (potentially composed several times \(\log(\log(\cdots))\)) and check out the forward pass value and name.

  3. In the differentiate function, you see that first, the traversal order is obtained, then the backward callback is executed on every node from the very end to the very start.

    The only missing brick is the function topological_sort. Implement it. Test it. Then, test the entire algorithm on the unary function of your choice.

  4. Define a single forward binary operation the corresponding backward operation, such as the multiplication. Use it (potentially composed several times \(((x * x) * x)\)) and check out the forward pass value and name. Test it. Check the topographic order. Test the entire algorithm.

  5. Implement and test all the other useful operations.

Correction

  1. A forward operation takes one (unary) or two (binary) nodes and produces a result node.

    Depending on the forward operation (addition, multiplication etc), the result val attribute value is calculated from the val of the single or double parents. The val attribute represents the content of the first rectangular node.

    A node can represent either a variable, or a constant. The attribute is_constant records this point. A node can either be created as constant manually, or be automatically constant if all its parents are constant.

    The backward attribute is a callable which takes a node and computes set the local derivative value in the parent node(s).

    The index attribute is a unique node identifier. The _counter class attribute keeps count of how many nodes were created in order to produce a unique index.

    (The name is the less transparent and most optional. It is mostly useful for debugging. It will be used to represent in a readable format each operation “(name first parent *|+|… name second parent)”.)

  2. src
    1def log_forward(node: Node) -> Node:
2    result = Node(
3        log(node.val),
4        (node,),
5        f"log({node.name})",
6    )
7    result.backward = log_backward
8    return result
    src
    1def log_backward(node: Node, derivatives: Derivatives) -> None:
2    derivatives[node.parents[0]] += derivatives[node] / node.parents[0].val
  3. src
     1def topological_sort(node: Node) -> tuple[Node, ...]:
 2    """here the topological order is intended from the leaf node up to the
 3    root nodes.
 4
 5    Each node points towards its parent(s). It means that starting from a leaf
 6    node, a DFS traversal will go all the way up to the last parents (root nodes).
 7
 8    N0 <- N1 <- N2 <- N3
 9           ^          |
10           |          |
11           ------------
12
13    Since the yield statement is located AFTER the recursive call,
14    the nodes would be yielded in the reverse topological order.
15
16    Assuming the first parent of N3 is N1:
17
18    N4, N1, N0
19    yields: N0, N1
20    N2, (N1 already visited)
21    yields: N2, N3
22
23    => N0, N1, N2,  N3
24
25    That is why it is reversed before return.
26    """
27    visited: set[int] = set()
28
29    def _dfs(current: Node) -> Generator[Node]:
30        if current.index in visited:
31            return
32        visited.add(current.index)
33        for parent in current.parents:
34            yield from _dfs(parent)
35        yield current
36
37    return tuple(reversed(tuple(_dfs(node))))
    tests
     1def test_topological_sort():
 2    # x <- x^2 <- x^2 + exp(x^2)
 3    #       ^         |
 4    #       |         V
 5    #        ---- exp(x^2)
 6    x = Node(3.0, name="x")
 7    x2 = multiplication_forward(x, x)
 8    z = addition_forward(x2, exp_forward(x2))
 9    order: tuple[Node, ...] = topological_sort(z)
10    reverse_expected = ("x", "(x * x)", "exp((x * x))", "((x * x) + exp((x * x)))")
11    assert tuple(reversed(reverse_expected)) == tuple(node.name for node in order)
  4. src
    1def multiplication_forward(first: Node, second: Node) -> Node:
2    result = Node(
3        first.val * second.val,
4        (first, second),
5        f"({first.name} * {second.name})",
6    )
7    result.backward = multiplication_backward
8    return result
    src
    1def multiplication_backward(node: Node, derivatives: Derivatives) -> None:
2    derivatives[node.parents[0]] += node.parents[1].val * derivatives[node]
3    derivatives[node.parents[1]] += node.parents[0].val * derivatives[node]
    tests
    1@pytest.fixture(params=list(range(1, 4)))
2def x_val(request) -> float:
3    x_val = float(request.param)
4    return x_val
    tests
     1@pytest.fixture(params=list(range(1, 6)))
 2def x_pow_one_by_one(request, x_val) -> tuple[Node, Node, float, float]:
 3    max_power: int = request.param
 4    x = Node(x_val, name="x")
 5    z = x
 6    for _ in range(max_power - 1):
 7        z = multiplication_forward(z, x)
 8    return (
 9        x,
10        z,
11        x_val**max_power,
12        max_power * x_val ** (max_power - 1),
13    )
    tests
     1def assert_derivatives(x_z_zv_dzv: tuple[Node, Node, float, float]) -> None:
 2    x, z, z_val, dz_val = x_z_zv_dzv
 3    print(f"\n x={x.val} f(x)={z.name}")
 4
 5    assert pytest.approx(z.val) == z_val
 6
 7    # ic(z)
 8
 9    dz: Derivatives = differentiate(z)
10
11    # ic(dz)
12    # breakpoint()
13
14    assert pytest.approx(dz[x]) == dz_val
    tests
    1def test_derivatives_pow_one_by_one(x_pow_one_by_one):
2    assert_derivatives(x_pow_one_by_one)
  5. src
      1"""Auto differentiation at the first order (only for first derivative),
  2on scalar expressions.
  3
  4Three sections:
  5- the Node class which builds the computation graph
  6- all the forward and backward operations
  7- the ordering and differentiate functions"""
  8
  9from dataclasses import dataclass, field
 10from math import exp, log
 11
 12from typing import Self, ClassVar
 13from collections.abc import Callable, Generator
 14from collections import defaultdict
 15
 16type Derivatives = dict[Node, float]
 17
 18
 19@dataclass
 20class Node:
 21    val: float
 22    parents: tuple[Self, ...] = field(default_factory=tuple)
 23    name: str = ""
 24    is_constant: bool = False
 25
 26    index: int = field(init=False)
 27
 28    _counter: ClassVar[int] = 0
 29
 30    def __post_init__(self) -> None:
 31        self.backward: Callable[[Self, Derivatives], None] = lambda _, __: None
 32        self.index = self._counter
 33        self._increment_counter()
 34
 35    def __hash__(self) -> int:
 36        return self.index
 37
 38    @classmethod
 39    def _increment_counter(cls):
 40        cls._counter += 1
 41
 42
 43ONE = Node(1.0, name="1", is_constant=True)
 44
 45
 46def multiplication_forward(first: Node, second: Node) -> Node:
 47    result = Node(
 48        first.val * second.val,
 49        (first, second),
 50        f"({first.name} * {second.name})",
 51    )
 52    result.backward = multiplication_backward
 53    return result
 54
 55
 56def addition_forward(first: Node, second: Node) -> Node:
 57    result = Node(
 58        first.val + second.val,
 59        (first, second),
 60        f"({first.name} + {second.name})",
 61    )
 62    result.backward = addition_backward
 63    return result
 64
 65
 66def division_forward(num: Node, den: Node) -> Node:
 67    result = Node(
 68        num.val / den.val,
 69        (num, den),
 70        f"({num.name} / {den.name})",
 71    )
 72    result.backward = division_backward
 73    return result
 74
 75
 76def exp_forward(node: Node) -> Node:
 77    result = Node(
 78        exp(node.val),
 79        (node,),
 80        f"exp({node.name})",
 81    )
 82    result.backward = exp_backward
 83    return result
 84
 85
 86def log_forward(node: Node) -> Node:
 87    result = Node(
 88        log(node.val),
 89        (node,),
 90        f"log({node.name})",
 91    )
 92    result.backward = log_backward
 93    return result
 94
 95
 96def power_int_forward(node: Node, power: int) -> Node:
 97    if not isinstance(power, int):
 98        raise ValueError("exponent is supposed to be integer.")
 99
100    result = ONE
101    for _ in range(abs(power)):
102        result = multiplication_forward(
103            result,
104            node,
105        )
106    if power < 0:
107        return division_forward(ONE, result)
108    else:
109        return result
110
111
112def power_float_forward(node: Node, power: Node) -> Node:
113    if node.val <= 0:
114        raise ValueError("cannot take a real power of a negative number")
115    result = exp_forward(multiplication_forward(power, log_forward(node)))
116    return result
117
118
119def multiplication_backward(node: Node, derivatives: Derivatives) -> None:
120    derivatives[node.parents[0]] += node.parents[1].val * derivatives[node]
121    derivatives[node.parents[1]] += node.parents[0].val * derivatives[node]
122
123
124def addition_backward(node: Node, derivatives: Derivatives) -> None:
125    derivatives[node.parents[0]] += derivatives[node]
126    derivatives[node.parents[1]] += derivatives[node]
127
128
129def division_backward(node: Node, derivatives: Derivatives) -> None:
130    derivatives[node.parents[0]] += derivatives[node] / node.parents[1].val
131    derivatives[node.parents[1]] -= (
132        derivatives[node] * node.parents[0].val / node.parents[1].val ** 2
133    )
134
135
136def exp_backward(node: Node, derivatives: Derivatives) -> None:
137    derivatives[node.parents[0]] += derivatives[node] * node.val
138
139
140def log_backward(node: Node, derivatives: Derivatives) -> None:
141    derivatives[node.parents[0]] += derivatives[node] / node.parents[0].val
142
143
144def topological_sort(node: Node) -> tuple[Node, ...]:
145    """here the topological order is intended from the leaf node up to the
146    root nodes.
147
148    Each node points towards its parent(s). It means that starting from a leaf
149    node, a DFS traversal will go all the way up to the last parents (root nodes).
150
151    N0 <- N1 <- N2 <- N3
152           ^          |
153           |          |
154           ------------
155
156    Since the yield statement is located AFTER the recursive call,
157    the nodes would be yielded in the reverse topological order.
158
159    Assuming the first parent of N3 is N1:
160
161    N4, N1, N0
162    yields: N0, N1
163    N2, (N1 already visited)
164    yields: N2, N3
165
166    => N0, N1, N2,  N3
167
168    That is why it is reversed before return.
169    """
170    visited: set[int] = set()
171
172    def _dfs(current: Node) -> Generator[Node]:
173        if current.index in visited:
174            return
175        visited.add(current.index)
176        for parent in current.parents:
177            yield from _dfs(parent)
178        yield current
179
180    return tuple(reversed(tuple(_dfs(node))))
181
182
183def differentiate(node: Node) -> Derivatives:
184    """after getting the topological order,
185    computes the numerical values of every intermediate
186    derivatives by calling the backward callbacks of every node.
187
188    If the node is declared constant, all the derivatives are zero.
189    Using a defaultdict derivatives allows to return 0.0 if a key is not present.
190
191    It serves two purposes:
192    - first the cumulate operation in the backward callbacks is automatically valid
193    - if a node is not key, it means it is not part of the parent tree,
194      so the derivative should be 0.0"""
195    order: tuple[Node, ...] = topological_sort(node)
196    derivatives: Derivatives = defaultdict(float)
197
198    if node.is_constant:
199        return derivatives
200
201    derivatives[node] = 1.0
202    for current in order:
203        current.backward(current, derivatives)
204    return derivatives
    tests
      1"""tests for first order scalar auto differentiation
  2
  3most of the tests are parametrized as follow:
  4- x_val takes several values and is passed to every fixture
  5- other fixtures (ex: x_pow_one_by_one) receives x_val and
  6  and an other parametrized value (here the power). These fixtures
  7  returns (the variable node, the expression node,
  8           the expression value, the derivative value)
  9
 10Every cross values are tested.
 11
 12All the tests of the forward/backward sweeps call assert_derivatives.
 13"""
 14
 15from math import exp, log
 16
 17import pytest
 18
 19from ai.fnn.autodiff_first import (
 20    multiplication_forward,
 21    addition_forward,
 22    division_forward,
 23    exp_forward,
 24    log_forward,
 25    power_int_forward,
 26    power_float_forward,
 27    Node,
 28    ONE,
 29    differentiate,
 30    Derivatives,
 31    topological_sort,
 32)
 33
 34
 35@pytest.fixture(params=list(range(1, 4)))
 36def x_val(request) -> float:
 37    x_val = float(request.param)
 38    return x_val
 39
 40
 41@pytest.fixture(params=list(range(1, 6)))
 42def x_pow_one_by_one(request, x_val) -> tuple[Node, Node, float, float]:
 43    max_power: int = request.param
 44    x = Node(x_val, name="x")
 45    z = x
 46    for _ in range(max_power - 1):
 47        z = multiplication_forward(z, x)
 48    return (
 49        x,
 50        z,
 51        x_val**max_power,
 52        max_power * x_val ** (max_power - 1),
 53    )
 54
 55
 56@pytest.fixture(params=list(range(3, 5)))
 57def x_pow_power_of_two(request, x_val) -> tuple[Node, Node, float, float]:
 58    nb_doubling: int = request.param
 59    x = Node(x_val, name="x")
 60    z = x
 61    max_power: int = 1
 62    for _ in range(nb_doubling - 1):
 63        max_power *= 2
 64        z = multiplication_forward(z, z)
 65    return (
 66        x,
 67        z,
 68        x_val**max_power,
 69        max_power * x_val ** (max_power - 1),
 70    )
 71
 72
 73@pytest.fixture(params=list(range(1, 6)))
 74def x_sum_one_by_one(request, x_val) -> tuple[Node, Node, float, float]:
 75    max_repet: int = request.param
 76    x = Node(x_val, name="x")
 77    z = x
 78    for _ in range(max_repet - 1):
 79        z = addition_forward(z, x)
 80    return (
 81        x,
 82        z,
 83        max_repet * x_val,
 84        max_repet,
 85    )
 86
 87
 88@pytest.fixture(params=list(range(1, 4)))
 89def x_inv_pow_one_by_one(request, x_val) -> tuple[Node, Node, float, float]:
 90    max_power: int = request.param
 91    x = Node(x_val, name="x")
 92    z = ONE
 93    for _ in range(max_power):
 94        z = division_forward(z, x)
 95    return (
 96        x,
 97        z,
 98        x_val ** (-max_power),
 99        -max_power / x_val ** (max_power + 1),
100    )
101
102
103@pytest.fixture
104def x_exp(x_val) -> tuple[Node, Node, float, float]:
105    x = Node(x_val, name="x")
106    z = exp_forward(x)
107    return (
108        x,
109        z,
110        exp(x_val),
111        exp(x_val),
112    )
113
114
115@pytest.fixture
116def x_exp_exp(x_val) -> tuple[Node, Node, float, float]:
117    x = Node(x_val, name="x")
118    z = exp_forward(exp_forward(x))
119    return (
120        x,
121        z,
122        exp(exp(x_val)),
123        exp(exp(x_val) + x_val),
124    )
125
126
127@pytest.fixture
128def x_log(x_val) -> tuple[Node, Node, float, float]:
129    x = Node(x_val, name="x")
130    z = log_forward(x)
131    return (
132        x,
133        z,
134        log(x_val),
135        1.0 / x_val,
136    )
137
138
139@pytest.fixture
140def x_log_log() -> tuple[Node, Node, float, float]:
141    x_val: float = 2.0
142    x = Node(x_val, name="x")
143    z = log_forward(log_forward(x))
144    return (
145        x,
146        z,
147        log(log(x_val)),
148        1.0 / (x_val * log(x_val)),
149    )
150
151
152@pytest.fixture
153def x_power_int(x_val) -> tuple[Node, Node, float, float]:
154    x = Node(x_val, name="x")
155    power: int = 4
156    z = power_int_forward(x, power)
157    return (
158        x,
159        z,
160        x_val**power,
161        power * x_val ** (power - 1),
162    )
163
164
165@pytest.fixture
166def x_power_float(x_val) -> tuple[Node, Node, float, float]:
167    x = Node(x_val, name="x")
168    power_val: float = 3.5
169    power = Node(power_val, name="a")
170    z = power_float_forward(x, power)
171    return (
172        x,
173        z,
174        x_val**power_val,
175        power_val * x_val ** (power_val - 1),
176    )
177
178
179@pytest.fixture
180def x2_p_exp_x2(x_val) -> tuple[Node, Node, float, float]:
181    x = Node(x_val, name="x")
182    x2 = multiplication_forward(x, x)
183    z = addition_forward(x2, exp_forward(x2))
184
185    return (
186        x,
187        z,
188        x_val**2 + exp(x_val**2),
189        2 * x_val * (1.0 + exp(x_val**2)),
190    )
191
192
193@pytest.fixture
194def x_one() -> tuple[Node, Node, float, float]:
195    x = ONE
196    z = x
197
198    return (
199        x,
200        z,
201        1.0,
202        0.0,
203    )
204
205
206def assert_derivatives(x_z_zv_dzv: tuple[Node, Node, float, float]) -> None:
207    x, z, z_val, dz_val = x_z_zv_dzv
208    print(f"\n x={x.val} f(x)={z.name}")
209
210    assert pytest.approx(z.val) == z_val
211
212    # ic(z)
213
214    dz: Derivatives = differentiate(z)
215
216    # ic(dz)
217    # breakpoint()
218
219    assert pytest.approx(dz[x]) == dz_val
220
221
222def test_derivatives_pow_one_by_one(x_pow_one_by_one):
223    assert_derivatives(x_pow_one_by_one)
224
225
226def test_derivatives_pow_power_of_two(x_pow_power_of_two):
227    assert_derivatives(x_pow_power_of_two)
228
229
230def test_derivatives_sum_one_by_one(x_sum_one_by_one):
231    assert_derivatives(x_sum_one_by_one)
232
233
234def test_derivatives_inv_one_by_one(x_inv_pow_one_by_one):
235    assert_derivatives(x_inv_pow_one_by_one)
236
237
238def test_derivatives_exp(x_exp):
239    assert_derivatives(x_exp)
240
241
242def test_derivatives_exp_exp(x_exp_exp):
243    assert_derivatives(x_exp_exp)
244
245
246def test_derivatives_log(x_log):
247    assert_derivatives(x_log)
248
249
250def test_derivatives_log_log(x_log_log):
251    assert_derivatives(x_log_log)
252
253
254def test_derivatives_power_int(x_power_int):
255    assert_derivatives(x_power_int)
256
257
258def test_derivatives_power_float(x_power_float):
259    assert_derivatives(x_power_float)
260
261
262def test_derivatives_x2_p_exp_x2(x2_p_exp_x2):
263    assert_derivatives(x2_p_exp_x2)
264
265
266def test_derivatives_x_one(x_one):
267    assert_derivatives(x_one)
268
269
270def test_topological_sort():
271    # x <- x^2 <- x^2 + exp(x^2)
272    #       ^         |
273    #       |         V
274    #        ---- exp(x^2)
275    x = Node(3.0, name="x")
276    x2 = multiplication_forward(x, x)
277    z = addition_forward(x2, exp_forward(x2))
278    order: tuple[Node, ...] = topological_sort(z)
279    reverse_expected = ("x", "(x * x)", "exp((x * x))", "((x * x) + exp((x * x)))")
280    assert tuple(reversed(reverse_expected)) == tuple(node.name for node in order)