如何证明这个不变量?
How to prove this invariant?
我的目标是证明霍纳法则是正确的。为此,我将 Horner 当前计算的值与“真实”多项式的值进行比较。
所以我做了这段代码:
package body Poly with SPARK_Mode is
function Horner (X : Integer; A : Vector) return Integer is
Y : Integer := 0;
Z : Integer := 0 with Ghost;
begin
for I in reverse A'First .. A'Last loop
pragma Loop_Invariant (Y * (X ** (I - A'First + 1)) = Z);
Y := A(I) + Y * X;
Z := Z + A(I) * (X ** (I - A'First));
end loop;
pragma Assert (Y = Z);
return Y;
end Horner;
end Poly;
应该证明不变量。不幸的是,gnatprove 告诉我:
cannot prove Y * (X ** (I - A'First + 1)) = Z
e.g. when A = (1 => 0, others => 0) and A'First = 0 and A'Last = 1 and I = 0 and X = 1 and Y = -1 and Z = 0
在这种情况下 Y=-1 是如何工作的?您知道如何解决这个问题吗?
这里的反例是假的,不对应真正的无效执行。该算法对于证明者来说太复杂了,这导致循环不变性保存没有被证明,以及虚假的反例。
要调查这种未经证明的检查,您必须进入证明属性的“自动激活”模式,这需要将 属性 分解为更小的步骤,直到任何一个自动证明者都可以处理更小的步骤,或者您可以隔离一个未经证明的初等 属性,您可以在引理中隔离,您可以单独验证。
这里我在一次迭代的开始为Y的值引入了一个幽灵变量YY,并在越来越小的断言中分解了循环不变量,这表明问题出在求幂(X ** (我- A'First + 1) = X * (X ** (I - A'First)) 我也在断言中隔离:
package body Poly with SPARK_Mode is
function Horner (X : Integer; A : Vector) return Integer is
Y : Integer := 0;
Z : Integer := 0 with Ghost;
YY : Integer with Ghost;
begin
for I in reverse A'First .. A'Last loop
pragma Loop_Invariant (Y * (X ** (I - A'First + 1)) = Z);
YY := Y;
Y := A(I) + Y * X;
Z := Z + A(I) * (X ** (I - A'First));
pragma Assert (Z = YY * (X ** (I - A'First + 1)) + A(I) * (X ** (I - A'First)));
pragma Assert (X ** (I - A'First + 1) = X * (X ** (I - A'First)));
pragma Assert (Z = YY * X * (X ** (I - A'First)) + A(I) * (X ** (I - A'First)));
pragma Assert (Z = (YY * X + A(I)) * (X ** (I - A'First)));
pragma Assert (Z = Y * (X ** (I - A'First)));
end loop;
pragma Assert (Y = Z);
return Y;
end Horner;
end Poly;
现在所有断言和循环不变量都使用 --level=2 和 SPARK Community 2020 证明。当然有些断言是不需要的,所以你可以删除它们。
我的目标是证明霍纳法则是正确的。为此,我将 Horner 当前计算的值与“真实”多项式的值进行比较。
所以我做了这段代码:
package body Poly with SPARK_Mode is
function Horner (X : Integer; A : Vector) return Integer is
Y : Integer := 0;
Z : Integer := 0 with Ghost;
begin
for I in reverse A'First .. A'Last loop
pragma Loop_Invariant (Y * (X ** (I - A'First + 1)) = Z);
Y := A(I) + Y * X;
Z := Z + A(I) * (X ** (I - A'First));
end loop;
pragma Assert (Y = Z);
return Y;
end Horner;
end Poly;
应该证明不变量。不幸的是,gnatprove 告诉我:
cannot prove Y * (X ** (I - A'First + 1)) = Z
e.g. when A = (1 => 0, others => 0) and A'First = 0 and A'Last = 1 and I = 0 and X = 1 and Y = -1 and Z = 0
在这种情况下 Y=-1 是如何工作的?您知道如何解决这个问题吗?
这里的反例是假的,不对应真正的无效执行。该算法对于证明者来说太复杂了,这导致循环不变性保存没有被证明,以及虚假的反例。
要调查这种未经证明的检查,您必须进入证明属性的“自动激活”模式,这需要将 属性 分解为更小的步骤,直到任何一个自动证明者都可以处理更小的步骤,或者您可以隔离一个未经证明的初等 属性,您可以在引理中隔离,您可以单独验证。
这里我在一次迭代的开始为Y的值引入了一个幽灵变量YY,并在越来越小的断言中分解了循环不变量,这表明问题出在求幂(X ** (我- A'First + 1) = X * (X ** (I - A'First)) 我也在断言中隔离:
package body Poly with SPARK_Mode is
function Horner (X : Integer; A : Vector) return Integer is
Y : Integer := 0;
Z : Integer := 0 with Ghost;
YY : Integer with Ghost;
begin
for I in reverse A'First .. A'Last loop
pragma Loop_Invariant (Y * (X ** (I - A'First + 1)) = Z);
YY := Y;
Y := A(I) + Y * X;
Z := Z + A(I) * (X ** (I - A'First));
pragma Assert (Z = YY * (X ** (I - A'First + 1)) + A(I) * (X ** (I - A'First)));
pragma Assert (X ** (I - A'First + 1) = X * (X ** (I - A'First)));
pragma Assert (Z = YY * X * (X ** (I - A'First)) + A(I) * (X ** (I - A'First)));
pragma Assert (Z = (YY * X + A(I)) * (X ** (I - A'First)));
pragma Assert (Z = Y * (X ** (I - A'First)));
end loop;
pragma Assert (Y = Z);
return Y;
end Horner;
end Poly;
现在所有断言和循环不变量都使用 --level=2 和 SPARK Community 2020 证明。当然有些断言是不需要的,所以你可以删除它们。