Parametrisitas Logika Linier

Apakah kita mampu membuktikan teorema parametricity gratis tentang fungsi seperti ? Seharusnya menyatakan bahwa f mengambil daftar dan selalu mengembalikan permutasi itu.$f : \forall A . [A] ⊸ [A]$$f$

Contoh lain: membuktikan bahwa fungsi akan selalu mengembalikan daftar permutasi dengan tepat satu elemen disalin.$f : \forall A . (A ⊸ (A, A)) ⊸ [A] ⊸ [A]$

Berbagai orang tertarik untuk membuktikan hal semacam ini. Neel Krishnaswami menyebutkan teorema khusus ini di sini . Saya juga melihat Frank Pfenning memberikan beberapa contoh keren untuk logika yang dipesan. Misalnya, jika Anda memiliki , maka dalam sistem tipe yang diurutkan, e harus menambahkan daftar x dan y .$A, x : [A], y : [A] \vdash e : [A]$$e$$x$$y$

Jawaban singkatnya adalah ya, kami dapat membuktikan contoh pertama Anda. Dalam konteks kalkulus lambda, pendekatan berbasis hubungan logis dijelaskan dalam makalah ini . Mereka akan membuktikan teorema Anda dalam dua langkah:

1. Tentukan interpretasi relasional dari jenis dan gunakan untuk membuktikan teorema bebas konvensional sepenuhnya mengabaikan linearitas yaitu pada dasarnya menggunakan alasan yang sama yang Anda lihat, misalnya, "Teorema Gratis!". Mengingat , teorema bebas yang biasa memberi tahu kita bahwa f mengembalikan daftar yang hanya berisi elemen yang ada dalam daftar yang diberikan. Mengingat daftar yang berbeda variabel linear bebas x 1 ... x n , kami menyimpulkan bahwa f [ x 1 , . . . $\vdash f : \forall A . [A] \multimap [A]$$f$$x_1 \ldots x_n$ mengevaluasi ke beberapa daftar [ y 1 , . . . , Y m ] di mana { y 1 , ... , y m } ⊆ { x 1 , . . . , x n } .$f [x_1, ..., x_n]$$[y_1, ..., y_m]$$\{y_1, \ldots, y_m\} \subseteq \{x_1, ..., x_n\}$
2. Perhatikan bahwa variabel linier bebas harus dipertahankan dalam evaluasi. Ini memungkinkan kita mengambil keuntungan dari linearitas. Jika tidak permutasi dari [ x 1 , . . . , x n ] , maka itu akan menyiratkan bahwa beberapa x i hilang atau diduplikasi selama evaluasi, yang tidak dapat terjadi.$[y_1, \ldots, y_m]$$[x_1, ..., x_n]$$x_i$

Tetapi, teorema semacam ini menjadi lebih menarik ketika kita melihat bahasa dengan efek dan kemampuan kita untuk membuktikannya untuk bahasa-bahasa seperti itu sangat terbatas. Sebagai contoh, perhatikan isomorfisma dari Sistem F. Dalam pengaturan nilai-panggilan, isomorfisma ini terputus ketika kita menambahkan non-terminasi. Kami harus bisa memulihkan isomorfisma yang sama, meskipun, dengan jenis linear: τ ≅ ∀ A . ( Τ → A ) ⊸ A . Sayangnya, kami tidak memiliki hubungan logis operasional yang dapat membuktikan ini.$\tau \cong \forall A . (\tau \to A) \to A$$\tau \cong \forall A . (\tau \to A) \multimap A$

Yang mengatakan, ada juga metode sintaksis yang dapat membuktikan isomorfisme dan teorema Anda. Ini tampaknya menjadi pendekatan yang sangat berguna dalam pengaturan linier, dan jauh lebih sedikit dari beban daripada mengatur hubungan logis untuk membuktikan teorema sederhana.

Edit: Karena Anda bertanya, inilah contoh dari bukti sintaksis dari teorema bebas untuk jenis dalam pengaturan dengan istilah ⊥ yang berulang selamanya dan diketik dengan baik dalam konteks apa pun pada jenis apa pun. Idenya adalah untuk menemukan seperangkat istilah kanonik dari suatu jenis dan menggunakannya untuk menentukan apa nilai pengembalian yang mungkin untuk suatu fungsi. Kita mulai dengan teorema kesehatan untuk istilah yang diketik dengan baik.$\forall A . (A \otimes A) \multimap A$$\bot$

$\Delta; \Gamma \vdash e : \tau$

• $e \approx v$$\Delta; \Gamma \vdash v : \tau$
• $e \approx n$$\Gamma$$\Delta; \Gamma \vdash n : \tau$
• $e \approx \bot$

$\approx$$\Delta$$x$

$\vdash f : \forall A . (A \otimes A) \multimap A$$f \approx \lambda x . e$$A; x : (A \otimes A) \vdash e : A$

• $e$$A; x : (A \otimes A) \vdash (v_1, v_2) : A$$v_1$$v_2$$A$$A$
• $e$$x$
• $e$$f$$\lambda x . \bot$

$e \approx\ \mathrm{let} (x_1, x_2) = x\ \mathrm{in}\ e’$$A; x_1 : A, x_2 : A \vdash e’ : A$$f \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ e’$$e’$$A$$e’ \approx x_i$

$\forall A . (A \otimes A) \multimap A$$\lambda x . \bot \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ \bot$

Anda meminta referensi untuk bukti semacam ini, tapi saya tidak yakin dengan yang baik. Jenis pemikiran ini terkenal di kalangan tertentu dan mungkin kembali sejauh Gentzen. Saya diberitahu bahwa ini mengingatkan pada pencarian bukti terfokus untuk kalkulus sekuensial, tetapi saya tidak tahu persis apa hubungannya.

Yang mengatakan, saya tidak mengetahui adanya karya modern yang diterbitkan yang menjelaskan metode yang relatif sederhana ini dengan baik. Memang, ini agak terbatas dalam penerapannya ke bahasa yang lebih sederhana. Di sisi lain, saya pikir itu telah dibayangi oleh "Teorema Gratis!" et al dan sebagai akibatnya bahkan banyak peneliti senior segera memikirkan hubungan logis ketika mereka mendengar ungkapan "teorema bebas", tidak menyadari bahwa teknik seperti ini dapat menjadi pendekatan alternatif yang lebih sederhana untuk bukti semacam itu (terutama dalam konteks sistem tipe linear).

$A$$f$$\forall A. (\forall B. B \multimap (B, B)) \multimap [A] \multimap [A]$$\forall B. B \multimap (B, B)$ ada karena harus menduplikasi inputnya.