- Komputer awal harus mengimplementasikan pemanggilan fungsi tanpa stack dan heap, dan kompiler mengelola status pemanggilan dengan variabel global tersembunyi yang mewakili parameter, alamat pengembalian, dan variabel lokal
- Pemanggil menyimpan argumen, menaruh posisi kembali ke variabel alamat pengembalian, lalu melompat ke titik awal fungsi; setelah perhitungan selesai, fungsi melompat kembali ke alamat yang tersimpan
- Karena bahkan variabel lokal secara logis sebenarnya memakai ruang penyimpanan global, dari luar tampak seperti fungsi tetapi cara kerjanya di dalam lebih mirip memori tetap dan
goto - Beberapa ABI dan prosesor mengoptimalkan pengiriman argumen dan penanganan alamat kembali dengan register atau
branch with link, tetapi batasan dasarnya tetap ada - Karena alamat pengembalian untuk fungsi yang sama akan tertimpa oleh pemanggilan baru, pemanggilan rekursif tidak mungkin dilakukan, sehingga bahasa pada masa itu menanganinya dengan melarang rekursi atau hanya mengizinkannya secara eksplisit
Cara menyusun pemanggilan fungsi tanpa stack
- Di lingkungan komputer awal, stack atau heap yang hari ini dianggap wajar belum ada
- Alokasi memori dinamis tanpa heap bisa digantikan dengan buffer berukuran tetap
- Saat menangani data berukuran variabel pun, buffer tetap yang cukup besar dipesan lebih dulu
- Jika data yang diminta melebihi kapasitas buffer, program dihentikan dengan kesalahan fatal
- Implementasi yang lebih ramah memungkinkan kapasitas maksimum ditetapkan saat kompilasi
- Implementasi yang lebih canggih bisa menaruh allocator kustom di atas buffer tetap dan memakainya seperti
allocatedanfree
Konvensi pemanggilan berbasis variabel global tersembunyi
- Untuk mengimplementasikan pemanggilan fungsi tanpa stack, kompiler mendefinisikan beberapa variabel global tersembunyi untuk tiap fungsi
- Variabel global untuk setiap parameter input
- Variabel global yang menampung alamat pengembalian fungsi
- Variabel global yang mewakili variabel lokal
- Kode pemanggilan dijalankan dalam urutan berikut
- Menyimpan nilai parameter ke variabel global tersembunyi yang sesuai
- Mencatat posisi untuk kembali ke variabel alamat pengembalian milik fungsi
- Melompat dengan
gotoke lokasi awal fungsi
- Fungsi membaca dan menulis parameter maupun variabel lokal seluruhnya dari variabel global tersembunyi
- Setelah selesai, fungsi menaruh nilai balik ke register nilai balik lalu melompat ke alamat yang tersimpan dalam variabel alamat pengembalian fungsi
Contoh kode mirip C yang diubah menjadi kode berbasis goto
- Fungsi contoh
add_two_values(int a, int b)tanpa stack dapat diubah menjadi ruang penyimpanan seperti berikuta2v_a,a2v_badalah variabel global untuk menyimpan argumena2v_cadalah variabel global yang mewakili variabel lokalca2v_retaddradalah variabel global untuk menyimpan alamat kembali
- Pemanggil
sample()menyimpan31415dan2718masing-masing ke variabel global argumen - Lalu menaruh lokasi
resumekea2v_retaddrdan melompat keadd_two_values add_two_valuesmenyimpan hasil perhitungan kereturn_value_register, lalu kembali melaluia2v_retaddr- Pemanggil yang kembali ke lokasi
resumemenyimpan nilai dari register nilai balik kesample_x
Optimasi dengan register dan branch with link
- Struktur yang sama bisa dibuat lebih cepat di tingkat ABI dengan pengiriman melalui register
- Banyak prosesor menyediakan
link registerkhusus dan instruksibranch with linkbranch with linkotomatis menyimpan alamat instruksi setelah instruksi percabangan ke link register- Pemanggil dapat menaruh dua argumen pertama ke
argument_register_1,argument_register_2 - Fungsi yang dipanggil dapat memindahkan nilai register ini ke variabel global tersembunyi miliknya untuk dipakai
- Alamat pengembalian juga bisa disimpan dari
link_registerke variabel alamat pengembalian milik fungsi - Optimasi ini mempertahankan struktur dasar bahwa pemanggilan dan pengembalian tetap bisa dilakukan tanpa stack
Mengapa rekursi tidak bisa dilakukan
- Batasan utama dari cara pemanggilan ini adalah pemanggilan rekursif tidak didukung
- Jika rekursi terjadi, variabel alamat pengembalian milik fungsi yang sama akan tertimpa oleh alamat pengembalian dari pemanggilan baru
- Saat pemanggilan luar selesai, lokasi asli untuk kembali sudah hilang sehingga program akan melompat ke tempat yang salah
- Bahasa pemrograman pada masa itu menghindari masalah ini dengan tidak mendukung rekursi
- FORTRAN pada awalnya bahkan tidak mendukung subrutin, dan subrutin baru ditambahkan pada 1958
- Dukungan rekursi menjadi standar di FORTRAN pada 1991, dan bahkan saat itu subrutin harus dinyatakan sebagai
RECURSIVE
Self-modifying code dan instruksi subrutin pada prosesor awal
- Beberapa kompiler memakai self-modifying code dengan cara yang lebih cerdik
- Field alamat di dalam instruksi lompat pada akhir fungsi pada dasarnya berperan sebagai variabel alamat pengembalian
- Pendekatan ini bukan sekadar trik sederhana, melainkan bisa menjadi kebutuhan praktis
- Beberapa prosesor mungkin tidak mendukung lompatan tidak langsung
- Setelah kegunaan subrutin diakui, berbagai prosesor menambahkan instruksi pemanggilan khusus
- Alamat pengembalian disimpan pada word pertama subrutin
- Eksekusi sebenarnya dimulai dari word kedua
- Saat mengembalikan kontrol, dilakukan lompatan tidak langsung melalui label awal subrutin
- Dalam contoh assembly,
bsr add_two_valuesmenyimpan alamat pengembalian pada word pertamaadd_two_values, lalu mulai mengeksekusi instruksi sebenarnya setelahnoppengorbanan
1 komentar
Komentar Hacker News
Untuk topik ini, The Art of Computer Programming benar-benar bagus
Sekilas tampak usang, tetapi ada sangat banyak algoritma untuk menangani array atau struktur data yang berubah secara dinamis pada era sebelum heap atau stack
Buku ini berlanjut langkah demi langkah hingga garbage collection dan implementasi list Lisp, dengan pengetahuan ensiklopedis yang memang diharapkan dari Knuth
Contoh yang sangat saya suka adalah cara dua array berbagi satu ruang secara dinamis. Jika satu array tumbuh maju dari
location#0, dan array kedua tumbuh mundur darilocation#End, ruang yang dialokasikan secara statis dapat dibagi pakai secara efisienBisa juga diperluas ke jumlah array yang arbitrer, tetapi pada titik itu lebih baik memakai
MallocdanRealloc, dan tekniknya sendiri juga sudah cukup dekat dengan routine mirip mallocPenyisipan dan paste tidak perlu menggeser data, tetapi penelusuran perlu. Meski begitu, cara ini bekerja dengan baik
Jika tidak tersedia sebanyak itu, ukurannya dibuat lebih kecil dari preferensi; jika minimum pun tidak bisa didapat, eksekusi gagal
Seingat saya, sistem menempatkan heap dan library di bagian bawah potongan RAM fisik itu, dan stack di bagian atas
Sekitar System 8, lapisan virtualisasi ditambahkan sehingga pendekatan ini menjadi kurang diperlukan, dan pada masa MacOS X, seperti sistem lain, digunakan memori paging sehingga trik semacam ini tidak lagi diperlukan
Namun tetap menarik membayangkan bahwa “satu trik aneh” seperti ini dari Art of Computer Programming pernah menjadi cara alokasi RAM untuk beberapa aplikasi yang berjalan bersamaan
Yang satu tumbuh ke atas dan yang lain tumbuh ke bawah. Strukturnya memikat, tetapi pada akhirnya tidak menghasilkan performa yang dijanjikan
Di dalam halaman berukuran tetap, array offset tumbuh maju, sedangkan array nilai baris berpanjang variabel tumbuh mundur dari akhir. Sejauh yang saya pahami, ketika sebuah baris dihapus, array di belakang bisa menyisakan lubang
Dokumentasinya mengutip TAOCP untuk struktur B-tree itu sendiri, jadi tidak mengherankan jika ini merupakan inspirasi langsung
Memasukkan fungsi rekursif ke ALGOL cukup kontroversial, dan tetap menjadi kisah yang menarik: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - Oktober 2022, 8 komentar
How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - Mei 2020, 47 komentar
How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - Agustus 2015, 124 komentar
How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - Juli 2014, 108 komentar
Interpreter Forth untuk mesin SUBLEQ(https://github.com/howerj/subleq) dan interpreter untuk mesin bit-serial (https://github.com/howerj/bit-serial) pernah dibuat, dan keduanya tidak memiliki stack pemanggilan fungsi yang dibutuhkan Forth
SUBLEQ bahkan tidak mengizinkan indirect load/store, jadi untuk melakukan hal yang sedikit saja kompleks diperlukan kode yang memodifikasi dirinya sendiri
Pendekatannya adalah membuat mesin virtual yang bisa menjalankan fungsi semacam itu pada kedua mesin, lalu menambahkan cooperative multithreading juga
Jika butuh heap, tulis saja dalam Forth; kumpulan word floating-point juga ditulis dalam Forth. Banyak MCU masih tidak memiliki instruksi floating-point, dan hal itu bisa ditangani lewat pemanggilan fungsi software yang mengimplementasikannya
Compiler lain tidak disebutkan, tetapi sepertinya memakai pendekatan serupa. Beberapa interpreter BASIC juga mengimplementasikan VM lalu menargetkannya, dan P-Code pun mirip
Sebagian besar memori sistem dasarnya adalah RAM video, dan harus diakses melalui prosedur yang cukup merepotkan dengan
poke/peekregister chip videoChip video mempertahankan pointer memori saat ini yang auto-increment, sehingga saat membaca atau menulis berurutan pointer bertambah 1, tetapi fakta bahwa sebagian besar memori sistem hanya bisa diakses dengan cara seperti ini membuat penulisan program besar menjadi sulit
Karena itu TI membuat mesin abstrak bernama GPL agar akses ke RAM video ini terasa lebih alami. Namun karena dijalankan secara interpretatif di atas TMS9900, ia lebih lambat daripada kode native, dan akses CPU ke RAM chip video juga hanya bisa dilakukan saat chip tidak sedang melakukan scanout layar, seperti pada periode horizontal/vertical retrace, sehingga makin lambat
Kode dan variabel BASIC semuanya juga berada di memori video ini, jadi jelas interpreter BASIC TI-99/4A ditulis dengan apa. Sama sekali tidak cepat
Bagian yang menarik adalah TMS9900 tidak memiliki register general-purpose yang sebenarnya. Register workspace WR0~WR15 berada di suatu tempat di memori, dan register workspace pointer WP menunjuk ke sana
Register fisik CPU hanya tiga: PC, WP, dan status register. Akibatnya ia bisa melakukan register windowing yang sangat primitif; ketika bercabang dengan instruksi
BLWP, kumpulan “register” baru di lokasi memori lain menjadi aktif, dan alamat balik disimpan di workspace baruBelakangan ini saya sering membicarakan TI-99/4A karena saya sedang membuat assembler untuk mesin ini sebagai proyek pribadi
Pernyataan bahwa sebagian prosesor menyimpan alamat balik pada word tepat sebelum instruksi pertama subrutin itu benar, dan PDP-8 memang begitu
Evolusi PDP-8 juga bisa dilihat sebagai perjalanan dukungan hardware untuk rekursi
Awalnya instruksi
JMSmenanamkan alamat balik ke word pertama fungsi. Sering kali caller menaruh argumen setelah instruksiJMS, lalu callee membaca argumen dengan offset relatif terhadap instruksi return sambil menaikkannya setiap kali, sehingga alamat balik kembali menunjuk ke lokasi kodeSetelah itu, cukup umum membuat stack sederhana dengan memakai salah satu lokasi auto-increment. PDP-8 memiliki 8 lokasi memori yang bertambah setiap kali dipakai sebagai pointer, dan prolog/epilog fungsi mengelola stack ini sendiri sehingga memungkinkan rekursi penuh
Belakangan lagi, implementasi mikroprosesor seperti Harris 6120 menambahkan hardware stack sehingga performanya meningkat
R, yaitu instruksi penyimpanan alamat balikInstruksi ini menyimpan
PC+1yang sudah dinaikkan ke bagian alamat instruksi pada lokasi tujuan, dan secara konvensi tujuan itu adalah instruksi unconditional branch tepat sebelum awal subrutinSetelah instruksi
R, diletakkan instruksi unconditional branchUmenuju subrutin tersebutSubrutin kembali dengan bercabang ke alamat tepat sebelum dirinya, dan di sana terdapat unconditional branch yang kembali ke titik tepat setelah lokasi pemanggilan
Rekursi tidak mungkin dilakukan kecuali memakai calling convention yang lebih maju. Dan semua kode instruksi dalam bahasa assembly-nya hanya satu huruf
Dalam program yang ditulis untuk AVR-8, memakai calling convention C terkadang terasa seperti tindakan gila
Jika memakai assembly, variabel loop internal bisa terus disimpan di register file yang besar, atau bisa memakai cara-cara yang dijelaskan dalam tulisan
Pendekatan “mewarnai” fungsi dalam aplikasi seperti ini juga bagus. Jika kita tahu fungsi merah dan fungsi hijau tidak pernah aktif bersamaan, variabel lokal atau parameter keduanya bisa digunakan ulang
Dulu, dalam proyek codebase mikrokontroler yang saya ikuti, beberapa developer menghabiskan berminggu-minggu melacak bug yang sulit ditangkap di berbagai subsistem
Jika kode dipindahkan, bug ikut berpindah. Setelah menelusuri sedikit dan memasang jebakan, kami bisa menemukan lokasi-lokasi kode tempat call stack menjadi terlalu dalam hingga menimpa struktur data lain
Saat pertama belajar pemrograman, saya benar-benar dipaksa memprogram dengan cara seperti ini. Bukan pada 1970-an, melainkan pada 2001
Karena pengalaman pemrograman pertama saya adalah “bahasa” scripting semi-grafis yang disediakan oleh tool pengembangan game RPG Maker 2000
Kalau belum pernah melihat scripting RM2K, bayangkan campuran Scratch dan mode Emacs Paredit. Contoh: https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
Kelihatannya seperti teks, tapi tidak bisa diedit seperti teks; hanya bisa diedit sebagai blok dengan dialog properti
Tentu saja bahasa scripting RPG Maker tidak punya hal keren seperti stack. Kalau butuh subrutin yang bisa dipakai ulang, kita harus mengalokasikan variabel global rahasia untuk parameter, dan tidak ada reentrancy
Kalau dipikir lagi, rasanya kalau cukup keras kepala, kita bisa mengimplementasikan baik register maupun runtime stack di dalam RPG Maker 2000
Awalnya terlihat mudah. Kita bisa membuat “register” palsu seperti zero page pada 6502, dan membuat stack dengan akses variabel tidak langsung (https://rpgmaker.net/tutorials/523/)
Masalahnya, RM2K punya concurrency dalam bentuk skrip “parallel process”. Kalau abstraksi seperti ini dipakai oleh parallel process, “thread” yang berbeda akan saling menimpa state seenaknya
Jadi, untuk tiap “core virtual” diperlukan beberapa zero page dan stack, lalu harus mengalokasikan/mengikat/menjadwalkan core virtual ke setiap skrip paralel. Dengan kata lain, entah bagaimana setiap skrip harus punya stack pointer yang hanya diketahui dirinya sendiri
Agar stabil terhadap race condition, biasanya diperlukan sesuatu seperti mutex
Mengingat kegigihan para developer game RPG Maker, rasanya pasti ada orang yang menemukan cara mengakali salah satu fitur runtime agar berperilaku seperti mutex, tapi sejujurnya saya takut sampai tidak ingin tahu apa yang sebenarnya mereka lakukan
Saya ingat mengunduh game dari rpgmaker.net yang mengimplementasikan custom battle system. Itu adalah implementasi yang mengganti seluruh sistem pertarungan bawaan dengan teknik seperti yang Anda jelaskan
Saat saya membukanya di editor untuk melihat cara kerjanya, saya benar-benar kewalahan. Ada ratusan “variabel”, dan kalau ingatan saya benar hanya i64 yang diperbolehkan, juga ratusan “switch”. Switch itu boolean
Saat itu saya sama sekali belum mengenal konsep seperti stack, heap, atau function call
Saya bahkan tidak bisa membayangkan seberapa besar energi yang dibutuhkan untuk membuat, memelihara, dan men-debug itu
Kalau ingatan saya benar, saat menulis program BASIC di ZX81, saya menulisnya dengan cara yang mendekati “tanpa stack”
1 GOTO 3010 LET C = A + B20 RETURN30 LET A = 140 LET B = 250 GOSUB 1060 LET A = C70 LET B = 380 GOSUB 1090 PRINT CRUN6Dengan kata lain, saya melakukan sendiri pekerjaan yang dalam tulisan itu dilakukan oleh compiler. Nomor baris adalah alamat memori, dan variabel tersembunyi tidak tersembunyi bagi saya. Karena sayalah compilernya
Satu-satunya hal yang dilakukan interpreter adalah menyimpan alamat kembali dari
GOSUBNamun, kodenya mungkin salah secara sintaksis atau ingatan saya sudah terdistorsi. 40 tahun itu waktu yang panjang, tapi ide umumnya benar
Selain itu, prosesor Z80 di dalam mesin itu memang punya fungsi manajemen stack. Interpreter BASIC-nya benar-benar sederhana, tapi ada alasannya: hanya ada RAM 1KB dan ROM 8KB untuk OS, interpreter, dan semuanya
GOSUBmenyimpan nomor baris atau referensi lain yang akan dirujuk olehRETURN, dan jika pemanggilanGOSUBditumpuk, ia harus mengingat beberapa titik kembali, jadi dalam bentuk apa pun diperlukan stackHanya saja, beberapa BASIC tidak punya stack serbaguna, melainkan hanya array tetap untuk return pointer dan indeks posisi saat ini; misalnya kedalaman panggilan bisa saja dipatok 7. Dari sudut pandang programmer, itu berperilaku seperti call stack
Tentu saja itu bukan stack “yang benar” dengan variabel lokal/parameter seperti yang mungkin dibayangkan orang saat mendengar kata stack
Di lingkungan dasar BBC BASIC, ada demo menarik yang memperlihatkan apa yang terjadi saat pemanggilan bertingkat, termasuk rekursi. Jika posisi stack diarahkan ke bagian paling atas memori display dan area itu tidak digambari apa pun, kita bisa melihat stack tumbuh seiring pekerjaan berjalan
Karena resolusi layarnya rendah, alamat kembali 2 byte terlihat sebagai 8 piksel tebal di mode layar 1 atau 5. Di mode 2 jumlahnya 4 tetapi dengan warna berkedip sehingga kurang bagus, dan di mode 0, 3, 4, 6 jumlahnya 16, tetapi melihat per bit lebih sulit dikenali daripada pola berulang 8 warna
Sebelum ada heap yang bisa diperluas secara arbitrer, programmer setidaknya melakukan sedikit penilaian engineering
Karena mereka harus mempertimbangkan distribusi probabilistik input dan menentukan ukuran semua ruang penyimpanan perantara dengan tepat
Karena itulah muncul bagian “BUGS AND LIMITATIONS”
Jadi semuanya dialokasikan secara statis pada waktu kompilasi, dan kita harus tahu berapa banyak memori yang akan dikonsumsi input
Namun mengetahui batas atas konsumsi memori dulu juga merupakan hal normal bagi programmer aplikasi. Karena tidak ada yang ingin kehabisan memori
Sekarang saya bertanya-tanya apakah orang-orang hanya membiarkan penggunaan memori secara YOLO
Misalnya, itu peningkatan besar dibanding batasan seperti panjang maksimum perintah sed yang terbatas dan pendek
Karena sudah terlalu lama melakukan pemrograman fungsional, saya sungguh sulit membayangkan bagaimana menulis kode tanpa rekursi
Secara teknis saya tahu cara mengubah algoritma rekursif menjadi algoritma iteratif, dan pernah melakukannya di lingkungan dengan keterbatasan sumber daya besar, tetapi saya tidak menyukainya
Biasanya versi rekursif lebih elegan, dan menurut saya cukup cepat dalam 99% kasus. Jika compiler mendukung rekursi ekor, mendekati 100%, tetapi pada sebagian besar pekerjaan yang lebih menarik, pada akhirnya tetap harus memelihara stack sendiri
Kadang saya sengaja mengerjakan hal seperti itu untuk belajar bagaimana orang melakukannya sebelum saya lahir. Saya sesekali mengutak-atik game Commodore 64, dan itu membuat saya sangat merasakan betapa mewahnya kondisi sekarang, saat kita terbiasa dengan hardware yang cepat, murah, dan mudah dipakai
Untuk melakukan rekursi di mesin-mesin tua seperti itu, kita harus membuat mekanisme stack sendiri, dan tetap saja pada dasarnya tidak ada cara bawaan selain penyimpanan global, jadi masih ada masalah yang harus ditangani
Saya pernah hidup pada masa itu, tetapi tidak ingin merekomendasikannya kepada siapa pun
Pada fitur
@letdi Enhanced GNU Awk, blok@letdi luar fungsi, misalnya di dalam blokBEGINatauEND, dibuat agar compiler mengalokasikan variabel global rahasiaVariabel-variabel ini digunakan ulang sebisa mungkin di antara blok
$ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'$ cat awkvars.out$let0001: untyped variable$let0002: untyped variable$let0003: 1ARGC: 1ARGIND: 0ARGV: array, 1 elementsBINMODE: 0[ .. snip many ]https://www.kylheku.com/cgit/egawk/about/
pingtidak bisa, dannc -z 104.37.63.7 443juga tidak bisaPembaruan: sepertinya infrastruktur keamanannya rusak. Saya bahkan tidak tahu itu apa dan juga tidak menggunakan Twitter. Kalau mengecek AS-nya, itu Google Fiber
Dan saya harap tidak ada yang melakukan doxxing terhadap saya