Làm thế nào để đặt hoặc Loại coq là đề xuất

Question

Tôi đang đọc hướng dẫn về Coq. Nó xây dựng một loại bool như sau:

Coq < Inductive bool : Set := true | false. 
bool is defined 
bool_rect is defined 
bool_ind is defined 
bool_rec is defined 

Sau đó, nó cho thấy những gì mỗi người trong số những điều này đang sử dụng "Kiểm tra".

Coq < Check bool_ind. 
bool_ind 
    : forall P : bool -> Prop, P true -> P false -> forall b : bool, P b 

Coq < Check bool_rec. 
bool_rec 
    : forall P : bool -> Set, P true -> P false -> forall b : bool, P b 

Coq < Check bool_rect. 
bool_rect 
    : forall P : bool -> Type, P true -> P false -> forall b : bool, P b 

Tôi hiểu bool_ind. Nó nói rằng nếu một cái gì đó giữ cho true và nó giữ cho false, sau đó nó giữ cho tất cả b trong bool (vì đó là hai chỉ).

Nhưng tôi không hiểu ý nghĩa của cụm từ bool_rec hoặc bool_rect. Dường như là P true (là Set cho bool_rec và Type cho bool_rect) đang được coi là giá trị mệnh đề. Tôi đang thiếu gì ở đây?

Answer 1

Trực giác của bạn cho bool_ind là điểm trên, nhưng suy nghĩ về lý do tại sao bool_ind có nghĩa là những gì bạn nói có thể giúp làm rõ hai cách còn lại. Chúng ta biết rằng

bool_ind : forall P : bool -> Prop, 
      P true -> 
      P false -> 
      forall b : bool, 
       P b 

Nếu chúng ta đọc này như một công thức hợp lý, chúng tôi có được đọc cùng bạn đã làm:

• Đối với mỗi vị P trên bool eans,
  • Nếu P true giữ, và
  • Nếu P false giữ, sau đó
  • Đối với mỗi boolean b,
    • P b giữ.

Nhưng điều này không chỉ là một công thức hợp lý, đó là một loại. Cụ thể, đó là một loại hàm (phụ thuộc). Và như một loại chức năng, nó nói (nếu bạn cho phép tôi mạn phép phát minh ra tên cho các đối số vô danh và kết quả):

• Cho một giá trị P : bool -> Prop,
  • Một giá trị Pt : P true,
  • một giá trị Pf : P false, và
  • một giá trị b : bool,
    • Chúng tôi có thể xây dựng một giá trị Pb : P b.

(Tất nhiên, đây là một chức năng cà ri, vì vậy có những cách khác để phá vỡ các loại thành văn xuôi, nhưng điều này là rõ ràng nhất cho mục đích của chúng tôi.)

Điều quan trọng ở đây, điều khiến Coq hoạt động như một định lý ngữ trong khi là ngôn ngữ lập trình (hoặc ngược lại) là Curry-Howard correspondence: loại là mệnh đề và giá trị là bằng chứng của các mệnh đề đó. Ví dụ, kiểu hàm đơn giản -> tương ứng với hàm ý, và kiểu hàm phụ thuộc forall tương ứng với định lượng phổ dụng. Vì vậy, trong Coq, để chứng minh rằng φ → ψ, chúng ta phải xây dựng một giá trị kiểu φ -> ψ: một hàm nhận giá trị loại φ (hoặc nói cách khác, một bằng chứng của đề xuất φ) và sử dụng nó để xây dựng một giá trị của loại ψ (một bằng chứng của đề xuất ψ).

Trong Coq, chúng tôi có thể nghĩ về tất cả các loại theo cách này, cho dù các loại đó có nằm trong số Set, Type hoặc Prop hay không. (Vì vậy, khi bạn nói "Có vẻ như P đúng (là một Set cho bool rec và một Type cho bool_rect) đang được coi như là một giá trị mệnh đề," bạn nói đúng!) Ví dụ, chúng ta hãy xem xét cách chúng ta thực hiện bool_ind chính chúng ta. Chúng tôi sẽ bắt đầu bằng cách liệt kê tất cả các tham số cho hàm, cùng với loại trả về của nó, cùng với kiểu trả về:

Definition bool_ind' (P : bool -> Prop) 
        (Pt : P true) 
        (Pf : P false) 
        (b : bool) 
        : P b := 

Cho đến giờ, rất tốt. Tại thời điểm này, chúng tôi muốn trả về một cái gì đó loại P b, nhưng chúng tôi không biết những gì b là. Vì vậy, như thường lệ trong các trường hợp này, chúng tôi khớp mẫu:

match b with 

Hiện tại có hai trường hợp. Trước tiên, b có thể là true. Trong trường hợp này, chúng ta phải trả về một cái gì đó kiểu P true, và may mắn chúng ta có một giá trị như vậy: Pt.

| true => Pt 

Trường hợp false cũng tương tự như:

| false => Pf 
    end. 

Lưu ý rằng khi chúng ta thực hiện bool_ind', nó không trông rất "proofy", nhưng thay vì rất "programmy". Tất nhiên, nhờ sự tương ứng của Curry-Howard, chúng giống nhau. Nhưng lưu ý rằng việc thực hiện rất giống nhau sẽ đủ cho hai chức năng khác:

Definition bool_rec' (P : bool -> Set) 
        (Pt : P true) 
        (Pf : P false) 
        (b : bool) 
        : P b := 
    match b with 
    | true => Pt 
    | false => Pf 
    end. 

Definition bool_rect' (P : bool -> Type) 
         (Pt : P true) 
         (Pf : P false) 
         (b : bool) 
         : P b := 
    match b with 
    | true => Pt 
    | false => Pf 
    end. 

Nhìn vào định nghĩa tính toán này cho thấy một cách khác để điều về bool_ind, bool_rec và bool_rect: họ đóng gói những gì bạn cần biết để nói về mỗi giá trị của bool. Nhưng cả hai cách, chúng tôi sẽ đóng gói thông tin đó: nếu tôi biết điều gì đó cho true và một số nội dung cho false, thì tôi biết điều đó cho tất cả các số bool s.

Định nghĩa hàm bool_{ind,rec,rect} tóm tắt theo cách thông thường chúng ta viết hàm trên boolean: có một đối số tương ứng với nhánh thực, và một đối số cho nhánh giả. Hay nói cách khác: các hàm này chỉ là các câu lệnh if. Trong một ngôn ngữ không phải lệ thuộc, đánh máy, họ có thể có các loại đơn giản forall S : Set, S -> S -> bool -> S:

Definition bool_simple_rec (S : Set) (St : P) (Sf : P) (b : bool) : S := 
    match b with 
    | true => St 
    | false => Sf 
    end. 

Tuy nhiên, do loại có thể phụ thuộc vào các giá trị, chúng ta phải luồn b thông qua các loại ở khắp mọi nơi.Nếu nó quay ra, chúng tôi không muốn điều đó, tuy nhiên, chúng ta có thể sử dụng chức năng tổng quát hơn của chúng tôi và nói:

Definition bool_simple_rec' (S : Set) : S -> S -> bool -> S := 
    bool_rec (fun _ => S). 

Chưa ai từng nói chúng tôi P : bool -> Set phải sử dụng các bool!

Tất cả các chức năng này thú vị hơn đối với đệ quy loại. Ví dụ, Coq có các loại sau đây của các số tự nhiên:

Inductive nat : Set := O : nat | S : nat -> nat. 

Và chúng tôi có

nat_ind : forall P : nat -> Prop, 
      P O -> 
      (forall n' : nat, P n' -> P (S n')) -> 
      forall n : nat, 
       P n 

Cùng với sự tương ứng nat_rec và nat_rect. (Tập thể dục cho người đọc: thực hiện các chức năng này trực tiếp.)

Thoạt nhìn, đây chỉ là nguyên tắc cảm ứng toán học. Tuy nhiên, đó cũng là cách chúng ta viết các hàm đệ quy trên nat s; chúng giống nhau. Nói chung, chức năng đệ quy trên nat trông giống như sau:

fix f n => match n with 
      | O => ... 
      | S n' => ... f n' ... 
      end 

Cánh tay của trận đấu sau O (trường hợp cơ sở) chỉ là giá trị của loại P O. Các cánh tay của trận đấu sau S n' (trường hợp đệ quy) là những gì được chuyển vào chức năng của loại forall n' : nat, P n' -> P (S n'): các n' s là như nhau, và giá trị của P n' là kết quả của các cuộc gọi đệ quy f n'.

Một cách khác để suy nghĩ về sự tương đương giữa các chức năng _rec và _ind, lúc bấy giờ và một trong đó tôi nghĩ là rõ ràng hơn đối với các loại vô hạn hơn trên bool -là rằng nó giống như sự tương đương giữa toán học ind uction (mà xảy ra trong Prop) và (kết cấu) rec ursion (xảy ra trong Set và Type).

---

Chúng ta hãy nhận được độc và sử dụng các chức năng này. Chúng ta sẽ định nghĩa một hàm đơn giản để chuyển đổi các boolean thành các số tự nhiên, và chúng ta sẽ thực hiện nó trực tiếp và với bool_rec. Cách đơn giản nhất để viết chức năng này là với một mô hình phù hợp:

Definition bool_to_nat_match (b : bool) : nat := 
    match b with 
    | true => 1 
    | false => 0 
    end. 

Định nghĩa khác là

Definition bool_to_nat_rec : bool -> nat := 
    bool_rec (fun _ => nat) 1 0. 

Và hai chức năng này đều giống nhau:

Goal bool_to_nat_match = bool_to_nat_rec. 
Proof. reflexivity. Qed. 

(Lưu ý: đây chức năng là cú pháp tương đương. Đây là điều kiện mạnh hơn chỉ đơn giản là làm điều tương tự.)

Ở đây, P : bool -> Set là fun _ => nat; nó cho chúng ta kiểu trả về, không phụ thuộc vào đối số. Pt : P true của chúng tôi là 1, điều cần tính khi chúng tôi được cung cấp true; tương tự, số Pf : P false của chúng tôi là 0.

Nếu chúng ta muốn sử dụng sự phụ thuộc, chúng ta phải nấu một loại dữ liệu hữu ích. Làm thế nào về

Inductive has_if (A : Type) : bool -> Type := 
    | has : A -> has_if A true 
    | lacks : has_if A false. 

Với định nghĩa này, has_if A true là đẳng cấu với A, và has_if A false là đẳng cấu với unit. Sau đó, chúng tôi có thể có một chức năng giữ lại đối số đầu tiên của nó nếu và chỉ khi nó được thông qua true.

Definition keep_if_match' (A : Type) (a : A) (b : bool) : has_if A b := 
    match b with 
    | true => has A a 
    | false => lacks A 
    end. 

Định nghĩa khác là

Definition keep_if_rect (A : Type) (a : A) : forall b : bool, has_if A b := 
    bool_rect (has_if A) (has A a) (lacks A). 

Và họ lại giống nhau:

Goal keep_if_match = keep_if_rect. 
Proof. reflexivity. Qed. 

Ở đây, kiểu trả về của hàm là phụ thuộc vào lập luận b, do đó, P : bool -> Type của chúng tôi thực sự làm điều gì đó.

Dưới đây là một ví dụ thú vị hơn, sử dụng số tự nhiên và danh sách được lập chỉ mục độ dài. Nếu bạn không thấy các danh sách được lập chỉ mục độ dài, còn được gọi là vectơ, chúng chính xác là những gì họ nói trên tin; vec A n là danh sách nA s.

Inductive vec (A : Type) : nat -> Type := 
    | vnil : vec A O 
    | vcons : forall n, A -> vec A n -> vec A (S n). 
Arguments vnil {A}. 
Arguments vcons {A n} _ _. 

(Các máy móc Arguments xử lý đối số tiềm ẩn.) Bây giờ, chúng tôi muốn tạo ra một danh sách các n bản sao của một số yếu tố đặc biệt, vì vậy chúng tôi có thể viết rằng với một fixpoint:

Fixpoint vreplicate_fix {A : Type} (n : nat) (a : A) : vec A n := 
    match n with 
    | O => vnil 
    | S n' => vcons a (vreplicate_fix n' a) 
    end. 

Ngoài ra, chúng ta có thể sử dụng nat_rect:

Definition vreplicate_rect {A : Type} (n : nat) (a : A) : vec A n := 
    nat_rect (vec A) vnil (fun n' v => vcons a v) n. 

Lưu ý rằng kể từ khi nat_rect chụp mẫu đệ quy, vreplicate_rect không phải là một điểm cố định. Một điều cần lưu ý là đối số thứ ba để nat_rect:

fun n' v => vcons a v 

Các v có khái niệm là kết quả của các cuộc gọi đệ quy để vreplicate_rect n' a; nat_rect tóm tắt mô hình đệ quy, vì vậy chúng tôi không cần phải gọi trực tiếp. n' thực sự giống như n' như trong vreplicate_fix, nhưng bây giờ có vẻ như chúng ta không cần phải đề cập đến nó một cách rõ ràng. Tại sao nó được thông qua? Đó là trở nên rõ ràng nếu chúng ta viết ra loại của chúng tôi:

fun (n' : nat) (v : vec A n') => vcons a v : vec A (S n') 

Chúng ta cần n' vì vậy chúng tôi biết những gì loại v có, và hậu quả là những loại quả có.

Hãy xem các chức năng này trong hành động:

Eval simpl in vreplicate_fix 0 tt. 
Eval simpl in vreplicate_rect 0 tt. 
    (* both => = vnil : vec unit 0 *) 

Eval simpl in vreplicate_fix 3 true. 
Eval simpl in vreplicate_rect 3 true. 
    (* both => = vcons true (vcons true (vcons true vnil)) : vec bool 3 *) 

Và quả thực, chúng giống nhau:

(* Note: these two functions do the same thing, but are not syntactically 
    equal; the former is a fixpoint, the latter is a function which returns a 
    fixpoint. This sort of equality is all you generally need in practice. *) 
Goal forall (A : Type) (a : A) (n : nat), 
     vreplicate_fix n a = vreplicate_rect n a. 
Proof. induction n; [|simpl; rewrite IHn]; reflexivity. Qed. 

Ở trên, tôi đặt ra việc thực hiện reimplementing nat_rect và bạn bè.Dưới đây là câu trả lời:

Fixpoint nat_rect' (P   : nat -> Type) 
        (base_case : P 0) 
        (recurse : forall n', P n' -> P (S n')) 
        (n   : nat) 
        : P n := 
    match n with 
    | O => base_case 
    | S n' => recurse n' (nat_rect' P base_case recurse n') 
    end. 

này hy vọng làm cho nó rõ ràng chỉ cáchnat_rect tóm tắt mô hình đệ quy, và tại sao nó là đủ nói chung.