mehrere Erfolge bei Coq-Verzweigungen und Backtracking?

Question

Ich habe Probleme, das Konzept von multiple successes in Coq (8.5p1, ch9.2) Verzweigung und Backtracking-Verhalten zu verstehen. Zum Beispiel aus der Dokumentation:

Backtracking Verzweigung

Wir sind mit der folgenden Struktur verzweigen:

ausdr1 + expr2

Taktik kann mit mehreren Erfolgen zu sehen. Wenn eine Taktik fehlschlägt fragt es nach mehr Erfolgen der vorherigen Taktik. expr1 + expr2 hat alle die Erfolge von v1 gefolgt von allen Erfolgen von v2.

Was ich nicht verstehe, ist, warum brauchen wir in erster Linie mehrere Erfolge? Ist nicht ein Erfolg gut genug, um einen Beweis zu beenden?

Auch aus der Dokumentation, so scheint es, dass es weniger kostspielig Verzweigungs Regeln sind, die irgendwie „voreingenommen“ sind, einschließlich

first [ expr1 | ::: | exprn ] 

und

expr1 || expr2 

Warum wir die kostspieligere Option brauchen + und nicht immer die letzteren, effizientere taktische?

Answer 1

Das Problem ist, dass Sie manchmal versuchen, ein Ziel zu entlasten, aber weitere Teilziele könnten zu einer Lösung führen, von der Sie dachten, dass sie funktionieren würde, um abgelehnt zu werden. Wenn Sie alle Erfolge gesammelt haben, können Sie zu einer beliebigen Stelle zurückkehren, wo Sie eine falsche Entscheidung getroffen haben, und einen anderen Zweig des Suchbaums erkunden.

Hier ist ein dummes Beispiel. Lassen Sie uns sagen, dass ich dieses Ziel beweisen möchte:

Goal exists m, m = 1. 

Nun, es ist ein ziemlich einfaches Ziel ist so das ich konnte es manuell tun, aber lassen Sie es nicht. Lassen Sie uns eine Taktik schreiben, die, wenn sie mit einer exists konfrontiert wird, alle möglichen natürlichen Zahlen versucht. Wenn ich schreibe:

Ltac existNatFrom n := 
    exists n || existNatFrom (S n). 

Ltac existNat := existNatFrom O. 

dann, sobald ich existNat ausgeführt haben, verpflichtet sich das System auf die erste erfolgreiche Wahl. Das bedeutet insbesondere, dass ich trotz der rekursiven Definition von existNatFrom beim Aufruf existNat immer O und nur O bekomme.

Das Ziel kann nicht gelöst werden:

Goal exists m, m = 1. 
    Fail (existNat; reflexivity). 
Abort. 

Auf der anderen Seite, wenn ich (+) statt (||) verwendet wird, werde ich durch alle möglichen natürlichen Zahlen geht (in einem faulen Weise durch Rückzieher verwenden). So schreibt:

Ltac existNatFrom' n := 
    exists n + existNatFrom' (S n). 

Ltac existNat' := existNatFrom' O. 

bedeutet, dass ich jetzt das Ziel, unter Beweis stellen können:

Goal exists m, m = 1. 
    existNat'; reflexivity. 
Qed.