Apa implikasi praktis dari teori tipe homotopy dalam pemrograman?

11

Saya baru mulai belajar Haskell, setelah datang dari dunia JavaScript / Ruby. Saya telah menemukan https://github.com/HoTT dan buku Teori Tipe Homotopy , yang sangat ingin saya baca.

Namun, saya akan belajar konsep teori matematika dan tipe saat saya pergi, jadi sepertinya akan butuh waktu lama sebelum saya mengerti apa arti teori tipe homotopy bagi programmer yang berlatih.

Bisakah Anda menggambarkan apa dampak teori tipe homotopy akan memiliki pada pemrograman dalam praktek, untuk orang awam? Misalnya, apakah akan membuat hal-hal tertentu lebih mudah untuk lebih mudah ditulis? Jika demikian, hal-hal apa? Atau akankah ini memungkinkan Anda melakukan hal-hal baru dalam pemrograman yang sebelumnya tidak mungkin? Jika demikian, hal-hal apa?

Terima kasih, sangat menantikan untuk melilitkan kepalaku di tingkat yang lebih dasar.

type-theory Lance Pollard
sumber
Saya berharap begitu, dan akan selalu tidak dapat dipahami oleh para programmer yang berlatih. Paling-paling, kita mungkin mendapatkan kompiler yang lebih cepat atau kotak hitam magis yang memanfaatkan matematika-fu.
Telastyn
Haha, inilah yang selama ini saya pikirkan. Saya masih bertanya-tanya, apakah ini jawabannya atau ada sesuatu yang melebihi apa yang Anda katakan? Sebagai contoh, bisakah database mendapat manfaat dari ini? Atau semacamnya.
Lance Pollard
1
Saya tidak punya ide. Saya membaca abstrak dan segera menjatuhkannya ke ember untuk omong kosong akademis yang tak bisa dipahami.
Telastyn
direkomendasikan membaca: Bagaimana cara saya menjelaskan $ {sesuatu} ke $ {seseorang}?
Agak
4
@ Telastyn: Jika Anda mengunduh buku dalam bahasa Portugis, buku itu juga tidak akan dapat dipahami selama Anda belum mencoba mempelajari bahasa tersebut. Mengapa secara terbuka mencela buku-buku Portugis dengan istilah menghina -omong-omong ? Motivasi Gödels untuk memperkenalkan fungsi rekursif primitif adalah sangat akademis, khususnya karena dunia bahkan tidak menjalankan program apa pun di usia 30-an. Saya tidak berpikir hanya karena seseorang adalah seorang programmer yang berlatih, topik-topik akademik akan "selalu tetap tidak dapat dipahami" dengan kemampuan Anda.
Nikolaj-K

Jawaban:

15

Salah satu hal kuat yang dapat dilakukan oleh kompiler selama fase optimisasi mereka adalah untuk menukar representasi yang tidak efisien dengan yang setara. Misalnya, di Haskell Anda bisa menggunakan daftar malas untuk menghitung jumlah angka, tetapi kompiler GHC Haskell akan mengakui bahwa ini setara dengan menggunakan iterasi dengan variabel sementara. Dengan begitu, Anda dapat memprogram melawan abstraksi sederhana yang mudah dipikirkan, sementara eksekusi Anda memanfaatkan representasi yang lebih cocok untuk platform perangkat keras (dan itu terjadi jauh lebih sulit untuk dipikirkan pada skala).

Namun, kesetaraan yang diketahui oleh kompiler sebagian besar terbatas pada struktur data yang diketahui dan diteliti, seperti aliran fusi untuk daftar. Anda dapat menentukan persamaan Anda sendiri dalam kode sumber (menggunakan sepasang fungsi konversi yang menyusun identitas di kedua arah), tetapi Anda harus menerapkannya secara manual, dan mungkin sulit untuk memilih jenis yang tepat untuk digunakan di semua tempat untuk menghindari konversi yang berlebihan.

Sekarang mari kita bayangkan sebuah dunia di mana Anda bisa mendefinisikan "tipe induktif yang lebih tinggi", katakanlah peta pencarian kanonik. Tipe ini memiliki beberapa konstruktor untuk berbagai jenis peta: pencarian biner, AVL, merah-hitam, Trie, Patricia, dll. Seiring dengan konstruktor data yang khas, Anda juga menentukan tipe ekivalen yang menangkap kemungkinan beberapa konversi antara representasi ini, di mana berbeda konversi menawarkan berbagai dimensi efisiensi (yaitu, waktu vs. memori).

Bagaimana jika kompiler dapat menggunakan gagasan ini untuk menulis ulang representasi peta secara transparan, seperti yang dapat dilakukan hari ini dengan fusi daftar? Sementara itu, dalam kode Anda, Anda bisa bekerja dengan konstruksi yang paling sederhana untuk dipikirkan (dan membuat pembuktian bekerja lebih mudah, jika Anda berada di lingkungan seperti itu). Ini mungkin terdengar seperti antarmuka abstrak dengan beberapa implementasi, tetapi ini mencakup kebebasan untuk memilih implementasi apa pun dan membuat kompiler secara transparan mengganti yang lain sesuai kebutuhan, tanpa memengaruhi makna program.

HoTT memberi kita jenis dasar teori untuk membenarkan mekanisme penulisan ulang yang mewah ini dan jenis-jenis yang didefinisikan dengan kaya ini, karena mempromosikan gagasan kesetaraan menjadi setara dengan kesetaraan. Masih harus dilihat bagaimana ini akan benar-benar dimainkan dalam praktek, tetapi ini memberi kita kerangka teoritis yang menjadi dasar kerja masa depan.

John Wiegley
sumber