Positif yang ketat

Dari referensi ini: Kepositifan yang ketat

Kondisi positif yang ketat mengesampingkan deklarasi seperti

data Bad : Set where
 bad : (Bad → Bad) → Bad
         A      B       C
 -- A is in a negative position, B and C are OK

Mengapa A negatif? Juga Mengapa B diizinkan? Saya mengerti mengapa C diizinkan.

Pertama, penjelasan terminologis: posisi negatif dan positif datang dari logika. Mereka adalah tentang assymetry di operator logika: di yang berperilaku berbeda dari . Hal serupa terjadi dalam teori kategori, di mana kita mengatakan contravarian dan kovarian bukannya negatif dan positif, masing-masing. Dalam fisika mereka berbicara tentang jumlah yang berperilaku "kovarien" dan "juga contravarian. Jadi ini adalah fenomena yang sangat umum. Seorang programmer mungkin menganggapnya sebagai" input "dan" output ".A $A \Rightarrow B$$A$$B$

Sekarang ke tipe data induktif.

Pikirkan sebuah datatype induktif sebagai semacam aljabar struktur: konstruktor adalah operasi yang mengambil unsur-unsur dari sebagai argumen dan menghasilkan unsur-unsur baru dari . Ini sangat mirip dengan aljabar biasa: penjumlahan mengambil dua angka dan menghasilkan angka.T $T$$T$$T$

Dalam aljabar, biasanya suatu operasi membutuhkan jumlah argumen yang terbatas, dan dalam kebanyakan kasus dibutuhkan argumen nol (konstan), satu (unary) atau dua (binary). Lebih mudah untuk menggeneralisasi ini untuk konstruktor tipe data. Misalkan cadalah konstruktor untuk tipe data T:

• jika ckonstan kita dapat menganggapnya sebagai fungsi unit -> T, atau setara (empty -> T) -> T,
• jika cunary kita dapat menganggapnya sebagai fungsi T -> T, atau yang setara (unit -> T) -> T,
• jika cbiner kita dapat menganggapnya sebagai fungsi T -> T -> T, atau setara T * T -> T, atau setara (bool -> T) -> T,
• jika kita menginginkan konstruktor cyang mengambil tujuh argumen, kita bisa melihatnya sebagai fungsi di (seven -> T) -> Tmana sevenbeberapa tipe yang sebelumnya didefinisikan dengan tujuh elemen.
• kita juga dapat memiliki konstruktor cyang mengambil banyak argumen yang tak terhingga banyaknya, yang akan menjadi fungsi (nat -> T) -> T.

Contoh-contoh ini menunjukkan bahwa bentuk umum dari sebuah konstruktor seharusnya

c : (A -> T) -> T

di mana kita sebut Adengan arity dari cdan kita berpikir tentang csebagai konstruktor yang mengambil Aargumen -banyak tipe Tuntuk menghasilkan unsur T.

Ini adalah sesuatu yang sangat penting: arities harus didefinisikan sebelum kita mendefinisikan T, atau kita tidak bisa mengatakan apa yang seharusnya dilakukan oleh konstruktor. Jika seseorang mencoba memiliki konstruktor

broken: (T -> T) -> T

lalu pertanyaan "berapa banyak argumen yang brokendibutuhkan?" tidak memiliki jawaban yang baik Anda mungkin mencoba menjawabnya dengan "dibutuhkan T-banyak argumen", tetapi itu tidak akan berhasil, karena Tbelum didefinisikan. Kita mungkin mencoba keluar dari cunundrum dengan menggunakan teori titik tetap mewah untuk menemukan jenis Tdan fungsi injeksi (T -> T) -> T, dan akan berhasil, tetapi kita juga akan melanggar prinsip induksi untuk Tsepanjang jalan. Jadi, itu ide yang buruk untuk mencoba hal seperti itu.

Demi kelengkapan, izinkan saya menjelaskan keseluruhan cerita. Kita perlu menggeneralisasi bentuk konstruktor di atas sedikit. Terkadang kami memiliki operasi atau konstruktor yang mengambil parameter . Sebagai contoh, perkalian skalar mengambil skalar dan vektor untuk menghasilkan vektor . Ini adalah operasi unary pada vektor, diparameterisasi oleh skalar. Kita dapat melihat perkalian skalar sebagai operasi unary yang tak terhingga banyaknya, satu untuk setiap skalar, tapi itu menjengkelkan. Jadi, bentuk umum konstruktor harus memungkinkan parameter dari beberapa tipe :v λ ⋅ $\lambda$$v$$\lambda \cdot v$cB

c : B * (A -> T) -> T

Memang, banyak konstruktor dapat ditulis ulang dengan cara ini, tetapi tidak semua, kita perlu satu langkah lagi, yaitu kita harus membiarkan Auntuk bergantung pada B:

c : (∑ (x : B), A x -> T) -> T

Ini adalah bentuk akhir dari konstruktor untuk tipe induktif. Ini juga tepat apa tipe-W. Bentuknya sangat umum sehingga kita hanya perlu satu konstruktor saja c! Memang, jika kita memiliki dua dari mereka

d' : (∑ (x : B'), A' x -> T) -> T
d'' : (∑ (x : B''), A'' x -> T) -> T

maka kita bisa menggabungkannya menjadi satu

d : (∑ (x : B), A x -> T) -> T

dimana

B := B' + B''
A(inl x) := A' x
A(inr x) := A'' x

Ngomong-ngomong, jika kita menjelajah bentuk umum kita melihat bahwa itu setara dengan

c : ∏ (x : B), ((A x -> T) -> T)

yang lebih dekat dengan apa yang sebenarnya ditulis orang dalam asisten bukti. Asisten pembuktian memungkinkan kita untuk menuliskan konstruktor dengan cara yang mudah, tetapi itu setara dengan bentuk umum di atas (latihan!).

Kemunculan pertama Baddisebut 'negatif' karena mewakili argumen fungsi, yaitu terletak di sebelah kiri panah fungsi (lihat Jenis rekursif gratis oleh Philip Wadler). Saya kira asal usul istilah 'posisi negatif' bermula dari gagasan contravariance ('contra' berarti berlawanan).

Tidak diperbolehkan memiliki tipe yang didefinisikan dalam posisi negatif karena seseorang dapat menulis program non-terminating menggunakannya, yaitu normalisasi yang kuat gagal di hadapannya (lebih lanjut tentang ini di bawah ini). Ngomong-ngomong, ini adalah alasan untuk nama aturan 'kepositifan ketat': kami tidak mengizinkan posisi negatif.

Kami mengizinkan kemunculan kedua Badkarena tidak menyebabkan non-terminasi dan kami ingin menggunakan tipe yang didefinisikan ( Bad) di beberapa titik dalam tipe data rekursif ( sebelum panah terakhir konstruktornya).

Penting untuk dipahami bahwa definisi berikut tidak melanggar aturan kepositifan yang ketat.

data Good : Set where
  good : Good → Good → Good

Aturan hanya berlaku untuk argumen konstruktor (yang keduanya Gooddalam kasus ini) dan tidak untuk konstruktor itu sendiri (lihat juga " Pemrograman Bersertifikat dengan Jenis Tanggungan " oleh Adam Chlipala ).

Contoh lain yang melanggar kepositifan yang ketat:

data Strange : Set where
  strange : ((Bool → Strange) → (ℕ → Strange)) → Strange
                       ^^     ^
            this Strange is   ...this arrow
            to the left of... 

Anda mungkin juga ingin memeriksa jawaban ini tentang posisi negatif.

Deklarasi yang tidak sepenuhnya positif ditolak karena seseorang dapat menulis fungsi yang tidak berhenti menggunakannya. Untuk melihat bagaimana seseorang dapat menulis definisi perulangan menggunakan datatype buruk dari atas, lihat BadInHaskell .

Berikut adalah contoh analog dalam Ocaml, yang menunjukkan bagaimana menerapkan perilaku rekursif tanpa (!) Menggunakan rekursi secara langsung:

type boxed_fun =
  | Box of (boxed_fun -> boxed_fun)

(* (!) in Ocaml the 'let' construct does not permit recursion;
   one have to use the 'let rec' construct to bring 
   the name of the function under definition into scope
*)
let nonTerminating (bf:boxed_fun) : boxed_fun =
  match bf with
    Box f -> f bf

let loop = nonTerminating (Box nonTerminating)

The nonTerminatingfungsi "membongkar" fungsi dari argumen dan apel ke argumen asli. Yang penting di sini adalah bahwa sebagian besar sistem tipe tidak mengizinkan fungsi lewat untuk diri mereka sendiri, jadi istilah seperti f ftidak akan mengetik centang, karena tidak ada tipe untuk fmemuaskan tanda ketik. Salah satu alasan sistem tipe diperkenalkan adalah untuk menonaktifkan aplikasi mandiri (lihat di sini ).

Membungkus tipe data seperti yang kami perkenalkan di atas dapat digunakan untuk menghindari hambatan ini dalam perjalanan menuju ketidakkonsistenan.

Saya ingin menambahkan bahwa perhitungan non-terminasi memperkenalkan inkonsistensi pada sistem logika. Dalam kasus Agda dan Coq, Falsetipe data induktif tidak memiliki konstruktor, jadi Anda tidak akan pernah bisa membangun istilah bukti tipe False. Tetapi jika perhitungan non-terminasi diizinkan, seseorang dapat melakukannya misalnya dengan cara ini (dalam Coq):

Fixpoint loop (n : nat) : False = loop n

Kemudian loop 0akan mengetik cek loop 0 : False, jadi di bawah korespondensi Curry-Howard itu berarti kita membuktikan proposisi yang salah.

Hasilnya : aturan kepositifan yang ketat untuk definisi induktif mencegah perhitungan yang tidak berakhir yang merupakan bencana bagi logika.