Capitolo 9 - Le funzioni - aspetti operativi

 

 

 

            9.1 - Scopo dei parametri

 

 

                Secondo le norme ANSI, i prototipi di funzione non sono obbligatori in due casi; se:

 

                (a) - la funzione genera un valore di tipo intero;

                (b) - la definizione della funzione si trova prima della sua prima chiamata.

 

ma é comunque opportuno utilizzarli ai fini controllo della lista dei parametri. Il prototipo, che di norma é ben definito già in sede di analisi, diviene l’informazione di riferimento sia per il contesto della chiamata della funzione, che della sua definizione.

 

                Lo scopo primario dei parametri é trasferire informazioni dal contesto della chiamata alla funzione, ossia fornirle un input adeguato; se vi é bisogno che altre informazioni transitino nel senso opposto, ciò é realizzabile con la restituzione di un valore da parte della funzione. Per questo essa viene spesso vista come scatola nera, in cui un certo insieme di dati in ingresso genera un ben determinato dato in uscita.

 

                L’esistenza di un solo valore ‘di ritorno’ (o di nessuno affatto) può essere un limite consistente, perché potrebbero esistere casi in cui sarebbe più naturale averne più d’uno; consideriamone alcuni esempi.

 

·         [1] - Se una funzione ha come parametro un numero non intero e come scopo la determinazione di mantissa e caratteristica della forma esponenziale normalizzata, le informazioni ‘naturali’ che essa deve restituire sono due numeri interi, ben distinti in valore e ruolo.

 

·         [2] - Nella soluzione di sistemi di equazioni lineari si utilizzano spesso  funzioni alle quali viene passata una matrice, oppure una sua riga, al fine di eseguire una trasformazione dell’intera riga; in questo caso non si tratta tanto di ricevere un valore di ritorno, quanto di modificare il dato utilizzato come parametro.

 

·         [3] - Per rilevare dalla tastiera dati in forma strutturata, funzioni come la getch sono troppo limitate; ne servono altre capaci di interpretare una sequenza di caratteri per assegnare valori ad insiemi generici di variabili, cioè ancora funzioni in grado di modificare il valore degli identificatori utilizzati come parametri.

 

 

                Se é in causa solo la molteplicità dei valori di ritorno come in [1], il linguaggio C permette di costruire funzioni adatte allo scopo, perché il valore di ritorno potrebbe essere, ad esempio, un puntatore ad un array.  La realizzazione può comportare difficoltà, perché si tratta di decidere ‘a cosa’ l’indirizzo in questione deve puntare e questo comporta la considerazione di modelli complessi di gestione della memoria (strutture e memoria dinamica)

 

                Questo problema può essere affrontato senza modificare la considerazione della funzione come scatola nera, ma generalizzando la natura dell’unico dato ‘in uscita’.

 

                Se invece si tratta di casi come [2] e [3] tale modello non é più adeguato, perché in questi casi é essenziale che la funzione operi sui suoi dati di ingresso, modificandoli, mentre il valore generato dalla funzione potrebbe non esistere affatto, come in [2], o avere un ruolo secondario, come in [3]; ad esempio, nell’ultimo caso essa potrebbe restituire come valore il numero di operazioni effettuate con successo, cioè il numero di dati effettivamente acquisiti.

 

  (9.1.1)                   Nella gestione dei parametri di una funzione esistono due esigenze distinte e logicamente

                               opposte: permettere, oppure no, alla funzione di modificare il valore di un parametro.

 

                L’analisi dei problemi che ne derivano potrebbe essere proseguita in astratto, in termini puramente logici e senza riferimento alle macchine; poiché però si tratta di individuare schemi operativi adatti ad una effettiva realizzazione, é opportuno considerarli dal punto di vista di ‘cosa accade’ durante l’esecuzione di un programma che utilizzi funzioni, concentrando l’attenzione sulla gestione della memoria.


 

            9.2 - Passaggio dei parametri per valore

 

 

                Un programma scritto in un qualunque linguaggio di programmazione, e per questo il C non fa eccezione, deve essere compilato per generarne la versione eseguibile, destinata ad essere caricata nella memoria di lavoro per avviare l’esecuzione, utilizzando le informazioni che compilatore e linker hanno preparato per il sistema operativo.

 

  (9.2.1)                   Il caricamento del programma comporta la allocazione di memoria di lavoro in termini di

                               indirizzo iniziale ad estensione, di almeno due spazi distinti: I, per la sequenza di istruzioni

                               del programma e D per la rappresentazione dei dati. Durante l’esecuzione, le istruzioni in

                               I possono legittimamente eseguire operazioni solo sui dati in D.

 

                Questo é un modello riduttivo dell’effettiva utilizzazione della memoria per un programma reale: ad esempio per i dati si dovrà distinguere tra una parte permanente, o statica, per la quale D risulta una buona rappresentazione, ed una temporanea e/o dinamica, che richiede ulteriori specificazioni (si veda la parte sullo stack, più avanti). Per gli obiettivi attuali quanto detto in (9.1.2) é però sufficiente.

 

  (9.2.2)                   Se il programma é diviso in funzioni, per ogni funzione l’allocazione degli spazi I e D é una

                               operazione indipendente, per cui ogni funzione è autorizzata a svolgere operazioni solo sulla

                               propria zona dati; tale principio vale anche per la funzione principale, che controlla il flusso

                               esecutivo dell’intero programma.

 

                Anche in questo caso il modello é riduttivo; esso rappresenta bene le esigenze dei dati locali, come sono stati definiti in (8.6.3), ma é evidente che richiede un ampliamento se debbono essere considerate risorse di tipo globale; ricordiamo però ancora che per il momento interessa solo l’analisi delle operazioni di macchina in riferimento alla gestione dei parametri delle funzioni.

 

  (9.2.3)                   Il valore di un parametro attuale nella chiamata di una funzione può essere reso disponibile

                               alla funzione stessa eseguendo una copia del dato dal contesto in cui avviene la chiamata alla

                               zona dati D propria della funzione.

 

                Per comprendere meglio i ‘tempi operativi’ consideriamo come le chiamate di sqrt fatta nel segmento della funzione principale main riportato sotto; per fissare le idee, indichiamo con D(main) e D(sqrt) le rispettive zone dati di main e sqrt.

 

  (9.2.4)                   double x, y, z ;

                               .....

                               y = z + sqrt ( x ) ; /*  prima chiamata  */       

                               ......

                               z = sqrt ( x + y ) : /*  seconda chiamata  */

 

                In entrambi i casi lo scopo é l’assegnazione ad una variabile in D(main) del valore dell’espressione a secondo membro; in particolare, nel primo caso si tratta di eseguire un somma il cui primo termine z é già presente in D(main), mentre il secondo termine deve essere valutato con la funzione sqrt, utilizzando come dato x, esso pure presente in D(main).

 

                La funzione sqrt é un processo di calcolo analogo alla num_primo di (8.5.1), con la differenza che la prima é già pronta in libreria, mentre la seconda é definita dall’utente; perché essa possa operare correttamente, e restituire il valore richiesto, la macchina deve:

 

  (9.2.5)                   (a) - sospendere l’esecuzione delle operazioni nel contesto della chiamata, mantenendo

                               memoria del punto in cui é avvenuta la sospensione;

                               (b) - trasferire i valori dei parametri (se ne esistono) allo spazio dati della funzione;

                               (c) - eseguire le operazioni della funzione fino alla loro conclusione logica;

                               (d) - mettere a disposizione il risultato di tali operazioni in uno spazio dati accessibile

                               dal contesto della chiamata;

                               (e) - riprendere le operazioni di tale contesto dal punto in cui sono state sospese;

 

passi operativi di cui al momento interessa soprattutto (b).


 

                Nel caso della prima chiamata di sqrt in (9.2.4), supponiamo ad esempio che la variabile x occupi otto byte in D(main) a partire dall’indirizzo 1000 della memoria ed abbia valore 12.5 (la forma dell’indirizzo é una semplificazione);  dopo la sospensione della operazione in I(main), si deve decidere come mettere a disposizione il dato nello spazio D(sqrt). Il modo più ovvio é utilizzare otto byte in D(sqrt) e copiare in essi il valore 12.5; le operazioni in I(sqrt) possono utilizzare questo dato ed eseguire i calcoli richiesti, procedendo come descritto in (8.5.5).

 

  (9.2.6)                   Se il valore di un parametro attuale viene copiato nello spazio dati accessibile alla funzione

                               chiamata, si dice che si effettua un passaggio di parametro per valore. In questo caso le

                               operazioni della funzione possono modificare la copia del dato, ma ciò non ha alcun

                               effetto sul valore originale nel contesto della chiamata. Si dice anche che in questo caso il

                               dato é protetto da effetti collaterali derivanti dalle operazioni della funzione.

 

                Ad esempio, se chi ha programmato la funzione sqrt, che opera presumibilmente per approssimazione, ha deciso di utilizzare la variabile che contiene la copia del dato originario modificandola direttamente, la variabile x non risente in nessun caso di questa decisione. In realtà non sappiamo nulla delle operazioni di sqrt, ma se il passaggio é fatto per valore c’è la garanzia che non vi siano effetti indesiderati su x.

 

                Se poi si considera la seconda chiamata, si nota che in essa il parametro non é nemmeno una variabile, ma un’espressione, che ovviamente deve essere valutata prima di avviare le operazioni di sqrt. Il risultato di una espressione non ha nome, quindi non ha una posizione identificabile in memoria, ma in genere solo una esistenza temporanea nei registri di calcolo del microprocessore. Poiché in qualche forma esso esiste, deve essere possibile trasferirne una copia nello spazio dati della funzione chiamata.

 

 

 

 

 

 

 

            9.3 - Passaggio dei parametri per riferimento

 

 

                Vi sono però occasioni in cui il passaggio per valore comporta un sovraccarico per la memoria ed altre in cui esso impedisce di effettuare operazioni essenziali per gli scopi per cui una funzione viene costruita.

 

                Il primo caso si verifica quando un parametro attuale é un identificatore che non rappresenta un dato di tipo semplice, ma, ad esempio, un array; se l’array é molto grande la sua duplicazione nello spazio dati della funzione chiamata può comportare tempi alti nella copia, ma soprattutto richieste di memoria eccessive. La matrice dichiarata come double m[200][200] richiede 320000 byte di memoria e per molti sistemi questo é già un problema; duplicarla é una richiesta eccessiva per quasi tutti.

 

                Il secondo caso é però più importante; con gli esempi [2] e [3] di 9.1 si hanno casi in cui non solo non é opportuno che la zona dati del programma chiamante sia protetta dalla funzione chiamata, ma addirittura funzioni che operino come richiesto non possono nemmeno essere costruite se non esistono alternative al passaggio per valore.

 

                Riprendiamo però l’esempio (9.2.4), con le ipotesi fatte sul valore e l’indirizzo di x, che possiamo riassumere in notazioni del C:

 

  (9.3.1)                   x = 12.5                 &x = 1000

 

e l’idea per l’alternativa é evidente: sarebbe sufficiente passare al programma chiamato la seconda informazione per permettere alle istruzioni in I(sqrt) di avere accesso allo spazio dati D(main), creando quindi la possibilità di modifiche al dato mediante operazioni dirette sul suo indirizzo originario. Questa non é ovviamente la decisione opportuna nel caso di sqrt, ma il principio può essere applicato in altri casi.

 

  (9.3.2)                   Se dal contesto della chiamata viene passato alla funzione chiamante l’indirizzo di

                               memoria di un dato, si dice che si effettua un passaggio di parametro per riferimento;

                               in questo caso nello spazio dati della funzione chiamata é presente una copia dello

                               indirizzo del dato e non il dato stesso.


 

                Vale a dire, con il passaggio per riferimento é possibile la modifica dei dati nello spazio del contesto in cui avviene la chiamata direttamente dalle operazioni della funzione chiamata. Poiché la funzione ha a disposizione una copia dell’indirizzo del dato, se la logica della funzione richiedesse di modificare tale indirizzo, ad esempio per operazioni su array, quello originario non ne risentirebbe.

 

  (9.3.3)                   Il passaggio per riferimento non richiede aggiunte alla sintassi, poiché la notazione dei

                               puntatori é sufficiente per la descrizione dei parametri. Esso elimina inoltre il problema 

                               della duplicazione dei dati, e permette di utilizzare gli stessi parametri come ‘veicoli’ di

                               valori generati dalle operazioni della funzione chiamata.

 

  (9.3.4)                   Il passaggio per riferimento é possibile solo se ha senso trattare l’indirizzo del dato, quindi

                               per le variabili di tutti i tipi, ma non per costanti ed espressioni.

 

                Per i parametri attuali il passaggio per riferimento richiede quindi l’utilizzazione esplicita dell’operatore di indirizzo ‘&’, a meno che lo stesso identificatore utilizzato come parametro abbia già la natura di un indirizzo, come nel caso dei nomi di array. Ad esempio, quasi tutte le funzioni di stringa viste in (5.5.9) debbono modificare la stessa stringa che figura come primo parametro, ed in esse figura il semplice identificatore.

 

                E’ quasi superfluo ricordare che, qualunque sia la decisione sul parametro, valore o riferimento, vi deve essere accordo nei tre contesti di dichiarazione del prototipo, chiamata e definizione di ogni funzione.

 

 

                I linguaggi di programmazione sono stati progettati ognuno con una diversa trattazione predefinita del passaggio dei parametri, che ne ha condizionato le notazioni.

 

                Per il Fortran ed il Basic, il passaggio avviene sempre per riferimento, salvo che per costanti ed espressioni, nel senso che questa é la decisione automaticamente applicata ad ogni identificatore che figuri come parametro attuale; tutti i compilatori attuali possiedono però anche metodi per imporre come eccezione un passaggio per valore, ma le relative convenzioni non sono standardizzate e programmi che utilizzino disponibilità di questo tipo perdono la portabilità da un sistema ad un altro.

 

                Per il Pascal, all’opposto, tutti i parametri sono passati per valore, salvo esplicita indicazione contraria nella definizione della funzione, fatta premettendo la parola chiave VAR all’identificatore del parametro; questo linguaggio non richiede prototipi, perché la definizione della funzione deve essere fatta prima della prima chiamata, in un flusso fisico che prevede la presenza dell’equivalente della funzione main come parte conclusiva del testo del programma.

 

                La decisione per il C é intermedia ed é probabilmente la migliore possibile, perché corrisponde al modo naturale di trattare tutti gli identificatori nei loro diversi tipi, di dato o puntatore:

 

  (9.3.5)                   In C, tutte la variabili ordinarie sono automaticamente passate per valore, mentre

                               tutti gli array e le strutture di dati più complesse sono passati per riferimento.

 

 

                Come esempio di passaggio per riferimento, riprendiamo [1] in 8.7: dato un numero di tipo float, si vuole scrivere una funzione in grado di restituire come interi distinti la mantissa e la caratteristica della forma esponenziale normalizzata. La macchina utilizza questa notazione come rappresentazione naturale dei numeri non interi, ma le due informazioni sono presenti in memoria in forma binaria codificata e non possono essere rilevate direttamente; si richiede quindi di operare sui numeri con i normali criteri decimali, cioè di scrivere la funzione in modo tale da simulare le operazioni con cui si risolverebbe manualmente il problema.

 

                Se diciamo x il numero interessato, e ricordando che la sequenza di cifre significative di un valore di tipo float equivale a 6-7 cifre decimali, l’analisi di un possibile algoritmo per ottenere questo scopo é:

 

  (9.3.6)                   dati:        x non intero; mantissa, caratteristica interi ;

                                               poni mantissa = caratteristica = 0 ;

                                               finché x > 1, dividi x per 10 ed incrementa caratteristica di 1 ;

                                               finché x < 0.1, moltiplica x per 10 e decrementa caratteristica di 1 ;

                                               poni mantissa = parte intera di ( x * 107  ) .


  (9.3.6)

                               /*  PARAMRIF.C - esempio di passaggio per riferimento

             */

             #include <stdio.h>

 

             typedef unsigned long  ulong ;                                     /* <1> */

             void mant_car ( float dato, ulong *mant, int *car ) ;       /* <2> */

             main ( )

             {  ulong mantissa ;  int caratteristica ;  double x ;

 

                printf ( "\n --  calcolo mantissa e caratteristica" ) ;  /* <3> */

                printf ( "\n --  per numero dato di tipo float" ) ;

                printf ( "\n --  x <= 0 per terminare \n\n" ) ;

                do  { printf ( " valore di x : " ) ;

                      scanf ( "%f", &x ) ;                                      /* <4> */

                      if ( x > 0 )

                        { mant_car ( x, &mantissa, &caratteristica ) ;          /* <5> */

                          printf ( "per %f mant. %ld, caratt. %d \n”,

                                    x, mantissa, caratteristica ) ;

                        }

                    } while ( x > 0 ) ;

             }

 

             /*---------------------------------------------------------*/

             /*  M A N T _ C A R  -  calcolo mantissa e caratteristica  */

             /*---------------------------------------------------------*/

 

             void    mant_car ( float d, ulong *m, int *c )              /* <6> */

             {

                    *m = 0 ; *c = 0 ;                                           /* <7> */

                    while ( d > 1 )  (*c)++, d /= 10. ;                         /* <8> */

                    while ( d < 0.1 )  (*c)--, d *= 10. ;

                    *m = d * 1.0e7 ;                                            /* <9> */

             }

 

                Seguono, al solito, commenti sugli elementi più significativi.

 

·         <1>:  Esempio di sinonimo di tipo: ulong sostituisce il più lungo unsigned long

 

·         <2>: Nel prototipo, il primo parametro é per valore, gli altri per riferimento

 

·         <3>: Sarebbe bene utilizzare sistematicamente scritture di questo tipo all’inizio del programma per informare l’utente sullo scopo del programma e soprattutto di cosa il programma attende dalla tastiera.

 

·         <4>: Questa funzione di lettura dei dati (si veda il capitolo sulle funzioni di I/O) é più complessa di getch ed opera come ‘filtro’ sulla sequenza di caratteri che provengono dalla tastiera; poiché x deve ricevere un valore, il passaggio di parametro deve essere per riferimento.

 

·         <5>: Nella chiamata della funzione mant_car, il primo identificatore é semplicemente citato, mentre agli altri due é premesso l’operatore di riferimento (indirizzo), come richiesto dal prototipo della funzione

 

·         <6>: Nella definizione della funzione, si osservi ancora la coerenza nella notazione dei parametri.

 

·         <7>: In questo contesto gli identificatori m e c sono puntatori; per modificare i corrispondenti valori in memoria, che sono quelli di due variabili nello spazio dati D(main), é necessario l’operatore di deferimento ‘*’.

 

·         <8>: Le parentesi in (*c)++ sono essenziali: lo scopo é infatti di incrementare la variabile, mentre la notazione *c++ avrebbe modificato il puntatore; si osservi poi che in questa istruzione e nella successiva d subisce variazioni, che non hanno però effetto su x, come mostra la scrittura che conclude le operazioni di main.

 

·         <9>: La moltiplicazione per 107 ha lo scopo di trasferire ad un intero il massimo numero di cifre decimali significative.

 


 

            9.4 - Memoria temporanea: lo stack

 

 

                In 8.8 si é presentato uno schema di utilizzazione della memoria per le istruzioni ed i dati di una funzione del programma, le zone denominate I e D. Esso ha una natura implicitamente statica, cioè suggerisce che una volta ‘marcate’ tali zone, esse rimangano stabili per tutta la durata dell’esecuzione del programma, mantenendo la stessa estensione, che é quella calcolata in fase di compilazione e predisposta dal linker.

 

                Se per le istruzioni questa rappresentazione é adeguata, per i dati si deve invece fare qualche altra considerazione, perché se l’allocazione statica della memoria é corretta per i dati di validità globale, non é così per quelli di tipo locale.

 

                I dati locali richiedono infatti spazio in memoria solo mentre esistono, cioè quando la funzione in cui essi sono dichiarati é attiva. Se tale spazio venisse allocato in modo temporaneo, come su una lavagna il cui contenuto può essere cancellato quando non serve più, le medesime posizioni di memoria potrebbero venire utilizzate successivamente da una diversa funzione.

 

                Le variabili dichiarate localmente in una funzione non sono il solo esempio di dato di validità temporanea; sono tali, ad esempio, anche tutte le informazioni sui parametri, che del resto nella definizione di una funzione sono trattate in modo simile alle variabili locali.

 

                Esistono anche altre informazioni ‘nascoste’, che hanno esse pure carattere di dato temporaneo e che nella programmazione in C non sono ‘viste’ direttamente, ma sono essenziali per il funzionamento del programma: gli esempi più importanti sono:

 

 (9.4.1)                    (a) - l’indirizzo di ritorno della istruzione nel corso della quale viene chiamata una funzione;

 

                               (b) - il contenuto dei registri del microprocessore (tutti o parte), che riflettono continuamente

                               lo stato corrente di un programma, e che per questo motivo debbono essere salvati durante la

                               chiamata di una funzione e ripristinati prima di restituire il controllo al contesto chiamante;

 

                               (c) - il valore di ritorno di una funzione, quando non é sufficiente un registro;

 

                               (d) - il valore di una espressione, o di sue parti durante la valutazione, anche questo nel

                               caso che i registri del microprocessore non siano sufficienti allo scopo.

 

 

                L’esigenza di una parte di memoria riutilizzabile in modo dinamico da parte dei dati di tipo temporaneo é quindi molto estesa. I dati in memoria possono venire organizzati in molti modi, ed uno di essi si rivela ideale per la rappresentazione delle informazioni temporanee. Si tratta della organizzazione a stack, o pila (nel senso di una pila di piatti), indicata anche con la sigla LIFO, che sta per Last In, First Out, o ‘ultimo dentro, primo fuori’, che é appunto il modo di utilizzare le pile.

 

  (9.4.2)                   Alle zone I e D per la rappresentazione delle istruzioni e dei dati statici si deve aggiungere

                               una zona S per l’allocazione dello stack; tale zona non é riservata ad una particolare

                               funzione del programma, ma comune a tutte.

 

                Come struttura di dati, lo stack può essere considerato come un array, i cui elementi dipendono dall’organizzazione della macchina e del sistema operativo. Nel caso dei sistemi MS-DOS, i cui microprocessori utilizzano registri a 16 bit, anche lo stack é organizzato sulla stessa misura; questa é la decisione più comune, perché il massimo scambio di informazioni é appunto tra stack e registri.

 

  (9.4.3)                   Le informazioni essenziali per la gestione dello stack sono:

 

                               (a) - il numero di byte di ogni elemento dello stack;

                               (b) - la sua estensione, o numero totale di byte allocati;

                               (b) - il puntatore alla prima posizione libera, o livello corrente dello stack.


 

                Inizialmente il livello é posto a zero; le due operazioni normalmente definite per uno stack sono indicate in genere con push (spingere, o premere) e pop (saltare fuori, o prelevare), rispettivamente inserimento di un elemento, con incremento dell’indicatore di livello (2 byte, per i sistemi MS-DOS) e prelevamento, con uguale decremento.

 

 

                Nell’architettura del linguaggio C é implicito che lo stack sia la zona ideale per la rappresentazione delle variabili locali, anche se l’effettiva implementazione di questa regola é lasciata al costruttore del compilatore, che potrebbe decidere in modo diverso.

 

                In un programma C anche main, o funzione principale, é una funzione, e la regola si applica anche ad essa; l’importanza di questa osservazione non é del tutto ovvia: la conseguenza é infatti che anche le variabili definite in main, essendo locali, sono allocate sullo stack.

 

                Essendo lo stack una zona di memoria con alta movimentazione di dati, essa viene in genere organizzata in modo da garantire un accesso molto veloce, ed in genere questo impone limiti alla sua dimensione; ad esempio, con il sistema operativo MS-DOS il compilatore Microsoft C ver. 6.0 ha come dimensione predefinita dello stack 2K byte, che possono essere aumentati su richiesta esplicita ad un massimo di 64K, ma che in ogni caso costituiscono uno spazio fortemente limitato.

 

                Per questo motivo l’array lista del programma (8.5.1) non é stato dichiarato ‘normalmente’ all’interno di main, ma a livello globale, evitando di utilizzare lo spazio dello stack e forzandone una allocazione statica.

 

                Si deve però osservare che questa soluzione non coincide con quanto suggerirebbe la distinzione degli spazi I e D specifici delle funzioni, vale a dire, lista non é una variabile di main e quindi non appartiene a quella parte della memoria che abbiamo indicato con D(main); se si fosse voluto ottenere questo risultato, cioè la allocazione di memoria fuori dallo stack, ma nella zona dati ‘privata’ della funzione, sarebbe stato necessario il ricorso ad una nuova parola chiave del linguaggio.

 

  (9.4.4)                   La parola chiave static é un modificatore di tipo, che può essere utilizzato in qualunque

                               dichiarazione di risorsa. Se applicata ad una variabile locale, essa ha l’effetto di forzarne

                               l’allocazione in memoria statica al caricamento del programma. La variabile rimane però

                               privata, cioè indefinita al di fuori della funzione in cui é dichiarata.

 

                La allocazione statica di variabili locali ha anche un altro effetto; mentre le variabili locali non qualificate come static ‘rinascono’ ad ogni chiamata della funzione, ed ogni loro utilizzazione richiede che esse siano state definite (ad esempio mediante una assegnazione) quelle dichiarate con tale attributo mantengono invece il loro valore da una chiamata alla successiva.

 

                L’attributo static può essere utilizzato anche per variabili globali, per le quali sembra una inutile ripetizione, offrendo invece la possibilità di diversificare ulteriormente la ‘catalogazione’ delle risorse di un programma; questo argomento verrà discusso a fondo trattando delle classi di memoria.

 

 

 

 

            9.5 - Le funzioni ricorsive

 

 

                In (8.4.7) si è osservato che per le funzioni del C é ammessa la chiamata ricorsiva, cioè la possibilità per una funzione di chiamare sé stessa, direttamente nelle proprie istruzioni, oppure indirettamente tramite una chiamata circolare di due o più funzioni.

 

                Le funzioni ricorsive si incontrano spesso in matematica; l’esempio più ovvio é dato dal fattoriale:

 

  (9.5.1)                   n ! = f ( n ) = n * ( n - 1 ) * ( n - 2 ) * ... * 2 * 1

 

é più correttamente definito da:

 

(9.5.2)                     f ( 0 ) = 1, ed  f ( n ) = n * f ( n - 1 ) se n > 1


 

in cui si riconosce che il calcolo della funzione per un valore dato rinvia a quello della medesima funzione per un valore inferiore, fino a giungere ad un ‘ancoraggio’, quando il parametro é nullo.

 

                Poiché il C ammette chiamate ricorsive, é possibile scrivere una funzione che riproduce esattamente la logica della definizione ricorsiva (9.5.2); questa non é però l’unica possibilità, perché il medesimo scopo potrebbe facilmente ottenersi con una normale tecnica iterativa, in questo caso un semplice ciclo for.

 

                La tecnica ricorsiva non é una risorsa indispensabile per un linguaggio di programmazione, perché é stato dimostrato che ogni algoritmo definito in termini ricorsivi può sempre essere riformulato in soli termini iterativi, cioè senza impiego di funzioni ricorsive.

 

                In generale, per i motivi che esporremo subito, é anzi preferibile utilizzare la versione iterativa, ma vi sono dei casi in cui per ottenere questo scopo si dovrebbero fare sforzi eccessivi, tali da rendere improponibile l’implementazione del programma in forma iterativa, ed é in questi casi che la possibilità di utilizzare funzioni ricorsive diviene importante.

 

                Un esempio notevole é dato dal problema delle torri di Hanoi: esistono tre posizioni, A, B, C ed in una di esse, diciamo A, é collocata un ‘cono’ di N cerchi di diametro strettamente decrescente (N intero > 1). Lo scopo é di spostare il ‘cono’ in un’altra posizione, diciamo C, osservando due regole. (a) si può spostare ogni volta un solo cerchio da una posizione ad un’altra e (b) in nessuna condizione un cerchio può essere collocato sopra uno di diametro inferiore.

 

                La formulazione é molto semplice, e la soluzione é immediata: il problema di N cerchi da A a C é risolto, se é risolto il problema di N-1 cerchi da A a B, poiché questa é la sola condizione che permette il passaggio del cerchio di diametro massimo da A a C, indispensabile per la soluzione.

 

                La constatazione più interessante é che si tratta della formulazione di una funzione ricorsiva, che costituisce un interessante esercizio di programmazione.

 

 

                Le funzioni ricorsive, pure nella ‘eleganza’ delle formulazioni, possono porre problemi di diversa natura.

 

                Il primo non é un vero problema, ed é il loro comportamento spesso ‘antiintuitivo’: é piuttosto difficile comprenderne chiaramente i dettagli operativi, e questo conduce spesso a programmi molto inefficienti; se vengono impiegate nel calcolo dei numeri di Fibonacci, ad esempio, possono dare luogo a calcoli di molti minuti al posto di qualche secondo.

 

                Un problema reale può invece nascere spesso con lo stack, che é proprio la struttura di dati senza la quale le funzioni ricorsive non sarebbero gestibile..

 

                Ogni funzione, ricorsiva o no, comporta un ‘costo’ in termini di utilizzazione di spazio sulla stack, che é almeno pari alla somma di quanto serve per memorizzare l’indirizzo di ritorno, i parametri e le variabili dichiarate nella funzione come locali (non static); inoltre, vi possono essere richieste addizionali nel corso delle operazioni della funzione, ma queste non sono generalmente un problema

 

                Consideriamo per primo un programma in cui non esistono funzioni ricorsive; supponiamo che vi sia una funzione f1 il cui costo-stack é di N1 byte (un valore tipico può essere 20-30) e che nel corso delle sue operazioni ne viene attivata un’altra, f2, che ne richiede N2.  Per un certo tempo la richiesta allo stack e quindi di almeno N1+N2 byte, ma alla conclusione di f2 si torna al livello N1.

 

                Se f2 a sua volta attiva un’altra funzione f3, l’occupazione totale di stack aumenta ancora, ma di nuovo diminuisce all’uscita da f3, e così via per chiamate successive. E’ evidente che catene molto lunghe di ‘funzioni dentro funzioni’ possono facilmente raggiungere il limite massimo di spazio disponibile sullo stack, rendendo impossibile la prosecuzione.

 

                Se le funzioni non sono ricorsive e se non vi sono eccessive richieste di spazio per variabili di tipo volatile, altro termine per le locali non statiche, é molto difficile creare problemi seri con sequenze di chiamate di funzioni; ma se le funzioni sono ricorsive il problema può crearsi rapidamente e divenire molto serio.


 

            9.6 - Esempio: calcolo del massimo comun divisore

 

 

                L’algoritmo di Euclide per il calcolo del massimo comun divisore di due numeri interi é un interessante esercizio di programmazione per le diverse ‘strategie’ che possono essere utilizzate.

 

                Dimostriamo completamente la proprietà su cui si basa l’algoritmo; se n ed m sono i due interi, esistono e sono unici due altri interi q ed r, quoziente e resto della divisione, n = q * m + r. Ora, se n ed m ammettono un divisore comune k, allora k é anche un divisore di r; per provarlo basta porre n = k * n’, m = k * m’, per ottenere che r = k * n’ - q * k * m’ = k * ( n’ - q * m’ ), é poiché in parentesi figura un intero positivo, é vero che k divide r.

 

Poiché é sempre r < m, l’importanza del risultato sta nel potere asserire

 

  (9.6.1)                   mcd ( n, m ) = mcd ( m, r ),

 

‘trasferendo’ il calcolo sulla prima coppia di interi alla seconda, più conveniente. Utilizzando ripetutamente la sostituzione, il calcolo si arresta appena il resto di una divisone é nullo.

 

                La relazione (9.6.1) é formulata in termini ricorsivi, quindi il programma può utilizzare una funzione ricorsiva; il programma che segue utilizza entrambe le forme, iterativa e ricorsiva, mettendole a confronto per valutare la convenienza dei tempi di calcolo.

 

                Poiché il tempo necessario per un solo calcolo sarebbe difficilmente valutabile, si é predisposto un ciclo per la ripetizione del medesimo calcolo un grande numero di volte; la costante MAX_CONTO, che nel programma é posta ad 1000000, che é un valore adeguato per calcolare tempi in secondi sulla macchina su cui é stata condotta la prova, dotata di un microprocessore Intel 486 / 100Mhz, sistema MS-DOS e compilatore Microsoft C vers. 6.

 

                Su tale macchina, in tutti i test si é verificato che il sovraccarico dovuto alla gestione dello stack nella versione ricorsiva comporta tempi di circa il 25% superiori rispetto a quelli della versione iterativa.

 

                Poiché il procedimento utilizza una divisione (nella forma del calcolo di modulo) si é introdotta una ulteriore variante, in cui il resto della divisione é calcolato con differenze ripetute; ciò perché somme e differenze sono operazioni più veloci rispetto al prodotto e soprattutto alla divisione; nei microprocessori moderni il salto in ordini di grandezza é stato ridotto rispetto al passato, ma esiste ancora e quindi questa prova ha comunque un certo interesse.

 

  (9.6.2)

 

       /*  EUCLIMCD.C   -  calcolo del massimo comun divisore con il metodo di

                           Euclide - confronto tra tecnica iterativa e ricorsiva

       */

       #include <stdio.h>

       #include <time.h>                                                         /* <1> */

 

       #define  MAX_CONTO  1000000

                                                                                 /* <2> */

       /*---   Prototipi funzioni   ---*/

 

             long   leggi_dato ( int ) ;

             long   ric_mcd ( long, long ) ;

             long   ite_mcd ( long, long ) ;

             long   dif_mcd ( long, long ) ;

 

       /*---   M A I N  -  controllo del flusso del programma   ---*/

 

       main ( )

       {

          int fase = 1 ;

          long conto, primo, secondo, valore, inizio, fine, delta ;

          char *metodo[] = { "ricors-resti ", "iterat-resti ",

                              "iterat-diffe " } ;                                /* <3> */

 

          printf ( "\n\n Calcoli MCD, ripetizioni %ld \n\n", MAX_CONTO ) ;


 

          primo = leggi_dato ( 1 ) ;

          secondo = leggi_dato ( 2 ) ;

 

          do { time ( &inizio ) ;                                         /* <4> */

               for ( conto = 1 ; conto <= MAX_CONTO ; conto++ )

                  { if ( fase == 1 )        valore = ric_mcd ( primo, secondo ) ;

                     else if ( fase == 2 )   valore = ite_mcd ( primo, secondo ) ;

                     else if ( fase == 3 )   valore = dif_mcd ( primo, secondo ) ;

                  }

               time ( &fine ) ;

               delta = fine - inizio ;

               printf ( "\n %s, mcd = %ld, tempo = %ld",

               metodo[fase], valore, delta ) ;

             }  while ( ++fase < 4 ) ;

          printf ( "\n" ) ;

       }

 

       /*---  L E G G I _ D A T O - input controllato di un long  ---*/

 

       long leggi_dato ( int posto )

       {

          int errore;  long dato ;

 

          do { printf ( "valore # %d ( > 1 ) : ", posto ) ;

               scanf ( "%ld", &dato ) ;                                          /* <5> */

               if ( errore = dato < 2 )  printf ( "\a" ) ;                       /* <6> */

             } while ( errore ) ;

          return ( dato ) ;

       }

 

       /*---   R I C _ M C D  -  calcolo ricorsivo   ---*/

      

       long ric_mcd ( long uno, long due )

       {

          long  resto, ret_val ;

 

          resto = uno % due ;

          ret_val = ( resto )  ? ric_mcd ( due, resto )  :  due ;         /* <7> */

          return ( ret_val ) ;

       }

 

       /*---   I T E _ M C D  -  calcolo iterativo con resti   ---*/

      

       long ite_mcd ( long uno, long due )

       {

          long resto ;

      

          do { resto = uno % due ;

               if ( resto )  { uno = due ;  due = resto ; }               /* <8> */

             }  while ( resto ) ;

           return ( due ) ;

       }

      

       /*---   D I F _ M C D  -  calcolo iterativo con differenze   ---*/

      

       long dif_mcd ( long uno, long due )

       {

          while ( uno != due )

               { if ( uno > due )  uno -= due ;  else  due -= uno ; }

      

          return ( uno ) ;

       }

 

                Seguono le principali osservazioni.

 

·       <1>: Il file di testata <time.h> é richiesto dalla funzione time, utilizzata per la rilevazione dei tempi.


·       <2>: La costante MAX_CONTO può essere modificata per test su altri sistemi.

 

·       <3>: Il vettore di stringhe metodo ha lo scopo di permettere il commento del risultato con una sola istruzione printf, utilizzando la costante intera fase che seleziona la chiamata della funzione di calcolo.

 

·       <4>: La funzione time restituisce nello stesso parametro il numero di secondi trascorsi da una data fissata dal sistema in modo arbitrario; i tempi effettivi sono ottenibili come differenze; il passaggio é per riferimento.

 

·       <5>: L’opzione di formato “%ld” é quella adatta per numeri di tipo long, esattamente come per printf.

 

·       <6>: si noti la forma tipica del C, con l’espressione in parentesi che permette di assegnare il valore alla variabile errore e di controllarlo logicamente nello stesso contesto.

 

·       <7>: Nella prima clausola del condizionale é presente la chiamata ricorsiva, che opera lo scambio di dati; si osservi che non c’é modo di determinare a priori quante volte verrà effettuata la chiamata, poiché il numero esatto dipende dai dati e può divenire anche molto alto.

 

·       <8>: Al contrario, nella versione iterativa la funzione viene attivata una volta sola e lo scambio dei valori delle variabili é scritto esplicitamente nel programma.

 

 

                Alcune prove sul sistema citato in precedenza hanno dato i seguenti tempi in secondi:

 

  (9.7.3)                   n                             m                            ricors.                    ite_resti                ite_diff

 

                               1040                      232                        10                           8                             6

                               567890                 470                        22                           17                           309

                               569020                 176927800          42                           31                           170

 

                Può essere interessante effettuare altre prove per ipotesi sul comportamento ipotizzabile del metodo delle differenze e di quello delle divisioni, in relazione all’ordine di grandezza dei valori dati e del loro rapporto.

 

               

 

 

 

 

 

            9.7 - Le funzioni come parametri

 

 

                Come conclusione dell’esame delle funzioni, possiamo considerare un argomento che ha notevole interesse, sia teorico, che applicativo; trattando dei parametri delle funzioni si é brevemente accennato che vi può essere la necessità di passare ad una funzione il nome di un’altra funzione come parametro.

 

                Anche questa esigenza é nata in contesti matematici, anche se le applicazioni sono di natura molto ampia; per le funzioni dell’analisi matematica sono infatti comuni problemi come la rappresentazione grafica, la derivazione, l’integrazione, l’interpolazione, ecc., che richiederebbero funzioni di programma capaci di svolgere le operazioni specifiche di un certo contesto non su una funzione fissata, ma sul nome ‘astratto’ di una funzione, che può essere modificata di volta in volta.

 

                Il problema può porsi anche in altri contesti; ad esempio, nel corso di un algoritmo di ordinamento é necessario effettuare operazioni di scambio, che possono riguardare direttamente i dati, oppure un insieme di indici collegati ai dati. I dati possono essere di tipo qualunque, e questo significa che non é possibile scrivere direttamente le funzioni di scambio in una funzione di ordinamento di tipo generale.

 

                Se però la funzione di ordinamento viene scritta utilizzando ancora un nome ‘astratto’ per la funzione di scambio, e richiedendo all’utente di scrivere da sé la sua specifica funzione di scambio, notificandone il nome, si sono poste le premesse per scrivere una volta per tutte le istruzioni di un algoritmo che può essere molto complesso, mettendolo a disposizione dell’utente con poche complicazioni rispetto alle altre funzioni di libreria.

 

 

                L’argomento non é però elementare; in questo contesto ci limitiamo a definire le notazioni che permettono di utilizzare le funzioni come parametri, completandole con un esempio ‘artificiale’, che cioè non risolve nessun problema, ma si limita a fornire un prototipo applicativo.

 

                Per quanto riguarda la sintassi, la variazione é abbastanza semplice, e riguarda solo la descrizione del parametro che ha la natura di una funzione:

 

  (9.7.1)                   Se una funzione ammette come parametro il valore di un’altra funzione, quest’ultima

                               deve essere descritta riproducendone in parte il prototipo nel prototipo della prima,

                               utilizzando le parentesi come indicatore di puntatore ad una funzione; la descrizione

                               del parametro nella prima funzione deve cioè avere la forma:

 

                                               tipo ( * [nome] ) ( [ par_1] ... [, [par_n] ] )

 

                               in cui il nome é opzionale, e per i parametri della funzione ‘variabile’ valgono le stesse

                               regole della descrizione generale dei parametri nei prototipi.

 

 

                L’esempio che segue si limita a generare due scritture che notificano in quale punto passa il flusso esecutivo del programma:

 

  (9.7.2)

 

       /*  VARFUN.C  -  esempio di chiamata variabile di funzione

       */

       #include <stdio.h>

 

       /*---   Dichiarazione dei prototipi   ---*/

 

               void    varfun ( void (*) ( void ) ) ;              /* <1> */

               void    fun1 ( void ) ;

               void    fun2 ( void ) ;

 

       /*---   Controllo del flusso del programma   ---*/

 

       main ( )

       {

              printf ( "\n -- main chiama fun1" ) ;

              varfun ( fun1 ) ;                                           /* <2> */

              printf ( "\n -- main chiama fun2" ) ;

              varfun ( fun2 ) ;                                           /* <3> */

       }

      

       void varfun ( void (*f) ( void ) )                                 /* <4> */

       {

            printf ( "\n -- ora in varfun" ) ;

            f ( ) ;                                                       /* <5> */

       }

      

       void fun1 ( )  { printf ( "\n -- ora in fun1" ) ; }

 

       void fun2 ( )  { printf ( "\n -- ora in fun2" ) ; }

 

 

                Si osservino i contesti da <1> a <5>, con tutte le occasioni in cui compaiono informazioni sulla ‘funzione variabile’, che per semplicità é priva di tipo e di parametri; se anche ve ne fossero, non ci sono altri elementi di novità rispetto al loro impiego consueto.

 

                Nei casi <2>, <3>, <4> é particolarmente evidente il ruolo di variabile che ha la funzione, mentre le funzioni specifiche, in questo esempio fun1 e fun2, sono del tutto ordinarie (salvo la sintesi della scrittura).