Ketik inferensi untuk pernyataan imperatif selain penugasan

Dalam pencarian saya untuk makalah penelitian tentang sistem tipe untuk bahasa imperatif, saya hanya menemukan solusi untuk bahasa dengan referensi yang bisa berubah tetapi tanpa struktur kontrol imperatif asli seperti operator majemuk, loop atau kondisional.

Jadi tidak jelas bagaimana bahasa imperatif dengan inferensi tipe parsial seperti http://rust-lang.org dapat diimplementasikan.

Makalah tidak menyebutkan jenis parametrized seperti List of akarena jenis parametrized adalah perpanjangan sepele dari sistem tipe Hindley-Milner - hanya algoritma unifikasi yang harus diperluas, dan sisa inferensi bekerja seperti apa adanya. Namun, tugas tidak dapat ditambahkan secara sepele karena timbul paradoks, sehingga teknik khusus seperti pembatasan nilai ML harus diterapkan.

Bisakah Anda merekomendasikan makalah atau buku apa pun yang menggambarkan sistem jenis untuk bahasa dengan loop imperatif, kondisional, IO dan pernyataan majemuk?

Jika Anda mencari referensi fungsional yang rapi untuk inferensi-tipe, saya sedikit mendukung Gundry, McBride, dan McKinna 2010 " Type Inference in Context ", meskipun ini mungkin bukan panduan yang baik untuk implementasi aktual apa pun yang ada .

Saya pikir bagian dari jawabannya adalah bahwa, di luar batasan nilai, sebenarnya tidak ada banyak kesulitan mengadaptasi inferensi tipe Hindley-Milner ke bahasa imperatif: jika Anda mendefinisikan e1; e2sebagai gula sintaksis (fn _ => e2) e1dan didefinisikan while e1 do e2sebagai gula sintaksis untuk whiledo e1 (fn () => e2), di mana whiledobiasa fungsi rekursif

fun whiledo g f = if g then (f (); whiledo g f) else ();

maka semuanya akan berfungsi dengan baik, termasuk inferensi tipe.

Adapun pembatasan nilai menjadi teknik khusus, saya suka cerita berikut; Saya cukup yakin saya mengambilnya dari Karl Crary. Pertimbangkan kode berikut, di mana batasan nilai akan mencegah Anda menulis dalam ML:

let
   val x: 'a option ref = ref NONE
in
   (x := SOME 5; x := SOME "Hello")  
end

Bandingkan dengan kode berikut, yang sama sekali tidak bermasalah:

let
   val x: unit -> 'a option ref = fn () => ref NONE
in
   (x () := SOME 5; x () := SOME "Hello")  
end

Kita tahu apa yang dilakukan contoh kedua: ia membuat dua sel ref baru yang mengandung NONE, kemudian menempatkan SOME 5yang pertama (an int option ref), kemudian menempatkan SOME "Hello"yang kedua (a string option ref).

xx$\forall \alpha. \mbox{ref}(\mbox{option}(\alpha))$x$\Lambda \alpha. \mbox{ref}[\alpha](\mbox{NONE})$

Ini menunjukkan bahwa satu perilaku "baik" dari contoh pertama adalah berperilaku dengan cara yang persis sama dengan contoh kedua berperilaku - instantiate tipe-level lambda dua kali berbeda. Pertama kalinya kami instantiate xdengan int, yang akan menyebabkan x [int]mengevaluasi ke sel tahanan referensi NONEdan kemudian SOME 5. Kedua kalinya kami instantiate xdengan string, yang akan kasus x [string]untuk mengevaluasi ke ( berbeda! Holding) sel referensi NONEdan kemudian SOME "Hello". Perilaku ini "benar" (tipe-aman), tetapi jelas bukan yang diharapkan oleh seorang programmer, dan inilah mengapa kami memiliki batasan nilai dalam ML, untuk menghindari programmer berurusan dengan jenis perilaku yang tidak terduga ini.

Tesis PhD Xavier Leroy adalah awal yang baik.

Saya minta maaf untuk necroanswering pertanyaan saya sendiri, tetapi referensi yang dimaksud adalah

Proposal untuk ML Standar , Milner, 1983

Bagian 6 "Formulir Berasal Standar" mencakup keinginan untuk konstruksi imperatif yang cukup luas. Dan sejauh ini itu adalah referensi paling awal dari transformasi yang sangat jelas ini yang bisa saya temukan.