Kiedy narzędzie do sprawdzania zakończenia redukuje dostęp do rekordu

Question

Potykam się o zachowanie sprawdzania terminatora Coq, którego sam nie potrafię wyjaśnić. Rozważmy:

Require Import Coq.Lists.List. 

Record C a := { P : a -> bool }. 

Arguments P {_}. 

Definition list_P {a} (a_C : C a) : list a -> bool := existsb (P a_C). 

Definition list_C {a} (a_C : C a) : C (list a) := {| P := list_P a_C |}. 

(* Note that *) 
Eval cbn in  fun a C => (P (list_C C)). 
(* evaluates to: fun a C => list_P C *) 

Inductive tree a := Node : a -> list (tree a) -> tree a. 

(* Works, using a local record *) 
Fixpoint tree_P1 {a} (a_C : C a) (t : tree a) : bool := 
    let tree_C := Build_C _ (tree_P1 a_C) in 
    let list_C' := Build_C _ (list_P tree_C) in 
    match t with Node _ x ts => orb (P a_C x) (P list_C' ts) end. 

(* Works too, using list_P directly *) 
Fixpoint tree_P2 {a} (a_C : C a) (t : tree a) : bool := 
    let tree_C := Build_C _ (tree_P2 a_C) in 
    match t with Node _ x ts => orb (P a_C x) (list_P tree_C ts) end. 

(* Does not work, using a globally defined record. Why not? *) 
Fixpoint tree_P3 {a} (a_C : C a) (t : tree a) : bool := 
    let tree_C := Build_C _ (tree_P3 a_C) in 
    match t with Node _ x ts => orb (P a_C x) (P (list_C tree_C) ts) end. 

Pierwszy i Drugi przykład pokazuje, że gdy próbuje zrozumieć czy fixpoint jest zakończenie, Coq jest w stanie rozwiązać rekordowe akcesorów, w zasadzie oceny co pisaliśmy w tree_P1 co pisaliśmy w tree_P2.

Ale wydaje się, że działa tylko wtedy, gdy rekord jest zbudowany lokalnie (let tree_C :=…), a nie, jeśli jest zdefiniowany przy użyciu Definition.

Ale Fixpoint może dokładnie przejrzeć inne definicje, np. przez list_P. Co jest specjalnego w nagraniach i czy mogę sprawić, aby Coq zaakceptował tree_P3?

Answer 1

Po pewnym czytania sprawdzający wypowiedzenia w Coq, myślę, że znalazłem rozwiązanie:

Kontrolujący zakończenie zawsze rozwijają lokalne definicje i beta-redukcji. Dlatego działa tree_P1.

Kontrolujący rozwiązanie będzie również, w razie potrzeby, rozwijać definicje, które nazywane są (jak list_C', P, existsb), dlatego tree_P2 prace.

Narzędzie do sprawdzania zakończenia terapii nie rozwiąże jednak definicji, które można zastosować w klauzuli match … with, na przykład list_C. Oto minimalne przykładem, że:

(* works *) 
Fixpoint foo1 (n : nat) : nat := 
    let t := Some True in 
    match Some True with | Some True => 0 
         | None => foo1 n end. 

(* works *) 
Fixpoint foo2 (n : nat) : nat := 
    let t := Some True in 
    match t with | Some True => 0 
       | None => foo2 n end. 

(* does not work *) 
Definition t := Some True. 

Fixpoint foo3 (n : nat) : nat := 
    match t with | Some True => 0 
       | None => foo3 n end. 

obejście dla oryginalnego kodu jest upewnienie się, że wszystkie definicje nazywane są (a nie wzór dopasowane przeciw), aby upewnić się, że kontroler zakończenie będzie je rozwijać . Możemy to zrobić poprzez przełączenie do stylu kontynuacja Podania:

Require Import Coq.Lists.List. 

Record C_dict a := { P' : a -> bool }. 

Definition C a : Type := forall r, (C_dict a -> r) -> r. 

Definition P {a} (a_C : C a) : a -> bool := 
    a_C _ (P' _). 

Definition list_P {a} (a_C : C a) : list a -> bool := existsb (P a_C). 

Definition list_C {a} (a_C : C a) : C (list a) := 
    fun _ k => k {| P' := list_P a_C |}. 

Inductive tree a := Node : a -> list (tree a) -> tree a. 

(* Works now! *) 
Fixpoint tree_P1 {a} (a_C : C a) (t : tree a) : bool := 
    let tree_C := fun _ k => k (Build_C_dict _ (tree_P1 a_C)) in 
    match t with Node _ x ts => orb (P a_C x) (P (list_C tree_C) ts) end. 

To działa nawet z klas typu, jak rozdzielczość klasa typ jest indepenent z tych zagadnień:

Require Import Coq.Lists.List. 

Record C_dict a := { P' : a -> bool }. 

Definition C a : Type := forall r, (C_dict a -> r) -> r. 
Existing Class C. 

Definition P {a} {a_C : C a} : a -> bool := a_C _ (P' _). 

Definition list_P {a} `{C a} : list a -> bool := existsb P. 

Instance list_C {a} (a_C : C a) : C (list a) := 
    fun _ k => k {| P' := list_P |}. 

Inductive tree a := Node : a -> list (tree a) -> tree a. 

(* Works now! *) 
Fixpoint tree_P1 {a} (a_C : C a) (t : tree a) : bool := 
    let tree_C : C (tree a) := fun _ k => k (Build_C_dict _ (tree_P1 a_C)) in 
    match t with Node _ x ts => orb (P x) (P ts) end. 

Answer 2

Na pytanie 1. Uważam, że w tree_P1 definicja instancji klasy znajduje się w konstrukcji fix i jest zmniejszana w momencie sprawdzania zakończenia.

Poniższa definicja została odrzucona, jak słusznie wskazuje.

Fixpoint tree_P1' {a} `{C a} (t : tree a) : bool := 
    let tree_C := Build_C _ tree_P1' in 
    match t with Node _ x ts => orb (P x) (@P _ (* mark *) _ ts) end. 

W tej definicji, instancja klasy potrzebne po komentarzu (* mark *) jest wypełniona przez definicję masz na linii 7. Ale ta definicja mieszka poza fix konstruktem i nie zostanie zmniejszona przez sprawdzający zakańczania w taki sam sposób. W rezultacie wystąpienie tree_P1', które nie zostanie zastosowane do żadnego argumentu drzewa, pozostanie w kodzie, a sprawdzanie zakończenia nie będzie w stanie określić, że to wystąpienie jest używane tylko w przypadku argumentów mniejszych niż początkowy argument.

To jest dzikie domysły, ponieważ nie możemy zobaczyć treści funkcji, która jest odrzucana.