Inferensi Tipe Berbasis Kendala dengan Data Aljabar

Saya sedang mengerjakan bahasa berbasis ekspresi dari silsilah ML, jadi tentu saja perlu inferensi jenis> :)

Sekarang, saya mencoba untuk memperluas solusi berbasis kendala untuk masalah tipe menyimpulkan, berdasarkan pada implementasi sederhana dalam EOPL (Friedman dan Wand), tetapi mereka secara elegan memihak tipe data aljabar.

Apa yang saya miliki sejauh ini bekerja dengan lancar; jika ekspresi eadalah a + b, e : Int, a : Intdan b : Int. Jika ecocok,

match n with
  | 0 -> 1
  | n' -> n' * fac(n - 1)`,

Saya benar dapat menyimpulkan bahwa t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)dan seterusnya ...

Tapi saya sangat tidak yakin ketika datang ke tipe data aljabar. Misalkan fungsi seperti filter:

let filter pred list =
  match list with
    | Empty -> Empty
    | Cons(e, ls') when pred e -> Cons (e, filter ls')
    | Cons(_, ls') -> filter

Agar tipe daftar tetap polimorfik, Kontra harus bertipe a * a list -> a list. Jadi, dalam menetapkan batasan-batasan ini, saya jelas perlu mencari jenis-jenis konstruktor aljabar saya ini - masalah yang saya miliki sekarang adalah 'sensitivitas konteks' dari banyak penggunaan konstruktor aljabar - bagaimana saya mengekspresikan dalam persamaan kendala saya bahwa adalam setiap kasus harus sama?

Saya mengalami kesulitan menemukan solusi umum untuk ini, dan saya tidak dapat menemukan banyak literatur tentang ini. Setiap kali saya menemukan sesuatu yang serupa - bahasa berbasis ekspresi dengan inferensi tipe berbasis kendala - mereka berhenti hanya pada tipe data aljabar dan polimorfisme.

Masukan apa pun sangat dihargai!

programming-languages type-theory functional-programming inductive-datatypes typing Keris
sumber

@ Beli Saya tidak bermaksud kedengaran tidak berterima kasih, tapi saya tidak mencari solusi yang siap pakai - apakah Anda punya saran? Kebanyakan dokumen yang ada dapat saya temukan (seperti makalah INRIA di ML, OCaml ...) jauh lebih luas daripada yang saya butuhkan (dan saya mampu memahami).

Kris

Saya akan mulai dengan bab inferensi di ATTAPL , saya pikir mereka membahas semua yang Anda butuhkan pada tingkat yang dapat diakses.

Gilles 'SO- stop being evil'

@Gilles Saya pikir ATTAPL adalah satu-satunya buku PL 'klasik' yang tidak saya miliki di rak buku saya: P Tapi terima kasih, saya akan melihat pada hari Senin, saya duduk di lantai di Uni dengan mungkin 10 salinan didistribusikan di kantor: )

Kris

@ Kris apakah Anda pernah menemukan sumber daya yang dapat diakses untuk mengatasi masalah ini? Implementasi saya "mini ML" terjebak pada masalah ini ... Saya rasa saya menemukan bab yang relevan dari ATTAPL ( pauillac.inria.fr/ ~ fpottier/ publis / emlti-final.pdf ) dan membaca bagian aljabar tipe data, tapi saya khawatir ini sedikit berlebihan.

michiakig

@spacemanaki Ya, saya telah menemukan pdfs.semanticscholar.org/8983/... sebagai sumber yang bagus untuk hal ini.

Kris

Inferensi Tipe Berbasis Kendala dengan Data Aljabar

Jawaban: