使用函数在 z3 中创建列表

Question

我正在尝试将这段伪代码转换为 SMT-LIB 语言，但我卡住了。

List function my_fun(int x)
{
    list = nil
    for(i in 1 to x):
        if(some_condition_on_i)
            list.concat(i)
    return list
}

到目前为止我所做的是：

(declare-const l1 (List Int))
(define-fun my_fun ((x Int)) (List Int)
    (forall ((t Int))
        (ite (and (some_condition_on_t) (< t x)) (insert t l1) l1 )
        )
    )
)

我知道这是错误的，而且不起作用。你能帮我理解我该怎么做吗？

Answer 1

SMT-LIB 模型逻辑，其中变量总是不可变的；另一方面，您的代码似乎是命令式的，即 list 和 i 等变量是可变的。这一关键差异将是编码程序的最大挑战，而对命令式程序进行推理的挑战激发了研究工具，例如 Dafny, Boogie, or Viper

这里有几点建议：

(insert t l1)表示一个新列表，将t插入l1得到。它将不会修改l1（并且无法修改l1，因为它是一个逻辑变量）
逻辑 forall 是一个布尔公式（计算结果为 true 或 false），它不是您可以执行的语句（例如，因为它的副作用）

如果 x 的值是静态已知的（即如果它是 5），那么你可以展开循环（这里是伪代码）：

l0 := Nil
l1 := ite(condition(1), insert(1, l0), l0)
l2 := ite(condition(2), insert(2, l1), l1)
...
l4 := ite(condition(4), insert(4, l3), l3)

如果 x 的值不是静态已知的，那么您很可能需要 循环不变量 或使用 修复点 为了解释未知次数的循环迭代

使用函数在 z3 中创建列表

Creating List in z3 using function

smt

z3