lattest-lib-0.2: src/Lattest/Model/Symbolic/SolveSymPrim.hs
{-# OPTIONS_HADDOCK hide, prune #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE ViewPatterns #-}
module Lattest.Model.Symbolic.SolveSymPrim (
combineGuards,
substituteInGuard,
evaluateGuard,
solveAnySequential,
valuationToGateValue,
solveGuard, solveGuardAny, solveGuardAmong, solveGuardIO,
isGuardSatisfiable
) where
import Lattest.Model.Alphabet(SymInteract(..), GateValue(..), SymGuard)
import Lattest.Model.BoundedMonad(BooleanConfiguration, OrdFunctor, asDualExpr)
import qualified Lattest.Model.Symbolic.Expr as E
import Lattest.Model.Symbolic.Expr (Valuation,Variable(..), runValuation, eval, substConst, Expr)
import Lattest.Model.Symbolic.Internal.ExprDefs (Expr (..))
import Lattest.SMT(getSolution,addAssertions,addDeclarations,getSolvable,SolvableProblem(..), runSMT, query, SMTQ, addAssertionsQ, sortOfEqualWith, push, pop)
import Data.Some (Some (..))
import qualified Data.Dependent.Map as DMap
import System.Random ( randomR, RandomGen, mkStdGen, randomIO )
import Data.Dependent.Sum (DSum (..))
import Control.Monad.State (StateT (..), evalStateT)
import Control.Monad.IO.Class (liftIO)
import System.IO (hPutStrLn, stderr)
import System.IO.Unsafe (unsafePerformIO)
import Data.IORef (IORef, newIORef, readIORef, atomicModifyIORef')
import qualified Data.Map as Map
import Data.Maybe (fromMaybe, isJust)
import Control.Monad (forM_, filterM)
import qualified Data.Set as Set
{-|
Combine the given guards into one.
-}
combineGuards :: (BooleanConfiguration m, OrdFunctor m) => m SymGuard -> SymGuard
combineGuards = asDualExpr
{-|
In the given guard, substitute the given valuation.
-}
substituteInGuard :: Valuation -> SymGuard -> SymGuard
--substituteInGuard valuation guard = evalConst' valuation guard
substituteInGuard = substConst
{-|
Evaluate the given guard
-}
evaluateGuard :: SymGuard -> Bool
evaluateGuard guard = case eval guard of
Left e -> error e -- TODO proper exception
Right b -> b
{-|
For the given list of interactions and guards, using SMT solving, pick the first interaction in that list for which the guard is satisfiable, if
any. The returned gate values for that interaction are picked randomly among the first solution and up to the given number of additional
solutions.
-}
solveAnySequential :: RandomGen randomgen => Int -> [(SymInteract g,SymGuard)] -> StateT randomgen IO (Maybe (GateValue g))
solveAnySequential _ [] = return Nothing
solveAnySequential extraSolutions ((interact'@(SymInteract _ vars),guard):alph) = do
maybeSolved <- solveGuardAmong extraSolutions vars guard
case maybeSolved of
Nothing -> solveAnySequential extraSolutions alph
Just solved -> return $ Just $ valuationToGateValue interact' solved
--data SymInteract g = SymInteract g [Variable]
--data GateValue g = GateValue g [Constant]
valuationToGateValue :: SymInteract g -> Valuation -> GateValue g
valuationToGateValue (SymInteract g' params) valuation =
GateValue g' $ fmap (getValueForVar $ runValuation valuation) params
where
getValueForVar :: DMap.DMap Variable E.Constant -> Some Variable -> Some E.Constant
getValueForVar val' (Some var) =
case DMap.lookup var val' of
Just (E.Constant value) -> case varType var of
E.IntType -> E.int value
E.UnitType -> E.unit
E.FloatType -> E.float value
E.RationalType -> E.rational value
E.RealType -> E.real value
E.BoolType -> E.bool value
E.CharType -> E.char value
E.ListType t -> E.withExprConstraints t E.list value
E.TupleType a b -> E.withExprConstraints a $ E.withExprConstraints b $ let (x,y) = value in E.tuple x y
E.SumType a b -> E.withExprConstraints a $ E.withExprConstraints b $ E.option value
Nothing -> undefined "valuationToGateValue: wrong type" -- TODO throw exception. Static type checking is infeasible due to external SMT solving. Should not happen if SMT solver behaves properly.
{-|
Check whether the given guard is satisfiable, without obtaining a valuation. If the SMT solver can not tell, the guard is reported
as not satisfiable, with a warning on stderr.
The outcome is cached per guard, so that a guard is only solved once. Outcomes where the SMT solver could not tell are not cached.
-}
isGuardSatisfiable :: [Some Variable] -> SymGuard -> IO Bool
isGuardSatisfiable vars guard = do
cache <- readIORef satisfiableCache
case Map.lookup guard cache of
Just isSat -> return isSat
Nothing -> do
g <- mkStdGen <$> randomIO -- We don't care about the solution, only whether there is one, so randomness is acceptable here
outcome <- fst $ runSMT g do
addDeclarations vars
addAssertions [guard]
query $ getSolvable >>= \case
Sat -> return $ Just True
Unsat -> return $ Just False
Unknown -> Nothing <$ warnUnknown guard
forM_ outcome \isSat -> atomicModifyIORef' satisfiableCache $ \c -> (Map.insert guard isSat c, ())
return $ fromMaybe False outcome
-- the guards solved so far by `isGuardSatisfiable`, with their outcome
satisfiableCache :: IORef (Map.Map SymGuard Bool)
satisfiableCache = unsafePerformIO $ newIORef Map.empty
{-# NOINLINE satisfiableCache #-}
warnUnknown :: SymGuard -> SMTQ ()
warnUnknown guard = liftIO $ hPutStrLn stderr $ "warning: SMT solver returned unknown, treating as unsatisfiable: " <> show guard
solveGuardIO :: [Some Variable] -> SymGuard -> IO (Maybe Valuation)
solveGuardIO vars guard = do
g <- mkStdGen <$> randomIO
evalStateT (solveGuard vars guard) g
solveGuard :: RandomGen g => [Some Variable] -> SymGuard -> StateT g IO (Maybe Valuation)
solveGuard = solveGuardAmong 10
-- | As 'solveGuard', but takes the first solution that the SMT solver comes up with, instead of picking randomly among several solutions.
solveGuardAny :: RandomGen g => [Some Variable] -> SymGuard -> StateT g IO (Maybe Valuation)
solveGuardAny = solveGuardAmong 0
-- solve the guard, picking randomly among the first solution and up to the given number of additional, different solutions.
-- If the SMT solver can not tell whether there is a (further) solution, then that is
-- treated as there being none, with a warning.
solveGuardAmong :: RandomGen g => Int -> [Some Variable] -> SymGuard -> StateT g IO (Maybe Valuation)
solveGuardAmong extraSolutions vars guard = StateT $ \randomgen ->
fst $ runSMT randomgen do
addDeclarations vars
-- addDeclarations (Set.toList $ freeVars guard)
addAssertions [guard]
-- Only one `query` block is allowed in a Symbolic. solveGuard returns an IO to avoid running into this problem.
-- Since sbv-14.8 (unreleased), addAssertions on higher order functions no longer need registerFunction to work in query.
-- This means that we will be able to change back to having our SMT type being what our SMTQ type is now; and having solveGuard return that.
query $ do
solveOutcome <- getSolvable
case solveOutcome of
Unsat -> return (Nothing, randomgen)
Unknown -> (Nothing, randomgen) <$ warnUnknown guard
Sat -> getSolution vars >>= \x -> go randomgen extraSolutions (Set.fromList $ filter hasMultipleValues vars) x []
where
-- the solutions found so far are the newest one and the older ones. The given variables are those that should still
-- differ from all solutions found so far. Once none are left, any solution different from the earlier ones is taken.
go :: RandomGen g => g -> Int -> Set.Set (Some Variable) -> Valuation -> [Valuation] -> SMTQ (Maybe Valuation, g)
go g 0 _ x xs = do
let (ix, g') = randomR (0, length xs) g
pure (Just $ (x : xs) !! ix, g')
go g n active x xs = do
-- assertions accumulate, so only the newest solution has to be excluded
addAssertionsQ [atleastoneisdifferent x]
(active', differing, g') <- solveDifferentIn g active (x : xs)
case differing of
Just x' -> go g' (n-1) active' x' (x : xs)
Nothing -> getSolvable >>= \case
Unsat -> go g' 0 mempty x xs
Unknown -> warnUnknown guard >> go g' 0 mempty x xs
Sat -> do
x' <- getSolution vars
go g' (n-1) mempty x' (x : xs)
-- look for a solution in which all given variables differ from the given solutions. Variables that can no longer
-- take a new value are dropped definitely. If the remaining variables can not all differ at once, randomly chosen
-- ones are ignored for this solution only.
solveDifferentIn :: RandomGen g => g -> Set.Set (Some Variable) -> [Valuation] -> SMTQ (Set.Set (Some Variable), Maybe Valuation, g)
solveDifferentIn g (Set.size -> 0) _ = pure (mempty, Nothing, g)
solveDifferentIn g active xs = differIn active xs >>= \case
Just x' -> pure (active, Just x', g)
Nothing -> do
stillVarying <- fmap Set.fromList <$> filterM (\v -> isJust <$> differIn (Set.singleton v) xs) $ Set.toList active
(differing, g') <- if length stillVarying == length active
then dropRandom g stillVarying -- these already failed to differ all at once
else dropUntilSolvable g stillVarying
pure (stillVarying, differing, g')
where
dropUntilSolvable g' (Set.size -> 0) = pure (Nothing, g')
dropUntilSolvable g' vs = differIn vs xs >>= \case
Just x' -> pure (Just x', g')
Nothing -> dropRandom g' vs
dropRandom g' vs = do
let (ix, g'') = randomR (0, Set.size vs - 1) g'
(before, after) = Set.splitAt ix vs
dropUntilSolvable g'' (before <> Set.drop 1 after)
-- look for a solution in which the given variables differ from the given solutions, without keeping that requirement
-- afterwards.
differIn :: Set.Set (Some Variable) -> [Valuation] -> SMTQ (Maybe Valuation)
differIn vs xs = do
push
addAssertionsQ [ isNot v | x <- xs, v@(var :=> _) <- DMap.assocs $ runValuation x, Some var `elem` vs ]
outcome <- getSolvable
x' <- case outcome of
Sat -> Just <$> getSolution vars
_ -> pure Nothing
pop
pure x'
-- variables that can only have one value are never required to differ
hasMultipleValues :: Some Variable -> Bool
hasMultipleValues (Some var) = case varType var of
E.UnitType -> False
_ -> True
atleastoneisdifferent :: Valuation -> SymGuard
atleastoneisdifferent = foldr ((E..||) . isNot) E.sFalse . DMap.assocs . runValuation
-- for doubles, rationals and reals, enforce a distance of at least 0.1
isNot :: DSum Variable E.Constant -> Expr Bool
isNot (var :=> (E.Constant val)) = E.sNot $ Expr $ sortOfEqualWith True 0.1 (E.Var var) (E.Const val)