Halaman "Skema Lanjutan: Beberapa Bit Nakal" menyatakan:
Lanjutan adalah konstruksi aliran kontrol yang kuat dari mana hampir semua struktur aliran kontrol lainnya [...] dapat diturunkan.
Saya berpikir bahwa Skema ini call/cc, yang terkait (*) ke operator J Peter Landin ini, dapat digunakan untuk mengimplementasikan setiap struktur kontrol aliran dikenal?
Dengan "control flow structure" Saya secara khusus memikirkan deskripsi Wikipedia tentang mereka, misalnya pengecualian, coroutine, benang hijau dan sebagainya.
Secara khusus, apakah ada contoh struktur aliran kontrol yang tidak dapat diimplementasikan menggunakan call/cc?
(*) Saya belum bisa menggali kertas yang menetapkan yang call/ccsekuat operator J. Sebuah makalah oleh Felleisen (yang saya belum baca dan diakui memiliki masalah untuk memahaminya sepenuhnya) menyelidiki ini, dan tampaknya menyimpulkan bahwa meskipun mereka berada di kelas kompleksitas yang berbeda, mereka secara formal setara.
(Perhatikan juga bahwa saya telah memperbarui pertanyaan berdasarkan komentar di bawah)
Memperbarui
Berdasarkan jawaban yang sangat baik dari @Neel di bawah ini, saya telah melihat situs-situs yang mengomentari kelanjutan yang dibatasi dan tidak didahulukan , dan memang terlihat bahwa sementara call/cc, yang tidak direvisi, tidak cukup. Sementara itu, kelanjutan kelas pertama, dibatasi (seperti shift/reset) dapat digunakan, tampaknya, untuk mengekspresikan struktur aliran kontrol apa pun.
call/cctidak dapat mengungkapkan pengecualian jika tidak ada negara . (Seperti yang ditunjukkan oleh Thielecke, pengecualian dapat diimplementasikan dengan mengedarkan dua kelanjutan, satu untuk program dan yang lainnya untuk penangan pengecualian, tetapi itu membutuhkan lebih dari sekadarcall/cc.)ambkabur, -operator, dan sebagainya.Jawaban:
Dalam jawaban ini, saya akan mengambil "ekspresif" dengan maksud "makro-ekspresif" dalam arti Felleisen 1991, On The Expressive Power of Programming Languages . (Secara intuitif, fitur bahasa dapat diekspresikan makro jika Anda dapat mendefinisikannya sebagai transformasi sumber lokal, tanpa menggunakan transformasi seluruh program.)
Dengan definisi ini, jawabannya adalah tidak : kontrol dibatasi tidak makro-ekspresif dalam lambda-calculus + call / cc. Untuk mengekspresikan operator kontrol yang dibatasi menggunakan panggilan / cc. Untuk menerapkan pembatas kontrol (bagian reset shift / reset), Anda perlu beberapa negara untuk mensimulasikan tanda kelanjutan, pada dasarnya untuk menyandikan tumpukan untuk mensimulasikan masa dinamis dari tanda kelanjutan.
Namun, kontrol terbatas adalah efek universal, dalam arti berikut. Dalam tesis PhD-nya , Andrzej Filinski menunjukkan bahwa efek samping yang dapat diekskripsikan dikodekan menggunakan salah satu kelanjutan yang dibatasi, atau panggilan / cc dan sel tunggal negara. Secara kasar, "efek samping yang dapat diekspresikan" adalah setiap efek yang tipe monadiknya dapat didefinisikan berdasarkan jenis-jenis bahasa pemrograman.
Secara mengejutkan, ide ini tampaknya cukup menarik dalam praktiknya. Selama dekade terakhir, Gordon Plotkin dan John Power telah menganjurkan gagasan untuk mengambil semantik aljabar teori efek : idenya adalah bahwa Anda menentukan operasi efek samping yang Anda minati, dan persamaan yang Anda harapkan dapat mereka penuhi, dan kemudian Anda secara umum bisa mendapatkan semantik dengan mengambil monad gratis atas teori ini.
Matija Pretnar dan Andrej Bauer mengambil pendekatan matematis ini, dan kemudian mengimplementasikannya dalam bahasa Eff mereka untuk menciptakan konstruksi bahasa baru yang dijuluki "effect handler": Anda dapat menulis kode yang menggunakan serangkaian fitur imperatif, dan kemudian memberikan fitur imperatif semantik dengan menulis satu set penangan yang mengatakan bagaimana menerapkan setiap operasi yang efektif.
sumber