M O N D O D I G I T A L E • n . 2 - g i u g n o 2 0 0 665

1. LA COMPILAZIONE

Q uali sono i programmi più eseguiti e menoconosciuti dall’utente? Con buona probabi-

lità la risposta è: i compilatori. Introdotto all’al-ba dell’informatica, il termine “compilazione”sta per la traduzione d’un testo sorgente, scrittoin linguaggio artificiale, in un testo pozzo1, scrit-to in un altro linguaggio.Cercheremo di descrivere i compilatori o tradut-tori nei loro aspetti concettuali, tecnici e appli-cativi, e nell’evoluzione concomitante a quelladelle architetture di calcolo e della Rete.I linguaggi progettati nei cinquant’anni passa-ti sono migliaia, quelli tuttora utilizzati pochedecine. I linguaggi, a seconda della destina-zione, si classificano in: programmazione de-gli elaboratori (per esempio, C++), interroga-zione di basi dati (per esempio, SQL), descri-zione dei documenti (per esempio, XML), pro-

getto dei sistemi digitali (per esempio, VHDL),controllo di robot ecc..Poiché sono i linguaggi programmativi quelliche stanno al centro della ricerca sulle tecnichedi compilazione, di cui beneficiano anche le al-tre categorie di linguaggi, non è limitativo par-lare della compilazione dei soli linguaggi di pro-grammazione.Con un balzo indietro di 50 anni, immaginiamola pena dei programmatori che scrivevano leapplicazioni nel linguaggio assemblatore, sce-gliendo i codici operativi, i registri e gli indirizzidei dati. All’ingrandirsi degli applicativi, le diffi-coltà crebbero, e, ad aggravare la situazione,per ogni nuovo elaboratore, il lavoro era com-pletamente da rifare: mancava totalmente laportabilità dei programmi.È storia nota l’invenzione del FORTRAN, il primoprogetto industriale d’un linguaggio e del suocompilatore. Altrettanto nota, credo, è la straor-dinaria sinergia che si ebbe negli anni 1950-60tra la linguistica, la nascente teoria degli auto-mi e dei linguaggi formali, e l’ingegneria deicompilatori.Il buon esito del compilatore FORTRAN della

DENTRO LA SCADENTRO LA SCATOLATOLARubrica a cura diFabio A. Schreiber

Dopo aver affrontato negli scorsi anni due argomenti fondanti dell’Informatica – il modo dicodificare l’informazione digitale e la concreta possibilità di risolvere problemi mediante glielaboratori elettronici – con questa terza serie andiamo ad esplorare “Come parlano i calcolatori”.La teoria dei linguaggi e la creazione di linguaggi di programmazione hanno accompagnato dipari passo l’evolversi delle architetture di calcolo e di gestione dei dati, permettendo losviluppo di applicazioni sempre più complesse, svincolando il programmatore dall’architetturadei sistemi e consentendogli quindi di concentrarsi sull’essenza del problema da risolvere.Lo sviluppo dell’Informatica distribuita ha comportato la nascita, accanto ai linguaggi perl’interazione tra programmatore e calcolatore, anche di linguaggi per far parlare i calcolatoritra di loro – i protocolli di comunicazione. Inoltre, la necessità di garantire la sicurezza e laprivatezza delle comunicazioni, ha spinto allo sviluppo di tecniche per “non farsi capire” daterzi, di quì l’applicazione diffusa della crittografia.Di questo e di altro parleranno le monografie quest’anno, come sempre affidate alla penna(dovrei dire tastiera!) di autori che uniscono una grande autorevolezza scientifica e professionalead una notevole capacità divulgativa.

La compilazione: concetti e sviluppi tecnologiciStefano Crespi Reghizzi

1 La denominazione “testo pozzo” qui usata sembra piùappropriata di quella tradizionale “testo oggetto”: infat-ti il flusso della traduzione corre, come un corso d’ac-qua, dalla sorgente al pozzo.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

0

0

0

1

66

IBM, fece fare un balzo alle applicazioni scienti-fiche, che poterono essere scritte in un linguag-gio di alto livello, e mostrò la via a altri linguag-gi importanti, come Algol 60, COBOL e Lisp.

2. STRUTTURA DEL COMPILATORE

La struttura di un compilatore degli anni 1960 èancora attuale, al livello delle parti principali. Visono più passate, ognuna elabora un testo (omeglio una rappresentazione intermedia IR) eproduce un’altro testo per la passata successiva.La prima passata legge il testo sorgente, scrittonel linguaggio da tradurre; l’ultima produce iltesto pozzo, nel linguaggio della macchina.Ogni passata, tranne l’ultima, produce dunqueuna IR, che è l’ingresso della passata successi-va. La granularità delle IR cambia da una passa-ta all’altra, dai costrutti del linguaggio sorgentefino alle istruzioni macchina.In questo schema, l’ordinamento tipico dellepassate è il seguente:❑ il parsificatore (o analizzatore lessicale-sin-tattico) verifica che il testo sorgente sia lessi-calmente e sintatticamente corretto, e lo tra-sforma in una IR, che agevola le passate suc-cessive. La IR tipica è l’albero sintattico astrat-to, AST, che mostra le inclusioni testuali tra i co-strutti del programma sorgente. Gli elementiatomici della AST sono gli identificatori, le fun-zioni, gli operatori, le costanti ecc., ossia i les-semi del linguaggio.❑ L’analizzatore semantico controlla sulla IRdel programma che le regole semantiche dellinguaggio sorgente siano rispettate: per esem-pio, le regole di conformità di tipo tra gli ope-randi delle espressioni aritmetiche.❑ Il generatore del codice sceglie le istruzionimacchina.❑ Ottimizzatori. Altre passate, poste a monte oa valle del generatore di codice, sono necessa-rie per migliorare l’efficienza del codice prodot-to. Le ottimizzazioni sono la parte più comples-sa e qualificante del compilatore.Tale schema viene denominato traduttore gui-dato dalla sintassi (SDT2), poiché la prima atti-vità è l’analisi sintattica, che si basa sullagrammatica formale (o sintassi) del linguag-gio sorgente. Per meglio comprendere, con-

viene guardare da vicino l’organizzazione deiprimi due stadi.

2.1. Teorie formali nel progettodel compilatoreLa decomposizione in passate permette di do-minare la complessità del progetto e di sfrutta-re in ciascuna passata certi metodi specializza-ti, che ora saranno tratteggiati.Dall’invenzione del FORTRAN, tutti i linguaggisono stati definiti mediante una grammaticaformale, cioè mediante delle regole sintattichequali per esempio:

frase_condizionale → if espressione_booleanathen istruzione else istru-zione

Le regole sono dette libere dal contesto (con-text-free o type 2) dal linguista Noam Chomsky,e BNF (Backus Naur Form) dagli informatici delprogetto Algol 60. I termini come frase_condi-zionale sono le classi sintattiche; la classe pro-gramma comprende tutti i testi sorgente cheobbediscono alla grammatica.Sotto la sintassi sta il lessico. Come in italianoun periodo è una serie di parole, così un pro-gramma è una sequenza di lessemi (costanti,identificatori, operatori, commenti, parole chia-ve come if ecc.).La grammatica comprende al livello inferiorele regole lessicali, esse stesse scritte sottoforma di regole libere dal contesto o più spes-so di espressioni regolari. Per esempio unacostante intera è definita dall’espressione re-golare 0 | (1 ... 9)(0 ... 9) *.La prima operazione del parsificatore è l’analisilessicale (scanning), che segmenta il testo sor-gente nei lessemi. Essa opera tramite dei sem-plici automi a stati finiti che scandiscono il filesorgente e riconoscono le classi lessicali.Successivamente il parsificatore esamina ilprogramma, ora rappresentato come stringa dilessemi, per verificare le regole sintattiche. L’al-goritmo è un automa che, oltre agli stati interni,possiede una memoria ausiliaria con modalitàdi accesso LIFO (ossia una pila).Gli algoritmi lessicali e sintattici, studiati daglianni 1960, sono efficienti: il tempo di calcolo èlineare rispetto alla lunghezza del programma,per gli algoritmi più diffusi, gli analizzatoriascendenti a spostamento e riduzione e quelli2 Syntax directed translator.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

67

0

0

0

1

discendenti del tipo predittivo, che realizzanoun automa deterministico. I due casi si differen-ziano rispetto all’ordine in cui l’albero sintatti-co è costruito: rispettivamente in ordine ascen-dente dai lessemi alla classe sintattica pro-gramma, o nell’ordine inverso, dalla radice allefoglie dell’albero, detto discendente.In pratica il parsificatore deve anche costruirel’albero sintattico astratto AST del programma edare indicazioni diagnostiche in caso di errore.Certo l’esito della parsificazione è soltanto ilprimo esame, perché un programma, pur se sin-tatticamente corretto, può violare la semanticadel linguaggio. Anche la distinzione tra corret-tezza sintattica e semantica, come quella tralessico e sintassi, è un retaggio della prima teo-ria di Chomsky.Più precisamente gli errori presenti in un pro-gramma sono classificabili come lessicali, sintat-tici e semantici. Un’altra classificazione ortogo-nale distingue gli errori statici da quelli dinamici,dove l’aggettivo “statico” indica un’attività svol-ta durante la traduzione, mentre “dinamico” si ri-ferisce a quanto sarà fatto durante l’esecuzionedel programma. Per esempio, l’assegnamentod’una costante del tipo stringa a una variabile deltipo integer è un errore semantico statico; l’usodi una variabile, come indice d’un vettore, la qua-le fuoriesca dalle dimensioni del vettore stesso,è un errore semantico, ma dinamico.La seconda passata verifica la correttezza se-mantica statica del programma. Le regole di ti-pizzazione e di visibilità (“scope”) sono quelleproprie del linguaggio sorgente. L’analizzatoreo valutatore semantico è un algoritmo ricorsivoche visita lo AST, controllando, per ogni co-strutto (per esempio, un assegnamento) l’os-servanza delle regole semantiche.A differenza di quelle sintattiche, le regole se-mantiche non sono generalmente coperte daun modello formale, anche se non sono manca-ti i tentativi di formalizzarle.Nei compilatori dei linguaggi correnti, la se-mantica è talvolta specificata in qualche nota-zione semiformale, come le grammatiche conattributi (proposte da D. Knuth nel 1968).Superato il controllo semantico, il testo è tra-dotto in una IR, che quasi sempre include la ta-bella dei simboli, concettualmente simile a unabase dati che descrive le proprietà di tutti glienti (variabili, costanti, procedure o metodi,classi ecc.) presenti nel programma. Ma non

esiste uno standard, e ogni compilatore adottala propria IR.

3. FRONTE E RETRO

Gli analizzatori sintattico e semantico non di-pendono dall’architettura del processore, masoltanto dalle specifiche del linguaggio sorgen-te. Tale parte del compilatore è detta fronte otronco comune. I metodi di progetto del troncosono assestati e descritti in molti testi sui com-pilatori (per esempio, [1, 2]).Sul tronco si innestano, come le branche d’unalbero, altre passate dipendenti dalla macchi-na, note come retro (back-end), tra le qualispicca il generatore di codice.La divisione tra fronte e retro facilita il progettodel compilatore, sia separando gli ambiti di com-petenza dei progettisti, sia rendendo possibile ilriuso di una o dell’altra parte. Così il tronco d’uncompilatore per il C potrà essere riutilizzato, so-stituendo il generatore per la macchina A conquello per la macchina B. Viceversa due tronchiper il linguaggio C e C++ possono stare a montedello stesso generatore di codice. Naturalmente,affinché il riuso sia possibile, le interfacce IR de-vono essere unificate. Ciò di norma avviene al-l’interno d’una piattaforma di compilazione, pro-gettata da un’industria o organizzazione, per unagamma di linguaggi sorgente e di architetture;mentre l’interoperatività di compilatori di diversaorigine è ostacolata dall’assenza di standard.

4. META-COMPILAZIONE

Ben presto infastidì i progettisti la ripetizione delprogetto del parsificatore, al mutare del linguag-gio sorgente: di qui l’idea di produrre il parsifica-tore con un programma generatore, parametriz-zato con le regole lessicali e sintattiche del lin-guaggio sorgente. Il generatore legge le regole (imeta-dati) e produce il programma del parsifica-tore specifico. Molti compilatori sono stati cosìprodotti, grazie alla disponibilità di buoni stru-menti, dal classico lex/yacc (flex/bison nella ver-sione libera di GNU) che produce un parsificatoreascendente in C, al più recente ANTLR, che gene-ra un parsificatore a discesa ricorsiva in Java.Perché non generare automaticamente anche l’a-nalizzatore semantico, che è assai più comples-so del parsificatore? L’idea ebbe comprensibil-mente molti fautori, e alcuni strumenti (parame-

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

0

0

0

1

68

trizzati da una specifica semiformale delle azionisemantiche nota come grammatiche con attribu-ti) ottennero qualche diffusione, per poi finire indisarmo. Due fattori giocano a sfavore dei meta-compilatori semantici: la mancanza di una teo-ria formalizzata, semplice e condivisa; e il fattoche le tecniche di programmazione orientate aglioggetti già permettono un buon riuso di quellaparte del compilatore che tratta le proprietà del-le entità dichiarate nel programma sorgente.L’uso di librerie di classi parametriche rispettoal linguaggio sorgente o all’architettura pozzo èfrequente nelle piattaforme di compilazionesulle quali ritorneremo più avanti.

5. GENERAZIONE DEL CODICE

La più ovvia dipendenza dalla macchina vienedall’architettura dell’insieme di istruzioni (ISA).Fino agli anni 1980 il generatore di codice erascritto a mano da uno specialista del processore,abile nello sfruttare ogni istruzione. Ma la cre-scente complessità delle istruzioni delle macchi-ne CISC3 e la difficile manutenzione del generato-re, stimolarono le ricerche sulla produzione auto-matica dei generatori. Ebbero successo i genera-tori di generatori di codice, impostati mediante laricerca di forme (vedasi per esempio, [3]) sull’al-bero della IR. In breve, ogni istruzione macchina(per esempio, un’addizione tra un registro e unacella di memoria) è descritta formalmente comeun pattern, ossia un frammento. La IR del pro-gramma deve essere ricoperta (tiling) con le for-me corrispondenti ai pattern della macchina. Poi-ché molte ricoperture sono possibili, l’algoritmodeve orientare la scelta con opportune euristicheverso la copertura di costo minimo, dove il costoè il tempo di esecuzione del codice macchina.Occorre dire che la ricerca della ricopertura otti-male dell’albero IR risulta molto più facile sel’architettura è del tipo RISC4, nel qual caso èagevole scrivere a mano il generatore di codice.

6. ANALISI STATICA DI FLUSSO

Per rendere eseguibile il codice, manca ancoraun aspetto essenziale: la scelta dei registri delprocessore; infatti il passo precedente, per non

affrontare in un colpo solo tutte le difficoltà, hagenerato delle istruzioni che usano un numeroillimitato di registri. Ma un cattivo uso dei regi-stri provoca inutili copiature di dati, nonché ral-lentamenti dovuti agli accessi alla memoria. Iprocessori moderni dispongono di tanti regi-stri, che se ben sfruttati permettono di limitaregli accessi alla memoria.L’assegnazione dei registri alle variabili è unproblema di conflitto nell’uso di risorse scarse;poiché la ricerca della soluzione ottima è com-plessa, si deve ricorrere a metodi euristici.Due variabili possono stare nello stesso registrose, in nessun punto del programma, entrambi ivalori sono necessari: si dice che gli intervalli divita delle due variabili sono disgiunti. Per asse-gnare i registri, è necessario calcolare gli inter-valli di vita delle variabili. Il programma, ormai incodice macchina, è rappresentato dal suo grafodi controllo (CFG5), un’astrazione in cui ci si limi-ta a guardare quali variabili siano lette o calcola-te da ogni istruzione. Gli insiemi delle variabilivive in ogni punto del CFG sono calcolati risol-vendo con metodo iterativo certe equazioni diflusso, facilmente ricavabili, istruzione per istru-zione. La teoria delle equazioni di flusso (pre-sente nei riferimenti [1, 2, 3, 4]) si fonda sull’al-gebra dei semi-anelli commutativi e trova appli-cazioni, non solo nella compilazione, ma anchenell’analisi e nella verifica dei programmi.Risolte le equazioni, il compilatore, impiegan-do un metodo euristico, assegna registri diversialle variabili che hanno intervalli di vita sovrap-posti, senza superare per altro il numero di re-gistri disponibili. In caso d’impossibilità, essogenera a malincuore del codice (spillatura) percopiare in memoria e poi riprendere i valori dicerte variabili.

7. OTTIMIZZAZIONI: UN CATALOGOSENZA FINE

Ora il codice macchina è eseguibile, ma le sueprestazioni sarebbero inaccettabili, se non ve-nisse migliorato con tante astute trasformazio-ni. L’ottimizzazione è la parte più impegnativadel compilatore, la cui complessità cresce conquella dei processori.Conviene distinguere le trasformazioni indipen-

3 Complex instruction set computer.4 Reduced instruction set computer. 5 Control flow graph.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

69

0

0

0

1

denti dalla macchina dalle altre. Le prime sonoefficaci su ogni architettura. Si pensi al calcolod’una espressione X + Y · Z che compare duevolte nel programma, senza che le variabilicambino valore. Il compilatore salva in un regi-stro il risultato del primo calcolo, e sostituisce ilsecondo con la copiatura del registro.Un catalogo ragionato delle numerosissimetrasformazioni esistenti è in Muchnick [4]. Unaquestione delicata è l’ordine in cui eseguire letrasformazioni; infatti una modifica, apparente-mente non migliorativa, può abilitare altri mi-glioramenti.Per esemplificare le ottimizzazioni dipendentidalla macchina, possiamo soffermarci su dueimportanti aspetti architetturali.

8. GERARCHIA DI MEMORIA

Per ridurre le attese (latenze) dovute alle ope-razioni sulla memoria RAM, le macchine usa-no memorie cache, più veloci ma molto piùpiccole. Un programma che con un ciclo itera-tivo spaziasse su troppe celle di memoria va-nificherebbe l’efficacia della cache, che do-vrebbe essere continuamente caricata e scari-cata dalla memoria.Concentrando l’attenzione sulle parti del pro-gramma eseguite più intensamente (i cosiddet-ti nuclei o punti caldi), l’ottimizzatore riorganiz-za i cicli in modo da operare su uno spazio dimemoria contenibile nella cache. Inoltre essoinserisce anticipatamente nel codice le istru-zioni di precaricamento (prefetch), che caricanola cache con i dati, in anticipo rispetto al mo-mento in cui saranno richiesti.

9. PARALLELISMO SCHEDULAZIONEE PREDICAZIONE

Le macchine offrono tante forme di paralleli-smo: pipeline, disponibilità di più unità funzio-nali, istruzioni composte da più codici operativi(architettura VLIW6), fino alle architetture mul-tiprocessore.Per sfruttare il pipeline, un buon codice deverarefare le istruzioni di salto. Una trasforma-zione migliorativa consiste nell’ingrandire ledimensioni dei blocchi basici (una serie diistruzioni non interrotte da salti né da etichet-

te), magari srotolando il corpo di un ciclo ite-rativo due o più volte.Le architetture VLIW bene illustrano il proble-ma della schedulazione delle istruzioni, ossiadel loro riordino rispetto all’ordine originale,allo scopo di utilizzare al meglio in ogni istan-te di clock tutte le unità funzionali della mac-china.La schedulazione è semplice per un blocco ba-sico, ma diventa intrattabile per l’intero pro-gramma. Il compilatore impiega una gammadi schedulatori, appropriati per diverse partidel programma: l’algoritmo di list scheduling(simile al job shop scheduling della ricercaoperativa) si addice alla parti acicliche; l’ele-gante algoritmo di software pipelining e mo-dulo scheduling si applica ai cicli più caldi delprogramma, l’algoritmo di trace schedulingprivilegia la traccia del programma eseguitapiù spesso, anche al costo di duplicare del co-dice nelle altre parti.Un altro meccanismo, spesso combinato con ilparallelismo, è l’esecuzione speculativa e pre-dicativa del codice. L’idea è che nessuna unitàfunzionale deve essere lasciata inerte. Se peresempio, un moltiplicatore fosse disponibile,ma la o le istruzioni in fase di esecuzione non lorichiedessero, sarebbe un peccato. Il compila-tore, analizzando il codice, sceglie una futura edistante istruzione di moltiplicazione da fareseguire anticipatamente, pur senza la certez-za che il flusso di controllo la raggiungerà.Per confermare l’effetto dell’istruzione, quan-do si avrà la certezza della sua utilità, un bit opredicato, riceve il valore da un’appositaistruzione.L’esecuzione predicativa non è indicata per di-spositivi alimentati a batteria, perché consu-ma energia per eseguire operazioni talvoltainutili.

10. ELABORAZIONE DI FLUSSIMULTI MEDIALI

La diffusione dei dispositivi multi-mediali hacreato una nuova classe di coprocessori di flus-so (stream), realizzati con architetture moltopiù veloci dei microprocessori, per tali elabora-zioni. L’elaborazione consiste in un ciclo diistruzioni ripetute indefinitivamente sul flussod’ingresso, per produrre quello d’uscita. Lapresenza di numerose unità funzionali inter-6 Very long instruction word.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

0

0

0

1

70

connesse da una rete rende difficile la program-mazione manuale e motiva lo sviluppo di com-pilatori capaci di estrarre da un programma ge-nerico le parti destinate al coprocessore di flus-so e di tradurle nelle istruzioni del coprocesso-re stesso. La traduzione presenta difficili pro-blemi di assegnazione ottimale delle istruzionialle unità funzionali.L’esempio dei processori di flusso è emblema-tico della compilazione per architetture specia-li, un campo in sviluppo grazie alla flessibilitàofferta dalle moderne tecniche di progetto del-lo hardware.Ogni trasformazione ottimizzante dà un piccolocontributo (si spera positivo ma non sempre ècosì!) all’efficienza del codice macchina. Ag-giungendo con abilità e tenacia qualche puntopercentuale qua e là, si ottengono le buoneprestazioni che qualificano i compilatori.

11. INTERPRETAZIONEE COMPILAZIONE DINAMICA

La Rete ha fatto emergere nuove esigenze,perché gli applicativi possono essere trasferitida una macchina remota fornitrice a quelladell’utente, proprio al momento dell’esecu-zione. Non essendo praticamente possibiletrasferire i codici binari, perché la macchinautente è in generale ignota, la soluzione, af-fermatasi con il linguaggio Java, è l’interpreta-zione. L’applicativo, tradotto dal fornitore inun linguaggio intermedio o virtuale (ByteCo-de) indipendente dalla macchina, è spedito al-la macchina destinataria, dove è eseguito dauna macchina virtuale VM. In questo modo l’o-nere di adattare il linguaggio Java all’architet-tura è spostato dal mittente al destinatariodell’applicativo.Ma la velocità dell’applicativo interpretato èalmeno un ordine di grandezza inferiore, ri-spetto al codice compilato. Come conciliarel’indipendenza dalla macchina con l’efficien-za? La risposta sta nella compilazione dinami-ca (anche detta JIT just in time). Accanto all’in-terprete, vi è un traduttore che converte leistruzioni virtuali in quelle del processore. Poi-ché, quando gira il traduttore, l’applicativo èfermo, e l’utente si spazientisce, occorre ri-durre il tempo di compilazione. Tipicamente,l’esecuzione inizia mediante la macchina vir-tuale, poi parte il compilatore dinamico che

traduce le parti calde, limitando le ottimizza-zioni a quelle meno faticose. Per esempio l’as-segnazione dei registri fisici è fatta con algo-ritmi più sbrigativi di quelli utilizzati da uncompilatore statico. Occorre preliminarmenteidentificare le parti calde, per mezzo di tecni-che di analisi statica e di conteggio dinamico(profiling) delle istruzioni eseguite.Il compilatore dinamico deve essere program-mato con estrema cura, per portare frutto. Unarassegna della compilazione dinamica è in [5].Non sempre però la compilazione dinamica èpossibile. I piccoli dispostivi, come i telefonini,non hanno sufficiente memoria per il compila-tore dinamico. Per essi, la macchina virtuale re-sta l’unica possibilità, che deve sfruttare ognipossibile risparmio di memoria, senza per altrosacrificare la velocità.

12. ALTRI USI DELLA COMPILAZIONEDINAMICA

La compilazione dinamica ha altre applicazioni:la traduzione da binario a binario trasforma, almomento dell’esecuzione, il codice macchinadella macchina A in quello della macchina B,curando anche la conversione delle chiamate disistema operativo. Questa tecnica è molto uti-lizzata per emulare un‘architettura ISA su diun’altra, per esempio, l’architettura Intel x86sull’architettura TransMeta.La ottimizzazione continua si applica sulle mac-chine, per esempio, i serventi delle basi dati, inciclo continuo, con programmi in cui il profilodel carico da eseguire cambia, mettiamo, tra ungiorno e il successivo.Il codice macchina potrà essere ottimizzato infunzione del profilo attuale del carico. Peresempio, se una certa procedura in un certogiorno è invocata con un parametro fissato suun valore costante, il compilatore può specia-lizzare il corpo della procedura, propagando ilvalore costante e eliminando eventuali test sulvalore del parametro.In un campo diverso, con dispositivi a batte-ria, si usa la compilazione dinamica per ridur-re la potenza elettrica assorbita. È noto che lapotenza cresce con il quadrato della frequen-za del clock e che i nuovi processori dispongo-no di comandi per variare la frequenza di lavo-ro. Se l’applicativo in esecuzione ha sufficientimargini rispetto alle scadenze di tempo reale

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

71

0

0

0

1

da rispettare, la frequenza può essere rallen-tata, riducendo il consumo. È un monitore di-namico che valuta le opportunità e produce leistruzioni necessarie.

13. INFRASTRUTTURE APERTEPER LA COMPILAZIONE

Oggi chi deve sviluppare un compilatore ha lapossibilità di partire dall’esistente e di modifi-carlo, e solo raramente si impostano da zerodei nuovi traduttori. Molti compilatori di pro-prietà di aziende sono l’evoluzione di progetti,anche molto vecchi, che via via si adeguano perle nuove architetture. Inoltre varie comunitàhanno progettato e mantengono aggiornate lecosiddette infrastrutture aperte (o piattaforme)per la compilazione, veri progetti collettivi dicomponenti software per la costruzione deicompilatori.La maggior parte delle piattaforme opera suilinguaggi più classici e diffusi: C, C++, Java e C#.Per inciso, nonostante la fioritura di tante pro-poste linguistiche, C e C++ restano la scelta pre-ferita di quanti devono scrivere i compilatori e ilsoftware di sistema.Altre comunità lavorano sui linguaggi funziona-li e sui linguaggi interpretati di alto livello, co-me Python.Limitandoci alle infrastrutture più diffuse, lapiù veneranda è SUIF della Stanford Univer-sity, “una piattaforma libera progettata peraiutare la ricerca collaborativa sui compilatoriottimizzanti e parallelizzanti”. È facile scriverein C++ le proprie passate di compilazione ap-poggiandosi alle pratiche rappresentazioni IRdi SUIF. Sono disponibili i fronti per C, C++,Fortran, e Java, e i retro per vari microproces-sori. Una funzionalità, forse sorprendente mautilissima, ritraduce in C un programma, dallinguaggio intermedio IR di SUIF. Ciò permettedi analizzare l’effetto delle ottimizzazioni pro-dotte e di confrontarle con quelle di compila-tori rivali.Il grande progetto GCC (GNU Compiler Collec-tion) fa capo alla organizzazione GNU e mira afornire una linea di compilatori liberi, dellastessa qualità di quelli industriali. Vi sono fron-ti per C, C++, Fortran, Java e Ada e retro per x86e altre macchine.Una gemmazione del progetto, DotGNU, si è ri-volta ai linguaggi programmativi e per i servizi

di Rete della Microsoft. Si ricorda che l’insiemeDot Net di Microsoft è principalmente un lin-guaggio intermedio, ispirato dal ByteCode diJava, di cui allarga le potenzialità e l’idoneitàper diversi linguaggi sorgente.L’affermarsi del progetto GCC ha l’effetto posi-tivo di consolidare certi standard di fatto per lerappresentazioni intermedie, e di sottrarre losviluppo dei linguaggi al controllo esclusivo diuna o poche aziende.Sempre per le piattaforme Dot Net, ha avutobuona diffusione l’infrastruttura MONO, liberama sponsorizzata da Novell.Per il linguaggio Java esistono varie disponibi-lità di macchine virtuali e di compilatori dinami-ci; Kaffe è una delle più note. Sono questi peròdei progetti di minor respiro e di sopravvivenzatalvolta incerta.

14. IL FUTURO

L’innovazione nello sviluppo dei linguaggi diprogrammazione segna il passo, e i migliori trai nuovi linguaggi che si affacciano mi sembranodelle abili rivisitazioni dei concetti classici, peradattarli a aspettative e motivazioni alquantomutate. Il progetto dei loro compilatori (ossiadei fronti) sarà un lavoro routinario per i profes-sionisti della compilazione.Le direzioni di principale innovazione per lacompilazione sono quelle attinenti allo svilup-po di nuove architetture di calcolo.Per i processori, la diffusione a breve e mediotermine delle architetture (esempio, Intel mul-ti-core) con più processori interconnessi in re-te, impone una complessa sinergia con il com-pilatore, al fine di parallelizzare e ripartire ilcodice, prima sui processori e poi sulle lorounità funzionali.In un’altra direzione, per portare i linguaggi suipiù piccoli dispositivi, sarà sempre necessarioun artigianato di grande abilità, con attenzionealle tecniche di programmazione più compattee efficienti.Più a lungo termine c’è chi prevede una drasti-ca caduta di affidabilità dei processori, causa-ta da guasti transienti, provocati sui piccolis-simi transistori delle fluttuazioni ambientali.In tale prospettiva, il compilatore sarà chia-mato a generare codici eseguibili ridondanti,capaci di scoprire, e mascherare gli errori dibasso livello.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 6

1

0

0

0

1

72

Per quanto riguarda le Reti, il supporto neces-sario per far funzionare in modo sicuro i servizie i programmi mobili sarà necessariamente di-namico, e la compilazione dinamica dovrà per-fezionare i propri metodi di progetto, di convali-da e di manutenzione.

Bibliografia

[1] Crespi Reghizzi S.: Linguaggi formali e compila-zione. Pitagora, Bologna 2006.

[2] Aho A., Sethi R., Ullman J., Lam M.: Compilers:Principles. Techniques, and Tools, AddisonWesley, 2006.

[3] Appel A.: Modern Compiler Implementation inJava. Cambridge University Press, 2002.

[4] Muchnick S.: Advanced Compiler Design andImplementation. Morgan Kaufmann, 1997.

[5] Duesterwald E.: Dynamic Compilation. In SrikantY. N., Shankar Priti (a cura di), The Compiler Desi-gn Handbook. CRC Press, 2002.

[6] Ujval Kapasi et al.: Programmable Stream Pro-cessors. Computer, Vol. 36, n. 8, p. 54-62., 2003.

STEFANO CRESPI REGHIZZI lavora nel Dipartimento di Elettronica e Informazione del Politecnico di Milano. Il grup-po di ricerca da lui guidato studia la teoria dei linguaggi artificiali e progetta compilatori e macchine virtualiper i moderni processori.Coordina il dottorato di ricerca in Ingegneria dell'Informazione: automatica, elettronica, informatica e teleco-municazioni. Insegna i corsi di Linguaggi formali e compilatori e di Analisi e ottimizzazione dei programmi, perla laurea in ingegneria informatica.Ingegnere elettronico, ha conseguito il dottorato in computer science alla University della California di Los An-geles. Ha insegnato e collaborato scientificamente nelle università di Berkeley, Lugano, Pisa, Santiago de Chi-le, Stanford e Parigi. È uno dei fondatori del programma scientifico internazionale “Automata theory frommathematics to applications” della ESF, la fondazione europea per la scienza. Tra le sue opere sulla compila-zione si ricorda il libro “Linguaggi formali nelle scienze della comunicazione”, rivolto a lettori di matrice uma-nistica e il testo universitario “Linguaggi formali e compilazione” per gli ingegneri informatici.E-mail: crespi@elet.polimi.it