Apakah tumpukan adalah satu-satunya cara yang masuk akal untuk menyusun program?

Sebagian besar arsitektur yang saya lihat mengandalkan tumpukan panggilan untuk menyimpan / mengembalikan konteks sebelum panggilan fungsi. Ini adalah paradigma umum yang mendorong operasi pop dan built-in untuk sebagian besar prosesor. Apakah ada sistem yang berfungsi tanpa tumpukan? Jika demikian, bagaimana cara kerjanya, dan untuk apa mereka digunakan?

Alternatif (agak) populer untuk tumpukan panggilan adalah lanjutan .

Parrot VM berbasiskan kelanjutan, misalnya. Ini sepenuhnya stackless: data disimpan dalam register (seperti Dalvik atau LuaVM, Parrot berbasis register), dan aliran kontrol diwakili dengan kelanjutan (tidak seperti Dalvik atau LuaVM, yang memiliki panggilan stack).

Struktur data populer lainnya, yang biasanya digunakan oleh Smalltalk dan Lisp VM adalah tumpukan spageti, yang seperti jaringan tumpukan.

Seperti @rwong tunjukkan , gaya kelanjutan-kelanjutan adalah alternatif dari tumpukan panggilan. Program yang ditulis dengan (atau ditransformasikan ke) gaya kelanjutan-lewat tidak pernah kembali, sehingga tidak perlu ada tumpukan.

Menjawab pertanyaan Anda dari perspektif yang berbeda: dimungkinkan untuk memiliki panggilan stack tanpa memiliki tumpukan terpisah, dengan mengalokasikan frame tumpukan di heap. Beberapa implementasi Lisp dan Skema melakukan ini.

Di masa lalu, prosesor tidak memiliki instruksi tumpukan, dan bahasa pemrograman tidak mendukung rekursi. Seiring waktu, semakin banyak bahasa memilih untuk mendukung rekursi, dan perangkat keras mengikuti paket dengan kemampuan alokasi bingkai tumpukan. Dukungan ini sangat bervariasi selama bertahun-tahun dengan prosesor yang berbeda. Beberapa prosesor mengadopsi stack frame dan / atau register stack pointer; beberapa instruksi yang diadopsi akan menyelesaikan alokasi frame tumpukan dalam satu instruksi.

Saat prosesor maju dengan level tunggal, lalu cache multi-level, satu keuntungan penting dari stack adalah lokalitas cache. Bagian atas tumpukan hampir selalu ada dalam cache. Setiap kali Anda dapat melakukan sesuatu yang memiliki tingkat hit cache yang besar, Anda berada di jalur yang benar dengan prosesor modern. Cache yang diterapkan ke tumpukan berarti bahwa variabel lokal, parameter, dll. Hampir selalu ada dalam cache, dan menikmati tingkat kinerja tertinggi.

Singkatnya, penggunaan stack berevolusi baik dalam perangkat keras maupun perangkat lunak. Ada model lain (misalnya komputasi aliran data dicoba untuk jangka waktu yang lama), namun, lokalitas tumpukan membuatnya berfungsi dengan sangat baik. Lebih lanjut, kode prosedural adalah apa yang prosesor inginkan, untuk kinerja: satu instruksi mengatakan apa yang harus dilakukan setelah yang lain. Ketika instruksi keluar dari urutan linier, prosesor melambat sangat, setidaknya sampai sekarang, karena kita belum menemukan cara untuk membuat akses acak secepat akses berurutan. (Btw, ada masalah serupa di setiap level memori, dari cache, ke memori utama, ke disk ...)

Antara kinerja yang ditunjukkan dari instruksi akses sekuensial dan perilaku cache yang menguntungkan dari tumpukan panggilan, kami memiliki, setidaknya saat ini, model kinerja yang unggul.

(Kami mungkin juga melemparkan keterputusan struktur data ke dalam karya ...)

Ini tidak berarti bahwa model pemrograman lain tidak dapat berfungsi, terutama ketika mereka dapat diterjemahkan ke dalam instruksi berurutan dan memanggil model tumpukan perangkat keras saat ini. Tetapi ada keuntungan berbeda untuk model yang mendukung di mana perangkat keras berada. Namun, hal-hal tidak selalu tetap sama, jadi kita bisa melihat perubahan di masa depan karena teknologi memori dan transistor yang berbeda memungkinkan untuk lebih paralelisme. Selalu ada olok-olok antara bahasa pemrograman dan kemampuan perangkat keras, jadi, kita akan lihat!

TL; DR

• Tumpukan panggilan sebagai mekanisme panggilan fungsi:
  1. Biasanya disimulasikan oleh perangkat keras tetapi tidak mendasar untuk pembangunan perangkat keras
  2. Sangat penting untuk pemrograman imperatif
  3. Tidak mendasar untuk pemrograman fungsional
• Stack sebagai abstraksi "last-in, first-out" (LIFO) adalah dasar untuk ilmu komputer, algoritma, dan bahkan beberapa domain non-teknis.
• Beberapa contoh organisasi program yang tidak menggunakan tumpukan panggilan:
  • Gaya kelanjutan-kelanjutan (CPS)
  • Mesin negara - perulangan raksasa, dengan segala yang disematkan. (Dimaksudkan untuk terinspirasi oleh arsitektur firmware Saab Gripen, dan dikaitkan dengan komunikasi oleh Henry Spencer dan direproduksi oleh John Carmack.) ^{(Catatan # 1)}
  • Arsitektur dataflow - jaringan aktor yang terhubung oleh antrian (FIFO). Antrian kadang-kadang disebut saluran.

Sisa dari jawaban ini adalah kumpulan pikiran dan anekdot yang acak, dan karenanya agak tidak teratur.

Tumpukan yang telah Anda gambarkan (sebagai mekanisme panggilan fungsi) khusus untuk pemrograman imperatif.

Di bawah pemrograman imperatif, Anda akan menemukan kode mesin. Kode mesin dapat meniru tumpukan panggilan dengan mengeksekusi urutan kecil instruksi.

Di bawah kode mesin, Anda akan menemukan perangkat keras yang bertanggung jawab untuk menjalankan perangkat lunak. Sementara mikroprosesor modern terlalu rumit untuk dijelaskan di sini, orang dapat membayangkan bahwa ada desain yang sangat sederhana yang lambat tetapi masih mampu mengeksekusi kode mesin yang sama. Desain yang begitu sederhana akan memanfaatkan elemen dasar dari logika digital:

1. Logika kombinasional, yaitu koneksi gerbang logika (dan, atau, tidak, ...) Perhatikan bahwa "logika kombinasional" tidak termasuk umpan balik.
2. Memori, yaitu sandal jepit, kait, register, SRAM, DRAM, dll.
3. Mesin negara yang terdiri dari beberapa logika kombinasi dan beberapa memori, cukup sehingga dapat mengimplementasikan "pengontrol" yang mengelola sisa perangkat keras.

Diskusi berikut berisi banyak contoh cara alternatif menyusun program penting.

• http://number-none.com/blow/john_carmack_on_inlined_code.html
• https://news.ycombinator.com/item?id=8374345

Struktur program seperti ini akan terlihat seperti ini:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Gaya ini akan sesuai untuk mikrokontroler, yaitu bagi mereka yang melihat perangkat lunak sebagai pendamping fungsi perangkat keras.

Tidak, belum tentu.

Membaca koran lama Appel's Garbage Collection bisa lebih cepat dari Stack Allocation . Ini menggunakan gaya kelanjutan lewat dan menunjukkan implementasi stackless.

Perhatikan juga bahwa arsitektur komputer lama (mis. IBM / 360 ) tidak memiliki register tumpukan perangkat keras. Tetapi OS dan kompiler memesan register untuk penunjuk tumpukan dengan konvensi (terkait dengan konvensi panggilan ) sehingga mereka dapat memiliki stack panggilan perangkat lunak .

Pada prinsipnya, seluruh kompiler C program dan optimizer dapat mendeteksi case (agak umum untuk embedded system) di mana grafik panggilan dikenal secara statis dan tanpa rekursi (atau pointer fungsi). Dalam sistem seperti itu, setiap fungsi dapat menyimpan alamat kembalinya di lokasi statis tetap (dan itulah cara Fortran77 bekerja di komputer era 1970).

Saat ini, prosesor juga memiliki tumpukan panggilan (dan instruksi panggilan & pengembalian mesin) yang mengetahui cache CPU .

Sejauh ini Anda sudah mendapat jawaban yang bagus; izinkan saya memberi Anda sebuah contoh yang tidak praktis tetapi sangat mendidik tentang bagaimana Anda bisa mendesain bahasa tanpa gagasan tumpukan atau "aliran kontrol" sama sekali. Berikut adalah program yang menentukan faktorial:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Kami menempatkan program ini dalam sebuah string, dan kami mengevaluasi program dengan substitusi teks. Jadi ketika kami mengevaluasi f(3), kami melakukan pencarian dan ganti dengan 3 untuk saya, seperti ini:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Bagus. Sekarang kita melakukan substitusi tekstual lain: kita melihat bahwa kondisi "jika" salah dan melakukan penggantian string lain, menghasilkan program:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Sekarang kita lakukan penggantian string lain pada semua sub-ekspresi yang melibatkan konstanta:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

Dan Anda lihat bagaimana ini terjadi; Saya tidak akan memaksakan poin lebih jauh. Kita bisa terus melakukan serangkaian pergantian string sampai kita let x = 6selesai dan kita akan selesai.

Kami menggunakan tumpukan secara tradisional untuk variabel lokal dan informasi lanjutan; ingat, tumpukan tidak memberi tahu Anda dari mana Anda berasal, itu memberi tahu Anda di mana Anda akan pergi berikutnya dengan nilai pengembalian di tangan.

Dalam model substitusi string pemrograman, tidak ada "variabel lokal" pada stack; parameter formal disubstitusikan untuk nilai-nilai mereka ketika fungsi diterapkan pada argumennya, daripada dimasukkan ke dalam tabel pencarian pada stack. Dan tidak ada "pergi ke suatu tempat berikutnya" karena evaluasi program hanya menerapkan aturan sederhana untuk substitusi string untuk menghasilkan program yang berbeda tetapi setara.

Sekarang, tentu saja, benar-benar melakukan pergantian string mungkin bukan cara yang tepat. Tetapi bahasa pemrograman yang mendukung "penalaran kesetaraan" (seperti Haskell) secara logis menggunakan teknik ini.

Sejak publikasi oleh Parnas pada tahun 1972 tentang kriteria yang akan digunakan dalam mendekomposisi sistem menjadi modul , telah diterima secara wajar bahwa menyembunyikan informasi dalam perangkat lunak adalah hal yang baik. Ini mengikuti debat panjang sepanjang 60-an tentang dekomposisi struktural dan pemrograman modular.

Modularitas

Hasil yang diperlukan dari hubungan black-box antara modul yang dilaksanakan oleh kelompok yang berbeda dalam sistem multi-threaded membutuhkan mekanisme untuk mengizinkan reentrancy dan sarana untuk melacak grafik panggilan dinamis sistem. Aliran eksekusi yang terkontrol harus melewati masuk dan keluar dari banyak modul.

Pelingkupan dinamis

Segera setelah pelingkupan leksikal tidak cukup untuk melacak perilaku dinamis, maka beberapa pembukuan runtime diperlukan untuk melacak perbedaannya.

Mengingat setiap utas (menurut definisi) hanya memiliki satu penunjuk instruksi saat ini, tumpukan LIFO sesuai untuk melacak setiap pemanggilan.

Pengecualian

Jadi, sementara model kelanjutan tidak mempertahankan struktur data secara eksplisit untuk stack, masih ada pemanggilan bersarang modul yang harus dipertahankan di suatu tempat!

Bahkan bahasa deklaratif mempertahankan riwayat evaluasi, atau sebaliknya meratakan rencana eksekusi untuk alasan kinerja dan mempertahankan kemajuan dengan cara lain.

Struktur loop tak berujung yang diidentifikasi oleh rwong adalah umum pada aplikasi dengan keandalan tinggi dengan penjadwalan statis yang melarang banyak struktur pemrograman umum tetapi menuntut agar seluruh aplikasi dianggap sebagai kotak putih tanpa menyembunyikan informasi yang signifikan.

Beberapa loop tak berujung bersamaan tidak memerlukan struktur apa pun untuk menahan alamat pengirim karena tidak memanggil fungsi, membuat pertanyaan dapat diperdebatkan. Jika mereka berkomunikasi menggunakan variabel bersama, maka ini dapat dengan mudah berubah menjadi analogi alamat pengirim gaya Fortran.

Semua mainframe lama (IBM System / 360) tidak memiliki gagasan stack sama sekali. Pada 260, misalnya, parameter dibangun di lokasi tetap dalam memori dan ketika subrutin dipanggil, itu disebut dengan R1menunjuk ke blok parameter dan R14berisi alamat pengirim. Rutin yang dipanggil, jika ingin memanggil subrutin lain, harus menyimpan R14di lokasi yang diketahui sebelum melakukan panggilan itu.

Ini jauh lebih dapat diandalkan daripada tumpukan karena semuanya dapat disimpan di lokasi memori tetap yang ditetapkan pada waktu kompilasi dan dapat dijamin 100% bahwa proses tidak akan pernah kehabisan tumpukan. Tidak ada "Alokasikan 1MB dan silangkan jari Anda" yang harus kita lakukan saat ini.

Panggilan subrutin rekursif diizinkan dalam PL / I dengan menentukan kata kunci RECURSIVE. Mereka berarti bahwa memori yang digunakan oleh subrutin secara dinamis daripada dialokasikan secara statis. Tapi panggilan rekursif jarang terjadi seperti sekarang.

Operasi tanpa tumpukan juga membuat multi-threading masif menjadi jauh lebih mudah, itulah sebabnya upaya sering dilakukan untuk membuat bahasa modern menjadi tidak bertali. Tidak ada alasan sama sekali, misalnya, mengapa kompiler C ++ tidak dapat dimodifikasi back-end untuk menggunakan memori yang dialokasikan secara dinamis daripada tumpukan.