Efficient way to "keep turning the crank" on a stateful computation

Question

I have a stateful process that is modelled as an i -> RWS r w s a. I want to feed it an input cmds :: [i]; currently I do that wholesale:

    let play = runGame theGame . go
          where
            go [] = finished
            go ((v, n):cmds) = do
                end1 <- stepWorld
                end2 <- ite (SBV.isJust end1) (return end1) $ stepPlayer (v, n)
                ite (SBV.isJust end2) (return end2) $ go cmds

I can try searching for an input of a predetermined size like this:

    result <- satWith z3{ verbose = True } $ do
        cmds <- mapM sCmd [1..inputLength]
        return $ SBV.fromMaybe sFalse $ fst $ play cmds

However, this gives me horrible performance in SBV itself, i.e. before Z3 is called (I can see that this is the case because the verbose output shows me the all the time is spent before the (check-sat) call). This is even with inputLength set to something small like 4.

However, with inputLength set to 1 or 2, the whole process is very snappy. So this makes me hope that there is a way to run SBV to get the model of the behaviour of a single step i -> s -> (s, a), and then tell the SMT solver to keep iterating that model for n different is.

So that is my question: in a stateful computation like this, where I want to feed SMT variables as input into the stateful computation, is there a way to let the SMT solver turn its crank to avoid the bad performance of SBV?

I guess a simplified "model question" would be if I have a function f :: St -> St, and a predicate p :: St -> SBool, and I want to solve for n :: SInt such that p (iterateN n f x0), what is the recommended way of doing that with SBV, supposing Mergeable St?

EDIT: I've uploaded the whole code to Github but bear in mind it is not a minimalized example; in fact it isn't even very nice Haskell code yet.

alias alias · Accepted Answer · 2020-07-03T14:47:38

Full symbolic execution

It's hard to opine without seeing full code we can execute. (Stack-overflow works the best when you post code segments people can actually run.) But some of the tell-tale signs of exponential complexity is creeping in your program. Consider the following segment you posted:

        go [] = finished
        go ((v, n):cmds) = do
                end1 <- stepWorld
                end2 <- ite (SBV.isJust end1) (return end1) $ stepPlayer (v, n)
                ite (SBV.isJust end2) (return end2) $ go cmds

This looks like a "linear" walk if you are programming with concrete values. But keep in mind that the ite construct has to "evaluate" both branches in each step. And you have a nested if: This is why you're getting an exponential slow down, with a factor of 4 in each iteration. As you observed, this gets out-of-hand pretty quickly. (One way to think about this is that SBV has to run all possible outcomes of those nested-if's in each step. You can draw the call-tree to see this grows exponentially.)

Without knowing the details of your stepWorld or stepPlayer it's hard to suggest any alternative schemes. But bottom line, you want to eliminate those calls to ite as much as possible, and push them as low in the recursive chain as you possibly can. Perhaps continuation-passing style can help, but it all depends on what the semantics of these operations are, and if you can "defer" decisions successfully.

Query mode

However, I do believe that a better approach for you to try would be to actually use SBV's query mode. In this mode, you do not symbolically simulate everything first before calling the solver. Instead, you incrementally add constraints to the solver, query for satisfiability, and based on the values you get you take different paths. I believe this approach would work the best in your situation, where you dynamically explore the "state space" but also make decisions along the way. There is an example of this in the documentation: HexPuzzle. In particular, the search function shows how you can navigate one-move-at-a-time, using the solver in the incremental mode (using push/pop).

I'm not exactly sure if this model of execution matches the logic in your game. Hopefully, it can at least give you an idea. But I've had good luck with the incremental approach in the past where you can explore such large search-spaces incrementally by avoiding having to make all of the choices before you send things to z3.

Efficient way to "keep turning the crank" on a stateful computation

1 Answers

Full symbolic execution

Query mode