La Ricorsione ... questa sconosciuta

Appunti sulla implementazione assembler delle procedure ricorsive e mutuamente ricorsive.

Una procedura è ricorsiva (o mutuamente) ricorsiva se nel corso della sua esecuzione richiama, direttamente (o indirettamente), se stessa.

Un esempio è l'implementazione ricorsiva della funzione fattoriale (definita per x>=0):

• fattoriale(x) = 1 se x=0
• fattoriale(x) = x * fattoriale(x-1) se x>0

Il problema chiave che dobbiamo risolvere nell'implementazione è:

• i registri usati per eseguire i calcoli verranno sovrascritti dalla chiamata ricorsiva della funzione

Esempio: usiamo il registro $t0 per contenere la variabile x, nell'esecuzione della procedura per calcolare fattoriale(5) accadrà:

1. il valore iniziale di $t0 è 5
2. la procedura calcola x-1 ed ottiene 4
3. lo mette nel registro $t0 e chiama se stessa per calcolare fattoriale(4)
4. per calcolare il risultato (5 * fattoriale(4)) si è ormai perso il valore iniziale (5) di x

Oltre alla perdita del valore x si assiste anche alla perdita del valore contenuto nel registro $ra (return address), che serve a completare la procedura tornando all'istruzione successiva a quella che l'ha chiamata.

Dato che la procedura chiama se stessa un gran numero di volte (nell'esempio pari al valore di x) non è pensabile di memorizzare i valori di x e di $ra negli altri registri (che sono pochi).

Abbiamo quindi bisogno di usare una struttura dati in memoria per memorizzare temporaneamente x e $ra.

La struttura dati di cui abbiamo bisogno è una stack (o pila):

• in cui i valori da memorizzare vengono inseriti uno ad uno
• e da cui vengono estratti in ordine inverso rispetto all'ordine di inserimento (LIFO=last in first out).

Per implementare una stack basta:

• una zona consecutiva di parole in memoria
• un registro che contiene l'indirizzo dell'ultimo elemento inserito (puntatore allo stack = Stack Pointer)

Le operazioni da compiere sulla stack saranno:

• push: inserimento di un elemento nella pila ed aggiornamento del puntatore
• pop: estrazione dell'ultimo elemento inserito nello stack ed aggiornamento del puntatore

Cosa dobbiamo inserire nella pila?

• sicuramente: il contenuto del registro $ra
• sicuramente: il contenuto dei registri di cui ci servirà il valore dopo aver effettuato la chiamata ricorsiva (nell'esempio la variabile x, ovvero il registro $t0)
• opzionalmente: tutti gli altri registri usati nella procedura

Salvare anche tutti gli altri registri usati nella procedura semplifica enormemente l'implementazione della procedura ed il suo uso nel programma principale, perchè evita l'introduzione di EffettiCollaterali difficili da controllare e da debuggare.

Per questo siete fortissimamente invitati a salvare TUTTI i registri modificati dalla procedura (tranne il valore del risultato, naturalmente).

Esempio passo passo

Vogliamo implementare le due funzioni mutuamente ricorsive:

• f(x) = x*g(x-1) se x>0
• f(x) = 42 altrimenti

• g(x) = x---+f(x-1) se x>0
• g(x) = 666 altrimenti

Si vede subito che sono mutuamente ricorsive perchè: f chiama g che chiama f che chiama g ...

In entrambe le funzioni usiamo:

• il registro $a0 per contenere la variabile x,
• il registro $sp (stack pointer) per puntare alla stack (che è già pronta in memoria e che cresce per valori di $sp decrescenti),
• il registro $v0 per tornare il risultato

Una prima implementazione (errata)

Una prima implementazione (sbagliata perchè non salva nessun valore su stack) potrebbe essere:

f:
   blez $a0, casobaseF
   sub $a0, 1         # calcolo x-1
   jal g              # calcolo g(x-1)
   mul $v0, $a0, $v0  # moltiplico il risultato di g(x-1) per x (ERRORE, oramai non ho più $a0)
   jr $ra             # torno alla procedura chiamante
casobaseF:
   li $v0, 42         # il risultato dev'essere f(x)=42
   jr $ra             # torno alla procedura chiamante

g:
   blez $a0, casobaseG
   sub $a0, 1         # calcolo x-1
   jal f              # calcolo f(x-1)
                      # tanto per cambiare decido di calcolare il risultato usando il registro $t0
   add $t0, $a0, $v0  # sommo il risultato di f(x-1) ad x (ERRORE, oramai non ho più $a0)
   move $v0, $t0      # metto il risultato nel registro $v0
   jr $ra             # torno alla procedura chiamante
casobaseG:
   li $v0, 666        # il risultato dev'essere g(x)=666
   jr $ra             # torno alla procedura chiamante

L'esempio sopra è utile perchè ci permette di capire quali registri dobbiamo salvare su stack:

• $ra (sempre)
• $a0 (obbligato) ne abbiamo bisogno dopo la chiamata ricorsiva sia di f che di g
• $t0 (opzionale) la procedura g lo modifica

Come si salvano i registri su stack (PUSH)

Per salvare i 3 registri su stack dobbiamo (push):

• decrementare lo stack pointer $sp di 12 (pari a 3 words)
• memorizzare i tre registri agli indirizzi 0, 4 ed 8 relativamente al valore dello $sp

   subu $sp, $sp, 12  # PRIMA: alloco 3 word sullo stack
   sw $ra, 0($sp)     # POI: inserisco $ra
   sw $a0, 4($sp)     #      inserisco $a0
   sw $t0, 8($sp)     #      inserisco $t0

Nota: è importante che la memorizzazione avvenga DOPO l'allocazione. In caso contrario se avvenisse una interruzione tra la memorizzazione dei valori e l'aggiornamento dello $sp i valori potrebbero essere sovrascritti.

Come si ripristinano i registri su stack (POP)

Per ripristinare i valori dei 3 registri da stack dobbiamo (pop):

• leggere i tre registri dagli indirizzi 0, 4 ed 8 relativamente al valore dello $sp
• incrementare lo stack pointer $sp di 12 (pari a 3 words)

   lw $ra, 0($sp)     # PRIMA: leggo $ra
   lw $a0, 4($sp)     #        leggo $a0
   lw $t0, 8($sp)     #        leggo $t0
   addi $sp, $sp, 12  # POI: rendo 3 word allo stack

Nota: è importante che la lettura avvenga PRIMA della disallocazione (sempre per evitare problemi con le interruzioni).

Implementazione corretta delle funzioni

Mettendo assieme il codice precedente otteniamo:

f:
   blez $a0, casobaseF

   subu $sp, $sp, 8   # PRIMA: alloco 2 word sullo stack
   sw $ra, 0($sp)     # POI: inserisco $ra
   sw $a0, 4($sp)     #      inserisco $a0

   sub $a0, 1         # calcolo x-1
   jal g              # calcolo g(x-1)
   mul $v0, $a0, $v0  # moltiplico il risultato di g(x-1) per x (ERRORE, oramai non ho più $a0)

   lw $ra, 0($sp)     # PRIMA: leggo $ra
   lw $a0, 4($sp)     #        leggo $a0
   addi $sp, $sp, 8   # POI: rendo 2 word allo stack

   jr $ra             # torno alla procedura chiamante

casobaseF:
   li $v0, 42         # il risultato dev'essere f(x)=42
   jr $ra             # torno alla procedura chiamante

g:
   blez $a0, casobaseG

   subu $sp, $sp, 12  # PRIMA: alloco 3 word sullo stack
   sw $ra, 0($sp)     # POI: inserisco $ra
   sw $a0, 4($sp)     #      inserisco $a0
   sw $t0, 8($sp)     #      inserisco $t0

   sub $a0, 1         # calcolo x-1
   jal f              # calcolo f(x-1)
                      # tanto per cambiare decido di calcolare il risultato usando il registro $t0
   add $t0, $a0, $v0  # sommo il risultato di f(x-1) ad x (ERRORE, oramai non ho più $a0)
   move $v0, $t0      # metto il risultato nel registro $v0

   lw $ra, 0($sp)     # PRIMA: leggo $ra
   lw $a0, 4($sp)     #        leggo $a0
   lw $t0, 8($sp)     #        leggo $t0
   addi $sp, $sp, 12  # POI: rendo 3 word allo stack



   jr $ra             # torno alla procedura chiamante

casobaseG:
   li $v0, 666        # il risultato dev'essere g(x)=666
   jr $ra             # torno alla procedura chiamante

NOTA: Potremmo scegliere di non salvare $t0 su stack e le nostre procedure funzionerebbero egregiamente MA in tal caso:

• la procedura g (e quindi anche la f che la chiama) avrebbe l'effetto collaterale di modificare il valore di $t0
• quindi ogni volta che usassimo f o g in un programma dovremmo ricordarci che $t0 perde il proprio valore
• dimenticarsene potrebbe essere fonte di errori difficili da rintracciare

Salvare anche $t0 ci semplifica la vita.

-- AndreaSterbini - 28 Aug 2002