Saya sedang mencari teknik implementasi untuk bahasa pemrograman, dan baru-baru ini menemukan tumpukan spaghetti, yang dianggap cocok untuk model gaya kelanjutan lewat (diberikan penggunaannya dalam misalnya Skema dan SML / NJ ). Demi kesederhanaan, mari kita hanya mempertimbangkan proses single-threaded untuk pertanyaan ini.

Namun, saya agak bingung dengan diagram di Wikipedia (juga ditemukan di tempat lain ). Secara khusus, saya tidak mengerti bagaimana situasi seperti itu dapat muncul. Saya hanya bisa membayangkan bahwa cabang yang berwarna abu-abu tidak dapat dijangkau dan harus dikumpulkan dari sampah. Di sisi lain, dengan pemahaman samar saya tentang bagaimana menerapkan CPS menggunakan tumpukan spaghetti, saya tidak bisa membayangkan bagaimana Anda bisa mendapatkan loop dalam struktur itu. Saya harus menyimpulkan bahwa, daripada "parent-pointer tree", ini sebenarnya adalah grafik asiklik terarah, dengan sebanyak mungkin sumber non-sampah yang ada utasnya, dan sebanyak-banyaknya tenggelam yang ada sebagai "titik keluar" potensial (potensial).

Tapi pemahaman saya tentang implementasi ini cukup samar, jadi saya kira saya mungkin kehilangan sesuatu. Saya harap seseorang dapat mencerahkan saya di sini di "tumpukan panggilan spaghetti", yang saya maksudkan struktur data seperti yang digunakan dalam Skema dan / atau SML / NJ untuk mengimplementasikan proses berbasis CPS.

1. Diberikan tumpukan panggilan spageti berikut:

   [exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                   ^
                                    `---- [frame C]
   

   Sejauh yang saya mengerti, kontrol aliran dari B baik melepaskan tumpukan dengan melompat ke induk (A menjadi aktif, B tidak dapat dijangkau sekarang menjadi sampah), atau mengganti bingkai aktif dengan subgraf, terhubung hanya menggunakan referensi yang dipegang oleh B atau referensi ke bingkai baru. Eksekusi tidak dapat mengalir ke frame C, yang berarti frame C adalah sampah.

2. Daripada situasi sebelumnya, saya berpikir bahwa situasi bebas sampah berikut mungkin muncul:

   [exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   Sebagai contoh, saya bisa membayangkan bahwa frame Z milik beberapa fungsi keputusan, yang berlanjut dengan frame X atau frame Y (yang mana keduanya akan kembali ke W). Ini berarti bahwa tumpukan panggilan spaghetti bukan " pohon pointer orangtua ".

3. Namun, saya tidak dapat membayangkan situasi di mana loop dapat dibangun. Ambil situasi berikut, misalnya:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   Saya tahu bahwa ikatan rekursif adalah suatu hal, tetapi saya sangat meragukan bahwa ini masuk akal. Jika Q kembali ke R, frame Q "dihabiskan". Jika R kembali ke P, dan P tidak bisa hanya kembali ke Q, karena itu harus diinisialisasi ulang terlebih dahulu. Dengan demikian, loop akan menyebabkan kondisi tidak konsisten. (Kecuali, tentu saja, saya salah mengerti tujuan dari struktur data ini, dan Anda hanya akan menggunakan node di dalamnya sebagai templat untuk kerangka Anda saat ini.)

Dari pengamatan ini, saya harus menyimpulkan bahwa tumpukan panggilan spaghetti (tanpa sampah) sebenarnya adalah DAG. Apakah ini benar? Atau apakah saya salah memahami tujuan dari struktur data ini?

Pembaruan:

• Saya telah membaca salinan makalah berikut:

  EA Hauck dan BA Dent. 1968. Mekanisme tumpukan B6500 / B7500 Burroughs '. Dalam Prosiding 30 April - 2 Mei 1968, konferensi komputer pegas bersama (AFIPS '68 (Spring)). ACM, New York, NY, AS, 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Makalah ini tampaknya mendefinisikan Sistem Suguaro Stack. Ternyata, Sistem Suguaro Stack ini adalah tumpukan panggilan tradisional yang memungkinkan beberapa "pekerjaan" berjalan melalui bingkai tumpukan yang dibagi sebagian; ini sama sekali tidak terkait dengan kelanjutan.

• Makalah berikut (dan kertas pendampingnya tahun 1996) tampaknya menjelaskan apa yang terjadi di kompiler SML / NJ:

  Zhong Shao dan Andrew W. Appel. 2000. Konversi penutupan yang efisien dan aman untuk ruang. ACM Trans. Program. Lang. Syst. 22, 1 (Januari 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Saya pikir saya harus membaca makalah ini ( menyalin di situs web penulis ) sebelum melakukan hal lain dengan pertanyaan ini. Konsep "Closely Linked Closures" sangat mirip dengan Sistem Suguaro Stack, karena selalu sangat dangkal dan hanya dimaksudkan untuk berbagi variabel bebas:

  Algoritme konversi-konversi baru kami menggunakan penutupan yang ditautkan dengan aman (kolom ke-3 dalam Gambar 1) yang hanya berisi variabel yang benar-benar dibutuhkan dalam fungsi tetapi menghindari penyalinan penutupan dengan mengelompokkan variabel dengan masa pakai yang sama ke dalam catatan yang dapat dibagi. [...] Tidak seperti penutupan tertaut, tingkat bersarang dari penutupan tertaut yang aman tidak pernah melebihi lebih dari dua (satu lapisan untuk penutupan itu sendiri; yang lain untuk catatan waktu hidup yang berbeda) sehingga mereka masih menikmati waktu akses variabel yang sangat cepat.

  Makalah ini juga secara eksplisit menyebutkan bahwa ia tidak menggunakan "sembarang runtime stack":

  Sebagai gantinya, kami memperlakukan semua catatan aktivasi sebagai penutupan untuk fungsi lanjutan dan mengalokasikannya dalam register di heap.

  Saya pikir saya salah paham dan / atau salah membaca artikel Wikipedia, karena tumpukan spaghetti tidak digunakan untuk kontrol aliran. Namun, setelah membaca makalah dengan teliti oleh Appel dan Shao, saya mungkin bisa menyatakan kembali pertanyaan dengan mengacu pada grafik ketergantungan dari penutup daripada "tumpukan panggilan spaghetti" (yang tampaknya bukan suatu hal).

Apakah Spaghetti Stacks Parent-Pointer Trees?

Ya, tumpukan spaghetti adalah pohon penunjuk orang tua. Anda dapat menganggap tumpukan spageti memiliki struktur yang sama dengan kumpulan daftar yang ditautkan tunggal yang berbagi struktur. Jika dilihat secara keseluruhan, kumpulan daftar membentuk pohon. Tetapi ketika dilihat secara individual, setiap daftar membentuk tumpukan.

Setiap proses dalam sistem akan memiliki salah satu dari daftar ini, yang mewakili tumpukan kontrolnya. Kepala daftar adalah bagian atas tumpukan (yaitu, bingkai aktif). Its nextpointer referensi frame induk.

Apa yang Anda lihat dalam diagram adalah struktur untuk banyak proses. Tumpukan untuk proses "aktif" disorot. Bagian-bagian dari pohon yang bukan bagian dari tumpukan aktif berwarna abu-abu. Ini mewakili tumpukan untuk proses lain.

Apakah Tumpukan Spaghetti Membentuk DAG?

Karena tumpukan Spaghetti adalah pohon penunjuk orang tua, mereka memang DAG. Tapi hanya DAG yang juga pohon yang bisa menjadi tumpukan Spaghetti. Jadi tidak, tumpukan Spaghetti tidak membentuk DAG yang bukan pohon.

Contoh fungsi keputusan Anda mengonfigurasi struktur tumpukan kontrol dengan data yang disimpan di tumpukan. Tentu saja, struktur apa pun dapat dibentuk jika kita mulai mempertimbangkan data. Tetapi sebagai struktur data, setiap node dalam tumpukan spageti akan memiliki tepat satu induk.