Dafny：快速指数计算（循环）

Question

我正在尝试在 Dafny 中实现和编译快速指数算法，但我运行遇到了几个问题。

上下文：

所有代码都在下面可用；
快速指数 (FastExp) 引理本身是迭代的；
一个exp函数用于确保计算正确（此函数递归执行传统指数）；
我不会讨论数学是如何完成的，或者它是否有效。这不是问题，数学是正确的。

现在，我运行遇到的主要问题：

我不知道在循环的 decrease 和 invariants;
FastExp 引理的后置条件“可能不成立”；

如果有人能帮助我解决这个简单的（我假设的）问题，我会很高兴。

提前致谢。

function isEven(a: int): bool
    requires a >= 0;
{
    if a == 0 then      true 
    else if a == 1 then false 
    else                isEven(a - 2)
}

function exp(x: int, n: int): int
    requires n > 0;
{
    if n == 1 then
        x
     else 
        x * exp(x, n-1)
}

lemma FastExp(x: int, n: int) returns (r: int)
requires n >= 0
ensures r == exp(x,n)
{
    var expo:int := n;
    var c:int := x;
    var tempR:int := 1;

    while expo > 0
        invariant 0 <= expo
        decreases expo
    {
        if isEven(expo) {
            tempR := tempR * c;
        }
        c := c * c;
        expo := expo / 2;
    }
    r := tempR;
}

Answer 1

A decreases 子句用于解释终止。要证明循环终止，您需要找到某个表达式，其值在每次迭代中都会减少（以有根据的顺序）。在你的情况下， expo 就是这样一个表达式，所以你的 decreases 子句就是证明循环终止所需的全部内容。（事实上，它比你需要的要多。如果你完全放弃这个 decreases 子句，Dafny 会自动猜出这个。）

推理循环的方法是找到一些条件，称为 循环不变量，它在每次迭代的最顶部都成立（即，条件每次评估环路防护时都为真）。您已经编写了一个这样的不变量，即 0 <= expo。然而，关于变量tempR和c，或者这些变量与expo、x和n之间的关系没有不变性。因此，验证者对循环迭代开始时或循环后这些变量的值一无所知。

因此，要验证您的程序是否执行正确的数学运算，您需要通过编写不变条件来说服验证者。

让我开始吧。您的不变量需要做三件事。 0：需要先保持，当第一次到达循环时。也就是说，对于变量的初始值，条件必须为真。 1：循环守卫的不变量和否定（仅这些，没有您可能认为也成立的其他事实）必须足以证明后置条件。例如，您唯一可以从当前循环不变量和守卫的否定中推断出的是循环之后的 expo == 0 。 2：不变量必须由循环体维护。也就是说，给定循环体开头的不变量和守卫，你必须证明在循环体之后不变量再次成立。

在你弄清楚循环不变量应该是什么之后，你需要证明一个关于求幂的数学事实。你到那儿就知道了。

祝你好运！

PS。以下是关于您的程序的一些其他评论：

您目前在 FastExp 的后置条件中调用 exp 时违反了前置条件。这意味着您的后置条件定义不明确并且并不总是有意义（这将使尝试建立后置条件的任务变得不可能）。问题是 FastExp 允许 n 为 0，但您的函数 exp 不允许。您将需要为指数 0 定义 exp 以证明 FastExp 的正确性。所以，改变exp的前提条件，让n成为0。（然后您必须修复 exp 的正文。）
Dafny 有一个类型 nat，代表非负整数。因此，如果您愿意，您可以简单地声明 n: nat 并删除这些前提条件，而不是声明 n: int 并添加前提条件 0 <= n。
定义isEven有一个更短的方法，即a % 2 == 0。
不需要引入局部变量tempR。你可以直接使用r。
将 FastExp 声明为引理有点奇怪。 Dafny 确实允许引理具有输出参数（这有时非常有用），您确实可以使用循环编写引理的证明。但是写 FastExp 的原因并不是要表明可以将某些值分配给 r 以使 r == exp(x, n) 为真——您可以通过分配 r := exp(x, n);.相反，声明 FastExp 的原因是您需要一个计算它的程序。为此，将 FastExp 声明为 method。（在 Dafny 中引理和方法之间的唯一技术区别是方法被编译而引理被编译器擦除。）

Dafny：快速指数计算（循环）

Dafny: Fast Exponent Calculation (Loops)

loops

dafny

invariants

loop-invariant