如何为 SPARK 中的递归函数设置 Pre 和 Post 条件？
How to make Pre and Post conditions for recursive functions in SPARK?
我正在将我在 Dafny 中做的一个练习翻译成 SPARK，其中一个人验证尾递归函数与递归函数。 Dafny 来源（已删减，因为它可能仍用于 类）：
function Sum(n:nat):nat
decreases n
{
if n==0 then n else n+Sum(n-1)
}
method ComputeSum(n:nat) returns (s:nat)
ensures s == Sum(n)
{
s := 0;
// ...censored...
}
到目前为止我在 SPARK 中得到的：
function Sum (n : in Natural) return Natural
is
begin
if n = 0 then
return n;
else
return n + Sum(n - 1);
end if;
end Sum;
function ComputeSum(n : in Natural) return Natural
with
Post => ComputeSum'Result = Sum(n)
is
s : Natural := 0;
begin
-- ...censored...
return s;
end ComputeSum;
我似乎无法弄清楚如何表达 decreases n 条件（现在我想起来可能有点奇怪......但几年前我就为此评分了所以谁是我来判断，问题仍然是如何完成它）。结果，我收到了可能溢出的警告 and/or 无限递归。
我猜要添加一个前置或 post 条件。尝试 Pre => n <= 1 显然不会溢出，但我仍然收到警告。在其上添加 Post => Sum'Result <= n**n 会使警告消失，但该条件会收到“post条件可能失败”警告，这是不对的，但猜想证明者无法分辨。也不是我应该检查的表达式，但我似乎无法弄清楚我正在寻找的其他 Post 。可能与递归表达式非常接近，但 none 我的尝试有效。一定是遗漏了一些语言结构...
那么，我该如何表达递归约束？
编辑 1：
以下链接 to this SO answer and this SPARK doc section，我试过这个：
function Sum (n : in Natural) return Natural
is
(if n = 0 then 0 else n + Sum(n - 1))
with
Pre => (n in 0 .. 2),
Contract_Cases => (n = 0 => Sum'Result = 0,
n >= 1 => Sum'Result = n + Sum(n - 1)),
Subprogram_Variant => (Decreases => n);
但是从 SPARK 收到这些警告：
spark.adb:32:30: medium: overflow check might fail [reason for check: result of addition must fit in a 32-bits machine integer][#0]
spark.adb:36:56: warning: call to "Sum" within its postcondition will lead to infinite recursion
我找到了一些有时有用的东西，我认为这足以结束标题问题：
function Sum (n : in Natural) return Natural
is
(if n = 0 then 0 else n + Sum(n - 1))
with
Pre => (n in 0 .. 10), -- works with --prover=z3, not Default (CVC4)
-- Pre => (n in 0 .. 100), -- not working - "overflow check might fail, e.g. when n = 2"
Subprogram_Variant => (Decreases => n),
Post => ((n = 0 and then Sum'Result = 0)
or (n > 0 and then Sum'Result = n + Sum(n - 1)));
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => Sum'Result = n + Sum(n - 1)); -- warning: call to "Sum" within its postcondition will lead to infinite recursion
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => n + Sum(n - 1) = Sum'Result); -- works
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => Sum'Result = n * (n + 1) / 2); -- works and gives good overflow counterexamples for high n, but isn't really recursive
GNAT Studio 中的命令行调用 (Ctrl+Alt+F)，--counterproof=on 和 --prover=z3 我对它的补充：
gnatprove -P%PP -j0 %X --output=oneline --ide-progress-bar --level=0 -u %fp --counterexamples=on --prover=z3
要点：
Subprogram_Variant => (Decreases => n) 需要告诉证明者 n 每次递归调用都会减少，就像 Dafny 版本一样。
- 类似合同的工作不一致，请参阅评论
Contract_Cases。
- 默认证明者 (CVC4) 失败，使用 Z3 成功。
- 失败反证毫无意义。
n = 2 作为范围 0 .. 100 的反证，但不是 0 .. 10.- 可能与the SPARK user guide中提到的有关：但是，请注意，由于反例始终仅使用CVC4证明器生成，因此它只能解释为什么该证明器无法证明属性.
- 需要在更改选项之间进行清理，例如--prover.
如果你想证明某个尾递归求和函数的结果等于给定递归求和函数对某个值N的结果，那么原则上只定义没有任何 post 条件的递归函数（作为表达式函数）。然后你只需要在尾递归函数的post-条件中提到递归（表达式）函数（注意递归上没有post-条件（ensures）也可以在 Dafny 中发挥作用）。
但是，由于 SPARK 的主要目标之一是证明不存在运行时错误，您必须证明不会发生溢出，并且由于 这个原因，您 do 在递归函数上需要一个 post 条件。正如@Jeffrey Carter 已经在评论中建议的那样，这种 post 条件的合理选择是 arithmetic progression:
的显式求和公式
Sum (N) = N * (1 + N) / 2
这个选择实际上非常有吸引力，因为有了这个公式，我们现在还可以根据计算一系列自然数之和的众所周知的数学显式表达式在功能上验证递归函数本身。
不幸的是，按原样使用此公式只会让您半途而废。在 SPARK（以及 Ada）中，前置条件和 post 条件是可选可执行的（另请参阅 SPARK 参考指南中的 RM 11.4.2 and section 5.11.1），因此它们本身必须没有任何运行时错误。因此，按原样使用公式只能让您证明任何正数都不会发生溢出，直到
max N s.t. N * (1 + N) <= Integer'Last <-> N = 46340
和post条件一样，乘法也不允许溢出（注意Natural'Last = Integer'Last = 2**31 - 1）。
要解决此问题，您需要使用 Ada 202x 标准库中引入的大整数包（另请参阅 RM A.5.6；此包已包含在 GNAT CE 2021 中和 GNAT FSF 11.2）。大整数是无界的，使用这些整数进行的计算永远不会溢出。使用这些整数，可以证明直到
之前任何正数都不会发生溢出
max N s.t. N * (1 + N) / 2 <= Natural'Last <-> N = 65535 = 2**16 - 1
这些整数在 post 条件中的用法如下例所示。
一些最后的笔记：
Subprogram_Variant方面只需要证明一个递归子程序最终会终止。必须通过向函数添加注释来明确请求此类终止证明（也显示在下面的示例中，并在评论中@egilhh 指出的 SPARK 文档中进行了讨论）。但是，Subprogram_Variant 方面对于您的初始目的而言并不需要：证明某些尾递归求和函数的结果等于某个值 N.[=40 的给定递归求和函数的结果=]
要编译使用新 Ada 202x 标准库函数的程序，请使用编译器选项 -gnat2020。
虽然我使用子类型来限制 N 的允许值范围，但您也可以使用前提条件。这应该没有任何区别。但是，在 SPARK（以及 Ada）中，通常认为尽可能使用（子）类型来表达约束是最佳实践。
将反例视为可能的线索而不是事实。它们可能有意义也可能没有意义。反例由一些求解器选择性地生成，可能没有意义。另请参阅 SPARK 用户指南中的 section 7.2.6。
main.adb
with Ada.Numerics.Big_Numbers.Big_Integers;
procedure Main with SPARK_Mode is
package BI renames Ada.Numerics.Big_Numbers.Big_Integers;
use type BI.Valid_Big_Integer;
-- Conversion functions.
function To_Big (Arg : Integer) return BI.Valid_Big_Integer renames BI.To_Big_Integer;
function To_Int (Arg : BI.Valid_Big_Integer) return Integer renames BI.To_Integer;
subtype Domain is Natural range 0 .. 2**16 - 1;
function Sum (N : Domain) return Natural is
(if N = 0 then 0 else N + Sum (N - 1))
with
Post => Sum'Result = To_Int (To_Big (N) * (1 + To_Big (N)) / 2),
Subprogram_Variant => (Decreases => N);
-- Request a proof that Sum will terminate for all possible values of N.
pragma Annotate (GNATprove, Terminating, Sum);
begin
null;
end Main;
输出 (gnatprove)
$ gnatprove -Pdefault.gpr --output=oneline --report=all --level=1 --prover=z3
Phase 1 of 2: generation of Global contracts ...
Phase 2 of 2: flow analysis and proof ...
main.adb:13:13: info: subprogram "Sum" will terminate, terminating annotation has been proved
main.adb:14:30: info: overflow check proved
main.adb:14:32: info: subprogram variant proved
main.adb:14:39: info: range check proved
main.adb:16:18: info: postcondition proved
main.adb:16:31: info: range check proved
main.adb:16:53: info: predicate check proved
main.adb:16:69: info: division check proved
main.adb:16:71: info: predicate check proved
Summary logged in [...]/gnatprove.out
附录（回应评论）
因此可以将post条件作为递归函数加入，但这无助于证明不存在溢出；您仍然需要提供函数结果的一些上限，以说服证明者表达式 N + Sum (N - 1) 不会导致溢出。
为了检查加法过程中是否存在溢出，证明者将根据其规范考虑 Sum 可能 return 的所有可能值，并查看这些值中是否至少有一个可能导致除了溢出。在 post 条件中没有显式限制的情况下，Sum 可能会根据其 return 类型 return 范围 Natural'Range 中的任何值。该范围包括 Natural'Last 并且该值肯定会导致溢出。因此，证明者将报告添加可能溢出。 Sum 从不 return 给定其允许的输入值这一事实与此处无关（这就是它报告 可能 的原因）。因此，需要更精确的 return 值上限。
如果没有确切的上限，那么您通常会回退到更保守的界限，例如在这种情况下，N * N（或使用饱和度数学，如 SPARK 中的斐波那契示例所示用户手册，section 5.2.7，但这种方法 确实 改变了你的功能，这可能是不可取的）。
这是另一个例子：
example.ads
package Example with SPARK_Mode is
subtype Domain is Natural range 0 .. 2**15;
function Sum (N : Domain) return Natural
with Post =>
Sum'Result = (if N = 0 then 0 else N + Sum (N - 1)) and
Sum'Result <= N * N; -- conservative upper bound if the closed form
-- solution to the recursive function would
-- not exist.
end Example;
example.adb
package body Example with SPARK_Mode is
function Sum (N : Domain) return Natural is
begin
if N = 0 then
return N;
else
return N + Sum (N - 1);
end if;
end Sum;
end Example;
输出 (gnatprove)
$ gnatprove -Pdefault.gpr --output=oneline --report=all
Phase 1 of 2: generation of Global contracts ...
Phase 2 of 2: flow analysis and proof ...
example.adb:8:19: info: overflow check proved
example.adb:8:28: info: range check proved
example.ads:7:08: info: postcondition proved
example.ads:7:45: info: overflow check proved
example.ads:7:54: info: range check proved
Summary logged in [...]/gnatprove.out
我正在将我在 Dafny 中做的一个练习翻译成 SPARK，其中一个人验证尾递归函数与递归函数。 Dafny 来源（已删减，因为它可能仍用于 类）：
function Sum(n:nat):nat
decreases n
{
if n==0 then n else n+Sum(n-1)
}
method ComputeSum(n:nat) returns (s:nat)
ensures s == Sum(n)
{
s := 0;
// ...censored...
}
到目前为止我在 SPARK 中得到的：
function Sum (n : in Natural) return Natural
is
begin
if n = 0 then
return n;
else
return n + Sum(n - 1);
end if;
end Sum;
function ComputeSum(n : in Natural) return Natural
with
Post => ComputeSum'Result = Sum(n)
is
s : Natural := 0;
begin
-- ...censored...
return s;
end ComputeSum;
我似乎无法弄清楚如何表达 decreases n 条件（现在我想起来可能有点奇怪......但几年前我就为此评分了所以谁是我来判断，问题仍然是如何完成它）。结果，我收到了可能溢出的警告 and/or 无限递归。
我猜要添加一个前置或 post 条件。尝试 Pre => n <= 1 显然不会溢出，但我仍然收到警告。在其上添加 Post => Sum'Result <= n**n 会使警告消失，但该条件会收到“post条件可能失败”警告，这是不对的，但猜想证明者无法分辨。也不是我应该检查的表达式，但我似乎无法弄清楚我正在寻找的其他 Post 。可能与递归表达式非常接近，但 none 我的尝试有效。一定是遗漏了一些语言结构...
那么，我该如何表达递归约束？
编辑 1：
以下链接 to this SO answer and this SPARK doc section，我试过这个：
function Sum (n : in Natural) return Natural
is
(if n = 0 then 0 else n + Sum(n - 1))
with
Pre => (n in 0 .. 2),
Contract_Cases => (n = 0 => Sum'Result = 0,
n >= 1 => Sum'Result = n + Sum(n - 1)),
Subprogram_Variant => (Decreases => n);
但是从 SPARK 收到这些警告：
spark.adb:32:30: medium: overflow check might fail [reason for check: result of addition must fit in a 32-bits machine integer][#0]
spark.adb:36:56: warning: call to "Sum" within its postcondition will lead to infinite recursion
我找到了一些有时有用的东西，我认为这足以结束标题问题：
function Sum (n : in Natural) return Natural
is
(if n = 0 then 0 else n + Sum(n - 1))
with
Pre => (n in 0 .. 10), -- works with --prover=z3, not Default (CVC4)
-- Pre => (n in 0 .. 100), -- not working - "overflow check might fail, e.g. when n = 2"
Subprogram_Variant => (Decreases => n),
Post => ((n = 0 and then Sum'Result = 0)
or (n > 0 and then Sum'Result = n + Sum(n - 1)));
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => Sum'Result = n + Sum(n - 1)); -- warning: call to "Sum" within its postcondition will lead to infinite recursion
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => n + Sum(n - 1) = Sum'Result); -- works
-- Contract_Cases => (n = 0 => Sum'Result = 0,
-- n > 0 => Sum'Result = n * (n + 1) / 2); -- works and gives good overflow counterexamples for high n, but isn't really recursive
GNAT Studio 中的命令行调用 (Ctrl+Alt+F)，--counterproof=on 和 --prover=z3 我对它的补充：
gnatprove -P%PP -j0 %X --output=oneline --ide-progress-bar --level=0 -u %fp --counterexamples=on --prover=z3
要点：
Subprogram_Variant => (Decreases => n)需要告诉证明者 n 每次递归调用都会减少，就像 Dafny 版本一样。- 类似合同的工作不一致，请参阅评论
Contract_Cases。
- 类似合同的工作不一致，请参阅评论
- 默认证明者 (CVC4) 失败，使用 Z3 成功。
- 失败反证毫无意义。
n = 2作为范围0 .. 100的反证，但不是0 .. 10.- 可能与the SPARK user guide中提到的有关：但是，请注意，由于反例始终仅使用CVC4证明器生成，因此它只能解释为什么该证明器无法证明属性.
- 需要在更改选项之间进行清理，例如--prover.
如果你想证明某个尾递归求和函数的结果等于给定递归求和函数对某个值N的结果，那么原则上只定义没有任何 post 条件的递归函数（作为表达式函数）。然后你只需要在尾递归函数的post-条件中提到递归（表达式）函数（注意递归上没有post-条件（ensures）也可以在 Dafny 中发挥作用）。
但是，由于 SPARK 的主要目标之一是证明不存在运行时错误，您必须证明不会发生溢出，并且由于 这个原因，您 do 在递归函数上需要一个 post 条件。正如@Jeffrey Carter 已经在评论中建议的那样，这种 post 条件的合理选择是 arithmetic progression:
的显式求和公式Sum (N) = N * (1 + N) / 2
这个选择实际上非常有吸引力，因为有了这个公式，我们现在还可以根据计算一系列自然数之和的众所周知的数学显式表达式在功能上验证递归函数本身。
不幸的是，按原样使用此公式只会让您半途而废。在 SPARK（以及 Ada）中，前置条件和 post 条件是可选可执行的（另请参阅 SPARK 参考指南中的 RM 11.4.2 and section 5.11.1），因此它们本身必须没有任何运行时错误。因此，按原样使用公式只能让您证明任何正数都不会发生溢出，直到
max N s.t. N * (1 + N) <= Integer'Last <-> N = 46340
和post条件一样，乘法也不允许溢出（注意Natural'Last = Integer'Last = 2**31 - 1）。
要解决此问题，您需要使用 Ada 202x 标准库中引入的大整数包（另请参阅 RM A.5.6；此包已包含在 GNAT CE 2021 中和 GNAT FSF 11.2）。大整数是无界的，使用这些整数进行的计算永远不会溢出。使用这些整数，可以证明直到
之前任何正数都不会发生溢出max N s.t. N * (1 + N) / 2 <= Natural'Last <-> N = 65535 = 2**16 - 1
这些整数在 post 条件中的用法如下例所示。
一些最后的笔记：
Subprogram_Variant方面只需要证明一个递归子程序最终会终止。必须通过向函数添加注释来明确请求此类终止证明（也显示在下面的示例中，并在评论中@egilhh 指出的 SPARK 文档中进行了讨论）。但是，Subprogram_Variant方面对于您的初始目的而言并不需要：证明某些尾递归求和函数的结果等于某个值N.[=40 的给定递归求和函数的结果=]要编译使用新 Ada 202x 标准库函数的程序，请使用编译器选项
-gnat2020。虽然我使用子类型来限制
N的允许值范围，但您也可以使用前提条件。这应该没有任何区别。但是，在 SPARK（以及 Ada）中，通常认为尽可能使用（子）类型来表达约束是最佳实践。将反例视为可能的线索而不是事实。它们可能有意义也可能没有意义。反例由一些求解器选择性地生成，可能没有意义。另请参阅 SPARK 用户指南中的 section 7.2.6。
main.adb
with Ada.Numerics.Big_Numbers.Big_Integers;
procedure Main with SPARK_Mode is
package BI renames Ada.Numerics.Big_Numbers.Big_Integers;
use type BI.Valid_Big_Integer;
-- Conversion functions.
function To_Big (Arg : Integer) return BI.Valid_Big_Integer renames BI.To_Big_Integer;
function To_Int (Arg : BI.Valid_Big_Integer) return Integer renames BI.To_Integer;
subtype Domain is Natural range 0 .. 2**16 - 1;
function Sum (N : Domain) return Natural is
(if N = 0 then 0 else N + Sum (N - 1))
with
Post => Sum'Result = To_Int (To_Big (N) * (1 + To_Big (N)) / 2),
Subprogram_Variant => (Decreases => N);
-- Request a proof that Sum will terminate for all possible values of N.
pragma Annotate (GNATprove, Terminating, Sum);
begin
null;
end Main;
输出 (gnatprove)
$ gnatprove -Pdefault.gpr --output=oneline --report=all --level=1 --prover=z3
Phase 1 of 2: generation of Global contracts ...
Phase 2 of 2: flow analysis and proof ...
main.adb:13:13: info: subprogram "Sum" will terminate, terminating annotation has been proved
main.adb:14:30: info: overflow check proved
main.adb:14:32: info: subprogram variant proved
main.adb:14:39: info: range check proved
main.adb:16:18: info: postcondition proved
main.adb:16:31: info: range check proved
main.adb:16:53: info: predicate check proved
main.adb:16:69: info: division check proved
main.adb:16:71: info: predicate check proved
Summary logged in [...]/gnatprove.out
附录（回应评论）
因此可以将post条件作为递归函数加入，但这无助于证明不存在溢出；您仍然需要提供函数结果的一些上限，以说服证明者表达式 N + Sum (N - 1) 不会导致溢出。
为了检查加法过程中是否存在溢出，证明者将根据其规范考虑 Sum 可能 return 的所有可能值，并查看这些值中是否至少有一个可能导致除了溢出。在 post 条件中没有显式限制的情况下，Sum 可能会根据其 return 类型 return 范围 Natural'Range 中的任何值。该范围包括 Natural'Last 并且该值肯定会导致溢出。因此，证明者将报告添加可能溢出。 Sum 从不 return 给定其允许的输入值这一事实与此处无关（这就是它报告 可能 的原因）。因此，需要更精确的 return 值上限。
如果没有确切的上限，那么您通常会回退到更保守的界限，例如在这种情况下，N * N（或使用饱和度数学，如 SPARK 中的斐波那契示例所示用户手册，section 5.2.7，但这种方法 确实 改变了你的功能，这可能是不可取的）。
这是另一个例子：
example.ads
package Example with SPARK_Mode is
subtype Domain is Natural range 0 .. 2**15;
function Sum (N : Domain) return Natural
with Post =>
Sum'Result = (if N = 0 then 0 else N + Sum (N - 1)) and
Sum'Result <= N * N; -- conservative upper bound if the closed form
-- solution to the recursive function would
-- not exist.
end Example;
example.adb
package body Example with SPARK_Mode is
function Sum (N : Domain) return Natural is
begin
if N = 0 then
return N;
else
return N + Sum (N - 1);
end if;
end Sum;
end Example;
输出 (gnatprove)
$ gnatprove -Pdefault.gpr --output=oneline --report=all
Phase 1 of 2: generation of Global contracts ...
Phase 2 of 2: flow analysis and proof ...
example.adb:8:19: info: overflow check proved
example.adb:8:28: info: range check proved
example.ads:7:08: info: postcondition proved
example.ads:7:45: info: overflow check proved
example.ads:7:54: info: range check proved
Summary logged in [...]/gnatprove.out