#![no_std]
extern crate alloc;
use alloc::{boxed::Box, format, string::String, vec::Vec};
use core::{fmt, ops};
pub trait Expr: Copy {
const MAYBE: bool = false;
fn maybe(&self) -> bool {
Self::MAYBE
}
fn eval(&self, env: &[f64]) -> f64;
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64;
fn lower(&self) -> Ast;
}
fn powi(x: f64, n: i32) -> f64 {
let mut acc = 1.0;
for _ in 0..n.unsigned_abs() {
acc *= x;
}
match n < 0 {
true => 1.0 / acc,
false => acc,
}
}
fn sign(x: f64) -> f64 {
if x > 0.0 {
1.0
} else if x < 0.0 {
-1.0
} else {
0.0
}
}
macro_rules! defined_over {
($op:literal, $($v:expr),+ $(,)?) => {$(
debug_assert!(
!$v.is_nan(),
concat!($op, " over a NaN operand ({}): an absent reading is a declination and belongs at the element boundary, where it is the out — inside a tree it has no agreed branch"),
$v
);
)+};
}
fn takes_left(strictly: bool, rv: f64) -> bool {
strictly || rv.is_nan()
}
macro_rules! lattice {
(propagates; $A:ident, $B:ident) => {
<$A>::MAYBE | <$B>::MAYBE
};
(propagates; $A:ident) => {
<$A>::MAYBE
};
(skips; $A:ident, $B:ident) => {
<$A>::MAYBE & <$B>::MAYBE
};
(never; $($T:ident),+) => {
false
};
}
macro_rules! grad_fn {
(linear; ($a:ident, $b:ident) $body:block; $val:ident; [$ga:expr, $gb:expr]; $seed:ident) => {
fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
let $a = self.0.grad(env, $ga, grad);
let $b = self.1.grad(env, $gb, grad);
$body
}
};
(linear; ($a:ident) $body:block; $val:ident; [$ga:expr]; $seed:ident) => {
fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
let $a = self.0.grad(env, $ga, grad);
$body
}
};
(chain; ($a:ident, $b:ident) $body:block; $val:ident; [$ga:expr, $gb:expr]; $seed:ident) => {
fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
let $a = self.0.eval(env);
let $b = self.1.eval(env);
let $val = $body;
self.0.grad(env, $ga, grad);
self.1.grad(env, $gb, grad);
$val
}
};
(chain; ($a:ident) $body:block; $val:ident; [$ga:expr]; $seed:ident) => {
fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
let $a = self.0.eval(env);
let $val = $body;
self.0.grad(env, $ga, grad);
$val
}
};
(skip; ($a:ident, $b:ident) $body:block; $val:ident; [$x:ident < $y:ident]; $seed:ident) => {
fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
let $a = self.0.eval(env);
let $b = self.1.eval(env);
match takes_left($x < $y, $b) {
true => self.0.grad(env, $seed, grad),
false => self.1.grad(env, $seed, grad),
}
}
};
(flat; ($($a:ident),+) $body:block; $val:ident; []; $seed:ident) => {
fn grad(&self, env: &[f64], _: f64, _: &mut [f64]) -> f64 {
self.eval(env)
}
};
}
macro_rules! strictly_case {
(skip; $node:ident, $V:path,($a:ident, $b:ident),[$x:ident < $y:ident]) => {
if let $V($a, $b) = $node {
return Ast::Cmp(Box::new((**$x).clone()), Box::new((**$y).clone()));
}
};
($shape:tt; $node:ident, $V:path,($a:ident, $b:ident),[$($g:tt)*]) => {};
}
macro_rules! ops {
(
binds($seed:ident, $val:ident);
binary { $(
$(#[$bm:meta])*
$B:ident($ba:ident, $bb:ident) $blat:tt $bbody:block $bshape:tt [$($bg:tt)*] $btex:literal $bfmt:literal $bop:literal;
)+ }
unary { $(
$(#[$um:meta])*
$U:ident($ua:ident) $ulat:tt $ubody:block $ushape:tt [$($ug:tt)*] $utex:literal $ufmt:literal $uop:literal;
)+ }
irregular { $(
$(#[$im:meta])*
$I:ident($($ity:ty),+);
)+ }
eval($eenv:ident) { $($earm:tt)* }
latex($lnames:ident) { $($larm:tt)* }
display($dout:ident) { $($darm:tt)* }
trace($tenv:ident) { $($tarm:tt)* }
) => {
$(
$(#[$bm])*
#[derive(Clone, Copy)]
pub struct $B<L, R>(pub L, pub R);
impl<L: Expr, R: Expr> Expr for $B<L, R> {
const MAYBE: bool = lattice!($blat; L, R);
fn eval(&self, env: &[f64]) -> f64 {
let $ba = self.0.eval(env);
let $bb = self.1.eval(env);
$bbody
}
grad_fn!($bshape; ($ba, $bb) $bbody; $val; [$($bg)*]; $seed);
fn lower(&self) -> Ast {
Ast::$B(Box::new(self.0.lower()), Box::new(self.1.lower()))
}
}
)+
$(
$(#[$um])*
#[derive(Clone, Copy)]
pub struct $U<E>(pub E);
impl<E: Expr> Expr for $U<E> {
const MAYBE: bool = lattice!($ulat; E);
fn eval(&self, env: &[f64]) -> f64 {
let $ua = self.0.eval(env);
$ubody
}
grad_fn!($ushape; ($ua) $ubody; $val; [$($ug)*]; $seed);
fn lower(&self) -> Ast {
Ast::$U(Box::new(self.0.lower()))
}
}
)+
#[derive(Clone, Debug, PartialEq)]
pub enum Ast {
$($(#[$im])* $I($($ity),+),)+
$($(#[$bm])* $B(Box<Ast>, Box<Ast>),)+
$($(#[$um])* $U(Box<Ast>),)+
}
impl Ast {
fn strictly(&self) -> Ast {
$(strictly_case!($bshape; self, Ast::$B, ($ba, $bb), [$($bg)*]);)+
panic!("no row named a comparison for this node, so nothing here skips an absent operand")
}
pub fn eval(&self, $eenv: &[f64]) -> f64 {
match self {
$(Ast::$B($ba, $bb) => { let $ba = $ba.eval($eenv); let $bb = $bb.eval($eenv); $bbody })+
$(Ast::$U($ua) => { let $ua = $ua.eval($eenv); $ubody })+
$($earm)*
}
}
pub fn latex(&self, $lnames: &[&str]) -> String {
match self {
$(Ast::$B($ba, $bb) => format!($btex, $ba.latex($lnames), $bb.latex($lnames)),)+
$(Ast::$U($ua) => format!($utex, $ua.latex($lnames)),)+
$($larm)*
}
}
pub fn trace(&self, $tenv: &[f64]) -> Trace {
let val = self.eval($tenv);
let (op, kids) = match self {
$(Ast::$B($ba, $bb) => ($bop, alloc::vec![$ba.trace($tenv), $bb.trace($tenv)]),)+
$(Ast::$U($ua) => ($uop, alloc::vec![$ua.trace($tenv)]),)+
$($tarm)*
};
Trace { op, val, kids }
}
}
impl fmt::Display for Ast {
fn fmt(&self, $dout: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
$(Ast::$B($ba, $bb) => write!($dout, $bfmt, $ba, $bb),)+
$(Ast::$U($ua) => write!($dout, $ufmt, $ua),)+
$($darm)*
}
}
}
};
}
ops! {
binds(seed, val);
binary {
Add(l, r) propagates { l + r } linear [seed, seed] "\\left({} + {}\\right)" "({} + {})" "+";
Sub(l, r) propagates { l - r } linear [seed, -seed] "\\left({} - {}\\right)" "({} - {})" "-";
Mul(l, r) propagates { l * r } chain [seed * r, seed * l] "\\left({} \\cdot {}\\right)" "({} * {})" "*";
Div(l, r) propagates { l / r } chain [seed / r, -seed * l / (r * r)] "\\frac{{{}}}{{{}}}" "({} / {})" "/";
Min(l, r) skips { l.min(r) } skip [l < r] "\\min\\left({}, {}\\right)" "min({}, {})" "min";
Max(l, r) skips { l.max(r) } skip [r < l] "\\max\\left({}, {}\\right)" "max({}, {})" "max";
Cmp(l, r) never { defined_over!("cmp", l, r); f64::from(l < r) } flat [] "\\left[{} < {}\\right]" "[{} < {}]" "<";
}
unary {
Neg(e) propagates { -e } linear [-seed] "-{}" "(-{})" "neg";
Square(e) propagates { e * e } chain [seed * 2.0 * e] "{}^{{2}}" "{}^2" "sq";
Abs(e) propagates { e.abs() } chain [seed * sign(e)] "\\left|{}\\right|" "|{}|" "abs";
Sqrt(e) propagates { libm::sqrt(e) } chain [seed / (2.0 * val)] "\\sqrt{{{}}}" "sqrt({})" "sqrt";
Exp(e) propagates { libm::exp(e) } chain [seed * val] "e^{{{}}}" "exp({})" "exp";
IsNan(e) never { f64::from(e.is_nan()) } flat [] "\\left[{} = \\varnothing\\right]" "[{} absent]" "absent?";
}
irregular {
Const(f64);
Var(usize);
Powi(Box<Ast>, i32);
Select(Box<Ast>, Box<Ast>, Box<Ast>);
Sum(Vec<Ast>);
}
eval(env) {
Ast::Const(c) => *c,
Ast::Var(i) => env[*i],
Ast::Powi(e, n) => powi(e.eval(env), *n),
Ast::Select(c, a, b) => {
let c = c.eval(env);
defined_over!("select's condition", c);
match c != 0.0 {
true => a.eval(env),
false => b.eval(env),
}
}
Ast::Sum(xs) => xs.iter().map(|e| e.eval(env)).sum(),
}
latex(names) {
Ast::Const(c) => format!("{c}"),
Ast::Var(i) => names.get(*i).map_or_else(|| format!("x_{{{i}}}"), |n| String::from(*n)),
Ast::Powi(e, n) => format!("{}^{{{n}}}", e.latex(names)),
Ast::Select(c, a, b) => format!(
"\\begin{{cases}}{} & {} \\\\ {} & \\text{{otherwise}}\\end{{cases}}",
a.latex(names),
c.latex(names),
b.latex(names)
),
Ast::Sum(xs) => {
let parts: Vec<String> = xs.iter().map(|e| e.latex(names)).collect();
format!("\\left({}\\right)", parts.join(" + "))
}
}
display(f) {
Ast::Const(c) => write!(f, "{c}"),
Ast::Var(i) => write!(f, "x{i}"),
Ast::Powi(e, n) => write!(f, "{e}^{n}"),
Ast::Select(c, a, b) => write!(f, "({a} if {c} else {b})"),
Ast::Sum(xs) => {
f.write_str("(")?;
for (i, e) in xs.iter().enumerate() {
if i > 0 {
f.write_str(" + ")?;
}
write!(f, "{e}")?;
}
f.write_str(")")
}
}
trace(env) {
Ast::Const(_) => ("const", Vec::new()),
Ast::Var(_) => ("var", Vec::new()),
Ast::Powi(e, _) => ("powi", alloc::vec![e.trace(env)]),
Ast::Select(c, a, b) => (
"select",
match c.eval(env) != 0.0 {
true => alloc::vec![c.trace(env), a.trace(env)],
false => alloc::vec![c.trace(env), b.trace(env)],
},
),
Ast::Sum(xs) => ("sum", xs.iter().map(|e| e.trace(env)).collect()),
}
}
#[derive(Clone, Copy)]
pub struct Var<const I: usize>;
#[derive(Clone, Copy)]
pub struct VarAt(pub usize);
#[derive(Clone, Copy)]
pub struct Const(pub f64);
#[derive(Clone, Copy)]
pub struct Absent;
#[derive(Clone, Copy)]
pub struct Powi<E, const N: i32>(pub E);
#[derive(Clone, Copy)]
pub struct Select<C, A, B>(pub C, pub A, pub B);
#[derive(Clone, Copy)]
pub struct Or<X, F>(pub X, pub F);
#[derive(Clone, Copy)]
pub struct Sum<E, const N: usize>(pub [E; N]);
impl<const I: usize> Expr for Var<I> {
fn eval(&self, env: &[f64]) -> f64 {
env[I]
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
grad[I] += seed;
env[I]
}
fn lower(&self) -> Ast {
Ast::Var(I)
}
}
impl Expr for VarAt {
fn eval(&self, env: &[f64]) -> f64 {
env[self.0]
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
grad[self.0] += seed;
env[self.0]
}
fn lower(&self) -> Ast {
Ast::Var(self.0)
}
}
impl Expr for Const {
fn eval(&self, _: &[f64]) -> f64 {
self.0
}
fn grad(&self, _: &[f64], _: f64, _: &mut [f64]) -> f64 {
self.0
}
fn lower(&self) -> Ast {
Ast::Const(self.0)
}
}
impl Expr for Absent {
const MAYBE: bool = true;
fn eval(&self, _: &[f64]) -> f64 {
f64::NAN
}
fn grad(&self, _: &[f64], _: f64, _: &mut [f64]) -> f64 {
f64::NAN
}
fn lower(&self) -> Ast {
Ast::Const(f64::NAN)
}
}
impl<E: Expr, const N: i32> Expr for Powi<E, N> {
const MAYBE: bool = E::MAYBE;
fn eval(&self, env: &[f64]) -> f64 {
powi(self.0.eval(env), N)
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
let v = self.0.eval(env);
self.0.grad(env, seed * f64::from(N) * powi(v, N - 1), grad);
powi(v, N)
}
fn lower(&self) -> Ast {
Ast::Powi(Box::new(self.0.lower()), N)
}
}
impl<X: Expr, F: Expr> Expr for Or<X, F> {
const MAYBE: bool = F::MAYBE;
fn eval(&self, env: &[f64]) -> f64 {
let x = self.0.eval(env);
match x.is_nan() {
true => self.1.eval(env),
false => x,
}
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
match self.0.eval(env).is_nan() {
true => self.1.grad(env, seed, grad),
false => self.0.grad(env, seed, grad),
}
}
fn lower(&self) -> Ast {
let x = self.0.lower();
Ast::Select(Box::new(Ast::IsNan(Box::new(x.clone()))), Box::new(self.1.lower()), Box::new(x))
}
}
impl<C: Expr, A: Expr, B: Expr> Expr for Select<C, A, B> {
const MAYBE: bool = A::MAYBE | B::MAYBE;
fn eval(&self, env: &[f64]) -> f64 {
let c = self.0.eval(env);
defined_over!("select's condition", c);
match c != 0.0 {
true => self.1.eval(env),
false => self.2.eval(env),
}
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
let c = self.0.eval(env);
defined_over!("select's condition", c);
match c != 0.0 {
true => self.1.grad(env, seed, grad),
false => self.2.grad(env, seed, grad),
}
}
fn lower(&self) -> Ast {
Ast::Select(Box::new(self.0.lower()), Box::new(self.1.lower()), Box::new(self.2.lower()))
}
}
impl<E: Expr, const N: usize> Expr for Sum<E, N> {
const MAYBE: bool = E::MAYBE;
fn eval(&self, env: &[f64]) -> f64 {
self.0.iter().map(|e| e.eval(env)).sum()
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
self.0.iter().map(|e| e.grad(env, seed, grad)).sum()
}
fn lower(&self) -> Ast {
Ast::Sum(self.0.iter().map(Expr::lower).collect())
}
}
pub trait Slots: Copy {
const LEN: usize;
const MAYBE: bool = false;
fn width(&self) -> usize {
Self::LEN
}
fn maybe(&self) -> bool {
Self::MAYBE
}
fn eval_slots(&self, env: &[f64], out: &mut [f64]);
fn grad_slots(&self, env: &[f64], jac: &mut [f64]);
fn lower_slots(&self) -> Vec<Ast>;
}
impl<T: Expr> Slots for Ex<T> {
const LEN: usize = 1;
const MAYBE: bool = T::MAYBE;
fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
out[0] = self.eval(env);
}
fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
self.grad(env, 1.0, jac);
}
fn lower_slots(&self) -> Vec<Ast> {
alloc::vec![self.lower()]
}
}
macro_rules! slots_tuple {
($($T:ident $i:tt),+) => {
impl<$($T: Slots),+> Slots for ($($T,)+) {
const LEN: usize = 0 $(+ $T::LEN)+;
const MAYBE: bool = $($T::MAYBE)|+;
fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
let mut at = 0;
$(
self.$i.eval_slots(env, &mut out[at..at + $T::LEN]);
at += $T::LEN;
)+
debug_assert_eq!(at, Self::LEN);
}
fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
let (w, mut at) = (env.len(), 0);
$(
self.$i.grad_slots(env, &mut jac[at * w..(at + $T::LEN) * w]);
at += $T::LEN;
)+
debug_assert_eq!(at, Self::LEN);
}
fn lower_slots(&self) -> Vec<Ast> {
let mut out = Vec::with_capacity(Self::LEN);
$(out.extend(self.$i.lower_slots());)+
out
}
}
};
}
slots_tuple!(A 0, B 1);
slots_tuple!(A 0, B 1, C 2);
slots_tuple!(A 0, B 1, C 2, D 3);
slots_tuple!(A 0, B 1, C 2, D 3, E 4);
impl<S: Slots, const N: usize> Slots for [S; N] {
const LEN: usize = N * S::LEN;
const MAYBE: bool = S::MAYBE;
fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
for (k, s) in self.iter().enumerate() {
s.eval_slots(env, &mut out[k * S::LEN..(k + 1) * S::LEN]);
}
}
fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
for (s, jac) in self.iter().zip(jac.chunks_exact_mut(S::LEN * env.len())) {
s.grad_slots(env, jac);
}
}
fn lower_slots(&self) -> Vec<Ast> {
self.iter().flat_map(Slots::lower_slots).collect()
}
}
#[derive(Clone, Copy)]
pub struct Ex<T: Expr>(pub T);
impl<T: Expr> Expr for Ex<T> {
const MAYBE: bool = T::MAYBE;
fn eval(&self, env: &[f64]) -> f64 {
self.0.eval(env)
}
fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
self.0.grad(env, seed, grad)
}
fn lower(&self) -> Ast {
self.0.lower()
}
}
#[derive(Clone, Copy)]
pub struct Vars;
impl Vars {
pub fn get<const I: usize>(self) -> Ex<Var<I>> {
Ex(Var)
}
pub fn at(self, i: usize) -> Ex<VarAt> {
Ex(VarAt(i))
}
}
pub fn constant(c: f64) -> Ex<Const> {
Ex(Const(c))
}
pub fn absent() -> Ex<Absent> {
Ex(Absent)
}
pub fn present<T: Expr>(x: Ex<T>) -> Ex<Sub<Const, IsNan<T>>> {
Ex(Sub(Const(1.0), IsNan(x.0)))
}
pub fn or<T: Expr, F: Expr>(x: Ex<T>, fallback: Ex<F>) -> Ex<Or<T, F>> {
Ex(Or(x.0, fallback.0))
}
pub fn square<T: Expr>(x: Ex<T>) -> Ex<Square<T>> {
Ex(Square(x.0))
}
pub fn abs<T: Expr>(x: Ex<T>) -> Ex<Abs<T>> {
Ex(Abs(x.0))
}
pub fn sum<T: Expr, const N: usize>(xs: [Ex<T>; N]) -> Ex<Sum<T, N>> {
Ex(Sum(xs.map(|x| x.0)))
}
pub fn sqrt<T: Expr>(x: Ex<T>) -> Ex<Sqrt<T>> {
Ex(Sqrt(x.0))
}
pub fn exp<T: Expr>(x: Ex<T>) -> Ex<Exp<T>> {
Ex(Exp(x.0))
}
pub fn powi_of<T: Expr, const N: i32>(x: Ex<T>) -> Ex<Powi<T, N>> {
Ex(Powi(x.0))
}
pub fn min<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Min<L, R>> {
Ex(Min(l.0, r.0))
}
pub fn max<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Max<L, R>> {
Ex(Max(l.0, r.0))
}
pub fn lt<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Cmp<L, R>> {
const {
assert!(
!L::MAYBE && !R::MAYBE,
"nothing compares a reading that may not be there: `or(x, d)` it against a number, or drop the comparison and let the absence propagate"
)
}
Ex(Cmp(l.0, r.0))
}
pub fn gt<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Cmp<R, L>> {
const {
assert!(
!L::MAYBE && !R::MAYBE,
"nothing compares a reading that may not be there: `or(x, d)` it against a number, or drop the comparison and let the absence propagate"
)
}
Ex(Cmp(r.0, l.0))
}
pub fn select<C: Expr, A: Expr, B: Expr>(c: Ex<C>, a: Ex<A>, b: Ex<B>) -> Ex<Select<C, A, B>> {
const {
assert!(
!C::MAYBE,
"a `Select` condition that may not be there decides nothing: `present(x)` is the test over an absence, and the branches are where one is written"
)
}
Ex(Select(c.0, a.0, b.0))
}
impl<L: Expr, R: Expr> ops::Add<Ex<R>> for Ex<L> {
type Output = Ex<Add<L, R>>;
fn add(self, rhs: Ex<R>) -> Self::Output {
Ex(Add(self.0, rhs.0))
}
}
impl<L: Expr, R: Expr> ops::Sub<Ex<R>> for Ex<L> {
type Output = Ex<Sub<L, R>>;
fn sub(self, rhs: Ex<R>) -> Self::Output {
Ex(Sub(self.0, rhs.0))
}
}
impl<L: Expr, R: Expr> ops::Mul<Ex<R>> for Ex<L> {
type Output = Ex<Mul<L, R>>;
fn mul(self, rhs: Ex<R>) -> Self::Output {
Ex(Mul(self.0, rhs.0))
}
}
impl<L: Expr, R: Expr> ops::Div<Ex<R>> for Ex<L> {
type Output = Ex<Div<L, R>>;
fn div(self, rhs: Ex<R>) -> Self::Output {
Ex(Div(self.0, rhs.0))
}
}
impl<E: Expr> ops::Neg for Ex<E> {
type Output = Ex<Neg<E>>;
fn neg(self) -> Self::Output {
Ex(Neg(self.0))
}
}
fn skipping(l: &Ast, r: &Ast, strictly: Ast, var: usize) -> Ast {
let b = |a: Ast| Box::new(a);
let (dl, dr) = (l.diff(var), r.diff(var));
Ast::Select(
b(Ast::IsNan(b(r.clone()))),
b(dl.clone()),
b(Ast::Select(b(Ast::IsNan(b(l.clone()))), b(dr.clone()), b(Ast::Select(b(strictly), b(dl), b(dr))))),
)
}
fn fold1(e: Ast, mk: impl FnOnce(Box<Ast>) -> Ast) -> Ast {
let konst = matches!(e, Ast::Const(_));
let n = mk(Box::new(e));
match konst {
true => Ast::Const(n.eval(&[])),
false => n,
}
}
fn fold2(l: Ast, r: Ast, mk: impl FnOnce(Box<Ast>, Box<Ast>) -> Ast) -> Ast {
let konst = matches!((&l, &r), (Ast::Const(_), Ast::Const(_)));
let n = mk(Box::new(l), Box::new(r));
match konst {
true => Ast::Const(n.eval(&[])),
false => n,
}
}
impl Ast {
pub fn diff(&self, var: usize) -> Ast {
let b = |a: Ast| Box::new(a);
match self {
Ast::Const(_) => Ast::Const(0.0),
Ast::Var(i) => Ast::Const((*i == var) as u8 as f64),
Ast::Add(l, r) => Ast::Add(b(l.diff(var)), b(r.diff(var))),
Ast::Sub(l, r) => Ast::Sub(b(l.diff(var)), b(r.diff(var))),
Ast::Mul(l, r) => Ast::Add(b(Ast::Mul(b(l.diff(var)), r.clone())), b(Ast::Mul(l.clone(), b(r.diff(var))))),
Ast::Div(l, r) => Ast::Div(
b(Ast::Sub(b(Ast::Mul(b(l.diff(var)), r.clone())), b(Ast::Mul(l.clone(), b(r.diff(var)))))),
b(Ast::Square(r.clone())),
),
Ast::Neg(e) => Ast::Neg(b(e.diff(var))),
Ast::Square(e) => Ast::Mul(b(Ast::Const(2.0)), b(Ast::Mul(e.clone(), b(e.diff(var))))),
Ast::Abs(e) => Ast::Mul(b(Ast::Div(e.clone(), b(Ast::Abs(e.clone())))), b(e.diff(var))),
Ast::Sqrt(e) => Ast::Div(b(e.diff(var)), b(Ast::Mul(b(Ast::Const(2.0)), b(Ast::Sqrt(e.clone()))))),
Ast::Exp(e) => Ast::Mul(b(Ast::Exp(e.clone())), b(e.diff(var))),
Ast::Powi(e, n) => Ast::Mul(b(Ast::Mul(b(Ast::Const(f64::from(*n))), b(Ast::Powi(e.clone(), n - 1)))), b(e.diff(var))),
Ast::Min(l, r) | Ast::Max(l, r) => skipping(l, r, self.strictly(), var),
Ast::Cmp(_, _) | Ast::IsNan(_) => Ast::Const(0.0),
Ast::Select(c, a, b_) => Ast::Select(c.clone(), b(a.diff(var)), b(b_.diff(var))),
Ast::Sum(xs) => Ast::Sum(xs.iter().map(|e| e.diff(var)).collect()),
}
}
pub fn simplify(&self) -> Ast {
let konst = |a: &Ast| match a {
Ast::Const(c) => Some(*c),
_ => None,
};
match self {
Ast::Const(_) | Ast::Var(_) => self.clone(),
Ast::Add(l, r) => {
let (l, r) = (l.simplify(), r.simplify());
match (konst(&l), konst(&r)) {
(Some(a), Some(b)) => Ast::Const(a + b),
(Some(0.0), _) => r,
(_, Some(0.0)) => l,
_ => Ast::Add(Box::new(l), Box::new(r)),
}
}
Ast::Sub(l, r) => {
let (l, r) = (l.simplify(), r.simplify());
match (konst(&l), konst(&r)) {
(Some(a), Some(b)) => Ast::Const(a - b),
(_, Some(0.0)) => l,
(Some(0.0), _) => Ast::Neg(Box::new(r)).simplify(),
_ => Ast::Sub(Box::new(l), Box::new(r)),
}
}
Ast::Mul(l, r) => {
let (l, r) = (l.simplify(), r.simplify());
match (konst(&l), konst(&r)) {
(Some(a), Some(b)) => Ast::Const(a * b),
(Some(0.0), _) | (_, Some(0.0)) => Ast::Const(0.0),
(Some(1.0), _) => r,
(_, Some(1.0)) => l,
_ => Ast::Mul(Box::new(l), Box::new(r)),
}
}
Ast::Div(l, r) => {
let (l, r) = (l.simplify(), r.simplify());
match (konst(&l), konst(&r)) {
(Some(a), Some(b)) => Ast::Const(a / b),
(Some(0.0), _) => Ast::Const(0.0),
(_, Some(1.0)) => l,
_ => Ast::Div(Box::new(l), Box::new(r)),
}
}
Ast::Neg(e) => {
let e = e.simplify();
match e {
Ast::Const(c) => Ast::Const(-c),
Ast::Neg(inner) => *inner,
_ => Ast::Neg(Box::new(e)),
}
}
Ast::Square(e) => fold1(e.simplify(), Ast::Square),
Ast::Abs(e) => fold1(e.simplify(), Ast::Abs),
Ast::Sqrt(e) => fold1(e.simplify(), Ast::Sqrt),
Ast::Exp(e) => fold1(e.simplify(), Ast::Exp),
Ast::Min(l, r) => fold2(l.simplify(), r.simplify(), Ast::Min),
Ast::Max(l, r) => fold2(l.simplify(), r.simplify(), Ast::Max),
Ast::Cmp(l, r) => fold2(l.simplify(), r.simplify(), Ast::Cmp),
Ast::IsNan(e) => fold1(e.simplify(), Ast::IsNan),
Ast::Powi(e, n) => {
let e = e.simplify();
match (konst(&e), n) {
(None, 0) => Ast::Const(1.0),
(None, 1) => e,
_ => fold1(e, |e| Ast::Powi(e, *n)),
}
}
Ast::Select(c, a, b) => {
let (c, a, b) = (c.simplify(), a.simplify(), b.simplify());
match konst(&c) {
Some(c) if c != 0.0 => a,
Some(_) => b,
None if a == b => a,
None => Ast::Select(Box::new(c), Box::new(a), Box::new(b)),
}
}
Ast::Sum(xs) => {
let mut acc = 0.0;
let mut rest: Vec<Ast> = Vec::new();
for x in xs.iter().map(Ast::simplify) {
match x {
Ast::Const(c) => acc += c,
other => rest.push(other),
}
}
if acc != 0.0 || rest.is_empty() {
rest.push(Ast::Const(acc));
}
if rest.len() == 1 { rest.pop().expect("len == 1") } else { Ast::Sum(rest) }
}
}
}
}
pub struct Trace {
pub op: &'static str,
pub val: f64,
pub kids: Vec<Trace>,
}
impl Trace {
fn fmt_kids(&self, f: &mut fmt::Formatter<'_>, prefix: &str) -> fmt::Result {
for (i, k) in self.kids.iter().enumerate() {
let last = i == self.kids.len() - 1;
let conn = if last { "└──" } else { "├──" };
write!(f, "\n{prefix}{conn}◉ {}: {}", k.op, k.val)?;
let child = format!("{prefix}{}", if last { " " } else { "│ " });
k.fmt_kids(f, &child)?;
}
Ok(())
}
}
impl fmt::Display for Trace {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "◉ {}: {}", self.op, self.val)?;
self.fmt_kids(f, "")
}
}