Warum müssen coq gegenseitig induktive Typen die gleichen Parameter haben?

Question

Nach Arthur's suggestion, änderte ich meine Fixpoint Beziehung zu einer gegenseitigen Inductive Beziehung, die die verschiedenen Vergleiche zwischen Spielen "aufbaut" anstatt "bohrend".

Aber jetzt habe ich eine völlig neue Fehlermeldung erhalte:

Error: Parameters should be syntactically the same for each inductive type. 

denke ich, wird die Fehlermeldung, dass ich die gleichen genauen Parameter für alle diese gegenseitige induktive Definitionen benötigen.

Ich realisiere, es gibt einfache Hacks um dies zu umgehen (unbenutzte Dummy-Variablen, lange Funktionstypen mit allem innerhalb der forall), aber ich sehe nicht, warum ich sollte.

Kann jemand die Logik hinter dieser Einschränkung gegenseitiger induktiver Typen erklären? Gibt es einen eleganteren Weg dies zu schreiben? Bedeutet diese Einschränkung auch, dass die induktiven Aufrufe zueinander die gleichen Parameter verwenden müssen (in diesem Fall kenne ich keine Hacks, die scheußliche Mengen an Code-Duplizierung speichern)?

(Die Definitionen aller Typen und Begriffe wie compare_quest, Spiel, g1side etc. sind unverändert von dem, was sie in meinem first question waren.

Inductive gameCompare (c : compare_quest) : game -> game -> Prop := 
| igc : forall g1 g2 : game, 
    innerGCompare (nextCompare c) (compareCombiner c) (g1side c) (g2side c) g1 g2 -> 
    gameCompare c g1 g2 
with innerGCompare (next_c : compare_quest) (cbn : combiner) (g1s g2s : side) 
    : game -> game -> Prop := 
| compBoth : forall g1 g2 : game, 
    cbn (listGameCompare next_c cbn (g1s g1) g2) 
     (gameListCompare next_c cbn g1 (g2s g2)) -> 
    innerGCompare next_c cbn g1s g2s g1 g2 
with listGameCompare (c : compare_quest) (cbn : combiner) : gamelist -> game -> Prop := 
| emptylgCompare : cbn_init cbn -> forall g2 : game, listGameCompare c cbn emptylist g2 
| otlgCompare : forall (g1_cdr : gamelist) (g1_car g2 : game), 
    (cbn (listGameCompare c cbn g1_cdr g2) (gameCompare c g1_car g2)) -> 
    listGameCompare c cbn (listCons g1_car g1_cdr) g2 
with gameListCompare (c : compare_quest) (cbn : combiner) : game -> gamelist -> Prop := 
| emptyglCompare : cbn_init cbn -> forall g1 : game, gameListCompare c cbn g1 emptylist 
| otglCompare : forall (g1 g2_car : game) (g2_cdr : gamelist), 
    (cbn (gameListCompare c cbn g1 g2_cdr) (gameCompare c g1 g2_car)) -> 
    gameListCompare c cbn g1 (listCons g2_car g2_cdr). 

In CGT, in der Regel zwei Spieler (genannt Left und Right) Wendet abwechselnd ein Spiel an, in dem der Spieler, der den letzten Zug macht, gewinnt.Jedes Spiel (dh jede Position in einem Spiel) kann als eine Reihe von Left Optionen und einer Reihe von Right Optionen gelesen werden, geschrieben als {G_L | G_R} Wenn Sie zwei Spiele vergleichen, können Sie auf vier verschiedene Arten vergleichen: <, >, = oder ||.

Ein Spiel ist A < B wenn B ist strikt besser als A für Left, unabhängig davon, wer zuerst geht. A > B wenn A ist besser als B für Left. A = B wenn die beiden Spiele gleichwertig sind (in dem Sinne, dass die Summe der Spiele A + -B ein Null-Spiel ist, so dass der Spieler, der zuerst geht, verliert). Und, A || B ob das Spiel besser ist für Left hängt davon ab, wer zuerst geht.

Eine Möglichkeit, den Vergleich zwischen zwei Spiele zu prüfen ist, wie folgt:

• A <= B wenn alle A Recht Kinder s Left Kinder <| B und A <| alle B sind ".

• A <| B wenn A hat ein Recht Kind, das <= B oder wenn A <= ein B ‚s linker Kinder.

• Und ähnlich für >= und >|.

So, dann durch Sehen, das Paar dieser Beziehungen zu zwei Spielen gelten A und B, dann ist es möglich, zu bestimmen, ob A < B (A<=B und A<|B), A=B (A<=B und A>=B), A > B (A>=B und A>|B) oder A || B (A<|B und A>|B).

Hier ist die wiki article on CGT.

Answer 1

Diese Einschränkung ist sehr interessant, und ich hatte es noch nie zuvor gesehen. Ich sehe keine Gründe dafür, warum dieser Code abgelehnt werden sollte. Meine beste Wette ist, dass, als die Leute die Grundlagen von Coq entwarfen, diese Einschränkung einige der Beweise leichter machte, und da sich nicht viele Leute darüber ärgerten, blieb es einfach so. Ich könnte jedoch völlig falsch liegen. Ich weiß, dass Parameter und Argumente (d. H. Diejenigen, die nach rechts von dem Pfeil gehen) für einige Dinge leicht unterschiedlich behandelt werden. Zum Beispiel sind die Universumsbedingungen, die bei der Definition von induktiven Typen auferlegt werden, weniger restriktiv bei Parametern im Vergleich zu Argumenten.

Vielleicht sollte dies an die Coq Club Mailingliste weitergeleitet werden? :)

Sie müssen nicht alles auf der rechten Seite des Pfeils setzen, um dies zum Funktionieren zu bringen. Eine Sache, die Sie tun können, ist, alles außer dem compare_quest Parameter nach rechts zu setzen. Wenn Sie eine induktive des gleichen Typs verwenden Sie in einem Konstruktor definiert, wobei die Parameter Sie geben muss nicht wie die das gleiche sein, das Sie auf die Überschrift geben, so das ist OK:

Inductive gameCompare (c : compare_quest) : game -> game -> Prop := 
| igc : forall g1 g2 : game, 
    innerGCompare (nextCompare c) (compareCombiner c) (g1side c) (g2side c) g1 g2 -> 
    gameCompare c g1 g2 

with innerGCompare (c : compare_quest) : combiner -> side -> side -> 
    game -> game -> Prop := 
| compBoth : forall cbn g1s g2s (g1 g2 : game), 
    cbn (listGameCompare c cbn (g1s g1) g2) 
     (gameListCompare c cbn g1 (g2s g2)) -> 
    innerGCompare c cbn g1s g2s g1 g2 

with listGameCompare (c : compare_quest) : combiner -> gamelist -> game -> Prop := 
| emptylgCompare : forall cbn, cbn_init cbn -> forall g2 : game, listGameCompare c cbn emptylist g2 
| otlgCompare : forall cbn (g1_cdr : gamelist) (g1_car g2 : game), 
    (cbn (listGameCompare c cbn g1_cdr g2) (gameCompare c g1_car g2)) -> 
    listGameCompare c cbn (listCons g1_car g1_cdr) g2 

with gameListCompare (c : compare_quest) : combiner -> game -> gamelist -> Prop := 
| emptyglCompare : forall cbn, cbn_init cbn -> forall g1 : game, gameListCompare c cbn g1 emptylist 
| otglCompare : forall cbn (g1 g2_car : game) (g2_cdr : gamelist), 
    (cbn (gameListCompare c cbn g1 g2_cdr) (gameCompare c g1 g2_car)) -> 
    gameListCompare c cbn g1 (listCons g2_car g2_cdr). 

Leider Dies zu bewerten versucht gibt einen neuen Fehler :(

Error: Non strictly positive occurrence of "listGameCompare" in 
"forall (cbn : Prop -> Prop -> Prop) (g1s g2s : game -> gamelist) 
    (g1 g2 : game), 
    cbn (listGameCompare c cbn (g1s g1) g2) (gameListCompare c cbn g1 (g2s g2)) -> 
    innerGCompare c cbn g1s g2s g1 g2". 

Dieser Fehler viel häufiger in Coq ist. Es beschwert sich, dass Sie die Art sind vorbei Sie als Argument an cbn definieren, denn das, dass führen könnte Typ ist zu links eines Pfeils (ein negatives Vorkommen), die bekanntermaßen zu logischen i führt Nichtkonsistenzen.

ich denken Sie dieses Problem loswerden kann durch inlining compareCombiner in den Konstrukteuren der letzten drei Typen, die einige Umgestaltung des Codes erfordern. Ich bin mir ziemlich sicher, dass es einen besseren Weg geben muss, dies zu definieren, aber ich verstehe nicht, was Sie sehr gut machen wollen, deshalb ist meine Hilfe dort etwas eingeschränkt.

UPDATE: Ich habe eine Reihe von Artikeln über die Formalisierung einiger CGT in Coq gestartet. Sie können die erste here finden.