Pertanyaan "Apa bagian dari Hindley-Milner yang kamu tidak mengerti?"


saya bersumpah dulu ada T-shirt untuk dijual yang menampilkan kata-kata abadi:


Bagian apa dari

Hindley-Milner

Apakah kamu tidak memahami?


Dalam kasus saya, jawabannya adalah ... semuanya!

Secara khusus, saya sering melihat notasi seperti ini dalam makalah Haskell, tetapi saya tidak tahu apa artinya. Saya tidak tahu apa cabang matematika itu seharusnya.

Saya mengenali huruf-huruf abjad Yunani tentu saja, dan simbol-simbol seperti "∉" (yang biasanya berarti bahwa sesuatu bukanlah unsur dari suatu himpunan).

Di sisi lain, saya belum pernah melihat "⊢" sebelumnya (Wikipedia mengklaim itu mungkin berarti "partisi"). Saya juga tidak terbiasa dengan penggunaan vinculum di sini. (Biasanya menunjukkan pecahan, tetapi itu tidak muncul menjadi kasus di sini.)

Jika seseorang setidaknya bisa memberi tahu saya di mana harus mulai mencari untuk memahami apa arti simbol lautan ini, itu akan sangat membantu.


750
2017-09-21 14:29


asal


Jawaban:


  • Itu bar horisontal berarti "[di atas] menyiratkan [di bawah]".
  • Jika ada beberapa ekspresi di [atas], lalu pertimbangkan mereka anded bersama; semua [di atas] harus benar untuk menjamin [di bawah].
  • : cara memiliki tipe
  •  cara dalam. (Juga  berarti "tidak dalam".)
  • Γ biasanya digunakan untuk merujuk pada suatu lingkungan Hidup atau konteks; dalam hal ini dapat dianggap sebagai satu set tipe anotasi, memasangkan identifier dengan jenisnya. Karena itu x : σ ∈ Γ berarti lingkungan itu Γ termasuk fakta itu x memiliki tipe σ.
  •  dapat dibaca sebagai terbukti atau menentukan. Γ ⊢ x : σ berarti lingkungan itu Γ menentukan itu x memiliki tipe σ.
  • , adalah cara termasuk asumsi tambahan khusus ke dalam suatu lingkungan Γ.
    Karena itu, Γ, x : τ ⊢ e : τ' berarti lingkungan itu Γ, dengan tambahan, asumsi utama itu x memiliki tipe τ, membuktikan itu e memiliki tipe τ'.

560
2017-09-21 17:28



Sintaks ini, meski mungkin terlihat rumit, sebenarnya cukup sederhana. Ide dasarnya berasal dari logika: seluruh ekspresi adalah implikasi dengan setengah bagian atas adalah asumsi dan setengah bagian bawah adalah hasilnya. Artinya, jika Anda tahu bahwa ekspresi teratas adalah benar, Anda dapat menyimpulkan bahwa ekspresi bawah juga benar.

Simbol

Hal lain yang perlu diingat adalah bahwa beberapa huruf memiliki makna tradisional; khususnya, Γ mewakili "konteks" yang Anda hadapi — yaitu, jenis-jenis hal lain yang telah Anda lihat. Jadi sesuatu seperti itu Γ ⊢ ... berarti "ekspresi ... ketika Anda mengetahui jenis setiap ekspresi di Γ.

Itu  Simbol pada dasarnya berarti Anda dapat membuktikan sesuatu. Begitu Γ ⊢ ... adalah pernyataan yang mengatakan, "Saya bisa membuktikan ... dalam suatu konteks Γ. Pernyataan-pernyataan ini juga disebut penilaian jenis.

Hal lain yang perlu diingat: dalam matematika, sama seperti ML dan Scala, x : σ maksudnya x memiliki tipe σ. Anda bisa membacanya seperti milik Haskell x :: σ.

Apa artinya setiap aturan

Jadi, mengetahui hal ini, ekspresi pertama menjadi mudah dimengerti: jika kita tahu itu x : σ ∈ Γ (itu adalah, x memiliki beberapa tipe σ dalam beberapa konteks Γ), maka kita tahu itu Γ ⊢ x : σ (yaitu, dalam Γ, x memiliki tipe σ). Jadi sungguh, ini tidak memberi tahu Anda sesuatu yang sangat menarik; itu hanya memberitahu Anda bagaimana menggunakan konteks Anda.

Aturan lain juga sederhana. Misalnya, ambil [App]. Aturan ini memiliki dua ketentuan: e₀ adalah fungsi dari beberapa tipe τ untuk beberapa tipe τ' dan e₁ adalah nilai tipe τ. Sekarang Anda tahu jenis apa yang akan Anda dapatkan dengan mendaftar e₀ untuk e₁! Semoga ini bukan kejutan :).

Aturan selanjutnya memiliki beberapa sintaks yang lebih baru. Terutama, Γ, x : τ hanya berarti konteksnya terdiri dari Γ dan penilaiannya x : τ. Jadi, jika kita tahu itu variabelnya x memiliki tipe τ dan ekspresi e memiliki tipe τ', kami juga tahu jenis fungsi yang dibutuhkan x dan kembali e. Ini hanya memberitahu kita apa yang harus dilakukan jika kita sudah tahu apa jenis fungsi yang dibutuhkan dan jenis apa yang dikembalikan, jadi seharusnya tidak mengejutkan juga.

Yang berikutnya hanya memberitahu Anda bagaimana menangani let pernyataan. Jika Anda tahu bahwa beberapa ekspresi e₁ memiliki tipe τ selama x memiliki tipe σ, lalu a let ekspresi yang mengikat secara lokal x ke nilai tipe σ akan membuat e₁ punya tipe τ. Sungguh, ini hanya memberi tahu Anda bahwa pernyataan let pada dasarnya memungkinkan Anda memperluas konteks dengan pengikatan baru — itulah tepatnya let tidak!

Itu [Inst] penawaran aturan dengan sub-mengetik. Ia mengatakan bahwa jika Anda memiliki nilai tipe σ' dan itu adalah sub-jenis σ ( mewakili hubungan pemesanan parsial) maka ekspresi itu juga tipe σ.

Aturan terakhir berkaitan dengan tipe generalisasi. Singkatnya: variabel bebas adalah variabel yang tidak diperkenalkan oleh pernyataan-terbuka atau lambda di dalam beberapa ekspresi; ungkapan ini sekarang bergantung pada nilai variabel bebas dari konteksnya. Aturannya mengatakan bahwa jika ada beberapa variabel α yang mana tidak "bebas" dalam apa pun dalam konteks Anda, maka aman untuk mengatakan bahwa ekspresi apa pun yang jenisnya Anda kenal e : σ akan memiliki tipe itu apa saja Nilai dari α.

Cara menggunakan aturan

Jadi, sekarang setelah Anda memahami simbol, apa yang Anda lakukan dengan aturan ini? Nah, Anda dapat menggunakan aturan ini untuk mencari tahu jenis berbagai nilai. Untuk melakukan ini, lihat ekspresi Anda (katakan f x y) dan temukan aturan yang memiliki kesimpulan (bagian bawah) yang cocok dengan pernyataan Anda. Mari kita sebut hal yang Anda coba temukan "tujuan" Anda. Dalam hal ini, Anda akan melihat aturan yang berakhiran e₀ e₁. Ketika Anda menemukan ini, Anda sekarang harus menemukan aturan yang membuktikan segalanya di atas garis aturan ini. Hal-hal ini umumnya sesuai dengan jenis sub-ekspresi, jadi pada dasarnya Anda mengulang pada bagian-bagian ekspresi. Anda hanya melakukan ini sampai Anda menyelesaikan pohon bukti Anda, yang memberi Anda bukti jenis ekspresi Anda.

Jadi semua aturan ini benar-benar spesifik — dan dalam detail matematika yang biasanya rumit: P — bagaimana cara mengetahui jenis-jenis ekspresi.

Sekarang, ini seharusnya terdengar akrab jika Anda pernah menggunakan Prolog — pada dasarnya Anda sedang menghitung pohon bukti seperti penerjemah Prolog manusia. Ada alasan Prolog disebut "pemrograman logika"! Ini juga penting karena cara pertama saya diperkenalkan ke algoritma inferensi H-M adalah dengan mengimplementasikannya dalam Prolog. Ini sebenarnya sangat sederhana dan membuat apa yang terjadi jelas. Anda tentu harus mencobanya.

Catatan: Saya mungkin membuat beberapa kesalahan dalam penjelasan ini dan akan menyukainya jika seseorang menunjukkannya. Saya akan benar-benar meliput ini di kelas dalam beberapa minggu, jadi saya akan lebih percaya diri kemudian: P.


301
2017-09-21 16:49



jika seseorang setidaknya bisa memberi tahu saya di mana harus mulai mencari untuk memahami apa arti simbol lautan ini

Lihat "Yayasan Praktis Bahasa Pemrograman.", bab 2 dan 3, tentang gaya logika melalui penilaian dan derivasi. Keseluruhan buku ini sekarang tersedia di Amazon.

Bab 2

Definisi Induktif

Definisi induktif adalah alat yang sangat diperlukan dalam mempelajari bahasa pemrograman. Dalam bab ini kita akan mengembangkan kerangka dasar definisi induktif, dan memberikan beberapa contoh penggunaannya. Definisi induktif terdiri dari satu set aturan untuk diturunkan penilaian, atau pernyataan, dari berbagai bentuk. Penghakiman adalah pernyataan tentang satu atau lebih objek sintaksis dari jenis yang ditentukan. Aturan menentukan kondisi yang diperlukan dan cukup untuk validitas penilaian, dan karenanya sepenuhnya menentukan maknanya.

2.1 penilaian

Kami mulai dengan gagasan a pertimbangan, atau tuntutan tentang objek sintaksis. Kami akan menggunakan banyak bentuk penilaian, termasuk contoh-contoh seperti ini:

  • n  nat - n adalah bilangan asli
  • n = n1 + n2 - n adalah jumlah dari n1 dan n2
  • τ  mengetik - τ adalah tipe
  • e : τ - ekspresi e memiliki tipe τ
  • e ⇓ v - ekspresi e memiliki nilai v

Suatu penilaian menyatakan bahwa satu atau lebih objek sintaksis memiliki properti atau berdiri dalam beberapa hubungan satu sama lain. Properti atau hubungan itu sendiri disebut a formulir penilaian, dan penilaian bahwa objek atau benda memiliki properti itu atau berdiri dalam hubungan itu dikatakan sebagai contoh bentuk penilaian itu. Formulir penilaian juga disebut a predikat, dan benda-benda yang merupakan contoh adalah miliknya subyek. Kami menulis Sebuah  J untuk penilaian yang menegaskan itu J memegang Sebuah. Ketika tidak penting untuk menekankan subjek penilaian, (teks memotong di sini)


69
2017-09-21 15:24



Notasi berasal deduksi alami.

⊢ simbol dipanggil pintu putar.

6 aturan itu sangat mudah.

Var aturan adalah aturan yang agak sepele - dikatakan bahwa jika tipe untuk identifier sudah ada di lingkungan jenis Anda, maka untuk menyimpulkan jenis yang baru Anda ambil dari lingkungan seperti apa adanya.

App aturan mengatakan bahwa jika Anda memiliki dua pengidentifikasi e0 dan e1 dan dapat menyimpulkan tipe mereka, maka Anda dapat menyimpulkan jenis aplikasi e0 e1. Aturannya berbunyi seperti ini jika Anda tahu itu e0 :: t0 -> t1 dan e1 :: t0 (t0 yang sama!), maka aplikasi diketik dengan baik dan jenisnya t1.

Abs dan Let adalah aturan untuk menyimpulkan jenis-jenis untuk lambda-abstraksi dan let-in.

Inst aturan mengatakan bahwa Anda dapat mengganti tipe dengan yang kurang umum.


44
2017-09-21 16:21



Bagaimana saya memahami aturan Hindley-Milner?

Hindley-Milner adalah seperangkat aturan dalam bentuk kalkulus berurutan (bukan deduksi alami) yang mengatakan Anda dapat menyimpulkan (paling umum) jenis program dari pembangunan program tanpa deklarasi tipe eksplisit.

Simbol dan notasi

Pertama, mari kita jelaskan simbolnya

  • 𝑥 adalah identifier (secara informal, nama variabel).
  • : berarti adalah jenis (secara informal, sebuah instance dari, atau "is-a").
  • 𝜎 (Sigma) adalah ekspresi yang merupakan variabel atau fungsi.
  • ∈ berarti adalah elemen
  • 𝚪 (Gamma) adalah lingkungan.
  •  (Tanda penegasan) berarti menegaskan (atau membuktikan, tetapi secara kontekstual "menegaskan" membaca lebih baik.)
  • 𝚪⊦ 𝑥  :  𝜎 demikian dibaca 𝚪 menegaskan 𝑥, a 𝜎
  • 𝑒 adalah contoh nyata (elemen) tipe 𝜎.
  • 𝜏 (tau) adalah tipe: baik dasar, variabel (𝛼), fungsional 𝜏 → 𝜏 ', atau produk 𝜏 × 𝜏 '
  • 𝜏 → 𝜏 ' adalah tipe fungsional di mana 𝜏 dan 𝜏 ' adalah tipe.
  • 𝜆𝑥.𝑒 cara 𝜆 (lambda) adalah fungsi anonim yang mengambil argumen, 𝑥, dan mengembalikan ekspresi, 𝑒.
  • membiarkan  𝑥  = 𝑒₀  di  𝑒₁ Berarti dalam ekspresi, 𝑒₁, ganti 𝑒₀ di manapun 𝑥 muncul.
  •  berarti elemen sebelumnya adalah subtipe (informal - subkelas) dari elemen yang terakhir.
  • 𝛼 adalah tipe variabel.
  • 𝛼.𝜎 adalah tipe, ∀ (untuk semua) variabel argumen, 𝛼, kembali 𝜎 ekspresi
  • gratis (𝚪) berarti bukan elemen dari variabel tipe bebas dari 𝚪 yang didefinisikan dalam konteks luar. (Variabel Terikat dapat diganti.)

Segala sesuatu di atas garis adalah premis, semuanya di bawah ini adalah kesimpulan (Per Martin-Löf)

Berikut ini adalah interpretasi bahasa Inggris dari pernyataan logika, diikuti dengan penjelasan.

Variabel

VAR Logic Diagram

Diberikan 𝑥 adalah tipe 𝜎 (sigma), elemen 𝚪 (Gamma),
menyimpulkan 𝚪 menegaskan 𝑥 adalah 𝜎.

Ini pada dasarnya adalah tautologi - nama pengenal adalah variabel atau fungsi.

Aplikasi Fungsi

APP Logic Diagram

Diberikan 𝚪 menegaskan 𝑒₀ adalah tipe fungsional dan 𝚪 menegaskan 𝑒₁ adalah 𝜏
menyimpulkan 𝚪 menegaskan penerapan fungsi 𝑒₀ to 𝑒₁ adalah tipe 𝜏 '

Ini berarti bahwa jika kita tahu bahwa suatu fungsi mengembalikan suatu tipe, dan kita menerapkannya ke sebuah argumen, hasilnya akan menjadi sebuah instance dari jenis yang kita tahu ia akan kembali.

Fungsi Abstraksi

ABS Logic Diagram

Diberikan 𝚪 dan 𝑥 tipe 𝜏 menegaskan 𝑒 adalah tipe, 𝜏 '
menyimpulkan 𝚪 menegaskan fungsi anonim, 𝜆 dari 𝑥 ekspresi kembali, 𝑒 adalah tipe 𝜏 → 𝜏 '.

Ini berarti bahwa jika kita tahu 𝑥 adalah tipe 𝜏 dan dengan demikian ekspresi 𝑒 adalah tipe 𝜏 ', maka fungsi 𝑥 ekspresi kembali 𝑒 adalah tipe 𝜏 → 𝜏'.

Biarkan deklarasi variabel

LET Logic Diagram

Diberikan 𝚪 menegaskan 𝑒₀, tipe 𝜎, dan 𝚪 dan 𝑥, tipe 𝜎, menegaskan 𝑒₁ tipe 𝜏
menyimpulkan 𝚪 menegaskan let 𝑥 = 𝑒₀ in 𝑒₁ tipe 𝜏

Ini berarti jika kita memiliki ekspresi 𝑒₀ yang merupakan 𝜎 (menjadi variabel atau fungsi), dan beberapa nama, 𝑥, juga 𝜎, dan ekspresi 𝑒₁ tipe 𝜏, maka kita dapat mengganti 𝑒₀ untuk 𝑥 di mana pun itu muncul di dalam dari 𝑒₁.

Instansiasi

INST Logic Diagram

Diberikan 𝚪 menegaskan 𝑒 tipe 𝜎 'dan 𝜎' adalah subtipe 𝜎
menyimpulkan 𝚪 menegaskan 𝑒 adalah tipe 𝜎

Ini mengatakan bahwa jika sebuah instance adalah tipe yang merupakan subtipe dari tipe lain, ia juga merupakan instance dari tipe super itu.

Ini memungkinkan kita untuk menggunakan jenis instantiasi dalam pengertian yang lebih umum bahwa sebuah ekspresi dapat mengembalikan tipe yang lebih spesifik.

Generalisasi

GEN Logic Diagram

Diberikan 𝚪 menegaskan 𝑒 adalah 𝜎 dan 𝛼 bukan merupakan elemen dari variabel bebas 𝚪,
menyimpulkan 𝚪 menegaskan 𝑒, ketik untuk semua ekspresi argumen 𝛼 mengembalikan 𝜎 ekspresi

Ini berarti kita dapat menggeneralisasi sebuah program untuk menerima semua jenis argumen yang belum terikat dalam ruang lingkup yang mengandung (variabel yang bukan non-lokal). Variabel terikat ini dapat disubstitusikan.

Kesimpulan

Aturan-aturan ini dikombinasikan memungkinkan kita untuk membuktikan jenis yang paling umum dari sebuah program yang ditegaskan, tanpa memerlukan anotasi tipe, memungkinkan untuk berbagai jenis untuk diterima dengan benar sebagai input (parametric polymorphism).


23
2018-02-03 23:01



Ada dua cara untuk memikirkan e: σ. Salah satunya adalah "ekspresi e memiliki tipe σ", yang lain adalah "pasangan yang berurutan dari ekspresi e dan jenis σ".

Lihat Γ sebagai pengetahuan tentang jenis ekspresi, diimplementasikan sebagai sekumpulan pasang ekspresi dan jenis, e: σ.

The turnstile ⊢ berarti bahwa dari pengetahuan di sebelah kiri, kita dapat menyimpulkan apa yang ada di sebelah kanan.

Aturan pertama [Var] dapat dibaca:
Jika pengetahuan kita Γ berisi pasangan e: σ, maka kita dapat menyimpulkan dari Γ bahwa e memiliki tipe σ.

Aturan kedua [Aplikasi] dapat dibaca:
Jika kita dari Γ dapat menyimpulkan bahwa e_0 memiliki tipe τ → τ ', dan kita dari Γ dapat menyimpulkan bahwa e_1 memiliki tipe τ, maka kita dari Γ dapat menyimpulkan bahwa e_0 e_1 memiliki tipe τ'.

Ini biasa untuk menulis Γ, e: σ daripada Γ ∪ {e: σ}.

Aturan ketiga [Abs] dapat dibaca:
Jika kita dari Γ diperpanjang dengan x: τ dapat menyimpulkan bahwa e memiliki tipe τ ', maka kita dari Γ dapat menyimpulkan bahwa λx.e memiliki tipe τ → τ'.

Aturan keempat [Biarkan] dibiarkan sebagai latihan. :-)

Aturan kelima [Inst] dapat dibaca:
Jika kita dari Γ dapat menyimpulkan bahwa e memiliki tipe σ ', dan σ' adalah subtipe dari σ, maka kita dari Γ dapat menyimpulkan bahwa e memiliki tipe σ.

Aturan keenam dan terakhir [Gen] dapat dibaca:
Jika kita dari Γ dapat menyimpulkan bahwa e memiliki tipe σ, dan α bukan merupakan variabel tipe bebas dalam salah satu dari jenis Γ, maka kita dari Γ dapat menyimpulkan bahwa e memiliki tipe ∀α σ.


16
2018-04-25 14:55