Saya sedang mengerjakan kompiler kalkulus lambda kecil yang memiliki sistem inferensi tipe Hindley-Milner yang berfungsi dan sekarang juga mendukung rekursif mari (bukan dalam kode tertaut), yang saya pahami harus cukup untuk membuatnya Turing lengkap .
Masalahnya sekarang adalah saya tidak tahu bagaimana membuatnya menjadi daftar dukungan, atau apakah sudah mendukung mereka dan saya hanya perlu menemukan cara untuk menyandikannya. Saya ingin dapat mendefinisikannya tanpa harus menambahkan aturan baru ke sistem tipe.
Cara termudah yang dapat saya pikirkan tentang daftar x
adalah sebagai sesuatu yang bisa berupa null
(atau daftar kosong), atau pasangan yang mengandung keduanya x
dan daftar x
. Tetapi untuk melakukan ini saya harus dapat mendefinisikan pasangan dan atau, yang saya percaya adalah produk dan jenis penjumlahannya.
Sepertinya saya bisa mendefinisikan pasangan dengan cara ini:
pair = λabf.fab
first = λp.p(λab.a)
second = λp.p(λab.b)
Karena pair
akan memiliki tipe a -> (b -> ((a -> (b -> x)) -> x))
, setelah melewati, katakan, an int
dan a string
, itu akan menghasilkan sesuatu dengan tipe (int -> (string -> x)) -> x
, yang akan menjadi representasi dari sepasang int
dan string
. Apa yang mengganggu saya di sini adalah bahwa jika itu mewakili pasangan, mengapa itu tidak setara dengan logis, atau menyiratkan proposisi int and string
? Namun, setara dengan (((int and string) -> x) -> x)
, seolah-olah saya hanya bisa memiliki tipe produk sebagai parameter untuk fungsi. Jawaban initampaknya mengatasi masalah ini, tetapi saya tidak tahu apa arti simbol yang dia gunakan. Juga, jika ini tidak benar-benar menyandikan jenis produk, apakah ada yang bisa saya lakukan dengan jenis produk yang tidak dapat saya lakukan dengan definisi pasangan saya di atas (mengingat saya juga dapat mendefinisikan n-tuple dengan cara yang sama)? Jika tidak, tidakkah ini akan bertentangan dengan fakta bahwa Anda tidak dapat mengungkapkan kata kata (AFAIK) hanya menggunakan implikasi?
Juga, bagaimana dengan tipe penjumlahan? Bisakah saya menyandikannya menggunakan tipe fungsi saja? Jika demikian, apakah ini cukup untuk mendefinisikan daftar? Atau yang lain, apakah ada cara lain untuk mendefinisikan daftar tanpa harus memperluas sistem tipe saya? Dan jika tidak, perubahan apa yang harus saya lakukan jika saya ingin membuatnya sesederhana mungkin?
Harap diingat bahwa saya adalah pemrogram komputer tetapi bukan ilmuwan komputer atau ahli matematika dan sangat buruk dalam membaca notasi matematika.
Sunting: Saya tidak yakin apa nama teknis dari apa yang telah saya implementasikan sejauh ini, tetapi semua yang saya miliki pada dasarnya adalah kode yang saya tautkan di atas, yang merupakan algoritma pembatas kendala yang menggunakan aturan untuk aplikasi, abstraksi dan variabel yang diambil dari algoritma Hinley-Milner dan kemudian algoritma unifikasi yang mendapatkan tipe utama. Misalnya, ekspresi \a.a
akan menghasilkan jenis a -> a
, dan ekspresi \a.(a a)
akan melempar kesalahan pemeriksaan yang terjadi. Di atas ini, tidak ada let
aturan tetapi fungsi yang tampaknya memiliki efek yang sama yang memungkinkan Anda mendefinisikan fungsi global rekursif seperti pseudo-code ini:
GetTypeOfGlobalFunction(term, globalScope, nameOfFunction)
{
// Here 'globalScope' contains a list of name-value pair where every value is of class 'ClosedType',
// meaning their type will be cloned before unified in the unification algorithm so that they can be used polymorphically
tempType = new TypeVariable() // Assign a dummy type to `tempType`, say, type 'x'.
// The next line creates an scope with everything in 'globalScope' plus the 'nameOfFunction = tempType' name-value pair
tempScope = new Scope(globalScope, nameOfFunction, tempType)
type = TypeOfTerm(term, tempScope) // Calculate the type of the term
Unify(tempType, type)
return type
// After returning, the code outside will create a 'ClosedType' using the returned type and add it to the global scope.
}
Kode pada dasarnya mendapatkan jenis istilah seperti biasa, tetapi sebelum menyatukan, ia menambahkan nama fungsi yang didefinisikan dengan tipe dummy ke dalam lingkup tipe sehingga dapat digunakan dari dalam dirinya sendiri secara rekursif.
Sunting 2: Saya baru menyadari bahwa saya juga perlu tipe rekursif, yang tidak saya miliki, untuk mendefinisikan daftar seperti yang saya inginkan.
let func = \x -> (func x)
) Anda mendapatkan apa yang saya miliki.Jawaban:
Pasangan
Pengkodean ini adalah pengkodean pasangan Gereja . Teknik serupa dapat menyandikan boolean, bilangan bulat, daftar, dan struktur data lainnya.
Di bawah konteksnya→ ∨ ∧ ¬ ⟺
x:a; y:b
, istilah tersebutpair x y
memiliki tipe(a -> b -> t) -> t
. Interpretasi logis dari tipe ini adalah rumus berikut (saya menggunakan notasi matematika standar: implikasi, is atau, is dan, is negation; adalah ekivalensi formula): Mengapa " dan atau "? Secara intuitif, karena∨ ∧ ¬a
b
t
pair
adalah fungsi yang mengambil fungsi sebagai argumen dan menerapkannya pada pasangan. Ada dua cara ini bisa berjalan: fungsi argumen dapat menggunakan pasangan, atau dapat menghasilkan nilai tipet
tanpa menggunakan pasangan sama sekali.pair
adalah konstruktor untuk tipe pasangan danfirst
dansecond
merupakan destruktor. (Ini adalah kata-kata yang sama yang digunakan dalam pemrograman berorientasi objek; di sini kata-kata tersebut memiliki makna yang terkait dengan interpretasi logis dari jenis dan istilah yang tidak akan saya bahas di sini.) Secara intuitif, penghancur memungkinkan Anda mengakses apa yang ada dalam objek dan konstruktor membuka jalan bagi destruktor dengan mengambil sebagai argumen fungsi yang mereka terapkan pada bagian-bagian objek. Prinsip ini dapat diterapkan untuk tipe lain.Jumlah
Pengkodean Gereja dari persatuan yang didiskriminasi pada dasarnya adalah dua kali lipat dari pengodean pasangan oleh Gereja. Di mana pasangan memiliki dua bagian yang harus disatukan dan Anda dapat memilih untuk mengekstraksi satu atau yang lain, Anda dapat memilih untuk membangun persatuan dengan salah satu dari dua cara dan ketika Anda menggunakannya Anda harus mengizinkan kedua cara. Jadi ada dua konstruktor, dan ada destruktor tunggal yang mengambil dua argumen.
Mari saya menyingkat jenis
(a->t) -> (b->t) -> t
sebagaiSUM(a,b)(t)
. Maka jenis-jenis destruktor dan konstruktor adalah:Jadi
Daftar
Untuk daftar, terapkan kembali prinsip yang sama. Daftar yang elemennya memiliki tipe
a
dapat dibuat dengan dua cara: daftar yang kosong, atau elemen (kepala) ditambah daftar (ekor). Dibandingkan dengan pasangan, ada sedikit twist ketika datang ke destruktor: Anda tidak dapat memiliki dua destruktor terpisahhead
dantail
karena mereka hanya akan bekerja pada daftar yang tidak kosong. Anda memerlukan destruktor tunggal, dengan dua argumen, salah satunya adalah fungsi 0-argumen (yaitu nilai) untuk kasus nil, dan yang lainnya fungsi 2-argumen untuk kasus kontra. Fungsinya sukais_empty
,head
dantail
bisa diturunkan dari situ. Seperti dalam kasus penjumlahan, daftar secara langsung memiliki fungsi destruktor sendiri.cons
cons
cons
Saat Anda menduga, jika Anda ingin mendefinisikan tipe yang hanya berisi daftar homogen, Anda perlu tipe rekursif. Mengapa? Mari kita lihat tipe daftar. Daftar dikodekan sebagai fungsi yang mengambil dua argumen: nilai untuk kembali pada daftar kosong, dan fungsi untuk menghitung nilai untuk kembali pada sel kontra. Membiarkan
a
menjadi tipe elemen,b
menjadi tipe daftar, danc
menjadi tipe yang dikembalikan oleh destruktor. Jenis daftar adalahMembuat daftar menjadi homogen mengatakan bahwa jika itu adalah sel kontra, ekor harus memiliki tipe yang sama dengan keseluruhan, yaitu menambahkan batasan
Sistem tipe Hindley-Milner dapat diperluas dengan tipe rekursif seperti itu, dan pada kenyataannya bahasa pemrograman praktis melakukannya. Bahasa pemrograman praktis cenderung menolak persamaan "telanjang" dan membutuhkan konstruktor data, tetapi ini bukan persyaratan intrinsik dari teori yang mendasarinya. Membutuhkan konstruktor data menyederhanakan inferensi tipe, dan dalam praktiknya cenderung menghindari menerima fungsi yang sebenarnya bermasalah tetapi kebetulan dapat diketik dengan beberapa kendala yang tidak diinginkan yang menyebabkan kesalahan jenis yang sulit dipahami di mana fungsi tersebut digunakan. Inilah sebabnya, misalnya, OCaml hanya menerima tipe rekursif yang tidak dijaga dengan
-rectypes
opsi kompiler non-default . Berikut adalah definisi di atas dalam sintaks OCaml, bersama dengan definisi tipe untuk daftar homogen menggunakan notasi untukaliased recursive types :type_expression as 'a
berarti tipetype_expression
tersebut disatukan dengan variabel'a
.Lipatan
Melihat ini sedikit lebih umum, apa fungsi yang mewakili struktur data?
Secara umum, struktur data direpresentasikan sebagai fungsi lipatannya . Ini adalah konsep umum untuk struktur data: fungsi lipat adalah fungsi tingkat tinggi yang melintasi struktur data. Ada pengertian teknis di mana lipatan bersifat universal : semua lintasan struktur data "generik" dapat dinyatakan dalam bentuk lipatan. Bahwa struktur data dapat direpresentasikan sebagai fungsi lipatannya menunjukkan ini: yang perlu Anda ketahui tentang struktur data adalah bagaimana melewatinya, sisanya adalah detail implementasi.
sumber
t
dan mengabaikan argumen yang seharusnya diambila
danb
(yang persis apa(a and b) or t
yang dikatakan). Dan sepertinya aku memiliki masalah yang sama dengan penjumlahan. Dan juga, tanpa tipe rekursif saya tidak akan memiliki daftar yang homogen. Jadi, dalam beberapa kata, apakah Anda mengatakan saya harus menambahkan aturan jumlah, produk, dan jenis rekursif untuk mendapatkan daftar yang homogen?case (right y) f g → g y
di akhir bagian Jumlah Anda ?Anda dapat mewakili jenis penjumlahan sebagai jenis produk dengan tag dan nilai. Dalam hal ini, kita bisa menipu sedikit dan menggunakan satu tag untuk mewakili nol atau tidak, memiliki tag kedua mewakili pasangan kepala / ekor.
Kami mendefinisikan boolean dengan cara yang biasa:
Daftar kemudian merupakan pasangan dengan elemen pertama sebagai boolean, dan elemen kedua sebagai pasangan kepala / ekor. Beberapa fungsi daftar dasar:
sumber