menerapkan tipe inferensi

Saya melihat beberapa diskusi menarik di sini tentang pengetikan statis vs. dinamis. Saya biasanya lebih suka pengetikan statis, karena pemeriksaan jenis kompilasi, kode yang didokumentasikan lebih baik, dll. Namun, saya setuju bahwa mereka mengacaukan kode jika dilakukan dengan cara Java, misalnya.

Jadi saya akan mulai membangun bahasa gaya fungsional saya sendiri, dan jenis inferensi adalah salah satu hal yang ingin saya terapkan. Saya mengerti bahwa ini adalah subjek besar, dan saya tidak mencoba membuat sesuatu yang belum pernah dilakukan sebelumnya, hanya menyimpulkan dasar ...

Ada petunjuk tentang apa yang harus dibaca yang akan membantu saya dalam hal ini? Lebih disukai sesuatu yang lebih pragmatis / praktis dibandingkan dengan teks teori kategori / jenis teori yang lebih teoritis. Jika ada teks diskusi implementasi di luar sana, dengan struktur data / algoritme, itu akan menyenangkan.

Saya menemukan sumber daya berikut berguna untuk memahami jenis inferensi, untuk meningkatkan kesulitan:

1. Bab 30 (Jenis Inferensi) dari buku PLAI yang tersedia secara bebas , Bahasa Pemrograman: Aplikasi dan Interpretasi , membuat sketsa jenis inferensi berbasis penyatuan.
2. Kursus musim panas Menginterpretasikan tipe sebagai nilai abstrak menghadirkan evaluator yang elegan, pemeriksa tipe, rekonstruksi tipe, dan inferencer menggunakan Haskell sebagai bahasa logam.
3. Bab 7 (Jenis) dari buku EOPL , Essentials of Programming Languages .
4. Bab 22 (Jenis Rekonstruksi) dari buku TAPL , Jenis dan Bahasa Pemrograman , dan implementasi OCaml yang sesuai, rekon dan fullrecon .
5. Bab 13 (Jenis Rekonstruksi) dari buku baru DCPL , Konsep Desain dalam Bahasa Pemrograman .
6. Seleksi makalah akademis .
7. TypeInference compiler penutupan adalah contoh pendekatan analisis aliran data untuk jenis inferensi, yang lebih cocok untuk bahasa dinamis yang pendekatan Hindler Milner.

Namun, karena cara terbaik untuk belajar adalah melakukannya, saya sangat menyarankan penerapan inferensi tipe untuk bahasa fungsional mainan dengan mengerjakan tugas pekerjaan rumah dari kursus bahasa pemrograman.

Saya merekomendasikan dua pekerjaan rumah yang dapat diakses di ML ini, yang dapat Anda selesaikan dalam waktu kurang dari sehari:

1. PCF Interpreter ( solusi ) untuk pemanasan.
2. PCF Type Inference ( solusi ) untuk mengimplementasikan algoritma W untuk inferensi tipe Hindley-Milner.

Tugas ini berasal dari kursus yang lebih maju:

1. Menerapkan MiniML

2. Jenis Polimorfik, Eksistensial, Rekursif (PDF)

3. Pemeriksaan Ketikan Dua Arah (PDF)

4. Subtipe dan Objek (PDF)

Sangat disayangkan banyak literatur tentang masalah ini sangat padat. Saya juga berada di posisi Anda. Saya mendapatkan pengantar pertama saya untuk subjek dari Bahasa Pemrograman: Aplikasi dan Interpretasi

http://www.plai.org/

Saya akan mencoba meringkas ide abstrak diikuti dengan detail yang tidak langsung saya temukan dengan jelas. Pertama, jenis inferensi dapat dianggap menghasilkan dan kemudian memecahkan kendala. Untuk menghasilkan batasan, Anda mengulang melalui pohon sintaks dan menghasilkan satu atau lebih batasan pada setiap node. Misalnya, jika node adalah +operator, operan dan hasilnya harus berupa angka. Node yang menerapkan suatu fungsi memiliki tipe yang sama dengan hasil dari fungsi tersebut, dan seterusnya.

Untuk bahasa tanpa let, Anda dapat menyelesaikan kendala di atas secara membabi buta dengan substitusi. Sebagai contoh:

(if (= 1 2) 
    1 
    2)

di sini, kita dapat mengatakan bahwa kondisi pernyataan jika harus Boolean, dan bahwa jenis pernyataan jika adalah sama dengan jenis yang thendan elseklausa. Karena kita tahu 1dan 2adalah angka, dengan substitusi, kita tahu ifpernyataannya adalah angka.

Di mana hal-hal menjadi buruk, dan apa yang saya tidak bisa mengerti untuk sementara waktu, berurusan dengan biarkan:

(let ((id (lambda (x) x)))
    (id id))

Di sini, kita telah terikat idke sebuah fungsi yang mengembalikan apa pun yang telah Anda teruskan, atau dikenal sebagai fungsi identitas. Masalahnya adalah jenis parameter fungsi xberbeda pada setiap penggunaan id. Yang kedua idadalah fungsi tipe a -> a, di mana abisa menjadi apa saja. Yang pertama adalah tipe (a -> a) -> (a -> a). Ini dikenal sebagai let-polymorphism. Kuncinya adalah memecahkan kendala dalam urutan tertentu: pertama-tama selesaikan kendala untuk definisi id. Ini akan menjadi a -> a. Kemudian baru, salinan terpisah dari jenis iddapat diganti menjadi batasan untuk setiap tempat iddigunakan, misalnya a2 -> a2dan a3 -> a3.

Itu tidak mudah dijelaskan dalam sumber daya online. Mereka akan menyebutkan algoritma W atau M tetapi tidak bagaimana mereka bekerja dalam hal memecahkan kendala, atau mengapa tidak muncul pada let-polimorfisme: masing-masing algoritma tersebut memberlakukan urutan untuk memecahkan kendala.

Saya menemukan sumber daya ini sangat membantu untuk mengikat Algoritma W, M, dan konsep umum pembuatan kendala dan menyelesaikan semuanya bersama-sama. Ini sedikit padat, tapi lebih baik dari banyak:

http://www.cs.uu.nl/research/techreps/repo/CS-2002/2002-031.pdf

Banyak makalah lain di sana juga bagus:

http://people.cs.uu.nl/bastiaan/papers.html

Saya harap itu membantu menjelaskan dunia yang agak suram.

Selain Hindley Milner untuk bahasa fungsional, pendekatan populer lainnya untuk jenis inferensi untuk bahasa dinamis adalah abstract interpretation.

Ide interpretasi abstrak adalah untuk menulis interpreter khusus untuk bahasa tersebut, alih-alih menjaga lingkungan nilai-nilai konkret (1, false, closure), ia bekerja pada nilai-nilai abstrak, alias tipe (int, bool, dll). Karena menafsirkan program pada nilai-nilai abstrak, itulah mengapa disebut interpretasi abstrak.

Pysonar2 adalah implementasi elegan dari interpretasi abstrak untuk Python. Ini digunakan oleh Google untuk menganalisis proyek Python. Pada dasarnya ini digunakan visitor patternuntuk mengirimkan panggilan evaluasi ke node AST yang relevan. Fungsi pengunjung transform menerima contextdi mana node saat ini akan dievaluasi, dan mengembalikan jenis node saat ini.

Jenis dan Bahasa Pemrograman oleh Benjamin C. Pierce

Lambda the Ultimate, mulai dari sini .