Karakterisasi istilah lambda yang memiliki tipe serikat pekerja

29

Banyak buku teks membahas jenis persimpangan di kalkulus lambda. Aturan mengetik untuk persimpangan dapat didefinisikan sebagai berikut (di atas kalkulus lambda hanya diketik dengan subtyping):

ΓM:T1ΓM:T2ΓM:T1T2(I)ΓM:(I)

Jenis titik-temu memiliki sifat yang menarik sehubungan dengan normalisasi:

  • Sebuah istilah lambda dapat diketik tanpa menggunakan aturan iff itu sangat normal.I
  • Istilah lambda mengakui tipe yang tidak mengandung jika memiliki bentuk normal.

Bagaimana jika alih-alih menambahkan persimpangan, kami menambahkan serikat?

ΓM:T1ΓM:T1T2(I1)ΓM:T2ΓM:T1T2(I2)

Apakah lambda-calculus dengan tipe sederhana, subtyping, dan serikat memiliki properti serupa yang menarik? Bagaimana istilah yang dapat diketik dengan serikat ditandai?

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Pertanyaan menarik. Bisakah Anda mengatakan bahwa antarmuka dari OOP sesuai dengan ini?
Raphael
Mungkin Anda bisa tertarik dengan cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…
Fabio F.

Jawaban:

11

Dalam sistem pertama yang Anda sebut subtyping adalah dua aturan ini:

Γ,x:T1M:SΓ,x:T1T2M:S(E1)Γ,x:T2M:SΓ,x:T1T2M:S(E2)

Mereka sesuai dengan aturan eliminasi untuk ; tanpa mereka more kurang lebih berguna.

Dalam sistem kedua (dengan penghubung dan , yang juga bisa kita tambahkan ), aturan subtyping di atas tidak relevan, dan saya pikir aturan terlampir yang Anda pikirkan adalah sebagai berikut:

Γ,x:T1M:SΓ,x:T2M:SΓ,x:T1T2M:S(E)Γ,x:M:S(E)

Untuk apa nilainya, sistem ini memungkinkan untuk mengetik (menggunakan aturan ), yang tidak dapat diketik hanya dengan tipe sederhana, yang memiliki bentuk normal, tetapi tidak sangat normal. . E(λx.I)Ω:AAE


Pikiran acak: (mungkin ini patut ditanyakan di TCS)

Ini membuat saya menduga bahwa properti terkait adalah seperti:

  • a λ-term mengakui tipe yang tidak mengandung iff memiliki bentuk normal untuk semua yang memiliki bentuk normal. ( gagal kedua tes, tetapi istilah λ di atas lulus)M N N δMMNNδ
  • istilah λ dapat diketik tanpa menggunakan aturan jika sangat normal untuk semua sangat normal . E M N NMEMNN

Latihan: buktikan kalau saya salah.

Juga sepertinya kasus yang merosot, mungkin kita harus mempertimbangkan untuk menambahkan orang ini ke dalam gambar. Sejauh yang saya ingat, itu akan memungkinkan untuk mendapatkan ?A(A)

Stéphane Gimenez
sumber
Poin bagus tentang aturan subtyping, mereka menunjukkan bahwa jenis serikat hampir tidak sealami persimpangan (yang diketik secara orthogonal ke panah). Tentang bagian kedua saya perlu memikirkan lagi.
Gilles 'SO- stop being evil'
Saya pikir menjawab latihan, jika Anda berbicara tentang jenis-jenis serikat. M=(λx.xx)(λy.y)
jmad
Tentang panggilan / cc: ini membutuhkan lebih dari sekadar istilah-istilah lambda (seperti istilah-istilah lambda-mu atau kerangka kerja lain) tetapi sistem tipe lebih kompleks, sistem logika, di mana tipe-tipe serikat pekerja mungkin tidak relevan.
jmad
@jmad: Memang, jenis persimpangan diperlukan untuk mengetik istilah ini :-( Mungkin mempertimbangkan serikat dan persimpangan bersama-sama akan menarik?
Stéphane Gimenez
Saya akan tertarik dengan istilah λ yang dapat diketik dengan tipe gabungan (rs. Dengan tipe persimpangan) tetapi tidak dengan tipe sederhana (rs. Dengan tipe persimpangan).
jmad
16

Saya hanya ingin menjelaskan mengapa tipe persimpangan cocok untuk mengkarakterisasi kelas normalisasi (kuat, head atau lemah), sedangkan sistem tipe lainnya tidak bisa. (cukup diketik atau sistem F).

Perbedaan utama adalah bahwa Anda harus mengatakan: "jika saya bisa mengetik dan maka saya bisa mengetik ". Ini sering tidak benar dalam jenis non-persimpangan karena istilah dapat diduplikasi:M 1M 2 M 1M2M1M2M1

(λx.Mxx)NMNN

dan kemudian mengetik berarti bahwa Anda dapat mengetik kedua kejadian tetapi tidak dengan jenis yang sama, misalnya Dengan jenis persimpangan Anda dapat mengubah ini menjadi: dan kemudian langkah penting sekarang sangat mudah: so dapat dengan mengetikkan tipe persimpangan.N M : T 1T 2T 3MNNN

M:T1T2T3N:T1N:T2
M:T1T2T1T2T3N:T1T2
(λx.Mxx):T1T2T3N:T1T2
(λx.Mxx)N

Sekarang tentang jenis penyatuan: misalkan Anda dapat mengetik dengan beberapa jenis penyatuan, maka Anda juga dapat mengetik dan kemudian mendapatkan untuk beberapa jenis Tetapi Anda masih harus membuktikan bahwa untuk setiap , yang tampaknya mustahil bahkan adalah tipe gabungan.λ x . x x S , T 1 , ... x : T 1T 2T nx x : S i x : T ix x : S S(λx.xx)(λy.y)λx.xxS,T1,

x:T1T2Tnxx:S
ix:Tixx:SS

Inilah mengapa saya tidak berpikir ada karakterisasi yang mudah tentang normalisasi untuk jenis serikat.

jmad
sumber