英文:
multiple decreases lines (is this a bug?)
问题
"我用Dafny玩了一下,并做了Leino的书中的练习。练习3.5要求添加一个decreases子句来证明以下函数的终止:
function K(x: nat, y: nat, z: nat): int
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
现在,我添加了“decreases x + y
”子句,这正常运行(如预期的那样)。但是也可以使用“decreases 6*(x+y) + z
”(同样正常)。不过,“decreases 5*(x+y) + z
”却不起作用(也符合预期)。
但令我惊讶的是,我可以有两个(甚至更多)decreases子句,似乎只要其中一个生效,其他的都会被接受(或者说被忽略?)。
这是一个bug,还是预期的行为(如果是这样,我可能没有理解)?
function K(x: nat, y: nat, z: nat): int
decreases 5*(x+y) + z
decreases x+y
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
这被Dafny接受了,但如果你注释掉“decreases x+y
”这一行,它会失败(这是正确的行为)。"
英文:
I played with Dafny and the exercises from Leino's book.
Exercise 3.5 asks for a decreases clause to prove the termination of the following function:
function K(x: nat, y: nat, z: nat): int
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
Now, I added the clause "decreases x + y
" which works fine (as expected).
But what also works is "decreases 6*(x+y) + z
" (also as expected).
What does not work is "decreases 5*(x+y) + z
" (also as expected).
But what surprised me is that I can have two (or even more) decreases clauses, and it appears that as soon as one of the decreases works, the others are happily accepted (or should I say ignored?).
Is that a bug, or intended behavior (in which case I miss the point)?
function K(x: nat, y: nat, z: nat): int
decreases 5*(x+y) + z
decreases x+y
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
This is accepted by Dafny, but if you comment out the "decreases x+y
" line, it fails (and that is correct).
答案1
得分: 1
引用自Dafny参考手册(https://dafny.org/dafny/DafnyRef/DafnyRef#sec-decreases-clause)
> Decreases clauses are used to prove termination in the presence of
> recursion. If more than one decreases clause is given, it is as if a
> single decreases clause had been given with the collected list of
> arguments and a collected list of Attributes. That is,
> decreases A, B decreases C, D
> is equivalent to
> decreases A, B, C, D
> Note that changing the order of multiple decreases clauses will change
> the order of the expressions within the equivalent single decreases
> clause, and will therefore have different semantics.
> Termination metrics in Dafny, which are declared by decreases clauses,
> are lexicographic tuples of expressions. At each recursive (or
> mutually recursive) call to a function or method, Dafny checks that
> the effective decreases clause of the callee is strictly smaller than
> the effective decreases clause of the caller.
只要decreases clauses元组在词典序上递减,它就是一个良好的终止度量。在上述情况下,Dafny使用5*(x+y)+z, x+y
作为decreases clauses元组。
在z==0
的if
分支中,5*(x+y)+z
表达式在递归调用中具有相同的值,而x+y
是递减的。在then分支中,5*(x+y)+z
表达式本身是递减的。在这里,第一个decrease clause要么保持不变,要么递减,当它保持不变时,其后的另一个decrease clause确实递减。
为了提供一个假设中一个clause的反例,请考虑以下程序
function K(x: nat, y: nat, z: nat): int
decreases z
decreases x + y
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
英文:
Quoting from Dafny reference manual (https://dafny.org/dafny/DafnyRef/DafnyRef#sec-decreases-clause)
> Decreases clauses are used to prove termination in the presence of
> recursion. If more than one decreases clause is given it is as if a
> single decreases clause had been given with the collected list of
> arguments and a collected list of Attributes. That is,
>
> decreases A, B decreases C, D
>
> is equivalent to
>
> decreases A, B, C, D
>
> Note that changing the order of multiple decreases clauses will change
> the order of the expressions within the equivalent single decreases
> clause, and will therefore have different semantics.
>
> Termination metrics in Dafny, which are declared by decreases clauses,
> are lexicographic tuples of expressions. At each recursive (or
> mutually recursive) call to a function or method, Dafny checks that
> the effective decreases clause of the callee is strictly smaller than
> the effective decreases clause of the caller.
As long as decreases clauses tuple is lexicographically decreasing, it is good termination measure. In above case dafny is using 5*(x+y)+z, x+y
as decrease clauses tuple.
In if
branch of z==0
, 5*(x+y)+z
expression has same value in recursive call whereas x+y
is decreasing. In then branch 5*(x+y)+z
expression itself is decreasing. It is mere coincidence here that first decrease clause is either remains constant or decreases and when it remain constant another decrease clause after it indeed decreases.
To give counter example of one of clauses hypothesis consider following program
function K(x: nat, y: nat, z: nat): int
decreases z
decreases x + y
{
if x < 10 || y < 5
then x + y
else if z == 0
then K(x-1, y, 5)
else K(x, y-1, z-1)
}
答案2
得分: 0
感谢Divyanshu Ranjan回答我的问题。
事实上,事情确实是你说的对。
如果我添加另一个从句,即“减少x-y”作为最后一个从句,它确实有效。如果我将其作为第一个从句,那么它会失败(正如应该的那样)。所以,谜题解开了(并不是一个错误)。
谢谢!
英文:
Thanks Divyanshu Ranjan for answering my question.
Indeed, it turns out that you are right.
If I add another clause, being "decreases x-y" as the last clause, where it does not matter, it indeed works. If I make it the first clause, then it fails (as it should be). So, mystery solved (and it is not a bug).
Thanks!
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论