Aplikasi Harian Teori Jenis

10

Saya ingin memahami teori jenis tetapi saya harus tahu dulu bagaimana saya bisa menerapkannya. Mungkinkah ada aplikasi yang lebih jelas dari teori tipe selain dari sistem tipe dalam pemrograman? Mungkinkah ada aplikasi lain, katakanlah dalam profil kepribadian dan sejenisnya?

type-theory applied-theory Tamad Lang
sumber
2
Mengapa sesuatu harus memiliki aplikasi di luar untuk apa ia diciptakan?
Raphael
3
Yayasan matematika? Orang-orang juga telah menggunakan teori tipe untuk memformalkan hal-hal seperti teori domain sintetik, topologi, dll. Ada juga karya Chris Martens tentang penggunaan alat teoretik tipe untuk memodelkan penceritaan kisah naratif. Tautan disertasi
Daniel Gratzer
1
Bisakah Anda mengklarifikasi jumlah sebagai aplikasi?
Jake
4
Saya tidak yakin dengan premis Anda. Misalkan seseorang berkata, "Saya ingin memahami teknik otomotif tetapi saya harus tahu dulu untuk apa saya bisa menggunakan mobil. Mungkinkah ada aplikasi mobil yang lebih tidak jelas selain transportasi?" Mereka mendapat jawaban dengan mengatakan bahwa beberapa orang tidur di mobil mereka, dan Ansel Adams menggunakan nya sebagai platform untuk mengambil foto . Yah itu bagus tapi itu tidak membantu siapa pun memahami teknik dan kemungkinan akan mengarahkan siswa hipotetis kami untuk merancang mobil dengan kursi super-berbaring dan suspensi yang sangat kaku.
David Richerby
3
Faktanya adalah bahwa banyak ilmu komputer teoritis (termasuk hal-hal yang saya kerjakan) praktis tidak berguna, meskipun secara matematis indah. Sayangnya Anda harus memilih sisi.
Yuval Filmus

Jawaban:

10

Anda mungkin tertarik pada karya tentang Ceptre , hasil penelitian PhD dari Chris Martens , yang menggunakan teori tipe untuk penceritaan interaktif. Dikutip di bawah ini adalah abstrak tesis :

Mendongeng interaktif menyatukan ide-ide komputasi yang mendalam dengan sejarah cerita dan permainan manusia yang kaya, memberikan konteks penting untuk alat dan bahasa yang akan dibangun. Pada saat yang sama, bahasa spesifikasi formal menawarkan palet teknik representasi dan inferensi yang biasanya disediakan untuk analisis bahasa pemrograman dan sistem deduktif yang kompleks. Tesis ini menghubungkan masalah-masalah dalam domain mendongeng interaktif dengan solusi dalam spesifikasi formal.

Secara khusus, kami memeriksa narasi dari sudut pandang struktural dan mengamati bahwa jalur naratif alternatif memainkan peran yang saling melengkapi untuk jadwal waktu yang berinteraksi secara simultan. Logika linier menyediakan alat representasional yang diperlukan untuk menyelidiki struktur ini, dan dengan memperluas korespondensi ke bukti dan konstruksi bukti, kami menemukan serangkaian kemungkinan komputasi. Kami menyajikan tiga upaya untuk mewujudkan kemungkinan itu: (1) penggunaan pemrograman logika linier untuk menghasilkan narasi; (2) bahasa pemrograman baru untuk penulisan narasi interaktif, permainan, dan simulasi; dan (3) teknik untuk menyatakan dan membuktikan properti program tingkat desain.

Kami menemukan bahwa pemrograman logika linier, diperkaya dengan ekstensi minimal ke semantik logisnya, memungkinkan berbagai idiom pemrograman dan pengkodean domain. Sebagai bukti, kami memberikan lima studi kasus, termasuk simulasi sosial, game petualangan berbasis pertempuran, dan game papan. Untuk mendukung alasan tentang kebenaran desain, kami menyajikan teknik untuk menyatakan dan membuktikan invarian program, serta bukti decidability untuk secara otomatis memeriksa invarian tersebut untuk fragmen besar bahasa.

Temuan ini menunjukkan bahwa logika linier adalah bahasa representasi yang bermanfaat untuk berfungsi sebagai dasar untuk pemodelan dan mengeksekusi dunia interaktif, dan mereka mengundang penyelidikan di masa depan tentang penggunaan metodologi bukti-teoretis untuk sistem kreatif.

gasche
sumber
1
Itu terdengar seperti penggunaan logika linier, bukan tipe teori per se .
David Richerby
6
Logika linier adalah topik landasan dari teori tipe. Karya ini sangat banyak bagian dari teori tipe sebagai disiplin (beberapa orang menggambarkan pekerjaan mereka sebagai "teori bukti" ketika itu sama relevan dengan teori tipe, meskipun nama-nama tidak setara dengan beberapa karya lain dalam "teori bukti" akan dianggap sebagai lebih spesifik untuk teori pembuktian daripada juga pusat untuk mengetik teori).
gasche
9

Ada penggunaan teori tipe yang menarik dalam linguistik. Lihat misalnya karya linguistik Chung-chieh Shan atau Christian Rétoré .

Dikutip di bawah ini adalah deskripsi buku Rétoré tentang tata bahasa kategori:

Buku ini adalah pengantar kontemporer dan komprehensif untuk tata bahasa kategoris dalam tradisi logis yang diprakarsai oleh karya Lambek. Ini membimbing siswa dan peneliti melalui hasil mendasar di lapangan, memberikan bukti modern dari banyak teorema klasik, serta kemajuan orisinal baru-baru ini. Banyak contoh dan latihan menggambarkan motivasi dan aplikasi hasil ini dari sudut pandang linguistik, komputasi dan logis. Kalkulus Lambek dan variannya, dan tata bahasa yang sesuai, merupakan inti dari catatan kuliah ini. Sebuah bab dikhususkan untuk fitur kunci dari tata bahasa kategori ini: antarmuka sintaksis semantik yang sangat elegan. Selain itu, kami mengadaptasi jaring bukti logika linier dengan kalkuli ini karena mereka menyediakan algoritma penguraian yang efisien sebagaimana dicontohkan dalam pengurai Grail.

Kutipan berikut adalah dalam pengantar bab buku Efek Samping Linguistik Shan :

Makalah ini menghubungkan kasus-kasus nonkomposisi yang tampak dalam bahasa alami dengan yang dalam bahasa pemrograman. Bentuknya seperti jam pasir: Saya mulai pada § 1 dengan pendekatan ke antarmuka semantik sintaksis yang membantu kita membangun teori semantik komposisi. Pendekatan itu adalah untuk menggambar analogi antara efek samping komputasi dalam bahasa pemrograman dan apa yang saya sebut dengan efek samping linguistik analogi dalam bahasa alami.

Koneksi ini dapat bermanfaat bagi para ilmuwan komputer maupun ahli bahasa, tetapi saya fokus di sini pada arah transfer teknologi yang terakhir. Lanjutan telah berguna untuk mengobati efek samping komputasi. Dalam §2, saya memperkenalkan bahasa logam baru untuk kelanjutan dalam semantik.

Bahasa logam yang saya perkenalkan berguna untuk menganalisis bahasa pemrograman dan bahasa alami. Untuk intuisi, saya mensurvei penggunaan pertama dalam §3, kemudian tunjukkan manfaat dari perawatan ini di §4.

Beralih ke bahasa alami dalam §5, saya menjelaskan secara terperinci bagaimana perspektif ini membantu Chris Barker dan saya mempelajari ikatan dan crossover, serta pertanyaan-pertanyaan dan superioritas. Saya juga telah menggunakan kelanjutan untuk mempelajari quantifier dan wh-indefinite scope, khususnya dalam bahasa Mandarin, tetapi hanya ada ruang di sini untuk membuat sketsa perkembangan lebih lanjut ini, di §6.

gasche
sumber
9

Karena korespondensi Curry-Howard , tipe dapat diartikan sebagai proposisi, dan proposisi sebagai tipe.

Sebagai hasil dari ini, teori tipe berlaku untuk setiap bidang yang menggunakan logika formal untuk pembuktiannya. Ini bisa berupa verifikasi rangkaian, analisis nyata, logika simbolik, geometri, dll.

Sebagai contoh, beberapa alat pemeriksaan bukti otomatis bekerja menggunakan prinsip ini: mereka memeriksa validitas bukti dengan memeriksa jenis istilah tertentu dalam beberapa jenis sistem. Pemeriksa bukti LF didasarkan pada pendekatan ini, seperti juga HOL Light . Sebagai contoh aplikasi, kode pembawa bukti menggunakan LF untuk memeriksa bukti keamanan memori dari kode yang tidak dipercaya. Manfaat menggunakan pemeriksa bukti semacam ini adalah bahwa implementasinya bisa sangat sederhana, dan dengan demikian kita dapat memperoleh kepastian yang tinggi bahwa implementasinya benar. Lihat, misalnya, makalah berikut:

Pemeriksa Bukti Dasar dengan Saksi-Saksi Kecil . Dinghao Wu, Andrew W. Appel, Aaron Stump. PPDP 2003.

Ya ampun
sumber
Ini mungkin membantu: math.ucr.edu/home/baez/rosetta.pdf
Nama samaran
Saya tidak berpikir ini menjawab pertanyaan. Bagaimana dengan aplikasi yang sebenarnya?
Yuval Filmus
@YuvalFilmus Tentukan "aktual"?
David Richerby
1
Apakah Anda tahu jika ada yang menggunakan teori tipe untuk membuktikan sesuatu yang baru tentang verifikasi rangkaian, analisis nyata, logika simbolik atau geometri? Atau apakah kita hanya berbicara tentang kasus di mana seseorang menggunakan 20 halaman teori tipe untuk membuktikan sesuatu yang mengambil tiga baris dalam buku teks dasar?
David Richerby
@ David Apa jawaban ini adalah bahwa pada prinsipnya Anda dapat menggunakan teori tipe untuk membuktikan barang. Juga, pada prinsipnya kita dapat menggunakan automata seluler untuk membuktikan barang, karena Aturan 110 adalah Turing-complete. Saya pikir pernyataan sebelumnya sama tidak berartinya dengan yang terakhir.
Yuval Filmus
7

Artikel menarik yang menjelaskan aplikasi tipe dependen, adalah The Power of Pi , yang menunjukkan bagaimana Agda dapat digunakan untuk memecahkan masalah yang menarik.

Contoh bagus lainnya adalah penggunaan tipe dependen untuk mengontrol sumber daya. Sebuah contoh yang baik adalah file manajemen API dari Efek dari Idris . Misalnya, fungsi untuk membaca baris dari file memiliki tipe berikut

readLine  : { [FILE_IO (OpenFile Read)] } Eff String

yang menentukan bahwa fungsi ini hanya berlaku jika ada file yang dibuka. Daftar dalam kurung menunjukkan efek mana yang tersedia. Dalam hal ini, kami berpendapat bahwa fungsi ini memerlukan efek membuka file untuk dibaca.

Informasi lebih lanjut tentang perpustakaan Efek dapat ditemukan di sini .

Satu lagi aplikasi adalah penggunaan tipe dependen untuk konkurensi seperti yang dilaporkan dalam artikel berikut oleh pencipta Idris.

Rodrigo Ribeiro
sumber
1
Lebih banyak contoh ditambahkan.
Rodrigo Ribeiro
3

seperti yang disebutkan dalam jawaban jmite, logika tipe / teori tipe tinggi dalam rangkaian / verifikasi perangkat keras / elektronik telah ada selama beberapa dekade dan sekarang sangat rutin sehingga bahkan tidak diperhatikan / dianggap sebagai "aplikasi" setelah upaya transfer yang tampaknya besar dalam ~ 1990-an meskipun masih merupakan bidang penelitian aktif. ada juga banyak aplikasi Coq dan jenis logika khususnya untuk rangkaian / perangkat keras / verifikasi elektronik sepanjang jalan dari gerbang logika tingkat rendah ke tingkat / struktur tatanan / subsistem yang jauh lebih tinggi. berikut adalah beberapa referensi kunci

vzn
sumber
1
Agar adil, meskipun, verifikasi perangkat keras yang paling aktual pada skala industri telah dilakukan dengan menggunakan pengecekan model, teknologi verifikasi yang umumnya tidak terkait dengan teori jenis (meskipun jembatan telah ditarik baru-baru ini). Teori tipe telah digunakan untuk membangun bahasa deskripsi perangkat keras (tidak dibuat-buat dari bahasa pemrograman), dan sebagian besar bahasa yang Anda berikan ada dalam kategori ini, dan beberapa asisten bukti yang dirancang untuk verifikasi perangkat keras (terutama HOL asli, tetapi bukan PVS yang paling banyak digunakan) adalah Curry-Howard transposes of type theory.
gasche
jika Anda memiliki latar belakang yang lebih dalam dalam verifikasi perangkat keras, akan menarik untuk mendengar lebih banyak detail dalam Obrolan Ilmu Komputer tetapi berpikir / mencurigai garis yang sempit / generalisasi tidak mudah untuk digambar di area ini misalnya antara pengecekan model dan teori jenis. diperlukan analisis historis yang sangat halus untuk secara komprehensif mengungkap / menyatukan koneksi antara dua bidang yang berbeda dengan tujuan yang berbeda dan kadang-kadang bahkan di luar kemampuan para ahli di kedua bidang secara individual ... keseluruhan referensi menunjukkan koneksi yang kuat yang dapat dianalisis lebih lanjut. ..
vzn