Mengapa program menggunakan tumpukan panggilan, jika panggilan fungsi bersarang dapat diuraikan?

Mengapa tidak meminta kompiler mengambil program seperti ini:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

dan mengubahnya menjadi program seperti ini:

function c(b) { return b^2 + 5 };

dengan demikian menghilangkan kebutuhan komputer untuk mengingat alamat pengirim c (b)?

Saya kira peningkatan ruang hard disk dan RAM yang diperlukan untuk menyimpan program dan mendukung kompilasi (masing-masing) adalah alasan mengapa kami menggunakan tumpukan panggilan. Apakah itu benar?

Ini disebut "inlining" dan banyak kompiler melakukan ini sebagai strategi optimasi dalam kasus di mana masuk akal.

Dalam contoh khusus Anda, optimasi ini akan menghemat ruang dan waktu eksekusi. Tetapi jika fungsi dipanggil di banyak tempat dalam program (tidak jarang!), Itu akan meningkatkan ukuran kode, sehingga strategi menjadi lebih meragukan. (Dan tentu saja jika suatu fungsi menyebut dirinya secara langsung atau tidak langsung akan mustahil untuk sebaris, karena kode akan menjadi tak terbatas dalam ukuran.)

Dan jelas itu hanya mungkin untuk fungsi "pribadi". Fungsi yang diekspos untuk penelepon eksternal tidak dapat dioptimalkan, setidaknya tidak dalam bahasa dengan tautan dinamis.

Ada dua bagian untuk pertanyaan Anda: Mengapa memiliki beberapa fungsi sama sekali (alih-alih mengganti panggilan fungsi dengan definisi mereka) dan mengapa mengimplementasikan fungsi-fungsi itu dengan tumpukan panggilan alih-alih secara statis mengalokasikan data mereka di tempat lain?

Alasan pertama adalah rekursi. Bukan hanya jenis "oh, mari kita membuat panggilan fungsi baru untuk setiap item dalam daftar ini", juga jenis sederhana di mana Anda memiliki dua panggilan fungsi yang aktif secara bersamaan, dengan banyak fungsi lain di antaranya. Anda perlu meletakkan variabel lokal di tumpukan untuk mendukung ini, dan Anda tidak bisa sebaris fungsi rekursif secara umum.

Lalu ada masalah untuk pustaka: Anda tidak tahu fungsi mana yang akan dipanggil dari mana dan seberapa sering, jadi "pustaka" tidak pernah benar-benar dapat dikompilasi, hanya dikirimkan ke semua klien dalam beberapa format tingkat tinggi yang nyaman yang kemudian menjadi dimasukkan ke dalam aplikasi. Selain masalah lain dengan ini, Anda benar-benar kehilangan tautan dinamis dengan semua kelebihannya.

Selain itu, ada banyak alasan untuk tidak menjalankan fungsi bahkan ketika Anda bisa:

1. Ini belum tentu lebih cepat. Menyiapkan frame stack dan merobohkannya mungkin adalah selusin instruksi satu siklus, untuk banyak fungsi perulangan atau besar yang bahkan tidak 0,1% dari waktu eksekusi.
2. Mungkin lebih lambat. Duplikasi kode memiliki biaya, misalnya, akan lebih menekan cache instruksi.
3. Beberapa fungsi sangat besar dan dipanggil dari banyak tempat, membariskannya di mana-mana meningkatkan biner jauh melampaui apa yang masuk akal.
4. Kompiler sering mengalami kesulitan dengan fungsi yang sangat besar. Semuanya sama, fungsi ukuran 2 * N membutuhkan waktu lebih dari 2 * T di mana fungsi ukuran N membutuhkan waktu T.

Tumpukan memungkinkan kita untuk memotong batas yang diberlakukan oleh jumlah register yang terbatas secara elegan.

Bayangkan memiliki 26 global "register az" (atau bahkan hanya memiliki register berukuran 7 byte dari chip 8080) Dan setiap fungsi yang Anda tulis dalam aplikasi ini berbagi daftar datar ini.

Awal yang naif adalah mengalokasikan beberapa register pertama ke fungsi pertama, dan mengetahui bahwa hanya butuh 3, mulai dengan "d" untuk fungsi kedua ... Anda kehabisan dengan cepat.

Sebaliknya, jika Anda memiliki pita metaforis, seperti mesin turing, Anda dapat meminta setiap fungsi memulai "panggil fungsi lain" dengan menyimpan semua variabel yang digunakan dan meneruskan () rekaman itu, dan kemudian fungsi callee dapat mengacaukan sebanyak mungkin mendaftar sesuai keinginan. Ketika callee selesai, ia mengembalikan kontrol ke fungsi induknya, yang tahu di mana harus mengambil output callee sesuai kebutuhan, dan kemudian memutar kaset mundur untuk mengembalikan kondisinya.

Frame panggilan dasar Anda adalah hanya itu, dan dibuat dan dihapus oleh urutan kode mesin standar yang dimasukkan oleh kompiler di sekitar transisi dari satu fungsi ke fungsi lainnya. (Sudah lama sejak saya harus mengingat frame stack C saya, tetapi Anda dapat membaca tentang berbagai cara tugas siapa yang menjatuhkan apa yang ada di X86_calling_conventions .)

(rekursi itu luar biasa, tetapi jika Anda harus menyulap register tanpa tumpukan, maka Anda akan sangat menghargai tumpukan.)

Saya kira peningkatan ruang hard disk dan RAM yang diperlukan untuk menyimpan program dan mendukung kompilasi (masing-masing) adalah alasan mengapa kami menggunakan tumpukan panggilan. Apakah itu benar?

Meskipun kita dapat menyejajarkan lebih banyak hari-hari ini, ("lebih banyak kecepatan" selalu baik; "lebih sedikit kb rakitan" berarti sangat sedikit dalam dunia aliran video) Batasan utama adalah kemampuan kompiler untuk meratakan jenis pola kode tertentu.

Misalnya, objek polimorfik - jika Anda tidak tahu satu-satunya jenis objek yang akan Anda berikan, Anda tidak dapat meratakannya; Anda harus melihat vtable objek dari fitur dan memanggil melalui pointer itu ... sepele untuk dilakukan saat runtime, tidak mungkin untuk inline pada waktu kompilasi.

Toolchain modern dapat dengan senang hati menggarisbawahi fungsi yang terdefinisi secara polimorfik ketika ia telah meratakan cukup banyak pemanggil untuk mengetahui dengan pasti aroma obj yang mana:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

di atas, kompiler dapat memilih untuk tetap menggunakan inline statis, dari InlineMe melalui tindakan apa pun yang ada di dalam (), atau kebutuhan untuk menyentuh vtable apa pun saat runtime.

Tetapi setiap ketidakpastian dalam apa rasa objek akan meninggalkan sebagai panggilan ke fungsi diskrit, bahkan jika beberapa doa lain dari fungsi yang sama yang inline.

Kasus-kasus yang tidak dapat ditangani oleh pendekatan itu:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Ada yang bahasa dan platform dengan tumpukan terbatas atau tidak ada panggilan. Mikroprosesor PIC memiliki tumpukan perangkat keras yang dibatasi antara 2 dan 32 entri . Ini menciptakan kendala desain.

COBOL melarang rekursi: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

Memberlakukan larangan rekursi berarti Anda dapat mewakili seluruh kaligraf program secara statis sebagai DAG. Kompiler Anda kemudian dapat memancarkan satu salinan fungsi untuk setiap tempat dari mana ia dipanggil dengan lompatan tetap alih-alih pengembalian. Tidak diperlukan tumpukan, hanya lebih banyak ruang program, berpotensi cukup banyak untuk sistem yang kompleks. Tetapi untuk sistem tertanam kecil ini berarti Anda dapat menjamin untuk tidak memiliki stack overflow saat runtime, yang akan menjadi berita buruk bagi reaktor nuklir / turbin jet / kontrol throttle mobil Anda, dll.

Anda ingin fungsi inlining , dan kebanyakan kompiler ( mengoptimalkan ) melakukan itu.

Perhatikan bahwa inlining membutuhkan fungsi yang dipanggil untuk diketahui (dan efektif hanya jika fungsi yang dipanggil tidak terlalu besar), karena secara konseptual ia mengganti panggilan dengan menulis ulang fungsi yang disebut. Jadi, Anda biasanya tidak dapat menyejajarkan fungsi yang tidak diketahui (mis., Penunjuk fungsi -dan yang menyertakan fungsi dari pustaka bersama yang terhubung secara dinamis -, yang mungkin terlihat sebagai metode virtual dalam beberapa vtable ; tetapi beberapa kompiler kadang-kadang dapat mengoptimalkan melalui teknik devirtualisasi ). Tentu saja tidak selalu mungkin untuk inline fungsi rekursif (beberapa kompiler pintar mungkin menggunakan evaluasi parsial dan dalam beberapa kasus dapat inline fungsi rekursif).

Perhatikan juga inlining, meskipun mudah, tidak selalu efektif: Anda (sebenarnya kompiler Anda) dapat meningkatkan ukuran kode sedemikian rupa sehingga cache CPU (atau prediktor cabang ) bekerja kurang efisien, dan itu akan membuat program Anda berjalan lebih lambat.

^{Saya sedikit fokus pada gaya pemrograman fungsional , karena Anda menandai qestion Anda seperti itu.}

Perhatikan bahwa Anda tidak perlu memiliki tumpukan panggilan (setidaknya dalam arti mesin dari ekspresi "tumpukan panggilan"). Anda hanya bisa menggunakan heap.

Jadi, lihat kelanjutan dan baca lebih lanjut tentang kelanjutan gaya lewat (CPS) dan transformasi CPS (secara intuitif, Anda bisa menggunakan penutupan kelanjutan sebagai "bingkai panggilan" yang dialokasikan dialokasikan di tumpukan, dan mereka semacam meniru tumpukan panggilan; maka Anda membutuhkan pengumpul sampah yang efisien ).

Andrew Appel menulis buku Compiling with Continuations dan pengumpulan sampah kertas lama bisa lebih cepat daripada alokasi tumpukan . Lihat juga makalah A.Kennedy (ICFP2007) yang Mengompilasi dengan Lanjutan, Lanjutan

Saya juga merekomendasikan membaca buku Lisp In Small Pieces dari Queinnec , yang memiliki beberapa bab terkait dengan kelanjutan & kompilasi.

Perhatikan juga bahwa beberapa bahasa (mis. Brainfuck ) atau mesin abstrak (mis. OISC , RAM ) tidak memiliki fasilitas panggilan tetapi masih Turing-lengkap , jadi Anda tidak (secara teori) bahkan memerlukan mekanisme fungsi panggilan, bahkan jika ini sangat nyaman. BTW, beberapa arsitektur kumpulan instruksi lama (misalnya IBM / 370 ) bahkan tidak memiliki tumpukan panggilan perangkat keras, atau instruksi mesin panggilan yang mendorong (IBM / 370 hanya memiliki instruksi mesin Cabang dan Tautan )

Akhirnya, jika seluruh program Anda (termasuk semua perpustakaan yang dibutuhkan) tidak memiliki rekursi, Anda dapat menyimpan alamat pengirim (dan variabel "lokal", yang sebenarnya menjadi statis) dari setiap fungsi di lokasi statis. Kompiler Fortran77 lama melakukannya pada awal 1980-an (sehingga program yang dikompilasi tidak menggunakan tumpukan panggilan pada saat itu).

Inlining (mengganti panggilan fungsi dengan fungsi yang setara) berfungsi dengan baik sebagai strategi optimasi untuk fungsi-fungsi sederhana yang kecil. Overhead panggilan fungsi dapat secara efektif diperdagangkan dengan penalti kecil dalam ukuran program tambahan (atau dalam beberapa kasus, tidak ada penalti sama sekali).

Namun, fungsi-fungsi besar yang pada gilirannya memanggil fungsi-fungsi lain dapat menyebabkan ledakan besar dalam ukuran program jika semuanya diuraikan.

Inti dari fungsi yang dapat dipanggil adalah untuk memfasilitasi penggunaan kembali secara efisien, tidak hanya oleh programmer, tetapi oleh mesin itu sendiri, dan itu termasuk properti seperti memori yang masuk akal atau jejak pada disk.

Untuk apa nilainya: Anda dapat memiliki fungsi yang dapat dipanggil tanpa tumpukan panggilan. Sebagai contoh: IBM System / 360. Ketika pemrograman dalam bahasa seperti FORTRAN pada perangkat keras itu, penghitung program (alamat pengirim) akan disimpan ke dalam bagian kecil dari memori yang disediakan tepat di depan titik masuk fungsi. Hal ini memungkinkan untuk fungsi yang dapat digunakan kembali, tetapi tidak memungkinkan untuk rekursi atau kode multi-threaded (upaya pada panggilan rekursif atau masuk kembali akan menghasilkan alamat kembali yang disimpan sebelumnya ditimpa ditimpa).

Sebagaimana dijelaskan oleh jawaban lain, tumpukan adalah hal yang baik. Mereka memfasilitasi rekursi dan panggilan multi-utas. Sementara setiap algoritma yang dikodekan untuk menggunakan rekursi dapat dikodekan tanpa mengandalkan rekursi, hasilnya mungkin lebih kompleks, lebih sulit untuk dipelihara, dan mungkin kurang efisien. Saya tidak yakin arsitektur stack-less dapat mendukung multi-threading sama sekali.