ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Formula.h
Go to the documentation of this file.
1/**
2 * @file semiring/Formula.h
3 * @brief Symbolic representation of provenance as a human-readable formula.
4 *
5 * The @c Formula pseudo-semiring (@c std::string, @f$\oplus@f$, @f$\otimes@f$,
6 * "๐Ÿ˜", "๐Ÿ™") produces a symbolic representation of provenance using
7 * Unicode semiring symbols. It is primarily used for debugging and
8 * testing.
9 *
10 * Each gate evaluates to a string:
11 * - @c zero() โ†’ "๐Ÿ˜"
12 * - @c one() โ†’ "๐Ÿ™"
13 * - @c plus() โ†’ "(a โŠ• b โŠ• โ€ฆ)" or just "a" for singletons
14 * - @c times() โ†’ "(a โŠ— b โŠ— โ€ฆ)" or just "a" for singletons
15 * - @c monus() โ†’ "(a โŠ– b)"
16 * - @c delta() โ†’ "ฮด(a)" or "ฮดa" if @c a starts with @c (
17 * - @c cmp() โ†’ "[s1 op s2]"
18 * - @c semimod()โ†’ "x*s"
19 * - @c agg() โ†’ operator-specific notation (e.g., "min(a,b)")
20 * - @c value() โ†’ the literal string itself
21 * - @c unmapped_input() โ†’ the leaf's abbreviated UUID ("1361b50eโ€ฆ")
22 *
23 * It also renders the measure-carrier gates that carry no algebraic
24 * meaning, and that every proper semiring therefore refuses -- being a
25 * serialisation of the circuit rather than an evaluation of it,
26 * @c Formula has a faithful rendering for each and refuses nothing:
27 * - @c rv() โ†’ "normal(2.5, 0.5)" (wired parameters substituted)
28 * - @c arith() โ†’ ordinary arithmetic notation ("(a + b)", "ln(a)"โ€ฆ),
29 * kept visually distinct from the semiring's
30 * @f$\oplus@f$ / @f$\otimes@f$
31 * - @c mixture() โ†’ "(p ? x : y)"
32 * - @c categorical() โ†’ "categorical(ฮบ; 0.3: a, 0.7: b)"
33 * - @c guarded_case()โ†’ "case(g โ†’ v; else d)"
34 * - @c observe() โ†’ "observe(x = 2.5)"
35 * - @c conditioned() โ†’ "(x | c)"
36 */
37#ifndef FORMULA_H
38#define FORMULA_H
39
40#include <algorithm>
41#include <numeric>
42#include <vector>
43#include <string>
44#include <sstream>
45#include <iomanip>
46#include <iterator>
47#include <map>
48#include <memory>
49
50#include "Semiring.h"
51
52/**
53 * @brief Concatenate the strings of a range with a delimiter.
54 *
55 * Used internally by @c Formula::agg() and the other n-ary renderings.
56 * Built in place, the size reserved first: a formula may be most of the
57 * memory in use, and a stream would hold it twice more.
58 *
59 * @tparam Range Any range of @c std::string.
60 * @param elements The range to join.
61 * @param delimiter String to insert between adjacent elements.
62 * @return All elements concatenated with @p delimiter between them.
63 */
64template <typename Range>
65static std::string join(Range const& elements, const char *const delimiter) {
66 const std::size_t dl = std::char_traits<char>::length(delimiter);
67 std::size_t n = 0, total = 0;
68 for(const auto &x : elements) {
69 total += x.size();
70 ++n;
71 }
72 std::string out;
73 out.reserve(total + (n ? (n - 1) * dl : 0));
74 bool first = true;
75 for(const auto &x : elements) {
76 if(!first)
77 out.append(delimiter, dl);
78 first = false;
79 out += x;
80 }
81 return out;
82}
83
84/**
85 * @brief The part of @p s to write as an operand of @p op: its inner
86 * content if it is wrapped in a single matched outer paren pair
87 * whose top-level operator (depth 1, inside that pair) is @p op,
88 * all of it otherwise.
89 *
90 * Used by @c Formula::plus() and @c Formula::times() to flatten same-op
91 * nested gates by associativity: a child @c "(a โŠ• b)" feeding into a
92 * parent @c plus is unwrapped to @c "a โŠ• b" so the join produces
93 * @c "a โŠ• b โŠ• c" instead of @c "(a โŠ• b) โŠ• c". A different top-level op
94 * (e.g., a @c times child) keeps its parens.
95 *
96 * @return The offset and length of that part in @p s: no copy is made.
97 */
98static std::pair<std::size_t, std::size_t>
99operand_range(const std::string &s, const std::string &op) {
100 const std::pair<std::size_t, std::size_t> whole{0, s.size()};
101 if(s.size() < 2 || s.front() != '(' || s.back() != ')')
102 return whole;
103 // Verify the leading '(' closes only at the very end : if any earlier
104 // ')' brings depth back to 0, the outer pair isn't a single matched
105 // wrap (e.g., @c "(a) โŠ• (b)" must not be stripped).
106 int depth = 0;
107 for(size_t i = 0; i < s.size() - 1; ++i) {
108 if(s[i] == '(') ++depth;
109 else if(s[i] == ')') {
110 if(--depth == 0)
111 return whole;
112 }
113 }
114 // Scan inner for a depth-0 occurrence of @p op. UTF-8 operators are
115 // multi-byte but @c compare on raw bytes is correct since we never
116 // straddle a UTF-8 char boundary at depth-0 positions outside parens.
117 const std::size_t b = 1, e = s.size() - 1;
118 depth = 0;
119 for(size_t i = b; i + op.size() <= e; ) {
120 if(s[i] == '(') { ++depth; ++i; }
121 else if(s[i] == ')') { --depth; ++i; }
122 else if(depth == 0 && s.compare(i, op.size(), op) == 0)
123 return {b, e - b};
124 else
125 ++i;
126 }
127 return whole;
128}
129
130/**
131 * @brief @c "(a op b op โ€ฆ)" over the operands @p v points to, flattened
132 * by @c operand_range, built in place.
133 */
134static std::string join_operands(const std::vector<const std::string *> &v,
135 const std::string &op) {
136 const std::string sep = " " + op + " ";
137 std::vector<std::pair<std::size_t, std::size_t> > r;
138 r.reserve(v.size());
139 std::size_t total = 2;
140 for(const auto *x : v) {
141 r.push_back(operand_range(*x, op));
142 total += r.back().second;
143 }
144 if(!v.empty())
145 total += (v.size() - 1) * sep.size();
146 std::string out;
147 out.reserve(total);
148 out += '(';
149 for(std::size_t k = 0; k < v.size(); ++k) {
150 if(k)
151 out += sep;
152 out.append(*v[k], r[k].first, r[k].second);
153 }
154 out += ')';
155 return out;
156}
157
158/** @brief Pointers to the strings of @p v. */
159static std::vector<const std::string *>
160pointers_to(const std::vector<std::string> &v) {
161 std::vector<const std::string *> r;
162 r.reserve(v.size());
163 for(const auto &x : v)
164 r.push_back(&x);
165 return r;
166}
167
168/**
169 * @brief Render a probability for display in a symbolic formula.
170 *
171 * Enough significant digits that the usual decimal probabilities print
172 * back as themselves (@c 0.3, not @c 0.299999), without the full
173 * round-trip verbosity of @c setprecision(17).
174 */
175static std::string format_number(double v) {
176 std::ostringstream os;
177 os << std::setprecision(15) << v;
178 return os.str();
179}
180
181namespace semiring {
182/**
183 * @brief Symbolic provenance representation over @c std::string.
184 *
185 * Evaluates circuits to human-readable Unicode formulas.
186 * Supports all optional operations (@c cmp, @c semimod, @c agg,
187 * @c value) in addition to the mandatory ones.
188 */
189class Formula : public semiring::Semiring<std::string>
190{
191/** The unknowns named and the equations recorded during one evaluation,
192 * shared by the copies of the semiring that evaluation makes. */
193struct Equations {
194 std::vector<std::string> names; ///< xโ‚, xโ‚‚, ..., in naming order
195 std::vector<std::string> rhs; ///< Right-hand side of each
196 /** Listing order of each: its primes, then its position in its system. */
197 std::vector<std::pair<std::size_t, std::size_t> > order;
198 std::map<std::string, std::size_t> index;
199};
200std::shared_ptr<Equations> equations = std::make_shared<Equations>();
201
202/** @brief @p n in Unicode subscript digits. */
203static std::string subscript(std::size_t n) {
204 static const char *digits[] = {"โ‚€", "โ‚", "โ‚‚", "โ‚ƒ", "โ‚„",
205 "โ‚…", "โ‚†", "โ‚‡", "โ‚ˆ", "โ‚‰"};
206 std::string d = std::to_string(n), r;
207 for(char ch : d)
208 r += digits[ch - '0'];
209 return r;
210}
211
212/** @brief The indices of the unknowns occurring in @p s: a name counts
213 * where no further subscript digit or prime follows it (xโ‚ is neither in
214 * xโ‚โ‚‚ nor in xโ‚โ€ฒ). */
215std::vector<std::size_t> unknowns_in(const std::string &s) const {
216 std::vector<std::size_t> r;
217 for(std::size_t k = 0; k < equations->names.size(); ++k) {
218 const std::string &nm = equations->names[k];
219 for(std::size_t p = s.find(nm); p != std::string::npos;
220 p = s.find(nm, p + 1)) {
221 const std::size_t e = p + nm.size();
222 const bool more = e + 2 < s.size()
223 && (unsigned char) s[e] == 0xE2
224 && (((unsigned char) s[e + 1] == 0x82
225 && ((unsigned char) s[e + 2] & 0xF0) == 0x80)
226 || ((unsigned char) s[e + 1] == 0x80
227 && (unsigned char) s[e + 2] == 0xB2));
228 if(!more) {
229 r.push_back(k);
230 break;
231 }
232 }
233 }
234 return r;
235}
236
237public:
238virtual bool symbolic() const override {
239 return true;
240}
241/**
242 * @brief Name an unknown after its position in its system, @c xแตข: the
243 * name ProvSQL Studio gives the same unknown on the circuit. An
244 * unknown of another system of the same evaluation at the same
245 * position is told apart by primes (@c xโ‚โ€ฒ).
246 */
247virtual value_type symbolic_unknown(std::size_t position) const override {
248 std::string nm = "x" + subscript(position);
249 std::size_t primes = 0;
250 while(equations->index.count(nm)) {
251 nm += "โ€ฒ";
252 ++primes;
253 }
254 equations->index.emplace(nm, equations->names.size());
255 equations->names.push_back(nm);
256 equations->rhs.emplace_back();
257 equations->order.emplace_back(primes, position);
258 return nm;
259}
260virtual void define(const value_type &unknown, const value_type &rhs) const override {
261 equations->rhs[equations->index.at(unknown)] = rhs;
262}
263/** @brief Values are renderings: two of them may denote the same element. */
264virtual bool exact_equality() const override {
265 return false;
266}
267virtual value_type zero() const override {
268 return "๐Ÿ˜";
269}
270virtual value_type one() const override {
271 return "๐Ÿ™";
272}
273virtual value_type plus(const std::vector<value_type> &v) const override {
274 return plus_of(pointers_to(v));
275}
276virtual value_type times(const std::vector<value_type> &v) const override {
277 return times_of(pointers_to(v));
278}
279virtual value_type plus_of(const std::vector<const value_type *> &v) const override {
280 if(v.size()==0)
281 return zero();
282 else if(v.size()==1)
283 return *v[0];
284 // Flatten same-op nesting by associativity: a child "(a โŠ• b)" is
285 // inlined as "a โŠ• b" so the join produces "a โŠ• b โŠ• c", not
286 // "(a โŠ• b) โŠ• c". Mixed-op children (e.g., a times subexpression)
287 // keep their parens.
288 return join_operands(v, "โŠ•");
289}
290virtual value_type times_of(const std::vector<const value_type *> &v) const override {
291 if(v.size()==0)
292 return one();
293 else if(v.size()==1)
294 return *v[0];
295 return join_operands(v, "โŠ—");
296}
297virtual value_type monus(value_type x, value_type y) const override
298{
299 return "("+x+" โŠ– "+y+")";
300}
301virtual value_type delta(value_type x) const override
302{
303 if(x[0]=='(')
304 return "ฮด"+x;
305 else
306 return "ฮด("+x+")";
307}
308virtual value_type cmp(value_type s1, ComparisonOperator op, value_type s2) const override {
309 std::string result = "["+s1+" ";
310 switch(op) {
312 result+="=";
313 break;
315 result+="โ‰ ";
316 break;
318 result+="โ‰ค";
319 break;
321 result+="<";
322 break;
324 result+="โ‰ฅ";
325 break;
327 result+=">";
328 break;
329 }
330 return result+" "+s2+"]";
331}
332virtual value_type semimod(value_type x, value_type s) const override {
333 return x + "*" + s;
334}
335virtual value_type agg(AggregationOperator op, const std::vector<std::string> &s) override {
337 return "<>";
338
339 if(s.empty()) {
340 switch(op) {
343 return "0";
345 return "+โˆž";
347 return "-โˆž";
350 return "<>";
352 return "โŠค";
354 return "โŠฅ";
356 return "[]";
358 assert(false);
359 }
360 }
361
362 std::string result;
363 switch(op) {
365 result+="[";
366 break;
368 result+="min(";
369 break;
371 result+="max(";
372 break;
374 result+="avg(";
375 break;
377 result+="choose(";
378 break;
379 default:
380 ;
381 }
382
383 result += s[0];
384
385 for(size_t i = 1; i<s.size(); ++i) {
386 switch(op) {
389 result+="+";
390 break;
396 result+=",";
397 break;
399 result+="โˆจ";
400 break;
402 result+="โˆง";
403 break;
405 assert(false);
406 }
407 result+=s[i];
408 }
410 result+="]";
411 else if(op==AggregationOperator::MIN ||
415 result+=")";
416 return result;
417}
418virtual value_type value(const std::string &s) const override {
419 return s;
420}
421/**
422 * @brief Render a random-variable leaf from its on-disk encoding.
423 *
424 * @c "normal:2.5,0.5" becomes @c "normal(2.5, 0.5)"; a wired parameter
425 * (written @c "$i", making the leaf a compound / latent one) is replaced
426 * by the rendering of the corresponding wire. Parsing here is
427 * deliberately textual: the rendering must survive any family the
428 * distribution registry gains, including one this build does not know.
429 */
430virtual value_type rv(const std::string &spec,
431 const std::vector<value_type> &params) const override {
432 const auto colon = spec.find(':');
433 if(colon == std::string::npos)
434 return spec;
435
436 std::vector<value_type> args;
437 size_t pos = colon + 1;
438 while(pos <= spec.size()) {
439 const auto comma = spec.find(',', pos);
440 const auto end = (comma == std::string::npos ? spec.size() : comma);
441 std::string arg = spec.substr(pos, end - pos);
442 if(arg.size() > 1 && arg[0] == '$') {
443 try {
444 const size_t slot = std::stoul(arg.substr(1));
445 if(slot < params.size())
446 arg = params[slot];
447 } catch(const std::exception &) {
448 // Malformed wire reference: keep the raw text.
449 }
450 }
451 args.push_back(arg);
452 if(comma == std::string::npos)
453 break;
454 pos = comma + 1;
455 }
456
457 return spec.substr(0, colon) + "(" + join(args, ", ") + ")";
458}
459/**
460 * @brief Render an arithmetic gate in ordinary arithmetic notation.
461 *
462 * Deliberately ASCII (@c +, @c *, @c -, @c /, @c ^) so that arithmetic
463 * over scalar children stays visually distinct from the semiring's
464 * @f$\oplus@f$ / @f$\otimes@f$ / @f$\ominus@f$. An operand count that
465 * does not match the operator's arity falls back to a functional
466 * rendering rather than misrepresenting the circuit.
467 */
469 const std::vector<value_type> &v,
470 const std::string &extra) const override {
471 const auto infix = [&v](const char *sep) {
472 return "(" + join(v, sep) + ")";
473 };
474 const auto functional = [&v](const char *name) {
475 return name + ("(" + join(v, ", ") + ")");
476 };
477
478 switch(op) {
480 if(v.empty()) return "0";
481 return v.size() == 1 ? v[0] : infix(" + ");
483 if(v.empty()) return "1";
484 return v.size() == 1 ? v[0] : infix(" * ");
486 return v.size() == 2 ? infix(" - ") : functional("minus");
488 return v.size() == 2 ? infix(" / ") : functional("div");
490 return functional("intdiv");
492 return v.size() == 1 ? "(-" + v[0] + ")" : functional("neg");
494 return functional("max");
496 return functional("min");
498 return v.size() == 2 ? infix(" ^ ") : functional("pow");
500 return functional("ln");
502 return functional("exp");
504 return functional("round");
506 return functional("floor");
508 return functional("ceil");
510 return functional("abs");
512 return functional("float8");
514 return functional("float4");
516 // Interleaved [indicator, value] wires; the fraction is in extra.
517 if(v.empty() || v.size() % 2 != 0)
518 return functional("percentile");
519 {
520 std::vector<value_type> rows;
521 for(size_t i = 0; i + 1 < v.size(); i += 2)
522 rows.push_back("[" + v[i] + "] " + v[i+1]);
523 return "percentile(" + extra + "; " + join(rows, ", ") + ")";
524 }
525 }
526 return functional("arith");
527}
528/** @brief Render a Bernoulli mixture as a conditional expression. */
530const override {
531 return "(" + p + " ? " + x + " : " + y + ")";
532}
533/**
534 * @brief Render a categorical mixture as its list of weighted outcomes,
535 * prefixed by the key that ties them to a single draw (two
536 * categoricals sharing a key share the draw).
537 */
539 const std::vector<double> &probs,
540 const std::vector<std::string> &outcomes)
541const override {
542 std::vector<value_type> arms;
543 for(size_t i = 0; i < probs.size() && i < outcomes.size(); ++i)
544 arms.push_back(format_number(probs[i]) + ": " + outcomes[i]);
545 return "categorical(" + key + "; " + join(arms, ", ") + ")";
546}
547/** @brief Render a guarded selection, first-match order preserved. */
548virtual value_type guarded_case(const std::vector<value_type> &v)
549const override {
550 if(v.empty() || v.size() % 2 == 0)
551 return "case(" + join(v, ", ") + ")";
552
553 std::vector<value_type> arms;
554 for(size_t i = 0; i + 1 < v.size(); i += 2)
555 arms.push_back(v[i] + " โ†’ " + v[i+1]);
556 arms.push_back("else " + v.back());
557 return "case(" + join(arms, "; ") + ")";
558}
559/** @brief Render a likelihood-weighting observation. */
560virtual value_type observe(value_type child, const std::string &datum)
561const override {
562 return "observe(" + child + " = " + datum + ")";
563}
564/**
565 * @brief Render a conditioning marker as @c "(target | evidence)".
566 *
567 * A three-wire (Boolean-event) conditioned gate also carries the
568 * materialised joint @c times(target, evidence) as its third wire; it
569 * is redundant with the first two and left out of the rendering.
570 */
571virtual value_type conditioned(const std::vector<value_type> &v)
572const override {
573 if(v.size() < 2)
574 return "cond(" + join(v, ", ") + ")";
575 return "(" + v[0] + " | " + v[1] + ")";
576}
577/**
578 * @brief Identify a variable leaf the provenance mapping does not name
579 * by an abbreviated form of its UUID.
580 *
581 * @c Formula serialises the circuit, so the base class's
582 * @f$\mathbb{1}@f$ would be doubly wrong here: it makes every unnamed
583 * leaf look alike, and -- being the multiplicative identity -- it is
584 * dropped by the enclosing @c times(), collapsing a whole join to
585 * @c "๐Ÿ™". An abbreviated UUID keeps the structure and stays
586 * recognisable against what ProvSQL Studio prints on the circuit's
587 * nodes. The first UUID group is kept: 32 bits, enough to tell the
588 * leaves of one circuit apart at a glance, with the full value one
589 * @c get_children / Studio click away.
590 */
591virtual value_type unmapped_input(const std::string &uuid) const override {
592 return uuid.size() > 8 ? uuid.substr(0, 8) + "โ€ฆ" : uuid;
593}
594value_type parse_leaf(const char *v) const {
595 return std::string(v);
596}
597/**
598 * @brief Special case: @c Formula serialises the circuit structure as
599 * a string rather than computing a semantic value, so a
600 * safe-query-rewritten circuit renders to its (rewritten)
601 * structural formula and remains a faithful description. The
602 * homomorphism question does not arise.
603 */
604virtual bool compatibleWithBooleanRewrite() const override {
605 return true;
606}
607/**
608 * @brief Serialise a Formula evaluation as text.
609 *
610 * Drops the cosmetic outer paren pair that @c plus / @c times / @c monus
611 * always produce: at the root there is no enclosing context, so the
612 * outer parens carry no disambiguation value.
613 */
614std::string to_text(value_type s) const {
615 /* In place, as the formula may be most of the memory in use: a copy
616 * would double it. */
618 /* The equations of the unknowns @p s reads, directly or through other
619 * equations, by position in their system. */
620 std::vector<bool> needed(equations->names.size(), false);
621 std::vector<std::size_t> todo = unknowns_in(s);
622 while(!todo.empty()) {
623 const std::size_t k = todo.back();
624 todo.pop_back();
625 if(needed[k])
626 continue;
627 needed[k] = true;
628 for(const auto j : unknowns_in(equations->rhs[k]))
629 todo.push_back(j);
630 }
631 std::vector<std::size_t> listed;
632 for(std::size_t k = 0; k < needed.size(); ++k)
633 if(needed[k])
634 listed.push_back(k);
635 std::sort(listed.begin(), listed.end(),
636 [this](std::size_t a, std::size_t b) {
637 return equations->order[a] < equations->order[b];
638 });
639 std::string eqs;
640 for(const auto k : listed)
641 eqs += (eqs.empty() ? " where " : ", ") + equations->names[k] + " = " +
642 strip_outer(equations->rhs[k]);
643 s += eqs;
644 return s;
645}
646
647private:
648/** @brief Whether the first character of @p s opens a paren pair closed by
649 * its last one, which is then cosmetic. */
650static bool wrapped(const std::string &s) {
651 if(s.size() < 2 || s.front() != '(' || s.back() != ')')
652 return false;
653 int depth = 0;
654 for(size_t i = 0; i < s.size() - 1; ++i) {
655 if(s[i] == '(') ++depth;
656 else if(s[i] == ')') {
657 if(--depth == 0)
658 return false;
659 }
660 }
661 return true;
662}
663/** @brief Drop the cosmetic outer paren pair of @p s, without a copy. */
664static void strip_outer_in_place(std::string &s) {
665 if(wrapped(s)) {
666 s.pop_back();
667 s.erase(0, 1);
668 }
669}
670/** @brief @p s without the cosmetic outer paren pair. */
671static std::string strip_outer(const std::string &s) {
672 return wrapped(s) ? s.substr(1, s.size() - 2) : s;
673}
674public:
675};
676}
677
678#endif /* FORMULA_H */
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
@ OR
Boolean OR aggregate.
Definition Aggregation.h:59
@ MAX
MAX โ†’ input type.
Definition Aggregation.h:56
@ COUNT
COUNT(*) or COUNT(expr) โ†’ integer.
Definition Aggregation.h:53
@ AND
Boolean AND aggregate.
Definition Aggregation.h:58
@ SUM
SUM โ†’ integer or float.
Definition Aggregation.h:54
@ ARRAY_AGG
Array aggregation.
Definition Aggregation.h:61
@ NONE
No aggregation (returns NULL).
Definition Aggregation.h:62
@ MIN
MIN โ†’ input type.
Definition Aggregation.h:55
@ CHOOSE
Arbitrary selection (pick one element).
Definition Aggregation.h:60
@ AVG
AVG โ†’ float.
Definition Aggregation.h:57
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
ArithmeticOperator
Arithmetic operations carried by gate_arith circuit gates.
Definition Aggregation.h:75
@ POW
binary power
Definition Aggregation.h:84
@ MAX
n-ary maximum (order statistic)
Definition Aggregation.h:82
@ DIV
binary quotient
Definition Aggregation.h:79
@ ROUND
rounding, to a number of digits given by a second wire
Definition Aggregation.h:88
@ PERCENTILE
continuous percentile over interleaved [indicator, value] wires
Definition Aggregation.h:87
@ FLOOR
unary floor
Definition Aggregation.h:89
@ CEIL
unary ceiling
Definition Aggregation.h:90
@ NEG
unary negation
Definition Aggregation.h:81
@ INTDIV
binary quotient truncated toward zero (integer division)
Definition Aggregation.h:80
@ ABS
unary absolute value
Definition Aggregation.h:91
@ EXP
unary exponential
Definition Aggregation.h:86
@ TIMES
n-ary product
Definition Aggregation.h:77
@ AS_FLOAT8
unary: the value as double precision reads it
Definition Aggregation.h:92
@ AS_FLOAT4
unary: the value as real reads it
Definition Aggregation.h:93
@ MIN
n-ary minimum (order statistic)
Definition Aggregation.h:83
@ LN
unary natural logarithm
Definition Aggregation.h:85
@ MINUS
binary difference
Definition Aggregation.h:78
static std::pair< std::size_t, std::size_t > operand_range(const std::string &s, const std::string &op)
The part of s to write as an operand of op: its inner content if it is wrapped in a single matched ou...
Definition Formula.h:99
static std::string join(Range const &elements, const char *const delimiter)
Concatenate the strings of a range with a delimiter.
Definition Formula.h:65
static std::vector< const std::string * > pointers_to(const std::vector< std::string > &v)
Pointers to the strings of v.
Definition Formula.h:160
static std::string format_number(double v)
Render a probability for display in a symbolic formula.
Definition Formula.h:175
static std::string join_operands(const std::vector< const std::string * > &v, const std::string &op)
"(a op b op โ€ฆ)" over the operands v points to, flattened by operand_range, built in place.
Definition Formula.h:134
Abstract semiring interface for provenance evaluation.
Symbolic provenance representation over std::string.
Definition Formula.h:190
virtual value_type plus_of(const std::vector< const value_type * > &v) const override
plus over the values v points to, read in place.
Definition Formula.h:279
virtual value_type times_of(const std::vector< const value_type * > &v) const override
times over the values v points to, read in place (see plus_of).
Definition Formula.h:290
virtual value_type zero() const override
Return the additive identity .
Definition Formula.h:267
virtual bool compatibleWithBooleanRewrite() const override
Special case: Formula serialises the circuit structure as a string rather than computing a semantic v...
Definition Formula.h:604
virtual value_type cmp(value_type s1, ComparisonOperator op, value_type s2) const override
Evaluate a comparison gate.
Definition Formula.h:308
std::shared_ptr< Equations > equations
Definition Formula.h:200
static void strip_outer_in_place(std::string &s)
Drop the cosmetic outer paren pair of s, without a copy.
Definition Formula.h:664
std::vector< std::size_t > unknowns_in(const std::string &s) const
The indices of the unknowns occurring in s: a name counts where no further subscript digit or prime f...
Definition Formula.h:215
virtual void define(const value_type &unknown, const value_type &rhs) const override
Record the equation unknown = rhs.
Definition Formula.h:260
virtual value_type semimod(value_type x, value_type s) const override
Apply a semimodule scalar multiplication.
Definition Formula.h:332
virtual value_type agg(AggregationOperator op, const std::vector< std::string > &s) override
Evaluate an aggregation gate.
Definition Formula.h:335
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition Formula.h:276
virtual value_type guarded_case(const std::vector< value_type > &v) const override
Render a guarded selection, first-match order preserved.
Definition Formula.h:548
value_type parse_leaf(const char *v) const
Definition Formula.h:594
static std::string strip_outer(const std::string &s)
s without the cosmetic outer paren pair.
Definition Formula.h:671
virtual value_type arith(ArithmeticOperator op, const std::vector< value_type > &v, const std::string &extra) const override
Render an arithmetic gate in ordinary arithmetic notation.
Definition Formula.h:468
std::string to_text(value_type s) const
Serialise a Formula evaluation as text.
Definition Formula.h:614
virtual value_type symbolic_unknown(std::size_t position) const override
Name an unknown after its position in its system, xแตข: the name ProvSQL Studio gives the same unknown ...
Definition Formula.h:247
virtual value_type unmapped_input(const std::string &uuid) const override
Identify a variable leaf the provenance mapping does not name by an abbreviated form of its UUID.
Definition Formula.h:591
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition Formula.h:297
virtual value_type observe(value_type child, const std::string &datum) const override
Render a likelihood-weighting observation.
Definition Formula.h:560
virtual value_type one() const override
Return the multiplicative identity .
Definition Formula.h:270
virtual value_type delta(value_type x) const override
Apply the operator.
Definition Formula.h:301
static bool wrapped(const std::string &s)
Whether the first character of s opens a paren pair closed by its last one, which is then cosmetic.
Definition Formula.h:650
virtual value_type mixture(value_type p, value_type x, value_type y) const override
Render a Bernoulli mixture as a conditional expression.
Definition Formula.h:529
virtual value_type categorical(value_type key, const std::vector< double > &probs, const std::vector< std::string > &outcomes) const override
Render a categorical mixture as its list of weighted outcomes, prefixed by the key that ties them to ...
Definition Formula.h:538
virtual bool exact_equality() const override
Values are renderings: two of them may denote the same element.
Definition Formula.h:264
virtual value_type value(const std::string &s) const override
Interpret a literal string as a semiring value.
Definition Formula.h:418
virtual value_type conditioned(const std::vector< value_type > &v) const override
Render a conditioning marker as "(target | evidence)".
Definition Formula.h:571
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition Formula.h:273
virtual bool symbolic() const override
Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown,...
Definition Formula.h:238
static std::string subscript(std::size_t n)
n in Unicode subscript digits.
Definition Formula.h:203
virtual value_type rv(const std::string &spec, const std::vector< value_type > &params) const override
Render a random-variable leaf from its on-disk encoding.
Definition Formula.h:430
Abstract base class for (m-)semirings.
Definition Semiring.h:119
The unknowns named and the equations recorded during one evaluation, shared by the copies of the semi...
Definition Formula.h:193
std::vector< std::pair< std::size_t, std::size_t > > order
Listing order of each: its primes, then its position in its system.
Definition Formula.h:197
std::vector< std::string > names
xโ‚, xโ‚‚, ..., in naming order
Definition Formula.h:194
std::map< std::string, std::size_t > index
Definition Formula.h:198
std::vector< std::string > rhs
Right-hand side of each.
Definition Formula.h:195