如何在 Dafny 中产生无效的 LogicalExpression？

Question

考虑下面这个愚蠢的函数：

function method unpair(n: nat): (nat, nat)
{
  var x,y :| n == (x+y)*(x+y+1)/2 + y;
  return (x,y)
}

给定一些自然数 n，我想确定满足方程 (x+y)*(x+y+1)/2 + y 的 2 个自然数 x 和 y。这可以使用 Cantor 的配对函数，但不确定我是否有正确的语法，因为 dafny 抛出错误：return 行上的“invalid LogicalExpression”。我该如何解决这个错误？

Answer 1

A function method 是（可能令人困惑）一个 function，唯一的区别是允许从非幽灵上下文中调用它。在任何 function（包括 function methods）中，我们不需要在 Dafny 中说 return。相反，函数体只是我们想要 return 的表达式。所以你应该写

function method unpair(n: nat): (nat, nat)
{
  var x,y :| n == (x+y)*(x+y+1)/2 + y;
  (x,y)
}

至此，您的函数在语法上是有效的。

Dafny 随后抱怨了几个语义问题。首先，有几个关于“不满足nat类型的约束”的错误。您可以通过显式声明 x 和 y 具有类型 nat 来修复这些问题，如下所示：

function method unpair(n: nat): (nat, nat)
{
  var x:nat,y:nat :| n == (x+y)*(x+y+1)/2 + y;
  (x,y)
}

此时Dafny又报了一个错误，就是无法证明x和y这样的总存在。这是一个更根本的问题。您将需要说服 Dafny（可能使用单独的引理）此类数字始终存在。

如何在 Dafny 中产生无效的 LogicalExpression？

How to result invalid LogicalExpression in Dafny?

methods

dafny