Manakah alternatif untuk menggunakan tumpukan untuk mewakili semantik panggilan fungsi?

Kita semua tahu dan suka bahwa panggilan fungsi biasanya diimplementasikan menggunakan stack; ada bingkai, alamat pengirim, parameter, seluruh lot.

Namun, stack adalah detail implementasi: konvensi pemanggilan dapat melakukan hal yang berbeda (mis. X86 menggunakan panggilan cepat (beberapa) register, MIPS dan pengikut menggunakan register windows, dan sebagainya) dan optimisasi dapat melakukan hal-hal lain (inlining, penghilangan frame pointer, optimisasi panggilan ekor ..).

Tentu, kehadiran instruksi stack yang mudah pada banyak mesin (VM seperti JVM dan CLR, tetapi juga mesin nyata seperti x86 dengan PUSH / POP mereka dll.) Membuatnya nyaman untuk menggunakannya untuk panggilan fungsi, tetapi dalam beberapa kasus dimungkinkan untuk memprogram dengan cara di mana tumpukan panggilan tidak diperlukan (Saya sedang memikirkan Gaya Berlanjut Berlanjut di sini, atau Aktor dalam sistem pengiriman pesan)

Jadi, saya mulai bertanya-tanya: apakah mungkin untuk mengimplementasikan fungsi panggilan semantik tanpa stack, atau lebih baik, menggunakan struktur data yang berbeda (antrian, mungkin, atau peta asosiatif?)
Tentu saja, saya mengerti bahwa stack sangat nyaman (ada alasan mengapa itu ada di mana-mana) tapi saya baru saja bertemu dengan implementasi yang membuat saya bertanya-tanya ..

Apakah ada di antara Anda yang tahu apakah itu pernah dilakukan dalam bahasa / mesin / mesin virtual apa pun, dan jika demikian, apa perbedaan dan kekurangannya?

EDIT: Perasaan saya adalah bahwa pendekatan sub-komputasi yang berbeda dapat menggunakan struktur data yang berbeda. Sebagai contoh, kalkulus lambda bukan berbasis stack (ide aplikasi fungsi ditangkap oleh reduksi) tapi saya melihat bahasa / mesin / contoh nyata. Itu sebabnya saya bertanya ...

Tergantung pada bahasanya, mungkin tidak perlu menggunakan tumpukan panggilan. Tumpukan panggilan hanya diperlukan dalam bahasa yang memungkinkan rekursi atau rekursi timbal balik. Jika bahasa tidak memungkinkan rekursi, maka hanya satu permintaan dari setiap prosedur yang dapat aktif setiap saat, dan variabel lokal untuk prosedur tersebut dapat dialokasikan secara statis. Bahasa-bahasa seperti itu memang harus membuat ketentuan untuk perubahan konteks, untuk penanganan interupsi, tetapi ini masih tidak memerlukan tumpukan.

Lihat FORTRAN IV (dan sebelumnya) dan COBOL versi awal untuk contoh bahasa yang tidak memerlukan tumpukan panggilan.

Lihat Data Kontrol 6600 (dan mesin Data Kontrol sebelumnya) untuk contoh superkomputer awal yang sangat sukses yang tidak menyediakan dukungan perangkat keras langsung untuk tumpukan panggilan. Lihat PDP-8 untuk contoh komputer mini awal yang sangat sukses yang tidak mendukung tumpukan panggilan.

Sejauh yang saya tahu, mesin tumpukan Burroughs B5000 adalah mesin pertama dengan tumpukan panggilan perangkat keras. Mesin B5000 dirancang dari bawah ke atas untuk menjalankan ALGOL, yang membutuhkan rekursi. Mereka juga memiliki salah satu arsitektur berbasis deskriptor pertama, yang meletakkan dasar bagi arsitektur kapabilitas.

Sejauh yang saya tahu, itu adalah PDP-6 (yang tumbuh menjadi DEC-10) yang mempopulerkan perangkat keras stack stack, ketika komunitas hacker di MIT menerima pengiriman satu dan menemukan bahwa operasi PUSHJ (Push Return Address and Jump) memungkinkan rutin cetak desimal dikurangi dari 50 instruksi menjadi 10.

Fungsi panggilan semantik yang paling dasar dalam bahasa yang memungkinkan rekursi membutuhkan kemampuan yang cocok dengan tumpukan. Jika itu yang Anda butuhkan, maka tumpukan dasar adalah pertandingan yang bagus dan sederhana. Jika Anda membutuhkan lebih dari itu, maka struktur data Anda harus berbuat lebih banyak.

Contoh terbaik untuk membutuhkan lebih banyak yang saya temui adalah "kelanjutan", kemampuan untuk menunda perhitungan di tengah, menyimpannya sebagai gelembung keadaan beku, dan mematikannya lagi nanti, mungkin berkali-kali. Lanjutan menjadi populer dalam dialek Skema LISP, sebagai cara untuk mengimplementasikan, antara lain, keluar dari kesalahan. Lanjutan membutuhkan kemampuan untuk memotret lingkungan eksekusi saat ini, dan mereproduksinya nanti, dan tumpukan agak tidak nyaman untuk itu.

"Struktur dan Interpretasi Program Komputer" dari Abelson & Sussman merinci lebih lanjut tentang kelanjutan.

Tidak mungkin untuk mengimplementasikan fungsi panggilan semantik tanpa menggunakan semacam tumpukan. Hanya dimungkinkan untuk memainkan permainan kata (mis. Gunakan nama lain untuk itu, seperti "buffer pengembalian FILO").

Dimungkinkan untuk menggunakan sesuatu yang tidak mengimplementasikan semantik fungsi panggilan (misalnya gaya kelanjutan lewat, aktor), dan kemudian membangun semantik fungsi panggilan di atasnya; tetapi ini berarti menambahkan semacam struktur data untuk melacak di mana kontrol dilewatkan ketika fungsi kembali, dan bahwa struktur data akan menjadi tipe tumpukan (atau tumpukan dengan nama / deskripsi yang berbeda).

Bayangkan Anda memiliki banyak fungsi yang semuanya dapat saling memanggil. Pada saat run-time, setiap fungsi harus tahu ke mana harus kembali ketika fungsi keluar. Jika firstpanggilan secondmaka Anda memiliki:

second returns to somewhere in first

Kemudian, jika secondpanggilan thirdAnda memiliki:

third returns to somewhere in second
second returns to somewhere in first

Kemudian, jika thirdpanggilan fourthAnda memiliki:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

Karena setiap fungsi dipanggil, lebih banyak informasi "tempat kembali" harus disimpan di suatu tempat.

Jika suatu fungsi kembali, maka informasi "tempat kembali" digunakan dan tidak lagi diperlukan. Misalnya, jika fourthkembali ke suatu tempat di thirdkemudian jumlah informasi "tempat untuk kembali" akan menjadi:

third returns to somewhere in second
second returns to somewhere in first

Pada dasarnya; "semantik fungsi panggilan" menyiratkan bahwa:

• Anda harus memiliki informasi "tempat untuk mengembalikan"
• jumlah informasi bertambah ketika fungsi dipanggil dan dikurangi ketika fungsi kembali
• bagian pertama dari "tempat untuk kembali" informasi yang disimpan akan menjadi bagian terakhir dari "tempat untuk kembali" informasi yang dibuang

Ini menjelaskan buffer FILO / LIFO atau tumpukan.

Jika Anda mencoba menggunakan jenis pohon, maka setiap simpul di pohon tidak akan pernah memiliki lebih dari satu anak. Catatan: simpul dengan banyak anak hanya dapat terjadi jika suatu fungsi memanggil 2 fungsi atau lebih pada saat yang sama , yang membutuhkan semacam konkurensi (mis. Utas, fork (), dll) dan itu tidak akan menjadi "semantik fungsi panggilan". Jika setiap simpul di pohon tidak akan pernah memiliki lebih dari satu anak; maka "pohon" itu hanya akan digunakan sebagai buffer FILO / LIFO atau tumpukan; dan karena itu hanya digunakan sebagai buffer FILO / LIFO atau tumpukan, cukup adil untuk mengklaim bahwa "tree" adalah tumpukan (dan satu-satunya perbedaan adalah permainan kata dan / atau detail implementasi).

Hal yang sama berlaku untuk setiap struktur data lain yang dapat digunakan untuk mengimplementasikan "fungsi panggilan semantik" - itu akan digunakan sebagai tumpukan (dan satu-satunya perbedaan adalah permainan kata dan / atau detail implementasi); kecuali jika rusak "fungsi panggilan semantik". Catatan: Saya akan memberikan contoh untuk struktur data lain jika saya bisa, tetapi saya tidak bisa memikirkan struktur lain yang sedikit masuk akal.

Tentu saja bagaimana stack diimplementasikan adalah detail implementasi. Ini bisa berupa area memori (di mana Anda melacak "stack top saat ini"), itu bisa berupa semacam daftar yang ditautkan (di mana Anda melacak "entri saat ini dalam daftar"), atau itu dapat diterapkan di beberapa cara lain. Juga tidak masalah apakah perangkat keras memiliki dukungan bawaan atau tidak.

Catatan: Jika hanya satu doa dari prosedur apa pun yang dapat aktif setiap saat; maka Anda dapat secara statis mengalokasikan ruang untuk informasi "tempat kembali". Ini masih berupa tumpukan (mis. Daftar entri yang dialokasikan secara statis yang digunakan dengan cara FILO / LIFO).

Perhatikan juga bahwa ada beberapa hal yang tidak mengikuti "fungsi panggilan semantik". Hal-hal ini termasuk "semantik yang berpotensi sangat berbeda" (mis. Kelanjutan lewat, model aktor); dan juga menyertakan ekstensi umum ke "semantik fungsi panggilan" seperti konkurensi (utas, serat, apa pun), setjmp/ longjmp, penanganan pengecualian, dll.

Bahasa konatatif mainan XY menggunakan antrian panggilan dan tumpukan data untuk dieksekusi.

Setiap langkah perhitungan hanya melibatkan dequing kata berikutnya yang akan dieksekusi dan dalam kasus builtin, mengumpankan fungsi internal tumpukan data dan antrian panggilan sebagai argumen, atau dengan userdefs, mendorong kata-kata yang menyusunnya ke depan antrian.

Jadi jika kita memiliki fungsi untuk menggandakan elemen teratas:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Kemudian fungsi menulis +dan dupmemiliki tanda tangan jenis tumpukan / antrian berikut:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

Dan secara paradoks, doubleakan terlihat seperti ini:

double [X Y] -> [X dup^+^Y]

Jadi dalam arti tertentu, XY adalah stackless.