Dafny 谓词 isBinarySearchTree

Question

我必须在 Dafny 中写一点 BST（二叉搜索树）class。
我从 Dafny 开始，然后写一个 class，插入方法是最简单的部分。

我多次尝试编写一个递归谓词，它可以检查作为参数传递的树是否是 BST（没有平衡条件，一个简单的二叉树遵循规则 left.value < node.value && right.value > node.value).

我在另一个 Whosebug post 中找到了一种在谓词中传递函数的方法，主要的递归检查在函数中，但它似乎不起作用。

错误基本上是'A pre-condition for this call might not hold'.
这是代码：

datatype Tree = Nil | Node(left: Tree, value: int, right: Tree)

class TreeADT{  

    function isBST(tree: Tree): bool
        decreases tree
    {
        match tree
        case Nil => true
        case Node(_,_,_) =>
            (tree.left == Nil || tree.left.value < tree.value) 
            && (tree.right == Nil || tree.right.value > tree.value) 
            && isBST(tree.left) && isBST(tree.right)
    }

    predicate isBinarySearchTree(tree: Tree)
    {
        isBST(tree)
    }
    
    method insert(tree: Tree, value: int) returns (toAdd: Tree) //maybe remove
        requires isBinarySearchTree(tree) 
        decreases tree;
        // ensures isBinarySearchTree(toAdd) //same error appear here
    {
        if(tree == Nil) {return Node(Nil, value, Nil);}
        else{
            if(value == tree.value) {return tree;}
            var temp: Tree;
            if(value < tree.value){
                temp := insert(tree.left, value);
                toAdd := Node(temp, tree.value, tree.right);
            }else{
                temp := insert(tree.right, value);
                toAdd := Node(tree.left, tree.value, temp);
            }
            return toAdd;
        }
            
    }

    method printOrderedTree(tree:Tree)
        decreases tree
    {
        if tree == Nil {}
        else { 
            printOrderedTree(tree.left); 
            print tree.value, ", "; 
            printOrderedTree(tree.right);
        }
    }


    method Main() {
        var t := insert(Nil, 5);
        var u := insert(t, 2); // error on pre-condition here
        print t, "\n";
        print u, "\n";
        printOrderedTree(u);
        var b:bool := isBST(u);
    }
}

我也尝试完全在谓词中完成它，但递归检查似乎无论如何都不起作用。

有没有想法在谓词中进行递归检查而不是循环检查？

感谢阅读。

编辑：
根据詹姆斯的回答，我修改了我的代码

datatype Tree = Nil | Node(left: Tree, value: int, right: Tree)

predicate isBinarySearchTree(tree: Tree)
    decreases tree
{
    match tree
    case Nil => true
    case Node(_,_,_) =>
        (tree.left == Nil || tree.left.value < tree.value) 
        && (tree.right == Nil || tree.right.value > tree.value) 
        && isBinarySearchTree(tree.left) && isBinarySearchTree(tree.right)
        && treeMin(tree.value, tree.right) && treeMax(tree.value, tree.left)
}

predicate treeMax(max: int, tree: Tree)
    decreases tree
{
    match tree
    case Nil => true
    case Node(left,v,right) => (max > v) && treeMax(max, left) && treeMax(max, right)
}

predicate treeMin(min: int, tree:Tree)
    decreases tree
{
    match tree
    case Nil => true
    case Node(left,v,right) => (min < v) && treeMin(min, left) && treeMin(min, right)
}

method insert(tree: Tree, value: int) returns (toAdd: Tree) //maybe remove
    requires isBinarySearchTree(tree) 
    decreases tree;
    ensures isBinarySearchTree(toAdd)
{
    if(tree == Nil) {return Node(Nil, value, Nil);}
    else{
        if(value == tree.value) {return tree;}
        var temp: Tree;
        if(value < tree.value){
            temp := insert(tree.left, value);
            toAdd := Node(temp, tree.value, tree.right);
        }else{
            temp := insert(tree.right, value);
            toAdd := Node(tree.left, tree.value, temp);
        }
        return toAdd;
    }
        
}

method printOrderedTree(tree:Tree)
    decreases tree
{
    if tree == Nil {}
    else { 
        printOrderedTree(tree.left); 
        print tree.value, ", "; 
        printOrderedTree(tree.right);
    }
}


method Main() {
    var t := insert(Nil, 5);
    var u := insert(t, 2);
    print t, "\n";
    print u, "\n";
    u := insert(u, 1);
    u := insert(u, 3);
    u := insert(u, 7);
    u := insert(u, 6);
    u := insert(u, 4);
    printOrderedTree(u);
}

但是在requires和ensures语句中出现了同样的问题，我现在检查是否所有左边的值都较小，右边所有的值都较大，但是这个错误又出现了

A postcondition might not hold on this return path.

如果我注释掉 ensures 语句，我会收到以下错误：

A precondition for this call might not hold.

所有有建设性的想法和愚蠢的提示都会被仔细阅读。

谢谢。

Answer 1

您的代码存在几个问题。

(1) TreeADT class 的目的是什么？在 Dafny 中，classes 通常用于表示可变对象，但是你的 class 没有字段或 mutator 方法，你使用 datatype 来保存数据，所以你可以得到完全摆脱 class。

(2) 你对isBST的定义是错误的。这是一个例子：

method UhOh()
  ensures isBST(Node(Node(Nil, 3, Node(Nil, 7, Nil)), 5, Nil))
{}

这棵树不是二叉搜索树，因为7大于5，但是7在5的左子树中。但是你的定义允许这棵树。

(3) 你运行遇到的具体问题是Dafny无法证明Main中的变量t是二叉搜索树。我看到你把 insert 的后置条件注释掉了。为什么？您将需要该后置条件。

我也不确定“在谓词中传递函数”是什么意思。你有一个无用（虽然无害）的包装谓词 isBST。在 Dafny 中，单词 predicate 只不过是 function 的缩写，其 return 类型为 bool.

您编辑的代码看起来好多了。现在 insert 的这两个附加后置条件足以完成证明：

ensures forall x :: treeMin(x, tree) && x < value ==> treeMin(x, toAdd)
ensures forall x :: treeMax(x, tree) && x > value ==> treeMax(x, toAdd)

Answer 2

添加几个断言语句后，您可以看到 dafny 无法验证的内容。

   if (value < tree.value) {
        temp := insert(tree.left, value);
        toAdd := Node(temp, tree.value, tree.right);
        assert treeMax(tree.value, temp);
    }
    else {
        temp := insert(tree.right, value);
        toAdd := Node(tree.left, tree.value, temp);
        assert treeMin(tree.value, temp);
    }

Dafny 无法验证添加的断言保留。思考为什么 dafny 无法验证的方式是它抽象地看起来所有具有给定 pre 和 post 条件而忘记实现的方法。 insert 方法前提是输入是有效的二叉搜索树，post 条件是输出是有效的二叉树。因此，始终 return 在树下方的插入方法是有效的实现。

现在不难看出为什么当温度总是 Tree(Tree(Nil, 1, Nil), 3, Tree(Nil, 5, Nil)).

时 treeMax 或 treeMin 不成立

回顾一下更大的问题是 ensures 提供的输入树和输出树之间没有 link。

Dafny 谓词 isBinarySearchTree

Dafny predicate isBinarySearchTree

recursion

binary-search-tree

predicate

dafny