Wird eine Person bestraft, indem 'self_relation' (und möglicherweise andere Bibliotheksdefinitionen) verwendet wird?

Question

Mit jeder gegebenen Programmiersprache sollten wir immer dann, wenn eine Standardbibliotheksfunktion existiert, diese verwenden, anstatt unseren eigenen Code zu schreiben. Man könnte meinen, dass dieser Rat auch für Coq gilt. Allerdings zwang ich mich kürzlich, das same_relation Prädikat des Relation Moduls zu verwenden, und mir bleibt das Gefühl, schlechter dran zu sein. Also muss mir etwas fehlen, daher meine Frage. Um zu zeigen, was ich meine lassen Sie uns auf mögliche Beziehungen betrachten:

Require Import Relations.  (* same_relation *) 
Require Import Setoids.Setoid. (* seems to be needed for rewrite *) 

Inductive rel1 {A:Type} : A -> A -> Prop := 
    | rel1_refl : forall x:A, rel1 x x. (* for example *) 

Inductive rel2 {A:Type} : A -> A -> Prop := 
    | rel2_refl : forall x:A, rel2 x x. (* for example *) 

Die spezifischen Details dieser Beziehungen spielen hier keine Rolle, solange rel1 und rel2 gleichwertig sind. Nun, wenn ich will die Coq Bibliothek ignorieren, ich konnte einfach Zustand:

Lemma L1: forall (A:Type)(x y:A), rel1 x y <-> rel2 x y. 
Proof. 
    (* some proof *) 
Qed. 

und wenn ich will mein Instinkt folgen und die Coq Bibliothek verwenden:

Lemma L2: forall (A:Type), same_relation A rel1 rel2. 
Proof. 
    (* some proof *) 
Qed. 

Im einfachsten Fall, es scheint, dass L1 oder Lemma L2 Lemma bewiesen zu haben, ist gleichermaßen von Vorteil:

Lemma application1: forall (A:Type) (x y:A), 
    rel1 x y -> rel2 x y (* for example *) 
Proof. 
    intros A x y H. apply L1 (* or L2 *) . exact H. 
Qed. 

Ob ich entscheiden apply L1 oderzu verwendenmacht keinen Unterschied ...

jedoch in der Praxis werden wir wahrscheinlich mit einem komplizierteren Ziel konfrontiert werden:

Lemma application2: forall (A:Type) (x y:A) (p:Prop), 
    p /\ rel1 x y -> p /\ rel2 x y. 
Proof. 
    intros A x y p H. rewrite <- L1. exact H. 
Qed. 

Mein Punkt hier ist, dass rewrite <- L1 durch rewrite <- L2 ersetzt wird fehlschlagen. Dies gilt auch für das vorherige Beispiel, aber ich konnte zumindest apply statt rewrite verwenden. Ich kann apply in diesem Fall nicht verwenden (es sei denn, ich mache mir die Mühe, mein Ziel zu teilen). So scheint es, dass ich den Komfort der Verwendung von rewrite verloren habe, wenn ich nur Lemma L2 habe.

Mit rewrite auf Ergebnisse, die eine Äquivalenz (nicht nur eine Gleichheit) sind, ist sehr bequem. Es scheint, dass das Einwickeln einer Äquivalenz in das Prädikat same_relation diese Bequemlichkeit wegnimmt. Habe ich Recht, meinem Instinkt zu folgen und mich dazu zu zwingen, same_relation zu verwenden? Allgemeiner ist es so wahr, dass wenn ein Konstrukt in der Standard-Coq-Bibliothek definiert ist, ich es verwenden sollte, anstatt meine eigene Version davon zu definieren?

Answer 1

Sie zwei Fragen stellen, ich versuche, separat zu beantworten:

• In Bezug auf Ihrem Rewrite-Problem, wird dieses Problem wie die Definition von same_relation geht als Doppel Aufnahme natürlich ist. Ich stimme zu, dass eine Definition, die verwendet, vielleicht bequemer wäre. Es hängt wirklich von der Art der Ziele ab, die Sie haben. Eine mögliche Lösung für Ihr Problem ist es, eine Ansicht zu definieren:

  Lemma L1 {A:Type} {x y:A} : rel1 x y <-> rel2 x y. 
  Proof. 
  Admitted. 
  
  Lemma L2 {A:Type} : same_relation A rel1 rel2. 
  Proof. 
  Admitted. 
  
  Lemma U {T} {R1 R2 : relation T} : 
      same_relation _ R1 R2 -> forall x y, R1 x y <-> R2 x y. 
  Proof. now destruct 1; intros x y; split; auto. Qed. 
  
  Lemma application2 {A:Type} {x y:A} {p:Prop} : 
      p /\ rel1 x y -> p /\ rel2 x y. 
  Proof. now rewrite (U L2). Qed. 
  

  Beachten Sie auch, dass mit einer <-> Beziehung Umschreiben wirklich nicht auf Gleichheit, sondern auf „setoid Umschreiben“. Tatsächlich gilt das Folgende nicht in Coq A <-> B -> A = B.

• In Bezug auf Ihre zweite Frage ist die Verwendung der Coq-Standardbibliothek ein sehr subjektives Thema.Ich persönlich benutze es selten, ich bevorzuge eine andere Bibliothek namens math-comp, aber YMMV. In Bezug auf Relationen ist mathcomp hauptsächlich auf boolesche Relationen spezialisiert rel x y = x -> y -> bool, daher wird Äquivalenz einfach als Gleichheit definiert, typischerweise geben r1 r2 Sie schreiben r1 =2 r2.

  IMHO am Ende sind solche Entscheidungen stark abhängig von Ihrer Anwendungsdomäne.

[Bearbeiten]: Beachten Sie, dass die Relation Bibliothek datiert ist:

Naive Mengenlehre in Coq. Coq V6.1. Diese Arbeit wurde im Juli 1993 von F. Prost begonnen.

In der Tat kann es nicht die beste moderne Basis sein, um Coq Entwicklungen auf zu bauen.