what4-1.0: Solver-agnostic symbolic values support for issuing queries

Copyright(c) Galois Inc 2015-2020
LicenseBSD3
Maintainerjhendrix@galois.com
Safe HaskellNone
LanguageHaskell2010

What4.Expr.WeightedSum

Contents

Description

Declares a weighted sum type used for representing sums over variables and an offset in one of the supported semirings. This module also implements a representation of semiring products.

Synopsis

Utilities

type Tm f = (HashableF f, OrdF f, HasAbsValue f) Source #

Weighted sums

data WeightedSum (f :: BaseType -> Type) (sr :: SemiRing) Source #

A weighted sum of semiring values. Mathematically, this represents an affine operation on the underlying expressions.

Instances
OrdF f => TestEquality (WeightedSum f :: SemiRing -> Type) Source # 
Instance details

Defined in What4.Expr.WeightedSum

Methods

testEquality :: WeightedSum f a -> WeightedSum f b -> Maybe (a :~: b) #

OrdF f => Hashable (WeightedSum f sr) Source # 
Instance details

Defined in What4.Expr.WeightedSum

Methods

hashWithSalt :: Int -> WeightedSum f sr -> Int #

hash :: WeightedSum f sr -> Int #

sumRepr :: WeightedSum f sr -> SemiRingRepr sr Source #

Runtime representation of the semiring for this sum.

sumOffset :: Lens' (WeightedSum f sr) (Coefficient sr) Source #

Retrieve the constant addend of the weighted sum.

constant :: Tm f => SemiRingRepr sr -> Coefficient sr -> WeightedSum f sr Source #

Create a sum from a constant coefficient value.

var :: Tm f => SemiRingRepr sr -> f (SemiRingBase sr) -> WeightedSum f sr Source #

Create a weighted sum corresponding to the given variable.

scaledVar :: Tm f => SemiRingRepr sr -> Coefficient sr -> f (SemiRingBase sr) -> WeightedSum f sr Source #

This returns a variable times a constant.

asConstant :: WeightedSum f sr -> Maybe (Coefficient sr) Source #

Attempt to parse a weighted sum as a constant.

asVar :: WeightedSum f sr -> Maybe (f (SemiRingBase sr)) Source #

Attempt to parse a weighted sum as a single expression. asVar w = Just r when denotation(w) = r

asWeightedVar :: WeightedSum f sr -> Maybe (Coefficient sr, f (SemiRingBase sr)) Source #

Attempt to parse weighted sum as a single expression with a coefficient. asWeightedVar w = Just (c,r) when denotation(w) = c*r.

asAffineVar :: WeightedSum f sr -> Maybe (Coefficient sr, f (SemiRingBase sr), Coefficient sr) Source #

Attempt to parse a weighted sum as a single expression with a coefficient and offset. asAffineVar w = Just (c,r,o) when denotation(w) = c*r + o.

isZero :: SemiRingRepr sr -> WeightedSum f sr -> Bool Source #

Return true if a weighted sum is equal to constant 0.

traverseVars :: forall k j m sr. (Applicative m, Tm k) => (j (SemiRingBase sr) -> m (k (SemiRingBase sr))) -> WeightedSum j sr -> m (WeightedSum k sr) Source #

Traverse the expressions in a weighted sum.

traverseCoeffs :: forall m f sr. (Applicative m, Tm f) => (Coefficient sr -> m (Coefficient sr)) -> WeightedSum f sr -> m (WeightedSum f sr) Source #

Traverse the coefficients in a weighted sum.

add :: Tm f => SemiRingRepr sr -> WeightedSum f sr -> WeightedSum f sr -> WeightedSum f sr Source #

Add two sums, collecting terms as necessary and deleting terms whose coefficients sum to 0.

addVar :: Tm f => SemiRingRepr sr -> WeightedSum f sr -> f (SemiRingBase sr) -> WeightedSum f sr Source #

Add a variable to the sum.

addVars :: Tm f => SemiRingRepr sr -> f (SemiRingBase sr) -> f (SemiRingBase sr) -> WeightedSum f sr Source #

Create a weighted sum that represents the sum of two terms.

addConstant :: SemiRingRepr sr -> WeightedSum f sr -> Coefficient sr -> WeightedSum f sr Source #

Add a constant to the sum.

scale :: Tm f => SemiRingRepr sr -> Coefficient sr -> WeightedSum f sr -> WeightedSum f sr Source #

Multiply a sum by a constant coefficient.

eval Source #

Arguments

:: (r -> r -> r)

Addition function

-> (Coefficient sr -> f (SemiRingBase sr) -> r)

Scalar multiply

-> (Coefficient sr -> r)

Constant evaluation

-> WeightedSum f sr 
-> r 

Evaluate a sum given interpretations of addition, scalar multiplication, and a constant rational.

evalM Source #

Arguments

:: Monad m 
=> (r -> r -> m r)

Addition function

-> (Coefficient sr -> f (SemiRingBase sr) -> m r)

Scalar multiply

-> (Coefficient sr -> m r)

Constant evaluation

-> WeightedSum f sr 
-> m r 

Evaluate a sum given interpretations of addition, scalar multiplication, and a constant. This evaluation is threaded through a monad. The addition function is associated to the left, as in foldlM.

extractCommon :: Tm f => WeightedSum f sr -> WeightedSum f sr -> (WeightedSum f sr, WeightedSum f sr, WeightedSum f sr) Source #

Given two weighted sums x and y, this returns a triple (z,x',y') where x = z + x' and y = z + y' and z contains the "common" parts of x and y. We only extract common terms when both terms occur with the same coefficient in each sum.

This is primarily used to simplify if-then-else expressions to preserve shared subterms.

fromTerms :: Tm f => SemiRingRepr sr -> [(f (SemiRingBase sr), Coefficient sr)] -> Coefficient sr -> WeightedSum f sr Source #

Produce a weighted sum from a list of terms and an offset.

transformSum :: (Applicative m, Tm g) => SemiRingRepr sr' -> (Coefficient sr -> m (Coefficient sr')) -> (f (SemiRingBase sr) -> m (g (SemiRingBase sr'))) -> WeightedSum f sr -> m (WeightedSum g sr') Source #

Apply update functions to the terms and coefficients of a weighted sum.

reduceIntSumMod Source #

Arguments

:: Tm f 
=> WeightedSum f SemiRingInteger

The sum to reduce

-> Integer

The modulus, must not be 0

-> WeightedSum f SemiRingInteger 

Reduce a weighted sum of integers modulo a concrete integer. This reduces each of the coefficients modulo the given integer, removing any that are congruent to 0; the offset value is also reduced.

Ring products

data SemiRingProduct (f :: BaseType -> Type) (sr :: SemiRing) Source #

A product of semiring values.

Instances
OrdF f => TestEquality (SemiRingProduct f :: SemiRing -> Type) Source # 
Instance details

Defined in What4.Expr.WeightedSum

Methods

testEquality :: SemiRingProduct f a -> SemiRingProduct f b -> Maybe (a :~: b) #

OrdF f => Hashable (SemiRingProduct f sr) Source # 
Instance details

Defined in What4.Expr.WeightedSum

Methods

hashWithSalt :: Int -> SemiRingProduct f sr -> Int #

hash :: SemiRingProduct f sr -> Int #

traverseProdVars :: forall k j m sr. (Applicative m, Tm k) => (j (SemiRingBase sr) -> m (k (SemiRingBase sr))) -> SemiRingProduct j sr -> m (SemiRingProduct k sr) Source #

Traverse the expressions in a product.

nullProd :: SemiRingProduct f sr -> Bool Source #

Returns true if the product is trivial (contains no terms).

asProdVar :: SemiRingProduct f sr -> Maybe (f (SemiRingBase sr)) Source #

If the product consists of exactly on term, return it.

prodRepr :: SemiRingProduct f sr -> SemiRingRepr sr Source #

Runtime representation of the semiring for this product

prodVar :: Tm f => SemiRingRepr sr -> f (SemiRingBase sr) -> SemiRingProduct f sr Source #

Produce a product representing the single given term.

prodMul :: Tm f => SemiRingProduct f sr -> SemiRingProduct f sr -> SemiRingProduct f sr Source #

Multiply two products, collecting terms and adding occurrences.

prodEval Source #

Arguments

:: (r -> r -> r)

multiplication evalation

-> (f (SemiRingBase sr) -> r)

term evaluation

-> SemiRingProduct f sr 
-> Maybe r 

Evaluate a product, given a function representing multiplication and a function to evaluate terms.

prodEvalM Source #

Arguments

:: Monad m 
=> (r -> r -> m r)

multiplication evalation

-> (f (SemiRingBase sr) -> m r)

term evaluation

-> SemiRingProduct f sr 
-> m (Maybe r) 

Evaluate a product, given a function representing multiplication and a function to evaluate terms, where both functions are threaded through a monad.

prodContains :: OrdF f => SemiRingProduct f sr -> f (SemiRingBase sr) -> Bool Source #

Returns true if the product contains at least on occurrence of the given term.