Ricorsione.... vorrei "capirci" qualcosa...:-)
Antonio Mazzeo
<sil...@bluecodes.com> wrote:
>Mi piacerebbe sentire il vostro parere sulla questione, e magari, avere una
>"spiegazione" (anche a livello di SO), del perche'....
>
>Grazie a chiunque abbia avuto la pazienza di leggere il POST, mi scuso per
>l'eccessiva lunghezza del messaggio... ma non volevo tralasciare dettagli
>che ritenevo importanti...
Sia in C che in C++ (e di conseguenza anche in Assembler, visto che il
listato e' ottenuto da un programma C) i dati sono inseriti nello
stack da destra a sinistra..
Avendo usato tu la ricorsione, e com secondo parametro di ricorsione
il risultato di una CHIAMATA, e' indispensabile chiamare la funzione
per poter ottenere il 2' parametro con il quale eseguire la
moltiplicazione.
Questo implica una chiamata ricorsiva sino al punto in cui non sara'
effettuata un'altra chiamata ricorsiva (nel tuo caso forse 24.. non ho
letto attentamente i listati). Nel caso in cui non ci sarebbe un
limite alle chiamate ricorsive.. otteresti uno stack overflow dopo un
bel po' di chiamate...
Se ti documenti sui vari tipi di chiamata (stdcall usato nel C)
troverai queste semplici informazioni
antonio
p.s. avresti ottenuto lo stesso risultato in un qualunque strumento di
sviluppo che usa questo standard di chiamate
HappyCactus
sil...@bluecodes.com says...
> .globl igamma
> .type igamma,@function
> igamma:
> pushl %ebp
> movl %esp, %ebp
> cmpl $0, 8(%ebp)
if (n != 0)
Vai a L3
> jne .L3
> movl $1, %eax
> jmp .L2
else
rv = 1;
salta a L2
> .L3:
...
> imull %edx, %eax
L3: a = igamma (n-1)
rv = n * a
> .L2:
> movl %ebp, %esp
> popl %ebp
> ret
return rv
fine.
Non vedo il problema: mi pare assolutamente lineare, chiaro, sintetico.
--
HappyCactus - Linux User #209744 - LFS User #6046 - >>> SMSPM950 <<<
Ci sono 10 categorie di persone al mondo: quelle che capiscono
il sistema binario e quelle che non lo capiscono.
Silvio Mazzaro
> if (n != 0)
> Vai a L3
>
>> jne .L3
>
>> movl $1, %eax
>> jmp .L2
>
> else
> rv = 1;
> salta a L2
>
>> .L3:
> ...
>> imull %edx, %eax
>
> L3: a = igamma (n-1)
> rv = n * a
>
>> .L2:
>> movl %ebp, %esp
>> popl %ebp
>> ret
> Non vedo il problema: mi pare assolutamente lineare, chiaro, sintetico.
Prima della "imull" c'e' comunque la "call" ad igamma! Segui bene il
flusso...
Salva i framepointers, confronta 4 (l'argomento) con 0, se non e' zero,
decrementa %eax, salvalo, richiama igamma.... riesegue gli stessi passi...
ora c'e' 3... poi 2... alla fine c'e' 1 e viene fatta la jump su .L2! ;-)
Dove viene eseguita la moltiplicazione? Seguendo il flusso non si vede....
A presto,
Silvio
Silvio Mazzaro
> Sia in C che in C++ (e di conseguenza anche in Assembler, visto che il
> listato e' ottenuto da un programma C) i dati sono inseriti nello
> stack da destra a sinistra..
Quindi...
call igamma
addl $16, %esp
movl %eax, %edx
movl 8(%ebp), %eax
imull %edx, %eax
Verrebbe eseguita in ordine inverso?
> Avendo usato tu la ricorsione, e com secondo parametro di ricorsione
> il risultato di una CHIAMATA, e' indispensabile chiamare la funzione
> per poter ottenere il 2' parametro con il quale eseguire la
> moltiplicazione.
Si, si... questo e' visibilissimo dal codice C... il mio problema... era
seguire, "correttamente" il flusso del programma....
> Questo implica una chiamata ricorsiva sino al punto in cui non sara'
> effettuata un'altra chiamata ricorsiva (nel tuo caso forse 24.. non ho
> letto attentamente i listati).
Ecco... avresti dovuto. :-)
Grazie comunque,
Silvio
Francesco
che dovresti leggere. Non ricordo gli autori.
Saluti,
Francesco
"Silvio Mazzaro" <sil...@bluecodes.com> ha scritto nel messaggio
news:Aa4k9.6909$Eu.1...@twister1.libero.it...
> Ciao a tutti!
>
> In questi giorni, mi sto dilettando "pesantemente" con il Prolog ed il
> Lisp... visto che entrambi fanno largo uso della Ricorsione... mi sono
> detto:
>
> "Beh, per quanto affascinante possa essere, quello che ho in quello
> scatolotto sotto al tavolo, e' pur sempre una "stack machine"... quindi
> vediamo bene di vedere cosa succede a livello, "basso" " :-)
>
> Senza smontare lo SWI-Prolog... ho abbozzato una sciocchezza in C del
tipo:
>
> [kirk@enterprise Code]$ cat igammaric.c
>
> #include <stdio.h>
>
> int igamma (int n)
> {
> if (n==0)
> return (1);
> else
> return (n=n*igamma(n-1));
> }
>
> int main()
> {
> printf("%i\n",igamma(4));
> exit(0);
> }
>
> Il cui risultato e' ovviamente 24... ;-) (Notate la scoattata, l'ho
chiamata
> Integer Gamma... i matematici capiranno...)
>
> Stoppando il gcc alla fase di assemblaggio, ripulendo un po il codice, ho
> ottenuto questo:
>
> [kirk@enterprise Code]$ cat igammaric.s
>
> .globl igamma
> .type igamma,@function
> igamma:
> pushl %ebp
> movl %esp, %ebp
> cmpl $0, 8(%ebp)
> jne .L3
> movl $1, %eax
> jmp .L2
> .L3:
> subl $12, %esp
> movl 8(%ebp), %eax
> decl %eax
> pushl %eax
> call igamma
> addl $16, %esp
> movl %eax, %edx
> movl 8(%ebp), %eax
> imull %edx, %eax
> .L2:
> movl %ebp, %esp
> popl %ebp
> ret
> .LC0:
> .string "%i\n"
>
> .globl main
> .type main,@function
> main:
> pushl %ebp
> movl %esp, %ebp
> subl $20, %esp
> pushl $4
> call igamma
> addl $8, %esp
> pushl %eax
> pushl $.LC0
> call printf
> movl %ebp, %esp
> popl %ebp
> ret
>
> Provate a seguire il flusso del programma e... beh, devo dire che c'ho
messo
> un po a capire (anzi, non credo di averlo capito...) come diavolo potesse
> eseguire la "imull" il processore, decrementando (come e' giusto che sia),
> il
> valore di %eax ad ogni cilclo, alla fine di tutto, c'e' quella bellissima
> jump, che a "colpo" d'occhio, sembra non far eseguire la
moltiplicazione...
> ma.... a colpi di gdb, "qualcosa" si vede...
>
> Questo e' uno scriptino che mi sono fatto, per lavorare tranquillamente
sui
> miei listati... solo che la "list" restituisce l'ASM e non il C... ;-)
>
> [kirk@enterprise Code]$ cat /usr/local/bin/linka
> #!/bin/sh
> as -a --gstabs $1.s -o $1.o
> ld -m elf_i386 -dynamic-linker /lib/ld-linux.so.2 /usr/lib/crt1.o
> /usr/lib/crti.o /usr/lib/crtn.o -lc $1.o -o $1
>
> E quindi con un...
>
> [kirk@enterprise Code]$ linka igammaric
> GAS LISTING igammaric.s page 1
>
>
> 1 .globl igamma
> 2 .type igamma,@function
> 3 igamma:
> 4 0000 55 pushl %ebp
> 5 0001 89E5 movl %esp, %ebp
> 6 0003 837D0800 cmpl $0, 8(%ebp)
> 7 0007 7507 jne .L3
> 8 0009 B8010000 movl $1, %eax
> 8 00
> 9 000e EB18 jmp .L2
> 10 .L3:
> 11 0010 83EC0C subl $12, %esp
> 12 0013 8B4508 movl 8(%ebp), %eax
> 13 0016 48 decl %eax
> 14 0017 50 pushl %eax
> 15 0018 E8FCFFFF call igamma
> 15 FF
> 16 001d 83C410 addl $16, %esp
> 17 0020 89C2 movl %eax, %edx
> 18 0022 8B4508 movl 8(%ebp), %eax
> 19 0025 0FAFC2 imull %edx, %eax
> 20 .L2:
> 21 0028 89EC movl %ebp, %esp
> 22 002a 5D popl %ebp
> 23 002b C3 ret
> 24 .LC0:
> 25 002c 25690A00 .string "%i\n"
> 26
> 27 .globl main
> 28 .type main,@function
> 29 main:
> 30 0030 55 pushl %ebp
> 31 0031 89E5 movl %esp, %ebp
> 32 0033 83EC14 subl $20, %esp
> 33 0036 6A04 pushl $4
> 34 0038 E8FCFFFF call igamma
> 34 FF
> 35 003d 83C408 addl $8, %esp
> 36 0040 50 pushl %eax
> 37 0041 682C0000 pushl $.LC0
> 37 00
> 38 0046 E8FCFFFF call printf
> 38 FF
> 39 004b 89EC movl %ebp, %esp
> 40 004d 5D popl %ebp
> 41 004e C3 ret
>
> GAS LISTING igammaric.s page 2
>
>
> DEFINED SYMBOLS
> igammaric.s:3 .text:00000000 igamma
> igammaric.s:29 .text:00000030 main
>
> UNDEFINED SYMBOLS
> printf
>
> A questo punto, lanciando il debugger....
>
> [kirk@enterprise Code]$ gdb -q ./igammaric
> (gdb) list
> 1 .globl igamma
> 2 .type igamma,@function
> 3 igamma:
> 4 pushl %ebp
> 5 movl %esp, %ebp
> 6 cmpl $0, 8(%ebp)
> 7 jne .L3
> 8 movl $1, %eax
> 9 jmp .L2
> 10 .L3:
> (gdb)
> 11 subl $12, %esp
> 12 movl 8(%ebp), %eax
> 13 decl %eax
> 14 pushl %eax
> 15 call igamma
> 16 addl $16, %esp
> 17 movl %eax, %edx
> 18 movl 8(%ebp), %eax
> 19 imull %edx, %eax
> 20 .L2:
>
> Breakkando, vorrei andare a leggermi i valori dei registri contenenti il
> fattoriale... e con mia grande sorpresa... "tocco" con mano il lavoro
fatto
> sullo stack...
>
> (gdb) break 19
> Breakpoint 1 at 0x80482dd: file igammaric.s, line 19.
> (gdb) run
> Starting program: /home/kirk/Code/./igammaric
>
> Breakpoint 1, igamma () at igammaric.s:19
> 19 imull %edx, %eax
> Current language: auto; currently asm
> (gdb) info reg
> eax 0x1 1
> ecx 0x40162928 1075194152
> edx 0x1 1
> ebx 0x401618e8 1075189992
> esp 0xbffff770 0xbffff770
> ebp 0xbffff770 0xbffff770
> esi 0x40015ad4 1073830612
> edi 0xbffff844 -1073743804
> eip 0x80482dd 0x80482dd
> eflags 0x200282 2097794
> .......
>
> (gdb) c
> Continuing.
>
> Breakpoint 1, igamma () at igammaric.s:19
> 19 imull %edx, %eax
> (gdb) info reg
> eax 0x2 2
> ecx 0x40162928 1075194152
> edx 0x1 1
> ebx 0x401618e8 1075189992
> esp 0xbffff788 0xbffff788
> ebp 0xbffff788 0xbffff788
> esi 0x40015ad4 1073830612
> edi 0xbffff844 -1073743804
> eip 0x80482dd 0x80482dd
> eflags 0x200286 2097798
> cs 0x23 35
> ss 0x2b 43
> ds 0x2b 43
>
> E cosi' a salire, fino a ritrovarmi "ovviamente" in %eax il valore 24....
>
> Vi sembra banale?
>
> A me no, per questo vi volevo rendere partecipi delle mie osservazioni,
> seguendo il flusso dell'Assembly, o, se volete, il binario direttamente,
> sembrerebbe che la moltiplicazione non venga mai eseguita... ma invece (e
> non so bene con che criterio), viene "pushata" nello stack, e ritirata
> fuori al momento giusto, (si vede dal debugging interattivo...) in ordine
> inverso...
>
> Mi piacerebbe sentire il vostro parere sulla questione, e magari, avere
una
> "spiegazione" (anche a livello di SO), del perche'....
>
> Grazie a chiunque abbia avuto la pazienza di leggere il POST, mi scuso per
> l'eccessiva lunghezza del messaggio... ma non volevo tralasciare dettagli
> che ritenevo importanti...
>
> A presto,
>
> Silvio
Kiuhnm
> C'è un "vecchio" libro della F. Angeli, dal titolo "Il pensiero
> ricorsivo", che dovresti leggere. Non ricordo gli autori.
Quoting, please.
Kiuhnm