Z3 中的 Curried 函数和函数应用

Question

我正在研究一种与 STLC 非常相似的语言，我正在将其转换为 Z3 命题，因此有一些关于 Z3 如何处理（未解释的）函数的（子）问题：

函数在我的语言中是自然柯里化的，并且当我递归地转换我的语言的术语时，我希望也能够递归地构建相应的 Z3 AST。也就是说，当我有一个术语 f x y 时，我想首先将 f 应用于 x，然后将其应用于 y。有没有办法做到这一点？到目前为止我发现的 API (Z3_mk_func_decl/Z3_mk_app) 似乎要求我先收集所有参数并一次应用它们。
是否有合理的方式来表示类似 (if b then f else g) x 的内容？

在这两种情况下，我完全可以接受未解释的函数并将推理限制为“b = True /\ f x = 0 => (if b then f else g) x = 0 成立”之类的事情。

Answer 1

SMTLib（如http://smtlib.cs.uiowa.edu/papers/smt-lib-reference-v2.6-r2017-07-18.pdf中所述）是一种多排序的一阶逻辑。所有函数（未解释或未解释）都必须应用于其所有参数，并且您不能有任何形式的柯里化。此外，您不能执行更高阶的 if-then-else，即 if-then-else 的分支必须是一阶值。（但是，它们可以是数组，您可以想象用数组“伪造”函数。但这不是重点。）

应该注意的是，SMTLib (v3) 的下一次迭代将基于高阶逻辑，届时您所要求的功能可能会可用。参见：http://smtlib.cs.uiowa.edu/version3.shtml。当然，这仍然是一个提议，需要一段时间才能确定下来，真正的解决者才能开始忠实地实施它。最终这会发生，但我不希望在短期内发生。

旁白：既然你提到了 STLC（简单类型 lambda 演算），我想你可能熟悉像 Haskell 这样的函数式语言。如果是这种情况，您可能需要考虑使用 SBV：https://hackage.haskell.org/package/sbv。它通过在幕后仔细地将它们翻译出来，为完成其中一些事情提供了一个框架。这是一个例子：

Prelude Data.SBV> sat $ \b -> (ite b (uninterpret "f") (uninterpret "g")) (0::SInteger) .== (0::SInteger)
Satisfiable. Model:
  s0 = True :: Bool

  f :: Integer -> Integer
  f _ = 0

  g :: Integer -> Integer
  g _ = 2

这里我们创建了两个函数并使用 ite 构造来“合并”它们；并让求解器 return 给我们一个模型。在幕后，SBV 将完全饱和这些应用程序，让您“假装”您正在以更高阶的方式进行编程，就像在 STLC 或 Haskell 中一样。当然，细节决定成败，这种方法也有局限性，但是在 Haskell 中对 STLC 进行建模是许多人的经典消遣，使用 SBV 进行象征性的建模可能是一个有趣的练习。

Z3 中的 Curried 函数和函数应用

Curried functions and function application in Z3

z3