Abstract base class for (m-)semirings. More...

#include "Semiring.h"

Public Types
typedef V	value_type
	The carrier type of this semiring.

Public Member Functions
virtual value_type	zero () const =0
	Return the additive identity $\mathbb{0}$.
virtual value_type	one () const =0
	Return the multiplicative identity $\mathbb{1}$.
virtual value_type	plus (const std::vector< value_type > &v) const =0
	Apply the additive operation to a list of values.
virtual value_type	times (const std::vector< value_type > &v) const =0
	Apply the multiplicative operation to a list of values.
virtual value_type	monus (value_type x, value_type y) const =0
	Apply the monus (m-semiring difference) operation.
virtual value_type	delta (value_type x) const =0
	Apply the $\delta$ operator.
virtual value_type	cmp (value_type s1, ComparisonOperator op, value_type s2) const
	Evaluate a comparison gate.
virtual value_type	semimod (value_type x, value_type s) const
	Apply a semimodule scalar multiplication.
virtual value_type	agg (AggregationOperator op, const std::vector< value_type > &s)
	Evaluate an aggregation gate.
virtual value_type	value (const std::string &s) const
	Interpret a literal string as a semiring value.
virtual value_type	unmapped_input (const std::string &uuid) const
	Value of a variable leaf (`gate_input` / `gate_mulinput`) that the provenance mapping does not name.
virtual value_type	rv (const std::string &spec, const std::vector< value_type > &params) const
	Evaluate a continuous random-variable leaf (`gate_rv`).
virtual value_type	arith (ArithmeticOperator op, const std::vector< value_type > &children, const std::string &extra) const
	Evaluate an arithmetic gate over scalar children (`gate_arith`).
virtual value_type	mixture (value_type p, value_type x, value_type y) const
	Evaluate a Bernoulli mixture (`gate_mixture`, three wires).
virtual value_type	categorical (value_type key, const std::vector< double > &probs, const std::vector< std::string > &outcomes) const
	Evaluate a categorical mixture (`gate_mixture` over `gate_mulinput` outcomes).
virtual value_type	guarded_case (const std::vector< value_type > &children) const
	Evaluate a guarded selection (`gate_case`).
virtual value_type	observe (value_type child, const std::string &datum) const
	Evaluate a latent-variable observation (`gate_observe`).
virtual value_type	conditioned (const std::vector< value_type > &children) const
	Evaluate a conditioning marker (`gate_conditioned`).
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	compatibleWithBooleanRewrite () const
	Return `true` if a semiring homomorphism `BoolFunc(X)` →+* `S` exists, so the safe-query (Boolean-rewrite) optimisation produces circuits that are semantically faithful when evaluated under this semiring.
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.

Detailed Description

template<typename V>
class semiring::Semiring< V >

Abstract base class for (m-)semirings.

Template Parameters

V	The carrier type (e.g. `bool`, `unsigned`, `std::string`).

Required operations

All pure-virtual methods must be implemented by concrete subclasses.

Optional operations

cmp(), semimod(), agg(), and value() have default implementations that throw SemiringException. Override them in subclasses that support these circuit gate types.

Absorptive semirings

A semiring is absorptive (i.e., $\mathbb{1} \oplus a = \mathbb{1}$ for all $a$) iff absorptive() returns true. Absorptivity implies idempotency ( $a \oplus a = a$), which lets the circuit evaluator and the HAVING-semantics machinery deduplicate operands and short-circuit over the multiplicative identity.

Definition at line 96 of file Semiring.h.

Member Typedef Documentation

◆ value_type

template<typename V>

typedef V semiring::Semiring< V >::value_type

The carrier type of this semiring.

Definition at line 100 of file Semiring.h.

Constructor & Destructor Documentation

◆ ~Semiring()

template<typename V>

virtual semiring::Semiring< V >::~Semiring ( )

virtualdefault

Member Function Documentation

◆ absorptive()

template<typename V>

virtual bool semiring::Semiring< V >::absorptive ( ) const

inlinevirtual

Return true if this semiring is absorptive ( $\mathbb{1} \oplus a = \mathbb{1}$ for all $a$).

When true, the circuit evaluator and HAVING-semantics machinery may exploit the resulting idempotency ( $a \oplus a = a$, implied by absorptivity) to deduplicate children of plus gates and to short-circuit over the multiplicative identity.

Returns: false by default; override to return true.

Reimplemented in semiring::Boolean, semiring::BoolExpr, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::TropicalNonneg, and semiring::Viterbi.

Definition at line 360 of file Semiring.h.

◆ agg()

template<typename V>

virtual value_type semiring::Semiring< V >::agg	(	AggregationOperator	op,
		const std::vector< value_type > &	s )

inlinevirtual

Evaluate an aggregation gate.

Parameters

op	The aggregation function (COUNT, SUM, MIN…).
s	List of child semiring values to aggregate.

Returns: The aggregated value.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 180 of file Semiring.h.

◆ arith()

template<typename V>

virtual value_type semiring::Semiring< V >::arith	(	ArithmeticOperator	op,
		const std::vector< value_type > &	children,
		const std::string &	extra ) const

inlinevirtual

Evaluate an arithmetic gate over scalar children (gate_arith).

Parameters

op	The arithmetic operation.
children	The values of the gate's wires (for `PERCENTILE`, interleaved [indicator, value] pairs).
extra	The gate's payload (the fraction for `PERCENTILE`, empty otherwise).

Returns: The result of the operation in this semiring.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 248 of file Semiring.h.

◆ categorical()

template<typename V>

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

inlinevirtual

Evaluate a categorical mixture (gate_mixture over gate_mulinput outcomes).

Parameters

key	The value of the mixture's key (its `gate_input` wire).
probs	Probability of each outcome.
outcomes	Textual payload of each outcome, parallel to `probs`.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 285 of file Semiring.h.

◆ certified_exclusive_plus()

template<typename V>

virtual value_type semiring::Semiring< V >::certified_exclusive_plus ( const std::vector< value_type > & ) const

inlinevirtual

Build the disjunction of pairwise-exclusive disjuncts, certified deterministic.

Only called when certifying() is true; the default throws.

Reimplemented in semiring::BoolExpr.

Definition at line 441 of file Semiring.h.

◆ certified_world_term()

template<typename V>

virtual value_type semiring::Semiring< V >::certified_world_term	(	const std::vector< value_type > &	,
		const std::vector< value_type > &	) const

inlinevirtual

Build one complete world term: the conjunction of the present literals and the negations of the missing literals, certified decomposable.

Only called when certifying() is true; the default throws.

Reimplemented in semiring::BoolExpr.

Definition at line 429 of file Semiring.h.

◆ certifying()

template<typename V>

virtual bool semiring::Semiring< V >::certifying ( ) const

inlinevirtual

Whether this semiring builds certified exclusive enumerations (see the three hooks below).

The HAVING possible-worlds machinery (provsql_having) enumerates, for a comparison over a group aggregate, the complete valuations of the group's contributors that satisfy the predicate. Those disjuncts partition the worlds – the OR is deterministic and each world term an AND of literals over distinct contributors, decomposable – i.e., the enumeration is a d-DNNF by construction. A circuit-building semiring can persist that knowledge as the d-DNNF certificate (the same mark the bounded-treewidth reachability route emits), letting the linear certificate-aware evaluators handle the result; scalar semirings have nothing to mark.

Returns: false by default (the hooks below then go unused and the default constructions are used).

Reimplemented in semiring::BoolExpr.

Definition at line 404 of file Semiring.h.

◆ cmp()

template<typename V>

virtual value_type semiring::Semiring< V >::cmp	(	value_type	s1,
		ComparisonOperator	op,
		value_type	s2 ) const

inlinevirtual

Evaluate a comparison gate.

Parameters

s1	Left operand.
op	Comparison operator.
s2	Right operand.

Returns: Result of the comparison in this semiring.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 156 of file Semiring.h.

◆ compatibleWithBooleanRewrite()

template<typename V>

virtual bool semiring::Semiring< V >::compatibleWithBooleanRewrite ( ) const

inlinevirtual

Return true if a semiring homomorphism BoolFunc(X) →+* S exists, so the safe-query (Boolean-rewrite) optimisation produces circuits that are semantically faithful when evaluated under this semiring.

The compiled-semiring dispatcher consults this predicate before evaluating a circuit whose root gate carries PROVSQL_ROOT_TAG_BOOLEAN_REWRITE. Returning false on a tagged circuit raises CircuitException.

Defaults to false: a new semiring whose author has not yet verified the homomorphism is fail-closed by construction. Subclasses with a verified homomorphism (currently Boolean, BoolExpr, Formula, and IntervalUnion) override to return true. The justification (Lean-proof reference) belongs in a comment next to each override; see the src/semiring/ headers.

Reimplemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

Definition at line 382 of file Semiring.h.

◆ conditioned()

template<typename V>

virtual value_type semiring::Semiring< V >::conditioned ( const std::vector< value_type > & children ) const

inlinevirtual

Evaluate a conditioning marker (gate_conditioned).

Parameters

children The gate's wires: [target, evidence] for the value-level (random-variable) form, [target, evidence, joint] for the Boolean-event one, where joint is the materialised times(target, evidence).

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 337 of file Semiring.h.

◆ delta()

template<typename V>

virtual value_type semiring::Semiring< V >::delta ( value_type x ) const

pure virtual

Apply the $\delta$ operator.

Parameters

x	Input value.

Returns: $\delta(x)$.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

◆ guarded_case()

template<typename V>

virtual value_type semiring::Semiring< V >::guarded_case ( const std::vector< value_type > & children ) const

inlinevirtual

Evaluate a guarded selection (gate_case).

Parameters

children The gate's wires, [guard_1, value_1, …, guard_k, value_k, default] (odd length), with first-match semantics.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 304 of file Semiring.h.

◆ independent_literal()

template<typename V>

virtual bool semiring::Semiring< V >::independent_literal ( const value_type & ) const

inlinevirtual

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.

Only consulted when certifying() is true.

Returns: false by default.

Reimplemented in semiring::BoolExpr.

Definition at line 418 of file Semiring.h.

◆ mixture()

template<typename V>

virtual value_type semiring::Semiring< V >::mixture	(	value_type	p,
		value_type	x,
		value_type	y ) const

inlinevirtual

Evaluate a Bernoulli mixture (gate_mixture, three wires).

Parameters

p	The Bernoulli event's value.
x	The value taken when the event holds.
y	The value taken otherwise.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 267 of file Semiring.h.

◆ monus()

template<typename V>

virtual value_type semiring::Semiring< V >::monus	(	value_type	x,
		value_type	y ) const

pure virtual

Apply the monus (m-semiring difference) operation.

Parameters

x	Minuend.
y	Subtrahend.

Returns: $x \ominus y$.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

◆ observe()

template<typename V>

virtual value_type semiring::Semiring< V >::observe	(	value_type	child,
		const std::string &	datum ) const

inlinevirtual

Evaluate a latent-variable observation (gate_observe).

Parameters

child	The observed leaf's value.
datum	The observed value, as text.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 319 of file Semiring.h.

◆ one()

template<typename V>

virtual value_type semiring::Semiring< V >::one ( ) const

pure virtual

Return the multiplicative identity $\mathbb{1}$.

Returns: The one element of the semiring.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

Here is the caller graph for this function:

◆ plus()

template<typename V>

virtual value_type semiring::Semiring< V >::plus ( const std::vector< value_type > & v ) const

pure virtual

Apply the additive operation to a list of values.

Parameters

v	Ordered list of operands (empty list should return `zero()`).

Returns: $v_0 \oplus v_1 \oplus \cdots$.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

◆ rv()

template<typename V>

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

inlinevirtual

Evaluate a continuous random-variable leaf (gate_rv).

Parameters

spec	The gate's distribution encoding (`"normal:2.5,0.5"`), where a parameter written `"$i"` is wired rather than literal (a latent / compound leaf).
params	The values of the gate's wires, indexed as the `"$i"` references; empty for an all-literal leaf.

Returns: The leaf's value in this semiring.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 227 of file Semiring.h.

◆ semimod()

template<typename V>

virtual value_type semiring::Semiring< V >::semimod	(	value_type	x,
		value_type	s ) const

inlinevirtual

Apply a semimodule scalar multiplication.

Parameters

x	Provenance value.
s	Scalar value.

Returns: $x * s$ in the semimodule.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 168 of file Semiring.h.

◆ times()

template<typename V>

virtual value_type semiring::Semiring< V >::times ( const std::vector< value_type > & v ) const

pure virtual

Apply the multiplicative operation to a list of values.

Parameters

v	Ordered list of operands (empty list should return `one()`).

Returns: $v_0 \otimes v_1 \otimes \cdots$.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

◆ unmapped_input()

template<typename V>

virtual value_type semiring::Semiring< V >::unmapped_input ( const std::string & uuid ) const

inlinevirtual

Value of a variable leaf (gate_input / gate_mulinput) that the provenance mapping does not name.

The absent-mapping convention: such a leaf contributes no provenance, i.e. the multiplicative identity, which is what every proper semiring wants and what this default returns. A semiring that renders the circuit rather than evaluating it overrides this to identify the leaf instead – $\mathbb{1}$ would not merely be anonymous there, it would be absorbed by the enclosing times and take the structure with it. BooleanCircuit::toString does the same for the Boolean-expression rendering (its x<id> fallback).

Parameters

uuid	The leaf gate's UUID, in canonical text form.

Reimplemented in semiring::Formula.

Definition at line 212 of file Semiring.h.

Here is the call graph for this function:

◆ value()

template<typename V>

virtual value_type semiring::Semiring< V >::value ( const std::string & s ) const

inlinevirtual

Interpret a literal string as a semiring value.

Used for gate_value gates whose payload is a string.

Parameters

s	Literal string.

Returns: The corresponding semiring value.

Exceptions

SemiringException if not overridden.

Reimplemented in semiring::Formula.

Definition at line 193 of file Semiring.h.

◆ zero()

template<typename V>

virtual value_type semiring::Semiring< V >::zero ( ) const

pure virtual

Return the additive identity $\mathbb{0}$.

Returns: The zero element of the semiring.

Implemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

The documentation for this class was generated from the following file:

/home/pierre/git/software/provsql/src/semiring/Semiring.h

Public Types

Public Member Functions

Detailed Description

Required operations

Optional operations

Absorptive semirings

Member Typedef Documentation

◆ value_type

Constructor & Destructor Documentation

◆ ~Semiring()

Member Function Documentation

◆ absorptive()

◆ agg()

◆ arith()

◆ categorical()

◆ certified_exclusive_plus()

◆ certified_world_term()

◆ certifying()

◆ cmp()

◆ compatibleWithBooleanRewrite()

◆ conditioned()

◆ delta()

◆ guarded_case()

◆ independent_literal()

◆ mixture()

◆ monus()

◆ observe()

◆ one()

◆ plus()

◆ rv()

◆ semimod()

◆ times()

◆ unmapped_input()

◆ value()

◆ zero()