Buku-buku tentang bahasa pemrograman semantik

31

Saya telah membaca " Semantik dengan Aplikasi " dari Nielson & Nielson , dan saya sangat menyukai subjeknya. Saya ingin memiliki satu buku lagi tentang semantik bahasa pemrograman - tetapi saya hanya bisa mendapatkan satu buku.

Saya melihat-lihat buku Turbak / Gifford , tetapi terlalu panjang lebar; Saya pikir Winskel akan baik-baik saja, tetapi saya tidak memiliki akses ke sana (tidak ada di perpustakaan Universitas kami, dan saya kekurangan uang), dan saya bahkan tidak yakin apakah itu tidak berkencan. Slonneger tampaknya baik-baik saja, tetapi bagian praktis membuatnya agak terlalu lama, dan saya tidak terlalu nyaman dengan gayanya.

Jadi pertanyaan saya adalah - apakah Winskel buku yang bagus? Dan apakah itu tanggal?

Juga, apakah ada buku ringkas lain tentang masalah ini?

reference-request pl.programming-languages semantics denotational-semantics books Jay
sumber
5
menambahkan tautan ke halaman penerbit untuk semua buku. mungkin berguna untuk orang lain yang ingin menjelajah.
Suresh Venkat
2
Semantik seperti apa yang Anda minati? Denotasional? Operasional? Gambaran?
Ohad Kammar
@Ohad Kammar: Saya tertarik pada keduanya.
Jay

Jawaban:

31

Itu semua tergantung seberapa dalam Anda ingin pergi, dan seberapa banyak Anda sudah tahu. Untuk seorang pemula, buku Winksel benar-benar bagus, tetapi ya, itu tidak memperkenalkan Anda pada seni semantik seperti yang ditulis sekitar 20 tahun yang lalu. Namun demikian itu masih merupakan pengantar pertama yang baik untuk subjek. Mungkin juga bermanfaat untuk menunjukkan bahwa T. Nipkow telah memformalkan sebagian besar buku Winskel di Isabelle / HOL, lihat di sini . Jadi jika Anda ingin belajar menggunakan asisten bukti interaktif bersama-sama dengan memahami semantik bahasa pemrograman, Anda memiliki banyak bahan yang koheren untuk menggambar.

Buku-buku lain yang lebih maju adalah:

  • Gunter, Semantik Pemrograman Bahasa , sebuah buku yang lebih maju yang berfokus pada semantik denotasional, sebuah pendekatan untuk semantik, yang belum memenuhi harapan. Berfokus pada bahasa yang berfungsi murni dan mengabaikan konkurensi. Ini adalah buku yang saya pelajari sendiri semantik sebagai sarjana, dan kalau dipikir-pikir saya berharap saya telah menggunakan buku Winksel sebagai gantinya. Gunter bukan bacaan yang mudah bagi pemula.

  • Domain dan lambda-calculi oleh Amadio dan Curien. Buku lain datang lebih banyak ditulis dalam tradisi domain-teori, meskipun membahas proses kalkulus.

  • Buku-buku John Mitchell yang telah disebutkan di atas. Mereka juga kebanyakan tentang perhitungan berurutan.

Buku-buku seperti Pierce's TAPL sangat bagus, tetapi fokus sempit pada satu aspek bahasa pemrograman, yaitu jenis, sama pentingnya dengan itu. Saya tidak akan merekomendasikan ini sebagai pengantar pertama untuk area umum bahasa pemrograman, tetapi wajib dibaca untuk siapa saja yang ingin belajar tentang jenis.

Sejujurnya, saya pikir saat ini tidak ada buku pengantar terbaru tentang semantik bahasa yang mencerminkan kemajuan substansial dekade terakhir, dengan pergeseran yang menentukan dari metode denotasi dan perhitungan berurutan ke konkurensi (proses kalkulus dan semantik permainan) , semantik aksioma dan penggunaan asisten bukti interaktif dalam verifikasi.

Pembaruan 22. April 2014: Tobias Nipkow dan Gerwin Klein telah menerbitkan buku baru

yang dapat dilihat sebagai 'Winskel in Isabelle / HOL'. Ini merupakan pengantar untuk semantik bahasa pemrograman (terutama operasional dan aksiomatik) tetapi tidak seperti pendekatan berbasis pena dan kertas sebelumnya, buku ini mengungkapkan semua matematika dalam Isabelle / HOL. Dengan kata lain, itu sekaligus buku tentang pembuktian teorema.

Buku ini sangat baru jadi saya belum pernah menggunakan untuk mengajar, tetapi kelihatannya sangat cocok sebagai pengantar yang ditempatkan di tingkat yang lebih rendah daripada Yayasan Perangkat Lunak oleh Pierce et al.

Martin Berger
sumber
2
Apakah ada pergeseran dari metode denotasional? Menurut saya lebih seperti jenis orang yang sebelumnya akan menggunakan bukti bergelombang tangan, saat ini diharapkan untuk menghasilkan bukti formal. Karena metode denotasional masih tidak dapat dengan mudah memodelkan semua yang kita lakukan, dan membutuhkan lebih banyak prasyarat, para peneliti tersebut menggunakan metode yang lebih mudah didekati seperti permainan, proses kalkulus, asisten bukti. Saya tidak yakin apakah ada penurunan dalam metode denotasional.
Ohad Kammar
4
Tolong jangan bingung semantik denotasional dengan teori domain . Semantik gim dapat, dan biasanya denotasi sempurna, artinya makna suatu program adalah fungsi dari makna bagian-bagiannya.
Andrej Bauer
2
Saya telah membuka utas baru mengenai komentar ini. Tetapi bahkan jika saya tidak yakin saya setuju dengan definisi Anda, semantik game bersifat denotasional. Saya pikir saya harus mengganti "game" dengan "semantik operasional" dalam komentar saya, dan memasukkan semantik game sebagai mungkin bentuk lain dari riset semantik denotasional. cstheory.stackexchange.com/questions/3577/…
Ohad Kammar
1
Saya tidak yakin ada perubahan. Lihat komentar pertamaku, mengingat komentar Andrej.
Ohad Kammar
1
Apakah ada perubahan? Pertanyaan yang menarik Bagaimana kita mengukur pergeseran? Ada begitu banyak kriteria yang bisa kita terapkan, dari yang relatif konkret seperti jumlah hibah yang diberikan untuk pendekatan yang berbeda, hingga ide-ide yang tidak jelas seperti berbagi pikiran. Mengingat seberapa terlibat kami, sebagai peneliti, sebagai karyawan, sebagai pelamar untuk uang hibah, berada dalam hasil dari pertanyaan seperti itu, tidak mungkin bahwa kami akan menyetujui jawaban.
Martin Berger
20

Berikut ini adalah contoh acak bahan yang tersedia secara online gratis:

  • Winskel, Semantik Resmi Bahasa Pemrograman , pratinjau Google Buku . Saya tidak tahu apa-apa tentang buku ini. Ada dalam daftar karena pertanyaannya secara khusus menanyakan tentang kontennya, yang sebagian besar online.
  • Morgan, Pemrograman dari Spesifikasi , daftar file ps . Subjek adalah penyempurnaan, yang merupakan proses mulai dengan deskripsi tingkat tinggi yang tidak dapat dieksekusi dan secara sistematis mengubah menjadi sesuatu yang dapat dieksekusi. Tentu saja, setiap langkah penyempurnaan harus memelihara semantik, sehingga membahas jenis semantik tertentu juga (sebagian besar didasarkan pada predikat treansformer).
  • Harper, Yayasan Praktis Bahasa Pemrograman , pdf konsep . Lihat komentar oleh Dave Clarke di bawah ini.
  • Remy, Menggunakan, Memahami, dan Mengungkap Bahasa OCaml , pdf . Ini adalah buku yang saya pelajari pemrograman fungsional (OCaml, lebih tepatnya) dan saya menyukainya banyak . Ini menyajikan semantik fitur bahasa dasar dengan cara yang sangat bagus dan dalam proses menyajikan lambda kalkulus dan teori ketik pada dasar `perlu tahu '.
  • Peyton Jones, Implementasi Bahasa Pemrograman Fungsional , djvu . Bab-bab pertama menjelaskan kalkulus lambda (dan `semantik operasionalnya ') dan bagaimana fitur-fitur bahasa tingkat tinggi dicobakan ke dalam kalkulus lambda. Dalam pengertian ini, makalah ini memberikan semantik operasional untuk bahasa fungsional.
  • Pierce (ed), Topik Tingkat Lanjut dalam Jenis dan Bahasa Pemrograman , pratinjau Google Buku .
  • Slonneger, Sintaks dan Semantik Bahasa Pemrograman , daftar file pdf . Saya melihat ini secara singkat sejak dulu dan tidak begitu menyukainya. Ada dalam daftar karena disebutkan dalam pertanyaan.
  • Brookes, Seorang Semantik untuk Logika Pemisahan Bersamaan , pdf . Ini adalah artikel besar (80 halaman), bukan buku. Saya memasukkannya karena ini merupakan perkembangan yang cukup baru yang menurut saya menarik.
Radu GRIGore
sumber
1
itu banyak tautan :)
Suresh Venkat
3
Ini akan lebih berguna jika sudah disajikan sebagai daftar. Bagaimanapun, saya akan merekomendasikan buku Harper: klik "mungkin".
Dave Clarke
Saya setuju. Radu, bisakah Anda membuat daftar buku, jadi kami tahu apa yang kami klik? ini akan menjadi sumber yang bagus.
Suresh Venkat
Daftarnya sekarang. (Versi pertama diposting sekitar jam 2 pagi, setelah tidur sekitar jam 5 malam sebelumnya.: P)
Radu GRIGore
16

Saya akan membagi buku-buku tentang semantik bahasa pemrograman menjadi dua kelas: mereka yang fokus pada pemodelan konsep bahasa pemrograman dan mereka yang fokus pada aspek - aspek dasar semantik. Tidak ada alasan buku tidak bisa melakukan keduanya. Tetapi, biasanya, hanya ada begitu banyak yang dapat Anda masukkan ke dalam sebuah buku, dan penulis juga memiliki kecenderungan mereka sendiri tentang apa yang penting.

Buku Winskel, telah disebutkan, melakukan sedikit dari kedua aspek. Dan, itu adalah buku pemula yang bagus. Buku yang sama baiknya, bahkan mungkin lebih baik, adalah yang saya mulai dengan: deskripsi denotasional Gordon tentang bahasa pemrograman . Ini adalah buku pertama saya tentang semantik, yang saya baca segera setelah saya menyelesaikan pekerjaan sarjana saya. Saya harus mengatakan itu memberi saya landasan semantik dan saya tidak pernah bertanya-tanya bagaimana semantik denotasional berbeda dari semantik operasional atau semantik aksiomatik, dll. Buku ini akan tetap menjadi favorit saya sepanjang waktu di semantik denotasional.

Buku-buku lain yang berfokus pada aspek pemodelan daripada aspek-aspek mendasar adalah sebagai berikut:

  • Tennent's Semantik dari bahasa pemrograman , yang merupakan buku uptodate lebih atau kurang tentang semantik bahasa pemrograman imperatif. Mudah dibaca. Namun, itu cenderung abstrak di bagian akhir buku ini dan Anda mungkin harus berjuang untuk melihat mengapa hal-hal dilakukan dengan cara tertentu.

  • Teori Reynolds tentang bahasa pemrograman . Siapa pun yang berspesialisasi dalam semantik harus membaca buku ini. Lagipula itu adalah karya Reynolds. (David Schmidt pernah berkata kepada saya, "bahkan jika Reynolds membacakan koran pagi untuk Anda, Anda ingin mendengarkan dengan cermat, karena Anda mungkin belajar sesuatu yang penting"!) Ini memiliki cakupan yang baik dari aspek pemodelan dan aspek dasar.

Buku-buku terbaik tentang aspek-aspek dasar adalah Gunter's (yang saya anggap sebagai buku teks pascasarjana), dan buku Mitchell (yang merupakan buku referensi yang bagus untuk dimuat di rak buku Anda karena cukup komprehensif).

Uday Reddy
sumber
Sangat menyenangkan memiliki Anda di sini, Uday!
Radu GRIGore
Saya senang berada di sini juga. Ini adalah sumber yang sangat bagus!
Uday Reddy
Bagaimana dengan: Transisi dan Pohon: Pengantar Semantik Operasional Struktural dari Hans Hüttel 2010. Tampaknya memiliki ulasan yang baik tetapi tidak ada yang menyebutkannya di sini.
Arturo Hernandez
1
@Uday: Terima kasih atas jawabannya. Apa yang dimaksud dengan "memodelkan konsep bahasa pemrograman" dan "aspek dasar semantik"? Apa perbedaan dan hubungan mereka?
Tim
1
@ Tim: Untuk memberikan semantik bahasa pemrograman, Anda perlu beberapa bentuk struktur matematika, misalnya, menetapkan dalam kasus paling sederhana, tetapi struktur canggih seperti domain, kategori, coalgebras dll. Untuk masalah yang tidak bisa ditangani oleh set. Yang saya maksud dengan "aspek dasar" adalah teori struktur yang lebih canggih ini. Dalam kasus sebelumnya, fokusnya adalah pada bahasa pemrograman dan, dalam kasus yang terakhir, itu adalah pada dasar matematika.
Uday Reddy
8

Saya benar-benar menikmati membaca Winskel ketika saya mengambil kursus sarjana tentang semantik. Tapi saya tidak tahu apakah ini tanggal, karena saya tidak melakukan penelitian di bidang ini. Nilai tambah dari Winskel adalah Anda dapat menemukannya diterjemahkan dalam bahasa lain selain bahasa Inggris.

Untuk bacaan lebih lanjut, lebih banyak di tingkat pascasarjana, saya sarankan buku - buku John Mitchell Yayasan untuk Pemrograman Bahasa dan Konsep dalam Bahasa Pemrograman . Jika Anda hanya membaca bab-bab pertama, saya kira mereka juga memenuhi persyaratan keringkasan Anda.

Anda tidak akan menemukan draf gratis buku-buku ini, jadi jika Anda memiliki anggaran terbatas pilih "mungkin" dalam jawaban Radu.

Alessandro Cosentino
sumber
6

Yah, saya bukan ahli dalam hal ini, tetapi ada beberapa saran umum yang bisa saya berikan.

Pertama, ada beberapa orang yang sudah membaca buku dan memberikan ulasan. Misalnya, untuk buku Winskel The Formal Semantics of Programming Languages (lihat [1] dan [2] ) saya menemukan ulasan di Amazon.

Bagian dari satu ulasan berbunyi:

Buku ini membingungkan antara sintaks dan semantik sejak awal, seperti memisahkan literal dari nilainya. Tidak ada notasi khusus yang digunakan untuk membedakannya. Ini adalah masalah penting yang harus ditangani penulis dalam topik seperti ini. Juga, beberapa notasi lain yang digunakannya cukup membingungkan, seperti menunjukkan premis dan kesimpulan.

Penulis tampaknya berasumsi bahwa Anda memiliki SEMUA prasyarat yang diperlukan ketika ia menjelaskan materi latar belakang dalam beberapa bab pertama (yaitu teori himpunan, semantik operasional, induksi, definisi induktif) dengan sangat singkat. Gaya yang digunakan penulis dalam pengantar adalah dengan menempatkan dua atau tiga paragraf teks dan meletakkan beberapa formula lalu memberikan latihan. Yang, bagi saya, cukup membuat frustrasi ...

18/20 orang menganggap ulasan ini berguna. Anda dapat mencari Amazon (atau sumber lain) untuk melihat lebih banyak ulasan.

Kedua, Amazon menawarkan Jenis dan Bahasa Pemrograman dan Teori Kategori Dasar untuk Ilmuwan Komputer beserta buku ini. Pada topik lain, Dave Clarke menawarkan buku-buku ini sebagai buku yang bagus sekali tentang "Jenis Sistem dan Pemrograman Semantik Bahasa." Sekali lagi, saya bukan ahli, tetapi itu mungkin berguna bagi Anda.

MS Dousti
sumber
TaPL berjalan agak terlalu lambat untuk seleraku. Ini buku yang bagus, tapi saya sebutkan ini karena orang yang bertanya kelihatannya khawatir tentang buku-buku "bertele-tele".
Radu GRIGore
@ Radu: Tentu saja TAPL lambat, tapi ini pengantar yang bagus. Buku Harper yang Anda sebutkan di tautan Anda berjalan lebih cepat dan mencakup lebih banyak landasan, meskipun belum selesai.
Dave Clarke
4
Ambil ulasan Amazon tentang buku Winskel dengan sedikit garam. Ini sering digunakan sebagai teks yang direkomendasikan dalam kursus semantik sarjana dan mungkin menarik siswa yang tidak puas. Saya sudah membaca buku dan menemukan bab pengantar lebih dari cukup. Notasi-nya di seluruh tampaknya sepenuhnya standar juga.
Dominic Mulligan