Mengapa suatu fungsi dengan tipe polymorphic `forall t: Type, t-> t` menjadi fungsi identitas?

Saya baru mengenal teori bahasa pemrograman. Saya menonton beberapa kuliah online di mana instruktur mengklaim bahwa fungsi dengan tipe polimorfik forall t: Type, t->tmenjadi identitas, tetapi tidak menjelaskan mengapa. Adakah yang bisa menjelaskan kepada saya mengapa? Mungkin bukti klaim dari prinsip pertama.

Hal pertama yang perlu diperhatikan adalah bahwa ini tidak selalu benar. Sebagai contoh, tergantung pada bahasa fungsi dengan tipe itu, selain menjadi fungsi identitas, dapat: 1) loop selamanya, 2) bermutasi beberapa negara, 3) kembali null, 4) melempar pengecualian, 5) melakukan beberapa I / O, 6) garpu utas untuk melakukan sesuatu yang lain, 7) lakukancall/cc shenanigans, 8) menggunakan sesuatu seperti Java Object.hashCode, 9) menggunakan refleksi untuk menentukan apakah jenisnya bilangan bulat dan menambahkannya jika demikian, 10) menggunakan refleksi untuk menganalisis tumpukan panggilan dan melakukan sesuatu berdasarkan konteks di mana ia disebut, 11) mungkin banyak hal lain dan tentu saja kombinasi sewenang-wenang di atas.

Jadi properti yang mengarah ke ini, parametrik, adalah properti dari bahasa secara keseluruhan dan ada variasi yang lebih kuat dan lebih lemah. Bagi banyak kalkulus formal yang dipelajari dalam teori jenis, tidak ada perilaku di atas yang dapat terjadi. Misalnya, untuk Sistem F / kalkulus lambda polimorfik murni, di mana parametrikitas pertama kali dipelajari, tidak ada perilaku di atas yang dapat terjadi. Ini sama sekali tidak memiliki pengecualian, keadaan bisa berubah null,,call/cc , I / O, refleksi, dan itu sangat normalisasi sehingga tidak dapat loop selamanya. Seperti yang disebutkan Gilles dalam komentar, makalah Teorema gratis!oleh Phil Wadler adalah pengantar yang baik untuk topik ini dan rujukannya akan melangkah lebih jauh ke dalam teori, khususnya teknik hubungan logis. Tautan itu juga mencantumkan beberapa makalah lain oleh Wadler tentang topik parametrik.

Karena parametrisitas adalah sifat bahasa, untuk membuktikannya diperlukan terlebih dahulu mengartikulasikan bahasa dan kemudian argumen yang relatif rumit. Argumen informal untuk kasus khusus ini dengan asumsi kita berada dalam kalkulus lambda polimorfik adalah bahwa karena kita tidak tahu apa-apa tentang tkita tidak dapat melakukan operasi pada input (misalnya kita tidak bisa menambahnya karena kita tidak tahu apakah itu angka) atau buat nilai dari tipe itu (untuk semua yang kita tahu t= Void, tipe tanpa nilai sama sekali). Satu-satunya cara untuk menghasilkan nilai tipe tadalah dengan mengembalikan nilai yang diberikan kepada kami. Tidak ada perilaku lain yang mungkin. Salah satu cara untuk melihatnya adalah dengan menggunakan normalisasi yang kuat dan menunjukkan bahwa hanya ada satu bentuk istilah normal dari tipe ini.

Buktinya, klaimnya cukup rumit, tetapi jika itu yang Anda inginkan, Anda bisa membaca makalah asli Reynolds tentang topik itu.

Gagasan utamanya adalah bahwa ia berlaku untuk fungsi-fungsi polimorfik parametrik , di mana tubuh fungsi polimorfiknya sama untuk semua instantiasi monomorfik dari fungsi tersebut. Dalam sistem seperti itu, tidak ada asumsi yang dapat dibuat tentang jenis parameter tipe polimorfik, dan jika satu-satunya nilai dalam lingkup memiliki tipe generik, tidak ada hubungannya dengan mengembalikannya, atau mengembalikannya ke fungsi lain. telah didefinisikan, yang pada gilirannya tidak dapat melakukan apa-apa selain mengembalikannya atau meneruskannya ... dll Jadi pada akhirnya, yang dapat Anda lakukan adalah beberapa rantai fungsi identitas sebelum mengembalikan parameter.

Dengan semua peringatan yang disebutkan Derek, dan mengabaikan paradoks yang dihasilkan dari menggunakan teori himpunan, izinkan saya membuat sketsa bukti dalam semangat Reynolds / Wadler.

Fungsi dari tipe:

f :: forall t . t -> t

adalah keluarga dari fungsi diindeks oleh jenis t .$f_t$$t$

Idenya adalah bahwa, untuk secara formal mendefinisikan fungsi-fungsi polimorfik, kita tidak seharusnya memperlakukan tipe sebagai set nilai, melainkan sebagai hubungan. Tipe dasar, seperti Intmenginduksi hubungan kesetaraan - misalnya, dua Intnilai terkait jika mereka sama. Fungsi terkait jika mereka memetakan nilai terkait ke nilai terkait. Kasus yang menarik adalah fungsi polimorfik. Mereka memetakan tipe terkait dengan nilai terkait.

Dalam kasus kami, kami ingin membangun hubungan antara dua fungsi polimorfik dan g dari tipe:$f$$g$

forall t . t -> t

$s$$t$$f$$s$$f_s$$s \to s$$t$$g_t$$t \to t$$f$$g$$f_s$$g_t$

fst$f_s$$f_t$

()()t()t((), c)ct$f_{(\,)}$$f_t$$f_{(\,)}$()()$f_t$cc()c$f_t$$id_t$tfid

Anda dapat menemukan lebih banyak detail di blog saya .

EDIT: Komentar di atas telah memberikan bagian yang hilang. Beberapa orang sengaja bermain dengan bahasa yang kurang lengkap. Secara eksplisit saya tidak peduli dengan bahasa seperti itu. Bahasa tidak lengkap yang benar-benar dapat digunakan adalah hal sulit yang gila untuk desain. Seluruh sisanya memperluas apa yang terjadi mencoba menerapkan teorema ini ke bahasa penuh.

Salah!

function f(a): forall t: Type, t->t
    function g(a): forall t: Type, t->t
       return (a is g) ? f : a
    return a is f ? g : a

di mana isoperator membandingkan dua variabel untuk identitas referensi. Artinya, mereka mengandung nilai yang sama. Bukan nilai yang setara, nilai yang sama. Fungsinya fdan gsetara dengan beberapa definisi tetapi tidak sama.

Jika fungsi ini dilewatkan dengan sendirinya ia mengembalikan sesuatu yang lain; jika tidak mengembalikan inputnya. Sesuatu yang lain memiliki tipe yang sama seperti itu sendiri sehingga dapat diganti. Dengan kata lain, fbukan identitas, karena f(f)kembali g, sedangkan identitas akan kembali f.

Untuk memegang teorema itu harus mengasumsikan kemampuan konyol untuk mengurangi

function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(1000, <0, a>)[1]¹

Jika Anda mau berasumsi bahwa Anda dapat mengasumsikan inferensi tipe yang jauh lebih mudah dapat ditangani.

Jika kita mencoba untuk membatasi domain sampai teorema tersebut berlaku, kita akhirnya harus membatasi domain tersebut terlalu jauh.

• Fungsional Murni (tidak ada keadaan bisa berubah, tidak ada IO). OK saya bisa hidup dengan itu. Banyak waktu kami ingin menjalankan bukti atas fungsi.
• Perpustakaan standar kosong. meh.
• Tidak raisedan tidak exit. Sekarang kita mulai dibatasi.
• Tidak ada tipe bawah.
• Bahasa memiliki aturan yang memungkinkan kompiler untuk menutup rekursi tak terbatas dengan menganggapnya harus diakhiri. Kompiler diizinkan untuk menolak rekursi tak terbatas sepele.
• Kompiler dibiarkan gagal jika disajikan dengan sesuatu yang tidak dapat dibuktikan dengan baik.² Sekarang perpustakaan standar tidak dapat mengambil fungsi sebagai argumen. Boo.
• Tidak ada nil. Ini mulai bermasalah. Kami sudah kehabisan cara untuk menangani 1 / 0.³
• Bahasa tidak dapat melakukan inferensi tipe cabang dan tidak memiliki penggantian ketika programmer dapat membuktikan inferensi tipe yang tidak dapat dilakukan oleh bahasa. Ini sangat buruk.

Keberadaan kedua kendala terakhir telah melumpuhkan bahasa. Meskipun Turing masih lengkap, satu-satunya cara untuk menyelesaikannya adalah dengan mensimulasikan platform internal yang menafsirkan bahasa dengan persyaratan yang lebih longgar.

¹ Jika menurut Anda kompilator dapat menyimpulkan yang itu, coba yang ini

function fermat(z) : int -> int
    function pow(x, p)
        return p = 0 ? 1 : x * pow(x, p - 1)
    function f2(x, y, z) : int, int, int -> <int, int>
        left = pow(x, 5) + pow(y, 5)
        right = pow(z, 5)
        return left = right
            ? <x, y>
            : pow(x, 5) < right
                ? f2(x + 1, y, z)
                : pow(y, 5) < right
                    ? f2(2, y + 1, z)
                    : f2(2, 2, z + 1)
    return f2(2, 2, z)
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(fermat(3)[0], <0, a>)[1]

² Bukti bahwa kompiler tidak dapat melakukan ini tergantung pada penyamaran. Kita dapat menggunakan beberapa pustaka untuk memastikan kompiler tidak dapat melihat loop sekaligus. Juga, kita selalu dapat membangun sesuatu di mana program akan bekerja tetapi tidak dapat dikompilasi karena kompiler tidak dapat melakukan induksi dalam memori yang tersedia.

³ Seseorang mengira Anda dapat memiliki pengembalian nihil ini tanpa jenis generik sewenang-wenang yang mengembalikan nihil. Ini membayar penalti yang buruk karena saya tidak melihat bahasa yang efektif yang dapat membayarnya.

function f(a, b, c): t: Type: t[],int,int->t
    return a[b/c]

tidak boleh dikompilasi. Masalah mendasar adalah pengindeksan array runtime tidak berfungsi lagi.