Sklad

Stroj SIC/XE nima ukazov za delo z skladom.

• Zakaj sklad (nujno) potrebujemo?
• Kje se shrani naslov ob izvedbi ukaza JSUB, na katerega s vrnemo iz rutine z ukazom RSUB?
• Kako bi v SIC/XE implementirati neko rekurzivno rutino?
• Kako višji programski jeziki navadno prevedejo klice funkcij? Kako prenašajo parametre?

Navadno je delo s skladom v zbirniku podprto z ukazi PUSH / POP za dodajanje in odvzemanje registrov na/s sklad/a. Tako bi v SIC/XE potrebovali rutine, kot so:

PUSHA, POPA, PUSHS, POPS, PUSHL, POPL

Bi znali implementirati take rutine? Kakšna bi bila razlika med PUSHA in PUSHL – v čem je težava s PUSHL? Za kakšne vrste rutin nujno potrebujemo PUSHL in POPL?

Implementacija

Pisanje vseh zgornjih rutin bi bilo precej duhamorno in morda sploh ne potrebujemo vseh. Zato bomo izziv malce poenostavili in shranjevanje na sklad razbili v dve podoperaciji: kopiranje registra na sklad in povečevanje/zmanševanje kazalca na sklad.

Za implementacijo sklada potrebujemo kazalec na vrh sklada stackptr, ki naj kaže na prvo nezasedeno besedo sklada. Namesto kopice rutin bomo raje implementirali le dve: za povečevanje in zmanjševanje kazalca na vrh sklada. Registre pa bomo pred oz. po uporabi teh rutin sami ročno zapisali/prebrali iz sklada.

Porivanje na sklad bomo torej izvedli z dvema ukazoma. Operacijo „PUSHA“ bomo izvedli tako:

STA   @stackptr    . na vrh sklada zapišemo A
JSUB   stackpush   . povečamo kazalec na vrh sklada

Vsakemu PUSHu mora nekje v programu slediti ustrezen POP, npr. „POPA“ bo zgledal takole:

JSUB   stackpop    . zmanjšamo kazalec na vrh sklada
LDA   @stackptr    . z vrha sklada preberemo A

Napišite program stack.asm, v katerem implementirate naslednje tri rutine:

• stackinit: inicializira kazalec stackptr glede na nek rezerviran kos pomnilnika;
• stackpush: poveča kazalec na vrh sklada; in
• stackpop: zmanjša kazalec na vrh sklada.

Ne pozabite tudi rezervirati prostora za sklad.

Fakulteta

S pomočjo rutin iz predhodne naloge napišite rekurzivno rutino za izračun fakultete (n!). Število n prenesete v registru A, v katerem naj rutina tudi vrne rezultat.

• S pomočjo rutin za izpis iz prejšnjih vaj izpišite n! za nekaj števil.
• Za vajo fakulteto napišite rekurzivno, seveda pa je precej učinkovitejša iterativna različica. Lahko napišete še to.

★ Hanojski stolpi

Kateri računalničar ne pozna uganke Hanojski stolpi? S pomočjo rutin za delo s skladom in rutin za izpis napišite program hanoi, ki izpiše rešitev uganke. Rešitev je zaporedje potez, npr. A>B, ki so potrebne za prestavitev vseh obročev s stolpa A na stolp C.

V splošnem rekurzivni korak izgleda tako (1 označuje začetni, 2 končni in 3 vmesni stolp):

1. Prestavi n−1 obročev s stolpa 1 na 3 (preko 2).
2. Prestavi en obroč s stolpa 1 na 2.
3. Prestavi n−1 obročev s stolpa 3 na 2 (preko 1).

Rekurzivna rutina naj število obročev n dobi v registru A. V registru S pa hranimo konfiguracijo stolpov – za vsak stolp en bajt. Npr. ACB je začetna konfiguracija: premikamo iz A na C preko B. Po želji lahko program dopolnite, da začetno število diskov na obroču prebere iz naprave.