1#![no_std]
21
22extern crate alloc;
23
24use alloc::{boxed::Box, format, string::String, vec::Vec};
25use core::{fmt, ops};
26
27pub trait Expr: Copy {
29 const MAYBE: bool = false;
33 fn maybe(&self) -> bool {
36 Self::MAYBE
37 }
38
39 fn eval(&self, env: &[f64]) -> f64;
40 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64;
48 fn lower(&self) -> Ast;
49}
50
51fn powi(x: f64, n: i32) -> f64 {
54 let mut acc = 1.0;
55 for _ in 0..n.unsigned_abs() {
56 acc *= x;
57 }
58 match n < 0 {
59 true => 1.0 / acc,
60 false => acc,
61 }
62}
63
64fn sign(x: f64) -> f64 {
65 if x > 0.0 {
66 1.0
67 } else if x < 0.0 {
68 -1.0
69 } else {
70 0.0
71 }
72}
73
74macro_rules! defined_over {
87 ($op:literal, $($v:expr),+ $(,)?) => {$(
88 debug_assert!(
89 !$v.is_nan(),
90 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"),
91 $v
92 );
93 )+};
94}
95
96fn takes_left(strictly: bool, rv: f64) -> bool {
102 strictly || rv.is_nan()
103}
104
105macro_rules! lattice {
108 (propagates; $A:ident, $B:ident) => {
109 <$A>::MAYBE | <$B>::MAYBE
110 };
111 (propagates; $A:ident) => {
112 <$A>::MAYBE
113 };
114 (skips; $A:ident, $B:ident) => {
115 <$A>::MAYBE & <$B>::MAYBE
116 };
117 (never; $($T:ident),+) => {
118 false
119 };
120}
121
122macro_rules! grad_fn {
132 (linear; ($a:ident, $b:ident) $body:block; $val:ident; [$ga:expr, $gb:expr]; $seed:ident) => {
133 fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
134 let $a = self.0.grad(env, $ga, grad);
135 let $b = self.1.grad(env, $gb, grad);
136 $body
137 }
138 };
139 (linear; ($a:ident) $body:block; $val:ident; [$ga:expr]; $seed:ident) => {
140 fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
141 let $a = self.0.grad(env, $ga, grad);
142 $body
143 }
144 };
145 (chain; ($a:ident, $b:ident) $body:block; $val:ident; [$ga:expr, $gb:expr]; $seed:ident) => {
146 fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
147 let $a = self.0.eval(env);
148 let $b = self.1.eval(env);
149 let $val = $body;
150 self.0.grad(env, $ga, grad);
151 self.1.grad(env, $gb, grad);
152 $val
153 }
154 };
155 (chain; ($a:ident) $body:block; $val:ident; [$ga:expr]; $seed:ident) => {
156 fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
157 let $a = self.0.eval(env);
158 let $val = $body;
159 self.0.grad(env, $ga, grad);
160 $val
161 }
162 };
163 (skip; ($a:ident, $b:ident) $body:block; $val:ident; [$x:ident < $y:ident]; $seed:ident) => {
164 fn grad(&self, env: &[f64], $seed: f64, grad: &mut [f64]) -> f64 {
165 let $a = self.0.eval(env);
166 let $b = self.1.eval(env);
167 match takes_left($x < $y, $b) {
168 true => self.0.grad(env, $seed, grad),
169 false => self.1.grad(env, $seed, grad),
170 }
171 }
172 };
173 (flat; ($($a:ident),+) $body:block; $val:ident; []; $seed:ident) => {
174 fn grad(&self, env: &[f64], _: f64, _: &mut [f64]) -> f64 {
175 self.eval(env)
176 }
177 };
178}
179
180macro_rules! strictly_case {
184 (skip; $node:ident, $V:path,($a:ident, $b:ident),[$x:ident < $y:ident]) => {
185 if let $V($a, $b) = $node {
186 return Ast::Cmp(Box::new((**$x).clone()), Box::new((**$y).clone()));
187 }
188 };
189 ($shape:tt; $node:ident, $V:path,($a:ident, $b:ident),[$($g:tt)*]) => {};
190}
191
192macro_rules! ops {
208 (
209 binds($seed:ident, $val:ident);
210 binary { $(
211 $(#[$bm:meta])*
212 $B:ident($ba:ident, $bb:ident) $blat:tt $bbody:block $bshape:tt [$($bg:tt)*] $btex:literal $bfmt:literal $bop:literal;
213 )+ }
214 unary { $(
215 $(#[$um:meta])*
216 $U:ident($ua:ident) $ulat:tt $ubody:block $ushape:tt [$($ug:tt)*] $utex:literal $ufmt:literal $uop:literal;
217 )+ }
218 irregular { $(
219 $(#[$im:meta])*
220 $I:ident($($ity:ty),+);
221 )+ }
222 eval($eenv:ident) { $($earm:tt)* }
223 latex($lnames:ident) { $($larm:tt)* }
224 display($dout:ident) { $($darm:tt)* }
225 trace($tenv:ident) { $($tarm:tt)* }
226 ) => {
227 $(
228 $(#[$bm])*
229 #[derive(Clone, Copy)]
230 pub struct $B<L, R>(pub L, pub R);
231
232 impl<L: Expr, R: Expr> Expr for $B<L, R> {
233 const MAYBE: bool = lattice!($blat; L, R);
234
235 fn eval(&self, env: &[f64]) -> f64 {
236 let $ba = self.0.eval(env);
237 let $bb = self.1.eval(env);
238 $bbody
239 }
240
241 grad_fn!($bshape; ($ba, $bb) $bbody; $val; [$($bg)*]; $seed);
242
243 fn lower(&self) -> Ast {
244 Ast::$B(Box::new(self.0.lower()), Box::new(self.1.lower()))
245 }
246 }
247 )+
248
249 $(
250 $(#[$um])*
251 #[derive(Clone, Copy)]
252 pub struct $U<E>(pub E);
253
254 impl<E: Expr> Expr for $U<E> {
255 const MAYBE: bool = lattice!($ulat; E);
256
257 fn eval(&self, env: &[f64]) -> f64 {
258 let $ua = self.0.eval(env);
259 $ubody
260 }
261
262 grad_fn!($ushape; ($ua) $ubody; $val; [$($ug)*]; $seed);
263
264 fn lower(&self) -> Ast {
265 Ast::$U(Box::new(self.0.lower()))
266 }
267 }
268 )+
269
270 #[derive(Clone, Debug, PartialEq)]
274 pub enum Ast {
275 $($(#[$im])* $I($($ity),+),)+
276 $($(#[$bm])* $B(Box<Ast>, Box<Ast>),)+
277 $($(#[$um])* $U(Box<Ast>),)+
278 }
279
280 impl Ast {
281 fn strictly(&self) -> Ast {
286 $(strictly_case!($bshape; self, Ast::$B, ($ba, $bb), [$($bg)*]);)+
287 panic!("no row named a comparison for this node, so nothing here skips an absent operand")
288 }
289
290 pub fn eval(&self, $eenv: &[f64]) -> f64 {
291 match self {
292 $(Ast::$B($ba, $bb) => { let $ba = $ba.eval($eenv); let $bb = $bb.eval($eenv); $bbody })+
293 $(Ast::$U($ua) => { let $ua = $ua.eval($eenv); $ubody })+
294 $($earm)*
295 }
296 }
297
298 pub fn latex(&self, $lnames: &[&str]) -> String {
299 match self {
300 $(Ast::$B($ba, $bb) => format!($btex, $ba.latex($lnames), $bb.latex($lnames)),)+
301 $(Ast::$U($ua) => format!($utex, $ua.latex($lnames)),)+
302 $($larm)*
303 }
304 }
305
306 pub fn trace(&self, $tenv: &[f64]) -> Trace {
309 let val = self.eval($tenv);
310 let (op, kids) = match self {
311 $(Ast::$B($ba, $bb) => ($bop, alloc::vec![$ba.trace($tenv), $bb.trace($tenv)]),)+
312 $(Ast::$U($ua) => ($uop, alloc::vec![$ua.trace($tenv)]),)+
313 $($tarm)*
314 };
315 Trace { op, val, kids }
316 }
317 }
318
319 impl fmt::Display for Ast {
322 fn fmt(&self, $dout: &mut fmt::Formatter<'_>) -> fmt::Result {
323 match self {
324 $(Ast::$B($ba, $bb) => write!($dout, $bfmt, $ba, $bb),)+
325 $(Ast::$U($ua) => write!($dout, $ufmt, $ua),)+
326 $($darm)*
327 }
328 }
329 }
330 };
331}
332
333ops! {
334 binds(seed, val);
337
338 binary {
339 Add(l, r) propagates { l + r } linear [seed, seed] "\\left({} + {}\\right)" "({} + {})" "+";
340 Sub(l, r) propagates { l - r } linear [seed, -seed] "\\left({} - {}\\right)" "({} - {})" "-";
341 Mul(l, r) propagates { l * r } chain [seed * r, seed * l] "\\left({} \\cdot {}\\right)" "({} * {})" "*";
342 Div(l, r) propagates { l / r } chain [seed / r, -seed * l / (r * r)] "\\frac{{{}}}{{{}}}" "({} / {})" "/";
343 Min(l, r) skips { l.min(r) } skip [l < r] "\\min\\left({}, {}\\right)" "min({}, {})" "min";
346 Max(l, r) skips { l.max(r) } skip [r < l] "\\max\\left({}, {}\\right)" "max({}, {})" "max";
347 Cmp(l, r) never { defined_over!("cmp", l, r); f64::from(l < r) } flat [] "\\left[{} < {}\\right]" "[{} < {}]" "<";
351 }
352
353 unary {
354 Neg(e) propagates { -e } linear [-seed] "-{}" "(-{})" "neg";
355 Square(e) propagates { e * e } chain [seed * 2.0 * e] "{}^{{2}}" "{}^2" "sq";
356 Abs(e) propagates { e.abs() } chain [seed * sign(e)] "\\left|{}\\right|" "|{}|" "abs";
359 Sqrt(e) propagates { libm::sqrt(e) } chain [seed / (2.0 * val)] "\\sqrt{{{}}}" "sqrt({})" "sqrt";
362 Exp(e) propagates { libm::exp(e) } chain [seed * val] "e^{{{}}}" "exp({})" "exp";
363 IsNan(e) never { f64::from(e.is_nan()) } flat [] "\\left[{} = \\varnothing\\right]" "[{} absent]" "absent?";
368 }
369
370 irregular {
374 Const(f64);
375 Var(usize);
376 Powi(Box<Ast>, i32);
377 Select(Box<Ast>, Box<Ast>, Box<Ast>);
379 Sum(Vec<Ast>);
380 }
381
382 eval(env) {
383 Ast::Const(c) => *c,
384 Ast::Var(i) => env[*i],
385 Ast::Powi(e, n) => powi(e.eval(env), *n),
386 Ast::Select(c, a, b) => {
387 let c = c.eval(env);
388 defined_over!("select's condition", c);
389 match c != 0.0 {
390 true => a.eval(env),
391 false => b.eval(env),
392 }
393 }
394 Ast::Sum(xs) => xs.iter().map(|e| e.eval(env)).sum(),
395 }
396
397 latex(names) {
398 Ast::Const(c) => format!("{c}"),
399 Ast::Var(i) => names.get(*i).map_or_else(|| format!("x_{{{i}}}"), |n| String::from(*n)),
400 Ast::Powi(e, n) => format!("{}^{{{n}}}", e.latex(names)),
401 Ast::Select(c, a, b) => format!(
402 "\\begin{{cases}}{} & {} \\\\ {} & \\text{{otherwise}}\\end{{cases}}",
403 a.latex(names),
404 c.latex(names),
405 b.latex(names)
406 ),
407 Ast::Sum(xs) => {
408 let parts: Vec<String> = xs.iter().map(|e| e.latex(names)).collect();
409 format!("\\left({}\\right)", parts.join(" + "))
410 }
411 }
412
413 display(f) {
414 Ast::Const(c) => write!(f, "{c}"),
415 Ast::Var(i) => write!(f, "x{i}"),
416 Ast::Powi(e, n) => write!(f, "{e}^{n}"),
417 Ast::Select(c, a, b) => write!(f, "({a} if {c} else {b})"),
418 Ast::Sum(xs) => {
419 f.write_str("(")?;
420 for (i, e) in xs.iter().enumerate() {
421 if i > 0 {
422 f.write_str(" + ")?;
423 }
424 write!(f, "{e}")?;
425 }
426 f.write_str(")")
427 }
428 }
429
430 trace(env) {
431 Ast::Const(_) => ("const", Vec::new()),
432 Ast::Var(_) => ("var", Vec::new()),
433 Ast::Powi(e, _) => ("powi", alloc::vec![e.trace(env)]),
434 Ast::Select(c, a, b) => (
437 "select",
438 match c.eval(env) != 0.0 {
439 true => alloc::vec![c.trace(env), a.trace(env)],
440 false => alloc::vec![c.trace(env), b.trace(env)],
441 },
442 ),
443 Ast::Sum(xs) => ("sum", xs.iter().map(|e| e.trace(env)).collect()),
444 }
445}
446
447#[derive(Clone, Copy)]
449pub struct Var<const I: usize>;
450#[derive(Clone, Copy)]
453pub struct VarAt(pub usize);
454#[derive(Clone, Copy)]
456pub struct Const(pub f64);
457#[derive(Clone, Copy)]
461pub struct Absent;
462#[derive(Clone, Copy)]
464pub struct Powi<E, const N: i32>(pub E);
465#[derive(Clone, Copy)]
468pub struct Select<C, A, B>(pub C, pub A, pub B);
469#[derive(Clone, Copy)]
473pub struct Or<X, F>(pub X, pub F);
474#[derive(Clone, Copy)]
476pub struct Sum<E, const N: usize>(pub [E; N]);
477
478impl<const I: usize> Expr for Var<I> {
479 fn eval(&self, env: &[f64]) -> f64 {
480 env[I]
481 }
482
483 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
484 grad[I] += seed;
485 env[I]
486 }
487
488 fn lower(&self) -> Ast {
489 Ast::Var(I)
490 }
491}
492
493impl Expr for VarAt {
494 fn eval(&self, env: &[f64]) -> f64 {
495 env[self.0]
496 }
497
498 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
499 grad[self.0] += seed;
500 env[self.0]
501 }
502
503 fn lower(&self) -> Ast {
504 Ast::Var(self.0)
505 }
506}
507
508impl Expr for Const {
509 fn eval(&self, _: &[f64]) -> f64 {
510 self.0
511 }
512
513 fn grad(&self, _: &[f64], _: f64, _: &mut [f64]) -> f64 {
514 self.0
515 }
516
517 fn lower(&self) -> Ast {
518 Ast::Const(self.0)
519 }
520}
521
522impl Expr for Absent {
523 const MAYBE: bool = true;
524
525 fn eval(&self, _: &[f64]) -> f64 {
526 f64::NAN
527 }
528
529 fn grad(&self, _: &[f64], _: f64, _: &mut [f64]) -> f64 {
530 f64::NAN
531 }
532
533 fn lower(&self) -> Ast {
534 Ast::Const(f64::NAN)
535 }
536}
537
538impl<E: Expr, const N: i32> Expr for Powi<E, N> {
539 const MAYBE: bool = E::MAYBE;
540
541 fn eval(&self, env: &[f64]) -> f64 {
542 powi(self.0.eval(env), N)
543 }
544
545 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
546 let v = self.0.eval(env);
547 self.0.grad(env, seed * f64::from(N) * powi(v, N - 1), grad);
548 powi(v, N)
549 }
550
551 fn lower(&self) -> Ast {
552 Ast::Powi(Box::new(self.0.lower()), N)
553 }
554}
555
556impl<X: Expr, F: Expr> Expr for Or<X, F> {
557 const MAYBE: bool = F::MAYBE;
558
559 fn eval(&self, env: &[f64]) -> f64 {
560 let x = self.0.eval(env);
561 match x.is_nan() {
562 true => self.1.eval(env),
563 false => x,
564 }
565 }
566
567 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
568 match self.0.eval(env).is_nan() {
569 true => self.1.grad(env, seed, grad),
570 false => self.0.grad(env, seed, grad),
571 }
572 }
573
574 fn lower(&self) -> Ast {
577 let x = self.0.lower();
578 Ast::Select(Box::new(Ast::IsNan(Box::new(x.clone()))), Box::new(self.1.lower()), Box::new(x))
579 }
580}
581
582impl<C: Expr, A: Expr, B: Expr> Expr for Select<C, A, B> {
583 const MAYBE: bool = A::MAYBE | B::MAYBE;
586
587 fn eval(&self, env: &[f64]) -> f64 {
588 let c = self.0.eval(env);
589 defined_over!("select's condition", c);
590 match c != 0.0 {
591 true => self.1.eval(env),
592 false => self.2.eval(env),
593 }
594 }
595
596 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
597 let c = self.0.eval(env);
598 defined_over!("select's condition", c);
599 match c != 0.0 {
600 true => self.1.grad(env, seed, grad),
601 false => self.2.grad(env, seed, grad),
602 }
603 }
604
605 fn lower(&self) -> Ast {
606 Ast::Select(Box::new(self.0.lower()), Box::new(self.1.lower()), Box::new(self.2.lower()))
607 }
608}
609
610impl<E: Expr, const N: usize> Expr for Sum<E, N> {
611 const MAYBE: bool = E::MAYBE;
612
613 fn eval(&self, env: &[f64]) -> f64 {
614 self.0.iter().map(|e| e.eval(env)).sum()
615 }
616
617 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
618 self.0.iter().map(|e| e.grad(env, seed, grad)).sum()
619 }
620
621 fn lower(&self) -> Ast {
622 Ast::Sum(self.0.iter().map(Expr::lower).collect())
623 }
624}
625
626pub trait Slots: Copy {
630 const LEN: usize;
631 const MAYBE: bool = false;
634 fn width(&self) -> usize {
636 Self::LEN
637 }
638
639 fn maybe(&self) -> bool {
640 Self::MAYBE
641 }
642
643 fn eval_slots(&self, env: &[f64], out: &mut [f64]);
644 fn grad_slots(&self, env: &[f64], jac: &mut [f64]);
646 fn lower_slots(&self) -> Vec<Ast>;
647}
648
649impl<T: Expr> Slots for Ex<T> {
652 const LEN: usize = 1;
653 const MAYBE: bool = T::MAYBE;
654
655 fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
656 out[0] = self.eval(env);
657 }
658
659 fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
660 self.grad(env, 1.0, jac);
661 }
662
663 fn lower_slots(&self) -> Vec<Ast> {
664 alloc::vec![self.lower()]
665 }
666}
667
668macro_rules! slots_tuple {
671 ($($T:ident $i:tt),+) => {
672 impl<$($T: Slots),+> Slots for ($($T,)+) {
673 const LEN: usize = 0 $(+ $T::LEN)+;
674 const MAYBE: bool = $($T::MAYBE)|+;
675
676 fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
677 let mut at = 0;
678 $(
679 self.$i.eval_slots(env, &mut out[at..at + $T::LEN]);
680 at += $T::LEN;
681 )+
682 debug_assert_eq!(at, Self::LEN);
683 }
684
685 fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
686 let (w, mut at) = (env.len(), 0);
687 $(
688 self.$i.grad_slots(env, &mut jac[at * w..(at + $T::LEN) * w]);
689 at += $T::LEN;
690 )+
691 debug_assert_eq!(at, Self::LEN);
692 }
693
694 fn lower_slots(&self) -> Vec<Ast> {
695 let mut out = Vec::with_capacity(Self::LEN);
696 $(out.extend(self.$i.lower_slots());)+
697 out
698 }
699 }
700 };
701}
702slots_tuple!(A 0, B 1);
703slots_tuple!(A 0, B 1, C 2);
704slots_tuple!(A 0, B 1, C 2, D 3);
705slots_tuple!(A 0, B 1, C 2, D 3, E 4);
706
707impl<S: Slots, const N: usize> Slots for [S; N] {
708 const LEN: usize = N * S::LEN;
709 const MAYBE: bool = S::MAYBE;
710
711 fn eval_slots(&self, env: &[f64], out: &mut [f64]) {
712 for (k, s) in self.iter().enumerate() {
713 s.eval_slots(env, &mut out[k * S::LEN..(k + 1) * S::LEN]);
714 }
715 }
716
717 fn grad_slots(&self, env: &[f64], jac: &mut [f64]) {
718 for (s, jac) in self.iter().zip(jac.chunks_exact_mut(S::LEN * env.len())) {
719 s.grad_slots(env, jac);
720 }
721 }
722
723 fn lower_slots(&self) -> Vec<Ast> {
724 self.iter().flat_map(Slots::lower_slots).collect()
725 }
726}
727
728#[derive(Clone, Copy)]
731pub struct Ex<T: Expr>(pub T);
732
733impl<T: Expr> Expr for Ex<T> {
734 const MAYBE: bool = T::MAYBE;
735
736 fn eval(&self, env: &[f64]) -> f64 {
737 self.0.eval(env)
738 }
739
740 fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64 {
741 self.0.grad(env, seed, grad)
742 }
743
744 fn lower(&self) -> Ast {
745 self.0.lower()
746 }
747}
748
749#[derive(Clone, Copy)]
752pub struct Vars;
753impl Vars {
754 pub fn get<const I: usize>(self) -> Ex<Var<I>> {
755 Ex(Var)
756 }
757
758 pub fn at(self, i: usize) -> Ex<VarAt> {
759 Ex(VarAt(i))
760 }
761}
762
763pub fn constant(c: f64) -> Ex<Const> {
764 Ex(Const(c))
765}
766pub fn absent() -> Ex<Absent> {
770 Ex(Absent)
771}
772pub fn present<T: Expr>(x: Ex<T>) -> Ex<Sub<Const, IsNan<T>>> {
776 Ex(Sub(Const(1.0), IsNan(x.0)))
777}
778pub fn or<T: Expr, F: Expr>(x: Ex<T>, fallback: Ex<F>) -> Ex<Or<T, F>> {
781 Ex(Or(x.0, fallback.0))
782}
783pub fn square<T: Expr>(x: Ex<T>) -> Ex<Square<T>> {
784 Ex(Square(x.0))
785}
786pub fn abs<T: Expr>(x: Ex<T>) -> Ex<Abs<T>> {
787 Ex(Abs(x.0))
788}
789pub fn sum<T: Expr, const N: usize>(xs: [Ex<T>; N]) -> Ex<Sum<T, N>> {
790 Ex(Sum(xs.map(|x| x.0)))
791}
792pub fn sqrt<T: Expr>(x: Ex<T>) -> Ex<Sqrt<T>> {
793 Ex(Sqrt(x.0))
794}
795pub fn exp<T: Expr>(x: Ex<T>) -> Ex<Exp<T>> {
796 Ex(Exp(x.0))
797}
798pub fn powi_of<T: Expr, const N: i32>(x: Ex<T>) -> Ex<Powi<T, N>> {
799 Ex(Powi(x.0))
800}
801pub fn min<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Min<L, R>> {
802 Ex(Min(l.0, r.0))
803}
804pub fn max<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Max<L, R>> {
805 Ex(Max(l.0, r.0))
806}
807pub fn lt<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Cmp<L, R>> {
811 const {
812 assert!(
813 !L::MAYBE && !R::MAYBE,
814 "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"
815 )
816 }
817 Ex(Cmp(l.0, r.0))
818}
819pub fn gt<L: Expr, R: Expr>(l: Ex<L>, r: Ex<R>) -> Ex<Cmp<R, L>> {
821 const {
822 assert!(
823 !L::MAYBE && !R::MAYBE,
824 "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"
825 )
826 }
827 Ex(Cmp(r.0, l.0))
828}
829pub fn select<C: Expr, A: Expr, B: Expr>(c: Ex<C>, a: Ex<A>, b: Ex<B>) -> Ex<Select<C, A, B>> {
832 const {
833 assert!(
834 !C::MAYBE,
835 "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"
836 )
837 }
838 Ex(Select(c.0, a.0, b.0))
839}
840
841impl<L: Expr, R: Expr> ops::Add<Ex<R>> for Ex<L> {
842 type Output = Ex<Add<L, R>>;
843
844 fn add(self, rhs: Ex<R>) -> Self::Output {
845 Ex(Add(self.0, rhs.0))
846 }
847}
848impl<L: Expr, R: Expr> ops::Sub<Ex<R>> for Ex<L> {
849 type Output = Ex<Sub<L, R>>;
850
851 fn sub(self, rhs: Ex<R>) -> Self::Output {
852 Ex(Sub(self.0, rhs.0))
853 }
854}
855impl<L: Expr, R: Expr> ops::Mul<Ex<R>> for Ex<L> {
856 type Output = Ex<Mul<L, R>>;
857
858 fn mul(self, rhs: Ex<R>) -> Self::Output {
859 Ex(Mul(self.0, rhs.0))
860 }
861}
862impl<L: Expr, R: Expr> ops::Div<Ex<R>> for Ex<L> {
863 type Output = Ex<Div<L, R>>;
864
865 fn div(self, rhs: Ex<R>) -> Self::Output {
866 Ex(Div(self.0, rhs.0))
867 }
868}
869impl<E: Expr> ops::Neg for Ex<E> {
870 type Output = Ex<Neg<E>>;
871
872 fn neg(self) -> Self::Output {
873 Ex(Neg(self.0))
874 }
875}
876
877fn skipping(l: &Ast, r: &Ast, strictly: Ast, var: usize) -> Ast {
882 let b = |a: Ast| Box::new(a);
883 let (dl, dr) = (l.diff(var), r.diff(var));
884 Ast::Select(
885 b(Ast::IsNan(b(r.clone()))),
886 b(dl.clone()),
887 b(Ast::Select(b(Ast::IsNan(b(l.clone()))), b(dr.clone()), b(Ast::Select(b(strictly), b(dl), b(dr))))),
888 )
889}
890
891fn fold1(e: Ast, mk: impl FnOnce(Box<Ast>) -> Ast) -> Ast {
894 let konst = matches!(e, Ast::Const(_));
895 let n = mk(Box::new(e));
896 match konst {
897 true => Ast::Const(n.eval(&[])),
898 false => n,
899 }
900}
901
902fn fold2(l: Ast, r: Ast, mk: impl FnOnce(Box<Ast>, Box<Ast>) -> Ast) -> Ast {
903 let konst = matches!((&l, &r), (Ast::Const(_), Ast::Const(_)));
904 let n = mk(Box::new(l), Box::new(r));
905 match konst {
906 true => Ast::Const(n.eval(&[])),
907 false => n,
908 }
909}
910
911impl Ast {
914 pub fn diff(&self, var: usize) -> Ast {
917 let b = |a: Ast| Box::new(a);
918 match self {
919 Ast::Const(_) => Ast::Const(0.0),
920 Ast::Var(i) => Ast::Const((*i == var) as u8 as f64),
921 Ast::Add(l, r) => Ast::Add(b(l.diff(var)), b(r.diff(var))),
922 Ast::Sub(l, r) => Ast::Sub(b(l.diff(var)), b(r.diff(var))),
923 Ast::Mul(l, r) => Ast::Add(b(Ast::Mul(b(l.diff(var)), r.clone())), b(Ast::Mul(l.clone(), b(r.diff(var))))),
924 Ast::Div(l, r) => Ast::Div(
925 b(Ast::Sub(b(Ast::Mul(b(l.diff(var)), r.clone())), b(Ast::Mul(l.clone(), b(r.diff(var)))))),
926 b(Ast::Square(r.clone())),
927 ),
928 Ast::Neg(e) => Ast::Neg(b(e.diff(var))),
929 Ast::Square(e) => Ast::Mul(b(Ast::Const(2.0)), b(Ast::Mul(e.clone(), b(e.diff(var))))),
930 Ast::Abs(e) => Ast::Mul(b(Ast::Div(e.clone(), b(Ast::Abs(e.clone())))), b(e.diff(var))),
933 Ast::Sqrt(e) => Ast::Div(b(e.diff(var)), b(Ast::Mul(b(Ast::Const(2.0)), b(Ast::Sqrt(e.clone()))))),
934 Ast::Exp(e) => Ast::Mul(b(Ast::Exp(e.clone())), b(e.diff(var))),
935 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))),
936 Ast::Min(l, r) | Ast::Max(l, r) => skipping(l, r, self.strictly(), var),
941 Ast::Cmp(_, _) | Ast::IsNan(_) => Ast::Const(0.0),
942 Ast::Select(c, a, b_) => Ast::Select(c.clone(), b(a.diff(var)), b(b_.diff(var))),
943 Ast::Sum(xs) => Ast::Sum(xs.iter().map(|e| e.diff(var)).collect()),
944 }
945 }
946
947 pub fn simplify(&self) -> Ast {
949 let konst = |a: &Ast| match a {
950 Ast::Const(c) => Some(*c),
951 _ => None,
952 };
953 match self {
954 Ast::Const(_) | Ast::Var(_) => self.clone(),
955 Ast::Add(l, r) => {
956 let (l, r) = (l.simplify(), r.simplify());
957 match (konst(&l), konst(&r)) {
958 (Some(a), Some(b)) => Ast::Const(a + b),
959 (Some(0.0), _) => r,
960 (_, Some(0.0)) => l,
961 _ => Ast::Add(Box::new(l), Box::new(r)),
962 }
963 }
964 Ast::Sub(l, r) => {
965 let (l, r) = (l.simplify(), r.simplify());
966 match (konst(&l), konst(&r)) {
967 (Some(a), Some(b)) => Ast::Const(a - b),
968 (_, Some(0.0)) => l,
969 (Some(0.0), _) => Ast::Neg(Box::new(r)).simplify(),
970 _ => Ast::Sub(Box::new(l), Box::new(r)),
971 }
972 }
973 Ast::Mul(l, r) => {
974 let (l, r) = (l.simplify(), r.simplify());
975 match (konst(&l), konst(&r)) {
976 (Some(a), Some(b)) => Ast::Const(a * b),
977 (Some(0.0), _) | (_, Some(0.0)) => Ast::Const(0.0),
978 (Some(1.0), _) => r,
979 (_, Some(1.0)) => l,
980 _ => Ast::Mul(Box::new(l), Box::new(r)),
981 }
982 }
983 Ast::Div(l, r) => {
984 let (l, r) = (l.simplify(), r.simplify());
985 match (konst(&l), konst(&r)) {
986 (Some(a), Some(b)) => Ast::Const(a / b),
987 (Some(0.0), _) => Ast::Const(0.0),
988 (_, Some(1.0)) => l,
989 _ => Ast::Div(Box::new(l), Box::new(r)),
990 }
991 }
992 Ast::Neg(e) => {
993 let e = e.simplify();
994 match e {
995 Ast::Const(c) => Ast::Const(-c),
996 Ast::Neg(inner) => *inner,
997 _ => Ast::Neg(Box::new(e)),
998 }
999 }
1000 Ast::Square(e) => fold1(e.simplify(), Ast::Square),
1003 Ast::Abs(e) => fold1(e.simplify(), Ast::Abs),
1004 Ast::Sqrt(e) => fold1(e.simplify(), Ast::Sqrt),
1005 Ast::Exp(e) => fold1(e.simplify(), Ast::Exp),
1006 Ast::Min(l, r) => fold2(l.simplify(), r.simplify(), Ast::Min),
1007 Ast::Max(l, r) => fold2(l.simplify(), r.simplify(), Ast::Max),
1008 Ast::Cmp(l, r) => fold2(l.simplify(), r.simplify(), Ast::Cmp),
1009 Ast::IsNan(e) => fold1(e.simplify(), Ast::IsNan),
1013 Ast::Powi(e, n) => {
1014 let e = e.simplify();
1015 match (konst(&e), n) {
1016 (None, 0) => Ast::Const(1.0),
1017 (None, 1) => e,
1018 _ => fold1(e, |e| Ast::Powi(e, *n)),
1019 }
1020 }
1021 Ast::Select(c, a, b) => {
1022 let (c, a, b) = (c.simplify(), a.simplify(), b.simplify());
1023 match konst(&c) {
1024 Some(c) if c != 0.0 => a,
1025 Some(_) => b,
1026 None if a == b => a,
1028 None => Ast::Select(Box::new(c), Box::new(a), Box::new(b)),
1029 }
1030 }
1031 Ast::Sum(xs) => {
1032 let mut acc = 0.0;
1033 let mut rest: Vec<Ast> = Vec::new();
1034 for x in xs.iter().map(Ast::simplify) {
1035 match x {
1036 Ast::Const(c) => acc += c,
1037 other => rest.push(other),
1038 }
1039 }
1040 if acc != 0.0 || rest.is_empty() {
1041 rest.push(Ast::Const(acc));
1042 }
1043 if rest.len() == 1 { rest.pop().expect("len == 1") } else { Ast::Sum(rest) }
1044 }
1045 }
1046 }
1047}
1048
1049pub struct Trace {
1052 pub op: &'static str,
1053 pub val: f64,
1054 pub kids: Vec<Trace>,
1055}
1056
1057impl Trace {
1058 fn fmt_kids(&self, f: &mut fmt::Formatter<'_>, prefix: &str) -> fmt::Result {
1059 for (i, k) in self.kids.iter().enumerate() {
1060 let last = i == self.kids.len() - 1;
1061 let conn = if last { "└──" } else { "├──" };
1062 write!(f, "\n{prefix}{conn}◉ {}: {}", k.op, k.val)?;
1063 let child = format!("{prefix}{}", if last { " " } else { "│ " });
1064 k.fmt_kids(f, &child)?;
1065 }
1066 Ok(())
1067 }
1068}
1069
1070impl fmt::Display for Trace {
1071 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1072 write!(f, "◉ {}: {}", self.op, self.val)?;
1073 self.fmt_kids(f, "")
1074 }
1075}