LaRicorsioneQuestaSconosciuta < Architetture2/MZ

%TOC%
----
------++ 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
   1 la procedura calcola _x-1_ ed ottiene 4
   1 lo mette nel registro *$t0* e chiama se stessa per calcolare _fattoriale(4)_
   1 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
e
   * _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:
<verbatim>
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
</verbatim>

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*
<verbatim>
   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
</verbatim>

__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)
<verbatim>
   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
</verbatim>

__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:

<verbatim>
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
</verbatim>


__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.

-- Users.AndreaSterbini - 28 Aug 2002
This topic: Architetture2/MZ > WebHome > LaRicorsioneQuestaSconosciuta
Topic revision: r2 - 2002-08-28 - AndreaSterbini