Skip to main content

tpt_math_autodiff_rev/
lib.rs

1//! Reverse-mode (tape / Wengert-list) automatic differentiation.
2//!
3//! Where forward mode (see the `tpt-math-autodiff-fwd` crate) propagates one
4//! derivative direction per evaluation, reverse mode records the computation
5//! on a [`GradientTape`] and then replays it backwards, producing **all**
6//! partial derivatives of a single scalar output in one pass. That makes it
7//! the right tool for gradients of many-input, one-output functions such as
8//! loss functions and objective functions.
9//!
10//! # How it works
11//!
12//! * [`GradientTape`] owns a Wengert list: an append-only sequence of nodes,
13//!   each holding one primitive [`Op`] and the primal value it produced.
14//! * [`Variable`] is a `Copy` handle to a node — its index, its value, and a
15//!   back-pointer to the tape. Arithmetic operators and math methods evaluate
16//!   the primal value, push a node, and return a handle to it.
17//! * [`Op::diff`] supplies the local derivative rule for each primitive as a
18//!   small list of `(operand, ∂out/∂operand)` [`Partials`].
19//! * [`GradientTape::backward`] seeds the output node with an adjoint of `1`
20//!   and scans the tape in reverse. Because operands are always recorded
21//!   before the nodes that consume them, reverse index order *is* a reverse
22//!   topological order, so each node's adjoint is complete by the time it is
23//!   visited. Contributions are accumulated, so re-using a subexpression (a
24//!   diamond in the DAG) is handled automatically.
25//!
26//! # Examples
27//!
28//! ```
29//! use tpt_math_autodiff_rev::GradientTape;
30//!
31//! let tape = GradientTape::new();
32//! let x = tape.var(2.0);
33//! let y = tape.var(3.0);
34//! let z = x * x + y.sin();
35//! let g = tape.gradient(z, &[x, y]);
36//!
37//! assert!((g[0] - 4.0).abs() < 1e-9); // dz/dx = 2x
38//! assert!((g[1] - 3.0_f64.cos()).abs() < 1e-9); // dz/dy = cos(y)
39//! ```
40//!
41//! Supported primitives: `+`, `-`, `*`, `/` (between variables and with plain
42//! `f64` on either side), unary `-`, [`sin`], [`cos`], [`tan`], [`exp`],
43//! [`ln`], [`sqrt`], [`powi`], [`powf`] and [`recip`], plus constants that
44//! never carry a gradient.
45//!
46//! [`sin`]: Variable::sin
47//! [`cos`]: Variable::cos
48//! [`tan`]: Variable::tan
49//! [`exp`]: Variable::exp
50//! [`ln`]: Variable::ln
51//! [`sqrt`]: Variable::sqrt
52//! [`powi`]: Variable::powi
53//! [`powf`]: Variable::powf
54//! [`recip`]: Variable::recip
55
56#![forbid(unsafe_code)]
57#![warn(missing_docs, missing_debug_implementations)]
58
59mod op;
60mod tape;
61mod var;
62
63pub use crate::op::{Op, Partials, MAX_OPERANDS};
64pub use crate::tape::{Gradient, GradientTape};
65pub use crate::var::Variable;
66
67/// Everything needed to build and differentiate an expression.
68pub mod prelude {
69    pub use crate::{Gradient, GradientTape, Op, Partials, Variable};
70}
71
72/// Evaluate `f` at `inputs` and return `(value, gradient)`.
73///
74/// A convenience wrapper that creates a tape, seeds one input [`Variable`] per
75/// entry of `inputs`, evaluates `f`, and runs the backward pass — useful when
76/// the tape itself is not interesting to the caller.
77///
78/// # Examples
79///
80/// ```
81/// use tpt_math_autodiff_rev::value_and_gradient;
82///
83/// // f(x, y) = x * y + sin(x)
84/// let (value, grad) = value_and_gradient(&[2.0, 3.0], |_tape, v| v[0] * v[1] + v[0].sin());
85///
86/// assert!((value - (6.0 + 2.0_f64.sin())).abs() < 1e-9);
87/// assert!((grad[0] - (3.0 + 2.0_f64.cos())).abs() < 1e-9);
88/// assert!((grad[1] - 2.0).abs() < 1e-9);
89/// ```
90pub fn value_and_gradient<F>(inputs: &[f64], f: F) -> (f64, Vec<f64>)
91where
92    F: for<'t> FnOnce(&'t GradientTape, &[Variable<'t>]) -> Variable<'t>,
93{
94    let tape = GradientTape::with_capacity(inputs.len() * 4);
95    let vars = tape.vars(inputs);
96    let output = f(&tape, &vars);
97    let gradient = tape.gradient(output, &vars);
98    (output.value(), gradient)
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104    use tpt_math_autodiff_fwd::Dual;
105
106    /// Tolerance for exact analytic comparisons.
107    const TOL: f64 = 1e-9;
108
109    fn assert_close(actual: f64, expected: f64) {
110        assert!(
111            (actual - expected).abs() < TOL,
112            "expected {expected}, got {actual} (delta {})",
113            (actual - expected).abs()
114        );
115    }
116
117    /// f(x) = x^2 at x = 3 => f'(x) = 2x = 6.
118    #[test]
119    fn square_derivative() {
120        let tape = GradientTape::new();
121        let x = tape.var(3.0);
122        let f = x * x;
123        let g = tape.gradient(f, &[x]);
124        assert_close(f.value(), 9.0);
125        assert_close(g[0], 6.0);
126    }
127
128    /// f(x, y) = x*y + sin(x) at (2, 3)
129    /// => df/dx = y + cos(x) = 3 + cos(2), df/dy = x = 2.
130    #[test]
131    fn product_plus_sine_gradient() {
132        let tape = GradientTape::new();
133        let x = tape.var(2.0);
134        let y = tape.var(3.0);
135        let f = x * y + x.sin();
136        let g = tape.gradient(f, &[x, y]);
137
138        assert_close(f.value(), 6.0 + 2.0_f64.sin());
139        assert_close(g[0], 3.0 + 2.0_f64.cos());
140        assert_close(g[1], 2.0);
141    }
142
143    /// A deep expression with a shared subexpression (a diamond in the DAG),
144    /// which only differentiates correctly if the backward pass accumulates
145    /// contributions in reverse topological order.
146    ///
147    /// u = x*y, f = sin(u)*u + u
148    /// => df/du = u*cos(u) + sin(u) + 1, df/dx = y * df/du, df/dy = x * df/du.
149    #[test]
150    fn nested_shared_subexpression() {
151        let tape = GradientTape::new();
152        let (xv, yv) = (1.3_f64, 2.1_f64);
153        let x = tape.var(xv);
154        let y = tape.var(yv);
155
156        let u = x * y;
157        let f = u.sin() * u + u;
158
159        let uv = xv * yv;
160        let df_du = uv * uv.cos() + uv.sin() + 1.0;
161
162        let g = tape.gradient(f, &[x, y]);
163        assert_close(f.value(), uv.sin() * uv + uv);
164        assert_close(g[0], yv * df_du);
165        assert_close(g[1], xv * df_du);
166    }
167
168    /// A nested expression whose closed form collapses: ln(exp(x^2 + y)) is
169    /// exactly x^2 + y, so the gradient must be (2x, 1) despite the long tape.
170    #[test]
171    fn nested_inverse_functions_collapse() {
172        let tape = GradientTape::new();
173        let x = tape.var(0.7);
174        let y = tape.var(-0.3);
175        let f = (x.powi(2) + y).exp().ln();
176        let g = tape.gradient(f, &[x, y]);
177
178        assert_close(f.value(), 0.7 * 0.7 - 0.3);
179        assert_close(g[0], 1.4);
180        assert_close(g[1], 1.0);
181    }
182
183    /// Division and integer powers: f = x^3 / y.
184    #[test]
185    fn quotient_and_power_gradient() {
186        let tape = GradientTape::new();
187        let (xv, yv) = (2.0_f64, 4.0_f64);
188        let x = tape.var(xv);
189        let y = tape.var(yv);
190        let f = x.powi(3) / y;
191        let g = tape.gradient(f, &[x, y]);
192
193        assert_close(f.value(), 2.0);
194        assert_close(g[0], 3.0 * xv * xv / yv);
195        assert_close(g[1], -xv.powi(3) / (yv * yv));
196    }
197
198    /// Every primitive at once, checked against central finite differences.
199    #[test]
200    fn matches_central_finite_differences() {
201        // f(x, y) = sin(x)*cos(y) + tan(x/4) + exp(x - y) + ln(x + 3)
202        //           + sqrt(y) + x^3 + y^1.5 - x/y
203        fn eval(tape: &GradientTape, x: Variable<'_>, y: Variable<'_>) -> f64 {
204            let f = x.sin() * y.cos()
205                + (x / 4.0).tan()
206                + (x - y).exp()
207                + (x + 3.0).ln()
208                + y.sqrt()
209                + x.powi(3)
210                + y.powf(1.5)
211                - x / y;
212            let _ = tape;
213            f.value()
214        }
215
216        let (xv, yv) = (0.9_f64, 1.7_f64);
217        let tape = GradientTape::new();
218        let x = tape.var(xv);
219        let y = tape.var(yv);
220        let f = x.sin() * y.cos()
221            + (x / 4.0).tan()
222            + (x - y).exp()
223            + (x + 3.0).ln()
224            + y.sqrt()
225            + x.powi(3)
226            + y.powf(1.5)
227            - x / y;
228        let g = tape.gradient(f, &[x, y]);
229
230        let h = 1e-6;
231        let fd = |dx: f64, dy: f64| {
232            let t = GradientTape::new();
233            let a = t.var(xv + dx);
234            let b = t.var(yv + dy);
235            eval(&t, a, b)
236        };
237        let fd_x = (fd(h, 0.0) - fd(-h, 0.0)) / (2.0 * h);
238        let fd_y = (fd(0.0, h) - fd(0.0, -h)) / (2.0 * h);
239
240        assert!((g[0] - fd_x).abs() < 1e-6, "d/dx: {} vs {fd_x}", g[0]);
241        assert!((g[1] - fd_y).abs() < 1e-6, "d/dy: {} vs {fd_y}", g[1]);
242    }
243
244    /// Reverse mode must agree with the forward-mode dual numbers from
245    /// `tpt-math-autodiff-fwd` on the same function.
246    #[test]
247    fn agrees_with_forward_mode() {
248        let (xv, yv) = (1.3_f64, 2.7_f64);
249
250        // Reverse mode: f = sin(x*y) + exp(x)/y - ln(x + y).
251        let tape = GradientTape::new();
252        let x = tape.var(xv);
253        let y = tape.var(yv);
254        let f = (x * y).sin() + x.exp() / y - (x + y).ln();
255        let rev = tape.gradient(f, &[x, y]);
256
257        // Forward mode: the same expression over `Dual<f64, 2>`.
258        let dx = Dual::<f64, 2>::variable(xv, 0);
259        let dy = Dual::<f64, 2>::variable(yv, 1);
260        let df = (dx * dy).sin() + dx.exp() / dy - (dx + dy).ln();
261
262        assert_close(f.value(), df.re());
263        assert_close(rev[0], df.du(0));
264        assert_close(rev[1], df.du(1));
265    }
266
267    /// The convenience wrapper produces the same answers as manual taping.
268    #[test]
269    fn value_and_gradient_helper() {
270        let (value, grad) = value_and_gradient(&[2.0, 3.0], |_tape, v| v[0] * v[1] + v[0].sin());
271        assert_close(value, 6.0 + 2.0_f64.sin());
272        assert_close(grad[0], 3.0 + 2.0_f64.cos());
273        assert_close(grad[1], 2.0);
274    }
275
276    /// A many-input function: reverse mode gets the whole gradient from one
277    /// backward pass.
278    #[test]
279    fn many_inputs_single_backward_pass() {
280        let values: Vec<f64> = (1..=8).map(|i| f64::from(i) / 4.0).collect();
281        let tape = GradientTape::new();
282        let vars = tape.vars(&values);
283
284        // f = sum_i (x_i^2 * sin(x_0))
285        let s = vars[0].sin();
286        let mut f = tape.constant(0.0);
287        for &v in &vars {
288            f += v * v * s;
289        }
290
291        let sum_sq: f64 = values.iter().map(|v| v * v).sum();
292        let grad = tape.backward(f);
293
294        for (i, (&v, var)) in values.iter().zip(vars.iter()).enumerate() {
295            let mut expected = 2.0 * v * values[0].sin();
296            if i == 0 {
297                expected += sum_sq * values[0].cos();
298            }
299            assert_close(grad.wrt(*var), expected);
300        }
301    }
302
303    /// Gradient descent smoke test: the tape drives an optimiser to the
304    /// minimum of the Rosenbrock-like bowl f = (x-1)^2 + 10*(y - x^2)^2.
305    #[test]
306    fn drives_gradient_descent() {
307        let (mut x, mut y) = (-1.2_f64, 1.0_f64);
308        for _ in 0..20_000 {
309            let (_, g) = value_and_gradient(&[x, y], |_t, v| {
310                let a = v[0] - 1.0;
311                let b = v[1] - v[0] * v[0];
312                a * a + 10.0 * b * b
313            });
314            x -= 1e-3 * g[0];
315            y -= 1e-3 * g[1];
316        }
317        assert!((x - 1.0).abs() < 1e-3, "x = {x}");
318        assert!((y - 1.0).abs() < 1e-3, "y = {y}");
319    }
320}
321
322#[cfg(test)]
323mod hyperbolic_and_atan_tests {
324    use super::*;
325
326    /// Gradient of `f` at `point`, checked against central differences.
327    fn check_gradient<F>(point: &[f64], f: F)
328    where
329        F: for<'t> Fn(&[Variable<'t>]) -> Variable<'t>,
330    {
331        let tape = GradientTape::new();
332        let vars: Vec<Variable<'_>> = point.iter().map(|&v| tape.var(v)).collect();
333        let out = f(&vars);
334        let grad = tape.gradient(out, &vars);
335        let h = 1e-6;
336        for i in 0..point.len() {
337            let mut hi = point.to_vec();
338            let mut lo = point.to_vec();
339            hi[i] += h;
340            lo[i] -= h;
341            let eval = |p: &[f64]| {
342                let t = GradientTape::new();
343                let v: Vec<Variable<'_>> = p.iter().map(|&x| t.var(x)).collect();
344                f(&v).value()
345            };
346            let fd = (eval(&hi) - eval(&lo)) / (2.0 * h);
347            assert!(
348                (grad[i] - fd).abs() < 1e-6,
349                "component {i}: reverse {} vs finite difference {fd}",
350                grad[i]
351            );
352        }
353    }
354
355    #[test]
356    fn tanh_sinh_cosh_atan_match_finite_differences() {
357        check_gradient(&[0.7], |v| v[0].tanh());
358        check_gradient(&[-0.4], |v| v[0].sinh());
359        check_gradient(&[0.9], |v| v[0].cosh());
360        check_gradient(&[1.3], |v| v[0].atan());
361    }
362
363    #[test]
364    fn atan2_gradient_matches_finite_differences() {
365        check_gradient(&[0.6, -1.1], |v| v[0].atan2(v[1]));
366    }
367
368    #[test]
369    fn atan2_partials_have_the_documented_form() {
370        let tape = GradientTape::new();
371        let y = tape.var(3.0);
372        let x = tape.var(4.0);
373        let out = y.atan2(x);
374        let g = tape.gradient(out, &[y, x]);
375        // ∂/∂y = x/(x²+y²) = 4/25, ∂/∂x = −y/(x²+y²) = −3/25.
376        assert!((g[0] - 4.0 / 25.0).abs() < 1e-12);
377        assert!((g[1] + 3.0 / 25.0).abs() < 1e-12);
378        assert!((out.value() - 3.0_f64.atan2(4.0)).abs() < 1e-14);
379    }
380}