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	~Semiring ()=default

virtual bool	absorptive () const
	Return `true` if this semiring is absorptive ( \(a \oplus a = a\)).

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., \(a \oplus a = a\) for all \(a\)) iff absorptive() returns true. This allows the circuit evaluator to deduplicate children of plus gates for efficiency.

Definition at line 83 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 87 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 ( \(a \oplus a = a\)).

When true, the circuit evaluator may deduplicate the children of plus gates, which can improve performance significantly for semirings such as Boolean and Why-provenance.

Returns: false by default; override to return true.

Reimplemented in semiring::Boolean, and semiring::BoolExpr.

Definition at line 195 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 167 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 143 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, and semiring::Why.

◆ 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, and semiring::Why.

◆ 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, and semiring::Why.

◆ 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::Counting, semiring::Formula, semiring::BoolExpr, and semiring::Why.

◆ 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 155 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::Counting, semiring::Formula, semiring::BoolExpr, and semiring::Why.

◆ 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 180 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, 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()

◆ cmp()

◆ delta()

◆ monus()

◆ one()

◆ plus()

◆ semimod()

◆ times()

◆ value()

◆ zero()