Bagaimana efek samping ditangani dalam semantik?

Dalam bagian "Pengantar Bahasa Pemrograman" Anthony Aaby tentang Semantik , ia membuat pengamatan berikut:

Banyak pekerjaan dalam semantik bahasa pemrograman termotivasi oleh masalah yang dihadapi dalam mencoba membangun dan memahami program-program penting --- program dengan perintah penugasan. Karena perintah tugas menugaskan nilai ke variabel, tugas dapat memiliki efek yang tak terduga di bagian program yang jauh.

Ini menurut saya sebagai pengakuan yang luar biasa, bahwa membiarkan efek samping akan memotivasi sebagian besar pekerjaan dalam semantik.

Bagaimana keberadaan efek samping dalam bahasa pemrograman berdampak pada kemampuan memetakan suatu program ke model komputasi? Apakah ada pendekatan untuk mengelola negara yang dapat meningkatkan proses ini sambil tetap memungkinkan efek samping?

Berdasarkan jawaban Charles, kesulitan utama dalam teori bahasa pemrograman adalah bahwa gagasan alami tentang kesetaraan program biasanya bukan kesetaraan yang ketat baik dalam semantik matematika paling sederhana yang dapat Anda berikan, atau dalam model mesin yang mendasarinya. Sebagai contoh, pertimbangkan bit kode mirip Java berikut ini:

Object x = new Object();
Object y = new Object();
... some more code ...

Jadi program ini membuat objek dan menamakannya x, dan kemudian membuat objek kedua bernama y, dan kemudian melanjutkan mengeksekusi beberapa kode lagi. Sekarang, anggaplah seorang programmer memutuskan untuk membalik urutan alokasi dari dua objek ini:

Object y = new Object();
Object x = new Object();
... some more code ...

Sekarang, ajukan pertanyaan: apakah refactoring ini mengubah perilaku program? Di satu sisi, pada mesin yang mendasarinya, x dan y akan dialokasikan di lokasi yang berbeda dalam dua kali menjalankan program. Jadi dalam hal ini, program berperilaku berbeda.

Tetapi dalam bahasa seperti Java, Anda hanya dapat menguji referensi untuk kesetaraan, dan bukan untuk pesanan, jadi ini adalah perbedaan yang " tidak bisa diamati " oleh beberapa kode lainnya . Akibatnya, sebagian besar programmer akan berharap bahwa membalik urutan tidak akan membuat perbedaan pada jawaban akhir, dan sebagian besar penulis kompiler berharap dapat melakukan pemesanan ulang dan optimisasi berdasarkan ini. (Di sisi lain, dalam bahasa seperti C, Anda dapat membandingkan pointer untuk pemesanan, dengan melemparkannya ke integer terlebih dahulu, dan penataan ulang ini tidak serta merta menjaga perilaku yang dapat diamati.)

Salah satu pertanyaan sentral semantik adalah untuk menjawab pertanyaan tentang kapan dua program setara secara nyata. Karena gagasan pengamatan kami bergantung pada fitur-fitur bahasa pemrograman, kami berakhir dengan definisi seperti "dua program setara ketika tidak ada program klien yang dapat menghitung jawaban yang berbeda berdasarkan menerima program-program tersebut sebagai input." Kuantifikasi atas semua program klien adalah yang membuat pertanyaan ini sulit - sepertinya Anda akhirnya harus mengatakan sesuatu tentang semua program klien yang mungkin untuk mengatakan sesuatu tentang dua bagian kode tertentu.

Trik dengan semantik denotasional adalah untuk memberikan interpretasi matematis yang memungkinkan Anda menghindari kuantifikasi universal ini - Anda mengatakan bahwa arti dari sepotong kode adalah nilai matematika, dan Anda membandingkannya dengan memeriksa untuk melihat apakah mereka secara matematis sama atau tidak. Ini adalah lokal (yaitu, komposisi), dan tidak melibatkan kuantifikasi atas semua klien yang mungkin. (Anda perlu menunjukkan bahwa semantik denotasional menyiratkan kesetaraan kontekstual agar itu menjadi sehat, tentu saja. Ketika selesai - ketika kesetaraan denotasional persis sama dengan kesetaraan kontekstual, kita katakan semantik "sepenuhnya abstrak".)

Tetapi berarti Anda perlu memastikan bahwa semantik denotasional memvalidasi kesetaraan tersebut. Jadi untuk contoh ini, jika Anda ingin memberikan semantik denotasi untuk bahasa seperti Java ini, Anda perlu memastikan tidak hanya bahwa memanggil baru mengambil tumpukan dan memberi Anda kembali tumpukan baru dengan objek yang baru dibuat, tetapi itu artinya dari program ini invarian sama di bawah semua permutasi dari tumpukan input. Ini dapat melibatkan struktur matematika yang cukup kompleks (misalnya, dalam hal ini bekerja dalam kategori yang memastikan semuanya berfungsi modulo kelompok permutasi yang sesuai).

Tentu saja ada cara untuk berurusan dengan efek dalam semantik (denotasional). Sebagai contoh, kita dapat menggunakan gagasan Eugenio Moggi bahwa efek komputasi adalah monad (ide ini juga telah digunakan dalam desain Haskell). Salah satu masalah dengan ini adalah bahwa monad sulit untuk digabungkan. Gordon Plotkin dan John Power menyarankan penyempurnaan monad Moggi untuk teori Lawvere , atau teori aljabar sebagaimana mereka juga disebut, yang mencakup efek aljabar (efek paling umum adalah aljabar, seperti negara, I / O, non-determinisme, tetapi kelanjutannya adalah tidak). Untuk perawatan komprehensif, lihat tesis Matija Pretnar .

Saya juga harus menyebutkan kemungkinan semantik dunia untuk negara bagian, yang dikembangkan oleh Frank Oles dan John Reynolds (maaf, tidak dapat menemukan tautan yang lebih baik, hal ini berasal dari tahun 1982), yang mendahului monad Moggi. Mereka menggunakan kategori presheave untuk menyediakan semantik bahasa seperti algol yang memodelkan banyak aspek negara bagian dengan benar (tapi tidak semuanya, saya pikir model memungkinkan snapback, tapi mungkin ingatan saya salah).

Matthias Felleisen menyajikan solusi yang menarik untuk masalah efek samping dalam semantik dalam seri tentang "Teori dan Negara Kontrol Sintaksis."

Garis pekerjaan itu menghasilkan mesin CESK, kerangka mesin abstrak sederhana yang mampu memodelkan bahasa fungsional, berorientasi objek, imperatif dan bahkan logika secara ringkas. Kerangka kerja CESK menangani tidak hanya efek samping, tetapi juga konstruksi kontrol "kompleks" seperti pengecualian, kelanjutan, kemalasan, dan bahkan utas.

Mesin CESK, dan semantik operasional langkah kecil secara lebih luas, telah menjadi standar de facto dalam teori bahasa pemrograman selama sekitar dua dekade.

Singkatnya, mesin CESK adalah mesin langkah kecil dengan empat komponen untuk menggambarkan setiap keadaan mesin: string kontrol (generalisasi dari penghitung program), lingkungan, toko (juga disebut heap) dan kelanjutan saat ini.

Lingkungan memetakan variabel ke alamat; toko memetakan alamat ke nilai.

Ini membuatnya mudah untuk memodelkan variabel yang bisa berubah: cukup ubah nilainya di alamatnya.

Ini juga membuatnya mudah untuk memodelkan pointer dan alokasi dinamis: cukup buat alamat toko nilai kelas satu.

Dengan cara yang serupa, kelanjutan kelas satu dihasilkan dari menjadikannya nilai yang dapat dialamatkan.

Bagaimana keberadaan efek samping dalam bahasa pemrograman berdampak pada kemampuan memetakan suatu program ke model komputasi?

Ini tidak selalu menyulitkan, tetapi itu memberlakukan pembatasan pada cara semantik ekspresi yang lebih besar dapat dibangun dari yang lebih kecil. Ini dapat berinteraksi sangat buruk dengan konstruksi pemrograman tertentu lainnya, misalnya, jika seseorang ingin memberikan semantik denotasi gaya Scott untuk bahasa yang memungkinkan penugasan fungsi tingkat tinggi ke referensi global.

Bukan hanya efek samping seperti keadaan yang menyebabkan masalah. Bahasa imperatif sederhana seperti bahasa perintah Dijkstra yang dijaga memiliki efek samping seperti ini, dan memiliki semantik yang bagus. Masalah muncul dengan ekstensi lambda-kalkulus dengan jenis semantik operasional yang diharapkan dari bahasa pemrograman bahkan tanpa adanya efek samping: yang paling awal, PCF Plotkin, diberi model denotasi yang relatif lebih awal, tetapi semantiknya tidak sepenuhnya abstrak, yang berarti bahwa semantik denotasional terlalu umum, tidak persis sesuai dengan semantik operasionalnya. PCF akhirnya menerima semantik denotasi yang sepenuhnya abstrak pada akhir 1980-an dengan semantik permainan, yang sama sekali tidak seperti semantik orde-teoretis Scott. Concurrency masih belum menerima perlakuan denotasi yang memadai.

Banyak yang mempertanyakan pentingnya semantik semacam ini. Kami selalu dapat menyediakan semacam semantik operasional, bahkan jika "semantik" itu hanya sumber program dan nama-nama beberapa mesin yang telah menyusun dan menjalankan program: untuk alasan ini Strachey mengutuk semantik operasional. Tetapi semantik operasi struktural Plotkin telah menunjukkan bagaimana semantik operasional dapat dipisahkan dari model mesin, dan karya Pitt telah menunjukkan bagaimana semantik tersebut dapat mendukung alasan yang sama tentang program dan bahasa pemrograman ke semantik denotasional. Jadi semantik operasional adalah alternatif yang layak untuk semantik denotasional, dan telah diterapkan dengan sukses ke sejumlah besar bahasa pemrograman seperti Standar ML.

Apakah ada pendekatan untuk mengelola negara yang dapat meningkatkan proses ini sambil tetap memungkinkan efek samping?

Pada tingkat tertentu, kesulitan menyediakan semantik berhubungan dengan kesulitan menyediakan bahasa pemrograman yang kuat yang berperilaku seperti yang diharapkan. Keputusan desain yang termotivasi secara pragmatis - seperti menghindari penggunaan negara global bersama dengan konkurensi, biasanya melalui konkurensi lewat pesan - membuatnya lebih mudah untuk menyediakan semantik.