Struktur data dalam bahasa pemrograman dengan tipe linear

Anggaplah kita berhadapan dengan bahasa pemrograman yang memiliki dukungan untuk tipe linier (istilah tipe linier dapat digunakan paling banyak sekali, jadi bisa dikatakan). Hal ini memungkinkan untuk menangani beberapa efek komputasi (seperti mutasi, bahkan mengubah jenis operan) dengan cara yang bermasalah untuk bahasa, jenis sistem yang beroperasi hanya pada "kebenaran abadi".

Banyak struktur data dapat dicirikan dengan tipe induktif (daftar dan pohon adalah contoh kanonik). Jika kita menambahkan tipe induktif linier ke dalam campuran, kita juga bisa menangani struktur data yang bisa berubah.

Namun, tidak jelas bagi saya bagaimana merepresentasikan struktur data yang dipamerkan berbagi dan referensi siklik dalam bahasa pemrograman dengan tipe linier (contoh struktur data tersebut adalah DAG dan grafik lainnya, diwakili oleh daftar adjacency atau yang lainnya, daftar cyclic). Bisakah kita melakukan itu? Jika tidak memungkinkan, dengan cara apa kita harus memperluas bahasa untuk mengakomodasi struktur data seperti itu?

Contoh paling terlibat yang saya temukan sejauh ini adalah daftar yang ditautkan dua kali lipat. Apakah ada contoh lain?

pl.programming-languages type-theory linear-logic Bjørn Kjos-Hanssen
sumber

Linearitas bukan kendala yang cukup untuk menjabarkan representasi stateful yang unik, dan jawaban untuk pertanyaan Anda tergantung pada bagaimana Anda menafsirkan logika linier dalam hal negara. Ini biasanya akan tercermin dalam bagaimana Anda harus menafsirkan $!A$ modalitas.

Jika semantik referensi yang Anda maksudkan mengatakan bahwa semua pointer adalah nilai unik (yaitu, paling banyak ada satu referensi ke suatu objek) maka dags dan struktur grafik tidak dapat diekspresikan, untuk jenis alasan tautologis bahwa dag dapat berisi banyak referensi ke objek yang sama. Dalam hal ini, harus menjadi perhitungan yang menciptakan nilai baru tipe , karena Anda ingin peta dan $!A$ $A$ $\delta_A : !A \multimap !A \otimes !A$ $\epsilon_A : !A \multimap A$ .

Namun, anggaplah Anda menginginkannya untuk mewakili berbagi . Kemudian, objek dapat dikumpulkan dengan penghitungan referensi, dengan peta $!A$ dan dapat direalisasikan sebagai operasi yang hanya meningkatkan jumlah referensi. Dalam hal ini, Anda tidak dapat menggunakan linearitas untuk menganggap bahwa selalu aman untuk mengubah nilai, karena ada pembagian. Tetapi Anda dapat memastikan bahwa semua alokasi memori eksplisit dalam program Anda, dan bahwa tidak ada siklus di heap. $\delta_A : !A \multimap !A \otimes !A$ $\epsilon_A : !A \multimap A$

Kebanyakan implementasi praktis dari tipe linear tidak menggunakan kedua interpretasi ini. Sebaliknya, referensi dipandang sebagai entitas yang dapat digandakan secara bebas, dan apa yang kami lacak secara linear sebenarnya adalah kemampuan . Kemampuan bukan nilai runtime; mereka murni entitas konseptual yang dimaksudkan untuk mewakili izin untuk mengakses referensi. Idenya adalah bahwa Anda memprogram dengan gaya izin-lewat, dan bahkan jika ada banyak referensi ke objek yang sama, pembacaan atau modifikasi sepotong negara hanya dapat terjadi jika Anda juga memiliki kemampuan untuk mengaksesnya. Dan karena kemampuannya linier, Anda tahu bahwa hanya Anda yang dapat mengubahnya.

\begin{matrix} n e w & : & \forall α . α ⊸ \exists c : ι . c a p (c) \otimes r e f (α, c) \\ g e t & : & \forall α, c : ι . c a p (c) \otimes r e f (α, c) ⊸ α \otimes c a p (c) \otimes r e f (α, c) \\ s e t & : & \forall α, c : ι . c a p (c) \otimes r e f (α, c) \otimes α ⊸ c a p (c) \otimes r e f (α, c) \\ c o p y & : & \forall α, c : ι . r e f (α, c) ⊸ r e f (α, c) \otimes r e f (α, c) \end{matrix}

$\array{ \mathsf{new} & : & \forall \alpha. \;\alpha \multimap \exists c : \iota. \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{get} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \multimap \alpha \otimes \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{set} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \otimes \alpha \multimap \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\ \mathsf{copy} & : & \forall \alpha, c:\iota.\; \mathsf{ref}(\alpha,c) \multimap \mathsf{ref}(\alpha,c) \otimes \mathsf{ref}(\alpha,c) }$

$c$ $\iota$ $\alpha$ $\mathsf{cap}(c)$ $c$ $\mathsf{ref}(\alpha, c)$ $\alpha$ $c$ $\mathsf{get}$ $\mathsf{set}$ $c$ $\mathsf{new}$ $\mathsf{copy}$

Neel Krishnaswami
sumber

Terima kasih atas jawaban yang menggugah pikiran. Saya tertarik, apakah ada perbedaan (teknis) antara aliasing dan berbagi? Apakah ada sistem yang secara bertahap dapat berubah dari linear (paling banyak satu referensi) ke dibagikan oleh paling banyak n referensi untuk dibagikan dengan cara yang tidak dibatasi?

1. Mengasingkan dan berbagi adalah sinonim. 2. Ya, interpretasi gaya-kemampuan, ditambah dengan izin fraksional Boyland mengizinkan ini. Lihat juga karya terbaru Pottier tentang kalkulus kemampuan untuk teori, dan karya Aldrich dan Bierhof tentang Plural untuk implementasi.

Neel Krishnaswami

Struktur data dalam bahasa pemrograman dengan tipe linear

Jawaban: