“接受任意数量量词的Ltac策略”

huangapple go评论54阅读模式
英文:

Ltac tactic that accepts an arbitrary number of quantifiers

问题

I'm trying to write a--my first--Coq tactic.
It should split forall x y z ..., A <-> B into two: forall x y z ..., A -> B and forall x y z ..., B -> A.

This is my first attempt:

Ltac iff_split H :=
  match type of H with
  | forall x y, ?A <-> ?B =>
    let Hr := fresh H "r" in
    let Hl := fresh H "l" in
    assert (Hr : forall x y, A -> B) by (apply H);
    assert (Hl : forall x y, B -> A) by (apply H);
    clear H
  end.

It works only for a fixed number of quantifiers (in this case just 2), but I want to extend it to accept an arbitrary list of them.

How can I achieve this?

英文:

I'm trying to write a--my first--Coq tactic.
It should split forall x y z ..., A &lt;-&gt; B into two: forall x y z ..., A -&gt; B and forall x y z ..., B -&gt; A.

This is my first attempt:

Ltac iff_split H :=
  match type of H with
  | forall x y, ?A &lt;-&gt; ?B =&gt;
    let Hr := fresh H &quot;r&quot; in
    let Hl := fresh H &quot;l&quot; in
    assert (Hr : forall x y, A -&gt; B) by (apply H);
    assert (Hl : forall x y, B -&gt; A) by (apply H);
    clear H
  end.

It works only for a fixed number of quantifiers (in this case just 2), but I want to extend it to accept an arbitrary list of them.

How can I achieve this?

答案1

得分: 1

这个答案使用了一个技巧(仅供专家使用 😄)由Adam Chlipala提出。

不清楚的话,请随时要求更多解释。

Ltac 不允许进入绑定器,但你可以通过折叠量词来欺骗它。

让我们以 forall x y, x + y = 0 为例,这是一个嵌套的全称量化。你可以将它折叠成 forall p, fst p + snd p = 0,这是一个简单的量化。如果你可以任意折叠和展开嵌套的量词,那么你就完成了:你折叠,执行你的转换,然后展开。

以下是执行这一操作的代码:

Ltac fold_forall f :=
  let rec loop F := 
    match F with
      | forall x y, @?body x y =&gt; 
          let v := (eval cbv beta in (forall t, body (fst t) (snd t))) in
          loop v 
      |  _ =&gt; F
    end 
  in  loop (forall _ : unit, f).

Ltac unfold_forall f :=
  let rec loop F := 
    match F with
      | forall t : _ * _, @?body t =&gt;
         let v := (eval cbv beta in (forall x y, (body (x, y)))) in
         loop v
      |  _ =&gt; match eval simpl in F with
              | _ -&gt; ?G =&gt; G 
              end
    end 
  in loop f.

Ltac mk_left f :=
   match f with
    | forall x : ?T, ?A &lt;-&gt; ?B =&gt; constr:(forall x : T, A -&gt; B)
   end.

Ltac mk_right f :=
   match f with
    | forall x : ?T, ?A &lt;-&gt; ?B =&gt; constr:(forall x : T, B -&gt; A)
   end.

Ltac my_tac  H := 
 match type of H with
 | ?v =&gt; let v1 := fold_forall v in 
         let v2 := mk_left v1 in
         let v3 := unfold_forall v2 in
         let v4 := mk_right v1 in
         let v5 := unfold_forall v4 in 
         assert v3 by apply H;
         assert v5 by apply H
 end.

Goal (forall x y z : nat, (x = z) &lt;-&gt; (z = y)) -&gt; False.
intros H.
my_tac H.

这是执行该操作的代码。

英文:

This answer uses a trick (for expert only 😊) due to Adam Chlipala.
Don't hesitate to ask for more explanation if something is unclear.

Ltac does not allow to go under binder but you can trick it by
folding the quantifiers.
Let us take forall x y, x + y = 0 that is a nested universal quantification.
You can fold it in into forall p, fst p + snd p = 0 that is a simple quantification. If you can arbitrary fold and unfold nested quantifications, you are done: you fold, perform your transformation then unfold.

Here is the code that does the trick

Ltac fold_forall f :=
  let rec loop F := 
    match F with
      | forall x y, @?body x y =&gt; 
          let v := (eval cbv beta in (forall t, body (fst t) (snd t))) in
          loop v 
      |  _ =&gt; F
    end 
  in  loop (forall _ : unit, f).

Ltac unfold_forall f :=
  let rec loop F := 
    match F with
      | forall t : _ * _, @?body t =&gt;
         let v := (eval cbv beta in (forall x y, (body (x, y)))) in
         loop v
      |  _ =&gt; match eval simpl in F with
              | _ -&gt; ?G =&gt; G 
              end
    end 
  in loop f.

Ltac mk_left f :=
   match f with
    | forall x : ?T, ?A &lt;-&gt; ?B =&gt; constr:(forall x : T, A -&gt; B)
   end.

Ltac mk_right f :=
   match f with
    | forall x : ?T, ?A &lt;-&gt; ?B =&gt; constr:(forall x : T, B -&gt; A)
   end.

Ltac my_tac  H := 
 match type of H with
 | ?v =&gt; let v1 := fold_forall v in 
         let v2 := mk_left v1 in
         let v3 := unfold_forall v2 in
         let v4 := mk_right v1 in
         let v5 := unfold_forall v4 in 
         assert v3 by apply H;
         assert v5 by apply H
 end.

Goal (forall x y z : nat, (x = z) &lt;-&gt; (z = y)) -&gt; False.
intros H.
my_tac H.

huangapple
  • 本文由 发表于 2023年5月7日 18:10:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/76193268.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定