Mengapa Coq memasukkan ekspresi let dalam bahasa intinya

9

Coq menyertakan let-expressions dalam bahasa intinya. Kami dapat menerjemahkan ekspresi let ke aplikasi seperti ini: let x : t = v in b ~> (\(x:t). b) v Saya mengerti bahwa ini tidak selalu berfungsi karena nilainya vtidak akan tersedia saat mengetik pemeriksaan b. Namun ini dapat dengan mudah diperbaiki oleh casing khusus pengetikan aplikasi jenis (\(x:t). b) v. Hal ini memungkinkan kami untuk menghapus ekspresi let dengan biaya kasus khusus saat mengetik pemeriksaan. Mengapa Coq termasuk masih menyertakan ekspresi let? Apakah mereka memiliki kelebihan lain (selain tidak memerlukan kasing khusus)?

Labbekak
sumber
4
Saran Anda terdengar seperti menambahkan peretasan untuk menghindari kebutuhan letekspresi, tetapi ada a) tidak ada alasan untuk menghindari letekspresi dan mereka juga nyaman, dan b) menambahkan peretasan ke bahasa inti Anda bukan ide yang bagus.
Derek Elkins meninggalkan SE

Jawaban:

23

Ini adalah kesalahpahaman umum bahwa kita dapat menerjemahkan let-ekspresi ke aplikasi. Perbedaan antara let x : t := b in vdan (fun x : t => v) badalah bahwa dalam let-ekspresi, selama pengecekan tipe vkita tahu bahwa xsama dengan b, tetapi dalam aplikasi kita tidak (subekspresi fun x : t => vharus masuk akal sendiri).

Berikut ini sebuah contoh:

(* Dependent type of vectors. *)
Inductive Vector {A : Type} : nat -> Type :=
  | nil : Vector 0
  | cons : forall n, A -> Vector n -> Vector (S n).

(* This works. *)
Check (let n := 0 in cons n 42 nil).

(* This fails. *)
Check ((fun (n : nat) => cons n 42 nil) 0).

Saran Anda untuk membuat aplikasi (fun x : t => v) bkasus khusus tidak benar-benar berfungsi. Mari kita pikirkan lebih hati-hati.

Misalnya, bagaimana Anda akan menangani ini, melanjutkan contoh di atas?

Definition a := (fun (n : nat) => cons n 42 nil).
Check a 0.

Agaknya ini tidak akan berhasil karena atidak bisa diketik, tetapi jika kita membuka definisi, kita mendapatkan ekspresi yang diketik dengan baik. Apakah Anda pikir pengguna akan mencintai kami, atau membenci kami karena keputusan desain kami?

e₁ e₂e₁λ

Anda juga akan mematahkan teorema dasar yang mengatakan bahwa setiap sub-ekspresi dari ekspresi yang diketik dengan baik diketik dengan baik. Itu masuk akal seperti memperkenalkan nullke Jawa.

Andrej Bauer
sumber