使用归一化器来减少递归函数

Question

我想证明属性在有限数量的情况下参数化。我想将问题分为每个案例一个实例并分别解决每个实例。这是一个清理事情的例子：

module Minimal
open FStar.List
open FStar.Tactics
open FStar.Reflection.Data

unfold let lst = [0;1]

unfold let prop i = 
  match i with
  | 0 -> i == 0
  | 1 -> i == 1
  | _ -> False

val propHolds (i:int) : Lemma (requires (List.mem i lst)) (ensures (prop i))

在这种情况下，案例由列表 lst 定义。我可以很容易地证明 propholds:

let propHolds i =
  assert_by_tactic (prop 0) (fun () -> norm[delta;primops;iota;zeta]; dump "normalized"; trivial ());
  assert_by_tactic (prop 1) (fun () -> norm[delta;primops;iota;zeta]; dump "normalized"; trivial ())

但我显然不想为每个案例写一个单独的 assert_by_tactic（而不是当可能有数千个时......）。我想以某种方式为 lst 中的所有元素自动生成上面的证明。

我尝试了各种方法，这是其中之一：

  assert_by_tactic (let rec props i =
                       if i = 0 then prop 0
                       else (prop i) /\ (props (i-1))
                    in
                      props 1) (fun () -> norm[delta;primops;iota;zeta]; dump "normalized")

不幸的是，这并没有完全达到我想要的效果，assert_by_tactic 失败了（并且没有按照我期望的方式减少）。我想我遗漏了一些关于规范化的明显内容，但在 F* 中执行此操作的规范方法是什么？如果解决方案指向失败的 "case"/断言（如果存在的话），则加分。

Answer 1

F* 的类型系统只能确保术语的弱规范化。类型良好的开放术语可能会发散，例如，当在不一致的上下文中减少时。为了防止这种情况，F* 规范器采用各种启发式方法，默认情况下，保守地拒绝减少未减少的匹配主体中的递归调用。这就是阻止 List.mem 完全减少到未减少的级联 if/then/else 的原因（if/then/else 只是布尔匹配的糖分）。

List.memP，F* 的标准库中的一个相关函数在这种情况下对缩减更友好，因为它不会在内部阻止未缩减的匹配。请注意，List.memP 不一定总是比 List.mem 更友好——后者是布尔值，因此在某些情况下它可以计算更多（例如，List.mem 3 [1;2;3] 会很好地减少到true);

试试这个程序：

module Minimal
open FStar.Tactics

let lst = [0;1;2;3;4;5;6;7;8;9;10]

let prop i =
  match i with
  | 0 -> i == 0
  | 1 -> i == 1
  | 2 -> i == 2
  | 3 -> i == 3
  | 4 -> i == 4
  | 5 -> i == 5
  | 6 -> i == 6
  | 7 -> i == 7
  | 8 -> i == 8
  | 9 -> i == 9
  | 10 -> i == 10
  | _ -> False

let propHolds (i:int) =
  assert (List.memP i lst ==> prop i) 
      by (dump "A";
          norm [delta_only [`%List.memP; `%lst]; iota; zeta; simplify];
          dump "B")

在 dump B，您会看到假设简化为嵌套析取。 Z3可以从那里轻松证明目标。

这是另一种方法，这次没有策略。

let trigger_norm (a:Type) 
  : Lemma
    (requires a)
    (ensures (Pervasives.norm [delta_only [`%List.memP; `%lst]; iota; zeta; simplify] a))
  = ()


let propHolds (i:int) 
  : Lemma
    (requires List.memP i lst)
    (ensures prop i)
  = trigger_norm (List.memP i lst)

现在，作为对下面 jebus 的评论的回应，您可以进一步使用策略证明后置条件，尽管 SMT 求解器执行此操作的速度非常快……所以我不会为此使用策略除非你有一些特别强烈的理由这样做。

这是另一种解决方案：

module SO
open FStar.Tactics

let lst = [0;1;2;3;4;5;6;7;8;9;10]

let pred i =
  match i with
  | 0 -> i == 0
  | 1 -> i == 1
  | 2 -> i == 2
  | 3 -> i == 3
  | 4 -> i == 4
  | 5 -> i == 5
  | 6 -> i == 6
  | 7 -> i == 7
  | 8 -> i == 8
  | 9 -> i == 9
  | 10 -> i == 10
  | _ -> False

let case_impl (a b c:Type) 
  : Lemma
    (requires (a ==> c) /\ (b ==> c))
    (ensures (a \/ b) ==> c) 
  = ()

let solve_pred_impl () : Tac unit =
    let eq = implies_intro () in
    rewrite eq;
    norm [delta_only [`%pred]; iota];
    trivial()

let test i =  
  assert (List.memP i lst ==> pred i)
      by (norm [delta_only [`%List.memP; `%lst]; iota; zeta; simplify];
          let _ = repeat 
            (fun () ->
              mapply (`case_impl); 
              split();
              solve_pred_impl()) in
          solve_pred_impl())

使用归一化器来减少递归函数

Using the normalizer to reduce a recursive function

fstar