ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
semiring::Formula Class Reference

Symbolic provenance representation over std::string. More...

#include "Formula.h"

Inheritance diagram for semiring::Formula:
Collaboration diagram for semiring::Formula:

Classes

struct  Equations
 The unknowns named and the equations recorded during one evaluation, shared by the copies of the semiring that evaluation makes. More...

Public Member Functions

virtual bool symbolic () const override
 Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown, define).
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 on the circuit.
virtual void define (const value_type &unknown, const value_type &rhs) const override
 Record the equation unknown = rhs.
virtual bool exact_equality () const override
 Values are renderings: two of them may denote the same element.
virtual value_type zero () const override
 Return the additive identity \(\mathbb{0}\).
virtual value_type one () const override
 Return the multiplicative identity \(\mathbb{1}\).
virtual value_type plus (const std::vector< value_type > &v) const override
 Apply the additive operation to a list of values.
virtual value_type times (const std::vector< value_type > &v) const override
 Apply the multiplicative operation to a list of values.
virtual value_type plus_of (const std::vector< const value_type * > &v) const override
 plus over the values v points to, read in place.
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).
virtual value_type monus (value_type x, value_type y) const override
 Apply the monus (m-semiring difference) operation.
virtual value_type delta (value_type x) const override
 Apply the \(\delta\) operator.
virtual value_type cmp (value_type s1, ComparisonOperator op, value_type s2) const override
 Evaluate a comparison gate.
virtual value_type semimod (value_type x, value_type s) const override
 Apply a semimodule scalar multiplication.
virtual value_type agg (AggregationOperator op, const std::vector< std::string > &s) override
 Evaluate an aggregation gate.
virtual value_type value (const std::string &s) const override
 Interpret a literal string as a semiring value.
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.
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.
virtual value_type mixture (value_type p, value_type x, value_type y) const override
 Render a Bernoulli mixture as a conditional expression.
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 a single draw (two categoricals sharing a key share the draw).
virtual value_type guarded_case (const std::vector< value_type > &v) const override
 Render a guarded selection, first-match order preserved.
virtual value_type observe (value_type child, const std::string &datum) const override
 Render a likelihood-weighting observation.
virtual value_type conditioned (const std::vector< value_type > &v) const override
 Render a conditioning marker as "(target | evidence)".
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.
value_type parse_leaf (const char *v) const
virtual bool compatibleWithBooleanRewrite () const override
 Special case: Formula serialises the circuit structure as a string rather than computing a semantic value, so a safe-query-rewritten circuit renders to its (rewritten) structural formula and remains a faithful description.
std::string to_text (value_type s) const
 Serialise a Formula evaluation as text.
Public Member Functions inherited from semiring::Semiring< std::string >
virtual ~Semiring ()=default
virtual bool absorptive () const
 Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).
virtual bool idempotent () const
 Return true if this semiring is idempotent ( \(a \oplus a = a\) for all \(a\)).
virtual bool selective () const
 Return true if \(\oplus\) is selective (for all \(a, b\), \(a \oplus b \in \{a, b\}\)).
virtual bool commutative () const
 Return true if \(\otimes\) is commutative ( \(a \otimes b = b \otimes a\) for all \(a, b\)).
virtual bool has_star () const
 Return true if star computes \(a^* = \mathbb{1} \oplus a \oplus a^2 \oplus \cdots\).
virtual value_type star (const value_type &a) const
 \(a^*\), the sum of the powers of a.
virtual bool equal (const value_type &a, const value_type &b) const
 Equality of the semiring elements two values denote.
virtual bool exclusive () const
 Return true if the semiring is exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\).
virtual bool mul_idempotent () const
 Return true if \(\otimes\) is idempotent: \(a \otimes a = a\).
bool product_is_joint () const
 Whether the product of the predicate provenances of two conditions over one family of occurrences is the provenance of their conjunction (and their sum that of their disjunction).
virtual bool mul_sub_left_distributive () const
 Return true if \(\otimes\) distributes over the monus on the left: \(a \otimes (b \ominus c) = (a \otimes b) \ominus (a \otimes c)\) for all \(a, b, c\).
virtual bool certifying () const
 Whether this semiring builds certified exclusive enumerations (see the three hooks below).
virtual bool independent_literal (const value_type &) const
 Whether v is an independent literal for certification purposes: a base Bernoulli variable (or a constant), so that distinct literals have disjoint supports and an AND over them is decomposable.
virtual value_type certified_world_term (const std::vector< value_type > &, const std::vector< value_type > &) const
 Build one complete world term: the conjunction of the present literals and the negations of the missing literals, certified decomposable.
virtual value_type certified_exclusive_plus (const std::vector< value_type > &) const
 Build the disjunction of pairwise-exclusive disjuncts, certified deterministic.

Private Member Functions

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 follows it (x₁ is neither in x₁₂ nor in x₁′).

Static Private Member Functions

static std::string subscript (std::size_t n)
 n in Unicode subscript digits.
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.
static void strip_outer_in_place (std::string &s)
 Drop the cosmetic outer paren pair of s, without a copy.
static std::string strip_outer (const std::string &s)
 s without the cosmetic outer paren pair.

Private Attributes

std::shared_ptr< Equations > equations = std::make_shared<Equations>()

Additional Inherited Members

Public Types inherited from semiring::Semiring< std::string >
typedef std::string value_type
 The carrier type of this semiring.

Detailed Description

Symbolic provenance representation over std::string.

Evaluates circuits to human-readable Unicode formulas. Supports all optional operations (cmp, semimod, agg, value) in addition to the mandatory ones.

Definition at line 189 of file Formula.h.

Member Function Documentation

◆ agg()

virtual value_type semiring::Formula::agg ( AggregationOperator op,
const std::vector< std::string > & s )
inlineoverridevirtual

Evaluate an aggregation gate.

Parameters
opThe aggregation function (COUNT, SUM, MIN…).
sList of child semiring values to aggregate.
Returns
The aggregated value.
Exceptions
SemiringExceptionif not overridden.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 335 of file Formula.h.

◆ arith()

virtual value_type semiring::Formula::arith ( ArithmeticOperator op,
const std::vector< value_type > & v,
const std::string & extra ) const
inlineoverridevirtual

Render an arithmetic gate in ordinary arithmetic notation.

Deliberately ASCII (+, *, -, /, ^) so that arithmetic over scalar children stays visually distinct from the semiring's \(\oplus\) / \(\otimes\) / \(\ominus\). An operand count that does not match the operator's arity falls back to a functional rendering rather than misrepresenting the circuit.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 468 of file Formula.h.

Here is the call graph for this function:

◆ categorical()

virtual value_type semiring::Formula::categorical ( value_type key,
const std::vector< double > & probs,
const std::vector< std::string > & outcomes ) const
inlineoverridevirtual

Render a categorical mixture as its list of weighted outcomes, prefixed by the key that ties them to a single draw (two categoricals sharing a key share the draw).

Reimplemented from semiring::Semiring< std::string >.

Definition at line 538 of file Formula.h.

Here is the call graph for this function:

◆ cmp()

virtual value_type semiring::Formula::cmp ( value_type s1,
ComparisonOperator op,
value_type s2 ) const
inlineoverridevirtual

Evaluate a comparison gate.

Parameters
s1Left operand.
opComparison operator.
s2Right operand.
Returns
Result of the comparison in this semiring.
Exceptions
SemiringExceptionif not overridden.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 308 of file Formula.h.

◆ compatibleWithBooleanRewrite()

virtual bool semiring::Formula::compatibleWithBooleanRewrite ( ) const
inlineoverridevirtual

Special case: Formula serialises the circuit structure as a string rather than computing a semantic value, so a safe-query-rewritten circuit renders to its (rewritten) structural formula and remains a faithful description.

The homomorphism question does not arise.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 604 of file Formula.h.

◆ conditioned()

virtual value_type semiring::Formula::conditioned ( const std::vector< value_type > & v) const
inlineoverridevirtual

Render a conditioning marker as "(target | evidence)".

A three-wire (Boolean-event) conditioned gate also carries the materialised joint times(target, evidence) as its third wire; it is redundant with the first two and left out of the rendering.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 571 of file Formula.h.

Here is the call graph for this function:

◆ define()

virtual void semiring::Formula::define ( const value_type & unknown,
const value_type & rhs ) const
inlineoverridevirtual

Record the equation unknown = rhs.

Parameters
unknownA value returned by symbolic_unknown.
rhsIts right-hand side, over unknowns of the same kind.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 260 of file Formula.h.

◆ delta()

virtual value_type semiring::Formula::delta ( value_type x) const
inlineoverridevirtual

Apply the \(\delta\) operator.

Parameters
xInput value.
Returns
\(\delta(x)\).

Implements semiring::Semiring< std::string >.

Definition at line 301 of file Formula.h.

◆ exact_equality()

virtual bool semiring::Formula::exact_equality ( ) const
inlineoverridevirtual

Values are renderings: two of them may denote the same element.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 264 of file Formula.h.

◆ guarded_case()

virtual value_type semiring::Formula::guarded_case ( const std::vector< value_type > & v) const
inlineoverridevirtual

Render a guarded selection, first-match order preserved.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 548 of file Formula.h.

Here is the call graph for this function:

◆ mixture()

virtual value_type semiring::Formula::mixture ( value_type p,
value_type x,
value_type y ) const
inlineoverridevirtual

Render a Bernoulli mixture as a conditional expression.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 529 of file Formula.h.

◆ monus()

virtual value_type semiring::Formula::monus ( value_type x,
value_type y ) const
inlineoverridevirtual

Apply the monus (m-semiring difference) operation.

Parameters
xMinuend.
ySubtrahend.
Returns
\(x \ominus y\).

Implements semiring::Semiring< std::string >.

Definition at line 297 of file Formula.h.

◆ observe()

virtual value_type semiring::Formula::observe ( value_type child,
const std::string & datum ) const
inlineoverridevirtual

Render a likelihood-weighting observation.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 560 of file Formula.h.

◆ one()

virtual value_type semiring::Formula::one ( ) const
inlineoverridevirtual

Return the multiplicative identity \(\mathbb{1}\).

Returns
The one element of the semiring.

Implements semiring::Semiring< std::string >.

Definition at line 270 of file Formula.h.

Here is the caller graph for this function:

◆ parse_leaf()

value_type semiring::Formula::parse_leaf ( const char * v) const
inline

Definition at line 594 of file Formula.h.

◆ plus()

virtual value_type semiring::Formula::plus ( const std::vector< value_type > & v) const
inlineoverridevirtual

Apply the additive operation to a list of values.

Parameters
vOrdered list of operands (empty list should return zero()).
Returns
\(v_0 \oplus v_1 \oplus \cdots\).

Implements semiring::Semiring< std::string >.

Definition at line 273 of file Formula.h.

Here is the call graph for this function:

◆ plus_of()

virtual value_type semiring::Formula::plus_of ( const std::vector< const value_type * > & v) const
inlineoverridevirtual

plus over the values v points to, read in place.

GenericCircuit::evaluate passes the values of a gate's children this way rather than copied into a vector. The default copies them and calls plus; a semiring whose values may be large (Formula) overrides it.

Parameters
vOrdered list of pointers to the operands.
Returns
\(v_0 \oplus v_1 \oplus \cdots\).

Reimplemented from semiring::Semiring< std::string >.

Definition at line 279 of file Formula.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rv()

virtual value_type semiring::Formula::rv ( const std::string & spec,
const std::vector< value_type > & params ) const
inlineoverridevirtual

Render a random-variable leaf from its on-disk encoding.

"normal:2.5,0.5" becomes "normal(2.5, 0.5)"; a wired parameter (written "$i", making the leaf a compound / latent one) is replaced by the rendering of the corresponding wire. Parsing here is deliberately textual: the rendering must survive any family the distribution registry gains, including one this build does not know.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 430 of file Formula.h.

Here is the call graph for this function:

◆ semimod()

virtual value_type semiring::Formula::semimod ( value_type x,
value_type s ) const
inlineoverridevirtual

Apply a semimodule scalar multiplication.

Parameters
xProvenance value.
sScalar value.
Returns
\(x * s\) in the semimodule.
Exceptions
SemiringExceptionif not overridden.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 332 of file Formula.h.

◆ strip_outer()

std::string semiring::Formula::strip_outer ( const std::string & s)
inlinestaticprivate

s without the cosmetic outer paren pair.

Definition at line 671 of file Formula.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ strip_outer_in_place()

void semiring::Formula::strip_outer_in_place ( std::string & s)
inlinestaticprivate

Drop the cosmetic outer paren pair of s, without a copy.

Definition at line 664 of file Formula.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ subscript()

std::string semiring::Formula::subscript ( std::size_t n)
inlinestaticprivate

n in Unicode subscript digits.

Definition at line 203 of file Formula.h.

Here is the caller graph for this function:

◆ symbolic()

virtual bool semiring::Formula::symbolic ( ) const
inlineoverridevirtual

Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown, define).

A symbolic semiring renders the provenance rather than evaluating it; where a recursion derives a tuple through itself, the least solution of its equations is an infinite sum, which such a semiring renders as the equations themselves (see GenericCircuit::solveFixSystem).

Returns
false by default; override, with the two methods below.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 238 of file Formula.h.

◆ symbolic_unknown()

virtual value_type semiring::Formula::symbolic_unknown ( std::size_t position) const
inlineoverridevirtual

Name an unknown after its position in its system, xᵢ: the name ProvSQL Studio gives the same unknown on the circuit.

An unknown of another system of the same evaluation at the same position is told apart by primes (x₁′).

Reimplemented from semiring::Semiring< std::string >.

Definition at line 247 of file Formula.h.

Here is the call graph for this function:

◆ times()

virtual value_type semiring::Formula::times ( const std::vector< value_type > & v) const
inlineoverridevirtual

Apply the multiplicative operation to a list of values.

Parameters
vOrdered list of operands (empty list should return one()).
Returns
\(v_0 \otimes v_1 \otimes \cdots\).

Implements semiring::Semiring< std::string >.

Definition at line 276 of file Formula.h.

Here is the call graph for this function:

◆ times_of()

virtual value_type semiring::Formula::times_of ( const std::vector< const value_type * > & v) const
inlineoverridevirtual

times over the values v points to, read in place (see plus_of).

Parameters
vOrdered list of pointers to the operands.
Returns
\(v_0 \otimes v_1 \otimes \cdots\).

Reimplemented from semiring::Semiring< std::string >.

Definition at line 290 of file Formula.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ to_text()

std::string semiring::Formula::to_text ( value_type s) const
inline

Serialise a Formula evaluation as text.

Drops the cosmetic outer paren pair that plus / times / monus always produce: at the root there is no enclosing context, so the outer parens carry no disambiguation value.

Definition at line 614 of file Formula.h.

Here is the call graph for this function:

◆ unknowns_in()

std::vector< std::size_t > semiring::Formula::unknowns_in ( const std::string & s) const
inlineprivate

The indices of the unknowns occurring in s: a name counts where no further subscript digit or prime follows it (x₁ is neither in x₁₂ nor in x₁′).

Definition at line 215 of file Formula.h.

Here is the caller graph for this function:

◆ unmapped_input()

virtual value_type semiring::Formula::unmapped_input ( const std::string & uuid) const
inlineoverridevirtual

Identify a variable leaf the provenance mapping does not name by an abbreviated form of its UUID.

Formula serialises the circuit, so the base class's \(\mathbb{1}\) would be doubly wrong here: it makes every unnamed leaf look alike, and – being the multiplicative identity – it is dropped by the enclosing times(), collapsing a whole join to "𝟙". An abbreviated UUID keeps the structure and stays recognisable against what ProvSQL Studio prints on the circuit's nodes. The first UUID group is kept: 32 bits, enough to tell the leaves of one circuit apart at a glance, with the full value one get_children / Studio click away.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 591 of file Formula.h.

◆ value()

virtual value_type semiring::Formula::value ( const std::string & s) const
inlineoverridevirtual

Interpret a literal string as a semiring value.

Used for gate_value gates whose payload is a string.

Parameters
sLiteral string.
Returns
The corresponding semiring value.
Exceptions
SemiringExceptionif not overridden.

Reimplemented from semiring::Semiring< std::string >.

Definition at line 418 of file Formula.h.

◆ wrapped()

bool semiring::Formula::wrapped ( const std::string & s)
inlinestaticprivate

Whether the first character of s opens a paren pair closed by its last one, which is then cosmetic.

Definition at line 650 of file Formula.h.

Here is the caller graph for this function:

◆ zero()

virtual value_type semiring::Formula::zero ( ) const
inlineoverridevirtual

Return the additive identity \(\mathbb{0}\).

Returns
The zero element of the semiring.

Implements semiring::Semiring< std::string >.

Definition at line 267 of file Formula.h.

Here is the caller graph for this function:

Member Data Documentation

◆ equations

std::shared_ptr<Equations> semiring::Formula::equations = std::make_shared<Equations>()
private

Definition at line 200 of file Formula.h.


The documentation for this class was generated from the following file:
  • /home/pierre/git/software/provsql/src/semiring/Formula.h