Apakah urutan deklarasi dalam tipe induktif penting?

9

Saya bertanya-tanya apakah urutan deklarasi tipe induktif dapat berpengaruh.

Misalnya dalam Coq, Anda dapat menentukan Natdengan:

Inductive Nat :=
  | O : Nat
  | S : Nat -> Nat.

atau

Inductive Nat :=
  | S : Nat -> Nat
  | O : Nat.

Ini mungkin akan mengubah urutan parameter dalam eliminator yang dibuat secara otomatis, tapi itu bukan masalah besar.

Yang saya ingin tahu adalah apakah mungkin untuk menulis pernyataan seperti

Inductive typewhereordermatters :=
  | cons1 : type1
  | cons2 : type2.

di mana type2tipe dependen, tergantung pada cons1? (dan dalam hal ini, tulis deklarasi dalam urutan lain tidak akan memiliki arti, karena type2akan merujuk pada cons1yang belum ada).

lo.logic type-theory coq dependent-type Guillaume Brunerie
sumber

Jawaban:

10

  1. Perintahnya tidak masalah. Saya tidak bisa memikirkan kasus di mana itu akan terjadi. Seperti yang ditunjukkan oleh Andrej Bauer dalam komentar, jika Anda mengubah urutannya, hasilnya kanon secara isomorfis seperti aslinya .

  2. Satu kasing tidak dapat bergantung pada kasing lainnya. Unsur-unsur penjumlahan mewakili pilihan, sehingga tidak masuk akal bahwa pilihan yang diambil tergantung pada pilihan yang tidak diambil.

Dave Clarke
sumber
2
Anda bisa lebih spesifik tentang poin pertama Anda. Perintahnya tidak masalah. Jika Anda mengubah urutannya, hasilnya adalah isomorfik kanonik dengan aslinya.
Andrej Bauer
2
@ Dave: Terima kasih! Saya mengajukan pertanyaan ini karena (teori yang sangat eksperimental) jenis induktif yang lebih tinggi, di mana fenomena ini tampaknya terjadi , dan saya ingin tahu apakah ini juga dapat terjadi dengan jenis induktif biasa.
Guillaume Brunerie
1
@Guillaume: Saya tidak yakin fenomena apa yang Anda tunjuk dengan tautannya. Klausa konstruktor yang berbeda dari definisi tipe data tidak dapat saling bergantung, apakah itu tipe data tingkat tinggi atau tidak. Mungkin Anda memikirkan catatan dependen (yang digunakan pada tautan, dan tersedia di Agda dan Coq )?
Noam Zeilberger
1
@Noam: Pada contoh tipe induktif yang lebih tinggi circle, tipe loopkonstruktor bergantung pada basekonstruktor.
Guillaume Brunerie
2
@ Guillaume: Saya mengerti sekarang (mereka memperkenalkan sintaksis eksperimental), tidak tahu bagaimana saya melewatkannya.
Noam Zeilberger
6

Apakah pesanan itu penting menurut cara Anda bertanya? Tidak.

Tetapi apakah urutannya sama sekali tidak relevan dengan berfungsinya asisten bukti? Sekali lagi, tidak. Di Matita, asisten bukti sangat mirip dengan Coq, urutan konstruktor ditulis dalam definisi induktif tidak masalah untuk pengecekan tipe, khususnya ketika tipe memeriksa ekspresi kecocokan.

Matita pertama-tama harus memeriksa bahwa semua konstruktor sedang dicocokkan dalam tubuh pertandingan. Ia melakukan ini dengan bersepeda melalui konstruktor dalam urutan di mana mereka dinyatakan. Kemudian, ketikkan untuk memeriksa ekspresi kecocokan yang tepat, yang terjadi dalam urutan terbalik, memeriksa casing untuk konstruktor yang terakhir dinyatakan terlebih dahulu. Jenis ini kemudian dilakukan dan digunakan untuk memeriksa kasus-kasus lainnya.

Ini sangat sering muncul ketika menulis ekspresi kecocokan yang besar. Anda ingin mengisi kasing yang mudah terlebih dahulu, meninggalkan kasing yang lebih sulit di bawah wildcard, ketikkan secara berkala memeriksa apa yang telah Anda tulis untuk memastikan bahwa itu masuk akal. Kadang-kadang Matita tidak dapat menyimpulkan jenis ekspresi pertandingan yang tidak lengkap tetapi akan dengan senang hati melakukannya jika Anda mengisi kasing untuk konstruktor terakhir yang ditentukan dalam jenis induktif.

Saya kira, meskipun saya tidak yakin, bahwa Coq melakukan sesuatu yang serupa.

Dominic Mulligan
sumber