Tags:
create new tag
view all tags
%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
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r2
<
r1
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r2 - 2002-08-28
-
AndreaSterbini
Log In
or
Register
Architetture2/MZ Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Prenotazioni esami
Laurea Triennale ...
Laurea Triennale
Algebra
Algoritmi
Introduzione agli algoritmi
Algoritmi 1
Algoritmi 2
Algoritmi per la
visualizzazione
Architetture
Prog. sist. digitali
Architetture 2
Basi di Dati
Basi di Dati 1 Inf.
Basi di Dati 1 T.I.
Basi di Dati (I modulo, A-L)
Basi di Dati (I modulo, M-Z)
Basi di Dati 2
Calcolo
Calcolo differenziale
Calcolo integrale
Calcolo delle Probabilitą
Metodi mat. per l'inf. (ex. Logica)
canale AD
canale PZ
Programmazione
Fond. di Programmazione
Metodologie di Programmazione
Prog. di sistemi multicore
Programmazione 2
AD
EO
PZ
Esercitazioni Prog. 2
Lab. Prog. AD
Lab. Prog. EO
Lab. Prog. 2
Prog. a Oggetti
Reti
Arch. di internet
Lab. di prog. di rete
Programmazione Web
Reti di elaboratori
Sistemi operativi
Sistemi Operativi (12 CFU)
Anni precedenti
Sistemi operativi 1
Sistemi operativi 2
Lab. SO 1
Lab. SO 2
Altri corsi
Automi, Calcolabilitą
e Complessitą
Apprendimento Automatico
Economia Aziendale
Elaborazione Immagini
Fisica 2
Grafica 3D
Informatica Giuridica
Laboratorio di Sistemi Interattivi
Linguaggi di Programmazione 3° anno Matematica
Linguaggi e Compilatori
Sistemi Informativi
Tecniche di Sicurezza dei Sistemi
ACSAI ...
ACSAI
Computer Architectures 1
Programming
Laurea Magistrale ...
Laurea Magistrale
Percorsi di studio
Corsi
Algoritmi Avanzati
Algoritmica
Algoritmi e Strutture Dati
Algoritmi per le reti
Architetture degli elaboratori 3
Architetture avanzate e parallele
Autonomous Networking
Big Data Computing
Business Intelligence
Calcolo Intensivo
Complessitą
Computer Systems and Programming
Concurrent Systems
Crittografia
Elaborazione del Linguaggio Naturale
Estrazione inf. dal web
Fisica 3
Gamification Lab
Information Systems
Ingegneria degli Algoritmi
Interazione Multi Modale
Metodi Formali per il Software
Methods in Computer Science Education: Analysis
Methods in Computer Science Education: Design
Prestazioni dei Sistemi di Rete
Prog. avanzata
Internet of Things
Sistemi Centrali
Reti Wireless
Sistemi Biometrici
Sistemi Distribuiti
Sistemi Informativi Geografici
Sistemi operativi 3
Tecniche di Sicurezza basate sui Linguaggi
Teoria della
Dimostrazione
Verifica del software
Visione artificiale
Attivitą complementari
Biologia Computazionale
Design and development of embedded systems for the Internet of Things
Lego Lab
Logic Programming
Pietre miliari della scienza
Prog. di processori multicore
Sistemi per l'interazione locale e remota
Laboratorio di Cyber-Security
Verifica e Validazione di Software Embedded
Altri Webs ...
Altri Webs
Dottorandi
Commissioni
Comm. Didattica
Comm. Didattica_r
Comm. Dottorato
Comm. Erasmus
Comm. Finanziamenti
Comm. Scientifica
Comm Scientifica_r
Corsi esterni
Sistemi Operativi (Matematica)
Perl e Bioperl
ECDL
Fondamenti 1
(NETTUNO)
Tecniche della Programmazione 1° modulo
(NETTUNO)
Seminars in Artificial Intelligence and Robotics: Natural Language Processing
Informatica generale
Primo canale
Secondo canale
II canale A.A. 10-11
Informatica
Informatica per Statistica
Laboratorio di Strumentazione Elettronica e Informatica
Progetti
Nemo
Quis
Remus
TWiki ...
TWiki
Tutto su TWiki
Users
Main
Sandbox
Home
Site map
AA web
AAP web
ACSAI web
AA2021 web
Programming web
AA2021 web
AN web
ASD web
Algebra web
AL web
AA1112 web
AA1213 web
AA1920 web
AA2021 web
MZ web
AA1112 web
AA1213 web
AA1112 web
AA1314 web
AA1415 web
AA1516 web
AA1617 web
AA1819 web
Old web
Algo_par_dis web
Algoreti web
More...
MZ Web
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
View
Raw View
Print version
Find backlinks
History
More topic actions
Edit
Raw edit
Attach file or image
Edit topic preference settings
Set new parent
More topic actions
Account
Log In
Register User
Questo sito usa cookies, usandolo ne accettate la presenza. (
CookiePolicy
)
Torna al
Dipartimento di Informatica
E
dit
A
ttach
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback