Pemanggilan Subrutin di Dunia Kuno: Sebelum Komputer Memiliki Stack atau Heap

Pemanggilan subrutin pada masa kuno ketika komputer belum memiliki stack dan heap

• Dalam komputasi modern, kita menganggap stack dan heap sebagai sesuatu yang wajar, tetapi pada masa awal komputasi, komputer beroperasi tanpa stack maupun heap.
• Tidak terlalu sulit membayangkan komputasi tanpa alokasi memori dinamis. Anda harus menggunakan buffer memori berukuran tetap untuk semuanya.
• Jika perlu menangani data berukuran variabel, Anda mencadangkan buffer berukuran tetap yang cukup besar untuk menampung data yang dapat diperkirakan.
• Anda bisa menyediakan pengaturan saat waktu kompilasi agar klien dapat menyesuaikan kapasitas maksimum, atau menulis allocator kustom yang dapat "mengalokasikan" dan "membebaskan" memori dari buffer berukuran tetap.

Memanggil fungsi tanpa stack

• Kompiler mendefinisikan variabel global rahasia untuk parameter masuk, alamat pengembalian, dan variabel lokal tiap fungsi.
• Untuk menghasilkan pemanggilan fungsi, kompiler menetapkan nilai parameter ke variabel global rahasia terkait, menetapkan alamat pengembalian ke "variabel alamat pengembalian" rahasia milik fungsi, lalu melompat ke awal fungsi.
• Fungsi membaca parameter dari variabel global rahasia dan menggunakan variabel global rahasia yang telah ditentukan sebelumnya yang secara logis setara dengan variabel lokal.
• Saat fungsi selesai, ia melompat ke alamat yang ada di "variabel alamat pengembalian" rahasia milik fungsi.

Optimasi ABI

• Untuk mengoptimalkan ABI, sebagian nilai diteruskan melalui register alih-alih variabel global.
• Sebagian besar prosesor memiliki register "link" dan instruksi "branch with link", yang secara otomatis menetapkan register link ke alamat setelah instruksi "branch with link".
• Konvensi pemanggilan dioptimalkan dengan meneruskan dua parameter pertama melalui register.

Ketidakmungkinan pemanggilan rekursif

• Pemanggilan rekursif tidak berfungsi. Pemanggilan rekursif menimpa variabel alamat pengembalian dengan alamat pengembalian milik pemanggilan rekursif, sehingga saat pemanggilan luar selesai, eksekusi melompat ke lokasi yang salah.
• Bahasa pemrograman pada masa itu menyelesaikan masalah ini dengan menyatakan bahwa rekursi tidak didukung.

Percakapan bonus

• Beberapa kompiler bekerja lebih licik dengan menggunakan self-modifying code: variabel alamat pengembalian khusus itu sebenarnya adalah field alamat dari instruksi jump di akhir fungsi.
• Jika prosesor tidak mendukung indirect jump, metode ini digunakan sebagai kebutuhan praktis.
• Setelah nilai praktis subrutin diakui, banyak prosesor menambahkan instruksi pemanggilan subrutin yang menyimpan alamat pengembalian di kata pertama subrutin, lalu memulai eksekusi dari kata kedua subrutin.
• Untuk kembali dari subrutin, dilakukan indirect jump melalui label awal subrutin.

Pendapat GN⁺

• Artikel ini membantu memahami perkembangan teknik manajemen memori yang digunakan dalam pengembangan perangkat lunak modern dengan menjelaskan cara pemrograman pada masa awal komputasi ketika stack dan heap belum ada.
• Cara pemrograman pada masa tanpa stack dan heap mungkin terasa sangat asing dan tidak efisien bagi pengembang modern, tetapi ini memberikan pengetahuan latar yang penting untuk memahami bagaimana teknologi berkembang sepanjang sejarah komputasi.
• Batasan pemrograman pada masa ketika pemanggilan rekursif tidak dimungkinkan memberikan fakta sejarah yang menarik bagi pengembang yang saat ini menggunakan algoritma rekursif.
• Dari sudut pandang kritis, pendekatan pemrograman awal ini menunjukkan bahwa metode tersebut sangat terbatas untuk memenuhi kebutuhan modern yang kompleks dan beragam.

[GN⁺]

Komentar Hacker News

• Penilaian positif terhadap buku "The Art of Computer Programming"

  • Buku ini memang terlihat tua, tetapi membahas berbagai algoritma untuk memodifikasi array dinamis maupun struktur data dari masa sebelum heap dan stack.
  • Buku ini juga menjelaskan garbage collection dan implementasi daftar Lisp, serta memberikan pengetahuan ensiklopedis yang membuat orang menaruh harapan pada Knuth.

• Penjelasan tentang cara dua array berbagi satu ruang secara dinamis

  • Satu array tumbuh normal dari posisi #0, sementara yang lain tumbuh terbalik dari posisi #End, sehingga keduanya dapat berbagi ruang yang dialokasikan secara statis dengan efisien.
  • Metode ini bisa diperluas ke beberapa array, tetapi pada titik itu mungkin lebih baik menggunakan Malloc dan Realloc.

• Membagikan tautan ke kisah menarik tentang bagaimana memperkenalkan fungsi rekursif ke bahasa ALGOL sempat menjadi hal yang kontroversial

  • Tautan tersebut membagikan kisah dengan sejarah menarik tentang bagaimana rekursi diperkenalkan ke dalam bahasa pemrograman.

• Berbagi pengalaman menulis interpreter Forth untuk mesin SUBLEQ dan mesin bit-serial

  • Kedua mesin ini tidak memiliki stack pemanggilan fungsi yang merupakan elemen penting Forth.
  • SUBLEQ tidak mengizinkan pemuatan dan penyimpanan tidak langsung, sehingga membutuhkan self-modifying code untuk melakukan pekerjaan yang tidak lazim.
  • Mereka membangun mesin virtual untuk menjalankan fungsi-fungsi tersebut, dan mendukung cooperative multithreading.
  • Jika diperlukan, heap ditulis dalam Forth, dan juga mencakup operasi floating-point yang diimplementasikan sebagai fungsi perangkat lunak.

• Penjelasan tentang evolusi teknis terkait pemanggilan subrutin pada prosesor PDP-8

  • Pada awalnya, instruksi JMS menyimpan alamat pengembalian di word pertama fungsi.
  • Setelah itu, lokasi auto-increment digunakan untuk membuat stack sederhana, dan prolog/epilog fungsi mengelola stack ini secara manual sehingga rekursi penuh menjadi mungkin.
  • Belakangan, stack perangkat keras ditambahkan ke implementasi mikroprosesor untuk meningkatkan performa.

• Berbagi preferensi terhadap rekursi dari seorang pengguna yang sudah lama berpengalaman dengan pemrograman fungsional

  • Ia tahu cara mengubah algoritma rekursif menjadi algoritma iteratif, tetapi tetap lebih menyukai rekursi.
  • Dalam kebanyakan kasus, rekursi cukup cepat, terlebih lagi jika kompiler mendukung tail recursion.
  • Saat mengutak-atik game Commodore 64, ia berusaha mempelajari bagaimana pemrograman dilakukan pada masa lalu.

• Berbagi pengalaman merancang multiplexer serial RS232 sekitar tahun 1991

  • Rancangan perangkat keras menggunakan prosesor Z80, EPROM, dan perangkat serial Z80-SIO.
  • Karena tidak ada stack, mereka menggunakan metode memuat lebih dulu alamat pengembalian ke pasangan register untuk pemanggilan fungsi.

• Menyebut situasi masa lalu ketika, sebelum heap dapat diperluas, para programmer harus mempertimbangkan distribusi kemungkinan input dan menetapkan ukuran penyimpanan sementara secara tepat

  • Hal ini menyebabkan munculnya "bug dan keterbatasan".

• Penjelasan bahwa pada masa ketika rekursi tidak bisa digunakan, tail recursion tetap memungkinkan

  • Selain branch_with_link yang dipakai pada pemanggilan awal, cabang biasa harus digunakan.

• Penjelasan tentang cara kompiler di Enhanced GNU Awk mengalokasikan variabel global rahasia untuk blok @let yang berada di luar fungsi

  • Variabel-variabel ini digunakan ulang sebanyak mungkin.

• Menyebut sebuah post yang menggambarkan dunia dari makalah "Goto considered harmful"

  • Kebanyakan orang hanya tahu judulnya, padahal makalah itu berargumen tentang penyediaan satu titik masuk untuk subrutin.
  • Terkadang orang menulis kode assembly agar melompat ke subrutin lain, tetapi mereka tidak ingin semua kode assembly menjadi seperti itu.