如何使用 Data.SBV 来帮助推导出正确的栈机实现？
How to use Data.SBV to help derive correct stack machine implementation?
Graham Hutton，在 Programming in Haskell 的第 2 版中，最后 2 章的主题是 stack machine 基于 AST 的实现。
最后，他展示了如何从 AST 的 语义模型 推导 该机器的正确实现。
我试图在推导过程中寻求 Data.SBV 的帮助，但失败了。
我希望有人能帮助我了解我是否：
- 要求
Data.SBV做不到的事情，或者
- 向
Data.SBV 询问它 可以 做的事情，但询问不正确。
-- test/sbv-stack.lhs - Data.SBV assisted stack machine implementation derivation.
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
import qualified Data.SBV.List as L
import Data.SBV.List ((.:), (.++)) -- Since they don't collide w/ any existing list functions.
-- AST Definition
data Exp = Val SWord8
| Sum Exp Exp
-- Our "Meaning" Function
eval :: Exp -> SWord8
eval (Val x) = x
eval (Sum x y) = eval x + eval y
type Stack = SList Word8
-- Our "Operational" Definition.
--
-- This function attempts to implement the *specification* provided by our
-- "meaning" function, above, in a way that is more conducive to
-- implementation in our available (and, perhaps, quite primitive)
-- computational machinery.
--
-- Note that we've (temporarily) assumed that this machinery will consist
-- of some form of *stack-based computation engine* (because we're
-- following Hutton's example).
--
-- Note that we give the *specification* of the function in the first
-- (commented out) line of the definition. The derivation of the actual
-- correct definition from this specification is detailed in Ch. 17 of
-- Hutton's book.
eval' :: Exp -> Stack -> Stack
-- eval' e s = eval e : s -- our "specification"
eval' (Val n) s = push n s -- We're defining this one manually.
where
push :: SWord8 -> Stack -> Stack
push n s = n .: s
eval' (Sum x y) s = add (eval' y (eval' x s))
where
add :: Stack -> Stack
add = uninterpret "add" s -- This is the function we're asking to be derived.
-- Now, let's just ask SBV to "solve" our specification of `eval'`:
spec :: Goal
spec = do x :: SWord8 <- forall "x"
y :: SWord8 <- forall "y"
-- Our spec., from above, specialized to the `Sum` case:
constrain $ eval' (Sum (Val x) (Val y)) L.nil .== eval (Sum (Val x) (Val y)) .: L.nil
我们得到：
λ> :l test/sbv-stack.lhs
[1 of 1] Compiling Main ( test/sbv-stack.lhs, interpreted )
Ok, one module loaded.
Collecting type info for 1 module(s) ...
λ> sat spec
Unknown.
Reason: smt tactic failed to show goal to be sat/unsat (incomplete quantifiers)
发生了什么事？！
好吧，也许，要求 SBV 解决除 predicate（即 - a -> Bool）以外的任何问题都不起作用？
这里的根本问题是您混合了 SMTLib 的序列逻辑和量词。结果证明这个问题对于 SMT 求解器来说太难处理了。如果您将自己限制在基本逻辑上，那么这种函数综合确实是可能的。 （位向量、整数、实数。）但是将序列添加到混合中会将其放入不可判定的片段中。
这并不意味着 z3 无法合成您的 add 函数。也许未来的版本可能能够处理它。但在这一点上，你是在启发式的摆布之下。要了解原因，请注意您要求求解器综合以下定义：
add :: Stack -> Stack
add s = v .: s''
where (a, s') = L.uncons s
(b, s'') = L.uncons s'
v = a + b
虽然这看起来相当无辜和简单，但它需要超出 z3 当前能力的能力。总的来说，z3 目前可以合成仅对具体元素做出有限数量选择的函数。但是，如果输出取决于输入的每个选择的输入，则无法这样做。 （将其视为案例分析生成引擎：它可以想出一个将某些输入映射到其他输入的函数，但无法确定是否应该增加某些东西或必须添加两个东西。这来自有限模型中的工作寻找理论，并且超出了这个答案的范围！有关详细信息，请参见此处：https://arxiv.org/abs/1706.00096)
SBV 和 SMT 解决这类问题的一个更好的用例是实际告诉它 add 函数是什么，然后使用 Hutton 的策略证明某些给定程序是正确的 "compiled" .请注意，我明确说的是 "given" 程序：为任意程序建模和证明这一点也非常困难，但对于给定的固定程序，您可以很容易地做到这一点。如果你有兴趣证明任意程序的对应关系，你真的应该看看 Isabelle、Coq、ACL2 等定理证明器；它可以处理归纳法，这是您无疑需要解决此类问题的一种证明技术。请注意，SMT 求解器通常无法执行归纳。 （您可以使用电子匹配来模拟一些归纳法，例如证明，但这充其量只是一种拼凑，而且通常无法维护。）
这是你的例子，编码证明 \x -> \y -> x + y 程序是 "correctly" 编译和执行的参考语义：
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
import qualified Data.SBV.List as L
import Data.SBV.List ((.:))
-- AST Definition
data Exp = Val SWord8
| Sum Exp Exp
-- Our "Meaning" Function
eval :: Exp -> SWord8
eval (Val x) = x
eval (Sum x y) = eval x + eval y
-- Evaluation by "execution"
type Stack = SList Word8
run :: Exp -> SWord8
run e = L.head (eval' e L.nil)
where eval' :: Exp -> Stack -> Stack
eval' (Val n) s = n .: s
eval' (Sum x y) s = add (eval' y (eval' x s))
add :: Stack -> Stack
add s = v .: s''
where (a, s') = L.uncons s
(b, s'') = L.uncons s'
v = a + b
correct :: IO ThmResult
correct = prove $ do x :: SWord8 <- forall "x"
y :: SWord8 <- forall "y"
let pgm = Sum (Val x) (Val y)
spec = eval pgm
machine = run pgm
return $ spec .== machine
当我 运行 这个时，我得到：
*Main> correct
Q.E.D.
而且证明几乎不需要时间。您可以通过添加其他运算符、绑定形式、函数调用来轻松扩展它，如果您愿意，整个过程都可以。只要你坚持一个固定的 "program" 进行验证，它应该就可以了。
如果你犯了错误，比方说通过减法定义add（将它的最后一行修改为ready v = a - b），你会得到：
*Main> correct
Falsifiable. Counter-example:
x = 32 :: Word8
y = 0 :: Word8
我希望这能让您了解 SMT 求解器的当前功能，以及如何通过 SBV 将它们用于 Haskell。
程序综合是一个活跃的研究领域，有许多自定义技术和工具。开箱即用的 SMT 求解器不会让您到达那里。但是，如果您确实在 Haskell 中构建了这样一个自定义系统，则可以使用 SBV 访问底层 SMT 求解器来解决在此过程中必须处理的许多约束。
(旁白： SBV 包附带了一个扩展示例，其本质相似但目标不同：https://hackage.haskell.org/package/sbv-8.5/docs/Documentation-SBV-Examples-Strings-SQLInjection.html。该程序展示了如何使用 SBV和 SMT 求解器在理想化的 SQL 实现中找到 SQL 注入漏洞。这在这里可能会引起一些兴趣，并且更符合 SMT 求解器在实践中的典型使用方式。）
Graham Hutton，在 Programming in Haskell 的第 2 版中，最后 2 章的主题是 stack machine 基于 AST 的实现。 最后，他展示了如何从 AST 的 语义模型 推导 该机器的正确实现。
我试图在推导过程中寻求 Data.SBV 的帮助，但失败了。
我希望有人能帮助我了解我是否：
- 要求
Data.SBV做不到的事情，或者 - 向
Data.SBV询问它 可以 做的事情，但询问不正确。
-- test/sbv-stack.lhs - Data.SBV assisted stack machine implementation derivation.
{-# LANGUAGE OverloadedLists #-}
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
import qualified Data.SBV.List as L
import Data.SBV.List ((.:), (.++)) -- Since they don't collide w/ any existing list functions.
-- AST Definition
data Exp = Val SWord8
| Sum Exp Exp
-- Our "Meaning" Function
eval :: Exp -> SWord8
eval (Val x) = x
eval (Sum x y) = eval x + eval y
type Stack = SList Word8
-- Our "Operational" Definition.
--
-- This function attempts to implement the *specification* provided by our
-- "meaning" function, above, in a way that is more conducive to
-- implementation in our available (and, perhaps, quite primitive)
-- computational machinery.
--
-- Note that we've (temporarily) assumed that this machinery will consist
-- of some form of *stack-based computation engine* (because we're
-- following Hutton's example).
--
-- Note that we give the *specification* of the function in the first
-- (commented out) line of the definition. The derivation of the actual
-- correct definition from this specification is detailed in Ch. 17 of
-- Hutton's book.
eval' :: Exp -> Stack -> Stack
-- eval' e s = eval e : s -- our "specification"
eval' (Val n) s = push n s -- We're defining this one manually.
where
push :: SWord8 -> Stack -> Stack
push n s = n .: s
eval' (Sum x y) s = add (eval' y (eval' x s))
where
add :: Stack -> Stack
add = uninterpret "add" s -- This is the function we're asking to be derived.
-- Now, let's just ask SBV to "solve" our specification of `eval'`:
spec :: Goal
spec = do x :: SWord8 <- forall "x"
y :: SWord8 <- forall "y"
-- Our spec., from above, specialized to the `Sum` case:
constrain $ eval' (Sum (Val x) (Val y)) L.nil .== eval (Sum (Val x) (Val y)) .: L.nil
我们得到：
λ> :l test/sbv-stack.lhs
[1 of 1] Compiling Main ( test/sbv-stack.lhs, interpreted )
Ok, one module loaded.
Collecting type info for 1 module(s) ...
λ> sat spec
Unknown.
Reason: smt tactic failed to show goal to be sat/unsat (incomplete quantifiers)
发生了什么事？！
好吧，也许，要求 SBV 解决除 predicate（即 - a -> Bool）以外的任何问题都不起作用？
这里的根本问题是您混合了 SMTLib 的序列逻辑和量词。结果证明这个问题对于 SMT 求解器来说太难处理了。如果您将自己限制在基本逻辑上，那么这种函数综合确实是可能的。 （位向量、整数、实数。）但是将序列添加到混合中会将其放入不可判定的片段中。
这并不意味着 z3 无法合成您的 add 函数。也许未来的版本可能能够处理它。但在这一点上，你是在启发式的摆布之下。要了解原因，请注意您要求求解器综合以下定义：
add :: Stack -> Stack
add s = v .: s''
where (a, s') = L.uncons s
(b, s'') = L.uncons s'
v = a + b
虽然这看起来相当无辜和简单，但它需要超出 z3 当前能力的能力。总的来说，z3 目前可以合成仅对具体元素做出有限数量选择的函数。但是，如果输出取决于输入的每个选择的输入，则无法这样做。 （将其视为案例分析生成引擎：它可以想出一个将某些输入映射到其他输入的函数，但无法确定是否应该增加某些东西或必须添加两个东西。这来自有限模型中的工作寻找理论，并且超出了这个答案的范围！有关详细信息，请参见此处：https://arxiv.org/abs/1706.00096)
SBV 和 SMT 解决这类问题的一个更好的用例是实际告诉它 add 函数是什么，然后使用 Hutton 的策略证明某些给定程序是正确的 "compiled" .请注意，我明确说的是 "given" 程序：为任意程序建模和证明这一点也非常困难，但对于给定的固定程序，您可以很容易地做到这一点。如果你有兴趣证明任意程序的对应关系，你真的应该看看 Isabelle、Coq、ACL2 等定理证明器；它可以处理归纳法，这是您无疑需要解决此类问题的一种证明技术。请注意，SMT 求解器通常无法执行归纳。 （您可以使用电子匹配来模拟一些归纳法，例如证明，但这充其量只是一种拼凑，而且通常无法维护。）
这是你的例子，编码证明 \x -> \y -> x + y 程序是 "correctly" 编译和执行的参考语义：
{-# LANGUAGE ScopedTypeVariables #-}
import Data.SBV
import qualified Data.SBV.List as L
import Data.SBV.List ((.:))
-- AST Definition
data Exp = Val SWord8
| Sum Exp Exp
-- Our "Meaning" Function
eval :: Exp -> SWord8
eval (Val x) = x
eval (Sum x y) = eval x + eval y
-- Evaluation by "execution"
type Stack = SList Word8
run :: Exp -> SWord8
run e = L.head (eval' e L.nil)
where eval' :: Exp -> Stack -> Stack
eval' (Val n) s = n .: s
eval' (Sum x y) s = add (eval' y (eval' x s))
add :: Stack -> Stack
add s = v .: s''
where (a, s') = L.uncons s
(b, s'') = L.uncons s'
v = a + b
correct :: IO ThmResult
correct = prove $ do x :: SWord8 <- forall "x"
y :: SWord8 <- forall "y"
let pgm = Sum (Val x) (Val y)
spec = eval pgm
machine = run pgm
return $ spec .== machine
当我 运行 这个时，我得到：
*Main> correct
Q.E.D.
而且证明几乎不需要时间。您可以通过添加其他运算符、绑定形式、函数调用来轻松扩展它，如果您愿意，整个过程都可以。只要你坚持一个固定的 "program" 进行验证，它应该就可以了。
如果你犯了错误，比方说通过减法定义add（将它的最后一行修改为ready v = a - b），你会得到：
*Main> correct
Falsifiable. Counter-example:
x = 32 :: Word8
y = 0 :: Word8
我希望这能让您了解 SMT 求解器的当前功能，以及如何通过 SBV 将它们用于 Haskell。
程序综合是一个活跃的研究领域，有许多自定义技术和工具。开箱即用的 SMT 求解器不会让您到达那里。但是，如果您确实在 Haskell 中构建了这样一个自定义系统，则可以使用 SBV 访问底层 SMT 求解器来解决在此过程中必须处理的许多约束。
(旁白： SBV 包附带了一个扩展示例，其本质相似但目标不同：https://hackage.haskell.org/package/sbv-8.5/docs/Documentation-SBV-Examples-Strings-SQLInjection.html。该程序展示了如何使用 SBV和 SMT 求解器在理想化的 SQL 实现中找到 SQL 注入漏洞。这在这里可能会引起一些兴趣，并且更符合 SMT 求解器在实践中的典型使用方式。）