使用 Haskell 和 SBV 的列表理解条件

Question

我想写一个 Haskell 带有条件符号表达式 (SBV) 的列表理解。我用下面的小例子重现了这个问题。

import Data.SBV

allUs :: [SInteger] 
allUs = [0,1,2]  

f :: SInteger -> SBool 
f 0 = sTrue
f 1 = sFalse
f 2 = sTrue

someUs :: [SInteger] 
someUs = [u | u <- allUs, f u == sTrue]

with show someUs, 这给出了以下错误

*** Data.SBV: Comparing symbolic values using Haskell's Eq class!
***
*** Received:    0 :: SInteger  == 0 :: SInteger
*** Instead use: 0 :: SInteger .== 0 :: SInteger
***
*** The Eq instance for symbolic values are necessiated only because
*** of the Bits class requirement. You must use symbolic equality
*** operators instead. (And complain to Haskell folks that they
*** remove the 'Eq' superclass from 'Bits'!.)

CallStack (from HasCallStack):
  error, called at ./Data/SBV/Core/Symbolic.hs:1009:23 in sbv-8.8.5-IR852OLMhURGkbvysaJG5x:Data.SBV.Core.Symbolic

条件改成f u .== sTrue也报错

<interactive>:8:27: error:
    • Couldn't match type ‘SBV Bool’ with ‘Bool’
      Expected type: Bool
        Actual type: SBool
    • In the expression: f u .== sTrue
      In a stmt of a list comprehension: f u .== sTrue
      In the expression: [u | u <- allUs, f u .== sTrue]

如何解决这个问题？

Answer 1

你的 f 和你的 someUs 都不是书面的符号可计算的。理想情况下，这些应该是类型错误，立即被拒绝。这是因为符号值不能是 Eq class 的实例：为什么？因为确定符号值的相等性需要调用底层求解器；所以结果不能是Bool；真的应该是SBool。但是 Haskell 不允许模式匹配中的通用守卫允许这种可能性。（这也有充分的理由，所以这并不是 Haskell 的错。只是这两种编程风格不能很好地结合在一起。）

你可以问为什么 SBV 将符号值作为 Eq class 的实例。它是 Eq 实例的唯一原因是错误消息告诉您的内容：因为我们希望它们成为 Bits class 的实例；其中 Eq 作为 superclass 要求。但那完全是另一个讨论。

基于此，您如何在 SBV 中编写函数？以下是如何使用符号样式编写 f：

f :: SInteger -> SBool
f i = ite (i .== 0) sTrue
    $ ite (i .== 1) sFalse
    $ ite (i .== 2) sTrue
    $               sFalse   -- arbitrarily filled to make the function total

丑陋，但这是唯一的写法，除非你想玩一些类似引用的把戏。

关于someUs：这也不是你可以直接用符号写的东西：这被称为脊柱具体列表。如果不实际运行在单个元素上设置求解器，SBV 就无法知道结果列表的长度。通常，您不能在具有符号元素的具体脊柱列表上执行 filter 之类的函数。

解决方案是使用所谓的符号列表和有界列表抽象。这不是很令人满意，但这是避免终止问题的最佳方法：

{-# LANGUAGE OverloadedLists #-}

import Data.SBV
import Data.SBV.List
import Data.SBV.Tools.BoundedList

f :: SInteger -> SBool
f i = ite (i .== 0) sTrue
    $ ite (i .== 1) sFalse
    $ ite (i .== 2) sTrue
    $               sFalse   -- arbitrarily filled to make the function total

allUs :: SList Integer
allUs = [0,1,2]

someUs :: SList Integer
someUs = bfilter 10 f allUs

当我运行这个时，我得到：

*Main> someUs
[0,2] :: [SInteger]

但是你会问 bfilter 的电话号码 10 是多少？好吧，这个想法是假定所有列表的长度都有某种上限，并且 Data.SBV.Tools.BoundedList 导出了一堆方法来轻松处理它们；都采用绑定参数。只要输入最多达到这个长度，它们就会正常工作。如果您的列表长于给定的界限，则无法保证会发生什么。（一般来说，它会在边界处切断你的列表，但你不应该依赖这种行为。）

在 https://hackage.haskell.org/package/sbv-8.12/docs/Documentation-SBV-Examples-Lists-BoundedMutex.html

有一个与 BMC（有界模型检查）协调使用此类列表的示例

总而言之，由于 Haskell 中的限制（其中 Bool 是固定类型，因此在符号上下文中处理列表会带来一些建模成本以及您可以做多少class) 和底层求解器，它们不能很好地处理递归定义的函数。后者主要是由于这样的证明需要归纳，而 SMT 求解器不能开箱即用地进行归纳。但是，如果您使用类似 BMC 的想法遵循游戏规则，则可以在合理范围内处理问题的实际实例。

Answer 2

(.==) 需要 EqSymbolic、return 和 SBool 的两个实例。在列表理解中，条件是使用 guard 函数实现的。

这是它的样子：

guard :: Alternative f => Bool -> f ()
guard False = empty
guard True = pure ()

对于列表，empty 是 []，pure () return 是单例列表 [()]。计算结果为 False 的列表中的任何成员都将 return 一个空列表而不是一个单元项，将其从链中的计算中排除。

[True, False, True] >>= guard
= concatMap guard [True, False, True]
= concat $ map guard [True, False, True]
= concat $ [[()], [], [()]]
= [(), ()]

当上下文被展平时第二个分支被排除，因此它从计算中被“修剪”。

这里似乎有两个问题 - 当您在 f 中进行模式匹配时，您正在使用 Eq class 进行比较。这就是 SBV 错误的来源。由于您的值靠得很近，您可以使用 select，它接受一个项目列表、一个默认值、一个计算结果为索引的表达式，并尝试从该列表中获取第 index 个项目。

您可以将 f 重写为

f :: SInteger -> SBool
f = select [sTrue, sFalse, sTrue] sFalse

第二个问题是守卫明确寻找 Bool，但 (.==) 仍然 return 是 SBool。查看 Data.SBV，您应该能够使用 unliteral 将其强制转换为常规 Bool，它会尝试将 SBV 值解包为等效的 Haskell 值.

fromSBool :: SBool -> Bool
fromSBool = fromMaybe False . unliteral

someUs :: [SInteger]
someUs = [u | u <- allUs, fromSBool (f u)]
-- [0 :: SInteger, 2 :: SInteger]

使用 Haskell 和 SBV 的列表理解条件

Conditions on list comprehension using Haskell and SBV

haskell

sbv