合成一个保留循环不变量和变量的循环程序

Question

我想创建一个具有以下先决条件的程序：不变量：

y = x ∗ x ∧ z = y ∗ x ∧ x ≤ n

变体：

n − x

程序结构如下：

while<cond>
   <invariant specification>
   <body>

用 frama-c 或 why3 编写的程序看起来应该如何？

编辑： 我通过删除乘法和添加加法来修改你的程序。通过这样做，我使用了两个循环。我运行我的程序，但我收到了警告。这是程序：

#include <limits.h>

/*@ requires n < INT_MAX; // avoids overflow in computing z
*/
void f(unsigned long n) {
    unsigned long x = 0, y = 0, z = 0, contor, aux_x, aux_y;
    /*@ loop assigns x, y, z, contor, aux_x, aux_y;
      @ loop invariant y == x * x && z == y * x && x <= n;
      @ loop variant n - x;
      @ */
    while (x < n) {
        x++;
        contor = 1;
        aux_x = 0;
        aux_y = 0;
        /* @ loop assings contor, aux_x, aux_y;
           @ loop invariant 1 <= contor <= x;
           @ loop variant x - contor, x, y;
           @*/
        while (contor <= x) {
            aux_x += x;
            aux_y += y;
            contor++;
        }
        y = aux_x;
        z = aux_y;
    }
}

还有警告：

[kernel] Parsing loop.c (with preprocessing)
[rte] annotating function f
[wp] loop.c:20: Warning: Missing assigns clause (assigns 'everything' instead)
[wp] 6 goals scheduled
[wp] [Alt-Ergo 2.4.1] Goal typed_f_loop_assigns_part2 : Timeout (Qed:6ms) (10s) (cached)
[wp] [Alt-Ergo 2.4.1] Goal typed_f_loop_variant_decrease : Timeout (Qed:16ms) (10s) (cached)
[wp] [Alt-Ergo 2.4.1] Goal typed_f_loop_invariant_established : Timeout (Qed:3ms) (10s)
[wp] [Alt-Ergo 2.4.1] Goal typed_f_loop_invariant_preserved : Timeout (Qed:11ms) (10s)
[wp] [Cache] found:2, updated:2
[wp] Proved goals:    2 / 6
  Qed:               2  (7ms)
  Alt-Ergo 2.4.1:    0  (interrupted: 4) (cached: 2)
[wp:pedantic-assigns] loop.c:5: Warning: 
  No 'assigns' specification for function 'f'.
  Callers assumptions might be imprecise.

你能解释一下为什么即使我为内部循环指定了不变量和变量，我还是收到了那些讨厌的警告吗？

Answer 1

不太清楚你想要实现什么，但这里有一个 C 程序可以用 frama-c -wp loop.c 证明并且具有适当的不变量和变量：

/*@ requires n < 2097152; // avoids overflow in computing z
 */
void f(unsigned long n) {
  unsigned long x = 0, y = 0, z = 0;
  /*@ loop invariant y == x * x && z == y * x && x <= n;
      loop assigns x,y,z;
      loop variant n - x;
  */
  while (x < n) {
    x++;
    y = x * x;
    z = y * x;
  }
}

注意：requires 不是可以在计算 z 时避免溢出的最通用的方法，但计算 2^21 比求立方根更容易共 2^64-1.

合成一个保留循环不变量和变量的循环程序

Synthesize a loop program that preserves the loop invariant and variant

frama-c

why3