lattest-lib-0.2: src/Lattest/Model/Symbolic/Internal/ExprImpls.hs
{-
This is a modified version of:
TorXakis - Model Based Testing
See LICENSE in the parent Symbolic folder.
-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE ViewPatterns #-}
{-# OPTIONS_GHC -Wno-redundant-constraints #-}
module Lattest.Model.Symbolic.Internal.ExprImpls
( -- * Constructors to create Value Expressions
-- ** Constant value
sConst
, sTrue
, sFalse
-- ** VarRef
, sVar
-- ** General Operators to create Value Expressions
-- *** Equal
, (.==)
-- *** If Then Else
, sIfThenElse
-- *** Function Call
--, cstrFunc
-- ** Boolean Operators to create Value Expressions
-- *** Not
, sNot
-- *** And
, sAnd
-- *** Sum
, sSum
-- *** Product
, sProduct
-- *** Divide
, (./)
-- *** Modulo
, (.%)
-- *** Comparisons GEZ
, sIsNonNegative
-- ** List operations
, sLength
, sConcat
, sCons
, sNil
, sAppend
, sElem
, sTake
, sDrop
, sHead
, sTail
, sMap
, sFilter
, sFoldr
, sFoldl
-- ** Pair operations
, sFirst
, sSecond
, sPair
, pattern SPair
, ETriple, pattern STriple
, EQuadruple, pattern SQuadruple
-- ** Either
, sEither, sLeft, sRight
-- ** Nested sums
-- In Lattest, we only have binary sum (Either) and product (Tuple) types, but you might be interested in a sum or product with three or more subtypes instead.
-- Here, we provide a few functions that may relieve some of the burden of using nested binary splits to represent such types.
, EThree, sFirstOfThree, sSecondOfThree, sThirdOfThree, sThree
, EFour, sFirstOfFour, sSecondOfFour, sThirdOfFour, sFourthOfFour, sFour
-- ** Enums
, SEnum (..), SEnum2 (..), SEnum3 (..), SEnum4 (..), SEnum5 (..)
, SEnumThree, sEnum3, SEnumFour, sEnum4, SEnumFive, sEnum5
-- * Quantifiers
, sForall
, sExists
-- * Substitution of var by value
, VarModel(..)
, assign
, Valuation(..)
, varUnion
, mapVars
, mapVarExprs
, valuationToVarModel
, emptyValuation
, assignValues
, assignValue
, getVariables
, identityVarModel
, varsToGuard
, insertIntoValuation
, substConst
, subst
, substVarModel
, assignedExpr
, assignment
, noAssignment
, (=:)
, eval
, reduce
, mapExpressionVars
)
where
import Control.Arrow (first)
import qualified Data.Set as Set
import qualified Lattest.Model.Symbolic.Internal.Boute as Boute
import qualified Lattest.Model.Symbolic.Internal.FreeMonoidX as FMX
import Lattest.Model.Symbolic.Internal.Product as Product
import Lattest.Model.Symbolic.Internal.Sum as Sum
import Lattest.Model.Symbolic.Internal.ExprDefs
import Data.Dependent.Map (DMap)
import qualified Data.Dependent.Map as DMap
import Data.Constraint.Extras (Has (..))
import Data.Constraint.Compose (ComposeC)
import qualified Data.List as List
import Data.SBV (AlgReal)
import Lattest.Model.Symbolic.Internal.FreeMonoidX (mapFreeMonoidX, allFreeMonoidX)
import GHC.Integer (divInteger)
import Data.Maybe (catMaybes)
import Data.Some (Some (..))
import Data.Dependent.Sum (DSum(..))
sConst :: ExprConstraints t => t -> Expr t
sConst = Expr . Const
sTrue :: Expr Bool
sTrue = sConst True
sFalse :: Expr Bool
sFalse = sConst False
sVar :: Variable t -> Expr t
sVar = Expr . Var
-- | Apply operator ITE (IF THEN ELSE) on the provided value expressions.
-- Preconditions are /not/ checked.
sIfThenElse :: Expr Bool -> Expr t -> Expr t -> Expr t
sIfThenElse (view -> Const True) t _ = t
sIfThenElse (view -> Const False) _ f = f
sIfThenElse (view -> c) (view -> t) (view -> f) = Expr $ Ite c t f
(.==) :: ExprConstraints t => Expr t -> Expr t -> Expr Bool
x .== y = Expr $ Equal (typeOf' x) (view x) (view y)
infix 4 .==
{-
-- | Apply operator Equal on the provided value expressions.
-- Preconditions are /not/ checked.
(.==) :: Expr -> Expr -> Expr
-- Simplification a == a <==> True
(.==) ve1 ve2 | ve1 == ve2 = sConst (Cbool True)
-- Simplification Different Values <==> False : use Same Values are already detected in previous step
(.==) (view -> Vconst _) (view -> Vconst _) = sConst (Cbool False)
-- Simplification True == e <==> e (twice)
(.==) (view -> Vconst (Cbool True)) e = e
(.==) e (view -> Vconst (Cbool True)) = e
-- Simplification False == e <==> not e (twice)
(.==) (view -> Vconst (Cbool False)) e = sNot e
(.==) e (view -> Vconst (Cbool False)) = sNot e
-- Not x == x <==> false (twice)
(.==) e (view -> Vnot n) | e == n = sConst (Cbool False)
(.==) (view -> Vnot n) e | e == n = sConst (Cbool False)
-- Not x == Not y <==> x == y -- same representation
(.==) (view -> Vnot n1) (view -> Vnot n2) = (.==) n1 n2
-- Not a == b <==> a == Not b -- same representation (twice)
(.==) x@(view -> Vnot n) e = if n <= e
then Expr (Vequal x e)
else Expr (Vequal (sNot e) n)
(.==) e x@(view -> Vnot n) = if n <= e
then Expr (Vequal x e)
else Expr (Vequal (sNot e) n)
-- a == b <==> b == a -- same representation
(.==) ve1 ve2 = if ve1 <= ve2
then Expr (Vequal ve1 ve2)
else Expr (Vequal ve2 ve1)
-}
-- | Apply operator Not on the provided value expression.
-- Preconditions are /not/ checked.
sNot :: Expr Bool -> Expr Bool
sNot (view -> Const b) = sConst (not b) -- constant fold: ¬True ≡ False, ¬False ≡ True
sNot (view -> Not ve) = Expr ve -- eliminate double negation: ¬¬e ≡ e
-- push the negation into the branches: ¬(if cs then tb else fb) ≡ if cs then ¬tb else ¬fb
sNot (view -> Ite cs tb fb) = Expr (Ite cs (view $ sNot (Expr tb)) (view $ sNot (Expr fb)))
sNot (view -> ve) = Expr $ Not ve
-- | Apply operator And on the provided set of value expressions.
-- Preconditions are /not/ checked.
sAnd :: Set.Set (Expr Bool) -> Expr Bool
--sAnd = sAnd' . flattenAnd
sAnd = mkAnd . flattenAnd
where
flattenAnd :: Set.Set (Expr Bool) -> Set.Set (ExprView Bool)
flattenAnd = Set.unions . map fromExpr . Set.toList
fromExpr :: Expr Bool -> Set.Set (ExprView Bool)
fromExpr (view -> And a) = a
fromExpr (view -> x) = Set.singleton x
-- annihilation (x ∧ False ≡ False) and identity (x ∧ True ≡ x); a single conjunct needs no wrapping
mkAnd :: Set.Set (ExprView Bool) -> Expr Bool
mkAnd (absorb -> vs)
| Set.member (Const False) vs = sFalse
| hasComplements vs = sFalse -- contradiction: x ∧ ¬x ≡ False
| otherwise = case Set.toList vs' of
[] -> sTrue
[v] -> Expr v
_ -> Expr (And vs')
where vs' = Set.delete (Const True) vs
-- absorption under negation: e ∧ ¬(e ∧ rest) ≡ e ∧ ¬rest. A conjunct that is
-- already asserted at the top level of the conjunction is redundant inside a
-- negated conjunction, so it can be dropped from it. If every conjunct of the
-- negated cube is dropped this yields ¬True ≡ False, which the checks above catch.
absorb :: Set.Set (ExprView Bool) -> Set.Set (ExprView Bool)
absorb vs = Set.map simplify vs
where
simplify (Not (And s))
| not (Set.null (Set.intersection s vs)) = view $ sNot $ sAnd $ Set.map Expr $ s Set.\\ vs
simplify v = v
-- does the conjunction contain both some e and its negation ¬e?
hasComplements :: Set.Set (ExprView Bool) -> Bool
hasComplements vs = any ((`Set.member` vs) . negated) (Set.toList vs)
where
negated (Not e) = e
negated e = Not e
{-
-- And doesn't contain elements of type Vand.
sAnd' :: Set.Set Expr Bool -> Expr Bool
sAnd' s =
if Set.member (sConst (Cbool False)) s
then sConst (Cbool False)
else let s' = Set.delete (sConst (Cbool True)) s in
case Set.size s' of
0 -> sConst (Cbool True)
1 -> head (Set.toList s')
_ -> -- not(x) and x == False
let nots = filterNot (Set.toList s') in
if any (contains s') nots
then sConst (Cbool False)
-- else let ts = isCstrTuples (Set.toList s') in
-- if sameExpr ts
-- then sConst (Cbool False)
else Expr (Vand s')
where
filterNot :: [Expr] -> [Expr]
filterNot [] = []
filterNot (x:xs) = case view x of
Vnot n -> n : filterNot xs
_ -> filterNot xs
contains :: Set.Set Expr -> Expr -> Bool
contains set (view -> Vand a) = all (`Set.member` set) (Set.toList a)
contains set a = Set.member a set
{-
isCstrTuples :: [Expr] -> [(CstrId, Expr)]
isCstrTuples [] = []
isCstrTuples (x:xs) = case view x of
Viscstr c v -> (c,v) : isCstrTuples xs
_ -> isCstrTuples xs
-}
sameExpr :: [(CstrId, Expr)] -> Bool
sameExpr [] = False
sameExpr (x:xs) = containExpr x xs
where
containExpr :: (CstrId, Expr) -> [(CstrId, Expr)] -> Bool
containExpr _ [] = False
containExpr (c1,x1) ((c2,x2):cxs) = if x1 == x2
then assert (c1 /= c2) True
else containExpr (c1,x1) cxs
-}
-- * Sum
isSum :: ExprView Integer -> Bool
isSum (Sum IntType _) = True
isSum _ = False
getSum :: ExprView Integer -> FreeSum (ExprView Integer)
getSum (Sum IntType s) = s
getSum _ = error "ExprImpls.hs - getSum - Unexpected Expr "
sSumInt :: FreeSum (Expr Integer) -> Expr Integer
sSumInt = Expr . cstrSum . FMX.mapTerms (SumTerm . view . summand)
-- | Apply operator sum on the provided sum of value expressions.
-- Preconditions are /not/ checked.
cstrSum :: FreeSum (ExprView Integer) -> ExprView Integer
-- implementation details:
-- Properties incorporated
-- at most one value: the value is the sum of all values
-- special case if the sum is zero, no value is inserted since v == v+0
-- remove all nested sums, since (a+b) + (c+d) == (a+b+c+d)
cstrSum ms = cstrSum' $ nonadds <> FMX.flatten sumOfAdds
where
(adds, nonadds) = FMX.partitionT isSum ms
sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Integer)))
sumOfAdds = FMX.mapTerms (getSum . summand) adds
-- Sum doesn't contain elements of type VExprSum
cstrSum' :: FreeSum (ExprView Integer) -> ExprView Integer
cstrSum' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
sumVals = summand $ FMX.foldFMX valueSum
retMS = case sumVals of
0 -> nonvals -- 0 + x == x
_ -> Sum.add (Const sumVals) nonvals
in
case FMX.toOccurList retMS of
[] -> Const 0 -- sum of nothing equal zero
[(term,1)] -> summand term
_ -> Sum IntType retMS
getConst :: ExprView e -> e
getConst (Const c) = c
getConst _ = error "Not Const"
isSumF :: ExprView Double -> Bool
isSumF (Sum FloatType _) = True
isSumF _ = False
getSumF :: ExprView Double -> FreeSum (ExprView Double)
getSumF (Sum FloatType s) = s
getSumF _ = error "ExprImpls.hs - getSumF - Unexpected Expr "
isSumR :: ExprView Rational -> Bool
isSumR (Sum RationalType _) = True
isSumR _ = False
getSumR :: ExprView Rational -> FreeSum (ExprView Rational)
getSumR (Sum RationalType s) = s
getSumR _ = error "ExprImpls.hs - getSumF - Unexpected Expr "
isSumReal :: ExprView AlgReal -> Bool
isSumReal (Sum RealType _) = True
isSumReal _ = False
getSumReal :: ExprView AlgReal -> FreeSum (ExprView AlgReal)
getSumReal (Sum RealType s) = s
getSumReal _ = error "ExprImpls.hs - getSumF - Unexpected Expr "
sSumFloat :: FreeSum (Expr Double) -> Expr Double
sSumFloat = Expr . cstrSumF . FMX.mapTerms (SumTerm . view . summand)
-- | Apply operator sum on the provided sum of floating-point values.
cstrSumF :: FreeSum (ExprView Double) -> ExprView Double
cstrSumF ms = cstrSumF' $ nonadds <> FMX.flatten sumOfAdds
where
(adds, nonadds) = FMX.partitionT isSumF ms
sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Double)))
sumOfAdds = FMX.mapTerms (getSumF . summand) adds
cstrSumF' :: FreeSum (ExprView Double) -> ExprView Double
cstrSumF' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
sumVals = summand $ FMX.foldFMX valueSum
retMS = case sumVals of
0.0 -> nonvals -- 0.0 + x == x
_ -> Sum.add (Const sumVals) nonvals
in
case FMX.toOccurList retMS of
[] -> Const 0.0 -- sum of nothing equals zero
[(term,1)] -> summand term
_ -> Sum FloatType retMS
sSumRational :: FreeSum (Expr Rational) -> Expr Rational
sSumRational = Expr . cstrSumR . FMX.mapTerms (SumTerm . view . summand)
cstrSumR :: FreeSum (ExprView Rational) -> ExprView Rational
cstrSumR ms = cstrSumR' $ nonadds <> FMX.flatten sumOfAdds
where
(adds, nonadds) = FMX.partitionT isSumR ms
sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView Rational)))
sumOfAdds = FMX.mapTerms (getSumR . summand) adds
cstrSumR' :: FreeSum (ExprView Rational) -> ExprView Rational
cstrSumR' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
sumVals = summand $ FMX.foldFMX valueSum
retMS = case sumVals of
0.0 -> nonvals -- 0.0 + x == x
_ -> Sum.add (Const sumVals) nonvals
in
case FMX.toOccurList retMS of
[] -> Const 0.0 -- sum of nothing equals zero
[(term,1)] -> summand term
_ -> Sum RationalType retMS
sSumReal :: FreeSum (Expr AlgReal) -> Expr AlgReal
sSumReal = Expr . cstrSumReal . FMX.mapTerms (SumTerm . view . summand)
cstrSumReal :: FreeSum (ExprView AlgReal) -> ExprView AlgReal
cstrSumReal ms = cstrSumReal' $ nonadds <> FMX.flatten sumOfAdds
where
(adds, nonadds) = FMX.partitionT isSumReal ms
sumOfAdds :: FMX.FreeMonoidX (FMX.FreeMonoidX (SumTerm (ExprView AlgReal)))
sumOfAdds = FMX.mapTerms (getSumReal . summand) adds
cstrSumReal' :: FreeSum (ExprView AlgReal) -> ExprView AlgReal
cstrSumReal' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
valueSum = FMX.mapTerms (SumTerm . getConst . summand) vals
sumVals = summand $ FMX.foldFMX valueSum
retMS = case sumVals of
0.0 -> nonvals -- 0.0 + x == x
_ -> Sum.add (Const sumVals) nonvals
in
case FMX.toOccurList retMS of
[] -> Const 0.0 -- sum of nothing equals zero
[(term,1)] -> summand term
_ -> Sum RealType retMS
-- Product
-- | Is Expr a Product Expression?
isProduct :: ExprView Integer -> Bool
isProduct (Product IntType _) = True
isProduct _ = False
getProduct :: ExprView Integer -> FreeProduct (ExprView Integer)
getProduct (Product IntType p) = p
getProduct _ = error "ExprImpls.hs - getProduct - Unexpected Expr "
sProductInt :: FreeProduct (Expr Integer) -> Expr Integer
sProductInt = Expr . cstrPrd . FMX.mapTerms (ProductTerm . view . factor)
-- | Apply operator product on the provided product of value expressions.
-- Be aware that division is not associative for Integer, so only use power >= 0.
-- Preconditions are /not/ checked.
cstrPrd :: FreeProduct (ExprView Integer) -> ExprView Integer
-- implementation details:
-- Properties incorporated
-- at most one value: the value is the product of all values
-- special case if the product is one, no value is inserted since v == v*1
-- remove all nested products, since (a*b) * (c*d) == (a*b*c*d)
cstrPrd ms =
cstrPrd' $ noprods <> FMX.flatten prodOfProds
where
(prods, noprods) = FMX.partitionT isProduct ms
prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Integer)))
prodOfProds = FMX.mapTerms (getProduct . factor) prods
-- Product doesn't contain elements of type VExprProduct
cstrPrd' :: FreeProduct (ExprView Integer) -> ExprView Integer
cstrPrd' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
(zeros, _) = FMX.partitionT isZero vals
in
case FMX.nrofDistinctTerms zeros of
0 -> -- let productVals = Product.foldPower timesVal 1 vals in
let intProducts = FMX.mapTerms (getConst <$>) vals
productVals = factor (FMX.foldFMX intProducts)
in
case FMX.toDistinctAscOccurListT nonvals of
[] -> Const productVals
[(term, 1)] -> cstrSum (FMX.fromOccurList [(SumTerm term, productVals)]) -- term can be Sum -> rewrite needed
_ -> cstrSum (FMX.fromOccurList [(SumTerm (Product IntType nonvals), productVals)]) -- productVals can be 1 -> rewrite possible
_ -> let (_, n) = Product.fraction zeros in
case FMX.nrofDistinctTerms n of
0 -> Const 0 -- 0 * x == 0
_ -> error "Error in model: Division by Zero in Product (via negative power)"
where
isZero :: ExprView Integer -> Bool
isZero (Const 0) = True
isZero _ = False
-- Product of floating-point values
isProductF :: ExprView Double -> Bool
isProductF (Product FloatType _) = True
isProductF _ = False
getProductF :: ExprView Double -> FreeProduct (ExprView Double)
getProductF (Product FloatType p) = p
getProductF _ = error "ExprImpls.hs - getProductF - Unexpected Expr "
-- Product of floating-point values
isProductR :: ExprView Rational -> Bool
isProductR (Product RationalType _) = True
isProductR _ = False
getProductR :: ExprView Rational -> FreeProduct (ExprView Rational)
getProductR (Product RationalType p) = p
getProductR _ = error "ExprImpls.hs - getProductF - Unexpected Expr "
-- Product of floating-point values
isProductReal :: ExprView AlgReal -> Bool
isProductReal (Product RealType _) = True
isProductReal _ = False
getProductReal :: ExprView AlgReal -> FreeProduct (ExprView AlgReal)
getProductReal (Product RealType p) = p
getProductReal _ = error "ExprImpls.hs - getProductF - Unexpected Expr "
sProductFloat :: FreeProduct (Expr Double) -> Expr Double
sProductFloat = Expr . cstrPrdF . FMX.mapTerms (ProductTerm . view . factor)
-- | Apply operator product on the provided product of floating-point values.
cstrPrdF :: FreeProduct (ExprView Double) -> ExprView Double
cstrPrdF ms =
cstrPrdF' $ noprods <> FMX.flatten prodOfProds
where
(prods, noprods) = FMX.partitionT isProductF ms
prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Double)))
prodOfProds = FMX.mapTerms (getProductF . factor) prods
-- Product doesn't contain elements of type ProductFloat
cstrPrdF' :: FreeProduct (ExprView Double) -> ExprView Double
cstrPrdF' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
(zeros, _) = FMX.partitionT isZeroF vals
in
case FMX.nrofDistinctTerms zeros of
0 -> let floatProducts = FMX.mapTerms (getConst <$>) vals
productVals = factor (FMX.foldFMX floatProducts)
withConst = if productVals == 1.0 -- 1.0 * x == x
then nonvals
else Product.multiply (Const productVals) nonvals
in
case FMX.toDistinctAscOccurListT withConst of
[] -> Const productVals
[(term, 1)] -> term
_ -> Product FloatType withConst
_ -> let (_, n) = Product.fraction zeros in
case FMX.nrofDistinctTerms n of
0 -> Const 0.0 -- 0.0 * x == 0.0
_ -> error "Error in model: Division by Zero in Product (via negative power)"
where
isZeroF :: ExprView Double -> Bool
isZeroF (Const 0.0) = True
isZeroF _ = False
sProductRational :: FreeProduct (Expr Rational) -> Expr Rational
sProductRational = Expr . cstrPrdR . FMX.mapTerms (ProductTerm . view . factor)
-- | Apply operator product on the provided product of floating-point values.
cstrPrdR :: FreeProduct (ExprView Rational) -> ExprView Rational
cstrPrdR ms =
cstrPrdR' $ noprods <> FMX.flatten prodOfProds
where
(prods, noprods) = FMX.partitionT isProductR ms
prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView Rational)))
prodOfProds = FMX.mapTerms (getProductR . factor) prods
-- Product doesn't contain elements of type ProductFloat
cstrPrdR' :: FreeProduct (ExprView Rational) -> ExprView Rational
cstrPrdR' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
(zeros, _) = FMX.partitionT isZeroR vals
in
case FMX.nrofDistinctTerms zeros of
0 -> let floatProducts = FMX.mapTerms (getConst <$>) vals
productVals = factor (FMX.foldFMX floatProducts)
withConst = if productVals == 1.0 -- 1.0 * x == x
then nonvals
else Product.multiply (Const productVals) nonvals
in
case FMX.toDistinctAscOccurListT withConst of
[] -> Const productVals
[(term, 1)] -> term
_ -> Product RationalType withConst
_ -> let (_, n) = Product.fraction zeros in
case FMX.nrofDistinctTerms n of
0 -> Const 0.0 -- 0.0 * x == 0.0
_ -> error "Error in model: Division by Zero in Product (via negative power)"
where
isZeroR :: ExprView Rational -> Bool
isZeroR (Const 0.0) = True
isZeroR _ = False
sProductReal :: FreeProduct (Expr AlgReal) -> Expr AlgReal
sProductReal = Expr . cstrPrdReal . FMX.mapTerms (ProductTerm . view . factor)
-- | Apply operator product on the provided product of floating-point values.
cstrPrdReal :: FreeProduct (ExprView AlgReal) -> ExprView AlgReal
cstrPrdReal ms =
cstrPrdReal' $ noprods <> FMX.flatten prodOfProds
where
(prods, noprods) = FMX.partitionT isProductReal ms
prodOfProds :: FMX.FreeMonoidX (FMX.FreeMonoidX (ProductTerm (ExprView AlgReal)))
prodOfProds = FMX.mapTerms (getProductReal . factor) prods
-- Product doesn't contain elements of type ProductFloat
cstrPrdReal' :: FreeProduct (ExprView AlgReal) -> ExprView AlgReal
cstrPrdReal' ms =
let (vals, nonvals) = FMX.partitionT isConst ms
(zeros, _) = FMX.partitionT isZeroR vals
in
case FMX.nrofDistinctTerms zeros of
0 -> let floatProducts = FMX.mapTerms (getConst <$>) vals
productVals = factor (FMX.foldFMX floatProducts)
withConst = if productVals == 1.0 -- 1.0 * x == x
then nonvals
else Product.multiply (Const productVals) nonvals
in
case FMX.toDistinctAscOccurListT withConst of
[] -> Const productVals
[(term, 1)] -> term
_ -> Product RealType withConst
_ -> let (_, n) = Product.fraction zeros in
case FMX.nrofDistinctTerms n of
0 -> Const 0.0 -- 0.0 * x == 0.0
_ -> error "Error in model: Division by Zero in Product (via negative power)"
where
isZeroR :: ExprView AlgReal -> Bool
isZeroR (Const 0.0) = True
isZeroR _ = False
-- Divide
-- | Apply operator Divide on the provided integer value expressions.
-- Preconditions are /not/ checked.
divideInt :: Expr Integer -> Expr Integer -> Expr Integer
divideInt (view -> Const t) (view -> Const n) | n /= 0 = sConst (t `Boute.div` n) -- leave error case (division by zero) unevaluated
divideInt (view -> vet) (view -> ven) = Expr (Divide vet ven)
-- | Apply operator Divide on the provided floating-point value expressions.
-- Preconditions are /not/ checked.
divideFloat :: Expr Double -> Expr Double -> Expr Double
divideFloat (view -> Const t) (view -> Const n) | n /= 0 = sConst (t / n) -- leave error case (division by zero) unevaluated
divideFloat (view -> vet) (view -> ven) = Expr (DivideFloat vet ven)
-- | Apply operator Divide on the provided floating-point value expressions.
-- Preconditions are /not/ checked.
divideRational :: Expr Rational -> Expr Rational -> Expr Rational
divideRational (view -> Const t) (view -> Const n) | n /= 0 = sConst (t / n) -- leave error case (division by zero) unevaluated
divideRational (view -> vet) (view -> ven) = Expr (DivideFloat vet ven)
-- Modulo
-- | Apply operator Modulo on the provided value expressions.
-- Preconditions are /not/ checked.
(.%) :: Expr Integer -> Expr Integer -> Expr Integer
(.%) (view -> Const t) (view -> Const n) | n /= 0 = sConst (t `Boute.mod` n) -- leave error case (division by zero) unevaluated
(.%) (view -> vet) (view -> ven) = Expr (Modulo vet ven)
infixl 7 .%
-- | Apply operator GEZ (Greater Equal Zero) on the provided integer value expression.
-- Preconditions are /not/ checked.
sIsNonNegativeInt :: Expr Integer -> Expr Bool
-- Simplification Values
sIsNonNegativeInt (view -> Const v) = sConst (0 <= v)
sIsNonNegativeInt (view -> Length _ _) = sConst True -- length of list is always Greater or equal to zero
sIsNonNegativeInt (view -> ve) = Expr (Gez ve)
-- | Apply operator GEZ (Greater Equal Zero) on the provided floating-point value expression.
-- Preconditions are /not/ checked.
sIsNonNegativeFloat :: Num a => Expr a -> Expr Bool
sIsNonNegativeFloat (view -> Const v) = sConst (0 <= v)
sIsNonNegativeFloat (view -> ve) = Expr (Gez ve)
sSum :: forall a. (Num a, ExprType a) => FreeSum (Expr a) -> Expr a
sSum = case typeOf' (undefined :: Expr a) of
IntType -> sSumInt
FloatType -> sSumFloat
RationalType -> sSumRational
RealType -> sSumReal
_ -> error "impossible Num instance"
sProduct :: forall a. (Num a, ExprType a) => FreeProduct (Expr a) -> Expr a
sProduct = case typeOf' (undefined :: Expr a) of
IntType -> sProductInt
FloatType -> sProductFloat
RationalType -> sProductRational
RealType -> sProductReal
_ -> error "impossible Num instance"
sIsNonNegative :: Num a => Expr a -> Expr Bool
sIsNonNegative a = case withExprConstraints a $ typeOf' a of
IntType -> sIsNonNegativeInt a
FloatType -> sIsNonNegativeFloat a
RationalType -> sIsNonNegativeFloat a
RealType -> sIsNonNegativeFloat a
_ -> error "impossible Num instance"
infixl 7 ./
(./) :: Num a => Expr a -> Expr a -> Expr a
(./) x y = withExprConstraints x $ case typeOf' x of
IntType -> divideInt x y
FloatType -> divideFloat x y
RationalType -> divideRational x y
_ -> error "impossible Num instance"
sConcat :: ExprConstraints a => Expr [[a]] -> Expr [a]
sConcat = Expr . Concat . view
-- implementation details:
-- Properties incorporated
-- "" ++ x == x - remove empty strings
-- "a" ++ "b" == "ab" - concat consecutive string values
-- remove all nested sConcat, since (a ++ b) ++ (c ++ d) == (a ++ b ++ c ++ d)
sLength :: Expr [x] -> Expr Integer
sLength (view -> x) = Expr $ Length (case has @ExprType x $ typeOf' x of ListType t -> t) x
sCons :: Expr x -> Expr [x] -> Expr [x]
sCons (view -> x) (view -> xs) = Expr $ Cons x xs
sNil :: ExprConstraints x => Expr [x]
sNil = Expr $ Const []
sAppend :: Expr [x] -> Expr [x] -> Expr [x]
sAppend (view -> xs) (view -> ys) = Expr $ Append xs ys
sElem :: Expr x -> Expr [x] -> Expr Bool
sElem (view -> x) (view -> xs) = Expr $ LElem (has @ExprType x $ typeOf' x) x xs
sTake :: Expr Integer -> Expr [x] -> Expr [x]
sTake (view -> i) (view -> xs) = Expr $ Take i xs
sDrop :: Expr Integer -> Expr [x] -> Expr [x]
sDrop (view -> i) (view -> xs) = Expr $ Drop i xs
sFirst :: ExprType b => Expr (t, b) -> Expr t
sFirst (view -> i) = Expr $ First (typeOf undefined) i
sSecond :: ExprType a => Expr (a, t) -> Expr t
sSecond (view -> i) = Expr $ Second (typeOf undefined) i
pattern SPair :: (ExprType a, ExprType b) => () => Expr a -> Expr b -> Expr (a,b)
pattern SPair x y <- (\xy -> (sFirst xy, sSecond xy) -> (x, y)) where
SPair (view -> x) (view -> y) = Expr $ Pair x y
sPair :: Expr a -> Expr b -> Expr (a,b)
sPair x y = withExprConstraints x $ withExprConstraints y $ SPair x y
type ETriple a b c = Expr (a, (b, c))
pattern STriple :: (ExprType a, ExprType b, ExprType c) => () => Expr a -> Expr b -> Expr c -> ETriple a b c
pattern STriple x y z <- (\xyz -> (sFirst xyz, sFirst $ sSecond xyz, sSecond $ sSecond xyz) -> (x, y, z)) where
STriple (view -> x) (view -> y) (view -> z) = Expr $ Pair x $ Pair y z
type EQuadruple a b c d = Expr (a, (b, (c, d)))
pattern SQuadruple :: (ExprType a, ExprType b, ExprType c, ExprType d) => () => Expr a -> Expr b -> Expr c -> Expr d -> EQuadruple a b c d
pattern SQuadruple w x y z <- (\wxyz -> (sFirst wxyz, sFirst $ sSecond wxyz, sFirst $ sSecond $ sSecond wxyz, sSecond $ sSecond $ sSecond wxyz) -> (w, x, y, z)) where
SQuadruple (view -> w) (view -> x) (view -> y) (view -> z) = Expr $ Pair w $ Pair x $ Pair y z
sHead :: ExprConstraints x => Expr [x] -> Expr x
sHead (view -> xs) = Expr $ Head xs
sTail :: ExprConstraints x => Expr [x] -> Expr [x]
sTail (view -> xs) = Expr $ Tail xs
-- | Map a function over a list. Think of the variable a and the expression b as morally forming a function a -> b:
-- the variable will, within the expression, represent the argument to the function.
sMap :: (ExprConstraints a, ExprConstraints b) => Variable a -> Expr b -> Expr [a] -> Expr [b]
sMap v (view -> b) (view -> xs) = Expr $ Map v b xs
sFilter :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr [a] -> Expr [a]
sFilter v (view -> b) (view -> xs) = Expr $ Filter v b xs
sFoldr :: (ExprConstraints a) => Variable a -> Variable b -> Expr b -> Expr b -> Expr [a] -> Expr b
sFoldr va vb (view -> b) (view -> i) (view -> xs) = Expr $ Foldr va vb b i xs
sFoldl :: (ExprConstraints a) => Variable b -> Variable a -> Expr b -> Expr b -> Expr [a] -> Expr b
sFoldl vb va (view -> b) (view -> i) (view -> xs) = Expr $ Foldl vb va b i xs
sZip :: (ExprConstraints a, ExprConstraints b) => Expr [a] -> Expr [b] -> Expr [(a,b)]
sZip (view -> xs) (view -> ys) = Expr $ Zip (typeOf undefined) (typeOf undefined) xs ys
-- | Case-of on Either: If sMap can be thought of as having type `(a -> b) -> List a -> List b`,
-- SEither should be considered as having type `(a -> c) -> (b -> c) -> Either a b -> c`.
sEither :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Variable a -> Variable b -> Expr c -> Expr c -> Expr (Either a b) -> Expr c
sEither lv rv (view -> le) (view -> re) (view -> e) = Expr $ Either lv rv le re e
sLeft :: (ExprConstraints a, ExprConstraints b) => Expr a -> Expr (Either a b)
sLeft (view -> a) = Expr $ ELeft a
sRight :: (ExprConstraints a, ExprConstraints b) => Expr b -> Expr (Either a b)
sRight (view -> b) = Expr $ ERight b
-- | Sum type with three options
type EThree a b c = Expr (Either a (Either b c))
sFirstOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr a -> EThree a b c
sFirstOfThree (view -> a) = Expr $ ELeft a
sSecondOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr b -> EThree a b c
sSecondOfThree (view -> b) = Expr $ ERight $ ELeft b
sThirdOfThree :: (ExprConstraints a, ExprConstraints b, ExprConstraints c) => Expr c -> EThree a b c
sThirdOfThree (view -> c) = Expr $ ERight $ ERight c
-- | Case-of on EThree
sThree :: Variable a -> Variable b -> Variable c -> Expr x -> Expr x -> Expr x -> EThree a b c -> Expr x
sThree va vb vc xa xb xc three = let vbc = Variable "sThreeIntermediate" (varType vb `SumType` varType vc) in
withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints xa $
sEither va vbc xa (sEither vb vc xb xc (sVar vbc)) three
-- | Sum type with four options
type EFour a b c d = Expr (Either a (Either b (Either c d)))
sFirstOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr a -> EFour a b c d
sFirstOfFour (view -> a) = Expr $ ELeft a
sSecondOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr b -> EFour a b c d
sSecondOfFour (view -> b) = Expr $ ERight $ ELeft b
sThirdOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr c -> EFour a b c d
sThirdOfFour (view -> c) = Expr $ ERight $ ERight $ ELeft c
sFourthOfFour :: (ExprConstraints a, ExprConstraints b, ExprConstraints c, ExprConstraints d) => Expr d -> EFour a b c d
sFourthOfFour (view -> d) = Expr $ ERight $ ERight $ ERight d
-- | Case-of on EFour
sFour :: Variable a -> Variable b -> Variable c -> Variable d -> Expr x -> Expr x -> Expr x -> Expr x -> EFour a b c d -> Expr x
sFour va vb vc vd xa xb xc xd four = let vthree = Variable "sFourIntermediate1" (varType vb `SumType` (varType vc `SumType` varType vd)) in
withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints vd $ withExprConstraints xa $
sEither va vthree xa (sThree vb vc vd xb xc xd $ sVar vthree) four
-- | Sum type with five options
type EFive a b c d e = Expr (Either a (Either b (Either c (Either d e))))
-- | Case-of on EFive
sFive :: Variable a -> Variable b -> Variable c -> Variable d -> Variable e -> Expr x -> Expr x -> Expr x -> Expr x -> Expr x -> EFive a b c d e -> Expr x
sFive va vb vc vd ve xa xb xc xd xe five = let vfour = Variable "sFiveIntermediate1" (varType vb `SumType` (varType vc `SumType` (varType vd `SumType` varType ve))) in
withExprConstraints va $ withExprConstraints vb $ withExprConstraints vc $ withExprConstraints vd $ withExprConstraints ve $ withExprConstraints xa $
sEither va vfour xa (sFour vb vc vd ve xb xc xd xe $ sVar vfour) five
-- | Symbolic enumerations, represented as sums of units.
class ExprType a => SEnum a where
sFirstOf :: Expr a
instance SEnum () where
sFirstOf = sConst ()
instance SEnum a => SEnum (Either () a) where
sFirstOf = withExprConstraints (typeOf @a undefined) $ sLeft $ sConst ()
-- | Class of enums with at least two options.
class SEnum a => SEnum2 a where
sSecondOf :: Expr a
instance SEnum a => SEnum2 (Either () a) where
sSecondOf = withExprConstraints (typeOf @a undefined) $ sRight sFirstOf
class SEnum2 a => SEnum3 a where
sThirdOf :: Expr a
instance SEnum2 a => SEnum3 (Either () a) where
sThirdOf = withExprConstraints (typeOf @a undefined) $ sRight sSecondOf
class SEnum3 a => SEnum4 a where
sFourthOf :: Expr a
instance SEnum3 a => SEnum4 (Either () a) where
sFourthOf = withExprConstraints (typeOf @a undefined) $ sRight sThirdOf
class SEnum4 a => SEnum5 a where
sFifthOf :: Expr a
instance SEnum4 a => SEnum5 (Either () a) where
sFifthOf = withExprConstraints (typeOf @a undefined) $ sRight sFourthOf
type SEnumThree = EThree () () ()
-- | Case-of on Enum with 3 options
sEnum3 :: Expr a -> Expr a -> Expr a -> SEnumThree -> Expr a
sEnum3 = sThree (Variable "1of3" UnitType) (Variable "2of3" UnitType) (Variable "3of3" UnitType)
type SEnumFour = EFour () () () ()
-- | Case-of on Enum with 4 options
sEnum4 :: Expr a -> Expr a -> Expr a -> Expr a -> SEnumFour -> Expr a
sEnum4 = sFour (Variable "1of4" UnitType) (Variable "2of4" UnitType) (Variable "3of4" UnitType) (Variable "4of4" UnitType)
type SEnumFive = EFive () () () () ()
-- | Case-of on Enum with 5 options
sEnum5 :: Expr a -> Expr a -> Expr a -> Expr a -> Expr a -> SEnumFive -> Expr a
sEnum5 = sFive (Variable "1of5" UnitType) (Variable "2of5" UnitType) (Variable "3of5" UnitType) (Variable "4of5" UnitType) (Variable "5of5" UnitType)
sForall :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr Bool
sForall v (view -> x) = Expr $ Forall v x
sExists :: (ExprConstraints a) => Variable a -> Expr Bool -> Expr Bool
sExists v (view -> x) = Expr $ Exists v x
-- | Apply String In Regular Expression operator on the provided value expressions.
-- Preconditions are /not/ checked.
--cstrStrInRe :: Expr -> Expr -> Expr
--cstrStrInRe (view -> Vconst (Cstring s)) (view -> Vconst (Cregex r)) = sConst (Cbool (T.unpack s =~ T.unpack (xsd2posix r) ) )
--cstrStrInRe s r = Expr (Vstrinre s r)
{-
-- | Create a call to a predefined function as a value expression.
cstrPredef :: PredefKind -> FuncId -> [Expr] -> Expr
cstrPredef p f a = Expr (Vpredef p f a)
-}
newtype Valuation = Valuation { runValuation :: DMap Variable Constant }
deriving (Eq, Ord)
instance Has (ComposeC Eq Constant) Variable where
has _ k = k
instance Has (ComposeC Ord Constant) Variable where
has _ k = k
instance Has (ComposeC Show Constant) Variable where
has _ k = k
instance Show Valuation where
show (Valuation val) = "{" ++ List.intercalate "," (printAsAssignments val) ++ "}"
where
printAsAssignments :: DMap Variable Constant -> [String]
printAsAssignments = DMap.foldrWithKey printAsAssignment []
printAsAssignment v t strs = (varName v ++ ":=" ++ show t) : strs
assignValues :: [Valuation -> Valuation] -> Valuation
assignValues = foldr ($) emptyValuation
emptyValuation :: Valuation
emptyValuation = Valuation DMap.empty
newtype VarModel = VarModel {runVarModel :: DMap Variable Expr}
deriving (Eq, Ord)
instance Show VarModel where
show (VarModel vm) = "{" ++ List.intercalate ", " (printAsAssignments vm) ++ "}"
where
printAsAssignments :: DMap Variable Expr -> [String]
printAsAssignments = DMap.foldrWithKey printAsAssignment []
printAsAssignment v t strs = (varName v ++ ":=" ++ show t) : strs
assignment :: [VarModel -> VarModel] -> VarModel
assignment = foldr ($) noAssignment
valuationToVarModel :: Valuation -> VarModel
valuationToVarModel = VarModel . DMap.map (\(Constant v) -> sConst v) . runValuation
insertIntoValuation :: Variable t -> Constant t -> Valuation -> Valuation
insertIntoValuation v c = withExprConstraints (varType v) $ assignValue v (fromConst c)
getVariables :: Valuation -> [Some Variable]
getVariables = DMap.keys . runValuation
assignIdentity :: Variable a -> VarModel -> VarModel
assignIdentity v = assign v (sVar v)
identityVarModel :: [Some Variable] -> VarModel
identityVarModel vars = assignment $ (\(Some v) -> assignIdentity v) <$> vars
varUnion :: VarModel -> VarModel -> VarModel
varUnion (VarModel vars1) (VarModel vars2) = VarModel $ DMap.union vars1 vars2
mapVars :: (forall a. Variable a -> Variable a) -> VarModel -> VarModel
mapVars f (VarModel vars) = VarModel $ DMap.mapKeysWith (error "mapVars mapped two distinct variables to the same variable") f vars
mapVarExprs :: (forall a. Variable a -> Variable a) -> VarModel -> VarModel
mapVarExprs f (VarModel vars) = VarModel $ DMap.map (mapExpressionVars f) vars
varsToGuard :: VarModel -> Expr Bool
varsToGuard (VarModel vars) = sAnd $ Set.fromList $ map (\(var :=> val) -> has @ExprType val $ withExprConstraints (typeOf' val) $ sVar var .== val) $ DMap.assocs vars
(=:) :: Variable t -> Expr t -> VarModel -> VarModel
(=:) = assign
infixr 0 =:
assign :: Variable t -> Expr t -> VarModel -> VarModel
assign v e = VarModel . DMap.insert v e . runVarModel
assignValue :: ExprConstraints t => Variable t -> t -> Valuation -> Valuation
assignValue v val = Valuation . DMap.insert v (Constant val) . runValuation
assignedExpr :: Variable t -> VarModel -> Maybe (Expr t)
assignedExpr v = DMap.lookup v . runVarModel
assignedExprWithDefault :: Variable t -> VarModel -> Expr t
assignedExprWithDefault v = DMap.findWithDefault (sVar v) v . runVarModel
noAssignment :: VarModel
noAssignment = VarModel DMap.empty
substConst :: Valuation -> Expr t -> Expr t
substConst valuation = subst (valuationToVarModel valuation)
-- | Apply a substitution to the right-hand-side expressions of a 'VarModel', leaving its keys untouched.
-- Composing substitutions this way lets an assignment be resolved against an accumulated substitution:
-- @substVarModel sigma assign@ rewrites every value-expression in @assign@ according to @sigma@.
substVarModel :: VarModel -> VarModel -> VarModel
substVarModel sigma (VarModel vars) = VarModel $ DMap.map (subst sigma) vars
-- | Substitute variables by value expressions in a value expression.
--
-- Preconditions are /not/ checked.
--
subst :: VarModel -- ^ Map from variables to value expressions.
{- -> Map.Map FuncId (FuncDef w e) -- ^ Map from identifiers to their
-- definitions, this is used to replace
-- function calls by their bodies if all
-- the arguments of the function are
-- constant.-}
-> Expr t -- ^ Value expression where the
-- substitution will take place.
-> Expr t
--subst ve _ x | ve == Map.empty = x
subst ve x = subst' ve (view x)
subst' :: VarModel -> ExprView t -> Expr t
subst' _ (Const const') = sConst const'
subst' ve (Var vid) = assignedExprWithDefault vid ve
subst' ve (Ite cond vexp1 vexp2) = sIfThenElse (subst' ve cond) (subst' ve vexp1) (subst' ve vexp2)
subst' ve (Divide t n) = (./) (subst' ve t) (subst' ve n)
subst' ve (Modulo t n) = (.%) (subst' ve t) (subst' ve n)
subst' ve (DivideFloat t n) = (./) (subst' ve t) (subst' ve n)
subst' ve (Sum t s) = withExprConstraints t $ sSum $ FMX.fromOccurListT $ map (first (subst' ve)) $ FMX.toDistinctAscOccurListT s
subst' ve (Product t p) = withExprConstraints t $ sProduct $ FMX.fromOccurListT $ map (first (subst' ve)) $ FMX.toDistinctAscOccurListT p
subst' ve (Length _ vexp) = sLength $ subst' ve vexp
subst' ve (Gez v) = sIsNonNegative (subst' ve v)
subst' ve (Equal _ vexp1 vexp2) = (.==) (subst' ve vexp1) (subst' ve vexp2)
subst' ve (And vexps) = sAnd $ Set.map (subst' ve) vexps
subst' ve (Not vexp) = sNot (subst' ve vexp)
subst' ve (Concat vexps) = sConcat $ subst' ve vexps
subst' ve (Cons x xs) = has @ExprType x $ sCons (subst' ve x) (subst' ve xs)
subst' ve (Append xs ys) = sAppend (subst' ve xs) (subst' ve ys)
subst' ve (LElem t x xs) = has @ExprType t $ sElem (subst' ve x) (subst' ve xs)
subst' ve (Take x xs) = sTake (subst' ve x) (subst' ve xs)
subst' ve (Drop x xs) = sDrop (subst' ve x) (subst' ve xs)
subst' ve (First t x) = has @ExprType t $ sFirst $ subst' ve x
subst' ve (Second t x) = has @ExprType t $ sSecond $ subst' ve x
subst' ve (Pair x y) = sPair (subst' ve x) (subst' ve y)
subst' ve (Head x) = sHead $ subst' ve x
subst' ve (Tail x) = sTail $ subst' ve x
subst' ve (ELeft x) = sLeft $ subst' ve x
subst' ve (ERight x) = sRight $ subst' ve x
subst' ve (Zip a b x y) = withExprConstraints a $ withExprConstraints b $ sZip (subst' ve x) (subst' ve y)
-- note: we purposely substitute the non-free variables too here. This ensures that any nested higher-order functions (e.g. a Map with an Either in the function)
-- that have shadowing (i.e. the name of the Map variable is also used by one of the Either variables) continue to work as expected:
-- each use of the variable refers to the closest (innermost) binder
subst' ve (Map v f xs) = Expr $ Map (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve xs)
subst' ve (Filter v f xs) = Expr $ Filter (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve xs)
subst' ve (Foldr v1 v2 f i xs) = Expr $ Foldr (case assignedExprWithDefault v1 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (case assignedExprWithDefault v2 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve i) (view $ subst' ve xs)
subst' ve (Foldl v1 v2 f i xs) = Expr $ Foldl (case assignedExprWithDefault v1 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (case assignedExprWithDefault v2 ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve f) (view $ subst' ve i) (view $ subst' ve xs)
subst' ve (Either vl vr l r x) = Expr $ Either
(case assignedExprWithDefault vl ve of { Expr (Var v) -> v; _ -> error "impossible"})
(case assignedExprWithDefault vr ve of { Expr (Var v) -> v; _ -> error "impossible"})
(view $ subst' ve l)
(view $ subst' ve r)
(view $ subst' ve x)
subst' ve (Forall v x) = Expr $ Forall (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve x)
subst' ve (Exists v x) = Expr $ Exists (case assignedExprWithDefault v ve of {Expr (Var v') -> v'; _ -> error "impossible"}) (view $ subst' ve x)
-- | Evaluate the provided value expression.
-- Either the Right Constant Value is returned or a (Left) error message.
eval :: Expr v -> Either String v
eval = evalView . view
evalView :: ExprView v -> Either String v
evalView (reduce -> Const v) = Right v
evalView _ = Left "Value Expression is not a constant value"
reduce :: ExprView v -> ExprView v
reduce (Var v) = Var v
reduce (Const v) = Const v
reduce (Ite (reduce -> Const b) (reduce -> e1) (reduce -> e2)) = if b then e1 else e2
reduce (Ite (reduce -> c) (reduce -> e1) (reduce -> e2)) = Ite c e1 e2
reduce (Sum t (mapFreeMonoidX reduce -> es)) | allFreeMonoidX isConst es = withExprConstraints t $ Const $ FMX.fold $ mapFreeMonoidX constant es
reduce (Sum t (mapFreeMonoidX reduce -> es)) = Sum t es
reduce (Product t (mapFreeMonoidX reduce -> es)) | allFreeMonoidX isConst es = withExprConstraints t $ Const $ FMX.fold $ mapFreeMonoidX constant es
reduce (Product t (mapFreeMonoidX reduce -> es)) = Product t es
reduce (Modulo (reduce -> e1) (reduce -> e2@(Const 0))) = Modulo e1 e2 -- leave divisions by zero as expressions
reduce (Modulo (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x `mod` y
reduce (Modulo (reduce -> e1) (reduce -> e2)) = Modulo e1 e2
reduce (Divide (reduce -> e1) (reduce -> e2@(Const 0))) = Divide e1 e2 -- leave divisions by zero as expressions
reduce (Divide (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x `divInteger` y
reduce (Divide (reduce -> e1) (reduce -> e2)) = Divide e1 e2
reduce (DivideFloat (reduce -> e1) (reduce -> e2@(Const 0))) = DivideFloat e1 e2 -- leave divisions by zero as expressions
reduce (DivideFloat (reduce -> (Const x)) (reduce -> (Const y))) = Const $ x / y
reduce (DivideFloat (reduce -> e1) (reduce -> e2)) = DivideFloat e1 e2
reduce (Length _ (reduce -> Const xs)) = Const $ fromIntegral $ length xs
reduce (Length t (reduce -> e)) = Length t e
reduce (Equal _ (reduce -> Const e1) (reduce -> Const e2)) = Const (e1 == e2)
reduce (Equal t (reduce -> e1) (reduce -> e2)) = Equal t e1 e2
reduce (Gez (reduce -> (Const x))) = Const $ x >= 0
reduce (Gez (reduce -> e)) = Gez e
reduce (Not (reduce -> (Const b))) = Const $ not b
reduce (Not (reduce -> e)) = Not e
reduce (And (Set.map reduce -> es))
| all isConst es = Const $ and (Set.map constant es)
| xs <- Set.filter isConst es
, ys <- Set.filter (not . isConst) es
= if and (Set.map constant xs) then And ys else Const False
reduce (Zip a b (reduce -> x) (reduce -> y))
| Const xs <- x
, Const ys <- y
= withExprConstraints a $ withExprConstraints b $ Const $ zip xs ys
| otherwise = Zip a b x y
reduce (Concat (reduce -> es))
| Const as <- es = Const $ concat as
reduce (Concat (reduce -> e)) = Concat e
reduce (Cons (reduce -> x) (reduce -> xs))
| Const a <- x
, Const as <- xs = Const $ a : as
| otherwise = Cons x xs
reduce (Append (reduce -> xs) (reduce -> ys))
| Const as <- xs
, Const bs <- ys = Const $ as ++ bs
| otherwise = Append xs ys
reduce (LElem t (reduce -> x) (reduce -> xs))
| Const a <- x
, Const as <- xs = Const $ a `elem` as
| otherwise = LElem t x xs
reduce (Take (reduce -> i) (reduce -> xs))
| Const j <- i
, Const as <- xs = Const $ take (fromInteger j) as
| otherwise = Take i xs
reduce (Drop (reduce -> i) (reduce -> xs))
| Const j <- i
, Const as <- xs = Const $ drop (fromInteger j) as
| otherwise = Drop i xs
reduce (First tp (reduce -> x))
| Const (y,_) <- x = case typeOf' x of
TupleType t _ -> withExprConstraints t $ Const y
| otherwise = First tp x
reduce (Second tp (reduce -> x))
| Const (_,y) <- x = case typeOf' x of
TupleType _ t -> withExprConstraints t $ Const y
| otherwise = Second tp x
reduce (Pair (reduce -> x) (reduce -> y))
| Const a <- x
, Const b <- y = Const (a,b)
| otherwise = Pair x y
reduce (Head (reduce -> xs))
| Const (y:_) <- xs = Const y
| Const [] <- xs = error "Head of empty list"
| otherwise = Head xs
reduce (Tail (reduce -> xs))
| Const (_:y) <- xs = Const y
| Const [] <- xs = error "Tail of empty list"
| otherwise = Tail xs
reduce (ELeft (reduce -> x))
| Const y <- x = Const (Left y)
| otherwise = ELeft x
reduce (ERight (reduce -> x))
| Const y <- x = Const (Right y)
| otherwise = ERight x
reduce (Map v (reduce -> f') (reduce -> xs))
| Const ys <- xs =
let f y = reduce $ view $ subst' (VarModel $ DMap.singleton v $ Expr $ Const y) f'
zs = map f ys
in case traverse (\case
Const a -> Just a
_ -> Nothing) zs of
Just as -> Const as
Nothing -> Map v f' xs
| otherwise = Map v f' xs
reduce (Filter v (reduce -> f') (reduce -> xs))
| Const ys <- xs =
let f y = (y,) $ reduce $ view $ subst' (VarModel $ DMap.singleton v $ Expr $ Const y) f'
zs = map f ys
in case traverse (\case -- innermost Maybe is whether the filter accepts the element, outermost Maybe is whether the reduction succeeds
(y, Const True) -> Just (Just y)
(_, Const False) -> Just Nothing
_ -> Nothing) zs of
Just as -> Const $ catMaybes as
Nothing -> Filter v f' xs
| otherwise = Filter v f' xs
reduce (Foldr v1 v2 (reduce -> f') (reduce -> i') (reduce -> xs))
| Const ys <- xs
, Const i <- i' =
let f a b = reduce $ view $ subst' (VarModel $ DMap.insert v2 (Expr b) $ DMap.singleton v1 $ Expr $ Const a) f'
in foldr f (Const i) ys
| otherwise = Foldr v1 v2 f' i' xs
reduce (Foldl v1 v2 (reduce -> f') (reduce -> i') (reduce -> xs))
| Const ys <- xs
, Const i <- i' =
let f b a = reduce $ view $ subst' (VarModel $ DMap.insert v1 (Expr b) $ DMap.singleton v2 $ Expr $ Const a) f'
in foldl f (Const i) ys
| otherwise = Foldl v1 v2 f' i' xs
reduce (Either vl vr (reduce -> l) (reduce -> r) (reduce -> x))
| Const (Left x') <- x =
reduce $ view $ subst' (VarModel $ DMap.singleton vl $ Expr $ Const x') l
| Const (Right x') <- x =
reduce $ view $ subst' (VarModel $ DMap.singleton vr $ Expr $ Const x') r
| otherwise = Either vl vr l r x
reduce (Forall v (reduce -> x))
| Const b <- x = Const b
| otherwise = Forall v x
reduce (Exists v (reduce -> x))
| Const b <- x = Const b
| otherwise = Exists v x
mapExpressionVars :: (forall a. Variable a -> Variable a) -> Expr t -> Expr t
mapExpressionVars f = Expr . mapExpressionVars' f . view
mapExpressionVars' :: (forall a. Variable a -> Variable a) -> ExprView t -> ExprView t
mapExpressionVars' _ e@(Const _) = e
mapExpressionVars' f (Var v) = Var $ f v -- this line is effectively the purpose of this function
mapExpressionVars' f (Ite cond vexp1 vexp2) = Ite (mapExpressionVars' f cond) (mapExpressionVars' f vexp1) (mapExpressionVars' f vexp2)
mapExpressionVars' f (Divide t n) = Divide (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (Modulo t n) = Modulo (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (DivideFloat t n) = DivideFloat (mapExpressionVars' f t) (mapExpressionVars' f n)
mapExpressionVars' f (Sum t s) = Sum t (FMX.mapTerms (SumTerm . mapExpressionVars' f . summand) s)
mapExpressionVars' f (Product t p) = Product t (FMX.mapTerms (ProductTerm . mapExpressionVars' f . factor) p)
mapExpressionVars' f (Length t vexp) = Length t (mapExpressionVars' f vexp)
mapExpressionVars' f (Gez v) = Gez (mapExpressionVars' f v)
mapExpressionVars' f (And vexps) = And (Set.map (mapExpressionVars' f) vexps)
mapExpressionVars' f (Not vexp) = Not (mapExpressionVars' f vexp)
mapExpressionVars' f (Equal t x y) = Equal t (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (LElem t x y) = LElem t (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (Concat x) = Concat (mapExpressionVars' f x)
mapExpressionVars' f (Cons x xs) = Cons (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Append x xs) = Append (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Take x xs) = Take (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Drop x xs) = Drop (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (First t x) = First t (mapExpressionVars' f x)
mapExpressionVars' f (Second t x) = Second t (mapExpressionVars' f x)
mapExpressionVars' f (Pair x xs) = Pair (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Head v) = Head (mapExpressionVars' f v)
mapExpressionVars' f (Tail v) = Tail (mapExpressionVars' f v)
mapExpressionVars' f (ELeft v) = ELeft (mapExpressionVars' f v)
mapExpressionVars' f (ERight v) = ERight (mapExpressionVars' f v)
mapExpressionVars' f (Zip a b x y) = Zip a b (mapExpressionVars' f x) (mapExpressionVars' f y)
mapExpressionVars' f (Map v x xs) = Map (f v) (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Filter v x xs) = Filter (f v) (mapExpressionVars' f x) (mapExpressionVars' f xs)
mapExpressionVars' f (Foldr v1 v2 g i xs) = Foldr (f v1) (f v2) (mapExpressionVars' f g) (mapExpressionVars' f i) (mapExpressionVars' f xs)
mapExpressionVars' f (Foldl v1 v2 g i xs) = Foldl (f v1) (f v2) (mapExpressionVars' f g) (mapExpressionVars' f i) (mapExpressionVars' f xs)
mapExpressionVars' f (Either v1 v2 l r x) = Either (f v1) (f v2) (mapExpressionVars' f l) (mapExpressionVars' f r) (mapExpressionVars' f x)
mapExpressionVars' f (Forall v x) = Forall (f v) (mapExpressionVars' f x)
mapExpressionVars' f (Exists v x) = Exists (f v) (mapExpressionVars' f x)