Python e me

Nei giorni scorsi ero alle prese con la preparazione di uno dei nostri articoli di ricerca, in cui ad un certo punto abbiamo cercato di comparare tre strumenti software di analisi. Ognuno degli strumenti è in realtà un prodotto di ricerca, e ognuno è scritto con un linguaggio diverso: il nostro programma, RTSCAN, è scritto in C++; IMITATOR, un tool che hanno sviluppato qui in Francia, è scritto in OCaml; e infine MAST è uno strumento sviluppato all’Universidad de Cantabria in Spagna, ed è scritto in Ada. Ognuno produce risultati in maniera completamente diversa, e c’era quindi la necessità di elaborare questi dati in output in maniera uniforme, per poi produrre dei grafici “decenti”.

Avevamo quindi bisogno di un po’ di script per generare dei dati in input ai tre strumenti, lanciarli, collezionare e uniformare gli output. Abbiamo cominciato con un grande classico: un po’ di bash scripting. Però dopo un po’ ci siamo resi conto che non saremmo andati molto lontano. Un po’ perché io sono sempre stato lento con bash: non mi piace molto la sintassi, e quindi trovo difficile memorizzarla. Un po’ perché sarebbero stati necessari dei tool esterni non banali, e quindi alla fine il risultato non sarebbe stato molto portabile.

Per fortuna che c’è Python. Io non ho mai davvero imparato il Python, perché non ne ho mai avuto il tempo. Non ho tempo per mettermi davanti a un libro o a un corso (anche di quelli accellerati) per imparare l’ABC di un linguaggio. E soprattutto, non ho tempo per imparare a usare le varie librerie (e ce n’è davvero tante). Ma per fortuna, Python ha due caratteristiche peculiari:

1) E’ facile cominciare. Cioè, in realtà all’inizio potete considerarlo tranquillamente come se fosse un linguaggio di scripting. Non c’è bisogno di astruse direttive, di dichiarare variabili, di scrivere funzioni, non c’è bisogno neanche di un main. Si parte a scrivere codice come viene viene, ed è molto probabile che funzioni subito come avevamo pensato.

2) In linea c’è tutto. Qualunque cosa tu voglia fare, basta googlare, e finisci o sul manuale di Python in linea, o su stackoverflow, dove hanno sempre la ricetta pronta per te.

Naturalmente, bisogna conoscere un minimo le basi della programmazione. Ma dal pensiero alla realizzazione passa davvero molto poco.

E passiamo a scrivere brevemente il nostro lavoro. Come prima cosa, avevamo bisogno di specificare il sistema da far analizzare ai tre strumenti. Per semplicità ed immediatezza, abbiamo scelto il formato JSON, che adesso va per la maggiore.  E naturalmente Python ha una libreria per leggere e interpretare un file JSON con sole due funzioni, e il risultato è una lista di dizionari.

Poi, abbiamo scritto 3 funzioni per visitare la lista di dizionari e produrre tre file di input per i tre strumenti. Poi abbiamo scritto 3 funzioni per lanciare i 3 strumenti. Infine, abbiamo fatto post-processing sugli output. Tutto questo in una mezza giornata. Un altro paio di giornate è passato a mettere a posto le cose (perché c’è sempre qualcosa da sistemare, naturalmente) e a cercare di far produrre dei grafici decenti a gnuplot (e ci siamo riusciti solo parzialmente).

Ma la cosa bella di Python è che non si limita ad essere un semplice linguaggio di scripting, ma ha tutte le potenzialità di un vero linguaggio di programmazione. Costrutti evoluti, Object Orientation, ma anche un po di functional programming. C’è la tipizzazione a run-time (il cosidetto duck-typing), il garbage collector. Utilizzando uno stile di programmazione pulito, Python consente di scrivere programmi molto eleganti e “belli”, senza grosso sforzo.

E’ insomma un linguaggio scalabile: si può andare facilmente dal piccolo script di poche linee, al programma mediamente complesso senza grossi problemi. Inoltre ti consente di fare fast prototyping: se hai un’idea, la butti giù e la testi in pochi minuti e con poco sforzo, e la puoi tenere lì in caldo pronto a riprenderla e ad evolverla in qualcosa di più complesso più avanti.

Ha dei difetti? Non sono sicurissimo di quanto possa scalare Python. Se il progetto diventa veramente grande, e con tanti programmatori, non sono sicuro che Python basti. Per esempio, il codice Python può diventare orribile se scritto male e senza giudizio; il fatto che si usi duck-typing richiede una certa dose di coordinazione sulle interfacce quando si lavora in tanti; e quando un progetto è grande, non è detto che tutti i programmatori siano allo stesso livello.

Insomma, mi sa che mi tocca studiarmelo meglio. Adesso che l’ho provato in un caso quasi reale, penso che comincerò ad utilizzarlo sempre più spesso!

Cloud computing

A Natale mi sono regalato uno smartphone Android, per la prima volta nella vita, e quindi ho passato un po’ di tempo a spippolare, come sempre succede in questi casi. Ho installato tutti i miei social network, ora sono un individuo sempre connesso (o quasi), e nei prossimi mesi esplorerò per bene le funzionalità dell’aggeggio (da non utente, sono sempre stato scettico sulla reale utilità di questi aggeggi, ma forse potrei cambiare idea in un futuro non troppo remoto).

Ad un certo punto ho provato a scrivere delle note tramite il tastierino, ma non è che funzioni benissimo: lo schermo è piccolo, i miei polpastrelli sono grandi, e azzeccare il tasto giusto non è facilissimo. Per fortuna che c’è il riconoscitore vocale! Clicchi sull’icona del microfono, e cominci a parlare normalmente, e il testo appare magicamente sullo schermo dopo pochi istanti e con pochissimi errori. “Uau”, ho pensato, “funziona benissimo!”

A dire la verità funziona anche troppo bene. Mmm, facciamo una prova. Disabilito il wireless e la connessione dati, e riprovo. Ma l’icona del microfono adesso non c’è più: non è possibile fare riconoscimento vocale quando sono off-line. Ecco la spiegazione: l’applicazione di riconoscimento vocale è un classico esempio di cloud computing.

Che vuol dire? Vuol dire in generale che la potenza di calcolo di un computer o di un dispositivo mobile viene aumentate usando ricorse remote di rete: la famosa nuvola. Lo smartphone viene utilizzato come un terminale evoluto, il cui scopo è semplicemente di prendere l’input dell’utente, e di mostrare l’output. Il calcolo vero e proprio viene “off-loaded” a un computer remoto. Possibilmente il calcolo viene parallelizzato in modo da eseguirlo più velocemete su tanti calcolatori.

Ora, i nostalgici che frequentano qusto blog ricorderanno come funzionavano i maniframe di una volta: un solo calcolatore centrale (il mainframe) e tanti terminali stupidi tutti collegati (in seriale!) al calcolatore centrale. Qui la faccenda è molto più complicata: problemi di sicurezza, distribuzione del carico, parallelizzazione, ottimizzazione delle risorse, risposta in tempo reale… c’è tanta ricerca, ricerca in cui naturalmente le grandi aziende come Google sono molto avanti, mentre  l’università arranca molto dietro.

Nel nostro caso, l’app prende la nostra voce (e chi sa che altro) e la spedisce ai server google, che rispediscono indietro il testo. Naturalmente, viene subito fuori il probema della privay: che se ne fa Google dei nostri dati? Beh, li usa per i suoi scopi, ovviamente. O pensate che a Mountain View siano tutti dei benefattori dell’umanità? Per ora, Google dice che i nostri dati vengono trattati in maniera anonima. Ma se nel futuro dovessero trovarsi eonomicamente in difficoltà, io non mi stupirei più di tanto se ricevessi sulle pagine web pubblicità personalizzata a seconda di quello che ho dettato a Google! Che ne so, se prendo una nota “prenotare l’aereo per Pisa”, i banner pubblicitari delle compagnie interessate a venermi un biglietto Parigi-Pisa cominceranno ad apparire sulle pagine web che visiterò da quel momento in poi.

E poi, ci potrebbe essere di peggio, naturalmente: se siete persone importanti, e con nemici importanti, evitate di usare i riconoscitori vocali moderni, mi raccomando!

Programmatori amatoriali

Ultimamente è saltata fuori la moda che tutti vogliono (o addirittura devono!) saper programmare. Il nostro esimio collaboratore Pier Giuliano ha segnalato questo pezzo su G+:

Rise of Coding: Why We Should All Learn a Little Code

dove si sostiene (non senza un certo poco celato conflitto di interessi) che tutti dovremmo saper programmare. Tutti, ma proprio tutti? Eh, certo se tutti sapessero cosa vuol dire programmare, forse schiferebbero meno e apprezzerebero un po’ di più il lavoro dei programmatori professionisti; per lo meno sarebbero in grado di apprezzare la difficoltà e la complesità di certe realizzazioni. Sembra che addirittura il sindaco di New York abbia deciso di imparare. Qui si dice anche che i CEO dovrebbero imparare un po’ di tecnologia, per il loro bene.

Non tutti sono d’accordo però. Alcuni rimpiangono i vecchi tempi quando per programmare si indossaa il camice bianco: l’epoca dei sacerdoti dei mainframe! Altri più realisticamente, affermano che programmare non è proprio per tutti. Per esempio, su slashdot mi informano di questo rant (ehm post):

Making non-coders code

E in effetti non ha tutti i torti: se uno non vuole imparare, se non si sente portato, perché deve imparare per forza? E addirittura produrre codice da mettere sui prodotti! Non invidio i programmatori profesionisti in quell’azienda.

Un flame simile c’era stato qualche tempo fa. Coding horror si era scagliato contro la moda. E qui avevano risposto molto ironicamente (direi sfottendo Atwood alla grande). Leggete perché ne vale la pena!

Boh, insomma, a me sembra si esaeri da una parte e dall’altra. Obbligare qualcuno a programmare, direi di no. Ma se tutti avessero un minimo di basi non sarebbe male. Non dico haskell, ma se tutti imparassero per lo meno a impostare uno spreadsheet per calcolarsi il budget familiare o le rate del mutuo, ecco io sarei pù contento. E voi che ne pensate?

Penna e calamaio

Oggi ho letto questa perla di saggezza:

Best programming advice you’ll ever get: before coding, sit back and think. Then think again.

(su Twitter da @miljar, ri-postato da Claudio Cicali su FF).
E non posso che essere d’accordo. Dirò di più: io sarei per tornare alla programmazione carta e penna.

Scrivere programmi col pennino?

Qualche anno fa, al corso di Sistemi Operativi del prof. Ancilotti a cui facevo da assistente, l’esame scritto consisteva nello scrivere un programmino con carta e penna. Capisco che a prima vista può sembrare folle: programmare con carta e penna? Beh, si, secondo me è più istruttivo, più didatticamente adeguato. Nel corso di Sistemi in Tempo Reale, ancora oggi faccio fare uno scritto in cui il primo esercizio consiste nello schematizzare un programma con carta e penna. In entrambi i corsi lasciavamo agli studenti la possibilità di usare tutto il materiale che volevano, (appunti, libri, slides, ecc.) tranne il PC.

A mia discolpa, dirò che non ho mai preteso una sintassi perfetta. Se uno scorda un punto e virgola, oppure scrive print invece di printf, non è un problema, purché il programma sia logicamente corretto. Se volete è un vantaggio per lo studente: non c’è bisogno di essere super precisi, purché l’algoritmo che ci sta sotto sia corretto.

Quando devo scrivere un algoritmo complicato, io di solito faccio con carta e penna così:

• Prendo un foglio A4 pulito, o ancora meglio un quadernone a quadretti.
• Comincio a fare uno sketch dell’algoritmo (di solito una singola funzione) con una matita. Da una parte a destra del foglio segno le variaili locali che mi servono di volta in volta.
• Qualche volta mi permetto di abbreviare: for all x in v invece del classico ciclo for, while senza condizione (la metto dopo), ecc.
• La regola pù importante è che la funzione deve stare tutta in un singolo foglio. Se mi accorgo che viene troppo lunga, spezzo in più funzioni, da mettere nei fogli successivi
• Se resta spazio, di solto metto qualche breve esempio di esecuzione, o qualche schemino che spiega graficamente il funzionamento.
• E’ importante fare il primo debug a occhio direttamente sul foglio.
• A volte, lascio lì il foglio per un po’ e vado a fare altro (che ne so, a farmi la barba). Il mio cervello in background continua a pensarci su (io sono fatto così), e spesso trovo dei bug o dei controesempi mentre mi aggiusto le basette.
• Quando ci ho pensato un po’ e sono abbastanza contento, è il momento di andare sul PC. Questa è la parte più meccanica di tutta la faccenda, ma anche quella che da più soddisfazione, specialmente se alla fine funziona!!

Sembra che Djikstra una volta abbia detto:

“Computer science is no more about computers than astronomy is about telescopes.”

e può darsi che si riferisse a questa cosa qui!

Comportamenti indefiniti

Il quiz dello scorso post era un pochino a trabocchetto, lo ammetto, ma Alessandro ha fatto un buon lavoro ed è quasi arrivato alla soluzione. Il quiz era il seguente:

Qual’è il comportamento del seguente programmino C?

#include <stdio.h>

int d = 5;

int set(int x)
{
    return d = x;
}

int main()
{
    int r = set(0) + 7 / d;
    printf("risultato = %d\n", r);
    return 1; 
}

E la risposta è

… (rullo di tamburi) …

il programma ha un comportamento indefinito!

Come, non sapete cos’è un comportamento indefinito? Beh, se programmate in C, è il momento di fare un corso di aggiornamento.

Benvenuti nel fantasmagorico mondo degli Undefined Behaviours!

Se volete una introduzione veloce, al solito c’è wikipedia. Se non ci avete capito molto, vi consiglio questa serie di tre post del bravissimo John Regher (tra l’altro, John ha anche un corso su Udacity, sul testing: se avete tempo di seguirvi un intero corso e volete studiare software testing, il corso di John è quello che fa per voi!).

Se invece volete continuare a leggere, vi spiego in quattro e quattr’otto di cosa stiamo parlando. La semantica del C/C++ è un po lasca, e in certi punti lascia libertà al compilatore. L’esempio classico è quello dell’accesso a un array al di là della sua dimensione. Per esempio, se avete un array di 10 interi, e accedete all’11-esima posizione, che succede? Lo standard C vi dice che, in tal caso, il comportamento del programma è “undefined”.

Che deve fare un compilatore quando si trova di fronte a un comportamento indefinito? Beh, l’interpretazione più diffusa è che il compilatore è libero di fare quello che gli pare. Qualunque cosa, e per “qualunque cosa” intendo proprio qualsiasi. Infatti, un programma che ha un “undefined behaviour” è semanticamente incorretto, e quindi da una cosa scorretta si può tirar fuori qualunque altra cosa, no? Persino dei diavoletti dal naso (nasal demons!).

Torniamo al quiz e vediamo perché il programma ha un comportamento indefinito. In C, l’ordine con cui vengono valutati gli operandi di una espressione non è sempre ben definito. Ci sono regole un pochino complicate, che hanno a che fare con i cosidetti sequence points. In pratica, un sequence point è un punto del programma in cui, prima di proseguire bisogna acertarsi di aver risolto tutti i “side effects” delle istruzioni precedenti. Il problema del nostro programma è che nella fattispecie l’operatore di somma non è un sequence point. Quando scriverte (x + y), il compilatore è libero di calcolare prima x e poi y, oppure viceversa. Di solito, l’ordine di valutazione degli argomenti non è importante: dopo tutto, in matematica l’addizione gode della proprietà commutativa, quindi ci si aspetta che cambiando l’ordine degli addendi il risultato non cambi! Per cui, chi ha scritto lo standard ha lasciato libero il compilatore di eseguire la valutazione degli addendi nell’ordine che preferiva. Per esempio, se per ragioni di ottimizzazione, è meglio valutare prima y e poi x, il compilatore lo farà, perché è libero di farlo, secondo lo standard.

Purtroppo, nel nostro programma, valutare prima la chiamata set(0) e poi 7/d, oppure prima 7/d e poi set(0) cambia il risultato: nel primo caso si ha una bella divisione per 0; nel secondo caso invece il risultato dovrebbe essere 1.
Poiché il risultato non è univoco, ma dipende dall’ordine in cui il compilatore decide di valutare i due operandi, allora il nostro programma ha un “Undefined Behaviour”. In pratica, è scorretto e non aderente allo standard. Tenete anche presente che una cosa è la precedenza fra operatori, e una cosa completamente diversa è l’ordine di valutazione degli operandi: la differenza è spiegata piuttosto bene qui.

Nella pratica, in questo caso il compilatore gcc segue sempre l’ordine di valutazione da sinistra verso destra, per cui se compilate ed eseguite il programma con gcc avrete come risultato un bell’errore di divisione per zero.

Più interessante è il comportamento di un altro compilatore che ultimamente sembra andare per la maggiore: si tratta di clang. Se compilate con il comando:

$ clang prova.c
$ ./a.out
Floating point exception (core dumped)

che è quello che ci si aspetta. Mentre se compilate con le ottimizzazioni:

$ clang -O2 prova.c
$ ./a.out
risultato = 894604808

Il numero che tira fuori è assolutamente casuale! Come mai? Beh, semplice: come detto prima, in presenza di “Undefined Behaviour” tutto può succedere, anche che vi escano i demoni dal naso! Più seriamente: Se il programma è non corretto (ha dei comportamenti indefiniti), il compilatore può tirare fuori eseguibili non corretti, non necessariamente nel modo che ci si aspetta.

Soluzioni?

Adesso la parte seria. Recentemente due ricercatori dell’University of Illinois at Urbana-Champaign (UIUC), Ellison e Rosu, hanno scritto un articolo molto interessante in cui si sono presi la briga di specificare in maniera formale la semantica del linguaggio C, utilizzando un altro linguaggio formale chiamato K. A differenza di altre specifiche formali, quella proposta da Ellison e Rosu è eseguibile, e questo significa che possono prendere un programma C e analizzarlo formalmente, ad esempio alla ricerca di undefined behaviours. Il loro codice è disponibile su googlecode, e teoricamente avrei potuto provarlo sul nostro programmino di esempio. (Ci ho provato per un po’ ma purtroppo il processo di compilazione mi si ferma a metà, devo aver sbagliato qualcosa. Se ci riesco ve lo faccio sapere.) Comunque, il programma dei nostri due ricercatori dovrebbe identificare la presenza di un undefined behaviour nel nostro programmino di quiz e metterlo bene in evidenza.

Il lavoro di Ellison e Rosu è molto importante: dato che molto codice per sistemi embedded e sistemi critici è ancora scritto in C, spesso in maniera euristica o artigianale, avere a disposizione strumenti automatici di verifica è essenziale per l’eliminazione di errori che potrebbero addirittura mettere a rischio la nostra sicurezza. La mia previsione è che nel futuro sentiremo parlare sempre di più di strumenti di verifica formale come assistenza alla programmazione.

Chucky Ellison, Grigore Rosu (2012). An executable formal semantics of C with applications ACM SIGPLAN Notices, 47 (1), 533-544 : 10.1145/2103621.2103719

Quizzettino del week-end

Dato che agosto è finito, e anche l’estate sta finendo, per allietare il fine settimana vi propongo un quiz facile facile, la cui soluzione sarà un post lungo e noiosissimo (scherzo! o forse no, boh). Insomma, la soluzione sarà data prossimamente, intanto beccatevi il quiz.

Qual’è il comportamento del seguente programmino C?

#include <stdio.h>

int d = 5;

int set(int x)
{
    return d = x;
}

int main()
{
    int r = set(0) + 7 / d;
    printf("risultato = %d\n", r);
    return 1; 
}

Cercate di essere precisi nella risposta, mi raccomando. Alla prossima!

Ottimizzare il codice

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Questa frase è stata attribuita a Donald E. Knuth, e se lo dice lui che ha scritto “The Art of Computer Programming”, ha inventato il TeX, e ha sviluppato la teoria della complessità degli algoritmi, potete stare certi che sia vero.

Il significato della frase è che bisognerebbe evitare di ottimizzare il codice prima di aver finito di scriverlo. Il modo di programmare “corretto” sarebbe:

• primo, si scrive il codice nella maniera più semplice possibile, possibilmente in maniera elegante e leggibile
• poi ci si accerta della sua correttezza (testing , debugging, e quello che pare a voi)
• Infine, pensiamo alle performance, ottimizzando il codice dove necessario

Spesso invece il programmatore comincia fin dall’inizio a complicare il codice e la strrutra del programma, alla ricerca del programma già perfettamente ottimizzato. Nel fare così, spesso viene fuori codice molto complicato e probabilmente pieno di bug. Da qui la sentenza di Knuth: l’ottimizzazione prematura è la radice di tutti i mali!

L’osservazione chiave è che spesso il codice contiene alcuni (pochi) “colli di bottiglia”, ed è lì che l’ottimizzatore deve concentrarsi per far andare veloce il suo programma. Come identificare questi “colli di bottiglia”? Per esempio, funzioni chiamate molto frequentemente, strutture dati usate pesantemente in tutto il codice, ecc. I programmatori esperti ormai lo fanno ad occhio, ma per programmi molto grandi e complessi non è affatto facile. Sarebbe bene ci fosse qualche strumento di ausilio al programmatore.

oggi vediamo come fare analisi delle prestazioni con due tool disponibili su Linux con licenza GPL: valgrind e kcachegrind.

Il primo è una specie di “emulatore” del vostro PC. Prende in ingresso un file eseguibile, e lo esegue su un “processore virtuale”. Nel portare avanti l’esecuzione, però, è in grado di effettuare una serie di analisi sul codice. Valgrind è una piattaforma generica su cui sono stati sviluppati diversi strumenti. Il più famoso è memchek che serve a controllare l’uso della memoria, ed individuare possibili “memory leak“. Quello di cui ci occupiamo oggi, invece, è callgrind che serve a stimare le performance delle varie parti di codice del nostro programma.

Per installare questi tool, su Ubuntu si deve scrivere sul terminale:

sudo apt-get install valgrind
sudo apt-get install kcachegrind

e siamo pronti per i nostri esperimenti.

Proveremo ad utilizzarlo sui programmini che Juhan ci ha proposto per fare confronti fra il Fortran e vari altri linguaggi. Cominciamo dalla versione C/C++ di tale programma, che riporto qui per comodità (anche perché ho fatto due modifiche).

#include <stdio.h>
#include <math.h>

double f[14];

#define POW(x,y) pow(x,y)
//#define POW(x,y) mypow(x,y)

inline double mypow(double x, int y)
{
    double r = 1;
    for (int i=0; i<y; i++) r *= x;
    return r;
}

double fsin(double a) {
    return a - POW(a, 3) / f[3] + POW(a, 5) / f[5]
        - POW(a, 7) / f[7] + POW(a, 9) / f[9]
        - POW(a, 11) / f[11] + POW(a, 13) / f[13];
}

static double fcos(double a) {
    return 1.0 - POW(a, 2) / f[2] + POW(a, 4) / f[4]
        - POW(a, 6) / f[6] + POW(a, 8) / f[8]
        - POW(a, 10) / f[10] + POW(a, 12) / f[12];
}

static double myln(double x) {
    if (x == 0.0) {
        return -1.0e20;
    } else {
        double r = (x - 1.0) / (x + 1.0);
        return 2.0 * (r + POW(r, 3) / 3.0
                      + POW(r, 5) / 5.0
                      + POW(r, 7) / 7.0
                      + POW(r, 9) / 9.0);
    }
}

double mylog(double x) {
    static double ln10 = myln(10.0);

    return x / ln10;
}

int main(int argc, char **argv)
{

    int i, j;
    f[0] = 1.0;
    for (i = 1; i < 14; i++)
        f[i] = i * f[i - 1];
    int deg = 60;// * 60;
    int nsteps = 180 * deg;
    double step = M_PI / nsteps;
    double ssum;
    double csum;
    double a, s, c, t = 0.0;
    double ls, lc;
    for (j = 1; j < 11; j++)
    {
        ssum = 0.0;
        csum = 0.0;
        for (i = 0; i < nsteps; i++)
        {
            a = i * step;
            s = fsin(a);
            ls = mylog(myln(s));
            ssum += s;
            c = fcos(a);
            lc = mylog(myln(c));
            csum += c;
            if ((i % (10 * deg)) == 0)
            {
                if (c != 0.0)
                    t = s / c;
                printf("%3d %11.8f %11.8f %11.8f %15.8e\n", (i / deg), a, s, c, t);
                printf(" %15.8e %15.8e\n", ls, lc);
            }
        }
    }
    printf("%g\n", ssum);
    printf("%g\n", csum);
}

Le due modifiche fatte sono le seguenti: ho sostituito tutte le chiamate a pow() con la macro POW. Quest’ultima si traduce per il momento nella chiamata di libreria pow() (che, come discusso nel post precedente, è più lenta). Inoltre, ho diminuito il numero di cicli da svolgere per accorciare un po la durata dell’esecuzione: adesso il conto viene fatto per deg = 60 invece che per deg = 60*60 (vedi linea 54).

Salvate il programma qui su sul vostro HD con il nome prova.cpp, e poi compilatelo con il seguente comando:

g++ -g prova.cpp -o provacpp

Il flag -g serve per inserire i simboli di debug nel file eseguibile, e la qual cosa ci permetterà di associare il costo delle operazioni alle relative istruzioni nel codice sorgente.

Adesso siamo pronti per l’esecuzione, ecco il comando da dare:

valgrind --tool=callgrind ./provacpp

Questo manda in esecuzione il tool callgrind sul file eseguibile provacpp. Il quale viene eseguito a una velocità molto inferiore a quella normale (parliamo di un rallentamento di quasi 100 volte!) e vengono collezionati i dati di performance. L’output è un file che si chiama

callgrind.out.PID

Dove PID è l’ID del processo che è stato eseguito.
Per visualizzare i dati, date il comando:

kcachegrind callgrind.out.PID

(dove naturalmente avrete sostituito PID con il numero giusto), e si aprirà una finestra come questa:

La finestra principale di KCacheGrind

Questo tool ci visualizza i risultati dell’esecuzione. Faccio zoom sulla finesta a sinistra dove viene mostrato il “call graph” (ovvero il grafo delle chiamate):

Come vedete, il main() chiama le funzioni myln, fsin e fcos, e ciascuna chiama la funzione pow, la quale a sua volta chiama le funzioni interne per fare operazioni floating point. Subito sotto il nome delle funzioni viene riportato il tempo (in percentuale) speso dal programma dentro quella funzione. Questo programma ha speso il 95.73% del suo tempo dentro la funzione pow()! Notare anche una certa asimmetria: myln prende il 50% del tempo, mentre fsin e fcos ciascuna circa il 25%.

Adesso riproviamo utilizzando la funzione mypow() (quella che fa le moltiplicazioni per fare le potenze): basta commentare la linea 6 e scommentare la 7, e ricompilare. Se rifate tutto il percorso otterrete questo callgraph:

Come vedete, le cose sono un po’ cambiate. In particolare, mypow() non chiama alcuna funzione in floating point (come ci si aspetta), e inoltre le percentuali di myln, fsin e fcos sono un po’ cambiate.

È anche possibile mostrare questi numeri direttamente sul sorgente, cliccando sulla tab “Source Code”, ed ecco lo snapshot relativo:

Infine: si può fare una cosa del genera anche per il fortran? Ovviamente sì! Vi riporto semplicemente il comando di compilazione e di esecuzione:

gfortran -g m_c10l.f08 fc10l.f08 -o provaf
valgrind --tool=callgrind ./provaf

E poi tutto come prima. Ecco lo screenshot del callgraph per il fortran:

Qui notiamo che la funzione per la stampa a video (_gfortran_transfer_real_write) prende ben il 13% del tempo, ed è probabilmente lei la causa delle peggiori prestazioni del fortran rispetto al C/C++. Inoltre, notate come da nessuma parte ci sia una chiamata ad alcuna pow(), perché nel fortran l’elevazione a potenza per un numero intero è una operazione del linguaggio.

Ovviamente, questi tool funzionano bene per codice eseguibile, non funzionano affatto bene su Java e su Python. Ci sono però altri tool, più o meno professionali, che fanno cose analoghe. Semmai se ne parla un’altra volta!

Spero che questo post possa esservi utile nel vostro lavoro di “ottimizzatori!”, e ricordate le parole di Knuth!

Nota di Juhan: Mi ricordo il profiler id Borland; questo è molto più bello e anche il prezzo. Vero? Vero dikiyvolk?

Programmazione C++: mappe

Puntate precedenti: I vettori, ancora sui vettori, Liste e iteratori.

Oggi analizzo un’altro contenitore della libreria standard del C++, molto usato e anche parecchio criticato: la mappa associativa. Si tratta di un contenitore un po’ particolare, perché permette di associare un “valore” a una “chiave”. In pratica, è come se potessimo indirizzare un vettore con una valore qualsiasi invece che con un indice numerico. L’esempio classico è il seguente:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);

    cout << "Elem1.first  = " << elem1.first << endl;
    cout << "Elem2.second = " << elem1.second << endl;

    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    for (auto i : eta_persona) 
        cout << "Eta' " <<  i.first << " = " << i.second << endl;    
}

Alla linea 9 dichiariamo il nostro contenitore e diciamo che associerà numeri interi a stringhe. Nell’esempio, infatti, cerchiamo di memorizzare l’età di un insieme di persone. La chiave è la stringa, ed è quella che utilizzeremo per fare le ricerche nel contenitore; il valore da cercare è l’intero.

Alla linea 10 facciamo subito vedere un esempio di assegnamento: alla chiave “Giuseppe” viene assegnato il valore 41 (e già, sto diventando vecchio…).

Ma esattamente, come vengono memorizzati gli elementi all’interno del contenitore? Gli elementi dentro il contenitore sono coppie (chiave, valore), e una coppia in C++ ha tipo std::pair. Alla linee 12 e 13 prepariamo due coppie di valori (vedete come è giovane Juhan, invece? ), e alla linee 15 e 16 li inseriamo nel contenitore. Una pair non è altro che una struttura con due campi: il primo campo si chiama first e corrisponde alla chiave; il secondo campo si chiama (sorpresa!) second e corrisponde al valore. Alle linee 18 e 19 stampiamo i due elementi a video.

Naturalmente, per stampare un elemento del contenitore possiamo anche utilizzare la notazione con le parentesi quadre, come alla linea 21.

Infine, se vogliamo scorrere e stampare tutti gli elementi della mappa, possiamo usare gli iteratori, esattamente come nel vettore e nella lista. Solo che stavolta, un iteratore punta a una coppia. Alle linee 24-25 stampiamo tutti gli elementi della mappa con un ciclo for.

Le persone abituate al vecchio C++ si stupiranno della sintassi: che sono quei due punti? Chi sa programmare in Python invece ritrova una vecchia conoscenza. Il nuovo ciclo for à la Python è disponibile nel nuovo standard ed è parecchio comodo, soprattutto se combinato con la nuova parola chiave auto. Vediamo di spiegarci: il C++ è un linguaggio fortemente tipato (a differenza del Python) e quindi vuole che si dichiarino i tipi di tutte le variabili. La variabile i avrebbe tipo

std::pair<string, int> i;

che però è lungo da scrivere (ed anche noioso). Non solo: il tipo è automaticamente ottenibile dal contenitore che sta a destra dei due punti: se voglio esplorare una map, allora sappiamo già che gli elementi ivi contenuti saranno pair. E allora, perché non lasciare che sia il compilatore a ricavarsi automaticamente il tipo? Questa tecnica è simile a quello che succede in Haskell, che è un linguaggio fortemente tipato, ma dove la dichiarazione dei tipi è superflua, tanto ci pensa il compilatore a ricavarseli automaticamente.

Ok, fin qui tutto facile. Compilate con il solito “g++ -std=c++0x”, otterrete l’eseguibile che potete lanciare, ottenendo questo risultato:

Elem1.first  = Giovanni
Elem2.second = 35
Eta' di Giuseppe: 41
Eta' di Eleonora: 0
Stampa tutte le eta': 
Eta' Eleonora = 0
Eta' Giovanni = 35
Eta' Giuseppe = 41
Eta' Juhan = 21

Uno dei problemi della map è però proprio la sua facilità d’uso, in particolare la notazione con le parentesi quadre. Che succede se ad esempio vogliamo sapere l’età di Eleonora? ecco il programmino:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);

    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;
    // Attenzione!!
    cout << "Eta' di Eleonora: " << eta_persona["Eleonora"] << endl;
    cout << "Stampa tutte le eta': " << endl;
    for (auto i : eta_persona) 
        cout << "Eta' " <<  i.first << " = " << i.second << endl;    
}

E l’output è questo:

Elem1.first  = Giovanni
Elem2.second = 35
Eta' di Giuseppe: 41
Eta' di Eleonora: 0
Stampa tutte le eta': 
Eta' Eleonora = 0
Eta' Giovanni = 35
Eta' Giuseppe = 41
Eta' Juhan = 21

Ops, l’elemento (“Eleonora”, 0) è stato inserito nella mappa, anche se ho acceduto in lettura! Che è successo?

È successo che i progettisti della libreria si sono trovati con un problema. Volevano fornire la possibilità di accedere agli elementi dell’array con la parentesi quadra, perché faceva “figo”; ma come comunicare il fatto che l’elemento non era presente? L’operazione di accesso non può restituire un valore di errore particolare (come -1) perché proprio quel valore potrebbe essere un numero valido nell’applicazione. Una soluzione poteva essere quella di lanciare un’eccezione, ma il codice si sarebbe complicato molto, e soprattutto, i progettisti volevano tener fuori dalle balle il meccanismo delle eccezioni per quanto possibile. Quindi hanno deciso per una soluzione un po’ sporca: se l’elemento non c’è lo aggiungiamo con un valore di default (nel caso dell’intero, 0). Ed ecco che, semplicemente cercando una chiave dentro la mappa, un nuovo elemento viene magicamente aggiunto.
Purtroppo, questo comportamento è tutt’altro che intuitivo, e se non lo sapete rischiate di finire nei casini.

Per sapere se un elemento esiste all’interno della mappa, senza rischiare di aggiungerlo, dovete utilizzare la funzione find() che vi restituisce un iteratore all’elemento trovato (se esiste), oppure alla fine del contenitore (se non esiste). Ecco il codice corretto:

#include <map>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    map<string, int> eta_persona;
    eta_persona["Giuseppe"] = 41;

    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;    

    auto iter = eta_persona.find("Eleonora");
    if (iter != eta_persona.end()) 
        cout <<"L'età di Eleonora è: " << iter->second << ekdl;
    else cout << "Eleonora non è stat ancora inserita" << endl;
}

Notate ancora una volta l’uso di auto per dichiarare l’iteratore. Senza di auto, avrei dovuto scrivere

map<string, int>::iterator iter = eta_persona.find("Eleonora");

Meglio con auto, no?

Se lanciate il programmino, ottenete:

Eta' di Giuseppe: 41
Eleonora non è stata ancora inserita

Tutto a posto, dunque.

Vediamo un po’, e se volessi utilizzare la funzione print() scritta l’altra volta per stampare tutti gli elementi di una mappa? Eccola:

#include <map>
#include <iostream>
#include <string>

using namespace std;

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

int main()
{
    map<string, int> eta_persona;

    eta_persona["Giuseppe"] = 41;
    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    print(eta_persona.begin(), eta_persona.end());
}

Purtroppo, così non funziona, il gcc vi da questo errore (quasi) incomprensibile:

maps2.cpp: In function ‘void print(Iter, Iter) [with Iter = std::_Rb_tree_iterator<std::pair<const std::basic_string, int> >]’:
maps2.cpp:27:49:   instantiated from here
maps2.cpp:11:31: error: cannot bind ‘std::ostream {aka std::basic_ostream}’ lvalue to ‘std::basic_ostream&&’
/usr/include/c++/4.6/ostream:581:5: error:   initializing argument 1 of ‘std::basic_ostream& std::operator<<(std::basic_ostream&&, const _Tp&) [with _CharT = char, _Traits = std::char_traits, _Tp = std::pair<const std::basic_string, int>]’

(Si lo so, è brutto, ma ora ve lo spiego io).
In pratica, alla linea 11 stiamo cerando di stampare una coppia (l’elemento puntato da p, che è un iteratore alla mappa), e il C++ non sa come stamparla. La funzione di stampa (sarebbe quell’operatore strano, <<) non sa come trattare le coppie, e quindi si ferma dando errore di compilazione.

Niente panico! Se il C++ non sa fare una cosa da se’, basta spiegargliela per bene. Non sai stampare una pair? Te lo dico io come si fa, aggiungendo una funzione in più:

template<class F, class S>
std::ostream& operator<<(std::ostream &out, 
                         const std::pair<F,S> &elem)
{
    out << "(" << elem.first << ", " << elem.second << ")";
    return out;
}

Questo è il famigerato overload degli operatori. In pratica, l’operatore << non è altro che una funzione, il cui nome è operator<<, e prende due argomenti, di cui il primo è uno stream di uscita (ad esempio cout, ma anche un qualsiasi file), il secondo è l’oggetto da stampare, nel nostro caso una qualunque coppia di elementi qualsiasi, per esempio di tipo generico F e S. Poiché una funzione così non esiste, la scriviamo noi. E gli diciamo che deve stampare per prima cosa una parentesi tonda aperta, seguita dal primo elemento della coppia, dalla virgola, dal secondo elemento della coppia, e infine dalla parentesi tonda chiusa. Infine, ritorniamo lo stream come risultato, in maniera che si possa fare una concatenazione, per esempio con endl.

Chiaro? No? Non importa, sarà chiaro con degli altri esempi che faremo più avanti (spero). Ecco il programma finale:

#include <map>
#include <iostream>
#include <string>

using namespace std;

template<class F, class S>
std::ostream& operator<<(std::ostream &out, 
                         const std::pair<F,S> &elem)
{
    out << "(" << elem.first << ", " << elem.second << ")";
    return out;
}

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << (*p) << ", ";
    cout << "]" << endl;
}


int main()
{
    map<string, int> eta_persona;

    eta_persona["Giuseppe"] = 41;
    pair<string, int> elem1 = {"Giovanni", 35};
    pair<string, int> elem2 = {"Juhan", 21};    
    eta_persona.insert(elem1);
    eta_persona.insert(elem2);
    cout << "Eta' di Giuseppe: " << eta_persona["Giuseppe"] << endl;

    cout << "Stampa tutte le eta': " << endl;
    print(eta_persona.begin(), eta_persona.end());
}

Prima di chiudere, alcune considerazione sull’efficienza.
La mappa è implementata internamente come un albero binario di ricerca, per cui ogni accesso prende un tempo proporzionale al logaritmo in base due del numero di elementi presenti. Anche per l’inserzione è lo stesso, sempre tempo logaritmico. Dato che l’albero binario è già ordinato, non ha senso ordinare una mappa; il requisito fondamentale, però, è che esista un ordinamento per il tipo che rappresenta la chiave. Se la chiave è una stringa, come nei nostri esempi, l’ordinamento di default è quello alfabetico. E’ però possibile sia cambiare l’ordinamento di default, sia impostare un ordinamento di default per una vostra classe specifica. Ma questo lo vedremo la prossima volta, che adesso si è fatto tardi!

Buon luglio e accendete i condizionatori che i PC soffrono al caldo!

Il centenario di Turing

L’altro ieri era il centenario della nascita di Alan Turing, uno dei padri dell’informatica. Per varie vicissitudini non sono riuscito a scrivere un post, e allora scrivo qualcosa oggi, sperando mi perdoniate per il mio cronico ritardo!

C’è gente che ha scritto post molto belli sull’evento, e ve li segnalo qui nel caso vogliate davvero imparare qualcosa su Turing: il post di Gianluigi Filippelli, completo ed enciclopedico come sempre, da cui si apprende che Alan Turing era un genio davvero eclettico; il post di Maurizio Codogno sul Post, che ci descrive il bellissimo doodle di Google, e quello sul suo blog personale che ci ricorda alcune curiosità.

E che rimane da dire dopo tutto questo florilegio di notizie? Beh, facciamo che metto qualche altro link curioso a risorse trovate su Internet, poi un giorno o l’altro scriverò anche un post più completo sulla macchina di Turing.

La macchina di Turing è effettivamente una grande invenzione, specialmente per i teorici dell’informatica che ci hanno campato per anni e ci hanno costruito carriere con articoli di ricerca. Con il tempo delle “approssimazioni” di macchine di Turing sono state veramente costruite! Guardate per esempio questo divertente video di una macchina di Turing fatta con il Lego Mindstorm:

Carina, vero? I mattoncini sul nastro in posizione “bassa” rappresentano uno 0, in posizione “alta” rappresentano un 1. Una specie di pistoncino “legge” la posizione del mattoncino, mentre un altro pistone sposta il mattoncino in alto o in basso.

Un altro video più serioso, e quindi anche noioso, lo trovate qui sotto. Questo qui forse rende meglio l’idea della macchina di Turing originale.

Se volete allenarvi a capire come funziona una Macchina di Turing, oltre al doodle di Google, ci sono diversi simulatori in giro sul web. Eccone uno (un po’ spartano a dire la verità). Se invece volete provare a scrivere un programmino per una macchina di turing da voi stessi, eccone un altro molto carino.

Dopotutto, in quasi tutte le università c’è un corso in cui si studia la macchina di Turing, e i progetti migliori degli studenti, si sa, finiscono sul web. Per esempio, quando ero studente, come progettino dell’esame di Informatica Teorica, ci fu dato di implementare una Macchina di Turing in Lisp. Credo di aver perso quel programmino, peccato! Magari qualcuno di buona volontà si vuole mettere a riscriverlo in qualche linguaggio esoterico?

Poi volevo dirvi che a Cambridge si è appena conclusa la “Turing Centenary Conference“, mentre a Manchester sta per concludersi “The Alan Turing Centenary Conference“, quest’ultima con partcipanti del calibro di Roger Penrose, Donald P. Knuth, Michael O. Rabin, Garry Kasparov (?), Vint Cerf, Tony Hoare. Gentaglia, insomma (scherzo!). Questi eventi fanno parte dell’Alan Turing Year, una serie di celebrazioni che vanno avanti dall’inizio dell’anno.

Naturalmente, saprete già tutti che “il nobel degli informatici” sarebbe il “Turing Award“, vero? E che nel passato è stato dato ad alcune vecchie conoscenze citate in questo blog come John McCarty, Ken Tomphson e Dennis Ritchie.

Che altro? Beh, Turing avrebbe lavorato alla “bomba”, la macchina per decrittare i messaggi segreti nazisti durante la seconda guerra mondiale, e avrebbe anche progettato un calcolatore elettronico (ACE) più o meno nello stesso periodo in cui Von Neumann progettò il suo EDVAC. In entrambi i casi, i due progetti si ispiravano alla Macchina di Turing, anche se Von Neumann non ammise mai di aver preso a prestito le sue idee da Turing. ACE rimase un segreto militare per moltissimo tempo e solo recentemente si è saputo della sua esistenza.

Insomma, credo sia chiaro che noi informatici dobbiamo un sacco a Alan Turing, senza di lui chissà che starei a fare adesso! Alla prossima!

Programmazione C++: liste e iteratori

Le liste

Nei post sulla programmazione funzionale ho rotto le scatole con le liste, la struttura dati di base di ogni buon linguaggio funzionale che si rispetti. Ci sono le liste in C++? Si, ma non sono poi così flessibili. In realtà, come vedremo più avanti, ogni contenitore può essere trattato come una lista, perché il C++ generalizza il concetto in una maniera molto potente e flessibile.

Dicevo nello scorso post che i vettori non sono sempre la struttura dati più adatta per le nostre esigenze, specialmente quando dobbiamo inserire e estrarre dal mezzo, perché gli elementi sono memorizzati consecutivamente in memoria e per inserire nel mezzo devo spostare una buona metà di elementi.

Nella lista, invece, gl elementi non sono memorizzati consecutivamente in memoria, ma possono stare dove gli pare. In pratica, il contenitore list della libreria standard implementa la buona vecchia lista linkata, gioia e dolori degli studenti del corso di “Fondamenti di Informatica I”.

Facciamo subito un esempio che è meglio.

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

    for (int i=0; i<10; i++) 
        lista.push_back(i);

    for (int i=0; i<10; i++) {
        cout << "Elemento " << i << ": " << lista.front() << endl;
        lista.pop_front();
    }
    return 0;
}

Per prima cosa, stavolta includiamo l’header file list invece di vector. Con il primo ciclo for inseriamo 10 elementi in fondo alla lista. Con il secondo ciclo for, prima stampiamo a video il contenuto della testa della lista (ottenuta con la funzione front), e poi lo estraiamo (con la funzione pop_front()).

Se volessi leggere gli elementi a partire dal fondo, posso usare back() e push_back(), come segue:

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

    for (int i=0; i<10; i++) 
        lista.push_back(i);

    for (int i=0; i<10; i++) {
        cout << "Elemento " << i << ": " << lista.back() << endl;
        lista.pop_back();
    }
    return 0;
}

E se volessi leggere un elemento nel mezzo? Qui non si può usare l’accesso diretto (o random) come nel vettore. In altre parole, scrivere

cout << lista[5];

darebbe un errore di compilazione perché la lista non ha la possibilità di visitare il quinto elemento con una somma e una moltiplicazione, ma deve scorrere tutti gli elementi uno alla volta.

Inoltre, entrambi questi programmi stampano la lista, ma la distruggono man mano che leggono. non è molto comodo vorremmo poter leggere senza distruggere.

Iteratori

Per scorrere gli elementi si usa il concetto di iteratore, che è anche un design pattern, ovvero una tecnica di programmazione ben studiata nei sacri testi della programmazione object oriented. Cos’è un iteratore?
In OOP, l’iteratore è un oggetto che permette di visitare gli elementi in un contenitore in un certo ordine. L’iteratore disaccoppia il contenitore dal metodo di visita, e semplifica l’interfaccia (un sacco di paroloni, ma poi in pratica è molto semplice, vedrete).

In C++ l’iteratore è una generalizzazione del concetto di puntatore, che ci permette di scorrere gli elementi di un contenitore in ordine, utilizzando una sintassi simile a quella dei puntatori. Ecco come scorrere gli elementi di una lista.

#include <list>
#include <iostream>

using namespace std;

int main()
{
    list<int> lista;

    for (int i=0; i<10; i++) 
        lista.push_back(i);

    list<int>::iterator p;
    int i = 0;
    for (p = lista.begin(); p != lista.end(); p++) 
        cout << "Elemento " << i++ << ": " << *p << endl;  

    return 0;
}

(Sembra molto complicato a prima vista, ma vedrete che tra un po’ ve lo semplifico. E’ che all’inizio, per capire le cose per bene, bisogna prendere la strada lunga, poi quando le nostre gambe sono ben allenate possiamo prendere la scorciatoia).

Quindi, l’iteratore qui l’ho chiamato p, e che si tratti di un iteratore lo capite dalla dichiarazione del tipo:

list::iterator p;

Poi, nel ciclo for, p prende inizialmente il valore restituito dalla funzione begin(). Questa funzione (metodo in dialetto OOP) restituisce l’iteratore che punta al primo elemento della lista. Il ciclo for si ferma quando p è pari al valore della funzione end(), che restituisce l’iteratore che punta al valore successivo all’ultimo elemento della lista. In pratica, end() restituisce un puntatore a un elemento non valido. A ogni iterazione del ciclo for, il valore di p è incrementato (p++): questo vuol dire che al termine di ogni iterazione, p passerà da un elemento al successivo.

Per ottenere il valore dell’elemento, basta utilizzare l’indirezione, ovvero l’operatore *:

cout << "Elemento " << i++ << ": " << *p << endl;  

Ok, fin qui credo sia semplice da capire, anche se un po’ complicato da scrivere.
E adesso, sorpresa: gli iteratori esistono anche per i vettori!
Ecco l’esempio:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vettore;

    for (int i=0; i<10; i++) 
        vettore.push_back(i);

    vector<int>::iterator p;
    int i = 0;
    for (p = vettore.begin(); p != vettore.end(); p++) 
        cout << "Elemento " << i++ << ": " << *p << endl;  

    return 0;
}

Come vedete ho semplicemente sostituito list con vector, e lista con vettore, e tutto funziona come prima.

Ok, se mi avete seguito fin qui, adesso è venuto il momento delle magie, attenzione. Per prima cosa, scrivo una funzione print che stampa tutti gli elementi di una lista:

void print(list<int>::iterator a, list<int>::iterator b)
{
    list<int>::iterator p;
    cout << "[";
    for (p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

Adesso per stampare una lista mi basta scrivere:

print(lista.begin(), lista.end());

Però, se volessi stampare un vettore dovrei riscrivere la funzione… posso generalizzarla? Certo che sì, basta usare gli ingiustamente famigerati template:

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}

Ecco, adesso la funzione non dipende più dal fatto che ho una lista: basta che abbia una qualsiasi cosa che si comporti come un iteratore. Qualsiasi cosa significa anche un normale puntatore C! Ecco un esempio finale in cui metto tutto insieme:

#include <list>
#include <vector> 
#include <string> 
#include <deque> 
#include <iostream>

using namespace std;

template<class Iter>
void print(Iter a, Iter b)
{
    cout << "[";
    for (Iter p=a; p!=b; ++p) cout << *p << ", ";
    cout << "]" << endl;
}


int main()
{
    list<int> lista;
    vector<int> vettore;

    for (int i=0; i<10; i++) 
        lista.push_back(i);
    for (int i=0; i<15; i++) 
        vettore.push_back(2*i);

    deque<string> coda = {"Ok", "Panico", "insalate", "di", "cibernetica"}; 
    int array[] = {1,2,3,5,7,11,13,17};

    string str = "C++ rulez";

    print(lista.begin(), lista.end());
    print(vettore.begin(), vettore.end());
    print(coda.begin(), coda.end());
    print(array, array+8);
    print(str.begin(), str.end());

    return 0;
}

Se salvate questo file con il nome “stampa_tutto.cpp”, potete compilare con il comando:

g++ -std=c++0x stampa_tutto.cpp

Questo produce il file a.out, e lanciandolo otterrete il seguente output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ]
[Ok, Panico, insalate, di, cibernetica, ]
[1, 2, 3, 5, 7, 11, 13, 17, ]
[C, +, +,  , r, u, l, e, z, ]

Spiegazione breve (che si è fatto tardi):
Ho preparato 4 contenitori: una lista, un vettore, una coda (con il tipo deque), e un classico array C. Le ho inizializzate in modo diverso (con un ciclo for le prime due, con una inizializzazione in linea le ultime 2).
Infine, ho preparato una stringa str.

Quindi, ho chiamato print() su tutte. L’unica chiamata strana è quella per l’array C: poichè un array non è un oggetto C++ ma una struttura dati C, non ha le funzioni membro begin() e end(). Quindi, ho passato direttamente il puntatore al primo elemento (array) e il puntatore successivo all’ultimo elemento (array+8).

Infine: anche la stringa è un contenitore! In particolare, è un contenitore di caratteri! Possiede gli iteratori, e le funzioni begin() e end(), come il vettore e la lista. Per cui, non vedo perchè non potrei chiamare la mia funzione print() su di essa, non credete?

Cone questo, oggi è tutto, alla prossima!