Skip to main content

tpt_math_symbolic/
lib.rs

1//! Permissive-license symbolic math (CAS).
2//!
3//! `tpt-math-symbolic` provides a small, dependency-light computer-algebra
4//! core built around an expression tree [`Expr<C>`] parameterised over a
5//! numeric [`Coefficient`]. It supports construction, algebraic
6//! simplification, symbolic differentiation, substitution and evaluation.
7//!
8//! # Design decision (spec.txt open call)
9//!
10//! The expression tree is generic over [`Coefficient`] rather than hard-wired
11//! to a single number type. The default convenience alias is
12//! [`Expr64`] (`Expr<f64>`). Enable the `exact` feature to also get
13//! [`ExprRational`], which is backed by arbitrary-precision
14//! [`tpt_math_exact::BigRational`] wrapped in a [`Coefficient`] implementation.
15//! This keeps the crate genuinely coefficient-agnostic without forcing every
16//! consumer onto exact arithmetic.
17//!
18//! # Correctness caveats
19//!
20//! Two properties of this CAS are intentional but worth flagging before you
21//! depend on it:
22//!
23//! * **Unbounded recursion in `simplify`.** Simplification is implemented as
24//!   straight structural recursion over the expression tree (`simplify`).
25//!   It terminates for any finite, acyclic expression, but it is *not* guarded
26//!   against cyclic/self-referential input: building an expression that
27//!   contains itself (e.g. via `Rc`/interior mutability smuggled past the
28//!   ownership model, or a malicious parser) would recurse until the stack
29//!   overflows. Construction through the public [`Expr`] API produces acyclic
30//!   trees, so normal use is safe; only hand-built or externally-parsed input
31//!   needs scrutiny.
32//!
33//! * **`f64` round-trip breaks exactness for transcendental functions.**
34//!   [`Coefficient`] values are rendered through [`fmt::Display`] and parsed
35//!   back via `f64` when evaluating functions such as `sin`/`cos`/`exp`
36//!   (see `apply_func`). For the default `f64` coefficient this is the
37//!   identity path and is fine, but it means *exact* coefficients (the `exact`
38//!   feature's `BigRational`) are first coerced to `f64`, losing precision and
39//!   making transcendental results approximate even when the inputs were
40//!   exact. Algebraic simplification (add/mul/pow of rationals) stays exact;
41//!   only transcendentals go through the `f64` round-trip.
42//!
43//! ```
44//! use tpt_math_symbolic::{Expr64, Symbolic};
45//!
46//! // Build (3*x + 1)^2 and differentiate with respect to x.
47//! let x = Expr64::var("x");
48//! let expr = (Expr64::from(3.0) * x.clone() + Expr64::from(1.0)).pow(2);
49//! let d = expr.derivative("x").simplify();
50//! assert_eq!(d.eval_str("x", 2.0).unwrap(), 42.0);
51//! ```
52
53use std::collections::HashMap;
54use std::fmt;
55
56use num_traits::{One, Zero};
57
58/// A numeric value that can sit at a leaf of an [`Expr`] and survive
59/// simplification, evaluation and differentiation.
60///
61/// Implementors must be a field-like type supporting the four arithmetic
62/// operations plus integer powers. `f64` satisfies this out of the box; the
63/// `exact` feature provides an implementation for wrapped
64/// [`tpt_math_exact::BigRational`].
65pub trait Coefficient:
66    Clone
67    + PartialEq
68    + fmt::Debug
69    + fmt::Display
70    + From<f64>
71    + Zero
72    + One
73    + std::ops::Add<Output = Self>
74    + std::ops::Sub<Output = Self>
75    + std::ops::Mul<Output = Self>
76    + std::ops::Div<Output = Self>
77    + std::ops::Neg<Output = Self>
78{
79    /// Raise `self` to an integer power.
80    fn powi(self, n: i32) -> Self;
81
82    /// Whether this coefficient is exactly zero.
83    fn is_zero_value(&self) -> bool {
84        *self == Self::zero()
85    }
86}
87
88impl Coefficient for f64 {
89    fn powi(self, n: i32) -> Self {
90        f64::powi(self, n)
91    }
92}
93
94/// A symbolic expression over coefficient type `C`.
95#[derive(Clone, Debug, PartialEq)]
96pub enum Expr<C: Coefficient> {
97    /// A literal constant, e.g. `3.0`.
98    Const(C),
99    /// A free variable, e.g. `x`.
100    Var(String),
101    /// Addition of two sub-expressions.
102    Add(Box<Expr<C>>, Box<Expr<C>>),
103    /// Subtraction of the right from the left.
104    Sub(Box<Expr<C>>, Box<Expr<C>>),
105    /// Multiplication of two sub-expressions.
106    Mul(Box<Expr<C>>, Box<Expr<C>>),
107    /// Division of the left by the right.
108    Div(Box<Expr<C>>, Box<Expr<C>>),
109    /// Arithmetic negation.
110    Neg(Box<Expr<C>>),
111    /// `base^exponent` with a non-negative integer exponent.
112    Pow(Box<Expr<C>>, usize),
113    /// A named unary function applied to a sub-expression, e.g. `sin(...)`.
114    Func(String, Box<Expr<C>>),
115}
116
117/// Extension trait providing fluent constructor and calculus helpers.
118///
119/// Implemented for `Expr<C>` so callers can write `x.derivative("x")`,
120/// `expr.simplify()`, and so on.
121pub trait Symbolic<C: Coefficient> {
122    /// Construct a variable expression.
123    fn var(name: impl Into<String>) -> Self;
124    /// Construct a constant expression from a literal `f64`.
125    fn constant(f: f64) -> Self;
126    /// Raise this expression to a non-negative integer power.
127    fn pow(self, n: usize) -> Self;
128    /// Simplify this expression using algebraic identities.
129    fn simplify(self) -> Self;
130    /// Differentiate with respect to `var`.
131    fn derivative(&self, var: &str) -> Self;
132    /// Substitute `var` for `value` throughout the expression.
133    fn substitute(&self, var: &str, value: C) -> Self;
134    /// Evaluate the expression to a coefficient, given a variable environment.
135    fn eval(&self, env: &HashMap<String, C>) -> Option<C>;
136    /// Convenience wrapper evaluating with a single variable binding.
137    fn eval_str(&self, var: &str, value: f64) -> Option<C>
138    where
139        C: From<f64>;
140}
141
142impl<C: Coefficient> Expr<C> {
143    /// Construct a variable expression.
144    pub fn var(name: impl Into<String>) -> Expr<C> {
145        Expr::Var(name.into())
146    }
147
148    /// Construct a constant expression from a literal `f64`.
149    pub fn constant(f: f64) -> Expr<C>
150    where
151        C: From<f64>,
152    {
153        Expr::Const(C::from(f))
154    }
155
156    /// Raise this expression to a non-negative integer power.
157    pub fn pow(self, n: usize) -> Expr<C> {
158        Expr::Pow(Box::new(self), n)
159    }
160
161    /// Build a named unary function expression, e.g. `Expr64::func("sin", x)`.
162    pub fn func(name: impl Into<String>, inner: Expr<C>) -> Expr<C> {
163        Expr::Func(name.into(), Box::new(inner))
164    }
165
166    /// Compile this expression to a closure over the variables `vars`.
167    ///
168    /// See [`compile`] for the calling convention and the error cases.
169    pub fn compile(&self, vars: &[&str]) -> Result<Compiled<C>, CompileError>
170    where
171        C: 'static,
172    {
173        compile(self, vars)
174    }
175}
176
177impl<C: Coefficient> Symbolic<C> for Expr<C> {
178    fn var(name: impl Into<String>) -> Expr<C> {
179        Expr::var(name)
180    }
181
182    fn constant(f: f64) -> Expr<C> {
183        Expr::constant(f)
184    }
185
186    fn pow(self, n: usize) -> Expr<C> {
187        Expr::pow(self, n)
188    }
189
190    fn simplify(self) -> Expr<C> {
191        // Run single passes until the expression stops changing. A pass can expose
192        // new folding opportunities (e.g. `x^1` inside a product), so one pass is
193        // not always a fixpoint. The cap is a guard against a non-converging rule.
194        let mut current = self;
195        for _ in 0..MAX_SIMPLIFY_PASSES {
196            let next = simplify(current.clone());
197            if next == current {
198                return next;
199            }
200            current = next;
201        }
202        current
203    }
204
205    fn derivative(&self, var: &str) -> Expr<C> {
206        derivative(self, var)
207    }
208
209    fn substitute(&self, var: &str, value: C) -> Expr<C> {
210        substitute(self, var, value)
211    }
212
213    fn eval(&self, env: &HashMap<String, C>) -> Option<C> {
214        eval(self, env)
215    }
216
217    fn eval_str(&self, var: &str, value: f64) -> Option<C>
218    where
219        C: From<f64>,
220    {
221        let mut env = HashMap::new();
222        env.insert(var.to_string(), C::from(value));
223        eval(self, &env)
224    }
225}
226
227/// `Expr<f64>` — the default, floating-point symbolic expression.
228pub type Expr64 = Expr<f64>;
229
230mod compile;
231pub use compile::{compile, CompileError, Compiled};
232mod syntax;
233pub use syntax::{parse_expr, ParseError};
234
235impl<C: Coefficient> From<f64> for Expr<C>
236where
237    C: From<f64>,
238{
239    fn from(f: f64) -> Expr<C> {
240        Expr::Const(C::from(f))
241    }
242}
243
244impl From<&str> for Expr64 {
245    fn from(name: &str) -> Expr64 {
246        Expr::Var(name.to_string())
247    }
248}
249
250impl From<String> for Expr64 {
251    fn from(name: String) -> Expr64 {
252        Expr::Var(name)
253    }
254}
255
256macro_rules! binop {
257    ($trait:ident, $variant:ident, $method:ident) => {
258        impl<C: Coefficient> std::ops::$trait for Expr<C> {
259            type Output = Expr<C>;
260            fn $method(self, rhs: Expr<C>) -> Expr<C> {
261                Expr::$variant(Box::new(self), Box::new(rhs))
262            }
263        }
264    };
265}
266
267binop!(Add, Add, add);
268binop!(Sub, Sub, sub);
269binop!(Mul, Mul, mul);
270binop!(Div, Div, div);
271
272impl<C: Coefficient> std::ops::Neg for Expr<C> {
273    type Output = Expr<C>;
274    fn neg(self) -> Expr<C> {
275        Expr::Neg(Box::new(self))
276    }
277}
278
279impl<C: Coefficient> std::ops::Add<C> for Expr<C> {
280    type Output = Expr<C>;
281    fn add(self, rhs: C) -> Expr<C> {
282        Expr::Add(Box::new(self), Box::new(Expr::Const(rhs)))
283    }
284}
285
286impl<C: Coefficient> std::ops::Mul<C> for Expr<C> {
287    type Output = Expr<C>;
288    fn mul(self, rhs: C) -> Expr<C> {
289        Expr::Mul(Box::new(self), Box::new(Expr::Const(rhs)))
290    }
291}
292
293/// Upper bound on fixpoint passes in [`Symbolic::simplify`].
294const MAX_SIMPLIFY_PASSES: usize = 64;
295
296fn simplify<C: Coefficient>(e: Expr<C>) -> Expr<C> {
297    match e {
298        Expr::Const(c) => Expr::Const(c),
299        Expr::Var(v) => Expr::Var(v),
300        Expr::Neg(a) => {
301            let a = simplify(*a);
302            match a {
303                Expr::Const(c) => Expr::Const(-c),
304                Expr::Neg(inner) => *inner,
305                other => Expr::Neg(Box::new(other)),
306            }
307        }
308        Expr::Add(a, b) => fold_add(vec![simplify(*a), simplify(*b)]),
309        Expr::Sub(a, b) => fold_add(vec![simplify(*a), simplify(Expr::Neg(Box::new(*b)))]),
310        Expr::Mul(a, b) => fold_mul(vec![simplify(*a), simplify(*b)]),
311        Expr::Div(a, b) => {
312            let (a, b) = (simplify(*a), simplify(*b));
313            match (&a, &b) {
314                (Expr::Const(c1), Expr::Const(c2)) => Expr::Const(c1.clone() / c2.clone()),
315                (_, Expr::Const(c)) if *c == C::one() => a,
316                // `x / x` is taken as 1. This is false at `x = 0` (undefined there),
317                // the usual CAS convention for cancelling identical factors.
318                _ if a == b => Expr::Const(C::one()),
319                _ => Expr::Div(Box::new(a), Box::new(b)),
320            }
321        }
322        Expr::Pow(a, n) => {
323            let a = simplify(*a);
324            match (a, n) {
325                (_, 0) => Expr::Const(C::one()),
326                (a, 1) => a,
327                (Expr::Const(c), n) => Expr::Const(c.powi(n as i32)),
328                (Expr::Pow(inner, m), n) => match m.checked_mul(n) {
329                    Some(p) => Expr::Pow(inner, p),
330                    None => Expr::Pow(Box::new(Expr::Pow(inner, m)), n),
331                },
332                (a, n) => Expr::Pow(Box::new(a), n),
333            }
334        }
335        Expr::Func(name, a) => {
336            let a = simplify(*a);
337            let folded = match &a {
338                Expr::Const(c) => apply_func(&name, c.clone()),
339                _ => None,
340            };
341            match folded {
342                Some(v) => Expr::Const(v),
343                None => Expr::Func(name, Box::new(a)),
344            }
345        }
346    }
347}
348
349/// Flatten and fold a sum of already-simplified terms.
350fn fold_add<C: Coefficient>(items: Vec<Expr<C>>) -> Expr<C> {
351    let mut stack = items;
352    let mut const_acc = C::zero();
353    let mut terms: Vec<Expr<C>> = Vec::new();
354    while let Some(it) = stack.pop() {
355        match it {
356            Expr::Add(l, r) => {
357                stack.push(*l);
358                stack.push(*r);
359            }
360            Expr::Const(c) => const_acc = const_acc + c,
361            Expr::Neg(inner) => match *inner {
362                Expr::Const(c) => const_acc = const_acc - c,
363                other => terms.push(Expr::Neg(Box::new(other))),
364            },
365            other => terms.push(other),
366        }
367    }
368    // Merge like terms (`2x + 3x` becomes `5x`), keeping first-seen order.
369    let mut groups: Vec<(C, Expr<C>)> = Vec::new();
370    for term in terms {
371        let (coef, base) = split_coefficient(term);
372        match groups.iter_mut().find(|(_, b)| *b == base) {
373            Some((acc, _)) => *acc = acc.clone() + coef,
374            None => groups.push((coef, base)),
375        }
376    }
377    let mut terms: Vec<Expr<C>> = groups
378        .into_iter()
379        .filter(|(c, _)| !c.is_zero_value())
380        .map(|(c, b)| join_coefficient(c, b))
381        .collect();
382    // Sort by printed form, so the order does not depend on the input order. A
383    // second pass then reproduces the first pass's output (a normal form).
384    terms.sort_by_cached_key(|t| t.to_string());
385    if terms.is_empty() {
386        return Expr::Const(const_acc);
387    }
388    let mut iter = terms.into_iter();
389    // Invariant-guarded: `terms` is non-empty because we early-returned above
390    // when `terms.is_empty()`, so `iter.next()` is guaranteed `Some`.
391    let mut result = iter.next().unwrap();
392    for t in iter {
393        result = Expr::Add(Box::new(result), Box::new(t));
394    }
395    if const_acc.is_zero_value() {
396        result
397    } else {
398        Expr::Add(Box::new(Expr::Const(const_acc)), Box::new(result))
399    }
400}
401
402/// Splits a term into `(coefficient, base)` so that like terms can be merged.
403///
404/// `c·b` with a leading constant `c` gives `(c, b)`, `−t` gives `(−1, t)` (or
405/// the negated coefficient of `t`), and anything else gives `(1, term)`.
406fn split_coefficient<C: Coefficient>(term: Expr<C>) -> (C, Expr<C>) {
407    match term {
408        Expr::Mul(l, r) => match *l {
409            Expr::Const(c) => (c, *r),
410            other => (C::one(), Expr::Mul(Box::new(other), r)),
411        },
412        Expr::Neg(inner) => {
413            let (c, base) = split_coefficient(*inner);
414            (C::zero() - c, base)
415        }
416        other => (C::one(), other),
417    }
418}
419
420/// Rebuilds a term from a coefficient and base. The inverse of
421/// [`split_coefficient`] for coefficients other than `0`.
422fn join_coefficient<C: Coefficient>(coef: C, base: Expr<C>) -> Expr<C> {
423    if coef == C::one() {
424        base
425    } else if coef == C::from(-1.0) {
426        Expr::Neg(Box::new(base))
427    } else {
428        Expr::Mul(Box::new(Expr::Const(coef)), Box::new(base))
429    }
430}
431
432/// Flatten and fold a product of already-simplified factors.
433fn fold_mul<C: Coefficient>(items: Vec<Expr<C>>) -> Expr<C> {
434    let mut stack = items;
435    let mut const_acc = C::one();
436    let mut terms: Vec<Expr<C>> = Vec::new();
437    while let Some(it) = stack.pop() {
438        match it {
439            Expr::Mul(l, r) => {
440                stack.push(*l);
441                stack.push(*r);
442            }
443            Expr::Const(c) => {
444                if c.is_zero_value() {
445                    return Expr::Const(C::zero());
446                }
447                const_acc = const_acc * c;
448            }
449            Expr::Neg(inner) => {
450                const_acc = const_acc * C::from(-1.0);
451                stack.push(*inner);
452            }
453            other => terms.push(other),
454        }
455    }
456    if terms.is_empty() {
457        return Expr::Const(const_acc);
458    }
459    // Same canonical ordering as `fold_add`, for the same reason.
460    terms.sort_by_cached_key(|t| t.to_string());
461    let mut iter = terms.into_iter();
462    // Invariant-guarded: `terms` is non-empty because we early-returned above
463    // when `terms.is_empty()`, so `iter.next()` is guaranteed `Some`.
464    let mut result = iter.next().unwrap();
465    for t in iter {
466        result = Expr::Mul(Box::new(result), Box::new(t));
467    }
468    if const_acc == C::one() {
469        result
470    } else {
471        Expr::Mul(Box::new(Expr::Const(const_acc)), Box::new(result))
472    }
473}
474
475/// Approximate a coefficient as `f64`. Parses decimal output and `p/q`
476/// rationals (as printed by exact coefficients); anything unparseable is NaN
477/// rather than a silent 0.
478fn to_f64<C: Coefficient>(c: C) -> f64 {
479    let s = c.to_string();
480    if let Some((p, q)) = s.split_once('/') {
481        match (p.trim().parse::<f64>(), q.trim().parse::<f64>()) {
482            (Ok(p), Ok(q)) => p / q,
483            _ => f64::NAN,
484        }
485    } else {
486        s.trim().parse::<f64>().unwrap_or(f64::NAN)
487    }
488}
489
490/// Fold a named unary function over a numeric coefficient. Returns `None` for
491/// names this crate does not know, so they stay symbolic instead of being
492/// silently treated as the identity.
493fn apply_func<C: Coefficient>(name: &str, c: C) -> Option<C> {
494    let f = func_pointer(name)?;
495    Some(C::from(f(to_f64(c))))
496}
497
498/// The `f64` implementation of a named unary function, or `None` if the name
499/// is unknown. Shared by [`apply_func`] and the closure compiler.
500fn func_pointer(name: &str) -> Option<fn(f64) -> f64> {
501    Some(match name {
502        "sin" => f64::sin,
503        "cos" => f64::cos,
504        "tan" => f64::tan,
505        "exp" => f64::exp,
506        "ln" => f64::ln,
507        "sqrt" => f64::sqrt,
508        "asin" => f64::asin,
509        "acos" => f64::acos,
510        "atan" => f64::atan,
511        "sinh" => f64::sinh,
512        "cosh" => f64::cosh,
513        "tanh" => f64::tanh,
514        _ => return None,
515    })
516}
517
518fn derivative<C: Coefficient>(e: &Expr<C>, var: &str) -> Expr<C> {
519    match e {
520        Expr::Const(_) => Expr::Const(C::zero()),
521        Expr::Var(v) => {
522            if v == var {
523                Expr::Const(C::one())
524            } else {
525                Expr::Const(C::zero())
526            }
527        }
528        Expr::Add(a, b) => derivative(a, var) + derivative(b, var),
529        Expr::Sub(a, b) => derivative(a, var) - derivative(b, var),
530        Expr::Neg(a) => -derivative(a, var),
531        Expr::Mul(a, b) => {
532            let da = derivative(a, var);
533            let db = derivative(b, var);
534            (**a).clone() * db + da * (**b).clone()
535        }
536        Expr::Div(a, b) => {
537            let da = derivative(a, var);
538            let db = derivative(b, var);
539            let bv = (**b).clone();
540            (da * bv.clone() - (**a).clone() * db) / (bv.clone() * bv)
541        }
542        Expr::Pow(a, n) => {
543            if *n == 0 {
544                Expr::Const(C::zero())
545            } else {
546                let da = derivative(a, var);
547                let base = (**a).clone();
548                let n_c = C::from(*n as f64);
549                Expr::Const(n_c) * base.clone().pow(*n - 1) * da
550            }
551        }
552        Expr::Func(name, a) => {
553            let da = derivative(a, var);
554            let inner = (**a).clone();
555            match name.as_str() {
556                "sin" => Expr::func("cos", inner) * da,
557                "cos" => -Expr::func("sin", inner) * da,
558                "exp" => Expr::func("exp", inner) * da,
559                "tan" => {
560                    let sec = Expr::Const(C::one()) + Expr::func("tan", inner.clone()).pow(2);
561                    sec * da
562                }
563                "ln" => da / inner,
564                "sqrt" => da / (Expr::Const(C::from(2.0)) * Expr::func("sqrt", inner)),
565                "asin" => da / Expr::func("sqrt", Expr::Const(C::one()) - inner.clone().pow(2)),
566                "acos" => -da / Expr::func("sqrt", Expr::Const(C::one()) - inner.clone().pow(2)),
567                "atan" => da / (Expr::Const(C::one()) + inner.clone().pow(2)),
568                "sinh" => Expr::func("cosh", inner) * da,
569                "cosh" => Expr::func("sinh", inner) * da,
570                "tanh" => (Expr::Const(C::one()) - Expr::func("tanh", inner).pow(2)) * da,
571                other => Expr::Func(format!("{other}'"), Box::new(inner)) * da,
572            }
573        }
574    }
575}
576
577fn substitute<C: Coefficient>(e: &Expr<C>, var: &str, value: C) -> Expr<C> {
578    match e {
579        Expr::Const(c) => Expr::Const(c.clone()),
580        Expr::Var(v) => {
581            if v == var {
582                Expr::Const(value)
583            } else {
584                Expr::Var(v.clone())
585            }
586        }
587        Expr::Add(a, b) => substitute(a, var, value.clone()) + substitute(b, var, value),
588        Expr::Sub(a, b) => substitute(a, var, value.clone()) - substitute(b, var, value),
589        Expr::Mul(a, b) => substitute(a, var, value.clone()) * substitute(b, var, value),
590        Expr::Div(a, b) => substitute(a, var, value.clone()) / substitute(b, var, value),
591        Expr::Neg(a) => -substitute(a, var, value),
592        Expr::Pow(a, n) => substitute(a, var, value).pow(*n),
593        Expr::Func(name, a) => Expr::Func(name.clone(), Box::new(substitute(a, var, value))),
594    }
595}
596
597fn eval<C: Coefficient>(e: &Expr<C>, env: &HashMap<String, C>) -> Option<C> {
598    match e {
599        Expr::Const(c) => Some(c.clone()),
600        Expr::Var(v) => env.get(v).cloned(),
601        Expr::Add(a, b) => Some(eval(a, env)? + eval(b, env)?),
602        Expr::Sub(a, b) => Some(eval(a, env)? - eval(b, env)?),
603        Expr::Mul(a, b) => Some(eval(a, env)? * eval(b, env)?),
604        Expr::Div(a, b) => {
605            let d = eval(b, env)?;
606            if d.is_zero_value() {
607                None
608            } else {
609                Some(eval(a, env)? / d)
610            }
611        }
612        Expr::Neg(a) => Some(-eval(a, env)?),
613        Expr::Pow(a, n) => Some(eval(a, env)?.powi(*n as i32)),
614        Expr::Func(name, a) => {
615            let v = eval(a, env)?;
616            apply_func(name, v)
617        }
618    }
619}
620
621impl<C: Coefficient> fmt::Display for Expr<C> {
622    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
623        match self {
624            Expr::Const(c) => write!(f, "{c}"),
625            Expr::Var(v) => write!(f, "{v}"),
626            Expr::Add(a, b) => write!(f, "({a} + {b})"),
627            Expr::Sub(a, b) => write!(f, "({a} - {b})"),
628            Expr::Mul(a, b) => write!(f, "({a} * {b})"),
629            Expr::Div(a, b) => write!(f, "({a} / {b})"),
630            Expr::Neg(a) => write!(f, "(-{a})"),
631            Expr::Pow(a, n) => write!(f, "({a}^{n})"),
632            Expr::Func(name, a) => write!(f, "{name}({a})"),
633        }
634    }
635}
636
637#[cfg(feature = "exact")]
638mod exact {
639    use super::*;
640    use std::ops::{Add, Div, Mul, Neg, Sub};
641    use tpt_math_exact::BigRational;
642
643    /// Arbitrary-precision rational wrapper implementing [`Coefficient`].
644    #[derive(Clone, Debug, PartialEq)]
645    pub struct Rational(pub BigRational);
646
647    impl From<f64> for Rational {
648        fn from(f: f64) -> Rational {
649            Rational(BigRational::from_float(f).unwrap_or_else(BigRational::zero))
650        }
651    }
652
653    impl From<BigRational> for Rational {
654        fn from(r: BigRational) -> Rational {
655            Rational(r)
656        }
657    }
658
659    impl fmt::Display for Rational {
660        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
661            write!(f, "{}", self.0)
662        }
663    }
664
665    impl Zero for Rational {
666        fn zero() -> Rational {
667            Rational(BigRational::zero())
668        }
669        fn is_zero(&self) -> bool {
670            self.0.is_zero()
671        }
672    }
673
674    impl One for Rational {
675        fn one() -> Rational {
676            Rational(BigRational::one())
677        }
678    }
679
680    impl Add for Rational {
681        type Output = Rational;
682        fn add(self, rhs: Rational) -> Rational {
683            Rational(self.0 + rhs.0)
684        }
685    }
686    impl Sub for Rational {
687        type Output = Rational;
688        fn sub(self, rhs: Rational) -> Rational {
689            Rational(self.0 - rhs.0)
690        }
691    }
692    impl Mul for Rational {
693        type Output = Rational;
694        fn mul(self, rhs: Rational) -> Rational {
695            Rational(self.0 * rhs.0)
696        }
697    }
698    impl Div for Rational {
699        type Output = Rational;
700        fn div(self, rhs: Rational) -> Rational {
701            Rational(self.0 / rhs.0)
702        }
703    }
704    impl Neg for Rational {
705        type Output = Rational;
706        fn neg(self) -> Rational {
707            Rational(-self.0)
708        }
709    }
710
711    impl Coefficient for Rational {
712        fn powi(self, n: i32) -> Rational {
713            if n >= 0 {
714                let k = n as u32;
715                Rational(BigRational::new(
716                    self.0.numer().pow(k),
717                    self.0.denom().pow(k),
718                ))
719            } else {
720                let k = (-n) as u32;
721                Rational(BigRational::new(
722                    self.0.denom().pow(k),
723                    self.0.numer().pow(k),
724                ))
725            }
726        }
727    }
728
729    /// `Expr<Rational>` — exact, arbitrary-precision symbolic expression.
730    pub type ExprRational = Expr<Rational>;
731}
732
733#[cfg(feature = "exact")]
734pub use exact::{ExprRational, Rational};
735
736#[cfg(test)]
737mod tests {
738    use super::*;
739
740    #[test]
741    fn like_terms_merge_into_one_coefficient() {
742        let x = Expr64::var("x");
743        let e = (x.clone() + x.clone()).simplify();
744        assert_eq!(e, Expr64::constant(2.0) * x.clone());
745        let e = (Expr64::constant(2.0) * x.clone() + Expr64::constant(3.0) * x.clone()).simplify();
746        assert_eq!(e, Expr64::constant(5.0) * x.clone());
747    }
748
749    #[test]
750    fn like_terms_cancel_to_zero() {
751        let x = Expr64::var("x");
752        let e = (x.clone() - x.clone()).simplify();
753        assert_eq!(e, Expr64::constant(0.0));
754        let e = (x.clone() + Expr64::constant(2.0) * x.clone() - Expr64::constant(3.0) * x.clone())
755            .simplify();
756        assert_eq!(e, Expr64::constant(0.0));
757    }
758
759    #[test]
760    fn like_terms_merge_products_with_shared_factors() {
761        // x·y + 2·(x·y) = 3·(x·y).
762        let (x, y) = (Expr64::var("x"), Expr64::var("y"));
763        let xy = x.clone() * y.clone();
764        let e = (xy.clone() + Expr64::constant(2.0) * xy.clone()).simplify();
765        assert_eq!(e, Expr64::constant(3.0) * (x.clone() * y.clone()));
766    }
767
768    #[test]
769    fn like_term_merge_preserves_value() {
770        let x = Expr64::var("x");
771        let raw = x.clone() * x.clone() + Expr64::func("sin", x.clone()) * Expr64::constant(2.0)
772            - x.clone() * x.clone() * Expr64::constant(0.5);
773        let simplified = raw.clone().simplify();
774        for &value in &[-1.3, 0.0, 0.7, 2.5] {
775            let want = raw.eval_str("x", value).unwrap();
776            let got = simplified.eval_str("x", value).unwrap();
777            assert!((got - want).abs() < 1e-12, "x = {value}: {got} vs {want}");
778        }
779    }
780
781    #[test]
782    fn const_folding() {
783        let x = Expr64::var("x");
784        let e = Expr64::from(2.0) * x.clone() + Expr64::from(3.0) - Expr64::from(3.0);
785        let s = e.simplify();
786        assert_eq!(s, Expr64::from(2.0) * x.clone());
787    }
788
789    #[test]
790    fn derivative_polynomial() {
791        // d/dx (x^2) = 2x
792        let x = Expr64::var("x");
793        let d = x.clone().pow(2).derivative("x").simplify();
794        assert_eq!(d.eval_str("x", 4.0).unwrap(), 8.0);
795    }
796
797    #[test]
798    fn derivative_product_rule() {
799        // d/dx (x * (x + 1)) = 2x + 1
800        let x = Expr64::var("x");
801        let e = x.clone() * (x.clone() + Expr64::from(1.0));
802        let d = e.derivative("x").simplify();
803        assert_eq!(d.eval_str("x", 5.0).unwrap(), 11.0);
804    }
805
806    #[test]
807    fn derivative_sin() {
808        // d/dx sin(x) = cos(x)
809        let x = Expr64::var("x");
810        let d = Expr64::func("sin", x.clone()).derivative("x").simplify();
811        let expected = (2.0f64).cos();
812        assert!((d.eval_str("x", 2.0).unwrap() - expected).abs() < 1e-9);
813    }
814
815    #[test]
816    fn substitute_and_eval() {
817        let x = Expr64::var("x");
818        let e = (x.clone() + Expr64::from(1.0)).pow(2);
819        let s = e.substitute("x", 3.0).simplify();
820        assert_eq!(s.eval_str("x", 0.0).unwrap(), 16.0);
821    }
822
823    #[test]
824    fn derivative_is_zero_for_other_var() {
825        let x = Expr64::var("x");
826        let y = Expr64::var("y");
827        let d = (x.clone() + y.clone()).derivative("y").simplify();
828        assert_eq!(d.eval_str("x", 10.0).unwrap(), 1.0);
829    }
830
831    #[test]
832    fn div_by_one_simplifies() {
833        let x = Expr64::var("x");
834        let e = x.clone() / Expr64::from(1.0);
835        assert_eq!(e.simplify(), x);
836    }
837
838    #[test]
839    fn func_of_constant_simplifies() {
840        // sin(0) -> 0
841        let e = Expr64::func("sin", Expr64::from(0.0));
842        assert_eq!(e.simplify(), Expr64::from(0.0));
843    }
844
845    #[test]
846    fn pow_zero_and_one_simplify() {
847        let x = Expr64::var("x");
848        assert_eq!(x.clone().pow(0).simplify(), Expr64::from(1.0));
849        assert_eq!(x.clone().pow(1).simplify(), x);
850    }
851
852    #[test]
853    fn identical_quotient_simplifies_to_one() {
854        // Documented domain caveat: x / x is taken as 1 (undefined at x = 0).
855        let x = Expr64::var("x");
856        assert_eq!((x.clone() / x).simplify(), Expr64::from(1.0));
857    }
858
859    #[test]
860    fn nested_powers_collapse() {
861        let x = Expr64::var("x");
862        assert_eq!(x.clone().pow(2).pow(3).simplify(), x.pow(6));
863    }
864
865    #[test]
866    fn simplify_reaches_fixpoint_after_exposing_pow_one() {
867        // (x^1) * 1 * 2 needs more than one pass to reach `2 * x`.
868        let x = Expr64::var("x");
869        let e = x.clone().pow(1) * Expr64::from(1.0) * Expr64::from(2.0);
870        assert_eq!(e.clone().simplify().simplify(), e.clone().simplify());
871        assert_eq!(e.simplify(), Expr64::from(2.0) * x);
872    }
873
874    #[test]
875    fn pow_of_constant_simplifies() {
876        let e = Expr64::from(2.0).pow(10);
877        assert_eq!(e.simplify(), Expr64::from(1024.0));
878    }
879
880    #[test]
881    fn double_negation_cancels() {
882        let x = Expr64::var("x");
883        let e = -(-x.clone());
884        assert_eq!(e.simplify(), x);
885    }
886
887    #[test]
888    fn eval_unknown_function_is_none() {
889        // An unknown name used to evaluate as the identity.
890        let e = Expr64::func("frobnicate", Expr64::from(2.0));
891        assert_eq!(e.eval(&HashMap::new()), None);
892    }
893
894    #[cfg(feature = "exact")]
895    #[test]
896    fn rational_coefficients_convert_to_f64() {
897        // Rationals print as "p/q"; the old parser turned that into 0.0.
898        assert_eq!(to_f64(exact::Rational::from(0.75)), 0.75);
899    }
900
901    #[test]
902    fn simplify_keeps_unknown_function_symbolic() {
903        let e = Expr64::func("frobnicate", Expr64::from(2.0));
904        assert!(matches!(simplify(e), Expr::Func(ref n, _) if n == "frobnicate"));
905    }
906
907    #[test]
908    fn eval_undefined_variable_is_none() {
909        let x = Expr64::var("x");
910        assert_eq!(x.eval_str("y", 1.0), None);
911    }
912
913    #[test]
914    fn eval_divide_by_zero_is_none() {
915        let expr = Expr64::from(1.0) / Expr64::from(0.0);
916        assert_eq!(expr.eval(&HashMap::new()), None);
917    }
918
919    #[test]
920    fn derivative_quotient_rule() {
921        // d/dx (x / (x + 1)) = 1 / (x + 1)^2; at x = 1 this is 1/4.
922        let x = Expr64::var("x");
923        let e = x.clone() / (x.clone() + Expr64::from(1.0));
924        let d = e.derivative("x").simplify();
925        assert!((d.eval_str("x", 1.0).unwrap() - 0.25).abs() < 1e-9);
926    }
927
928    #[test]
929    fn derivative_cos() {
930        // d/dx cos(x) = -sin(x); at x = 0 this is 0.
931        let x = Expr64::var("x");
932        let d = Expr64::func("cos", x.clone()).derivative("x").simplify();
933        assert!(d.eval_str("x", 0.0).unwrap().abs() < 1e-9);
934    }
935
936    #[test]
937    fn derivative_ln() {
938        // d/dx ln(x) = 1/x; at x = 2 this is 0.5.
939        let x = Expr64::var("x");
940        let d = Expr64::func("ln", x.clone()).derivative("x").simplify();
941        assert!((d.eval_str("x", 2.0).unwrap() - 0.5).abs() < 1e-9);
942    }
943
944    #[test]
945    fn inverse_and_hyperbolic_derivatives_match_finite_differences() {
946        // Compare each symbolic derivative with a central difference at a few
947        // points inside the domain of the inverse functions.
948        let x = Expr64::var("x");
949        for name in ["asin", "acos", "atan", "sinh", "cosh", "tanh"] {
950            let f = Expr64::func(name, x.clone());
951            let d = f.derivative("x").simplify();
952            for &p in &[-0.6, -0.2, 0.1, 0.5] {
953                let h = 1e-6;
954                let fp = f.eval_str("x", p + h).unwrap();
955                let fm = f.eval_str("x", p - h).unwrap();
956                let numeric = (fp - fm) / (2.0 * h);
957                let symbolic = d.eval_str("x", p).unwrap();
958                assert!(
959                    (symbolic - numeric).abs() < 1e-6,
960                    "{name}'({p}): symbolic {symbolic}, numeric {numeric}"
961                );
962            }
963        }
964    }
965
966    #[test]
967    fn inverse_and_hyperbolic_functions_fold_numerically() {
968        // A constant argument is folded by `simplify` through `apply_func`.
969        let folded = |name: &str, v: f64| Expr64::func(name, Expr64::from(v)).simplify();
970        assert_eq!(
971            folded("atan", 1.0),
972            Expr64::from(core::f64::consts::FRAC_PI_4)
973        );
974        assert_eq!(
975            folded("asin", 1.0),
976            Expr64::from(core::f64::consts::FRAC_PI_2)
977        );
978        assert!(matches!(folded("tanh", 0.0), Expr::Const(c) if c == 0.0));
979    }
980
981    #[test]
982    fn derivative_pow_zero_is_zero() {
983        let x = Expr64::var("x");
984        let d = x.clone().pow(0).derivative("x");
985        assert_eq!(d.simplify(), Expr64::from(0.0));
986    }
987}