Skip to main content

trading_data_expr/
lib.rs

1//! A typed primitive algebra: one expression value, four readings — evaluate, differentiate
2//! (exact), document (LaTeX/infix), debug (value-annotated trace). à la Jane Street's
3//! "Computations that differentiate, debug and document themselves".
4//!
5//! The tree is nested `Copy` marker structs ([`Var`]/[`Const`]/[`Add`]/…), zero heap on the
6//! compute path; [`Expr::eval`] monomorphizes to straight-line FMA and [`Expr::grad`] accumulates
7//! exact partials by the chain rule. [`Expr::lower`] projects to the runtime [`Ast`] enum for the
8//! documentation/debug readings, where `alloc` is fine (a LaTeX string allocates anyway).
9//!
10//! [`Const`] is the sole `f64 → Expr` door; there is no `Expr → f64 → Expr` escape, so a
11//! `trading_data_dag::Symbolic` body *cannot* compute any other way — the algebra is load-bearing.
12//!
13//! The two planes are one declaration: the `ops!` table below emits the marker struct, its
14//! [`Expr`] impl, the [`Ast`] variant and every mechanical walk over it from one row per operator,
15//! so `Expr::eval` and `Ast::eval` cannot say different things about the same operator. What a row
16//! cannot state — [`Ast::diff`]'s per-operator mathematics and [`Ast::simplify`]'s per-operator
17//! identities — is written out below it, and the operators no row fits ([`Const`], [`Var`], [`VarAt`],
18//! [`Powi`], [`Select`], [`Sum`], [`Absent`], [`Or`]) are declared beside the table as the
19//! exceptions they are.
20#![no_std]
21
22extern crate alloc;
23
24use alloc::{boxed::Box, format, string::String, vec::Vec};
25use core::{fmt, ops};
26
27/// One expression node: evaluate, accumulate exact partials, or project to [`Ast`].
28pub trait Expr: Copy {
29	/// Whether this expression may evaluate to no number at all — a declination the out plane reads
30	/// back as absence (`r[impl outs.absence.typed]`). [`Absent`] is the only leaf that sets it; every
31	/// operator derives it, by `|` where absence propagates and by `&` where it is skipped.
32	const MAYBE: bool = false;
33	/// So a kernel holding an opaque `impl Expr` can ask, as it asks [`Slots::width`]: RPITIT leaves
34	/// `<Body as Expr>::MAYBE` unnameable in a bound at the site that would state it.
35	fn maybe(&self) -> bool {
36		Self::MAYBE
37	}
38
39	fn eval(&self, env: &[f64]) -> f64;
40	/// Chain-rule pass: returns `self`'s value and adds `seed · ∂self/∂env[i]` into `grad[i]`
41	/// (`grad.len() == env.len()`). `seed` is `∂output/∂self` — 1.0 at the root.
42	///
43	/// ponytail: a `chain` row re-`eval`s a subtree then `grad` re-walks it — `T(s) = s + 2·T(s/2)`,
44	/// i.e. O(n·log n), exact and fine for the shallow scalar kernels this serves; switch to
45	/// single-pass reverse-mode over a small tape (cached node values) only if a genuinely
46	/// large/deep kernel appears.
47	fn grad(&self, env: &[f64], seed: f64, grad: &mut [f64]) -> f64;
48	fn lower(&self) -> Ast;
49}
50
51/// `f64::powi` is std-only; repeated multiplication is exact for the small exponents this serves and
52/// keeps the crate `no_std` without a second libm call.
53fn 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
74/// A NaN operand has no agreed branch under `Cmp` and under a `Select` *condition*: one reads it as
75/// false and the other as *taken*, so the value and the slope come off different branches and
76/// nothing in the array says so. [`Expr::MAYBE`] is what keeps a declination out of both at compile
77/// time; this is the backstop for the NaN no type can predict — the one arithmetic produces, `0/0`
78/// inside a tree.
79///
80/// [`Min`]/[`Max`] are *not* here: they are defined over an absent operand, they skip it, and
81/// `MAYBE` says which side comes out (`r[impl outs.absence.typed]`).
82///
83/// Debug-only because `r[kernels.pure.zero-cost]` is an equality in retired instructions: a release
84/// build of a `Pure` node costs what the same arithmetic written by hand costs, and a branch here
85/// would be a branch the hand-written version does not have.
86macro_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
96/// Whether a `Min`/`Max` takes its **left** operand, given the strict comparison that decides it
97/// where both are numbers. The tie goes right; an absent right is skipped, and an absent left is
98/// skipped by the comparison already being false. Which way round the comparison goes is the `skip`
99/// row's to say, and it says it once — this reads it, and `Ast::strictly` reads the same tokens as
100/// a tree, so the value's branch and the symbolic derivative's cannot be written apart.
101fn takes_left(strictly: bool, rv: f64) -> bool {
102	strictly || rv.is_nan()
103}
104
105/// The definedness lattice a row names, over the operand types it is written across
106/// (`r[impl outs.absence.typed]`).
107macro_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
122/// [`Expr::grad`] for one row, in the shape the row names. The four shapes are the four ways a seed
123/// reaches an operand, and the shape is what decides how many passes it costs:
124///
125/// - `linear` — the partials are constants, so each child's own `grad` return *is* its value and
126///   there is no evaluation pass at all;
127/// - `chain` — the partials read the operand values, so those are evaluated first and the seed
128///   expressions may name them and the node's own value;
129/// - `skip` — the whole seed goes to the one operand that came out, absence skipped;
130/// - `flat` — the value is piecewise constant, so no seed reaches either side.
131macro_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
180/// [`grad_fn`]'s `skip` shape read on the other plane: the same two operands in the same order, as
181/// a tree rather than as a comparison over numbers. Every other shape contributes nothing, which is
182/// what leaves `Ast::strictly` answering for the rows that named a comparison and no others.
183macro_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
192/// One row per operator, and both planes are read off it: the `Copy` marker struct and its [`Expr`]
193/// impl on the compute path, the [`Ast`] variant and every mechanical walk over it on the
194/// documentation path. A row is
195///
196/// ```text
197/// Name(operands) lattice { value } grad-shape [seeds] "latex" "infix" "trace";
198/// ```
199///
200/// The value expression is written **once** and emitted into `Expr::eval`, into the row's gradient,
201/// and into `Ast::eval` — which is the point: two evaluators of one semantics that cannot be edited
202/// apart. `Ast::diff` and `Ast::simplify` are not here because they are not mechanical: a
203/// derivative is per-operator mathematics and an identity is a per-operator claim, and a row that
204/// carried a closure for each would have bought nothing. What a `skip` row states *is* mechanical,
205/// though, and reaches them: its comparison is emitted twice, once over numbers for `Expr::grad`
206/// and once as a tree for `Ast::strictly`, so `Ast::diff` names the branch without restating it.
207macro_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		/// The runtime projection of an [`Expr`], for the documentation/debug readings only:
271		/// [`Ast::diff`] (exact symbolic derivative), [`Ast::simplify`], [`Ast::latex`]/[`fmt::Display`],
272		/// and [`Ast::trace`].
273		#[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			/// The comparison a `skip` row named, over the operands in the order it named them — the
282			/// same order [`Expr::grad`] branches on, so the value's branch and the symbolic
283			/// derivative's are one declaration. Panics off a `skip` row, which is a caller matching
284			/// something the table did not mark skipping.
285			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			/// Value-annotated tree: every node paired with its value under `env`, for the box-drawing
307			/// debug view.
308			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		/// Plain infix over `x_i` metavariables (parens on every compound), the display-dual of
320		/// [`Ast::latex`].
321		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	// `seed` is `Expr::grad`'s incoming seed and `val` the node's own value; both are named at this
335	// site because a binding a macro makes for itself is invisible to the tokens written here.
336	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		/// Skipped, not propagated: `min(absent, x)` is `x`, so the result is absent only where both
344		/// operands are — and `f64::min` already skips a NaN operand, which is that semantics.
345		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		/// `(l < r) as f64` — the algebra's only door out of the reals, and a flat one: a predicate has
348		/// no slope, which is exactly why a `Gate` node needs a kernel of its own rather than this.
349		/// `gt`/`ge` are this with the arguments swapped, so there is one comparison to differentiate.
350		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		// at the kink `sign(0)=0` picks subgradient 0; `diff().eval` gives `0/0 = NaN` there — the two
357		// agree only off the kink.
358		Abs(e) propagates { e.abs() } chain [seed * sign(e)] "\\left|{}\\right|" "|{}|" "abs";
359		// at `val = 0` the slope is infinite and `seed / 0.0` says so, which is the honest reading and
360		// the one `diff().eval` gives too.
361		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		/// `e.is_nan() as f64` — [`Cmp`]'s sibling over the one thing `Cmp` may not read. Flat for the
364		/// same reason: presence is not a quantity with a slope. This is what lets the algebra *reason*
365		/// about a declination instead of only carrying one — [`present`], [`or`], and the branch
366		/// [`Ast::diff`] takes through a skipping [`Min`] are all it.
367		IsNan(e) never { f64::from(e.is_nan()) } flat [] "\\left[{} = \\varnothing\\right]" "[{} absent]" "absent?";
368	}
369
370	// No row fits these: a leaf carries a payload instead of operands, `Powi` carries its exponent in
371	// the type, `Select` evaluates one branch rather than both, and `Sum` is variadic. Their `Expr`
372	// impls are written out below the table, and the arms a walk needs are here.
373	irregular {
374		Const(f64);
375		Var(usize);
376		Powi(Box<Ast>, i32);
377		/// `if c != 0 { a } else { b }`
378		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		// only the taken branch: a trace shows what the value came from, and the other arm did not
435		// contribute to it.
436		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/// Zero-size leaf reading `env[I]`; `I` is the dep slot it stands for.
448#[derive(Clone, Copy)]
449pub struct Var<const I: usize>;
450/// [`Var`] with the slot as a value, so `N` slots read alike are one type and fit a [`Sum`] or an
451/// array of [`Slots`].
452#[derive(Clone, Copy)]
453pub struct VarAt(pub usize);
454/// The only `f64` entry point into the algebra.
455#[derive(Clone, Copy)]
456pub struct Const(pub f64);
457/// No number — how a body inside the algebra declines. A leaf of its own rather than
458/// `Const(f64::NAN)` because [`Expr::MAYBE`] is what the comparing operators refuse, and a `Const`
459/// carrying a NaN would say nothing about which trees can reach one.
460#[derive(Clone, Copy)]
461pub struct Absent;
462/// Integer power, so the exponent stays exact and the derivative stays in the algebra.
463#[derive(Clone, Copy)]
464pub struct Powi<E, const N: i32>(pub E);
465/// `if c != 0 { a } else { b }`. The seed reaches the taken branch only, so a `Select` over a `Cmp`
466/// is a piecewise expression whose derivative is the taken piece's.
467#[derive(Clone, Copy)]
468pub struct Select<C, A, B>(pub C, pub A, pub B);
469/// `x` where it is a number, `fallback` where it declines — the door out of absence, and the reason
470/// it is a node rather than a `Select` written out: `Select`'s definedness is the union of its
471/// branches, where this one's is the fallback's alone.
472#[derive(Clone, Copy)]
473pub struct Or<X, F>(pub X, pub F);
474/// Homogeneous fold; heterogeneous sums chain via `+`.
475#[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	/// As the `Select` a reader would have written: the presence test is the condition, and the
575	/// fallback is the branch it takes.
576	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	/// The branches, and not the condition: a `Select` is where a body *writes* a declination, and
584	/// which branch is live is not a thing the type knows.
585	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
626/// One expression per slot of a multi-slot out — what a per-element kernel evaluates to fill an
627/// item. Heterogeneous, so a tuple rather than [`Sum`]'s homogeneous array: the slots of an item are
628/// different functions of one env, and a single-slot out is the one-tuple spelled without brackets.
629pub trait Slots: Copy {
630	const LEN: usize;
631	/// Whether *any* slot may decline — [`Expr::MAYBE`] over the tuple, which is what the item being
632	/// filled owes an absence channel for.
633	const MAYBE: bool = false;
634	/// So a kernel holding an opaque `impl Slots` can check its width against the item it fills.
635	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	/// Row-major `LEN × env.len()`, accumulated — the caller zeroes.
645	fn grad_slots(&self, env: &[f64], jac: &mut [f64]);
646	fn lower_slots(&self) -> Vec<Ast>;
647}
648
649/// [`Ex`] rather than a blanket over [`Expr`]: a downstream crate may implement this crate's `Expr`
650/// for a tuple, which would make the blanket overlap the tuple impls below.
651impl<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
668/// Over [`Slots`] rather than [`Ex`], so a recurrence whose state is a few named slots and a run
669/// of alike ones states it as one tuple.
670macro_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/// Operator-ergonomics handle: `x*y + constant(2.0)` builds the nested type. Delegates every
729/// [`Expr`] method to its inner primitive.
730#[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/// The dep-slot dispenser handed to a `trading_data_dag::Symbolic` body: `v.get::<I>()` is the
750/// `Var` reading dep `I` (bounds enforced at eval time by `env` length).
751#[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}
766/// How a body inside the algebra declines, which the out plane reads back as absence
767/// (`r[impl outs.absence.typed]`). Every tree reaching one carries [`Expr::MAYBE`], so the operators
768/// that cannot answer over one refuse it where it is written rather than where it lands.
769pub fn absent() -> Ex<Absent> {
770	Ex(Absent)
771}
772/// `1.0` where `x` is a number, `0.0` where it declines — how a body *reads* an absence instead of
773/// merely carrying one. Flat, and never absent itself, so it is a condition the comparing operators
774/// accept.
775pub fn present<T: Expr>(x: Ex<T>) -> Ex<Sub<Const, IsNan<T>>> {
776	Ex(Sub(Const(1.0), IsNan(x.0)))
777}
778/// `x` where it stands, `fallback` where it declines. The way out of absence: what comes back is a
779/// number exactly as often as `fallback` is one, which is what lets a body compare it.
780pub 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}
807/// A comparison is the one thing an absence has no answer for, so a tree that can carry one may not
808/// reach here: `or` it against a number first, or leave the comparison out and let the absence
809/// propagate (`r[impl outs.absence.typed]`).
810pub 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}
819/// `l > r` is `r < l`: one comparison in the algebra, read from the other side.
820pub 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}
829/// The **condition** may not decline — a `Select` is where a body writes an absence, and a branch
830/// that cannot be chosen is no branch. The two branches stay permissive, which is the whole point.
831pub 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
877/// [`takes_left`] as a tree: the right operand absent takes the left, the left absent then takes the
878/// right, and only where both are numbers does the row's comparison decide. Nested rather than one disjunction
879/// because `Select` evaluates the taken branch alone, which is what keeps the comparison off an
880/// operand it refuses.
881fn 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
891/// A node whose operands all simplified to constants *is* its value, and that value comes from
892/// [`Ast::eval`] rather than from a second copy of the operator's law.
893fn 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
911/// The two walks no row states: a derivative is per-operator mathematics, and an identity is a
912/// per-operator claim about what an operator may be rewritten to.
913impl Ast {
914	/// Exact symbolic derivative wrt dep `var`, chain rule per node. Call [`Ast::simplify`] to
915	/// clear the `0`/`1` litter it leaves. `sign(e)` is rendered as `e / |e|` (exact off the kink).
916	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			// `e/|e|` is `0/0 = NaN` at `e = 0`; `Div`-by-zero propagates `inf`/`NaN` — the honest
931			// numeric result, matching the FD path's own NaN handling.
932			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			// the kink is a branch, not a slope: which piece is live is what the row's comparison says,
937			// and the derivative is that piece's. `strictly` is that comparison, so which operand this
938			// takes is not restated here — and the two presence tests ahead of it are the row's skip,
939			// spelled so that the `Cmp` is never reached over an operand it may not read.
940			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	/// Const-fold + `0`/`1` identities, so a differentiated tree renders clean.
948	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			// no identity to claim, so the fold is the whole of it — and it goes through `eval`, which is
1001			// the operator's own law rather than a third copy of it.
1002			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			// the fold that matters: a `Min`/`Max` against a literal threshold differentiates through
1010			// this, and folding it away is what leaves the derivative reading the one branch it had
1011			// before absence was expressible.
1012			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					// both arms the same is what a differentiated `Min(x, x)` collapses to
1027					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
1049/// An [`Ast`] node paired with its evaluated value; [`fmt::Display`] renders the box-drawing
1050/// intermediate-value tree from the post.
1051pub 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}