Dafny 支持 "proof by construction" 吗？

Question

假设我有一个计算某些东西的方法：

method Difference(a: nat, b: nat) returns (c: nat)
  ensures a + c == b || b + c == a
{
  ...
}

暂时不要管实施。如果我 can 在 Dafny 中实现这个方法，这意味着对于所有可能的参数 a 和 b，必须有一些 return 值 c 满足后置条件。

换句话说，方法的主体是构造性证明，即：

forall a: nat, b: nat :: exists c: nat ::
  a + c == b || b + c == a

但是Dafny is not convinced:

method Difference(a: nat, b: nat) returns (c: nat)
  ensures a + c == b || b + c == a
{
  c := if a > b then a - b else b - a;
}

method Main() {
  assert forall a: nat, b: nat :: exists c: nat ::  // error: assertion violation :(
    a + c == b || b + c == a;
}

有没有办法在 Dafny 中使用这种推理？

Answer 1

这就是诀窍：将属性包装在谓词中，并在引理中证明 exists，这样你就可以用 assert 提示验证者。

也许还有一些方法可以在 forall 中进行提示。

predicate difference_property(a: nat, b: nat, c: nat)
{
    a + c == b || b + c == a
}

function difference(a: nat, b: nat): nat
{
    if a > b then a - b else b - a
}

lemma main(a: nat, b: nat)
    ensures exists c: nat :: difference_property(a, b, c)
{
    var c := difference(a, b);
    assert difference_property(a, b, c);
}

Answer 2

对于通过引理证明存在的情况，Valéry 的回答是一个很好的技巧。您还可以使用 Dafny 的 forall 语句将技巧扩展到 "hint inside a forall"，像这样

forall a: nat, b: nat
    ensures exists c: nat :: difference_property(a, b, c)
{
    var c := difference(a, b);
    assert difference_property(a, b, c);
}

证明了 forall 表达式

forall a: nat, b: nat :: 
    exists c: nat :: 
        difference_property(a, b, c)

对于Jason的另一个关于在证明中使用正确方法的问题，Dafny不支持。事实上，我认为不支持它是有道理的，因为方法可以对堆产生影响，例如。因此，某些见证的构建原则上可能取决于分配状态甚至修改现有状态。将这种效果内化到逻辑中是可疑的，会改变 Dafny 的本性。

Dafny 支持 "proof by construction" 吗？

Does Dafny support "proof by construction"?

proof

dafny