Dlaczego cewki indukcyjne muszą mieć te same parametry?

Question

Po , zmieniłem moją relację Fixpoint do wzajemnej relacji Inductive, która "buduje" różne porównania między grami, zamiast "wiercić w dół".

Ale teraz jestem otrzymaniu całkowicie nowy komunikat o błędzie:

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

Myślę, że komunikat o błędzie mówiąc, że muszę te same dokładne parametry dla wszystkich tych wspólnych definicji indukcyjnych.

Zdaję sobie sprawę, że istnieją proste sposoby na obejście tego problemu (nieużywane zmienne typu dummy, długie typy funkcjonalne ze wszystkim wewnątrz forall), ale nie rozumiem, dlaczego powinienem.

Czy ktoś może wyjaśnić logikę tego ograniczenia wzajemnych typów indukcyjnych? Czy istnieje bardziej elegancki sposób na napisanie tego? Czy to ograniczenie implikuje również, że indukcyjne wywołania do siebie muszą używać tych samych parametrów (w którym to przypadku nie znam żadnych hacków oprócz ohydnych ilości powielania kodu)?

(Definicje wszystkich rodzajach i kategoriach, takich jak compare_quest, gry, g1side itp pozostają niezmienione od tego, co było w moim first question.

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). 

W CGT, zazwyczaj dwóch graczy (o nazwie Left i Right) na zmianę gry, w której gracz wygrywa ostatni ruch Każda gra (czyli każda pozycja w grze) może być odczytana jako zestaw opcji Left i zestaw Right opcji zapisanych jako {G_L | G_R}. porównując dwie gry, można je porównać na cztery różne sposoby: <, >, = lub ||.

Gra jest A < B, jeśli B jest ściśle lepsza niż A dla Left, niezależnie od tego, kto pierwszy. A > B, jeśli A jest lepsze niż B dla Left. A = B, jeśli dwie gry są równoważne (w tym sensie, że suma gier A + -B jest grą zero, tak że gracz, który jako pierwszy przegrywa). I, A || B, która gra jest lepsza dla Left, zależy od tego, kto pierwszy.

Jednym ze sposobów, aby sprawdzić porównanie dwóch gier jest następujący:

• A <= B jeśli wszystkie A „s Left dzieci są <| B i A <| wszystkich B” Prawo dzieci s.

• A <| B jeśli A ma prawo dziecka, które jest <= B czy A <= któregokolwiek z lewych dzieci B „s.

• I podobnie dla >= i >|.

Tak więc widząc, która para tych stosunków zastosowanie do dwóch gier A i B, jest to możliwe do ustalenia, czy A < B (A<=B i A<|B), A=B (A<=B i A>=B) A > B (A>=B i A>|B) lub A || B (A<|B i A>|B).

Oto wiki article on CGT.

Answer 1

To ograniczenie jest bardzo interesujące i nigdy wcześniej nie spotkałem się z tym ograniczeniem. Nie widzę powodu, dla którego ten fragment kodu powinien zostać odrzucony. Moim najlepszym rozwiązaniem jest to, że kiedy ludzie projektowali podstawy Coqa, to ograniczenie ułatwiło wykonanie niektórych dowodów, a ponieważ niewielu ludzi było zirytowanych, po prostu tak pozostało. Mogłem się jednak całkowicie mylić; Wiem, że parametry i argumenty (tj. Te, które przechodzą na prawo od strzałki) są traktowane nieco inaczej dla niektórych rzeczy. Na przykład ograniczenia wszechświata nałożone podczas definiowania typów indukcyjnych są mniej restrykcyjne z parametrami w porównaniu z argumentami.

Być może to powinno być przekazane na listę dyskusyjną Coq Club? :)

Nie musisz umieszczać wszystkiego na prawo od strzałki, aby to działało. Jedną rzeczą, którą możesz zrobić, to umieścić po prawej stronie wszystko oprócz parametru compare_quest. Podczas korzystania z indukcyjnym tego samego typu jesteś określającej w konstruktorze parametr podać nie musi być taka sama jak ta, którą daje w nagłówku, tak to jest 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). 

Niestety , starając się ocenić ten daje nowy błąd :(

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". 

tego błędu jest znacznie bardziej powszechne w Coq. jest narzekają, że są przechodzącą typu definiowanej jako argument do cbn bo to może spowodować, że typ będący po lewej stronie strzałki (zdarzenie ujemne), o którym wiadomo, że prowadzi do logicznego nconsistencies.

I myślę, że można pozbyć się tego problemu, inlining compareCombiner w konstruktorach ostatnich trzech typów, co może wymagać pewnego refaktoryzacji kodu. Znowu jestem przekonany, że musi istnieć lepszy sposób na zdefiniowanie tego, ale nie rozumiem, co próbujesz zrobić bardzo dobrze, więc moja pomoc jest tam trochę ograniczona.

UPDATE: Zacząłem serię artykułów na temat formalizacji niektórych CGT w Coq. Możesz znaleźć pierwszy here.