SMTLIB2 / Z3 中的多态函数

Question

我的理解是否正确，不能在 Z3 或 SMTLIB2 中创建 "polymorphic" 函数？例如我想写这样的东西：

(declare-fun Prop (A) Bool)
(declare-fun x1   ()  Int)
(declare-fun x2   ()  Bool)
(assert (and (Prop x1) (Prop x2)))

（我想我可以通过为 Int + Bool 然后使 Prop 为联合类型工作，但想要首先仔细检查一下直接使用参数多态是不可能的？）

谢谢！

Answer 1

确实是这样。 SMTLib 使用多排序的一阶逻辑；所以在你的例子中 A 可以是任何类型，但它必须是已知的类型；不是类型参数。

话虽如此，SMTLib 确实允许未解释的排序；也就是说，您可以在没有底层表示的情况下引入新的种类。（就像未解释的函数一样。）然后，您可以使用这种注入函数，并模拟您想要的东西。（我知道，不好的双关语。）

这是一个示例，您可以如何使用您最喜欢的语言 Ranjit 执行此操作： https://gist.github.com/LeventErkok/163362a59060188f5e62

当运行时，它会生成以下 SMT-Lib 代码，其中显示了您需要自己生成的内容，给予或接受：https://gist.github.com/LeventErkok/920aba57cf8cb1810b4a

下面是那个例子的 Haskell 输出：

Satisfiable. Model: x1 = 0 :: SInteger x2 = False

当然，您可以花点心思查询 SMT 求解器，以获取对构造过程中使用的未解释函数的解释；但其中 none 由 SMTLib 原生支持。尽管 Z3 会给你一个模型，如果你问得好，并且如果你愿意解析有点晦涩和不幸的非标准输出。这是这个例子：https://gist.github.com/LeventErkok/54cee74eb3def22dfb5f

另请注意，您通常需要在注入时给出某些公理；就像它们是一对一的并且彼此不相交；这在 SMTLib 中也是可能的，尽管通常这些将需要量词，因此可能会导致求解器响应 "unknown"，因为您进入了半可判定区域。

SMTLIB2 / Z3 中的多态函数

Polymorphic Functions in SMTLIB2 / Z3

smt

z3