Mengapa titik dua menunjukkan bahwa nilai milik tipe?

19

Pierce (2002) memperkenalkan relasi pengetikan di halaman 92 dengan menulis:

Relasi pengetikan untuk ekspresi aritmatika, yang dituliskan "t: T", didefinisikan oleh seperangkat aturan inferensi yang menetapkan jenis ke istilah

dan catatan kaki mengatakan Simbol sering digunakan sebagai ganti:. Pertanyaan saya adalah mengapa tipe teori lebih suka menggunakan: over ? Jika tipe adalah himpunan nilai maka masuk akal untuk menulis , tidak ada notasi baru yang diperlukan.TtT

Apakah ini mirip dengan bagaimana beberapa penulis cs lebih suka bahkan berpikir itu penyalahgunaan notasi dan harus ditulis ?3n2=O(n2)3n2O(n2)

Björn Lindqvist
sumber
7
Predikat keanggotaan dapat benar atau salah, sedangkan deklarasi pengetikan umumnya diinterpretasikan sebagai pernyataan faktual yang dinyatakan benar atau kebenarannya dapat diperoleh dengan cara sintaksis murni . Bandingkan ini menjadi bilangan prima, yang tidak cukup dengan metode sintaktis keanggotaan. xX x:X
Musa Al-hassy
4
@ MusaAl-hassy: itu representasi yang keliru dari apa yang sedang terjadi. Itu tidak dinyatakan benar, karena itu berarti bahwa saya dapat "menyatakan" bahwa " false: int", misalnya. Demikian pula halnya bahwa penghakiman harus diperoleh dengan "cara sintaksis murni", misalnya dalam kasus teori tipe internal kategori dengan keluarga.
Andrej Bauer
3
Pertanyaan terkait pada cs.se: Apa sebenarnya perbedaan semantik antara set dan tipe?
Kadal diskrit
2
Untuk menambahkan komentar @ MusaAl-hassy, ​​dalam teori tipe komputasi Bob Constable, Stuart Allen, Bob Harper, dkk., digunakan secara rutin untuk mengetik penilaian karena lebih mirip dengan predikat keanggotaan (lihat pembicaraan ini , slide 25, sebagai contoh).
xrq
3
Tentunya juga merupakan penyalahgunaan notasi dan harus benar-benar ditulis λ n .3 n 2O ( λ n . N 2 ) ? (Matematikawan mungkin lebih suka n 3 n 2O ( n n 2 ) .)3n2O(n2)λn.3n2O(λn.n2)n3n2O(nn2)
Oscar Cunningham

Jawaban:

12

Karena apa yang ada di sebelah kanan titik dua belum tentu satu set dan apa yang di sebelah kiri titik dua belum tentu anggota set itu.

Teori tipe dimulai pada awal abad ke-20 sebagai pendekatan terhadap dasar matematika. Bertrand Russel menemukan sebuah paradoks dalam teori himpunan naif, dan ia bekerja pada teori tipe sebagai cara untuk membatasi kekuatan ekspresif teori himpunan untuk menghindari paradoks ini (dan lainnya). Selama bertahun-tahun, Russel dan yang lainnya telah mendefinisikan banyak teori tipe. Dalam beberapa teori tipe, tipe ditetapkan dengan sifat-sifat tertentu, tetapi pada yang lain, mereka adalah jenis binatang yang berbeda.

Secara khusus, banyak teori tipe memiliki formulasi sintaksis . Ada aturan yang menyebabkan sesuatu memiliki tipe. Saat aturan pengetikan digunakan sebagai landasan teori, penting untuk membedakan apa yang dikatakan aturan pengetikan dari apa yang bisa disimpulkan dengan menerapkan pengetahuan eksternal tambahan. Ini terutama penting jika aturan pengetikan adalah dasar untuk teori pembuktian: teorema yang berpegang pada teori himpunan dengan logika klasik dan aksioma pilihan mungkin atau tidak mungkin berlaku dalam logika konstruktif, misalnya. Salah satu makalah mani dalam domain ini adalah Church 's A Formulation of the Simple Type of Theory of Types (1940)

Mungkin cara perbedaan antara tipe dan set adalah yang paling jelas adalah bahwa aturan paling dasar untuk set, yaitu bahwa dua set adalah sama jika mereka memiliki elemen yang sama, biasanya tidak berlaku untuk tipe. Lihat jawaban Andrej Bauer di sini dan jawabannya pada pertanyaan terkait untuk beberapa contoh. Utas kedua itu memiliki jawaban lain yang layak dibaca.

Dalam kalkulus yang diketik, untuk mengatakan bahwa tipe adalah set sebenarnya untuk memberikan semantik untuk tipe. Memberi kalkulus sebuah semantik-teoretik tipe bukanlah hal yang sepele. Misalnya, Anda mendefinisikan bahasa dengan fungsi. Apa set adalah jenis fungsi? Fungsi total ditentukan oleh grafiknya, seperti yang kita diajarkan dalam teori himpunan 101. Tetapi bagaimana dengan fungsi parsial? Apakah Anda ingin memberikan semua fungsi non-terminating semantik yang sama? Anda tidak bisa menafsirkan tipe sebagai set untuk kalkulus yang memungkinkan fungsi rekursif sampai Anda menjawab pertanyaan itu. Memberikan bahasa pemrograman atau semantik denotasional adalah masalah yang sulit di awal tahun 1970-an. Makalah mani di sini adalah Menuju semantik matematika untuk bahasa komputer (1971) olehDana Scott dan Christopher Strachey . The Haskell wikibook memiliki presentasi yang baik tentang topik tersebut.

Seperti yang saya tulis di atas, bagian kedua dari jawabannya adalah bahwa bahkan jika Anda telah berhasil memberikan tipe semantik teoritis-set, hal di sebelah kiri titik dua tidak selalu menjadi elemen set. Nilai memiliki tipe, tetapi begitu juga hal-hal lain, seperti ekspresi dan variabel . Misalnya, ekspresi dalam bahasa pemrograman yang diketik memiliki tipe bahkan jika itu tidak berakhir. Anda mungkin bersedia untuk conflate integerdan Z , tapi (x := 0; while true; do x := x + 1; x)bukan merupakan unsur Z .

Saya tidak tahu kapan notasi usus besar muncul untuk jenis. Sekarang standar dalam semantik, dan umum dalam bahasa pemrograman, tetapi baik Russel maupun Gereja tidak menggunakannya. Algol tidak menggunakannya, tetapi bahasa Pascal yang sangat diilhami Algol melakukannya pada tahun 1971. Saya menduga itu bukan yang pertama, karena, banyak makalah teori dari awal tahun 1970 menggunakan notasi, tetapi saya tidak tahu tentang penggunaan sebelumnya. Menariknya, ini terjadi segera setelah konsep tipe dari pemrograman dan dari logika telah disatukan - seperti yang ditunjukkan Simon Martini dalam Beberapa Tipe Tipe dalam Bahasa Pemrograman , yang disebut "tipe" dalam bahasa pemrograman hingga 1960-an berasal dari bahasa sehari-hari. penggunaan kata dan bukan dari teori tipe.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
37

Alasan utama untuk memilih notasi titik dua t:T ke hubungan keanggotaan tT adalah bahwa hubungan keanggotaan dapat menyesatkan karena jenisnya bukan koleksi (hanya) .

[ Tambahan: Saya harus mencatat bahwa secara historis ketik teori itu ditulis menggunakan . Konsepsi Martin-LOF jenis dimaksudkan untuk menangkap set konstruktif, dan sudah Russell dan Whitehead digunakan ϵ untuk memebrship kelas. Akan menarik untuk melacak saat ketika : menjadi lebih umum daripada .]

Suatu tipe menggambarkan suatu jenis konstruksi tertentu, yaitu, bagaimana membuat objek dengan struktur tertentu, bagaimana menggunakannya, dan persamaan apa yang berlaku tentang mereka.

Misalnya produk tipe A×B memiliki aturan pengenalan yang menjelaskan cara membuat pasangan yang dipesan, dan aturan eliminasi menjelaskan bahwa kita dapat memproyeksikan komponen pertama dan kedua dari elemen A×B . Definisi A×B tidak tidak mulai dengan kata-kata "koleksi semua ..." dan juga tidak mengatakan apa-apa di mana saja seperti "semua elemen dari A×B adalah pasangan" (tetapi mengikuti dari definisi bahwa setiap unsur A×B bersifat proposisionalsama dengan sepasang). Dalam constrast, definisi set-teori dari X×Y adalah dinyatakan sebagai "himpunan semua pasangan memerintahkan ...".

Notasi t:T menandakan fakta bahwa t memiliki struktur yang dijelaskan oleh T .

Sebuah jenis T tidak menjadi bingung dengan yang ekstensi , yang merupakan koleksi dari semua objek tipe T . Suatu tipe tidak ditentukan oleh ekstensi, sama seperti grup yang tidak ditentukan oleh set carrier-nya. Lebih lanjut, dapat terjadi bahwa dua jenis memiliki ekstensi yang sama, tetapi berbeda, misalnya:

  1. Jenis semua bilangan prima bahkan lebih besar dari dua: Σ(n:N).isprime(n)×iseven(n)×(n>2) .
  2. Jenis semua bilangan prima ganjil lebih kecil dari dua: Σ(n:N).isprime(n)×isodd(n)×(n<2) .

Perpanjangan keduanya kosong, tetapi mereka bukan tipe yang sama.

Ada perbedaan lebih lanjut antara tipe-teoretik : dan set-teoritik . Objek a dalam himpunan teori ada secara independen dari set apa yang menjadi miliknya, dan itu mungkin milik beberapa set. Sebaliknya, sebagian besar jenis teori memuaskan keunikan mengetik: jika t:T dan t:U kemudian TU . Atau dengan kata lain, konstruksi tipe-teoritik t memiliki tepat satu tipe T , dan pada kenyataannya tidak ada cara untuk hanya memiliki objek t tanpa jenisnya (ditentukan secara unik).

Perbedaan lain adalah bahwa dalam menetapkan teori kita dapat menyangkal fakta bahwa aA dengan menulis ¬(aA) atau aA . Ini tidak mungkin dalam teori tipe, karena t:T adalah penilaian yang dapat diturunkan menggunakan aturan teori tipe, tetapi tidak ada dalam teori tipe yang akan memungkinkan kita untuk menyatakan bahwa sesuatu belum diturunkan. Ketika seorang anak membuat sesuatu dari balok LEGO mereka dengan bangga berlari ke orang tua mereka untuk menunjukkan kepada mereka konstruksi, tetapi mereka tidak pernah lari ke orang tua mereka untuk menunjukkan kepada mereka apa yang tidak mereka buat.

Andrej Bauer
sumber
1
Andrej, jawaban yang bagus. Apakah Anda mengetahui asal mula notasi usus besar?
Andreas Rossberg
Sayangnya, saya tidak. Teori tipe Gereja menggunakan subskrip, yaitu, untuk variabel tipe α . Russell dan Whitehead menggunakan ϵ untuk relasi milik suatu kelas. Algol 68 menempatkan tipe di depan nama variabel. The 1972 Martin-Lof jenis teori penggunaan , dan begitu juga dengan versi 1984 , tetapi [1994 versi] menggunakan titik dua. xααϵ
Andrej Bauer
1
Jadi argumen Anda adalah tipe adalah seperti grup? Itu masuk akal, tetapi notasi adalah umum dalam aljabar abstrak. gG
Björn Lindqvist
2
@ BjörnLindqvist: Saya kira jawaban ini bukan cerita lengkap. Bahkan dalam matematika standar yang kami gunakan " " untuk menunjukkan bahwa f adalah fungsi dari S ke T . Mengapa kami tidak menggunakan " f ( S T ) " atau sesuatu seperti itu? Ya, kami tidak melakukannya. Tentu saja, ada alasan bagus untuk menghindari penggunaan " " dalam presentasi teori jenis tertentu, hanya karena kita tidak ingin orang yang diajarkan ZFC berpikir itu seperti set ZFC, yang jelas bukan kasus. Tetapi itu tidak berarti bahwa usus besar belum melakukannyaf:STfSTf(ST)telah banyak digunakan jauh sebelum teori tipe menjadi populer.
user21820
1
@ user21820 "Kenapa kita tidak menggunakan ?" Hanya berspekulasi: karena matematikawan tidak pernah menganggap S T sebagai perangkat. Untuk sejarah notasi ini lihat di sini . Saya ragu bahwa titik dua dari f : S T adalah inspirasi untuk tipe teori. Tipe teori yang lebih mungkin berkaitan dengan titik dua berkaitan dengan fakta bahwa bukan karakter ASCII. f(ST)STf:ST
Michael
5

Björn,

Mungkin ada referensi sebelumnya tetapi untuk satu hal, titik dua digunakan dalam bahasa pemrograman Pascal:

Google hit pertama untuk Pascal

Bjørn Kjos-Hanssen
sumber
2
Apakah tidak ada bahasa pemrograman sebelumnya yang digunakan :?
Andrej Bauer
@AndrejBauer memang, saya menulis "Mungkin ada referensi sebelumnya tapi ..." untuk menjaga terhadap kemungkinan fakta itu.
Bjørn Kjos-Hanssen
@AndrejBauer Algol tidak. Apakah :digunakan dalam makalah teori sebelum tahun 1970-an?
Gilles 'SANGAT berhenti menjadi jahat'
1
Fortran memiliki REAL :: xtetapi saya tidak tahu apakah ini terjadi sebelum Pascal.
Michael
1
@Michael Fortran datang lebih awal dari Pascal (ca. 1955 vs ca. 1970), tapi saya pikir sintaks khusus ini diperkenalkan hanya di Fortran 90, jadi jauh lebih lambat dari Pascal. Lihat misalnya di sini fortranwiki.org/fortran/show/Modernizing+Old+Fortran
Federico