23#include <unordered_map>
24#include <unordered_set>
36 std::random_device rd;
37 rng.seed((
static_cast<uint64_t
>(rd()) << 32) | rd());
48 std::optional<double> ro)
50 if(!lo || !ro)
return false;
51 const double l = *lo, r = *ro;
73bool matchPointObservationCmp(
const GenericCircuit &gc,
gate_t g,
74 gate_t &leaf_out,
double &datum_out)
78 if(wires.size() != 2)
return false;
86 catch(
const CircuitException &) {
return false; }
90 return try_side(wires[0], wires[1]) || try_side(wires[1], wires[0]);
97 Sampler(
const GenericCircuit &gc, std::mt19937_64 &rng)
98 : gc_(gc), rng_(rng), bool_stamp_(gc.getNbGates(), 0),
99 bool_value_(gc.getNbGates(), 0) {}
102 void resetIteration() {
103 scalar_cache_.clear();
108 if(++iteration_ == 0) {
109 std::fill(bool_stamp_.begin(), bool_stamp_.end(), 0);
110 for(
auto &kv : fix_state_) {
111 std::fill(kv.second.reached.begin(), kv.second.reached.end(), 0);
112 kv.second.solved = 0;
122 std::optional<double> evalScalar(
gate_t g);
123 double evalWeight(
gate_t g);
127 void fixInputs(
const std::unordered_map<gate_t, bool> *world) {
136 std::unique_ptr<Distribution> buildRvDistribution(
137 gate_t leaf,
const DistributionTemplate &tmpl,
double &p1,
double &p2);
139 const GenericCircuit &gc_;
140 std::mt19937_64 &rng_;
144 unsigned iteration_ = 1;
145 std::vector<unsigned> bool_stamp_;
146 std::vector<char> bool_value_;
147 const char *boolMemo(
gate_t g)
const {
148 const auto i =
static_cast<std::size_t
>(g);
149 return i < bool_stamp_.size() && bool_stamp_[i] == iteration_
150 ? &bool_value_[i] :
nullptr;
152 void setBoolMemo(
gate_t g,
bool v) {
153 const auto i =
static_cast<std::size_t
>(g);
154 if(i >= bool_stamp_.size()) {
155 bool_stamp_.resize(i + 1, 0);
156 bool_value_.resize(i + 1, 0);
158 bool_stamp_[i] = iteration_;
161 std::unordered_map<gate_t, std::optional<double>> scalar_cache_;
162 const std::unordered_map<gate_t, bool> *fixed_ =
nullptr;
166 std::unordered_map<gate_t, std::unique_ptr<Distribution>> dist_cache_;
176 std::vector<std::size_t> seeds;
177 std::vector<unsigned> reached;
178 std::vector<std::size_t> queue;
179 std::size_t next = 0;
184 bool fixUnknownHolds(
gate_t sys, std::size_t i);
186 bool conjunctionHolds(
const std::vector<gate_t> &conj);
187 std::unordered_map<gate_t, FixState> fix_state_;
190bool Sampler::conjunctionHolds(
const std::vector<gate_t> &conj)
198bool Sampler::fixUnknownHolds(
gate_t sys, std::size_t target)
200 auto it = fix_state_.find(sys);
201 if(it == fix_state_.end()) {
204 for(std::size_t i = 0; i < st.lin.n; ++i)
205 if(!st.lin.b[i].empty())
206 st.seeds.push_back(i);
207 st.reached.assign(st.lin.n, 0);
208 it = fix_state_.emplace(sys, std::move(st)).first;
210 FixState &st = it->second;
211 const FixSystemLinear &l = st.lin;
213 throw CircuitException(
"gate_fixpoint index out of range");
222 const unsigned now = iteration_;
223 auto &reached = st.reached;
224 auto &queue = st.queue;
225 if(st.solved != now) {
229 for(
const std::size_t i : st.seeds)
230 for(
const auto &conj : l.
b[i])
231 if(conjunctionHolds(conj)) {
237 while(reached[target] != now && st.next < queue.size()) {
238 if((st.next & 4095) == 0)
240 const std::size_t j = queue[st.next++];
241 for(
const auto &[i, conj] : l.
out[j])
242 if(reached[i] != now && conjunctionHolds(conj)) {
247 return reached[target] == now;
250bool Sampler::evalBool(
gate_t g)
252 if(
const char *m = boolMemo(g))
return *m;
256 const auto &wires = gc_.
getWires(g);
262 if(fixed_ !=
nullptr) {
263 result = fixed_->at(g);
266 std::uniform_real_distribution<double> u(0.0, 1.0);
267 result = u(rng_) < gc_.
getProb(g);
273 if(evalBool(c)) { result =
true;
break; }
279 if(!evalBool(c)) { result =
false;
break; }
283 if(wires.size() != 2)
284 throw CircuitException(
"gate_monus must have exactly two children");
285 result = evalBool(wires[0]) && !evalBool(wires[1]);
295 if(wires.size() != 2)
296 throw CircuitException(
"gate_cmp must have exactly two children");
300 throw CircuitException(
301 "gate_cmp: unsupported operator OID " +
302 std::to_string(gc_.
getInfos(g).first));
303 result = applyCmp(evalScalar(wires[0]), op, evalScalar(wires[1]));
307 throw CircuitException(
308 "Monte Carlo over circuits containing gate_mulinput "
309 "is not yet supported on the RV path");
316 if(wires.size() != 1)
317 throw CircuitException(
"gate_delta must have exactly one child");
318 result = evalBool(wires[0]);
325 if(wires.size() != 1)
326 throw CircuitException(
327 "gate_assumed must have exactly one child");
328 result = evalBool(wires[0]);
333 if(wires.size() != 1)
334 throw CircuitException(
"gate_annotation must have exactly one child");
335 result = evalBool(wires[0]);
341 throw CircuitException(
"a projection or equality gate needs a child");
342 result = evalBool(wires[0]);
349 throw CircuitException(
350 "gate_fixpoint must have exactly one child, a gate_fixsystem");
351 const unsigned idx = gc_.
getInfos(g).first;
353 throw CircuitException(
"gate_fixpoint index out of range");
354 result = fixUnknownHolds(wires[0], idx - 1);
358 throw CircuitException(
359 "Unsupported gate type in Boolean evaluation: " +
363 setBoolMemo(g, result);
367std::optional<double> Sampler::evalScalar(
gate_t g)
369 auto it = scalar_cache_.find(g);
370 if(it != scalar_cache_.end())
return it->second;
372 std::optional<double> result = 0.0;
374 const auto &wires = gc_.
getWires(g);
381 result = std::nullopt;
392 auto dit = dist_cache_.find(g);
393 if(dit != dist_cache_.end()) {
394 result = dit->second->sample(rng_);
399 throw CircuitException(
400 "Malformed gate_rv extra: " + gc_.
getExtra(g));
401 if(!tmpl->parametric()) {
402 DistributionSpec spec{tmpl->family, tmpl->p1.literal, tmpl->p2.literal};
404 result = dit->second->sample(rng_);
414 result = buildRvDistribution(g, *tmpl, p1, p2)->sample(rng_);
420 throw CircuitException(
"gate_arith must have at least one child");
425 std::vector<double> v;
427 v.reserve(wires.size());
428 bool undefined =
false;
430 auto x = evalScalar(c);
431 if(!x) { undefined =
true;
break; }
435 result = std::nullopt;
443 for(
double x : v) r += x;
450 for(
double x : v) r *= x;
455 if(wires.size() != 2)
456 throw CircuitException(
"gate_arith MINUS must be binary");
457 result = v[0] - v[1];
462 if(wires.size() != 2)
463 throw CircuitException(
464 std::string(
"gate_arith ")
466 +
" must be binary");
467 const double num = v[0];
468 const double den = v[1];
479 result = std::nullopt;
481 result = std::trunc(num / den);
487 if(wires.size() != 1)
488 throw CircuitException(
"gate_arith NEG must be unary");
498 for(std::size_t i = 1; i < v.size(); ++i)
506 for(std::size_t i = 1; i < v.size(); ++i)
513 if(wires.size() != 2)
514 throw CircuitException(
"gate_arith POW must be binary");
515 const double base = v[0];
516 const double expo = v[1];
517 result = std::pow(base, expo);
525 if(std::isnan(*result) && !std::isnan(base) && !std::isnan(expo))
526 throw CircuitException(
527 "pow: negative base drawn with a non-integer exponent ("
528 + std::to_string(base) +
" ^ " + std::to_string(expo)
529 +
"); restrict the base to be non-negative, e.g. "
530 "pow(greatest(x, 0), p)");
535 if(wires.size() != 1)
536 throw CircuitException(
"gate_arith LN must be unary");
537 const double x = v[0];
543 throw CircuitException(
544 "ln: negative draw (" + std::to_string(x)
545 +
"); ln is only defined on [0, +Infinity) -- "
546 "restrict the argument's support");
547 result = std::log(x);
551 if(wires.size() != 1)
552 throw CircuitException(
"gate_arith EXP must be unary");
553 result = std::exp(v[0]);
562 if(wires.empty() || wires.size() > 2)
563 throw CircuitException(
"gate_arith ROUND takes one or two wires");
564 const double x = v[0];
565 if(wires.size() == 1) {
566 result = std::round(x);
568 const double d = v[1];
569 if(std::isnan(x) || std::isnan(d)) { result = x + d;
break; }
570 const double f = std::pow(10.0, d);
571 result = std::round(x * f) / f;
576 if(wires.size() != 1)
577 throw CircuitException(
"gate_arith FLOOR must be unary");
578 result = std::floor(v[0]);
581 if(wires.size() != 1)
582 throw CircuitException(
"gate_arith CEIL must be unary");
583 result = std::ceil(v[0]);
586 if(wires.size() != 1)
587 throw CircuitException(
"gate_arith ABS must be unary");
588 result = std::fabs(v[0]);
591 if(wires.size() != 1)
592 throw CircuitException(
"gate_arith ASFLOAT8 must be unary");
596 if(wires.size() != 1)
597 throw CircuitException(
"gate_arith ASFLOAT4 must be unary");
598 result =
static_cast<double>(
static_cast<float>(v[0]));
610 if(wires.size() < 2 || wires.size() % 2 != 0)
611 throw CircuitException(
612 "gate_arith PERCENTILE must have interleaved "
613 "indicator/value wires");
616 fraction = std::stod(gc_.
getExtra(g));
617 }
catch(
const std::exception &) {
618 throw CircuitException(
619 "Malformed gate_arith PERCENTILE extra (expected the "
622 std::vector<double> members;
623 for(std::size_t i = 0; i < wires.size(); i += 2) {
624 const auto present = evalScalar(wires[i]);
625 if(present && *present >= 0.5) {
626 const auto x = evalScalar(wires[i + 1]);
628 members.push_back(*x);
631 if(members.empty()) {
632 result = std::nullopt;
636 const double pos = fraction * (members.size() - 1);
637 const std::size_t lo =
static_cast<std::size_t
>(pos);
638 const double frac = pos -
static_cast<double>(lo);
639 result = (lo + 1 < members.size())
640 ? members[lo] + frac * (members[lo + 1] - members[lo])
645 throw CircuitException(
646 "Unknown gate_arith operator tag: " +
647 std::to_string(
static_cast<unsigned>(op)));
672 std::unique_ptr<Aggregator> agg =
677 throw CircuitException(
678 "gate_agg: makeAggregator returned null for op " +
679 std::to_string(
static_cast<int>(op)));
680 for(
gate_t child : wires) {
682 const auto &sm = gc_.
getWires(child);
683 if(sm.size() != 2)
continue;
684 if(!evalBool(sm[0]))
continue;
686 const auto x = evalScalar(sm[1]);
689 agg->add(AggValue(
static_cast<long>(*x)));
691 agg->add(AggValue(*x));
694 AggValue r = agg->finalize();
697 result =
static_cast<double>(std::get<long>(r.
v));
700 result = std::get<double>(r.
v);
728 result = std::nullopt;
731 throw CircuitException(
732 "gate_agg: unsupported aggregate result ValueType in MC");
746 const auto &wires = gc_.
getWires(g);
747 if(wires.size() != 2)
748 throw CircuitException(
749 "gate_semimod must have exactly two children "
750 "[k_gate, value_gate]");
751 result = evalBool(wires[0]) ? evalScalar(wires[1])
752 : std::optional<double>(0.0);
776 std::uniform_real_distribution<double> u(0.0, 1.0);
777 const double r = u(rng_);
781 std::size_t chosen = wires.size() - 1;
782 for(std::size_t i = 1; i < wires.size(); ++i) {
784 if(r < cum) { chosen = i;
break; }
786 for(std::size_t i = 1; i < wires.size(); ++i) {
787 setBoolMemo(wires[i], i == chosen);
792 if(wires.size() != 3)
793 throw CircuitException(
794 "gate_mixture must have exactly three children "
795 "[p_token, x_token, y_token]");
796 result = evalBool(wires[0]) ? evalScalar(wires[1])
797 : evalScalar(wires[2]);
808 const auto &wires = gc_.
getWires(g);
810 throw CircuitException(
811 "gate_case must have at least one child (the default)");
812 const std::size_t k = wires.size() / 2;
813 bool matched =
false;
814 for(std::size_t i = 0; i < k; ++i) {
815 if(evalBool(wires[2 * i])) {
816 result = evalScalar(wires[2 * i + 1]);
822 result = evalScalar(wires.back());
826 throw CircuitException(
827 "Unsupported gate type in scalar evaluation: " +
831 scalar_cache_[g] = result;
835std::unique_ptr<Distribution> Sampler::buildRvDistribution(
836 gate_t leaf,
const DistributionTemplate &tmpl,
double &p1,
double &p2)
839 auto resolve = [&](
const DistributionParam &p) {
840 if(p.wire_slot < 0)
return p.literal;
841 const auto x = evalScalar(w[p.wire_slot]);
843 throw CircuitException(
844 "gate_rv " + std::string(tmpl.family->name)
845 +
": a parameter has no value in a drawn world (a NULL, or "
846 "an aggregate over no row)");
849 p1 = resolve(tmpl.p1);
850 p2 = resolve(tmpl.p2);
851 auto dist = tmpl.family->factory(p1, p2);
860 if(!dist->integrationRange(dlo, dhi))
861 throw CircuitException(
862 "gate_rv " + std::string(tmpl.family->name)
863 +
": a parameter drawn outside the family's domain "
864 "(e.g. a scale/rate/shape <= 0: got "
865 + std::to_string(p1) +
", " + std::to_string(p2)
866 +
"); put a positive-support prior on it, e.g. "
867 "gamma / lognormal");
871double Sampler::evalWeight(
gate_t g)
874 const auto &wires = gc_.
getWires(g);
883 if(w == 0.0)
return 0.0;
892 if(wires.size() != 1)
893 throw CircuitException(
894 "gate_observe must have exactly one child (the observed leaf)");
895 const gate_t leaf = wires[0];
897 throw CircuitException(
898 "gate_observe child must be a gate_rv leaf");
902 throw CircuitException(
903 "gate_observe: malformed observed gate_rv extra: "
906 return buildRvDistribution(leaf, *tmpl, p1, p2)->pdf(d);
916 if(matchPointObservationCmp(gc_, g, leaf, datum)) {
920 return buildRvDistribution(leaf, *tmpl, p1, p2)->pdf(datum);
923 return evalBool(g) ? 1.0 : 0.0;
930 return evalBool(g) ? 1.0 : 0.0;
938 std::mt19937_64 rng =
seedRng();
939 Sampler sampler(gc, rng);
941 unsigned success = 0;
942 for(
unsigned i = 0; i < samples; ++i) {
943 sampler.resetIteration();
944 if(sampler.evalBool(root))
949 "Interrupted after " + std::to_string(i + 1) +
" samples");
951 return success * 1.0 / samples;
955 double eps,
double delta,
956 unsigned long max_samples,
957 unsigned long &samples_used,
958 bool &reached_target)
961 reached_target =
false;
969 const double e = std::exp(1.0);
970 const double Y = 4.0 * (e - 2.0) * std::log(2.0 / delta) / (eps * eps);
971 const double Y1 = 1.0 + (1.0 + eps) * Y;
973 std::mt19937_64 rng =
seedRng();
974 Sampler sampler(gc, rng);
976 unsigned long success = 0;
977 for(
unsigned long s = 0; s < max_samples; ++s) {
978 sampler.resetIteration();
979 if(sampler.evalBool(root)) {
981 if(
static_cast<double>(success) >= Y1) {
982 samples_used = s + 1;
983 reached_target =
true;
984 return Y1 /
static_cast<double>(samples_used);
989 "Interrupted after " + std::to_string(s + 1) +
" samples");
994 samples_used = max_samples;
995 return static_cast<double>(success) /
static_cast<double>(max_samples);
1000 const std::vector<gate_t> &cmps,
1003 const unsigned k = cmps.size();
1006 "monteCarloJointDistribution: empty cmps list");
1009 "monteCarloJointDistribution: too many cmps in island ("
1010 + std::to_string(k) +
" > 30)");
1012 std::mt19937_64 rng =
seedRng();
1013 Sampler sampler(gc, rng);
1015 const std::size_t nb_outcomes = std::size_t{1} << k;
1016 std::vector<unsigned> counts(nb_outcomes, 0);
1018 for (
unsigned i = 0; i < samples; ++i) {
1019 sampler.resetIteration();
1021 for (
unsigned j = 0; j < k; ++j) {
1022 if (sampler.evalBool(cmps[j])) w |= (std::size_t{1} << j);
1027 "Interrupted after " + std::to_string(i + 1) +
" samples");
1030 std::vector<double> probs(nb_outcomes);
1031 for (std::size_t w = 0; w < nb_outcomes; ++w)
1032 probs[w] = counts[w] * 1.0 / samples;
1039 std::mt19937_64 rng =
seedRng();
1040 Sampler sampler(gc, rng);
1042 std::vector<std::optional<double>> out;
1043 out.reserve(samples);
1044 for(
unsigned i = 0; i < samples; ++i) {
1045 sampler.resetIteration();
1046 out.push_back(sampler.evalScalar(root));
1050 "Interrupted after " + std::to_string(i + 1) +
" samples");
1058 std::vector<double> out;
1059 out.reserve(samples.size());
1060 for(
const auto &x : samples)
1061 if(x) out.push_back(*x);
1068static std::optional<std::vector<gate_t>>
1070 std::optional<gate_t> event,
unsigned max_inputs)
1072 std::vector<gate_t> inputs;
1073 std::unordered_set<gate_t> seen;
1074 std::stack<gate_t> todo;
1076 if(event) todo.push(*event);
1077 while(!todo.empty()) {
1080 if(!seen.insert(g).second)
continue;
1084 if(std::isnan(gc.
getProb(g)))
return std::nullopt;
1085 inputs.push_back(g);
1091 return std::nullopt;
1095 if(inputs.size() > max_inputs)
return std::nullopt;
1101std::optional<double>
1103 unsigned max_inputs)
1106 if(!inputs_opt)
return std::nullopt;
1107 const std::vector<gate_t> &inputs = *inputs_opt;
1109 std::mt19937_64 rng;
1110 Sampler sampler(gc, rng);
1111 std::unordered_map<gate_t, bool> world;
1112 sampler.fixInputs(&world);
1114 const std::uint64_t n_worlds = std::uint64_t(1) << inputs.size();
1115 for(std::uint64_t w = 0; w < n_worlds; ++w) {
1117 for(std::size_t i = 0; i < inputs.size(); ++i) {
1118 const bool present = (w >> i) & 1;
1119 const double pi = gc.
getProb(inputs[i]);
1120 world[inputs[i]] = present;
1121 p *= present ? pi : 1.0 - pi;
1123 if(p == 0.0)
continue;
1124 sampler.resetIteration();
1125 if(sampler.evalBool(root))
1135std::optional<std::vector<std::pair<double, std::optional<double>>>>
1137 std::optional<gate_t> event,
unsigned max_inputs)
1140 if(!inputs_opt)
return std::nullopt;
1141 const std::vector<gate_t> &inputs = *inputs_opt;
1143 std::mt19937_64 rng;
1144 Sampler sampler(gc, rng);
1145 std::unordered_map<gate_t, bool> world;
1146 sampler.fixInputs(&world);
1147 std::vector<std::pair<double, std::optional<double>>> out;
1148 const std::uint64_t n_worlds = std::uint64_t(1) << inputs.size();
1149 for(std::uint64_t w = 0; w < n_worlds; ++w) {
1151 for(std::size_t i = 0; i < inputs.size(); ++i) {
1152 const bool present = (w >> i) & 1;
1153 const double pi = gc.
getProb(inputs[i]);
1154 world[inputs[i]] = present;
1155 p *= present ? pi : 1.0 - pi;
1157 if(p == 0.0)
continue;
1158 sampler.resetIteration();
1159 if(event && !sampler.evalBool(*event))
continue;
1160 out.emplace_back(p, sampler.evalScalar(root));
1169std::pair<std::vector<std::optional<double>>,
1170 std::vector<std::optional<double>>>
1172 gate_t root_b,
unsigned samples)
1174 std::mt19937_64 rng =
seedRng();
1175 Sampler sampler(gc, rng);
1177 std::vector<std::optional<double>> out_a, out_b;
1178 out_a.reserve(samples);
1179 out_b.reserve(samples);
1180 for(
unsigned i = 0; i < samples; ++i) {
1181 sampler.resetIteration();
1187 out_a.push_back(sampler.evalScalar(root_a));
1188 out_b.push_back(sampler.evalScalar(root_b));
1192 "Interrupted after " + std::to_string(i + 1) +
" samples");
1194 return {std::move(out_a), std::move(out_b)};
1200 std::mt19937_64 rng =
seedRng();
1201 Sampler sampler(gc, rng);
1207 for(
unsigned i = 0; i < samples; ++i) {
1208 sampler.resetIteration();
1215 if(sampler.evalBool(event_root)) {
1216 out.
accepted.push_back(sampler.evalScalar(root));
1222 "Interrupted after " + std::to_string(i + 1) +
" samples");
1229 gate_t event_root,
unsigned samples)
1231 std::mt19937_64 rng =
seedRng();
1232 Sampler sampler(gc, rng);
1236 out.
xs.reserve(samples);
1237 out.
ys.reserve(samples);
1239 for(
unsigned i = 0; i < samples; ++i) {
1240 sampler.resetIteration();
1244 if(sampler.evalBool(event_root)) {
1245 out.
xs.push_back(sampler.evalScalar(root_a));
1246 out.
ys.push_back(sampler.evalScalar(root_b));
1252 "Interrupted after " + std::to_string(i + 1) +
" samples");
1257std::optional<std::vector<double>>
1259 gate_t event_root,
unsigned n)
1262 if (!m)
return std::nullopt;
1268 std::mt19937_64 rng =
seedRng();
1275 std::mt19937_64 rng =
seedRng();
1276 Sampler sampler(gc, rng);
1281 for(
unsigned i = 0; i < samples; ++i) {
1282 sampler.resetIteration();
1286 const double w = sampler.evalWeight(evidence);
1291 const auto x = sampler.evalScalar(root);
1303 "Interrupted after " + std::to_string(i + 1) +
" samples");
1311 if(samples == 0)
return 0.0;
1312 std::mt19937_64 rng =
seedRng();
1313 Sampler sampler(gc, rng);
1316 for(
unsigned i = 0; i < samples; ++i) {
1317 sampler.resetIteration();
1318 sw += sampler.evalWeight(evidence);
1321 "Interrupted after " + std::to_string(i + 1) +
" samples");
1323 return sw /
static_cast<double>(samples);
1329 std::vector<double> out;
1332 std::vector<double> cum;
1335 for(
const auto &pw : post.
particles) { c += pw.second; cum.push_back(c); }
1337 std::mt19937_64 rng =
seedRng();
1338 std::uniform_real_distribution<double> u(0.0, c);
1340 for(
unsigned i = 0; i < n; ++i) {
1341 const double r = u(rng);
1342 auto it = std::lower_bound(cum.begin(), cum.end(), r);
1343 std::size_t idx =
static_cast<std::size_t
>(it - cum.begin());
1345 out.push_back(post.
particles[idx].first);
1352 std::unordered_set<gate_t> seen;
1353 std::stack<gate_t> stack;
1355 while(!stack.empty()) {
1358 if(!seen.insert(g).second)
continue;
1366 || matchPointObservationCmp(gc, g, leaf, datum))
1377 bool fixpoint =
false;
1378 std::unordered_set<gate_t> seen;
1379 std::stack<gate_t> stack;
1381 while(!stack.empty()) {
1384 if(!seen.insert(g).second)
continue;
1397 std::unordered_set<gate_t> seen;
1398 std::stack<gate_t> stack;
1400 while(!stack.empty()) {
1403 if(!seen.insert(g).second)
continue;
1434 std::unordered_set<gate_t> seen;
1435 std::stack<gate_t> stack;
1438 while(!stack.empty()) {
1441 if(!seen.insert(g).second)
continue;
1470 std::unordered_set<gate_t> seen;
1471 std::stack<gate_t> stack;
1473 while(!stack.empty()) {
1476 if(!seen.insert(g).second)
continue;
ComparisonOperator cmpOpFromOid(Oid op_oid, bool &ok)
Map a PostgreSQL comparison-operator OID to a ComparisonOperator.
AggregationOperator getAggregationOperator(Oid oid)
Map a PostgreSQL aggregate function OID to an AggregationOperator.
std::unique_ptr< Aggregator > makeAggregator(AggregationOperator op, ValueType t)
Create a concrete Aggregator for the given operator and value type.
Typed aggregation value, operator, and aggregator abstractions.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
@ COUNT
COUNT(*) or COUNT(expr) → integer.
@ SUM
SUM → integer or float.
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
@ LE
Less than or equal (<=).
@ GE
Greater than or equal (>=).
bool sql_less(T a, T b)
The order PostgreSQL gives numbers: for floats, NaN equals NaN and is greater than every other value ...
bool sql_less< double >(double a, double b)
sql_less for double, with PostgreSQL's place for NaN.
@ INT
Signed 64-bit integer.
@ FLOAT
Double-precision float.
gate_t
Strongly-typed gate identifier.
Out-of-line template method implementations for Circuit<gateType>.
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Monte Carlo sampling over a GenericCircuit, RV-aware.
Continuous random-variable helpers (distribution parsing, moments).
Support-based bound check for continuous-RV comparators.
Exception type thrown by circuit operations on invalid input.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
FixSystemLinear linearizeFixSystem(gate_t sys) const
The equations of the gate_fixsystem sys, as linear forms over the gates that do not depend on its unk...
std::string getExtra(gate_t g) const
Return the string extra for gate g.
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.
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 ...
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.
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.
std::optional< double > enumerateBooleanProbability(const GenericCircuit &gc, gate_t root, unsigned max_inputs)
The probability of root, exactly, over the possible worlds of the circuit as it is: the alternative t...
std::pair< std::vector< std::optional< double > >, std::vector< std::optional< double > > > monteCarloScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, unsigned samples)
Coupled per-iteration draws of two scalar roots.
std::vector< double > posteriorResample(const WeightedPosterior &post, unsigned n)
Sampling-importance-resampling: draw n posterior samples from a weighted particle set (proportional t...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::vector< double > monteCarloJointDistribution(const GenericCircuit &gc, const std::vector< gate_t > &cmps, unsigned samples)
Estimate the joint distribution of cmps via Monte Carlo.
bool circuitHasNestedAggValue(const GenericCircuit &gc, gate_t root)
Whether a contribution of an aggregate is itself an aggregate result (a gate_semimod whose M side is ...
double monteCarloRVStopping(const GenericCircuit &gc, gate_t root, double eps, double delta, unsigned long max_samples, unsigned long &samples_used, bool &reached_target)
Whole-circuit (eps,delta)-relative probability via the Dagum-Karp-Luby-Ross stopping rule.
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
std::mt19937_64 seedRng()
The shared Monte Carlo generator, seeded from the provsql.monte_carlo_seed GUC (-1 = non-deterministi...
bool circuitHasUnresolvedSampleableAgg(const GenericCircuit &gc, gate_t root)
Whether a surviving gate_agg exists and every one is sample-faithful (SUM / AVG / MIN / MAX / COUNT –...
static std::optional< std::vector< gate_t > > enumerableInputs(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event, unsigned max_inputs)
The Boolean inputs the worlds of root (and event) range over, or nullopt when another random source,...
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
bool circuitHasFixpoint(const GenericCircuit &gc, gate_t root)
Whether a gate_fixpoint (a row of a recursion on cyclic data) is reachable from root.
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...
ConditionalScalarPairSamples monteCarloConditionalScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, gate_t event_root, unsigned samples)
Rejection-sample the PAIR (root_a, root_b) conditioned on event_root.
double monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples)
Run Monte Carlo on a circuit that may contain gate_rv leaves.
std::optional< std::vector< double > > try_truncated_closed_form_sample(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned n)
Try to draw n exact samples from the conditional distribution of root given event_root via closed-for...
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.
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
bool circuitHasRV(const GenericCircuit &gc, gate_t root)
Walk the circuit reachable from root looking for any gate_rv.
bool circuitHasObserve(const GenericCircuit &gc, gate_t root)
Whether the circuit reachable from root contains a gate_observe – the signal that a conditioning even...
int provsql_monte_carlo_seed
Seed for the Monte Carlo sampler; -1 means non-deterministic (std::random_device); controlled by the ...
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
const char * gate_type_name[]
Names of gate types.
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_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixsystem
Linear equation system x_i = f_i(x) of a recursive query, one equation per derived tuple: wires [x_1,...
@ 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...
#define PROVSQL_GATE_NULL_UUID
UUID of the constant value gate standing for the NULL value, the result of gate_null().
#define PROVSQL_AGG_SCALAR_FLAG
Scalar-aggregation flag, stored in the upper bit of a gate_agg's info2 (whose low 31 bits hold the ag...
ValueType getType() const
Return the runtime type tag of this value.
std::variant< long, double, bool, std::string, std::vector< long >, std::vector< double >, std::vector< bool >, std::vector< std::string > > v
The variant holding the actual value.
std::vector< std::vector< std::vector< gate_t > > > b
Constant part of each equation.
std::size_t n
Number of unknowns.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > out
Terms, by unknown read.
Outcome of a conditional coupled-pair Monte Carlo pass: xs[i] / ys[i] are the two roots' values from ...
std::vector< std::optional< double > > xs
std::vector< std::optional< double > > ys
Outcome of a conditional Monte Carlo sampling pass.
std::vector< std::optional< double > > accepted
Outcome of a likelihood-weighting (importance-sampling) pass.
double weight_sq_sum
Sum of w^2 over all attempted draws.
unsigned attempted
Number of prior draws.
std::vector< std::pair< double, double > > particles
(x, w) with w > 0.
double weight_sum
Sum of w over all attempted draws.