Apa model rakyat dari logika linier?

Mungkin aplikasi yang paling umum dari tipe linear dalam PL adalah menggunakannya untuk memberikan bahasa yang mengontrol aliasing (yaitu, nilai linier memiliki satu pointer ke sana, lebih atau kurang).

Tetapi ada sedikit ketidakcocokan antara penggunaan ini dan model denotasional khas dari logika linier. IIRC, Benton menunjukkan bahwa jika kategori tertutup Cartesian memiliki monad komutatif yang kuat , maka kategori aljabarnya akan tertutup simetris monoid (yaitu, model logika linier). Tetapi teorema ini tidak berlaku untuk penggunaan alias-control, karena state monad tidak komutatif. Dan memang, dalam beberapa tahun terakhir Simpson dan rekan-rekan kerjanya telah memberikan batu untuk monad kuat secara umum, yang bukan batu untuk istilah logika linier.

Jadi pertanyaan saya adalah, apakah semantik denotasional dari bahasa linear dengan negara? Apakah ada kategori simetris monoidal tertutup non-degenerasi (tensor bukan produk Cartesian) di mana alokasi, pembacaan, dan pembaruan linier dapat dimodelkan?

pl.programming-languages ct.category-theory imperative-programming denotational-semantics linear-logic Neel Krishnaswami
sumber

Ini adalah pertanyaan yang saya harapkan dari Anda untuk menjawab Neel, bukan bertanya. ;-)

Marc Hamann 8-10

jika Anda dapat menarik peneliti ke cstheory.stackoverflow.com yang mampu menjawab pertanyaan ini, maka dunia akan menjadi tempat yang lebih baik untuk itu.

Dave Clarke

Jawaban:

Tampak bagi saya bahwa arah Anda harus mempertimbangkan mencari di sekitar permainan semantik untuk referensi umum dan semantik terkait untuk logika linier, seperti yang didasarkan pada permainan Conway . Akun aljabar referensi dalam semantik game oleh Paul-André Melliès dan Nicolas Tabareau mungkin adalah tempat terbaik untuk memulai. Dalam makalah ini, logika linier disesuaikan dengan apa yang disebut logika tensor untuk menyelesaikan pekerjaan, jadi ini bukan pengaturan yang Anda inginkan. Tetapi mereka memang mengandalkan permainan Conway, jadi tentu saja ada koneksi dengan model logika linier. Mereka juga tidak benar-benar mengeksploitasi linearitas seperti pada tipe linier, tetapi ada mesin untuk melakukannya jika Anda mau, saya percaya.

Karya Jim Laird (seperti A Game Semantics of Names and Pointers ) dan Guy McCusker juga dapat berkontribusi untuk pencarian Anda. Semantik Game tesis menarik baru-baru ini untuk bahasa berorientasi objek oleh Nicholas Wolverson mendorong ide-ide ini lebih jauh dalam pengaturan OO. Dia mempertimbangkan dalam linear threading , hanya satu operasi yang aktif pada suatu waktu, dan menjelaskan cara menambahkan kelas linear . Keduanya mengandalkan pengetikan linear. Namun, sekali lagi, model yang mendasarinya bukan semata-mata model logika linier, tetapi dekat.

Dave Clarke
sumber

Hanya ingin tahu Neel. Apakah ini ada gunanya bagi Anda, atau apakah Anda sudah tahu tentang semua hal ini?

Dave Clarke

Saya tahu hal ini (tapi tidak baik), tetapi permainan semantik jauh lebih canggih daripada yang saya cari. Kebanyakan orang memiliki intuisi untuk keadaan linier yang tidak jauh dari pandangan Strachey kuno tentang perhitungan imperatif sebagai elemen tipe monadik

, dan saya berharap ada model keadaan linear yang akan menyerupai itu. Pada dasarnya, saya berharap ada sesuatu yang bisa Anda perlihatkan kepada mahasiswa tahun pertama tanpa membuat mereka takut. :)

T (A) = S \to A \times S

$T(A) = S \to A \times S$

Neel Krishnaswami

Mungkin Uday Reddy's Global state dianggap tidak perlu: Pengantar semantik berbasis objek, J. Lisp dan Symbolic Computation, 9 (1996): 7-76.

Dave Clarke

Saya membaca itu sekarang, sebenarnya!

Neel Krishnaswami

(Astaga, Neel, itu pertanyaan yang sulit.)

"Model rakyat" dari logika linier jelas merupakan model ruang yang koheren, dibahas dalam makalah Linear Logic Girard (dan juga dalam "Bukti dan Jenis"). Ini tidak merosot dalam arti yang Anda gambarkan.

Apakah semantik ini menyoroti bagaimana bahasa fungsional linier dapat diimplementasikan, saya tidak yakin. Ketika Anda berbicara tentang alokasi, membaca, dan pembaruan linear, Anda memang berbicara tentang implementasi. Jadi, mungkin, pertanyaan Anda mungkin dirumuskan sebagai, "bagaimana saya membuktikan benar implementasi bahasa fungsional linier yang menggunakan pembaruan negara?" Saya tidak tahu jawaban untuk itu, tapi saya pikir itu harus ada di surat kabar yang mengusulkan implementasi pembaruan linier.

Uday Reddy
sumber

Sebenarnya, terlalu mudah untuk membuktikan kebenaran implementasi keadaan linear - linearitas merupakan kendala struktural yang kuat sehingga Anda tidak perlu semantik untuk melakukan pembuktian ini. Akibatnya, saya tidak tahu semantik denotasional sederhana dari keadaan linier. Dua hal yang paling dekat dengan apa yang saya inginkan adalah pekerjaan Anda pada semantik berbasis objek, dan model "ruang panjang" dari Hofmann dalam karyanya tentang kompleksitas implisit.

Neel Krishnaswami

Sebenarnya, saya tidak akan menggambarkan semantik berbasis objek sebagai pemodelan "keadaan linear". Ini agak "negara berurutan" dan "objek linear", latte yang dikenakan oleh SCI. Model game dari Idealized Algol, yang juga "berbasis objek" dalam arti yang sama, tidak memiliki apa pun yang linier.

Uday Reddy

Bisakah Anda mencari referensi di mana bukti kebenaran tersebut dapat ditemukan? (Maaf, kembalikan pertanyaan itu pada Anda!)

Uday Reddy

Bukti kesehatan paling sederhana untuk bahasa linear dengan kondisi yang saya tahu adalah Ahmed, Fluet dan Morisett "L3: A Linear Language with Locations". ( ttic.uchicago.edu/~amal/papers/linloc-fi07.pdf ) Dalam makalah, mereka memberikan hubungan logis yang sederhana, tetapi menyebutkan bahwa kemajuan dan pelestarian bukti sintaksis juga berjalan.

Neel Krishnaswami

Ini adalah karya lain yang baru saja menarik perhatian saya. Coba citeseer untuk Stephen Cooper, tautan "Jenis Linier dan Pembaruan Imperatif" . Saya seharusnya tahu tentang ini, tetapi tidak.

Uday Reddy