Sejarah Bahasa Pemrograman

Sebenarnya.. ini bukanlah hal yang gampang. Buktinya, lihat saja pada sejarah komputer. Diperlukan beberapa dekade sebelum bahasa pemrograman modern stabil. Yang pertama bisa dikatakan penting adalah Algol diciptakan pada tahun 1960. Algol stabil dalam subroutine linkage berbasis stack. Tapi tidak pernah cukup memuaskan.

Pascal (diciptakan pada tahun 1974) adalah sebuah momen penting. Dia menjadi begitu terkenal dan menggunakan ide subroutine berbasis stack ini (yang mana disebut procedure dan function). Bahasa pemrograman bisa diklasifikasikan sebagai "Sebelum Pascal" dan "Sesudah Pascal".

Tapi mari kita kembali ke MIPS processor (yang diciptakan 10 tahun setelah pascal).

Quest 10: apakah MIPS instruksi optimal untuk pemanggilan dan pengembalian subroutine?

Jawab: Yes

Rantai Aktivasi Linear (lurus)

Sebuah subroutine tertentu (katakanlah A) dapat memanggil subroutine lain dalam suksesi (misal B, kemudian X, kemudian Y, dan Z). Tapi dalam satu saat dia hanya bisa menautkan satu subroutine di bawahnya. Hampir di semua bahasa pemrograman modern pemanggilan subroutine adalah menggikuti konvensi berbasis stack ini. Subroutine yang sedang berjalan aktiv adalah berada di akhir sebuah rantai dari rantai aktivasi yang kembali ke operating sistem.

Run-time stack mempunyai bentuk yang sama dengan rantai aktivasi. Tumpukan stack teratas adalah untuk subroutine yang berjalan aktiv. Saat subroutine selesai maka data di stack pop out.

Stack adalah terakhi ditumpuk pertama dicabut

Subroutine adalah terakhir dipanggil pertama diselesaikan

Ketika subroutine mencapai akhir pekerjaannya, dia kembali ke caller, dan rantai pun memendek. Caller tadi mungkin memanggil lagi subroutine yang lain, dan rantai pun memanjang lagi.

Selama program memiliki banyak subroutine dieksekusi, rantai aktivasi ini akan memanjang dan memendek seperti yo-yo. Akhirnya rantai ini benar-benar habis, setelah program mengembalikan kontrol ke operating system.

Quest 9: apakah kamu merasa kalau otak kamu seperti yo-yo?

Sekumpulan Pemanggilan Subroutine

Diagram di bawah menunjukkan main routine terhubung ke subroutine A, yang mana dia terhubung ke subroutine B yang juga terhubung ke subroutine C. Subroutine-subroutine ini terhubung seperti kancing-kancing yang terhubung dengan 2 benang. Kontrol dilewatkan melalui call ke prolog, dan melalui epolog kembali ke caller. Semua subroutine yang tertaut seperti rantai mempunyai 5 bagian yang sama (call, prolog, body, epilog, gain kontrol) kecuali subroutine terakhir yang hanya menggunakan prolog dan epilog saja.

Tiap kali subroutine ditambahkan ke rantai, maka semakin banyak data yang ditumpuk ke dalam stack. Jika dilihat dari proses terpanjang, di akhir rantai stack menyimpan banyak data yang merupakan data dari tiap-tiap subroutine termasuk main. Subroutine yang sedang aktif adalah subroutine yang datanya berada di tumpukan ter atas dari stack (dalam kasus ini adalah subroutine C).

Setiap kali subroutine kembali ke caller maka setiap itu pula data di-pop out dari stack.

Setiap subroutine sama sekali tidak mengetahui apapun tentang stack selain stack nya sendiri. Dia bekerja menge-push data ke stack (yang merupakan data pendahulunya) kemudian meng-popnya kembali (agar bisa digunakan lagi oleh pendahulunya). Dia tidak bekerja menggunakan stack milik orang subroutine lain begitu juga dia tidak tahu berapa dalam level stack yang sedang terjadi sekarang.

Kadang kala orang menyebut "memanggil subroutine" dengan panggilan "mengaktivkan subroutine" Setiap-kancing-kancing yang ada di gambar dan tiap-tiap bagian dari stack adalah bersesuaian dengan sebuah pengaktivan subroutine.

Diagram

Aturan ini kelihatan rumit. Di bawah ini adalah gambar yang meunjukkan empat buah bagian subroutine linkage. Rangkuman tiap-tiap bagiannya adalah sebagai berikut:

Pemanggilan subroutine: Mengepush semua register T yang mungkin akan dipakai setelah memanggil subroutine. Letakkan argumen ke register A yang akan dipakai nilainya bersama-sama tetapi tidak berubah. Panggil subroutine dengan jal.

Prolog: Jika subroutine ini memanggil subroutine yang lain, tumpuk $ra. Tumpuk semua register S yang mungkin akan berubah di subroutine ini.

Body: normal code, kecuali dia harus mengikuti aturan konvensi jika dia memanggil subroutine yang lain. register T dan register A boleh digunakan secara bebas seperti halnya register S karena telah disimpan sebelumnya di saat prolog.

Epilog: Letakan nilai hasil ke register V. Pop register S. Pop $ra, kembali ke caller jr $ra

Kembalikan kontrol: Pop register T yang di awal telah di Push.

Quest 7: apakah ada batasan mengenai seberapa dalam level dari pemanggilan subroutine ini?
Jawab: No

Konvensi Linkage Berbasis Stack

Konvensi linkage sederhana bisa dirombak menjadi konvensi linkage berbasis stack. Ini bukanlah konvensi resmi. Bagaimanapun kamu bisa menggunakan konvensi ini untuk project kecil berbahasa assembly, karena cara ini belum begitu rumit dan hampir sudah cukup. Jika kamu ingin menautkan routine bahasa assembly ke program berbahasa C atau menggunakan routine sebagai library, maka kamu perlu menggunakan konvensi yang full resmi. (namun kamu belum bisa melakukan hal ini di SPIM). Berikut adalah aturan sederhananya:

Pemanggilan subroutine (dilakukan oleh caller):

1. Push ke dalam stack register $t0 - $t9 yang berisi nilai yang perlu disimpan. Takutnya subroutine mungkin akan mengubah nilai ini.
2. Letakkan nilai argument / nilai yang boleh dishare ke dalam $a0 - $a3
3. Penggil subroutine dengan intruksi jal

Subroutine prolog (dilakukan di awal-awal subroutine):

1. Jika subroutine mungkin memanggil subroutine yang lain, push $ra ke stack
2. Push ke dalam stack register yang ada di $s0 - $s7 ke dalam stack yang mungkin subroutine akan mengubahnya

Bagian tengah subroutine:

1. Subroutine boleh mengubah register T, register A atau register S.
2. Jika subroutine memanggil subroutine lainnya maka penyimpanan register ke stack akan dilakukan dengan cara yang sama

Subroutine epilog (dilakukan sesaat sebelum subroutine kembali ke callernya):

1. Letakkan nilai hasil ke $v0-$v1
2. Pop dari dalam stack dengan urutan kebalik register $s0 - $s7 yang sebelumnya di-push di prolog
3. Pop return address dari stack ke $ra
4. Kembali ke caller dengan instruksi jr $ra

Mengembalikan kontrol (dari subroutine, dilakukan oleh caller):

1. Pop dari stack (dalam urutan kebalik) register $t0 - $t9 yang sebelumnya telah di-push.

Untuk optimasi kecepatan, Beberapa subroutine ada yang menggunakan sedikit register untuk menyimpan nilai sementara. Mereka boleh menggunakan register T tanpa harus repot menyimpan dan merestore. Sebuah subroutine yang membutuhkan banyak sumber daya register atau memerlukan nilai itu di lewatkan ke subroutine lainnya mungkin akan menggunakan register S tapi mereka harus membayar kerepotan dalam menyimpan dan merestore ke dalam stack.

Menge-Push dan Menge-Pop Register

Berikut adalah aturannya: Jika sebuah subroutine diduga akan mengubah isi dari register S, dia pertama-tama harus menge-push nilai register ke stack. Sebelum kembali ke caller dia harus sudah menge-pop nilainya dari stack menuju ke asal registernya.

Berikut adalah contoh penggalan program. Subrotine subB memanggil subC yang mana menggunakan dua register S.

subB:
         sub    $sp,$sp,4    # push $ra
         sw     $ra,($sp)

         . . . .

         jal    subC         # call subC
         nop

         . . . .
         
         lw     $ra,($sp)    # pop return address
         add    $sp,$sp,4
         jr     $ra          # return to caller
         nop

# subC expects to use $s0 and $s1         
# subC does not call another subroutine
#       
subC:             
         sub    $sp,$sp,4    # push $s0
         sw     $s0,($sp)
         sub    $sp,$sp,4    # push $s1
         sw     $s1,($sp)

         . . . .             # statements using $s0 and $s1

         lw     $s1,($sp)    # pop s1
         add    $sp,$sp,4
         lw     $s0,($sp)    # pop s0
         add    $sp,$sp,4

         jr     $ra          # return to subB 
         nop       

The registers are popped in the opposite order that they were pushed.