ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Expectation.cpp
Go to the documentation of this file.
1/**
2 * @file Expectation.cpp
3 * @brief Implementation of the analytical expectation / variance / moment
4 * evaluator over scalar RV sub-circuits.
5 */
6#include "Expectation.h"
7
8#include "AggMarginalEvaluator.h" // aggAvgRawMomentExact
9#include "AnalyticEvaluator.h"
10#include "Aggregation.h" // ComparisonOperator + cmpOpFromOid
11#include "BooleanCircuit.h"
12#include "Circuit.h"
13#include "CircuitFromMMap.h"
14#include "CollapsedAggMoment.h" // collapsedConditionalMoment
15#include "ComparatorResolution.h" // resolveComparators
16#include "ConjugatePosterior.h" // conjugatePosterior / conjugateLogEvidence
17#include "ProbabilityMethod.h" // booleanSubcircuitProbability
18#include "MonteCarloSampler.h"
19#include "RandomVariable.h"
20#include "distributions/Distribution.h" // makeDistribution -> integrationRange
21#include "PivotIntegration.h" // simpsonIntegrate / binomial / centralFromRaw
22#include "RangeCheck.h"
23#include "provsql_utils_cpp.h"
24#include "semiring/BoolExpr.h"
25
26extern "C" {
27#include "postgres.h"
28#include "fmgr.h"
29#include "utils/uuid.h"
30#include "provsql_utils.h"
31#include "provsql_error.h"
32
33PG_FUNCTION_INFO_V1(rv_moment);
34PG_FUNCTION_INFO_V1(rv_quantile);
35PG_FUNCTION_INFO_V1(rv_evidence);
36PG_FUNCTION_INFO_V1(agg_avg_moment_exact);
37}
38
39#include <algorithm>
40#include <cmath>
41#include <set>
42#include <stack>
43#include <string>
44#include <unordered_map>
45#include <unordered_set>
46#include <vector>
47#include "provsql_interrupt.h"
48
49namespace provsql {
50
51namespace {
52/// Copy the subtree rooted at @p root of @p gc into a fresh GenericCircuit
53/// @p sub (mirrors @c MMappedCircuit::createGenericCircuit, but from an
54/// in-memory circuit). Lets the moment path resolve a mixture selector's
55/// comparators in isolation -- without mutating the surrounding moment
56/// circuit, whose gate_case guards and native RV comparisons must keep
57/// their raw comparator structure.
58void extractSubcircuit(const GenericCircuit &gc, gate_t root,
59 GenericCircuit &sub, gate_t &sub_root)
60{
61 std::unordered_set<gate_t> seen;
62 std::stack<gate_t> stk;
63 stk.push(root);
64 while (!stk.empty()) {
65 gate_t g = stk.top(); stk.pop();
66 if (!seen.insert(g).second) continue;
67 const std::string u = gc.getUUID(g);
68 const gate_type t = gc.getGateType(g);
69 const gate_t id = sub.setGate(u, t);
70 const double pr = gc.getProb(g);
71 if (!std::isnan(pr)) sub.setProb(id, pr);
72 if (t == gate_mulinput || t == gate_eq || t == gate_agg || t == gate_cmp
73 || t == gate_arith) {
74 const auto infos = gc.getInfos(g);
75 sub.setInfos(id, infos.first, infos.second);
76 } else if (t == gate_plus || t == gate_times) {
77 const auto infos = gc.getInfos(g);
78 if (infos.first != 0 || infos.second != 0)
79 sub.setInfos(id, infos.first, infos.second);
80 }
81 if (t == gate_project || t == gate_value || t == gate_agg || t == gate_rv
82 || t == gate_mulinput || t == gate_annotation || t == gate_assumed
83 || t == gate_mobius || t == gate_arith || t == gate_observe)
84 sub.setExtra(id, gc.getExtra(g));
85 for (gate_t c : gc.getWires(g)) {
86 sub.addWire(id, sub.getGate(gc.getUUID(c)));
87 stk.push(c);
88 }
89 }
90 sub_root = sub.getGate(gc.getUUID(root));
91}
92} // namespace
93
95{
96 // Route through the single central Boolean-probability entry point
97 // (getBooleanCircuit + MethodCatalog::chooseAndRun, MC fallback), rather
98 // than a hand-rolled Boolean build + independentEvaluation. Any RV
99 // comparator in this Boolean function is resolved on an extracted COPY of
100 // the boolRoot subtree, so the resolution never touches the surrounding
101 // moment circuit (whose gate_case guards / native RV comparisons must
102 // keep their raw comparator for the correlation-aware value moment).
103 GenericCircuit sub;
104 gate_t sub_root;
105 extractSubcircuit(gc, boolRoot, sub, sub_root);
106 resolveComparators(sub, sub_root, /*simplify=*/false, /*decompose=*/false);
107 return booleanSubcircuitProbability(sub, sub_root);
108}
109
110namespace {
111
112using RvSet = std::set<gate_t>;
113
114/// Mixing weight π = P(p = true) for a mixture's Bernoulli wire.
115/// For a bare @c gate_input, the probability is the leaf's pinned
116/// @c set_prob; for any compound Boolean gate, defer to
117/// @c evaluateBooleanProbability.
118double mixturePi(const GenericCircuit &gc, gate_t p)
119{
120 return (gc.getGateType(p) == gate_input)
121 ? gc.getProb(p)
123}
124
125/// True iff @p g is a @c gate_rv whose distribution has a wired (token)
126/// parameter -- a latent / compound leaf with no constant-parameter
127/// closed form, so every analytic path must fall through to Monte Carlo.
128bool rvIsParametric(const GenericCircuit &gc, gate_t g)
129{
130 if (gc.getGateType(g) != gate_rv) return false;
131 auto tmpl = parse_distribution_template(gc.getExtra(g));
132 return tmpl && tmpl->parametric();
133}
134
135/// Whether the family of @p tmpl has a mean affine in its parameters, so the
136/// compound-leaf expectation is exact via @c mean(E[θ]) (see the
137/// @c meanIsAffine() doc). The flag is authoritative, per-family.
138bool familyMeanIsAffine(const DistributionTemplate &tmpl)
139{
140 return tmpl.family->factory(0.0, 0.0)->meanIsAffine();
141}
142
143/// Cache of the base-@c gate_rv UUID footprints reachable below each
144/// scalar gate, used as the structural-independence witness. Two
145/// children of an arithmetic gate are independent iff their footprints
146/// are disjoint -- and therefore the variance and TIMES expectation
147/// shortcuts apply.
148class FootprintCache {
149public:
150 explicit FootprintCache(const GenericCircuit &gc) : gc_(gc) {}
151
152 const RvSet &of(gate_t g) {
153 auto it = cache_.find(g);
154 if (it != cache_.end()) return it->second;
155 RvSet s;
156 auto type = gc_.getGateType(g);
157 if (type == gate_rv) {
158 // The leaf itself is a distinct random source (two independent
159 // normal(M,1) leaves share M but draw independently given it), so
160 // its own gate_t is always in the footprint. A latent (parametric)
161 // leaf ALSO carries the footprints of its parameter wires, so two
162 // leaves sharing a latent M overlap on M and are correctly flagged
163 // dependent -- defeating the closed-form independence shortcuts and
164 // routing the whole expression to the MC path that couples them.
165 // A non-parametric leaf has no wires, so this is a no-op there.
166 s.insert(g);
167 for (gate_t c : gc_.getWires(g)) {
168 const auto &cs = of(c);
169 s.insert(cs.begin(), cs.end());
170 }
171 } else if (type == gate_value) {
172 // empty -- no RV reached
173 } else if (type == gate_arith || type == gate_case) {
174 // gate_arith: all children are scalar operands. gate_case: the
175 // selected value depends on both the guards (which RVs they compare)
176 // and the value branches, so the footprint is the union over every
177 // wire -- a value and a guard sharing a leaf make the selection
178 // correlated, which must defeat the independence shortcuts.
179 for (gate_t c : gc_.getWires(g)) {
180 const auto &cs = of(c);
181 s.insert(cs.begin(), cs.end());
182 }
183 } else if (type == gate_mixture) {
184 const auto &wires = gc_.getWires(g);
185 if (gc_.isCategoricalMixture(g)) {
186 // Categorical-form mixture. Footprint = union of the
187 // mulinputs' footprints (each contributes {self, key} via the
188 // mulinput branch below), so two categoricals sharing a key
189 // overlap on it and are correctly flagged dependent.
190 for (std::size_t i = 1; i < wires.size(); ++i) {
191 const auto &fm = of(wires[i]);
192 s.insert(fm.begin(), fm.end());
193 }
194 } else if (wires.size() == 3) {
195 // Classic 3-wire mixture. Footprint = footprint(p) ∪
196 // footprint(x) ∪ footprint(y). The Boolean wire is included
197 // as a discrete random source so two mixtures whose p's share
198 // an atom are correctly recognised as dependent (their branch
199 // selection is correlated), bypassing the closed-form
200 // independence shortcut. Recursing into wires[0] (rather than
201 // inserting its gate_t directly) generalises that recognition
202 // from bare-input Bernoullis to compound Boolean wires.
203 const auto &fp = of(wires[0]);
204 s.insert(fp.begin(), fp.end());
205 const auto &fx = of(wires[1]);
206 s.insert(fx.begin(), fx.end());
207 const auto &fy = of(wires[2]);
208 s.insert(fy.begin(), fy.end());
209 }
210 } else if (type == gate_mulinput) {
211 // A mulinput is a state-carrying atom (so its own gate_t is in
212 // its footprint -- two mulinputs of the same group are distinct
213 // atoms even though they share a key) *and* references a shared
214 // key gate at wires[0] (whose footprint is added so the shared
215 // key makes the two mulinputs overlap on it, flagging them as
216 // dependent for pairwise_disjoint).
217 s.insert(g);
218 const auto &wires = gc_.getWires(g);
219 if (!wires.empty()) {
220 const auto &fk = of(wires[0]);
221 s.insert(fk.begin(), fk.end());
222 }
223 } else if (type == gate_input) {
224 // Atomic Boolean leaf. Use the gate's own UUID as its footprint
225 // so two Boolean expressions sharing this input collide on it.
226 s.insert(g);
227 } else if (type == gate_plus || type == gate_times || type == gate_monus
228 || type == gate_project || type == gate_eq
229 || type == gate_cmp || type == gate_update
230 || type == gate_annotation || type == gate_conditioned
231 || type == gate_delta || type == gate_assumed
232 || type == gate_agg || type == gate_semimod) {
233 // Boolean gates: footprint is the union of children's footprints.
234 // So are an aggregate and its contributions: two aggregates over the
235 // same rows (count(*) of a table times sum(x) of the same table) are
236 // not independent, and an empty footprint made their product the
237 // product of their expectations.
238 // Lets a compound `p` wire feeding a mixture propagate its atom
239 // dependencies to FootprintCache for the disjoint-children
240 // shortcuts in rec_expectation / rec_variance / rec_raw_moment.
241 for (gate_t c : gc_.getWires(g)) {
242 const auto &cs = of(c);
243 s.insert(cs.begin(), cs.end());
244 }
245 } else if (type == gate_zero || type == gate_one) {
246 // Empty footprint -- a constant-true / constant-false Boolean
247 // contributes no shared atoms.
248 } else {
249 // Unknown scalar gate type: return an empty footprint. Callers
250 // will trip the analytical-decomposition switch and route the
251 // gate to the MC fallback (or raise if the fallback is disabled),
252 // which is the right behaviour for any unanticipated leaf shape.
253 }
254 return cache_.emplace(g, std::move(s)).first->second;
255 }
256
257private:
258 const GenericCircuit &gc_;
259 std::unordered_map<gate_t, RvSet> cache_;
260};
261
262bool pairwise_disjoint(FootprintCache &fp, const std::vector<gate_t> &children)
263{
264 RvSet seen;
265 for (gate_t c : children) {
266 const auto &fpc = fp.of(c);
267 for (gate_t r : fpc) {
268 if (!seen.insert(r).second) return false;
269 }
270 }
271 return true;
272}
273
274/* Closed-form E[max] / E[min] of a gate_arith MAX/MIN whose children are
275 * independent bare gate_rv leaves of the SAME family with the SAME parameters
276 * (the i.i.d. order statistic). Returns std::nullopt when the shape is not
277 * i.i.d. bare-RV (mixture-wrapped aggregate children, mixed families, shared
278 * leaves, or a family without an elementary order-statistic mean) so the
279 * caller falls back to Monte Carlo.
280 *
281 * The per-family closed forms live in @c Distribution::iidOrderStatMean
282 * (Uniform, Exponential; Normal and Erlang i.i.d. maxima have no elementary
283 * closed form -- they need the 1-D order-statistic quadrature -- so they
284 * decline there).
285 */
286std::optional<double>
287iidOrderStatMean(const GenericCircuit &gc, gate_t g, bool isMax,
288 FootprintCache &fp)
289{
290 const auto &raw_wires = gc.getWires(g);
291 if (raw_wires.empty())
292 return std::nullopt;
293 /* Idempotence: max / min ignore repeats, so a child appearing more than
294 * once (the same gate) counts once. De-duplicating here generalises the
295 * closed form to any MAX/MIN gate -- without it a repeated child would
296 * collide with itself in pairwise_disjoint and silently drop to MC. */
297 std::vector<gate_t> wires;
298 wires.reserve(raw_wires.size());
299 {
300 std::set<gate_t> seen;
301 for (gate_t c : raw_wires)
302 if (seen.insert(c).second)
303 wires.push_back(c);
304 }
305 if (!pairwise_disjoint(fp, wires))
306 return std::nullopt; /* shared leaves -> correlated -> MC */
307
308 std::vector<DistributionSpec> specs;
309 specs.reserve(wires.size());
310 for (gate_t c : wires) {
311 if (gc.getGateType(c) != gate_rv)
312 return std::nullopt; /* not a bare RV (e.g. a mixture wrap) */
313 auto s = parse_distribution_spec(gc.getExtra(c));
314 if (!s)
315 return std::nullopt;
316 specs.push_back(*s);
317 }
318
319 /* i.i.d.: identical family and parameters across all children (the
320 * family descriptor is interned, so pointer comparison is family
321 * identity). */
322 for (std::size_t i = 1; i < specs.size(); ++i)
323 if (specs[i].family != specs[0].family ||
324 specs[i].p1 != specs[0].p1 || specs[i].p2 != specs[0].p2)
325 return std::nullopt;
326
327 return makeDistribution(specs[0])->iidOrderStatMean(specs.size(), isMax);
328}
329
330/* Closed-form (quadrature) E[max] / E[min] of a gate_arith MAX/MIN whose
331 * children are independent bare gate_rv leaves of *any* families (mixed or
332 * not-identical), generalising @c iidOrderStatMean. Uses the layer-cake
333 * identity over a window [lo, hi] covering every child's support:
334 * E[max] = lo + ∫ (1 − ∏ F_i(t)) dt, E[min] = lo + ∫ ∏ (1 − F_i(t)) dt.
335 * Composite Simpson. std::nullopt on shared leaves, a non-bare-RV child, or
336 * a distribution whose CDF is undefined (e.g. non-integer Erlang), so the
337 * caller falls back to Monte Carlo. */
338std::optional<double>
339mixedOrderStatMean(const GenericCircuit &gc, gate_t g, bool isMax,
340 FootprintCache &fp)
341{
342 const auto &raw_wires = gc.getWires(g);
343 if (raw_wires.empty())
344 return std::nullopt;
345 std::vector<gate_t> wires;
346 {
347 std::set<gate_t> seen;
348 for (gate_t c : raw_wires)
349 if (seen.insert(c).second)
350 wires.push_back(c);
351 }
352 if (!pairwise_disjoint(fp, wires))
353 return std::nullopt;
354
355 // Construct each child's Distribution once; the Simpson loop below calls
356 // cdf on them per point (never re-constructing per point).
357 std::vector<std::unique_ptr<Distribution>> dists;
358 double lo = 0.0, hi = 0.0;
359 bool first = true;
360 for (gate_t c : wires) {
361 if (gc.getGateType(c) != gate_rv)
362 return std::nullopt;
363 auto s = parse_distribution_spec(gc.getExtra(c));
364 if (!s)
365 return std::nullopt;
366 auto d = makeDistribution(*s);
367 double clo, chi;
368 if (!d->integrationRange(clo, chi))
369 return std::nullopt;
370 if (first) { lo = clo; hi = chi; first = false; }
371 else { lo = std::min(lo, clo); hi = std::max(hi, chi); }
372 dists.push_back(std::move(d));
373 }
374 if (!(hi > lo))
375 return std::nullopt;
376
377 const double integral = simpsonIntegrate(lo, hi, kSimpsonPanels,
378 [&](double t) {
379 if (isMax) {
380 double prodF = 1.0; /* ∏ F_i(t) = P(max ≤ t) */
381 for (const auto &d : dists) {
382 const double F = d->cdf(t);
383 if (std::isnan(F)) return std::numeric_limits<double>::quiet_NaN();
384 prodF *= F;
385 }
386 return 1.0 - prodF; /* P(max > t) */
387 }
388 double prod1mF = 1.0; /* ∏ (1 − F_i(t)) = P(min > t) */
389 for (const auto &d : dists) {
390 const double F = d->cdf(t);
391 if (std::isnan(F)) return std::numeric_limits<double>::quiet_NaN();
392 prod1mF *= (1.0 - F);
393 }
394 return prod1mF;
395 });
396 if (std::isnan(integral))
397 return std::nullopt;
398 return lo + integral;
399}
400
401unsigned mc_samples_or_throw(const std::string &what)
402{
403 const int n = provsql_rv_mc_samples;
404 if (n <= 0) {
405 throw CircuitException(
406 what + " could not be decomposed analytically and "
407 "provsql.rv_mc_samples = 0 disables the Monte Carlo fallback");
408 }
409 // Transparency: the analytic moment surface is about to return a Monte Carlo
410 // ESTIMATE, not a closed-form moment. Signal it (at the same verbose>=5
411 // evaluation tier as the probability-side approximation NOTICEs, so Studio
412 // and verbose users can tell an estimate from an exact value) -- the
413 // continuous-RV surface is approximate by nature, but never *silently* so.
414 // Set provsql.rv_mc_samples = 0 to require an exact result instead.
415 if (provsql_verbose >= 5)
417 "%s: no closed form found; estimating by Monte Carlo over %d samples "
418 "(an approximation, not an exact moment) -- set provsql.rv_mc_samples = 0 "
419 "to require an exact result instead", what.c_str(), n);
420 return static_cast<unsigned>(n);
421}
422
423/// Most Boolean inputs whose 2^n possible worlds the moment fallbacks
424/// enumerate, for an exact moment, before sampling.
425constexpr unsigned kEnumerateMaxInputs = 20;
426
427/**
428 * @brief The moment of order @p k of @p g, about @p mu (0 for a raw
429 * moment), given @p event, over the possible worlds of the circuit
430 * (@c enumerateScalarWorlds), or @c std::nullopt when they cannot be
431 * enumerated.
432 *
433 * The worlds where @p g has no value (an aggregate over no row) are left
434 * out, as the samplers leave out such draws.
435 *
436 * @throws NoValueException when it has a value in no world.
437 */
438std::optional<double> enumerated_moment(const GenericCircuit &gc, gate_t g,
439 unsigned k, double mu,
440 std::optional<gate_t> event,
441 const std::string &what)
442{
443 auto worlds = enumerateScalarWorlds(gc, g, event, kEnumerateMaxInputs);
444 if (!worlds) return std::nullopt;
445 if (event && worlds->empty())
446 throw CircuitException(what + ": conditioning event is infeasible");
447 double total = 0.0, mass = 0.0;
448 for (const auto &w : *worlds) {
449 if (!w.second) continue;
450 total += w.first * std::pow(*w.second - mu, static_cast<double>(k));
451 mass += w.first;
452 }
453 if (!(mass > 0.0)) throw NoValueException(what);
454 return total / mass;
455}
456
457double mc_raw_moment(const GenericCircuit &gc, gate_t g, unsigned k,
458 const std::string &what)
459{
460 if (auto m = enumerated_moment(gc, g, k, 0.0, std::nullopt, what))
461 return *m;
462 auto samples = monteCarloScalarSamples(gc, g, mc_samples_or_throw(what));
463 if (samples.empty()) return 0.0;
464 // A draw with no value (an agg(SUM/AVG/MIN/MAX) over an empty group,
465 // SQL NULL) is a missing observation of the moment; a NaN is a value
466 // and propagates, as in SQL.
467 double total = 0.0;
468 std::size_t defined_count = 0;
469 for (const auto &x : samples) {
470 if (!x) continue;
471 total += std::pow(*x, static_cast<double>(k));
472 ++defined_count;
473 }
474 if (defined_count == 0) throw NoValueException(what);
475 return total / static_cast<double>(defined_count);
476}
477
478double mc_central_moment(const GenericCircuit &gc, gate_t g, unsigned k,
479 double mu, const std::string &what)
480{
481 if (auto m = enumerated_moment(gc, g, k, mu, std::nullopt, what))
482 return *m;
483 auto samples = monteCarloScalarSamples(gc, g, mc_samples_or_throw(what));
484 if (samples.empty()) return 0.0;
485 double total = 0.0;
486 std::size_t defined_count = 0;
487 for (const auto &x : samples) {
488 if (!x) continue;
489 total += std::pow(*x - mu, static_cast<double>(k));
490 ++defined_count;
491 }
492 if (defined_count == 0) throw NoValueException(what);
493 return total / static_cast<double>(defined_count);
494}
495
496/// Minimum accepted-sample count for conditional MC moments. Below
497/// this floor we'd be reporting a moment from a handful of accepted
498/// draws and the variance of the estimator would be enormous; raise
499/// rather than silently return a noisy number.
500unsigned min_accepted_floor(unsigned attempted)
501{
502 unsigned floor = attempted / 1000;
503 return floor < 5 ? 5 : floor;
504}
505
506void check_acceptance_or_throw(const ConditionalScalarSamples &cs,
507 const std::string &what)
508{
509 if (cs.accepted.empty()) {
510 /* 0-of-N accepted is the unmistakable signature of an infeasible
511 * conditioning event: raising rv_mc_samples cannot help (the
512 * acceptance probability is exactly 0). Surface that directly
513 * rather than the generic "raise samples or check satisfiability"
514 * advice that applies to merely under-sampled events. */
515 throw CircuitException(
516 what + ": conditioning event is infeasible (0 of " +
517 std::to_string(cs.attempted) +
518 " Monte Carlo samples satisfied it)");
519 }
520 const unsigned floor = min_accepted_floor(cs.attempted);
521 if (cs.accepted.size() < floor) {
522 throw CircuitException(
523 what + ": conditional MC accepted only " +
524 std::to_string(cs.accepted.size()) + " out of " +
525 std::to_string(cs.attempted) +
526 " samples (need >= " + std::to_string(floor) +
527 "); raise provsql.rv_mc_samples or tighten the event.");
528 }
529}
530
531double mc_conditional_raw_moment(const GenericCircuit &gc, gate_t g,
532 unsigned k, gate_t event_root,
533 const std::string &what)
534{
535 if (auto m = enumerated_moment(gc, g, k, 0.0, event_root, what))
536 return *m;
538 gc, g, event_root, mc_samples_or_throw(what));
539 check_acceptance_or_throw(cs, what);
540 // Mirror the unconditional path: draws with no value (typically
541 // empty-group SQL NULLs from gate_agg) are excluded from the mean.
542 double total = 0.0;
543 std::size_t defined_count = 0;
544 for (const auto &x : cs.accepted) {
545 if (!x) continue;
546 total += std::pow(*x, static_cast<double>(k));
547 ++defined_count;
548 }
549 if (defined_count == 0) throw NoValueException(what);
550 return total / static_cast<double>(defined_count);
551}
552
553double mc_conditional_central_moment(const GenericCircuit &gc, gate_t g,
554 unsigned k, double mu,
555 gate_t event_root,
556 const std::string &what)
557{
558 if (auto m = enumerated_moment(gc, g, k, mu, event_root, what))
559 return *m;
561 gc, g, event_root, mc_samples_or_throw(what));
562 check_acceptance_or_throw(cs, what);
563 double total = 0.0;
564 std::size_t defined_count = 0;
565 for (const auto &x : cs.accepted) {
566 if (!x) continue;
567 total += std::pow(*x - mu, static_cast<double>(k));
568 ++defined_count;
569 }
570 if (defined_count == 0) throw NoValueException(what);
571 return total / static_cast<double>(defined_count);
572}
573
574double rec_expectation(const GenericCircuit &gc, gate_t g, FootprintCache &fp);
575double rec_variance(const GenericCircuit &gc, gate_t g, FootprintCache &fp);
576double rec_raw_moment(const GenericCircuit &gc, gate_t g, unsigned k,
577 FootprintCache &fp);
578
579/* -----------------------------------------------------------------------
580 * Likelihood-weighting (importance-sampling) posterior readouts.
581 *
582 * When the conditioning event is continuous-density evidence (it contains
583 * a gate_observe), the analytic / rejection conditional paths do not apply:
584 * draw latents from the prior and weight each draw by the observations'
585 * densities, then report the weighted posterior statistic. These helpers
586 * turn one importance-sampling pass (WeightedPosterior) into a posterior
587 * raw moment / central moment / quantile.
588 * -------------------------------------------------------------------- */
589
590/* Self-normalised weighted raw moment Σ w x^k / Σ w. The particles are
591 * the draws where the root has a value (a draw with none, e.g. an
592 * empty-group aggregate, is left out by importanceSampleConditional,
593 * mirroring the unconditional MC path). */
594double weightedRawMoment(const WeightedPosterior &post, unsigned k)
595{
596 double sw = 0.0, swx = 0.0;
597 for (const auto &[x, w] : post.particles) {
598 sw += w;
599 swx += w * std::pow(x, static_cast<double>(k));
600 }
601 if (sw <= 0.0) throw NoValueException("Posterior moment");
602 return swx / sw;
603}
604
605/* Self-normalised weighted central moment Σ w (x-mu)^k / Σ w. */
606double weightedCentralMoment(const WeightedPosterior &post, unsigned k,
607 double mu)
608{
609 double sw = 0.0, swd = 0.0;
610 for (const auto &[x, w] : post.particles) {
611 sw += w;
612 swd += w * std::pow(x - mu, static_cast<double>(k));
613 }
614 if (sw <= 0.0) throw NoValueException("Posterior moment");
615 return swd / sw;
616}
617
618/* Weighted empirical p-quantile: sort particles by value, walk the
619 * cumulative weight, linearly interpolate at p·(Σw) (the percentile_cont
620 * convention generalised to weights). */
621double weightedQuantile(WeightedPosterior post, double p)
622{
623 auto &pts = post.particles;
624 if (pts.empty()) throw NoValueException("Posterior quantile");
625 std::sort(pts.begin(), pts.end(), [](const auto &a, const auto &b) {
626 return sql_less(a.first, b.first);
627 });
628 double total = 0.0;
629 for (const auto &pw : pts) total += pw.second;
630 if (!(total > 0.0)) return pts.front().first;
631 const double target = p * total;
632 double cum = 0.0;
633 for (std::size_t i = 0; i < pts.size(); ++i) {
634 const double prev = cum;
635 cum += pts[i].second;
636 if (cum >= target) {
637 if (i == 0) return pts[0].first;
638 /* Linear interpolation between the two straddling particles at their
639 * cumulative-weight midpoints (matches the empirical MC quantile). */
640 const double frac = (pts[i].second > 0.0)
641 ? (target - prev) / pts[i].second
642 : 0.0;
643 return pts[i - 1].first + frac * (pts[i].first - pts[i - 1].first);
644 }
645 }
646 return pts.back().first;
647}
648
649/* Guard a posterior pass: raise on infeasible (no positive-weight draw)
650 * evidence, and warn when the effective sample size is degenerating. */
651void checkPosteriorOrThrow(const WeightedPosterior &post,
652 const std::string &what)
653{
654 if (post.particles.empty() || post.weight_sum <= 0.0) {
655 throw CircuitException(
656 what + ": evidence is infeasible (no positive-weight draw among " +
657 std::to_string(post.attempted) +
658 " Monte Carlo samples); the observations may contradict the prior, "
659 "or raise provsql.rv_mc_samples");
660 }
661 const double ess = post.effectiveSampleSize();
662 const double nonzero = static_cast<double>(post.particles.size());
663 if (provsql_ess_warn_fraction > 0.0 &&
664 ess < provsql_ess_warn_fraction * nonzero) {
666 "%s: posterior effective sample size low (%.1f of %u accepted); "
667 "likelihood weighting is degenerating -- raise provsql.rv_mc_samples, "
668 "or the model has many observations per latent (defer to SMC)",
669 what.c_str(), ess, static_cast<unsigned>(post.particles.size()));
670 }
671}
672
673/**
674 * @brief Try to evaluate @f$E[X^k \mid A]@f$ in closed form.
675 *
676 * Fires only when @p root is a bare @c gate_rv whose family has a
677 * closed-form truncated moment (@c Distribution::truncatedRawMoment)
678 * and the event walk under @p event_root collects a sound interval
679 * constraint on it.
680 * Otherwise returns @c std::nullopt and the caller falls through to
681 * MC rejection.
682 *
683 * For @p central, returns @f$E[(X - \mu_A)^k \mid A]@f$ where
684 * @f$\mu_A@f$ is the closed-form conditional mean obtained by
685 * recursing on @c k = 1, then binomially expanding the central
686 * moment in terms of the raw moments.
687 */
688std::optional<double>
689try_truncated_closed_form(const GenericCircuit &gc, gate_t root,
690 gate_t event_root, unsigned k, bool central)
691{
692 auto m = matchTruncatedSingleRv(gc, root, event_root);
693 if (!m) return std::nullopt;
694 const double lo = m->lo, hi = m->hi;
695
696 /* Closed-form raw moment of the truncated distribution; constructed
697 * once, then queried per moment order. A family without a closed
698 * form (Erlang: needs the regularised lower incomplete gamma) returns
699 * nullopt and the caller falls through to MC. */
700 const auto dist = makeDistribution(m->spec);
701 auto raw = [&](unsigned q) -> std::optional<double> {
702 if (q == 0) return 1.0;
703 return dist->truncatedRawMoment(lo, hi, q);
704 };
705
706 if (!central) return raw(k);
707 /* Central: E[(X - μ_A)^k | A] via the binomial expansion. */
708 return centralFromRaw(k, raw);
709}
710
711/* A conditioning event of the shape @c "X op Y", where the target @c X and the
712 * other operand @c Y are two independent bare @c gate_rv leaves. */
713struct RvVsRvCond {
714 DistributionSpec targetSpec; /* X (the moment's target) */
715 DistributionSpec otherSpec; /* Y */
716 bool targetGreater; /* true for X > Y, false for X < Y */
717};
718
719/* Match @p event_root as a single @c gate_cmp comparing the target @p root
720 * (a bare RV X) with an independent bare RV Y. Returns std::nullopt for any
721 * other shape (constant threshold -- handled by the truncation path;
722 * conjunctions; agg comparisons; shared operand) so the caller falls through. */
723std::optional<RvVsRvCond>
724matchRvVsRvConditional(const GenericCircuit &gc, gate_t root, gate_t event_root)
725{
726 if (gc.getGateType(root) != gate_rv || gc.getGateType(event_root) != gate_cmp)
727 return std::nullopt;
728 auto specX = parse_distribution_spec(gc.getExtra(root));
729 if (!specX) return std::nullopt;
730
731 const auto &wires = gc.getWires(event_root);
732 if (wires.size() != 2) return std::nullopt;
733 bool ok = false;
734 ComparisonOperator op = cmpOpFromOid(gc.getInfos(event_root).first, ok);
735 if (!ok || op == ComparisonOperator::EQ || op == ComparisonOperator::NE)
736 return std::nullopt;
737
738 gate_t other;
739 bool targetLeft;
740 if (wires[0] == root) { other = wires[1]; targetLeft = true; }
741 else if (wires[1] == root) { other = wires[0]; targetLeft = false; }
742 else return std::nullopt; /* target not an operand */
743 if (other == root || gc.getGateType(other) != gate_rv)
744 return std::nullopt; /* X op X, or Y not a bare RV */
745 auto specY = parse_distribution_spec(gc.getExtra(other));
746 if (!specY) return std::nullopt;
747
748 /* targetGreater: does the event assert X > Y? If X is the left operand,
749 * that is op in {GT,GE}; if X is the right operand (event Y op X), it is
750 * op in {LT,LE}. */
751 const bool greaterOp = (op == ComparisonOperator::GT ||
753 const bool lessOp = (op == ComparisonOperator::LT ||
755 bool targetGreater;
756 if (targetLeft) targetGreater = greaterOp;
757 else targetGreater = lessOp;
758 return RvVsRvCond{*specX, *specY, targetGreater};
759}
760
761/* E[X^k | X op Y] for independent X, Y via a 1-D quadrature:
762 * E[X^k | X>Y] = (∫ x^k f_X(x) F_Y(x) dx) / (∫ f_X(x) F_Y(x) dx),
763 * and the X<Y case swaps F_Y for 1-F_Y. Composite Simpson over X's support;
764 * exact for the Uniform-Uniform case (the integrands are low-degree
765 * polynomials), high-accuracy otherwise. Returns NaN if the event mass is
766 * negligible or a density/CDF is undefined. */
767double rvVsRvConditionalMoment(const DistributionSpec &X,
768 const DistributionSpec &Y,
769 bool targetGreater, unsigned k)
770{
771 // Construct both distributions once; the Simpson loop calls pdf/cdf on
772 // them per point (never re-constructing per point).
773 const auto dX = makeDistribution(X);
774 const auto dY = makeDistribution(Y);
775 double lo, hi;
776 if (!dX->integrationRange(lo, hi))
777 return std::numeric_limits<double>::quiet_NaN();
778
779 auto base = [&](double x) {
780 const double fX = dX->pdf(x);
781 const double FY = dY->cdf(x);
782 if (std::isnan(fX) || std::isnan(FY))
783 return std::numeric_limits<double>::quiet_NaN();
784 const double w = targetGreater ? FY : (1.0 - FY); /* P(Y<x) / P(Y>x) */
785 return fX * w;
786 };
787 const double den = simpsonIntegrate(lo, hi, kSimpsonPanels, base);
788 if (std::isnan(den) || !(den > 1e-12))
789 return std::numeric_limits<double>::quiet_NaN();
790 const double num = simpsonIntegrate(lo, hi, kSimpsonPanels,
791 [&](double x) {
792 return std::pow(x, static_cast<double>(k)) * base(x);
793 });
794 if (std::isnan(num))
795 return std::numeric_limits<double>::quiet_NaN();
796 return num / den;
797}
798
799/* Closed-form (quadrature) E[X^k | X op Y] / central moment for an
800 * RV-vs-RV conditioning event. Mirrors @c try_truncated_closed_form for the
801 * constant-threshold case. */
802std::optional<double>
803try_rvVsRv_conditional_moment(const GenericCircuit &gc, gate_t root,
804 gate_t event_root, unsigned k, bool central)
805{
806 auto m = matchRvVsRvConditional(gc, root, event_root);
807 if (!m) return std::nullopt;
808
809 auto raw = [&](unsigned q) -> std::optional<double> {
810 if (q == 0) return 1.0;
811 double r = rvVsRvConditionalMoment(m->targetSpec, m->otherSpec,
812 m->targetGreater, q);
813 if (std::isnan(r)) return std::nullopt;
814 return r;
815 };
816
817 if (!central) return raw(k);
818 return centralFromRaw(k, raw);
819}
820
821/* One comparison of a pivot RV X against another operand, a factor in the
822 * pivot-conjunction integrand. `other` is an independent bare RV (its CDF
823 * weights the integrand) or, when `isConst`, a constant threshold that clips
824 * the integration window. `pivotGreater` is true when the factor asserts
825 * X > operand. */
826struct PivotFactor {
827 bool isConst;
828 DistributionSpec other; /* valid iff !isConst */
829 double konst; /* valid iff isConst */
830 bool pivotGreater;
831};
832
833/* ∫ x^k f_X(x) Π_j W_j(x) dx over X's support, where each RV factor contributes
834 * W_j(x) = F_{Y_j}(x) for X>Y_j and 1-F_{Y_j}(x) for X<Y_j, and each
835 * constant factor clips the window to {x : x>c} / {x : x<c}. With k=0 this is
836 * the joint probability P(∧_j comparisons). Because the comparisons all share
837 * the single pivot X and the other operands are independent, marginalising each
838 * Y_j analytically collapses the joint to this 1-D integral. Composite Simpson
839 * (exact for the polynomial integrands of the Uniform case). Returns NaN if a
840 * density / CDF is undefined. */
841double pivotConjunctionIntegral(const DistributionSpec &X,
842 const std::vector<PivotFactor> &factors,
843 unsigned k)
844{
845 const auto dX = makeDistribution(X);
846 double lo, hi;
847 if (!dX->integrationRange(lo, hi))
848 return std::numeric_limits<double>::quiet_NaN();
849 for (const auto &f : factors)
850 if (f.isConst) {
851 if (f.pivotGreater) lo = std::max(lo, f.konst);
852 else hi = std::min(hi, f.konst);
853 }
854 if (!(hi > lo)) return 0.0;
855
856 std::vector<std::unique_ptr<Distribution>> others;
857 std::vector<bool> greater;
858 for (const auto &f : factors)
859 if (!f.isConst) {
860 others.push_back(makeDistribution(f.other));
861 greater.push_back(f.pivotGreater);
862 }
863
864 return simpsonIntegrate(lo, hi, kSimpsonPanels, [&](double x) {
865 const double fX = dX->pdf(x);
866 if (std::isnan(fX)) return std::numeric_limits<double>::quiet_NaN();
867 double w = fX;
868 for (std::size_t j = 0; j < others.size(); ++j) {
869 const double FY = others[j]->cdf(x);
870 if (std::isnan(FY)) return std::numeric_limits<double>::quiet_NaN();
871 w *= greater[j] ? FY : (1.0 - FY);
872 }
873 return std::pow(x, static_cast<double>(k)) * w;
874 });
875}
876
877/* A conditioning event that is a conjunction of comparisons all sharing the
878 * target bare RV X, each against an independent bare RV or a constant. */
879struct PivotConjunctionCond {
880 DistributionSpec targetSpec;
881 std::vector<PivotFactor> factors;
882};
883
884/* Match @p event_root as a @c gate_times (AND) of >=2 @c gate_cmp, each
885 * comparing the target @p root (bare RV X) with an independent bare RV or a
886 * constant. Returns nullopt for a single comparison (the truncation / rvVsRv
887 * paths own that), an agg comparison, a cmp not involving X, a non-bare other
888 * operand, or a repeated / shared other operand (would break independence). */
889std::optional<PivotConjunctionCond>
890matchPivotConjunctionConditional(const GenericCircuit &gc, gate_t root,
891 gate_t event_root)
892{
893 if (gc.getGateType(root) != gate_rv ||
894 gc.getGateType(event_root) != gate_times)
895 return std::nullopt;
896 auto specX = parse_distribution_spec(gc.getExtra(root));
897 if (!specX) return std::nullopt;
898
899 const auto &kids = gc.getWires(event_root);
900 if (kids.size() < 2) return std::nullopt;
901 std::vector<PivotFactor> factors;
902 std::set<gate_t> othersSeen;
903 for (gate_t c : kids) {
904 if (gc.getGateType(c) != gate_cmp) return std::nullopt;
905 const auto &w = gc.getWires(c);
906 if (w.size() != 2) return std::nullopt;
907 bool ok = false;
908 ComparisonOperator op = cmpOpFromOid(gc.getInfos(c).first, ok);
909 if (!ok || op == ComparisonOperator::EQ || op == ComparisonOperator::NE)
910 return std::nullopt;
911 gate_t other; bool targetLeft;
912 if (w[0] == root) { other = w[1]; targetLeft = true; }
913 else if (w[1] == root) { other = w[0]; targetLeft = false; }
914 else return std::nullopt;
915 const bool greaterOp = (op == ComparisonOperator::GT ||
917 const bool lessOp = (op == ComparisonOperator::LT ||
919 const bool pivotGreater = targetLeft ? greaterOp : lessOp;
920
921 PivotFactor f;
922 if (gc.getGateType(other) == gate_value) {
923 f = {true, DistributionSpec{}, parseDoubleStrict(gc.getExtra(other)),
924 pivotGreater};
925 } else if (gc.getGateType(other) == gate_rv && other != root) {
926 if (!othersSeen.insert(other).second) return std::nullopt;
927 auto specY = parse_distribution_spec(gc.getExtra(other));
928 if (!specY) return std::nullopt;
929 f = {false, *specY, 0.0, pivotGreater};
930 } else return std::nullopt;
931 factors.push_back(std::move(f));
932 }
933 return PivotConjunctionCond{*specX, std::move(factors)};
934}
935
936/* Closed-form (quadrature) E[X^k | ∧_j (X op Y_j)] for a conjunction of
937 * comparisons sharing the target X. E[X^k | A] = I_k / I_0 with
938 * I_q = ∫ x^q f_X Π_j W_j dx; central via the usual binomial expansion. */
939std::optional<double>
940try_pivotConjunction_conditional_moment(const GenericCircuit &gc, gate_t root,
941 gate_t event_root, unsigned k,
942 bool central)
943{
944 auto m = matchPivotConjunctionConditional(gc, root, event_root);
945 if (!m) return std::nullopt;
946
947 const double den = pivotConjunctionIntegral(m->targetSpec, m->factors, 0);
948 if (std::isnan(den) || !(den > 1e-12))
949 return std::nullopt; /* negligible / undefined event -> infeasible or MC */
950 auto raw = [&](unsigned q) -> std::optional<double> {
951 if (q == 0) return 1.0;
952 const double num = pivotConjunctionIntegral(m->targetSpec, m->factors, q);
953 if (std::isnan(num)) return std::nullopt;
954 return num / den;
955 };
956
957 if (!central) return raw(k);
958 return centralFromRaw(k, raw);
959}
960
961/* Closed-form image of a unary LN / EXP transform over a bare gate_rv
962 * child, via the TransformRuleRegistry (exp(normal) is lognormal,
963 * ln(lognormal) is normal). Read-only: unlike the hybrid simplifier's
964 * fold of the same shape, nothing is rewritten, so no shared-RV
965 * identity can be decoupled -- which is why the moment path may use it
966 * even though it deliberately does not run the simplifier. nullptr
967 * when the child is not a bare parseable rv or no rule covers the
968 * family; the caller falls to MC. */
969std::unique_ptr<Distribution> transform_image(const GenericCircuit &gc,
970 gate_t g,
972{
973 const char *transform = op == PROVSQL_ARITH_LN ? "ln"
974 : op == PROVSQL_ARITH_EXP ? "exp"
975 : nullptr;
976 if (!transform) return nullptr;
977 const auto &wires = gc.getWires(g);
978 if (wires.size() != 1 || gc.getGateType(wires[0]) != gate_rv)
979 return nullptr;
980 auto spec = parse_distribution_spec(gc.getExtra(wires[0]));
981 if (!spec) return nullptr;
982 return closeTransform(transform, *makeDistribution(*spec));
983}
984
985/* Closed-form distribution of a TIMES product over bare, pairwise
986 * distinct gate_rv factors (plus gate_value scalars), via the
987 * ProductRuleRegistry -- read-only, like transform_image, so no shared
988 * identity is disturbed. Quantiles need it (they do not factor the way
989 * the disjoint-product moment shortcuts do); nullptr when the shape or
990 * family combination is outside the registered closures. */
991std::unique_ptr<Distribution> product_image(const GenericCircuit &gc,
992 gate_t g)
993{
994 const auto &wires = gc.getWires(g);
995 if (wires.empty()) return nullptr;
996 double c_total = 1.0;
997 std::vector<std::unique_ptr<Distribution>> dists;
998 std::vector<const Distribution *> factors;
999 std::set<gate_t> seen;
1000 for (gate_t w : wires) {
1001 const auto t = gc.getGateType(w);
1002 if (t == gate_value) {
1003 try { c_total *= parseDoubleStrict(gc.getExtra(w)); }
1004 catch (const CircuitException &) { return nullptr; }
1005 continue;
1006 }
1007 if (t != gate_rv) return nullptr;
1008 if (!seen.insert(w).second) return nullptr; /* dependent */
1009 auto spec = parse_distribution_spec(gc.getExtra(w));
1010 if (!spec) return nullptr;
1011 dists.push_back(makeDistribution(*spec));
1012 factors.push_back(dists.back().get());
1013 }
1014 if (factors.empty()) return nullptr;
1015 /* A single RV with scalar factors is just the affine image; two or
1016 * more dispatch through the product registry. */
1017 std::unique_ptr<Distribution> combined;
1018 if (factors.size() == 1)
1019 combined = std::move(dists.front());
1020 else
1021 combined = closeProductFactors(factors);
1022 if (!combined) return nullptr;
1023 if (c_total != 1.0) return combined->scale(c_total);
1024 return combined;
1025}
1026
1027/* ------------------------------------------------------------------------
1028 * Tier A of the gate_case guard-partition integrator: a CASE that is a
1029 * piecewise function of a SINGLE pivot random variable X. Every guard is a
1030 * bare gate_cmp comparing X against a constant, and every arm value (and the
1031 * default) is affine in X -- a constant, or a*X + b. This is exactly the
1032 * abs / ReLU / clamp piecewise-sugar shape.
1033 *
1034 * Since the whole CASE depends on one RV, E[case^k] is a 1-D integral that
1035 * partitions X's support at the guard thresholds: on each sub-interval a
1036 * single arm fires (first-match, reproducing MonteCarloSampler's order), and
1037 * its affine value's k-th moment over that interval is a binomial combination
1038 * of the truncated raw moments
1039 * ∫_lo^hi x^j f(x) dx = truncatedRawMoment(lo,hi,j) · (F(hi)-F(lo)).
1040 * Returns std::nullopt when the shape is not single-pivot-affine or the family
1041 * lacks a closed-form truncated moment, so the caller falls back to MC. */
1042
1043struct AffineArm { double a, b; }; /* value = a*X + b */
1044
1045std::optional<AffineArm>
1046affineInPivot(const GenericCircuit &gc, gate_t arm, gate_t pivot)
1047{
1048 const auto t = gc.getGateType(arm);
1049 if (t == gate_value)
1050 return AffineArm{0.0, parseDoubleStrict(gc.getExtra(arm))};
1051 if (t == gate_rv)
1052 return (arm == pivot) ? std::optional<AffineArm>(AffineArm{1.0, 0.0})
1053 : std::nullopt;
1054 if (t == gate_arith) {
1055 const auto op = static_cast<provsql_arith_op>(gc.getInfos(arm).first);
1056 const auto &w = gc.getWires(arm);
1057 auto isPivot = [&](gate_t x) {
1058 return gc.getGateType(x) == gate_rv && x == pivot;
1059 };
1060 auto constVal = [&](gate_t x, double &out) {
1061 if (gc.getGateType(x) != gate_value) return false;
1062 out = parseDoubleStrict(gc.getExtra(x));
1063 return true;
1064 };
1065 double c;
1066 if (op == PROVSQL_ARITH_NEG && w.size() == 1 && isPivot(w[0]))
1067 return AffineArm{-1.0, 0.0};
1068 if (op == PROVSQL_ARITH_PLUS && w.size() == 2) {
1069 if (isPivot(w[0]) && constVal(w[1], c)) return AffineArm{1.0, c};
1070 if (isPivot(w[1]) && constVal(w[0], c)) return AffineArm{1.0, c};
1071 }
1072 if (op == PROVSQL_ARITH_MINUS && w.size() == 2) {
1073 if (isPivot(w[0]) && constVal(w[1], c)) return AffineArm{1.0, -c}; /* X - c */
1074 if (isPivot(w[1]) && constVal(w[0], c)) return AffineArm{-1.0, c}; /* c - X */
1075 }
1076 if (op == PROVSQL_ARITH_TIMES && w.size() == 2) {
1077 if (isPivot(w[0]) && constVal(w[1], c)) return AffineArm{c, 0.0};
1078 if (isPivot(w[1]) && constVal(w[0], c)) return AffineArm{c, 0.0};
1079 }
1080 }
1081 return std::nullopt;
1082}
1083
1084std::optional<double>
1085singlePivotCaseRawMoment(const GenericCircuit &gc, gate_t g, unsigned k)
1086{
1087 if (gc.getGateType(g) != gate_case) return std::nullopt;
1088 const auto &wires = gc.getWires(g);
1089 if (wires.size() < 3 || wires.size() % 2 == 0) return std::nullopt;
1090 const std::size_t m = wires.size() / 2; /* guard/value pairs */
1091
1092 /* ---- identify the common pivot RV and each guard's constant threshold ---- */
1093 gate_t pivot{}; bool havePivot = false;
1094 struct Guard { double c; ComparisonOperator op; bool pivotLeft; };
1095 std::vector<Guard> guards;
1096 guards.reserve(m);
1097 for (std::size_t i = 0; i < m; ++i) {
1098 gate_t gd = wires[2 * i];
1099 if (gc.getGateType(gd) != gate_cmp) return std::nullopt;
1100 const auto &gw = gc.getWires(gd);
1101 if (gw.size() != 2) return std::nullopt;
1102 bool ok = false;
1103 ComparisonOperator op = cmpOpFromOid(gc.getInfos(gd).first, ok);
1104 if (!ok || op == ComparisonOperator::EQ || op == ComparisonOperator::NE)
1105 return std::nullopt;
1106 gate_t rvSide, constSide; bool pivotLeft;
1107 if (gc.getGateType(gw[0]) == gate_rv && gc.getGateType(gw[1]) == gate_value) {
1108 rvSide = gw[0]; constSide = gw[1]; pivotLeft = true;
1109 } else if (gc.getGateType(gw[1]) == gate_rv &&
1110 gc.getGateType(gw[0]) == gate_value) {
1111 rvSide = gw[1]; constSide = gw[0]; pivotLeft = false;
1112 } else return std::nullopt;
1113 if (!havePivot) { pivot = rvSide; havePivot = true; }
1114 else if (rvSide != pivot) return std::nullopt; /* multi-pivot -> Tier B */
1115 guards.push_back({parseDoubleStrict(gc.getExtra(constSide)), op, pivotLeft});
1116 }
1117 if (!havePivot) return std::nullopt;
1118
1119 auto spec = parse_distribution_spec(gc.getExtra(pivot));
1120 if (!spec) return std::nullopt;
1121 const auto dist = makeDistribution(*spec);
1122
1123 /* ---- classify each arm (values then default) as affine in the pivot ---- */
1124 std::vector<AffineArm> arms; /* arms[0..m-1] value branches, arms[m] default */
1125 arms.reserve(m + 1);
1126 for (std::size_t i = 0; i < m; ++i) {
1127 auto af = affineInPivot(gc, wires[2 * i + 1], pivot);
1128 if (!af) return std::nullopt;
1129 arms.push_back(*af);
1130 }
1131 {
1132 auto af = affineInPivot(gc, wires.back(), pivot);
1133 if (!af) return std::nullopt;
1134 arms.push_back(*af);
1135 }
1136
1137 /* First-match arm selection at a pivot value x (guards are half-lines, so
1138 * this is constant across the open interior of every partition segment). */
1139 auto guardTrue = [](const Guard &gd, double x) -> bool {
1140 const double lhs = gd.pivotLeft ? x : gd.c;
1141 const double rhs = gd.pivotLeft ? gd.c : x;
1142 switch (gd.op) {
1143 case ComparisonOperator::LT: return lhs < rhs;
1144 case ComparisonOperator::LE: return lhs <= rhs;
1145 case ComparisonOperator::GT: return lhs > rhs;
1146 case ComparisonOperator::GE: return lhs >= rhs;
1147 default: return false;
1148 }
1149 };
1150 auto pickArm = [&](double x) -> const AffineArm & {
1151 for (std::size_t i = 0; i < m; ++i)
1152 if (guardTrue(guards[i], x)) return arms[i];
1153 return arms[m];
1154 };
1155
1156 /* ---- partition the pivot's support at the (sorted, deduped) thresholds ---- */
1157 std::vector<double> cuts;
1158 for (const auto &gd : guards) cuts.push_back(gd.c);
1159 std::sort(cuts.begin(), cuts.end());
1160 cuts.erase(std::unique(cuts.begin(), cuts.end()), cuts.end());
1161
1162 const double NINF = -std::numeric_limits<double>::infinity();
1163 const double PINF = std::numeric_limits<double>::infinity();
1164
1165 double total = 0.0;
1166 const std::size_t nseg = cuts.size() + 1;
1167 for (std::size_t s = 0; s < nseg; ++s) {
1168 const double lo = (s == 0) ? NINF : cuts[s - 1];
1169 const double hi = (s == cuts.size()) ? PINF : cuts[s];
1170 if (lo == hi) continue;
1171
1172 double t; /* interior test point of (lo, hi) */
1173 if (lo == NINF && hi == PINF) t = 0.0;
1174 else if (lo == NINF) t = hi - 1.0;
1175 else if (hi == PINF) t = lo + 1.0;
1176 else t = 0.5 * (lo + hi);
1177 const AffineArm &arm = pickArm(t);
1178
1179 const double dF = dist->cdf(hi) - dist->cdf(lo);
1180 if (std::isnan(dF)) return std::nullopt;
1181 if (dF <= 0.0) continue;
1182
1183 /* E[(aX+b)^k · 1(lo<X<hi)] = Σ_j C(k,j) a^j b^{k-j} ∫ x^j f dx. */
1184 for (unsigned j = 0; j <= k; ++j) {
1185 const double aj = std::pow(arm.a, static_cast<double>(j));
1186 if (aj == 0.0) continue; /* constant arm: only the j=0 term */
1187 const double coef = binomial(k, j) * aj
1188 * std::pow(arm.b, static_cast<double>(k - j));
1189 if (coef == 0.0) continue;
1190 double intj;
1191 if (j == 0) {
1192 intj = dF;
1193 } else {
1194 auto trm = dist->truncatedRawMoment(lo, hi, j);
1195 if (!trm) return std::nullopt; /* family lacks the closed form -> MC */
1196 intj = *trm * dF;
1197 }
1198 total += coef * intj;
1199 }
1200 }
1201 return total;
1202}
1203
1204/* Tier B of the guard-partition integrator: a two-arm CASE
1205 * CASE WHEN (a op b) THEN A ELSE B
1206 * whose single guard compares two DISTINCT independent bare RVs a, b, and whose
1207 * arms A (under the guard) and B (under its complement) are each affine in one
1208 * of a, b. Each arm's contribution is a 1-D integral over its value's pivot
1209 * RV, the other operand marginalised to a CDF weight -- exactly the pivot-
1210 * conjunction integral with a single factor. nullopt for any other shape
1211 * (guard vs a constant is Tier A; >2 arms; an arm not affine in a comparison
1212 * operand; a family without a usable pdf/cdf), so the caller falls to MC. */
1213std::optional<double>
1214twoArmCaseRawMoment(const GenericCircuit &gc, gate_t g, unsigned k)
1215{
1216 if (gc.getGateType(g) != gate_case) return std::nullopt;
1217 const auto &wires = gc.getWires(g);
1218 if (wires.size() != 3) return std::nullopt; /* one guard/value + default */
1219 gate_t guard = wires[0];
1220 if (gc.getGateType(guard) != gate_cmp) return std::nullopt;
1221 const auto &gw = gc.getWires(guard);
1222 if (gw.size() != 2) return std::nullopt;
1223 bool ok = false;
1224 ComparisonOperator op = cmpOpFromOid(gc.getInfos(guard).first, ok);
1225 if (!ok || op == ComparisonOperator::EQ || op == ComparisonOperator::NE)
1226 return std::nullopt;
1227 gate_t a = gw[0], b = gw[1];
1228 if (gc.getGateType(a) != gate_rv || gc.getGateType(b) != gate_rv || a == b)
1229 return std::nullopt;
1230 auto specA = parse_distribution_spec(gc.getExtra(a));
1231 auto specB = parse_distribution_spec(gc.getExtra(b));
1232 if (!specA || !specB) return std::nullopt;
1233 /* op GT/GE with a as the left operand => the guard asserts a > b. */
1234 const bool guard_a_gt_b = (op == ComparisonOperator::GT ||
1236
1237 /* E[value^k · 1(region)] for an arm whose value is affine in a or b, where
1238 * `regionAgtB` says the arm's region is (a > b). */
1239 auto armContribution = [&](gate_t armGate, bool regionAgtB)
1240 -> std::optional<double> {
1241 for (int which = 0; which < 2; ++which) {
1242 gate_t pv = (which == 0) ? a : b;
1243 auto af = affineInPivot(gc, armGate, pv);
1244 if (!af) continue;
1245 const DistributionSpec &pvSpec = (which == 0) ? *specA : *specB;
1246 const DistributionSpec &otSpec = (which == 0) ? *specB : *specA;
1247 /* Weight orientation: with pivot a the region a>b integrates b to F_b(a);
1248 * with pivot b the same region means b<a, i.e. 1-F_a(b). */
1249 const bool pivotGreater = (which == 0) ? regionAgtB : !regionAgtB;
1250 const PivotFactor f{false, otSpec, 0.0, pivotGreater};
1251 double total = 0.0;
1252 for (unsigned j = 0; j <= k; ++j) {
1253 const double aj = std::pow(af->a, static_cast<double>(j));
1254 if (aj == 0.0) continue;
1255 const double coef = binomial(k, j) * aj
1256 * std::pow(af->b, static_cast<double>(k - j));
1257 if (coef == 0.0) continue;
1258 const double I = pivotConjunctionIntegral(pvSpec, {f}, j);
1259 if (std::isnan(I)) return std::nullopt;
1260 total += coef * I;
1261 }
1262 return total;
1263 }
1264 return std::nullopt; /* arm not affine in either comparison operand */
1265 };
1266
1267 auto c0 = armContribution(wires[1], guard_a_gt_b); /* value under guard */
1268 if (!c0) return std::nullopt;
1269 auto c1 = armContribution(wires[2], !guard_a_gt_b); /* default under ¬guard */
1270 if (!c1) return std::nullopt;
1271 return *c0 + *c1;
1272}
1273
1274/* Evaluate a gate_case guard (a bare gate_cmp, or an AND/OR tree of them over
1275 * value RVs) under a strict ordering `rank` of the RVs (higher rank = larger
1276 * value). Returns nullopt if the guard references a constant, an RV outside
1277 * `rank`, or an unsupported gate -- i.e. the CASE is not a pure RV tournament. */
1278std::optional<bool>
1279evalGuardUnderOrder(const GenericCircuit &gc, gate_t guard,
1280 const std::unordered_map<gate_t, int> &rank)
1281{
1282 const auto t = gc.getGateType(guard);
1283 if (t == gate_cmp) {
1284 const auto &w = gc.getWires(guard);
1285 if (w.size() != 2) return std::nullopt;
1286 bool ok = false;
1287 ComparisonOperator op = cmpOpFromOid(gc.getInfos(guard).first, ok);
1288 if (!ok) return std::nullopt;
1289 auto ia = rank.find(w[0]), ib = rank.find(w[1]);
1290 if (ia == rank.end() || ib == rank.end()) return std::nullopt;
1291 const int ra = ia->second, rb = ib->second; /* distinct RVs -> ra != rb */
1292 switch (op) {
1294 case ComparisonOperator::LE: return ra < rb;
1296 case ComparisonOperator::GE: return ra > rb;
1297 case ComparisonOperator::EQ: return false; /* a.s. for continuous RVs */
1298 case ComparisonOperator::NE: return true;
1299 }
1300 return std::nullopt;
1301 }
1302 if (t == gate_times || t == gate_plus) {
1303 const bool isAnd = (t == gate_times);
1304 bool acc = isAnd;
1305 for (gate_t c : gc.getWires(guard)) {
1306 auto v = evalGuardUnderOrder(gc, c, rank);
1307 if (!v) return std::nullopt;
1308 acc = isAnd ? (acc && *v) : (acc || *v);
1309 }
1310 return acc;
1311 }
1312 return std::nullopt;
1313}
1314
1315/* Tier C: a first-match gate_case that computes the max or min of a set of
1316 * independent bare RVs. Recognised by simulating the first-match selection
1317 * over every strict ordering of the value RVs (continuous RVs tie with
1318 * probability 0, so strict orders capture the a.s. behaviour): if the selected
1319 * value is always the maximum (resp. minimum), the CASE is that order
1320 * statistic, whose k-th moment is
1321 * Σ_i ∫ x^k f_{X_i}(x) Π_{j≠i} F_{X_j}(x) dx (max; min flips F to 1-F),
1322 * a sum of pivot-conjunction integrals. Guards may be AND/OR trees of RV-vs-RV
1323 * comparisons among the value RVs; a constant or an outside RV in a guard, a
1324 * non-bare-RV arm, or too many RVs (the n! simulation is capped) decline. */
1325std::optional<double>
1326orderStatCaseRawMoment(const GenericCircuit &gc, gate_t g, unsigned k)
1327{
1328 if (gc.getGateType(g) != gate_case) return std::nullopt;
1329 const auto &wires = gc.getWires(g);
1330 if (wires.size() < 3 || wires.size() % 2 == 0) return std::nullopt;
1331 const std::size_t m = wires.size() / 2;
1332
1333 /* Arms (values + default) must all be bare RVs; collect the distinct set. */
1334 std::vector<gate_t> armRV(m + 1);
1335 std::vector<gate_t> uniq;
1336 std::unordered_map<gate_t, DistributionSpec> specOf;
1337 auto noteRV = [&](gate_t v) -> bool {
1338 if (gc.getGateType(v) != gate_rv) return false;
1339 if (specOf.find(v) == specOf.end()) {
1340 auto sp = parse_distribution_spec(gc.getExtra(v));
1341 if (!sp) return false;
1342 specOf.emplace(v, *sp);
1343 uniq.push_back(v);
1344 }
1345 return true;
1346 };
1347 for (std::size_t i = 0; i < m; ++i) {
1348 armRV[i] = wires[2 * i + 1];
1349 if (!noteRV(armRV[i])) return std::nullopt;
1350 }
1351 armRV[m] = wires.back();
1352 if (!noteRV(armRV[m])) return std::nullopt;
1353
1354 const std::size_t n = uniq.size();
1355 if (n < 2 || n > 7) return std::nullopt; /* n! simulation cap */
1356
1357 /* Guards must reference only the value RVs (checked implicitly by
1358 * evalGuardUnderOrder, which declines on any leaf outside `rank`). */
1359 std::vector<gate_t> guards(m);
1360 for (std::size_t i = 0; i < m; ++i) guards[i] = wires[2 * i];
1361
1362 /* Simulate first-match over every strict ordering of the RVs. */
1363 std::vector<std::size_t> perm(n);
1364 for (std::size_t i = 0; i < n; ++i) perm[i] = i;
1365 bool alwaysMax = true, alwaysMin = true;
1366 do {
1367 std::unordered_map<gate_t, int> rank;
1368 for (std::size_t i = 0; i < n; ++i) rank[uniq[perm[i]]] = static_cast<int>(i);
1369 /* max / min RV under this ordering (highest / lowest rank). */
1370 gate_t maxRV = uniq[perm[n - 1]], minRV = uniq[perm[0]];
1371
1372 gate_t selected = armRV[m]; /* default if no guard fires */
1373 for (std::size_t i = 0; i < m; ++i) {
1374 auto gv = evalGuardUnderOrder(gc, guards[i], rank);
1375 if (!gv) return std::nullopt;
1376 if (*gv) { selected = armRV[i]; break; }
1377 }
1378 if (selected != maxRV) alwaysMax = false;
1379 if (selected != minRV) alwaysMin = false;
1380 if (!alwaysMax && !alwaysMin) return std::nullopt;
1381 } while (std::next_permutation(perm.begin(), perm.end()));
1382
1383 const bool isMax = alwaysMax; /* prefer max if (degenerately) both hold */
1384
1385 /* Σ_i ∫ x^k f_{X_i} Π_{j≠i} (F_{X_j} or 1-F_{X_j}) dx. */
1386 double total = 0.0;
1387 for (std::size_t i = 0; i < n; ++i) {
1388 std::vector<PivotFactor> factors;
1389 factors.reserve(n - 1);
1390 for (std::size_t j = 0; j < n; ++j) {
1391 if (j == i) continue;
1392 factors.push_back({false, specOf.at(uniq[j]), 0.0, isMax});
1393 }
1394 const double I = pivotConjunctionIntegral(specOf.at(uniq[i]), factors, k);
1395 if (std::isnan(I)) return std::nullopt;
1396 total += I;
1397 }
1398 return total;
1399}
1400
1401/* Analytic k-th raw moment of a gate_case, trying each guard-partition tier. */
1402std::optional<double>
1403caseAnalyticRawMoment(const GenericCircuit &gc, gate_t g, unsigned k)
1404{
1405 if (auto v = singlePivotCaseRawMoment(gc, g, k)) return v;
1406 if (auto v = twoArmCaseRawMoment(gc, g, k)) return v;
1407 if (auto v = orderStatCaseRawMoment(gc, g, k)) return v;
1408 return std::nullopt;
1409}
1410
1411double rec_expectation(const GenericCircuit &gc, gate_t g, FootprintCache &fp)
1412{
1413 const auto type = gc.getGateType(g);
1414 switch (type) {
1415 case gate_value:
1416 return parseDoubleStrict(gc.getExtra(g));
1417 case gate_rv: {
1418 // A latent (parametric) leaf -- a parameter is itself a random
1419 // variable -- has no constant-parameter closed form. But the MEAN
1420 // still decomposes exactly when the family's mean is affine in its
1421 // parameters (Normal mean = μ, Uniform mean = (a+b)/2, inverse-
1422 // Gaussian mean = μ): E[X] = E[mean(θ)] = mean(E[θ]) by linearity of
1423 // expectation (no independence assumption), so recurse into the
1424 // parameter wires -- no MC. Nonlinear means (Exponential 1/λ,
1425 // Gamma k/λ, ...) keep meanIsAffine() = false and fall through to MC.
1426 if (rvIsParametric(gc, g)) {
1427 auto tmpl = parse_distribution_template(gc.getExtra(g));
1428 if (tmpl && familyMeanIsAffine(*tmpl)) {
1429 const auto &w = gc.getWires(g);
1430 auto param_mean = [&](const DistributionParam &p) {
1431 return p.wire_slot < 0 ? p.literal
1432 : rec_expectation(gc, w[p.wire_slot], fp);
1433 };
1434 return tmpl->family
1435 ->factory(param_mean(tmpl->p1), param_mean(tmpl->p2))
1436 ->mean();
1437 }
1438 return mc_raw_moment(gc, g, 1, "Expectation of a latent gate_rv");
1439 }
1440 auto spec = parse_distribution_spec(gc.getExtra(g));
1441 if (!spec)
1442 throw CircuitException(
1443 "Expectation: malformed gate_rv extra: " + gc.getExtra(g));
1444 return analytical_mean(*spec);
1445 }
1446 case gate_arith: {
1447 const auto op = static_cast<provsql_arith_op>(gc.getInfos(g).first);
1448 const auto &wires = gc.getWires(g);
1449 switch (op) {
1450 case PROVSQL_ARITH_PLUS: {
1451 double s = 0.0;
1452 for (gate_t c : wires) s += rec_expectation(gc, c, fp);
1453 return s;
1454 }
1455 case PROVSQL_ARITH_MINUS: {
1456 if (wires.size() != 2)
1457 throw CircuitException("gate_arith MINUS must be binary");
1458 return rec_expectation(gc, wires[0], fp)
1459 - rec_expectation(gc, wires[1], fp);
1460 }
1461 case PROVSQL_ARITH_NEG: {
1462 if (wires.size() != 1)
1463 throw CircuitException("gate_arith NEG must be unary");
1464 return -rec_expectation(gc, wires[0], fp);
1465 }
1466 case PROVSQL_ARITH_TIMES: {
1467 if (pairwise_disjoint(fp, wires)) {
1468 double p = 1.0;
1469 for (gate_t c : wires) p *= rec_expectation(gc, c, fp);
1470 return p;
1471 }
1472 return mc_raw_moment(gc, g, 1,
1473 "Expectation of gate_arith TIMES with shared random variables");
1474 }
1476 // Truncation has no linearity to push through.
1477 return mc_raw_moment(gc, g, 1,
1478 "Expectation of gate_arith INTDIV (integer division)");
1479 case PROVSQL_ARITH_DIV: {
1480 if (wires.size() != 2)
1481 throw CircuitException("gate_arith DIV must be binary");
1482 if (gc.getGateType(wires[1]) == gate_value) {
1483 const double divisor = parseDoubleStrict(gc.getExtra(wires[1]));
1484 /* A divisor that is zero in every world leaves no world with a
1485 * value, so there is no moment to report: SQL's NULL, as the
1486 * Monte Carlo path answers when no draw has a value (avg over a
1487 * group whose rows are all certainly absent), rather than an
1488 * infinity or a NaN. */
1489 if (divisor == 0.0)
1490 throw NoValueException(
1491 "Expectation of gate_arith DIV by a constant zero");
1492 return rec_expectation(gc, wires[0], fp) / divisor;
1493 }
1494 return mc_raw_moment(gc, g, 1,
1495 "Expectation of gate_arith DIV with non-constant divisor");
1496 }
1497 case PROVSQL_ARITH_MAX:
1498 case PROVSQL_ARITH_MIN: {
1499 // Order statistics have no linearity to push through. Exact
1500 // closed form for i.i.d. Uniform / Exponential; the layer-cake
1501 // 1-D quadrature for any other independent bare-RV mix (mixed
1502 // families, non-identical parameters, Normal); Monte Carlo only
1503 // when leaves are shared / correlated.
1504 const bool isMax = (op == PROVSQL_ARITH_MAX);
1505 if (auto v = iidOrderStatMean(gc, g, isMax, fp))
1506 return *v;
1507 if (auto v = mixedOrderStatMean(gc, g, isMax, fp))
1508 return *v;
1509 return mc_raw_moment(gc, g, 1,
1510 "Expectation of gate_arith " + std::string(isMax ? "MAX" : "MIN"));
1511 }
1513 /* The value as double precision reads it, which is the value these
1514 * evaluators already carry: the moment is its child's, exactly. */
1515 if (wires.size() == 1)
1516 return rec_expectation(gc, wires[0], fp);
1517 /* otherwise, the sampled group below */
1518 [[fallthrough]];
1522 case PROVSQL_ARITH_CEIL:
1523 case PROVSQL_ARITH_ABS:
1524 // Rounding and absolute value do not commute with expectation
1525 // either (E[round(X)] is not round(E[X])), and no closed-form image
1526 // is registered for them: the estimate over the worlds is what
1527 // there is.
1528 return mc_raw_moment(gc, g, 1,
1529 "Expectation of a gate_arith rounding or absolute value");
1530 case PROVSQL_ARITH_POW:
1531 case PROVSQL_ARITH_LN:
1532 case PROVSQL_ARITH_EXP:
1533 // Nonlinear transforms: expectation does not commute with the
1534 // map, so there is no linearity to push through. A registered
1535 // closed-form image (exp(normal) is lognormal, ln(lognormal)
1536 // is normal) gives the exact answer; otherwise the empirical
1537 // estimate is the general one.
1538 if (auto image = transform_image(gc, g, op))
1539 return image->mean();
1540 return mc_raw_moment(gc, g, 1,
1541 "Expectation of a gate_arith nonlinear transform");
1543 // Order-statistic aggregate over a random member set: no closed
1544 // form; the sampler sorts and interpolates each draw.
1545 return mc_raw_moment(gc, g, 1,
1546 "Expectation of a gate_arith PERCENTILE");
1547 }
1548 throw CircuitException(
1549 "Expectation: unknown gate_arith op tag: " +
1550 std::to_string(static_cast<unsigned>(op)));
1551 }
1552 case gate_mixture: {
1553 const auto &wires = gc.getWires(g);
1554 if (gc.isCategoricalMixture(g)) {
1555 // Categorical mixture: E[M] = Σ π_i · v_i, where each mulinput
1556 // mul_i carries π_i in set_prob and v_i in extra.
1557 double s = 0.0;
1558 for (std::size_t i = 1; i < wires.size(); ++i) {
1559 s += gc.getProb(wires[i])
1560 * parseDoubleStrict(gc.getExtra(wires[i]));
1561 }
1562 return s;
1563 }
1564 // E[mixture(p, X, Y)] = π·E[X] + (1-π)·E[Y], where π = P(p = true).
1565 // For a bare gate_input p, π is the leaf's pinned set_prob. For
1566 // a compound Boolean p, route through evaluateBooleanProbability
1567 // so π honors the tuple-independent semantics of the Boolean DAG.
1568 if (wires.size() != 3)
1569 throw CircuitException(
1570 "Expectation: gate_mixture must have exactly three children");
1571 const double pi = mixturePi(gc, wires[0]);
1572 return pi * rec_expectation(gc, wires[1], fp)
1573 + (1.0 - pi) * rec_expectation(gc, wires[2], fp);
1574 }
1575 case gate_case:
1576 if (auto v = caseAnalyticRawMoment(gc, g, 1))
1577 return *v;
1578 return mc_raw_moment(gc, g, 1, "Expectation of gate type gate_case");
1579 default:
1580 return mc_raw_moment(gc, g, 1,
1581 "Expectation of gate type " + std::string(gate_type_name[type]));
1582 }
1583}
1584
1585double rec_variance(const GenericCircuit &gc, gate_t g, FootprintCache &fp)
1586{
1587 const auto type = gc.getGateType(g);
1588 switch (type) {
1589 case gate_value:
1590 return 0.0;
1591 case gate_rv: {
1592 // Latent (parametric) leaf: no constant-parameter closed form.
1593 // Var(normal(M,1)) = 1 + Var(M) etc. is exact in expectation under
1594 // MC (the sampler draws the latent then the leaf per iteration).
1595 if (rvIsParametric(gc, g)) {
1596 const std::string what = "Variance of a latent gate_rv";
1597 const double mu = mc_raw_moment(gc, g, 1, what);
1598 return mc_central_moment(gc, g, 2, mu, what);
1599 }
1600 auto spec = parse_distribution_spec(gc.getExtra(g));
1601 if (!spec)
1602 throw CircuitException(
1603 "Variance: malformed gate_rv extra: " + gc.getExtra(g));
1604 return analytical_variance(*spec);
1605 }
1606 case gate_arith: {
1607 const auto op = static_cast<provsql_arith_op>(gc.getInfos(g).first);
1608 const auto &wires = gc.getWires(g);
1609 auto mc_var = [&](const std::string &what) {
1610 const double mu = mc_raw_moment(gc, g, 1, what);
1611 return mc_central_moment(gc, g, 2, mu, what);
1612 };
1613 switch (op) {
1614 case PROVSQL_ARITH_PLUS: {
1615 if (pairwise_disjoint(fp, wires)) {
1616 double s = 0.0;
1617 for (gate_t c : wires) s += rec_variance(gc, c, fp);
1618 return s;
1619 }
1620 return mc_var(
1621 "Variance of gate_arith PLUS with shared random variables");
1622 }
1623 case PROVSQL_ARITH_MINUS: {
1624 if (wires.size() != 2)
1625 throw CircuitException("gate_arith MINUS must be binary");
1626 if (pairwise_disjoint(fp, wires)) {
1627 return rec_variance(gc, wires[0], fp)
1628 + rec_variance(gc, wires[1], fp);
1629 }
1630 return mc_var(
1631 "Variance of gate_arith MINUS with shared random variables");
1632 }
1633 case PROVSQL_ARITH_NEG: {
1634 if (wires.size() != 1)
1635 throw CircuitException("gate_arith NEG must be unary");
1636 return rec_variance(gc, wires[0], fp);
1637 }
1638 case PROVSQL_ARITH_TIMES: {
1639 if (pairwise_disjoint(fp, wires)) {
1640 // Var(prod Xi) = prod E[Xi^2] - (prod E[Xi])^2
1641 // = prod (Var[Xi] + E[Xi]^2) - (prod E[Xi])^2
1642 double prod_e2 = 1.0;
1643 double prod_e1 = 1.0;
1644 for (gate_t c : wires) {
1645 const double mu_c = rec_expectation(gc, c, fp);
1646 const double v_c = rec_variance(gc, c, fp);
1647 prod_e2 *= (v_c + mu_c * mu_c);
1648 prod_e1 *= mu_c;
1649 }
1650 return prod_e2 - prod_e1 * prod_e1;
1651 }
1652 return mc_var(
1653 "Variance of gate_arith TIMES with shared random variables");
1654 }
1656 return mc_var("Variance of gate_arith INTDIV (integer division)");
1657 case PROVSQL_ARITH_DIV: {
1658 if (wires.size() != 2)
1659 throw CircuitException("gate_arith DIV must be binary");
1660 if (gc.getGateType(wires[1]) == gate_value) {
1661 const double divisor = parseDoubleStrict(gc.getExtra(wires[1]));
1662 if (divisor == 0.0) // no world has a value: see Expectation
1663 throw NoValueException(
1664 "Variance of gate_arith DIV by a constant zero");
1665 return rec_variance(gc, wires[0], fp) / (divisor * divisor);
1666 }
1667 return mc_var(
1668 "Variance of gate_arith DIV with non-constant divisor");
1669 }
1670 case PROVSQL_ARITH_MAX:
1671 case PROVSQL_ARITH_MIN:
1672 // No closed-form variance decomposition for order statistics; MC.
1673 return mc_var(
1674 "Variance of gate_arith " +
1675 std::string(op == PROVSQL_ARITH_MAX ? "MAX" : "MIN"));
1677 /* The value as double precision reads it, which is the value these
1678 * evaluators already carry: the moment is its child's, exactly. */
1679 if (wires.size() == 1)
1680 return rec_variance(gc, wires[0], fp);
1681 /* otherwise, the sampled group below */
1682 [[fallthrough]];
1686 case PROVSQL_ARITH_CEIL:
1687 case PROVSQL_ARITH_ABS:
1688 return mc_var(
1689 "Variance of a gate_arith rounding or absolute value");
1690 case PROVSQL_ARITH_POW:
1691 case PROVSQL_ARITH_LN:
1692 case PROVSQL_ARITH_EXP:
1693 if (auto image = transform_image(gc, g, op))
1694 return image->variance();
1695 return mc_var("Variance of a gate_arith nonlinear transform");
1697 return mc_var("Variance of a gate_arith PERCENTILE");
1698 }
1699 throw CircuitException(
1700 "Variance: unknown gate_arith op tag: " +
1701 std::to_string(static_cast<unsigned>(op)));
1702 }
1703 case gate_mixture: {
1704 const auto &wires = gc.getWires(g);
1705 if (gc.isCategoricalMixture(g)) {
1706 // Categorical mixture: Var(M) = Σ π_i v_i² − (Σ π_i v_i)².
1707 double e1 = 0.0, e2 = 0.0;
1708 for (std::size_t i = 1; i < wires.size(); ++i) {
1709 const double p = gc.getProb(wires[i]);
1710 const double v = parseDoubleStrict(gc.getExtra(wires[i]));
1711 e1 += p * v;
1712 e2 += p * v * v;
1713 }
1714 return e2 - e1 * e1;
1715 }
1716 // Var(M) = π·(Var(X) + E[X]²) + (1-π)·(Var(Y) + E[Y]²) - E[M]²
1717 // (law of total variance specialised to a Bernoulli mixture).
1718 if (wires.size() != 3)
1719 throw CircuitException(
1720 "Variance: gate_mixture must have exactly three children");
1721 const double pi = mixturePi(gc, wires[0]);
1722 const double ex = rec_expectation(gc, wires[1], fp);
1723 const double ey = rec_expectation(gc, wires[2], fp);
1724 const double vx = rec_variance(gc, wires[1], fp);
1725 const double vy = rec_variance(gc, wires[2], fp);
1726 const double em = pi * ex + (1.0 - pi) * ey;
1727 return pi * (vx + ex * ex)
1728 + (1.0 - pi) * (vy + ey * ey)
1729 - em * em;
1730 }
1731 case gate_case: {
1732 if (auto m2 = caseAnalyticRawMoment(gc, g, 2))
1733 if (auto m1 = caseAnalyticRawMoment(gc, g, 1))
1734 return *m2 - (*m1) * (*m1);
1735 const std::string what = "Variance of gate type gate_case";
1736 const double mu = mc_raw_moment(gc, g, 1, what);
1737 return mc_central_moment(gc, g, 2, mu, what);
1738 }
1739 default: {
1740 const std::string what =
1741 "Variance of gate type " + std::string(gate_type_name[type]);
1742 const double mu = mc_raw_moment(gc, g, 1, what);
1743 return mc_central_moment(gc, g, 2, mu, what);
1744 }
1745 }
1746}
1747
1748double rec_raw_moment(const GenericCircuit &gc, gate_t g, unsigned k,
1749 FootprintCache &fp)
1750{
1751 if (k == 0) return 1.0;
1752 if (k == 1) return rec_expectation(gc, g, fp);
1753
1754 const auto type = gc.getGateType(g);
1755 switch (type) {
1756 case gate_value:
1757 return std::pow(parseDoubleStrict(gc.getExtra(g)),
1758 static_cast<double>(k));
1759 case gate_rv: {
1760 // Latent (parametric) leaf: no constant-parameter closed form.
1761 if (rvIsParametric(gc, g))
1762 return mc_raw_moment(gc, g, k, "Raw moment of a latent gate_rv");
1763 auto spec = parse_distribution_spec(gc.getExtra(g));
1764 if (!spec)
1765 throw CircuitException(
1766 "Moment: malformed gate_rv extra: " + gc.getExtra(g));
1767 return analytical_raw_moment(*spec, k);
1768 }
1769 case gate_arith: {
1770 const auto op = static_cast<provsql_arith_op>(gc.getInfos(g).first);
1771 const auto &wires = gc.getWires(g);
1772 switch (op) {
1773 case PROVSQL_ARITH_NEG: {
1774 if (wires.size() != 1)
1775 throw CircuitException("gate_arith NEG must be unary");
1776 const double v = rec_raw_moment(gc, wires[0], k, fp);
1777 return ((k % 2 == 0) ? 1.0 : -1.0) * v;
1778 }
1779 case PROVSQL_ARITH_PLUS: {
1780 if (pairwise_disjoint(fp, wires)) {
1781 // Fold-left: m_acc[i] holds E[(X1 + ... + Xj)^i] for the
1782 // first j children processed; combining with the next
1783 // independent child Y uses the binomial theorem.
1784 std::vector<double> m_acc(k + 1, 0.0);
1785 for (unsigned i = 0; i <= k; ++i)
1786 m_acc[i] = rec_raw_moment(gc, wires[0], i, fp);
1787 for (size_t w = 1; w < wires.size(); ++w) {
1788 std::vector<double> next(k + 1, 0.0);
1789 std::vector<double> moments_y(k + 1, 0.0);
1790 for (unsigned i = 0; i <= k; ++i)
1791 moments_y[i] = rec_raw_moment(gc, wires[w], i, fp);
1792 for (unsigned kp = 0; kp <= k; ++kp) {
1793 double total = 0.0;
1794 for (unsigned i = 0; i <= kp; ++i) {
1795 total += binomial(kp, i) * m_acc[i] * moments_y[kp - i];
1796 }
1797 next[kp] = total;
1798 }
1799 m_acc = std::move(next);
1800 }
1801 return m_acc[k];
1802 }
1803 return mc_raw_moment(gc, g, k,
1804 "Raw moment of gate_arith PLUS with shared random variables");
1805 }
1806 case PROVSQL_ARITH_MINUS: {
1807 if (wires.size() != 2)
1808 throw CircuitException("gate_arith MINUS must be binary");
1809 if (pairwise_disjoint(fp, wires)) {
1810 double total = 0.0;
1811 for (unsigned i = 0; i <= k; ++i) {
1812 const double sign = ((k - i) % 2 == 0) ? 1.0 : -1.0;
1813 total += binomial(k, i)
1814 * rec_raw_moment(gc, wires[0], i, fp)
1815 * sign
1816 * rec_raw_moment(gc, wires[1], k - i, fp);
1817 }
1818 return total;
1819 }
1820 return mc_raw_moment(gc, g, k,
1821 "Raw moment of gate_arith MINUS with shared random variables");
1822 }
1823 case PROVSQL_ARITH_TIMES: {
1824 if (pairwise_disjoint(fp, wires)) {
1825 // (prod Xi)^k = prod Xi^k; under independence E factors.
1826 double p = 1.0;
1827 for (gate_t c : wires) p *= rec_raw_moment(gc, c, k, fp);
1828 return p;
1829 }
1830 return mc_raw_moment(gc, g, k,
1831 "Raw moment of gate_arith TIMES with shared random variables");
1832 }
1834 return mc_raw_moment(gc, g, k,
1835 "Raw moment of gate_arith INTDIV (integer division)");
1836 case PROVSQL_ARITH_DIV: {
1837 if (wires.size() != 2)
1838 throw CircuitException("gate_arith DIV must be binary");
1839 if (gc.getGateType(wires[1]) == gate_value) {
1840 const double divisor = parseDoubleStrict(gc.getExtra(wires[1]));
1841 if (divisor == 0.0) // no world has a value: see Expectation
1842 throw NoValueException(
1843 "Raw moment of gate_arith DIV by a constant zero");
1844 return rec_raw_moment(gc, wires[0], k, fp)
1845 / std::pow(divisor, static_cast<double>(k));
1846 }
1847 return mc_raw_moment(gc, g, k,
1848 "Raw moment of gate_arith DIV with non-constant divisor");
1849 }
1850 case PROVSQL_ARITH_MAX:
1851 case PROVSQL_ARITH_MIN:
1852 // Order-statistic raw moments have no elementary decomposition; MC.
1853 return mc_raw_moment(gc, g, k,
1854 "Raw moment of gate_arith " +
1855 std::string(op == PROVSQL_ARITH_MAX ? "MAX" : "MIN"));
1857 /* The value as double precision reads it, which is the value these
1858 * evaluators already carry: the moment is its child's, exactly. */
1859 if (wires.size() == 1)
1860 return rec_raw_moment(gc, wires[0], k, fp);
1861 /* otherwise, the sampled group below */
1862 [[fallthrough]];
1866 case PROVSQL_ARITH_CEIL:
1867 case PROVSQL_ARITH_ABS:
1868 return mc_raw_moment(gc, g, k,
1869 "Raw moment of a gate_arith rounding or absolute value");
1870 case PROVSQL_ARITH_POW:
1871 case PROVSQL_ARITH_LN:
1872 case PROVSQL_ARITH_EXP:
1873 if (auto image = transform_image(gc, g, op))
1874 return image->rawMoment(k);
1875 return mc_raw_moment(gc, g, k,
1876 "Raw moment of a gate_arith nonlinear transform");
1878 return mc_raw_moment(gc, g, k,
1879 "Raw moment of a gate_arith PERCENTILE");
1880 }
1881 throw CircuitException(
1882 "Moment: unknown gate_arith op tag: " +
1883 std::to_string(static_cast<unsigned>(op)));
1884 }
1885 case gate_mixture: {
1886 const auto &wires = gc.getWires(g);
1887 if (gc.isCategoricalMixture(g)) {
1888 // Categorical mixture: E[M^k] = Σ π_i v_i^k.
1889 double s = 0.0;
1890 for (std::size_t i = 1; i < wires.size(); ++i) {
1891 const double v = parseDoubleStrict(gc.getExtra(wires[i]));
1892 s += gc.getProb(wires[i])
1893 * std::pow(v, static_cast<double>(k));
1894 }
1895 return s;
1896 }
1897 // E[M^k] = π·E[X^k] + (1-π)·E[Y^k].
1898 if (wires.size() != 3)
1899 throw CircuitException(
1900 "Moment: gate_mixture must have exactly three children");
1901 const double pi = mixturePi(gc, wires[0]);
1902 return pi * rec_raw_moment(gc, wires[1], k, fp)
1903 + (1.0 - pi) * rec_raw_moment(gc, wires[2], k, fp);
1904 }
1905 case gate_case:
1906 if (auto v = caseAnalyticRawMoment(gc, g, k))
1907 return *v;
1908 return mc_raw_moment(gc, g, k, "Raw moment of gate type gate_case");
1909 default:
1910 return mc_raw_moment(gc, g, k,
1911 "Raw moment of gate type " + std::string(gate_type_name[type]));
1912 }
1913}
1914
1915} // namespace
1916
1917/* Conditional dispatch helpers: try closed-form first, fall through
1918 * to MC rejection. Used by all four public compute_* entries to keep
1919 * the conditional logic in one place and the unconditional path
1920 * unchanged. */
1921namespace {
1922
1923[[noreturn]] void raise_infeasible_event(const GenericCircuit &gc, gate_t root)
1924{
1925 (void)gc; (void)root;
1926 throw CircuitException(
1927 "conditioning event is infeasible (empty intersection with the "
1928 "random variable's support)");
1929}
1930
1931double conditional_raw_moment(const GenericCircuit &gc, gate_t root,
1932 unsigned k, gate_t event_root)
1933{
1934 if (k == 0) return 1.0;
1935 /* Collapsed exact posterior: a latent conditioned on a discrete rv over it
1936 * equalling a correlated COUNT (Y(R) = C). Rao-Blackwellises the count to a
1937 * pmf by 1-D quadrature over its shared latent, then closes the R posterior
1938 * by a second 1-D quadrature -- replacing the degenerating rejection sampler
1939 * with an exact quadrature. Declines (nullopt) on any shape mismatch. */
1940 if (auto cf = collapsedConditionalMoment(gc, root, event_root, k))
1941 return *cf;
1942 /* Conjugate prior/likelihood shape: the posterior is a first-class
1943 * distribution of the prior's family, so the raw moment is its family
1944 * closed form -- exact, deterministic, works at rv_mc_samples = 0.
1945 * Declines (nullopt) on any shape mismatch. */
1946 if (auto post = conjugatePosterior(gc, root, event_root))
1947 return makeDistribution(*post)->rawMoment(k);
1948 /* Continuous-density evidence (latent-variable posterior): likelihood
1949 * weighting. The closed-form / rejection paths below assume a bare-rv
1950 * truncation event, so they do not apply. */
1951 if (circuitHasObserve(gc, event_root)) {
1952 const std::string what = "Posterior raw moment";
1953 auto post = importanceSampleConditional(
1954 gc, root, event_root, mc_samples_or_throw(what));
1955 checkPosteriorOrThrow(post, what);
1956 return weightedRawMoment(post, k);
1957 }
1958 if (auto cf = try_truncated_closed_form(gc, root, event_root, k, false))
1959 return *cf;
1960 if (auto cf = try_rvVsRv_conditional_moment(gc, root, event_root, k, false))
1961 return *cf;
1962 if (auto cf = try_pivotConjunction_conditional_moment(gc, root, event_root,
1963 k, false))
1964 return *cf;
1965 if (eventIsProvablyInfeasible(gc, root, event_root))
1966 raise_infeasible_event(gc, root);
1967 return mc_conditional_raw_moment(
1968 gc, root, k, event_root,
1969 "Conditional raw moment of gate type " +
1970 std::string(gate_type_name[gc.getGateType(root)]));
1971}
1972
1973double conditional_central_moment(const GenericCircuit &gc, gate_t root,
1974 unsigned k, gate_t event_root)
1975{
1976 if (k == 0) return 1.0;
1977 if (k == 1) return 0.0;
1978 /* Collapsed exact posterior variance from the collapsed raw moments
1979 * (Var = E[R^2|C] - E[R|C]^2); declines together with the mean. */
1980 if (k == 2) {
1981 auto m1 = collapsedConditionalMoment(gc, root, event_root, 1);
1982 auto m2 = collapsedConditionalMoment(gc, root, event_root, 2);
1983 if (m1 && m2) return *m2 - (*m1) * (*m1);
1984 }
1985 /* Conjugate shape: exact central moment of the posterior distribution
1986 * (family variance for k = 2, binomial expansion over the family raw
1987 * moments above that). */
1988 if (auto post = conjugatePosterior(gc, root, event_root)) {
1989 auto dist = makeDistribution(*post);
1990 if (k == 2) return dist->variance();
1991 const double mu = dist->mean();
1992 double total = 0.0;
1993 for (unsigned i = 0; i <= k; ++i) {
1994 const double mu_pow = std::pow(-mu, static_cast<double>(k - i));
1995 total += binomial(k, i) * mu_pow * dist->rawMoment(i);
1996 }
1997 return total;
1998 }
1999 /* Continuous-density evidence: one importance-sampling pass yields both
2000 * the posterior mean and the central moment (no resampling). */
2001 if (circuitHasObserve(gc, event_root)) {
2002 const std::string what = "Posterior central moment";
2003 auto post = importanceSampleConditional(
2004 gc, root, event_root, mc_samples_or_throw(what));
2005 checkPosteriorOrThrow(post, what);
2006 const double mu = weightedRawMoment(post, 1);
2007 return weightedCentralMoment(post, k, mu);
2008 }
2009 if (auto cf = try_truncated_closed_form(gc, root, event_root, k, true))
2010 return *cf;
2011 if (auto cf = try_rvVsRv_conditional_moment(gc, root, event_root, k, true))
2012 return *cf;
2013 if (auto cf = try_pivotConjunction_conditional_moment(gc, root, event_root,
2014 k, true))
2015 return *cf;
2016 if (eventIsProvablyInfeasible(gc, root, event_root))
2017 raise_infeasible_event(gc, root);
2018 /* MC central: need μ_A first. */
2019 const double mu = conditional_raw_moment(gc, root, 1, event_root);
2020 return mc_conditional_central_moment(
2021 gc, root, k, mu, event_root,
2022 "Conditional central moment of gate type " +
2023 std::string(gate_type_name[gc.getGateType(root)]));
2024}
2025
2026} // namespace
2027
2029 std::optional<gate_t> event_root)
2030{
2031 if (event_root.has_value())
2032 return conditional_raw_moment(gc, root, 1, *event_root);
2033 FootprintCache fp(gc);
2034 return rec_expectation(gc, root, fp);
2035}
2036
2037double compute_raw_moment(const GenericCircuit &gc, gate_t root, unsigned k,
2038 std::optional<gate_t> event_root)
2039{
2040 if (event_root.has_value())
2041 return conditional_raw_moment(gc, root, k, *event_root);
2042 FootprintCache fp(gc);
2043 return rec_raw_moment(gc, root, k, fp);
2044}
2045
2046double compute_central_moment(const GenericCircuit &gc, gate_t root, unsigned k,
2047 std::optional<gate_t> event_root)
2048{
2049 if (event_root.has_value())
2050 return conditional_central_moment(gc, root, k, *event_root);
2051 if (k == 0) return 1.0;
2052 if (k == 1) return 0.0;
2053 FootprintCache fp(gc);
2054 if (k == 2) return rec_variance(gc, root, fp);
2055 // E[(X - mu)^k] = sum_{i=0}^{k} C(k, i) (-mu)^(k-i) E[X^i]
2056 const double mu = rec_expectation(gc, root, fp);
2057 double total = 0.0;
2058 for (unsigned i = 0; i <= k; ++i) {
2059 const double mu_pow = std::pow(-mu, static_cast<double>(k - i));
2060 total += binomial(k, i) * mu_pow * rec_raw_moment(gc, root, i, fp);
2061 }
2062 return total;
2063}
2064
2065/* ─────────────────────── quantiles (§B.1) ─────────────────────── */
2066
2067namespace {
2068
2069/* Empirical p-quantile with the linear-interpolation convention
2070 * PostgreSQL's percentile_cont uses (type 7: h = p·(n-1)), in its order of
2071 * floats (NaN last). Draws with no value (e.g. empty-group SQL NULLs from
2072 * gate_agg) are dropped like the MC moment estimators do. */
2073double empirical_quantile(const std::vector<std::optional<double>> &draws,
2074 double p)
2075{
2076 std::vector<double> xs = definedDraws(draws);
2077 if (xs.empty()) throw NoValueException("Quantile");
2078 std::sort(xs.begin(), xs.end(), sql_less<double>);
2079 if (p <= 0.0) return xs.front();
2080 if (p >= 1.0) return xs.back();
2081 const double h = p * static_cast<double>(xs.size() - 1);
2082 const std::size_t i = static_cast<std::size_t>(h);
2083 if (i + 1 >= xs.size()) return xs.back();
2084 const double frac = h - static_cast<double>(i);
2085 return xs[i] + frac * (xs[i + 1] - xs[i]);
2086}
2087
2088/* Exact quantile of a categorical-form gate_mixture: the generalised
2089 * inverse F⁻¹(p) = min{v : F(v) >= p} over the (value, mass) outcomes.
2090 * nullopt if an outcome's value fails to parse (falls to MC). */
2091std::optional<double> categorical_quantile(const GenericCircuit &gc,
2092 gate_t mix, double p)
2093{
2094 const auto &wires = gc.getWires(mix);
2095 std::vector<std::pair<double, double>> outcomes;
2096 outcomes.reserve(wires.size());
2097 for (std::size_t i = 1; i < wires.size(); ++i) {
2098 double v;
2099 try { v = parseDoubleStrict(gc.getExtra(wires[i])); }
2100 catch (const CircuitException &) { return std::nullopt; }
2101 outcomes.emplace_back(v, gc.getProb(wires[i]));
2102 }
2103 if (outcomes.empty()) return std::nullopt;
2104 std::sort(outcomes.begin(), outcomes.end());
2105 double cum = 0.0;
2106 for (const auto &vp : outcomes) {
2107 cum += vp.second;
2108 if (cum >= p && cum > 0.0) return vp.first;
2109 }
2110 return outcomes.back().first; /* p ≈ 1 vs. mass-sum roundoff */
2111}
2112
2113/* Closed-form (or numerically inverted) quantile of a bare gate_rv,
2114 * optionally truncated to [lo, hi] by a conditioning event: the
2115 * truncated quantile is Q(F(lo) + p·(F(hi) − F(lo))). Tries the
2116 * family's elementary inverse CDF first, then the generic monotone
2117 * CDF bisection (Erlang / Gamma); nullopt when neither decides, so
2118 * the caller falls to MC. */
2119std::optional<double> analytic_dist_quantile(const Distribution &dist,
2120 double p, double lo, double hi);
2121
2122std::optional<double> analytic_rv_quantile(const DistributionSpec &spec,
2123 double p, double lo, double hi)
2124{
2125 return analytic_dist_quantile(*makeDistribution(spec), p, lo, hi);
2126}
2127
2128std::optional<double> analytic_dist_quantile(const Distribution &dist,
2129 double p, double lo, double hi)
2130{
2131 if (p <= 0.0 || p >= 1.0) {
2132 /* Quantile limits are the (truncated) support edges. */
2133 const auto sup = dist.support();
2134 return (p <= 0.0) ? std::max(sup.lo, lo) : std::min(sup.hi, hi);
2135 }
2136 double u = p;
2137 if (std::isfinite(lo) || std::isfinite(hi)) {
2138 const double f_lo = std::isfinite(lo) ? dist.cdf(lo) : 0.0;
2139 const double f_hi = std::isfinite(hi) ? dist.cdf(hi) : 1.0;
2140 if (std::isnan(f_lo) || std::isnan(f_hi)) return std::nullopt;
2141 const double mass = f_hi - f_lo;
2142 if (mass < 1e-12) return std::nullopt; /* vanishing mass: MC's call */
2143 u = f_lo + p * mass;
2144 }
2145 double q = std::numeric_limits<double>::quiet_NaN();
2146 if (auto cf = dist.quantile(u)) q = *cf;
2147 if (std::isnan(q)) q = numericQuantile(dist, u);
2148 if (std::isnan(q)) return std::nullopt;
2149 /* Clamp defensively into the truncation interval (roundoff in u). */
2150 if (q < lo) q = lo;
2151 if (q > hi) q = hi;
2152 return q;
2153}
2154
2155} // namespace
2156
2157double compute_quantile(const GenericCircuit &gc, gate_t root, double p,
2158 std::optional<gate_t> event_root)
2159{
2160 const double inf = std::numeric_limits<double>::infinity();
2161
2162 if (event_root.has_value()) {
2163 /* Conjugate shape: exact quantile of the posterior distribution
2164 * (elementary inverse CDF or the monotone CDF bisection). */
2165 if (auto post = conjugatePosterior(gc, root, *event_root))
2166 if (auto q = analytic_rv_quantile(*post, p, -inf, inf))
2167 return *q;
2168 /* Continuous-density evidence: weighted empirical posterior quantile. */
2169 if (circuitHasObserve(gc, *event_root)) {
2170 const std::string what = "Posterior quantile";
2171 auto post = importanceSampleConditional(
2172 gc, root, *event_root, mc_samples_or_throw(what));
2173 checkPosteriorOrThrow(post, what);
2174 return weightedQuantile(std::move(post), p);
2175 }
2176 /* Bare RV under an interval event: exact truncated quantile. */
2177 if (auto m = matchTruncatedSingleRv(gc, root, *event_root)) {
2178 if (auto q = analytic_rv_quantile(m->spec, p, m->lo, m->hi))
2179 return *q;
2180 }
2181 if (eventIsProvablyInfeasible(gc, root, *event_root))
2182 raise_infeasible_event(gc, root);
2184 gc, root, *event_root,
2185 mc_samples_or_throw("Conditional quantile"));
2186 check_acceptance_or_throw(cs, "Conditional quantile");
2187 return empirical_quantile(std::move(cs.accepted), p);
2188 }
2189
2190 const auto type = gc.getGateType(root);
2191 if (type == gate_value) {
2192 /* Dirac at c: every quantile is c. */
2193 try { return parseDoubleStrict(gc.getExtra(root)); }
2194 catch (const CircuitException &) { /* fall through to MC */ }
2195 } else if (type == gate_rv) {
2196 if (auto spec = parse_distribution_spec(gc.getExtra(root)))
2197 if (auto q = analytic_rv_quantile(*spec, p, -inf, inf))
2198 return *q;
2199 } else if (type == gate_mixture && gc.isCategoricalMixture(root)) {
2200 if (auto q = categorical_quantile(gc, root, p))
2201 return *q;
2202 } else if (type == gate_arith) {
2203 /* A unary LN / EXP transform, or a product of independent factors,
2204 * with a registered closed-form image (exp(normal) is lognormal,
2205 * lognormal products are lognormal, ...) has an exact quantile
2206 * through the image distribution. */
2207 const auto op = static_cast<provsql_arith_op>(gc.getInfos(root).first);
2208 std::unique_ptr<Distribution> image =
2209 (op == PROVSQL_ARITH_TIMES) ? product_image(gc, root)
2210 : transform_image(gc, root, op);
2211 if (image)
2212 if (auto q = analytic_dist_quantile(*image, p, -inf, inf))
2213 return *q;
2214 }
2215
2216 /* Compound scalar circuits (arith trees, Bernoulli mixtures, ...):
2217 * quantiles do not decompose like moments, so estimate from the
2218 * empirical distribution at the rv_mc_samples budget. */
2219 return empirical_quantile(
2220 monteCarloScalarSamples(gc, root, mc_samples_or_throw("Quantile")),
2221 p);
2222}
2223
2224/**
2225 * @brief Lift conditioning out of a scalar arithmetic expression.
2226 *
2227 * Implements @c "f(X|A, Y|B, …) = f(X, Y, …) | (A ∧ B ∧ …)": walks the scalar
2228 * tree rooted at @p root, replaces every nested @c gate_conditioned by a
2229 * transparent passthrough to its target (so the tree becomes the plain
2230 * arithmetic over the unconditioned distributions), collects the evidence
2231 * children, and conjoins them -- together with any pre-existing @p event_opt
2232 * -- into a single conditioning event. The conjunction is built as an
2233 * in-memory @c gate_times over the evidence gates, all of which already live
2234 * in the (joint) circuit, so a base @c gate_rv shared between a value and its
2235 * evidence keeps a single draw under the MC sampler. A conditioned ROOT is
2236 * peeled to its bare target (returned), so a stored "X | C" reaching any
2237 * low-level RV entry point keeps the closed-form scalar path; the (possibly
2238 * new) root is returned. Leaves @p event_opt untouched and returns @p root
2239 * unchanged when the expression carries no conditioning.
2240 */
2242 std::optional<gate_t> &event_opt)
2243{
2244 std::vector<gate_t> evidences;
2245
2246 // 1. Peel a conditioned ROOT to its bare target. A root has no parent
2247 // wires, so it is replaced by its target directly rather than the
2248 // single-child gate_arith passthrough the buried case below needs;
2249 // keeping a bare gate_rv root preserves the closed-form truncation
2250 // path for "X | (X > c)". Handles the 2-child rv/agg carrier
2251 // [target, condition] and (defensively) the 3-child uuid carrier
2252 // [target, evidence, joint]; iterates in case of nested conditioning.
2253 while (gc.getGateType(root) == gate_conditioned) {
2254 const auto &w = gc.getWires(root);
2255 if (w.size() < 2)
2256 throw CircuitException("malformed conditioned gate in scalar expression");
2257 evidences.push_back(w[1]);
2258 root = w[0];
2259 }
2260
2261 // 2. Replace every BURIED gate_conditioned by an arith passthrough to its
2262 // target, collecting evidence as well.
2263 std::set<gate_t> seen;
2264 std::vector<gate_t> stack{root};
2265 while (!stack.empty()) {
2266 gate_t g = stack.back();
2267 stack.pop_back();
2268 if (!seen.insert(g).second) continue;
2269 if (gc.getGateType(g) == gate_conditioned) {
2270 const auto &w = gc.getWires(g);
2271 if (w.size() < 2)
2272 throw CircuitException("malformed conditioned gate in scalar expression");
2273 gate_t target = w[0];
2274 evidences.push_back(w[1]);
2275 gc.liftConditionedToTarget(g, target); // g becomes arith PLUS [target]
2276 stack.push_back(target);
2277 } else {
2278 for (gate_t c : gc.getWires(g))
2279 stack.push_back(c);
2280 }
2281 }
2282 if (evidences.empty())
2283 return root;
2284 if (event_opt.has_value())
2285 evidences.push_back(*event_opt);
2286 gate_t cond;
2287 if (evidences.size() == 1)
2288 cond = evidences[0];
2289 else {
2290 cond = gc.setGate(gate_times); // AND of all evidence (and prior event)
2291 auto &cw = gc.getWires(cond);
2292 for (gate_t e : evidences)
2293 cw.push_back(e);
2294 }
2295 event_opt = cond;
2296 return root;
2297}
2298
2299} // namespace provsql
2300
2301extern "C" {
2302
2303/**
2304 * @brief SQL: rv_moment(token uuid, k integer, central boolean,
2305 * prov uuid DEFAULT gate_one()) -> float8
2306 *
2307 * Single C entry point shared by the @c expected / @c variance /
2308 * @c moment / @c central_moment SQL functions. The SQL wrappers
2309 * select the (k, central) pair that matches their semantics:
2310 * - @c expected(rv, prov): k=1, central=false.
2311 * - @c variance(rv, prov): k=2, central=true.
2312 * - @c moment(rv, k, prov): central=false.
2313 * - @c central_moment(rv, k, prov): central=true.
2314 *
2315 * The @p prov argument carries the conditioning event: typically the
2316 * row's @c provenance() gate after a @c WHERE predicate folded a
2317 * @c gate_cmp into it. When @p prov resolves to @c gate_one (the
2318 * default, or the load-time simplification of any always-true
2319 * sub-circuit) the unconditional path runs unchanged. Otherwise we
2320 * load a JOINT circuit reaching both roots, so shared @c gate_rv
2321 * leaves collapse to a single @c gate_t -- the property the
2322 * conditional MC sampler relies on to couple the indicator's draw
2323 * with the value's draw.
2324 */
2325/**
2326 * @brief SQL: agg_avg_moment_exact(token uuid, k integer) -> float8
2327 *
2328 * The exact independent-rows arm behind @c agg_raw_moment's @c avg
2329 * dispatch: E[AVG^k | COUNT >= 1] from the joint (sum, count) PMF over
2330 * pairwise leaf-disjoint contributors (@c aggAvgRawMomentExact).
2331 * Returns NULL when the shape is out of scope -- shared leaves, compound
2332 * contributors, unset probabilities -- and the SQL caller falls back to
2333 * the Monte-Carlo scalar path.
2334 */
2335Datum agg_avg_moment_exact(PG_FUNCTION_ARGS)
2336{
2337 try {
2338 provsql_interrupt_scope interrupt_scope;
2339 pg_uuid_t *token = PG_GETARG_UUID_P(0);
2340 const int32 k_signed = PG_GETARG_INT32(1);
2341
2342 if (k_signed < 0)
2343 provsql_error("agg_avg_moment_exact: k must be non-negative (got %d)",
2344 k_signed);
2345
2346 auto gc = getGenericCircuit(*token);
2347 gate_t root = gc.getGate(uuid2string(*token));
2348 bool ok = false;
2349 const double r = provsql::aggAvgRawMomentExact(
2350 gc, root, static_cast<unsigned>(k_signed), ok);
2351 if (!ok)
2352 PG_RETURN_NULL();
2353 return Float8GetDatum(r);
2354 } catch (const std::exception &e) {
2356 provsql_error("agg_avg_moment_exact: %s", e.what());
2357 } catch (...) {
2359 provsql_error("agg_avg_moment_exact: unknown exception");
2360 }
2361 PG_RETURN_NULL();
2362}
2363
2364Datum rv_moment(PG_FUNCTION_ARGS)
2365{
2366 try {
2367 provsql_interrupt_scope interrupt_scope;
2368 pg_uuid_t *token = PG_GETARG_UUID_P(0);
2369 const int32 k_signed = PG_GETARG_INT32(1);
2370 const bool central = PG_GETARG_BOOL(2);
2371 pg_uuid_t *prov = PG_GETARG_UUID_P(3);
2372
2373 if (k_signed < 0)
2374 provsql_error("rv_moment: k must be non-negative (got %d)", k_signed);
2375 const unsigned k = static_cast<unsigned>(k_signed);
2376
2377 gate_t root_gate, event_gate;
2378 auto gc = getJointCircuit(*token, *prov, root_gate, event_gate);
2379
2380 /* gate_one event = unconditional after load-time simplification. */
2381 std::optional<gate_t> event_opt;
2382 if (gc.getGateType(event_gate) != gate_one)
2383 event_opt = event_gate;
2384
2385 /* Arithmetic over conditioned distributions: peel a conditioned ROOT to
2386 * its bare target (keeping the closed-form truncation path for the
2387 * bare-rv case) and lift any nested gate_conditioned out of the scalar
2388 * expression, folding its evidence into the conditioning event
2389 * (f(X|A, Y|B) = f(X, Y) | (A ∧ B)). Works whether the token arrives
2390 * already unpacked by the SQL dispatcher or as a raw conditioned root
2391 * (Studio's distribution panel calls this low-level binding directly). */
2392 root_gate = provsql::lift_conditioning(gc, root_gate, event_opt);
2393
2394 double result;
2395 if (central)
2396 result = provsql::compute_central_moment(gc, root_gate, k, event_opt);
2397 else if (k == 1)
2398 result = provsql::compute_expectation(gc, root_gate, event_opt);
2399 else
2400 result = provsql::compute_raw_moment(gc, root_gate, k, event_opt);
2401 return Float8GetDatum(result);
2402 } catch (const provsql::NoValueException &) {
2403 /* A value defined in no world (an aggregate over a group empty in
2404 * every world of positive probability): SQL's NULL, as agg_raw_moment
2405 * answers for the same case. */
2407 PG_RETURN_NULL();
2408 } catch (const std::exception &e) {
2410 provsql_error("rv_moment: %s", e.what());
2411 } catch (...) {
2413 provsql_error("rv_moment: unknown exception");
2414 }
2415 PG_RETURN_NULL();
2416}
2417
2418/**
2419 * @brief SQL: rv_quantile(token uuid, p float8,
2420 * prov uuid DEFAULT gate_one()) -> float8
2421 *
2422 * C entry point behind the polymorphic @c quantile SQL dispatcher.
2423 * Same conditioning plumbing as @c rv_moment (joint circuit, nested
2424 * @c gate_conditioned lifting); the evaluation itself is
2425 * @c compute_quantile: closed-form / numerically inverted CDF for a
2426 * (possibly truncated) bare @c gate_rv, exact generalised inverse for
2427 * a categorical mixture, empirical MC quantile for compound circuits.
2428 */
2429Datum rv_quantile(PG_FUNCTION_ARGS)
2430{
2431 try {
2432 provsql_interrupt_scope interrupt_scope;
2433 pg_uuid_t *token = PG_GETARG_UUID_P(0);
2434 const double p = PG_GETARG_FLOAT8(1);
2435 pg_uuid_t *prov = PG_GETARG_UUID_P(2);
2436
2437 if (std::isnan(p) || p < 0.0 || p > 1.0)
2438 provsql_error("rv_quantile: p must be in [0, 1] (got %g)", p);
2439
2440 gate_t root_gate, event_gate;
2441 auto gc = getJointCircuit(*token, *prov, root_gate, event_gate);
2442
2443 /* gate_one event = unconditional after load-time simplification. */
2444 std::optional<gate_t> event_opt;
2445 if (gc.getGateType(event_gate) != gate_one)
2446 event_opt = event_gate;
2447
2448 root_gate = provsql::lift_conditioning(gc, root_gate, event_opt);
2449
2450 return Float8GetDatum(
2451 provsql::compute_quantile(gc, root_gate, p, event_opt));
2452 } catch (const provsql::NoValueException &) {
2454 PG_RETURN_NULL();
2455 } catch (const std::exception &e) {
2457 provsql_error("rv_quantile: %s", e.what());
2458 } catch (...) {
2460 provsql_error("rv_quantile: unknown exception");
2461 }
2462 PG_RETURN_NULL();
2463}
2464
2465/**
2466 * @brief SQL: rv_evidence(evidence uuid) -> float8
2467 *
2468 * The marginal likelihood @c P(data) of an evidence circuit: the mean raw
2469 * importance weight over @c provsql.rv_mc_samples prior draws (the same
2470 * quantity rejection conditioning computes as @c P(C), now a product of the
2471 * observations' densities). Backs @c provsql.evidence.
2472 */
2473Datum rv_evidence(PG_FUNCTION_ARGS)
2474{
2475 try {
2476 provsql_interrupt_scope interrupt_scope;
2477 pg_uuid_t *token = PG_GETARG_UUID_P(0);
2478 auto gc = getGenericCircuit(*token);
2479 gate_t root = gc.getGate(uuid2string(*token));
2480 /* Conjugate shape with predictive densities registered for every
2481 * observation in the fold: the marginal likelihood is the exact
2482 * product of the sequential predictives (chain rule), accumulated
2483 * in log space. */
2484 if (auto le = provsql::conjugateLogEvidence(gc, root))
2485 return Float8GetDatum(std::exp(*le));
2486 if (provsql_rv_mc_samples == 0)
2488 "rv_evidence: provsql.rv_mc_samples is 0 (the marginal likelihood is "
2489 "estimated by Monte Carlo); set it to a positive sample budget");
2490 const double e = provsql::importanceEvidence(
2491 gc, root, static_cast<unsigned>(provsql_rv_mc_samples));
2492 return Float8GetDatum(e);
2493 } catch (const std::exception &ex) {
2495 provsql_error("rv_evidence: %s", ex.what());
2496 } catch (...) {
2498 provsql_error("rv_evidence: unknown exception");
2499 }
2500 PG_RETURN_NULL();
2501}
2502
2503} // extern "C"
Exact closed-form HAVING COUNT(*) op C probability over safe-join lineage – the recursive marginal-ve...
ComparisonOperator cmpOpFromOid(Oid op_oid, bool &ok)
Map a PostgreSQL comparison-operator OID to a ComparisonOperator.
Typed aggregation value, operator, and aggregator abstractions.
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
Definition Aggregation.h:40
@ LT
Less than (<).
Definition Aggregation.h:44
@ GT
Greater than (>).
Definition Aggregation.h:46
@ LE
Less than or equal (<=).
Definition Aggregation.h:43
@ NE
Not equal (<>).
Definition Aggregation.h:42
@ GE
Greater than or equal (>=).
Definition Aggregation.h:45
bool sql_less(T a, T b)
The order PostgreSQL gives numbers: for floats, NaN equals NaN and is greater than every other value ...
Closed-form CDF resolution for trivial gate_cmp shapes.
Boolean-expression (lineage formula) semiring.
Boolean provenance circuit with support for knowledge compilation.
GenericCircuit getJointCircuit(const std::vector< pg_uuid_t > &tokens, std::vector< gate_t > &gates)
Multi-root variant of getJointCircuit.
GenericCircuit getGenericCircuit(pg_uuid_t token)
Build a GenericCircuit from the mmap store rooted at token.
Build in-memory circuits from the mmap-backed persistent store.
Generic directed-acyclic-graph circuit template and gate identifier.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Rao-Blackwellised (collapsed) evaluation of a correlated COUNT / SUM and of a latent conditioned on s...
The single comparator-resolution pipeline and the single Boolean-subcircuit probability entry point,...
Exact conjugate-prior posteriors for observe-evidence circuits.
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Datum rv_quantile(PG_FUNCTION_ARGS)
SQL: rv_quantile(token uuid, p float8, prov uuid DEFAULT gate_one()) -> float8...
Datum rv_moment(PG_FUNCTION_ARGS)
Datum agg_avg_moment_exact(PG_FUNCTION_ARGS)
SQL: rv_moment(token uuid, k integer, central boolean, prov uuid DEFAULT gate_on...
Datum rv_evidence(PG_FUNCTION_ARGS)
SQL: rv_evidence(evidence uuid) -> float8.
Analytical expectation / variance / moment evaluator over RV circuits.
Monte Carlo sampling over a GenericCircuit, RV-aware.
Shared 1-D quadrature core for the pivot-conjunction and order-statistic closed forms.
Catalog of probability-evaluation methods (Strategy + registry).
Continuous random-variable helpers (distribution parsing, moments).
Support-based bound check for continuous-RV comparators.
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
Definition Circuit.hpp:195
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
double getProb(gate_t g) const
Return the probability for gate g.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
void liftConditionedToTarget(gate_t g, gate_t target)
Replace a gate_conditioned g by a transparent passthrough to its target child (a single-child gate_ar...
void setExtra(gate_t g, const std::string &ex)
Attach a string extra to gate g.
void setProb(gate_t g, double p)
Set the probability for gate g.
Abstract per-family continuous distribution.
The quantity asked for has a value in no world (an aggregate over a group empty in every world of pos...
Definition Expectation.h:47
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
std::optional< std::vector< std::pair< double, std::optional< double > > > > enumerateScalarWorlds(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event, unsigned max_inputs)
The possible worlds of a circuit whose only random sources are Boolean inputs: the exact alternative ...
double compute_raw_moment(const GenericCircuit &gc, gate_t root, unsigned k, std::optional< gate_t > event_root)
Compute the raw moment (or if event_root is set) for k >= 0.
std::optional< double > conjugateLogEvidence(const GenericCircuit &gc, gate_t evidence)
The exact log marginal likelihood of a conjugate-shaped evidence circuit; std::nullopt on any shape ...
double compute_quantile(const GenericCircuit &gc, gate_t root, double p, std::optional< gate_t > event_root)
Compute the p-quantile of the scalar rooted at root (of the truncated distribution if event_root is ...
double aggAvgRawMomentExact(GenericCircuit &gc, gate_t g, unsigned k, bool &ok)
Exact k-th raw moment of AVG = SUM/COUNT over independent rows, conditional on COUNT >= 1.
std::vector< std::optional< double > > monteCarloScalarSamples(const GenericCircuit &gc, gate_t root, unsigned samples)
Sample a scalar sub-circuit samples times and return the draws.
gate_t lift_conditioning(GenericCircuit &gc, gate_t root, std::optional< gate_t > &event_opt)
Lift conditioning out of a scalar arithmetic expression.
double analytical_variance(const DistributionSpec &d)
Closed-form variance Var(X) for a basic distribution.
double importanceEvidence(const GenericCircuit &gc, gate_t evidence, unsigned samples)
Marginal likelihood P(data) of evidence: the mean raw importance weight over samples prior draws.
double booleanSubcircuitProbability(GenericCircuit &gc, gate_t root, const std::string &method, const std::string &args, bool inv_free_cert, const Tolerance &tol, bool mc_fallback, std::string *actual_method_out)
Probability of the Boolean function rooted at root in gc – THE single entry point over the method por...
std::unique_ptr< Distribution > closeTransform(const char *transform, const Distribution &x)
The image distribution of transform applied to x, when a registered rule covers x's family; nullptr o...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::optional< double > centralFromRaw(unsigned k, Raw &&raw)
Central moment of order k from a raw-moment closure: .
bool eventIsProvablyInfeasible(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
True iff the conditioning event is provably infeasible for a bare gate_rv root.
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
double compute_central_moment(const GenericCircuit &gc, gate_t root, unsigned k, std::optional< gate_t > event_root)
Compute the central moment (or if event_root is set).
double simpsonIntegrate(double lo, double hi, int N, F &&f)
Composite-Simpson with N panels.
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
double binomial(unsigned n, unsigned k)
Binomial coefficient as a double (exact for the small orders the moment expansions use).
std::optional< double > collapsedConditionalMoment(const GenericCircuit &gc, gate_t target, gate_t event, unsigned k)
Collapsed exact posterior raw moment E[R^k | Y = C] for a latent target R conditioned (through the eq...
std::unique_ptr< Distribution > closeProductFactors(const std::vector< const Distribution * > &factors)
Fold a product of independent factors into a single distribution when a registered closure covers eve...
double evaluateBooleanProbability(const GenericCircuit &gc, gate_t boolRoot)
Probability that the Boolean subcircuit rooted at boolRoot evaluates to true under the tuple-independ...
std::optional< DistributionSpec > conjugatePosterior(const GenericCircuit &gc, gate_t target, gate_t evidence)
The exact posterior of target given evidence, as a resolved distribution spec, when the circuit match...
std::optional< DistributionSpec > parse_distribution_spec(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution.
std::optional< DistributionTemplate > parse_distribution_template(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution, keeping wired (token) parameters as wire r...
double numericQuantile(const Distribution &d, double p)
Numeric inverse CDF: monotone bisection of cdf() over the family's integration window.
double analytical_mean(const DistributionSpec &d)
Closed-form expectation E[X] for a basic distribution.
constexpr int kSimpsonPanels
Panel count shared by every composite-Simpson quadrature over a distribution's integration range: exa...
WeightedPosterior importanceSampleConditional(const GenericCircuit &gc, gate_t root, gate_t evidence, unsigned samples)
Self-normalised importance sampling of root given evidence.
std::optional< TruncatedSingleRv > matchTruncatedSingleRv(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Detect a closed-form, optionally-truncated single-RV shape.
double compute_expectation(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Compute (or if event_root is set) over the scalar sub-circuit rooted at root.
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
double analytical_raw_moment(const DistributionSpec &d, unsigned k)
Closed-form raw moment for a basic distribution.
bool circuitHasObserve(const GenericCircuit &gc, gate_t root)
Whether the circuit reachable from root contains a gate_observe – the signal that a conditioning even...
void resolveComparators(GenericCircuit &gc, gate_t root, bool simplify, bool decompose)
Run the comparator-resolution pipeline on gc, rewriting every gate_cmp (RV comparison,...
int provsql_verbose
Verbosity level; controlled by the provsql.verbose_level GUC.
Definition provsql.c:115
double provsql_ess_warn_fraction
Effective-sample-size warning threshold for likelihood weighting: warn when the posterior ESS falls b...
Definition provsql.c:127
int provsql_rv_mc_samples
Default sample count for analytical-evaluator MC fallbacks; 0 disables fallback (callers raise instea...
Definition provsql.c:126
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_warning(fmt,...)
Emit a ProvSQL warning message (execution continues).
#define provsql_notice(fmt,...)
Emit a ProvSQL informational notice (execution continues).
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
const char * gate_type_name[]
Names of gate types.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_PERCENTILE
continuous percentile (order-statistic aggregate): wires are interleaved [ind_1, x_1,...
@ PROVSQL_ARITH_DIV
binary, child0 / child1
@ PROVSQL_ARITH_ASFLOAT8
unary, child0 as double precision
@ PROVSQL_ARITH_LN
unary, natural logarithm of child0 (a negative draw raises at evaluation)
@ PROVSQL_ARITH_ROUND
child0 rounded half away from zero, to child1 decimal digits where a second child is given (SQL round...
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ PROVSQL_ARITH_POW
binary, child0 ^ child1 (real branch only: a negative base drawn with a non-integer exponent raises a...
@ PROVSQL_ARITH_ABS
unary, |child0|
@ PROVSQL_ARITH_FLOOR
unary, greatest integer <= child0
@ PROVSQL_ARITH_NEG
unary, -child0
@ PROVSQL_ARITH_INTDIV
binary, child0 / child1 truncated toward zero: SQL's division of two integers
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ PROVSQL_ARITH_CEIL
unary, least integer >= child0
@ PROVSQL_ARITH_EXP
unary, e^child0
@ PROVSQL_ARITH_TIMES
n-ary, product of children
@ PROVSQL_ARITH_MIN
n-ary, min of children (order statistic; least / min aggregate)
@ PROVSQL_ARITH_MAX
n-ary, max of children (order statistic; greatest / max aggregate)
@ PROVSQL_ARITH_ASFLOAT4
unary, child0 as real reads it
@ gate_observe
Latent-variable observation (likelihood-weighting evidence): one wire → an observed bare gate_rv leaf...
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_mobius
Signed Möbius combination: a MEASURE-only gate carrying one integer coefficient per child (in extra,...
@ gate_conditioned
Conditioning marker with two children [target, evidence]: measure-only, probability_evaluate returns ...
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.
Outcome of a conditional Monte Carlo sampling pass.
One parameter slot of a gate_rv, either a literal or a wire.
Parsed distribution spec (family + up to two parameters).
A gate_rv distribution spec that may carry wired (token) parameters – the parse-time counterpart of D...
Outcome of a likelihood-weighting (importance-sampling) pass.