Hubungan antara teori tipe Russell dan sistem tipe
12
Baru-baru ini saya menyadari bahwa ada semacam hubungan antara teori tipe Russell dan sistem tipe, seperti yang ditemukan misalnya dalam Haskell. Sebenarnya, beberapa notasi untuk tipe di Haskell tampaknya memiliki prekursor dalam tipe teori. Tapi, IMHO, motivasi Russell pada tahun 1908 adalah untuk menghindari paradoks Russell, dan saya tidak yakin bagaimana itu terkait dengan sistem tipe dalam ilmu komputer.
Apakah paradoks Russell dalam satu bentuk atau sesuatu yang harus kita khawatirkan, misalnya, jika kita tidak memiliki sistem tipe yang baik dalam bahasa tertentu?
`` Tipe teori "dalam arti bahasa pemrograman dan dalam arti Russell terkait erat. Bahkan, bidang modern teori tipe dependen bertujuan untuk memberikan dasar yang konstruktif untuk matematika. Tidak seperti teori set, kebanyakan penelitian dalam teori tipe didasarkan matematika dilakukan dalam asisten bukti seperti Coq, NuPRL, atau Agda. Dengan demikian, bukti yang dilakukan dalam sistem ini tidak hanya "dapat diformalkan" tetapi juga benar-benar formal dan diperiksa dengan mesin. Menggunakan taktik dan teknik otomatisasi bukti lainnya, kami mencoba membuktikan dengan ini sistem "tingkat tinggi" dan dengan demikian menyerupai matematika informal, tetapi karena semuanya diperiksa kami memiliki jaminan yang jauh lebih baik pada kebenaran.
Jenis-jenis dalam bahasa pemrograman biasa cenderung lebih terbatas, tetapi teori meta adalah sama.
Sesuatu yang mirip dengan paradoks Russell adalah masalah utama dalam teori tipe dependen. Secara khusus, memiliki
Type : Type
biasanya mengarah pada kontradiksi. Coq dan karya serupa oleh alam semesta bersarang
Type_0 : Type_1
tetapi dalam Coq secara default angka-angka ini tersirat karena biasanya tidak masalah bagi programmer.
Dalam beberapa sistem (Agda, Idris), tipe aturan ketik diaktifkan melalui flag kompilasi. Itu membuat logika tidak konsisten, tetapi sering membuat pemrograman eksplorasi / pembuktian lebih mudah.
Bahkan dalam bahasa yang lebih umum, paradoks Russell sesekali muncul. Misalnya, dalam Haskell, penyandian paradoks Russell yang menggabungkan impredicativity dan case type terbuka dimungkinkan, memungkinkan seseorang untuk membangun istilah yang berbeda tanpa rekursi bahkan pada level type. Haskell adalah `` tidak konsisten "(ketika diartikan sebagai logika dengan cara biasa) karena Haskell mendukung rekursi tipe dan tingkat nilai, belum lagi pengecualian. Tidak ada yang kurang, hasil ini agak menarik.
Terima kasih atas jawaban terperinci Anda - sejauh buktinya, masih belum ada alat yang terlihat untuk membuktikan kebenaran program dalam bahasa imperatif seperti C ++ atau Java, kan? Saya ingin meletakkan tangan saya pada salah satu dari ini ... Saya menyadari ini adalah singgung lengkap. Saya tahu tentang Coq dan Agda, tetapi mereka tampaknya tidak menjadi alat yang tepat untuk membuktikan kebenaran program yang ditulis dalam C ++ atau Java.
Frank
3
ada beberapa alat. Beberapa untuk C, banyak untuk Jawa, dan ton untuk Ada. Lihat misalnya: Why (Java, C, Ada), Krakatoa (Java), atau SPARK (Ada subset dengan tooling yang sangat baik). Untuk C ++, tidak begitu banyak. Anda juga mungkin tertarik dengan YNot (Coq DSL).
Philip JF
3
Anda benar tentang motivasi Russell. Paradoksnya mengganggu semua teori himpunan yang mengakui aksioma pemahaman yang tidak terbatas yang menyatakan bahwa: fungsi proposisi apa pun menentukan himpunan, yaitu semua entitas yang memenuhi fungsi. Di antara teori atau berdasarkan pada set yang memang memiliki cacat itu adalah teori set naif Cantor dan sistem Frege dari Grundgesetze (khusus: aksioma 5).
Karena jenis dianggap sebagai jenis set khusus, jika perawatan tidak dilakukan, paradoks yang sama dapat menyusup ke dalam sistem tipe. Yang dikatakan, saya tidak mengetahui adanya sistem tipe yang telah mengalami nasib seperti itu. Saya hanya dapat mengingat upaya awal Gereja dalam merumuskan kalkulus lambda di tahun 30-an, yang ternyata tidak konsisten (Kleene-Rosser Paradox), tetapi itu bukan karena tipe dan tidak terkait dengan paradoks Russell.
Pembaruan : Lihat jawaban Philip untuk jawaban aktual atas pertanyaan Anda.
Terima kasih atas jawaban anda. Mungkin ada alternatif untuk tipe-a-la-Russell untuk menghindari Russell paradox. Apakah ada solusi alternatif yang memiliki sesuatu yang menarik untuk disumbangkan ke bahasa komputer? Jenis-jenis duniawi sangat berguna untuk secara jelas menentukan kontrak antara bagian-bagian kode, dan bahkan sebelum itu, untuk memberikan semantik pada program sama sekali. Akankah ada semantik lain yang bisa diperoleh dengan sesuatu yang lain daripada tipe? (Saya tidak tahu apa yang akan terjadi :-)
Frank
1
Ya, banyak alternatif (Quine's NF, ZFC, dll), tapi saya tidak bisa melihat koneksi langsung antara krisis mendasar dan bahasa pemrograman. Jika Anda menganggap teori tipe Martin Lof sebagai bahasa pemrograman, mungkin ada beberapa koneksi di sana yang kembali ke intuitionism. Mengenai semantik bahasa pemrograman, ada beberapa bahasa dasar seperti PDL (Propositional Dynamic Logic) yang memiliki semantik Kripke (atau kemungkinan dunia). Tetapi jenis-jenis menurut saya sangat mendasar sehingga mereka mungkin berada di belakang layar :)
Hunan Rostomyan
1
Tetapi tipe agak mengecewakan: Anda ingin dan membutuhkannya, tetapi Anda ingin tidak harus menentukannya (karenanya, IMHO, mengapa kami memiliki sistem inferensi tipe dalam bahasa seperti Haskell atau Ocaml (Saya suka bahasa itu)). Di ujung lain spektrum, Python terasa sangat intuitif dan menyenangkan (dan efisien dalam hal waktu pengkodean) untuk tidak perlu terlalu khawatir tentang jenis-jenis dalam bahasa itu. Mungkin tipe inferensi adalah yang terbaik dari kedua dunia - tetapi itulah yang dikatakan insinyur. Saya hanya berangan-angan bahwa matematika dapat menyumbangkan konsep penting lainnya (seperti tipe) untuk ilmu komputer :-)
Frank
1
@ Jujur Setiap kali saya menggunakan bahasa tanpa tipe statis (kebanyakan Ruby) Saya benci pengalaman, karena saya benci kesalahan runtime yang dapat dihindari. Jadi, yang tampaknya menjadi masalah selera kebanyakan. Saya setuju bahwa inferensi tipe kuat dapat memberi Anda yang terbaik dari kedua dunia. Mungkin itulah sebabnya saya sangat menyukai Scala.
Raphael
Saya tidak yakin bahwa tidak memiliki tipe "secara otomatis" mengarah ke kesalahan runtime, karena Anda tampaknya menyiratkan :-) Saya tidak pernah punya masalah dengan Python.
Frank
3
Karena Anda menyebutkan Python, pertanyaannya bukan murni tipe-teoretik. Jadi saya mencoba memberikan perspektif yang lebih luas tentang jenis. Jenis adalah hal yang berbeda untuk orang yang berbeda. Saya telah mengumpulkan setidaknya 5 gagasan berbeda (tapi terkait) tentang jenis:
Jenis sistem adalah sistem logis dan teori set.
Sistem tipe mengaitkan suatu tipe dengan setiap nilai yang dihitung. Dengan memeriksa aliran nilai-nilai ini, sistem tipe mencoba untuk membuktikan atau memastikan bahwa tidak ada kesalahan tipe dapat terjadi.
Tipe adalah klasifikasi yang mengidentifikasi salah satu dari berbagai tipe data, seperti nilai sebenarnya, integer atau Boolean, yang menentukan nilai yang mungkin untuk tipe itu; operasi yang dapat dilakukan pada nilai-nilai jenis itu; arti data; dan nilai-nilai cara tipe itu dapat disimpan
Tipe data abstrak memungkinkan abstraksi data dalam bahasa tingkat tinggi. ADT sering diimplementasikan sebagai modul: antarmuka modul menyatakan prosedur yang sesuai dengan operasi ADT. Strategi penyembunyian informasi ini memungkinkan implementasi modul diubah tanpa mengganggu program klien.
Pemrograman implementasi bahasa menggunakan tipe nilai untuk memilih penyimpanan yang dibutuhkan nilai dan algoritma untuk operasi pada nilai.
Kutipan berasal dari Wikipedia, tetapi saya dapat memberikan referensi yang lebih baik jika diperlukan.
Tipe-1 muncul dari karya Russel, tetapi hari ini mereka tidak semata-mata melindungi dari paradoks: bahasa yang diketik dari teori tipe homotopy adalah cara baru untuk menyandikan matematika dalam bahasa formal, bahasa yang dapat dimengerti mesin, dan cara baru bagi manusia untuk memahami fondasi matematika. (Cara "lama" adalah pengkodean menggunakan teori himpunan aksiomatik).
Tipe 2-5 muncul dalam pemrograman dari beberapa kebutuhan yang berbeda: untuk menghindari bug, untuk mengklasifikasikan perancang perangkat lunak data dan programmer bekerja dengan, untuk merancang sistem besar dan menerapkan bahasa pemrograman masing-masing secara efisien.
Ketik sistem dalam C / C ++, Ada, Java, Python tidak muncul dari pekerjaan Russel atau keinginan untuk menghindari bug. Mereka muncul dari kebutuhan untuk menggambarkan berbagai jenis data di luar sana (misalnya "nama belakang adalah string karakter dan bukan angka"), memodulasi desain perangkat lunak dan memilih representasi tingkat rendah untuk data secara optimal. Bahasa-bahasa ini tidak memiliki tipe-1 atau tipe-2. Java memastikan keamanan relatif dari bug bukan dengan membuktikan kebenaran program menggunakan sistem tipe, tetapi dengan desain bahasa yang cermat (tanpa aritmatika pointer) dan sistem runtime (mesin virtual, verifikasi bytecode). Tipe sistem di Jawa bukanlah sistem logis atau teori himpunan.
Namun, sistem tipe dalam bahasa pemrograman Agda adalah varian modern dari sistem tipe Russel (berdasarkan pada pekerjaan selanjutnya atau Per Martin-Lof dan matematikawan lainnya). Tipe sistem di Agda dirancang untuk mengekspresikan properti matematika dari program dan bukti dari properti itu, itu adalah sistem logis dan teori himpunan.
Tidak ada perbedaan hitam-putih di sini: banyak bahasa yang cocok di antaranya. Misalnya, jenis sistem bahasa Haskell berakar pada karya Russel, dapat dilihat sebagai sistem Agda yang disederhanakan, tetapi dari sudut pandang matematika, itu tidak konsisten (kontradiksi sendiri) jika dilihat sebagai sistem logis atau teori himpunan.
Namun, sebagai kendaraan teoretis untuk melindungi program Haskell dari bug, ia bekerja dengan cukup baik. Anda bahkan dapat menggunakan tipe untuk menyandikan properti tertentu dan buktinya, tetapi tidak semua properti dapat disandikan, dan pemrogram tetap dapat melanggar properti yang terbukti jika ia menggunakan peretasan kotor yang tidak disarankan.
Tipe sistem Scala bahkan lebih jauh dari karya Russel dan bahasa pembuktian Agda yang sempurna, tetapi masih berakar pada karya Russel.
Adapun untuk membuktikan sifat-sifat bahasa industri yang sistem tipenya tidak dirancang untuk itu, ada banyak pendekatan dan sistem.
Untuk pendekatan yang menarik tetapi berbeda, lihat Coq dan proyek penelitian Microsoft Boogie. Coq bergantung pada teori tipe untuk menghasilkan program imperatif dari program Coq. Boogie bergantung pada anotasi program penting dengan properti dan membuktikan properti itu dengan teorema Z3 menggunakan pendekatan yang sama sekali berbeda dari Coq.
Anda benar tentang motivasi Russell. Paradoksnya mengganggu semua teori himpunan yang mengakui aksioma pemahaman yang tidak terbatas yang menyatakan bahwa: fungsi proposisi apa pun menentukan himpunan, yaitu semua entitas yang memenuhi fungsi. Di antara teori atau berdasarkan pada set yang memang memiliki cacat itu adalah teori set naif Cantor dan sistem Frege dari Grundgesetze (khusus: aksioma 5).
Karena jenis dianggap sebagai jenis set khusus, jika perawatan tidak dilakukan, paradoks yang sama dapat menyusup ke dalam sistem tipe. Yang dikatakan, saya tidak mengetahui adanya sistem tipe yang telah mengalami nasib seperti itu. Saya hanya dapat mengingat upaya awal Gereja dalam merumuskan kalkulus lambda di tahun 30-an, yang ternyata tidak konsisten (Kleene-Rosser Paradox), tetapi itu bukan karena tipe dan tidak terkait dengan paradoks Russell.
Pembaruan : Lihat jawaban Philip untuk jawaban aktual atas pertanyaan Anda.
sumber
Karena Anda menyebutkan Python, pertanyaannya bukan murni tipe-teoretik. Jadi saya mencoba memberikan perspektif yang lebih luas tentang jenis. Jenis adalah hal yang berbeda untuk orang yang berbeda. Saya telah mengumpulkan setidaknya 5 gagasan berbeda (tapi terkait) tentang jenis:
Jenis sistem adalah sistem logis dan teori set.
Sistem tipe mengaitkan suatu tipe dengan setiap nilai yang dihitung. Dengan memeriksa aliran nilai-nilai ini, sistem tipe mencoba untuk membuktikan atau memastikan bahwa tidak ada kesalahan tipe dapat terjadi.
Tipe adalah klasifikasi yang mengidentifikasi salah satu dari berbagai tipe data, seperti nilai sebenarnya, integer atau Boolean, yang menentukan nilai yang mungkin untuk tipe itu; operasi yang dapat dilakukan pada nilai-nilai jenis itu; arti data; dan nilai-nilai cara tipe itu dapat disimpan
Tipe data abstrak memungkinkan abstraksi data dalam bahasa tingkat tinggi. ADT sering diimplementasikan sebagai modul: antarmuka modul menyatakan prosedur yang sesuai dengan operasi ADT. Strategi penyembunyian informasi ini memungkinkan implementasi modul diubah tanpa mengganggu program klien.
Pemrograman implementasi bahasa menggunakan tipe nilai untuk memilih penyimpanan yang dibutuhkan nilai dan algoritma untuk operasi pada nilai.
Kutipan berasal dari Wikipedia, tetapi saya dapat memberikan referensi yang lebih baik jika diperlukan.
Tipe-1 muncul dari karya Russel, tetapi hari ini mereka tidak semata-mata melindungi dari paradoks: bahasa yang diketik dari teori tipe homotopy adalah cara baru untuk menyandikan matematika dalam bahasa formal, bahasa yang dapat dimengerti mesin, dan cara baru bagi manusia untuk memahami fondasi matematika. (Cara "lama" adalah pengkodean menggunakan teori himpunan aksiomatik).
Tipe 2-5 muncul dalam pemrograman dari beberapa kebutuhan yang berbeda: untuk menghindari bug, untuk mengklasifikasikan perancang perangkat lunak data dan programmer bekerja dengan, untuk merancang sistem besar dan menerapkan bahasa pemrograman masing-masing secara efisien.
Ketik sistem dalam C / C ++, Ada, Java, Python tidak muncul dari pekerjaan Russel atau keinginan untuk menghindari bug. Mereka muncul dari kebutuhan untuk menggambarkan berbagai jenis data di luar sana (misalnya "nama belakang adalah string karakter dan bukan angka"), memodulasi desain perangkat lunak dan memilih representasi tingkat rendah untuk data secara optimal. Bahasa-bahasa ini tidak memiliki tipe-1 atau tipe-2. Java memastikan keamanan relatif dari bug bukan dengan membuktikan kebenaran program menggunakan sistem tipe, tetapi dengan desain bahasa yang cermat (tanpa aritmatika pointer) dan sistem runtime (mesin virtual, verifikasi bytecode). Tipe sistem di Jawa bukanlah sistem logis atau teori himpunan.
Namun, sistem tipe dalam bahasa pemrograman Agda adalah varian modern dari sistem tipe Russel (berdasarkan pada pekerjaan selanjutnya atau Per Martin-Lof dan matematikawan lainnya). Tipe sistem di Agda dirancang untuk mengekspresikan properti matematika dari program dan bukti dari properti itu, itu adalah sistem logis dan teori himpunan.
Tidak ada perbedaan hitam-putih di sini: banyak bahasa yang cocok di antaranya. Misalnya, jenis sistem bahasa Haskell berakar pada karya Russel, dapat dilihat sebagai sistem Agda yang disederhanakan, tetapi dari sudut pandang matematika, itu tidak konsisten (kontradiksi sendiri) jika dilihat sebagai sistem logis atau teori himpunan.
Namun, sebagai kendaraan teoretis untuk melindungi program Haskell dari bug, ia bekerja dengan cukup baik. Anda bahkan dapat menggunakan tipe untuk menyandikan properti tertentu dan buktinya, tetapi tidak semua properti dapat disandikan, dan pemrogram tetap dapat melanggar properti yang terbukti jika ia menggunakan peretasan kotor yang tidak disarankan.
Tipe sistem Scala bahkan lebih jauh dari karya Russel dan bahasa pembuktian Agda yang sempurna, tetapi masih berakar pada karya Russel.
Adapun untuk membuktikan sifat-sifat bahasa industri yang sistem tipenya tidak dirancang untuk itu, ada banyak pendekatan dan sistem.
Untuk pendekatan yang menarik tetapi berbeda, lihat Coq dan proyek penelitian Microsoft Boogie. Coq bergantung pada teori tipe untuk menghasilkan program imperatif dari program Coq. Boogie bergantung pada anotasi program penting dengan properti dan membuktikan properti itu dengan teorema Z3 menggunakan pendekatan yang sama sekali berbeda dari Coq.
sumber