Out-of-bounds `select` even though I `constrain` the index

Question

I have a static-length list of values ks :: [SInt16] and an index x :: SInt16. I'd like to index into the list using x:

(.!) :: (Mergeable a) => [a] -> SInt16 -> a
xs .! i = select xs (error "(.!) : out of bounds") i

I would expect to be able to use (.!) with a sufficiently constrained x like this:

sat $ do
    let ks = [1, 3, 5, 2, 4]      

    x <- sInt16 "x"
    constrain $ 0 .<= x .&& x .< literal (fromIntegral $ length ks)

    let y = ks .! x
    return $ y .< x

However, this fails with the error coming from (.!).

Of course, in my real program, I use (.!) all over the place in locations where there is no suitable default value to use in select. How can I index into a list with a constrained-to-be-in-bounds index?

score 3 · Accepted Answer · answered Jul 02 '20 at 05:00

Simple solution

select is fully expanded by SBV during symbolic execution, hence you do have to provide a proper default value, as you found out. So, if you do want to use select you have to come up with an actual value there.

To address your immediate need, I'd suggest simply defining:

(.!) :: (Mergeable a) => [a] -> SInt16 -> a
[]       .! _ = error "(.!): Empty list!"
xs@(x:_) .! i = select xs x i

So long as you make sure you have asserted enough constraints on i, this should work just fine.

A slightly better approach

The above requires your user to keep track of proper constraints on the index variable, and this can get rather hairy. A simple trick to use in these cases is to use a "smart" constructor instead. First define:

import Data.SBV

mkIndex :: SIntegral b => String -> [a] -> Symbolic (SBV b)
mkIndex nm lst = do i <- free nm
                    constrain $ 0 .<= i .&& i .< literal (fromIntegral (length lst))
                    pure i

(.!) :: (Mergeable a) => [a] -> SInt16 -> a
[]       .! _ = error "(.!): Empty list!"
xs@(x:_) .! i = select xs x i

Now you can say:

p = sat $ do let ks = [1, 3, 5, 2, 4]

             x <- mkIndex "x" ks

             let y = ks .! x
             return $ y .< x

This is just a bit more verbose than your original (as you need to pass the list you want to index into), but it can save a lot of headaches down the road. Furthermore, you can change your mkIndex to put diagnostics, or assert further constraints as needed.

A more defensive approach

The "better" approach above requires you to know in advance the length of the list you'll be indexing into. This is obvious in your example, but I can imagine situations where that information will not be readily available. If that is the case, I'd recommend actually creating a symbolic value for the out-of-bounds access element, and tracking that explicitly yourself. This is more complicated, but you can hide most of it behind a simple data-type. Something like:

{-# LANGUAGE ScopedTypeVariables #-}

import Data.SBV

newtype Index a b = Index (SBV a, SBV b)

mkIndex :: (SymVal a, SymVal b) => String -> Symbolic (Index a b)
mkIndex nm = do def <- free $ nm ++ "_access_out_of_bounds_value"
                idx <- free nm
                pure $ Index (def, idx)

(.!) :: (SymVal a, SIntegral b) => [SBV a] -> Index a b -> SBV a
xs .! Index (i, i') = select xs i i'

Now assume you try to do a sat, but put in incorrect constraints on your index:

p = sat $ do let ks = [1, 3, 5, 2, 4]

             xi@(Index (_, x)) :: Index Int16 Int16 <- mkIndex "x"

             -- incorrectly constrain x here to do out-of-bounds
             constrain $ x .> 10

             let y = ks .! xi

             pure $ y .< x

You'll get:

*Main> p
Satisfiable. Model:
  x_access_out_of_bounds_value =     0 :: Int16
  x                            = 16386 :: Int16

This way, you can see that something went wrong, and what value the solver picked to satisfy the access-out-of-bounds case.

Summary

Which approach you take really depends on your actual needs. But I'd recommend going for at least the second alternative if possible, as an SMT solver can always "cleverly" pick values to give you unexpected models. You'd have protected yourself against at least the most obvious bugs that way. In a production system, I'd insist on the third approach, as debugging bugs that arise due to complicated constraints can be rather difficult in practice. The more "tracking" variables you leave for yourself, the better.

Out-of-bounds `select` even though I `constrain` the index

1 Answers1

Simple solution

A slightly better approach

A more defensive approach

Summary