如何在 z3py 中的代数数据类型上定义 z3 函数（即递归函数）？

Question

我的目标是将队列定义为 z3 数据类型（在 z3py 中），以便我可以在队列上执行操作作为约束。有没有什么办法可以做到，有的话是什么？

自从我知道的三个教程提到它们以来，我的第一直觉是为此使用代数数据类型 (ADT)，通过递归函数定义，例如 OCaml 或 Haskell 中常见的函数定义.我找到了一些前段时间讨论 z3 中的 ADT 的帖子，例如 list concat in z3。其他帖子上的一些答案声称 z3 不支持递归，但接受的答案定义了一个与我想要的风格非常相似的函数，所以我不知道 right/up-to-date 答案是什么。

def queuegen(sort):
    Queue = Datatype('Queue_of_%s' % sort.name())
    Queue.declare('enqueue', ('last', sort), ('rest', Queue))
    Queue.declare('empty')
    Queue = Queue.create()
    x = Const('x',sort)
    q = Const('q', Queue)
    enqueue = Queue.enqueue
    dequeue = Function('dequeue', Queue, Queue)
    peek = Function('peek', Queue, sort)
    size = Function('size', Queue, IntSort())

# just showing my attempted recursive definition for size(q), 
# since no sense in worrying about the other functions if I can't do this
    sizedef = ForAll(q,If(q == Queue.empty, size(q) == 0,\
                     size(q) == 1 + size(Queue.rest(q))))

    return Queue, [enqueue,dequeue,peek,size], sizedef

当我将生成的 sizedef 约束添加到求解器并尝试检查它时，z3 没有完成。

Answer 1

队列、栈等本质上都是递归定义。编写您链接的答案时，SMTLib 不支持递归类型和函数声明。量化公理是获得这些东西的唯一机制，对底层求解器的详细支持没有太大希望。

好消息是标准已经发展，现在它规定了编写递归数据类型和函数的精确机制。请参阅 http://smtlib.cs.uiowa.edu/papers/smt-lib-reference-v2.6-r2017-07-18.pdf.

的第 4.2.3 节

不太好的消息是求解器支持仍然很弱。虽然 z3 会接受此类定义，但它不太可能真正证明有关此类结构的任何有趣定理。底线保持不变：证明递归函数的属性（比如你的 size）需要归纳，而 SMT 求解器根本没有归纳能力。量词模式和电子匹配只能带你走这么远，而且它们只适用于未解释的函数。长话短说，如果您想对此类结构进行推理，请使用适当的定理证明器。 SMT 求解器在这里不是正确的选择。如今，许多定理证明者无论如何都将 SMT 求解器称为神谕，因此您可以两全其美。（例如，查看 Isabelle Z3 集成。）

这里的另一个问题是您是否可以从 Python API 执行此操作。显然，正如您所发现的，他们添加了对定义递归数据类型的支持，但我不清楚他们是否还添加了适当的递归函数声明。答案很可能不是，但如果您发现其他情况，请告诉我们。

长话短说：如果要对递归数据类型和递归函数建模，请不要使用 SMT 求解器。只是用错了工具。

Answer 2

对于寻求解决类似问题的任何人，我没有找到使用 ADT 的方法（这很遗憾，因为它们更干净）。我通过维护三个变量定义了一个 queue：头部、尾部和从整数到值的函数。

既然你可以根据另一个函数定义一个z3函数，你可以使用一个函数映射到queue的元素，一个头来跟踪前面的索引，和一个尾巴来确定 queue 是否为空（head == tail）。当您 enqueue 时，您只需创建一个具有与尾部关联的正确值的新函数，然后递增尾部。当你 dequeue （可变）时，你只需使用 head 访问旧函数的值，然后递增 head （从现在开始忽略以前的索引）。

这比使用 ADT 更糟糕，因为您必须在没有语言帮助的情况下自己确保不变性，但它似乎确实可以完成工作。

如何在 z3py 中的代数数据类型上定义 z3 函数（即递归函数）？

How does one define z3 functions (namely recursive ones) on algebraic data types within z3py?

algebraic-data-types

z3

z3py