越界 `select` 即使我 `constrain` 索引

Question

我有一个静态长度值列表 ks :: [SInt16] 和一个索引 x :: SInt16。我想使用 x:

索引到列表中

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

我希望能够像这样使用具有足够约束的 x 的 (.!)：

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

但是，这失败了，错误来自 (.!)。

当然，在我的真实程序中，我在 select 中没有合适的默认值的地方到处使用 (.!)。 我怎样才能索引到具有限制在边界索引的列表中？

Answer 1

简单的解决方案

select 在符号执行期间由 SBV 完全扩展，因此您必须提供适当的默认值，正如您所发现的。所以，如果你确实想使用 select，你必须在那里给出一个实际值。

为了满足您的迫切需求，我建议您简单地定义：

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

只要您确保对 i 施加了足够的约束，这应该可以正常工作。

稍微好一点的方法

以上要求您的用户跟踪对索引变量的适当约束，这可能会变得相当棘手。在这些情况下使用的一个简单技巧是改用“智能”构造函数。首先定义：

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

现在你可以说：

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

             x <- mkIndex "x" ks

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

这只是比您原来的要冗长一点（因为您需要传递要索引的列表），但它可以避免很多麻烦。此外，您可以更改 mkIndex 以进行诊断，或根据需要声明进一步的约束。

更具防御性的方法

上述“更好”的方法要求您提前知道要索引的列表的长度。这在您的示例中很明显，但我可以想象这些信息不容易获得的情况。如果是这种情况，我建议实际为越界访问元素创建一个符号值，并自己明确地跟踪它。这更复杂，但您可以将其中的大部分隐藏在一个简单的数据类型后面。类似于：

{-# 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'

现在假设您尝试执行 sat，但对您的索引设置了不正确的约束：

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

您将获得：

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

这样，您可以看到出了什么问题，以及求解器选择了什么值来满足访问越界的情况。

总结

具体采用哪种方法取决于您的实际需要。但如果可能的话，我建议至少选择第二种选择，因为 SMT 求解器总是可以“巧妙地”选择值来为您提供意想不到的模型。您至少可以通过这种方式保护自己免受最明显的错误的侵害。在生产系统中，我会坚持使用第三种方法，因为调试由于复杂约束而出现的错误在实践中可能相当困难。给自己留的“跟踪”变量越多越好。

越界 `select` 即使我 `constrain` 索引

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

haskell

smt

sbv

symbolic-execution

简单的解决方案

稍微好一点的方法

更具防御性的方法

总结