Maurizio Gabbrielli Simone Martin i • • I 1n u a • • I r o r a a z i o n e Principi e paradigmi Seconda edizione McGraw-Hill Italia .. tutti per uso personatale ciscn per uso diverso a quetaltalo personatale in A Francesca e Antonella, che non vorranno mai leggere questo libro, he hanno e ihuito elo 1na ( 011!1 u {t.i1( \(ti, l:'te A Costanza, Maria e Teresa, che forse lo leggeranno, ma che hanno fatto dl tutto per non farcelo scriv Prefazione Ho accettato con grande piacere l'invito r1vo1tomi a scrivere queste poche righe di prefazione per almeno due ragioni. La prima è che la richiesta mi viene da due colleghi che ho sempre tenuto in grandissima considerazione, fin dal tempo in cui li ho potuti conoscere ed apprezzare come studenti prima e giovani ricercatori poi. La seconda ragione è che il tè~to n10Ito vicino dl libro 12he i(l dv1ei -.en1p1c ~ voluto scrivere e, per ragioni varie, non ho mai scritto. In particolare, l'approcc10 seguito dal libro è quello che io stesso ho seguito nell'organizzazione di vari corsi di linguaggi di programmazione che ho insegnato, in diverse fasi e sotto diverse etichette, per quasi trent'anni. L'approccio, schematizzato in due parole, è quello di introdurre concetti 1 generali (sia dei meccanismi linguistici sia delle corrispondenti strutture di im- plementazione) in modo indipendente da linguaggi specifici e solo in un secondo tempo collocare nello schema i "linguaggi veri". Questo è l'unico approccio che permette di mettere in evidenza le similitudini tra linguaggi (ed anche tra para- digmi) apparentemente molto diversi. Allo stesso tempo si rende così più facile il compito di imparare linguaggi diversi. Nella mia esperienza di docente, gli ex- studenti si ricordano i principi appresi nel corso anche dopo molti anni e continua- no ad apprezzarne l'approccio, che ha loro permesso di adattarsi alle evoluzioni delle tecnologie senza grandi difficoltà. Il testo di Gabbrielli e Martini ha come riferimento prevalente un corso della laurea (triennale) in Informatica. Per questa ragione non ha prerequisiti complessi e affronta l'argomento trovando un perfetto equilibrio tra rigore e semplicità. Par- ticolarmente apprezzabile e riuscito è lo sforzo di mettere in luce il collegamento con alcuni "pezzi di teoria" importanti (come i linguaggi formali, la calcolabilità, la semantica), che il libro giustamente richiama, anche perché in molti corsi di laurea questi argomenti non vengono più trattati. Giorgio Levi ' Introduzione Facilius per partes in cognitionem totius adducimur. (Seneca, Epist., 89, I) L'apprc11d1mento di u11 linguaggill di pr<>grammaL1<>nc {,O~titui::.ce per 1110Iti $lU- denti 11 rito d'1n1ziazione all'informatica. S1 tratta di un passaggio importante, ma che presto si rivela insufficiente: tra gli attrezzi del mestiere ci sono molti linguag- gi ed una competenza importante del bravo informatico è quella di saper passare da un linguaggio all'altro (e di apprenderne di nuovi) con naturalezza e velocità. Questa competenza non la si acquisisce soltanto imparando ex novo molti linguaggi diversi. Come le lingue naturali, anche i linguaggi di programmazione hanno tra loro somiglianze, analogie, fenomeni di importazione dall'uno all'altro, genealogie che ne influenzano le caratteristiche. Se è impossibile imparare bene decine di linguaggi di programmazione, è possibile invece conoscere a fondo i meccanismi che ispirano e guidano il progetto e l'implementazione dì centinaia di linguaggi diversi. Questa conoscenza delle "parti" facilita la comprensione del "tutto" costituito da un nuovo linguaggio, fornendo una competenza metodologi- ca fondamentale nella vita professionale dell'informatico, in quanto consente di anticipare l'innovazione e di sopravvivere ali' obsolescenza delle tecnologie. ' E per questi motivi che un corso sugli aspetti generali dei linguaggi di pro- grammazione è, in tutto il mondo, un passaggio chiave della formazione avanzata (universitaria o professionale) di un informatico. Relativamente ai linguaggi di possedere programmazione, le competenze fondamentali che un informatico deve sono almeno di quattro tipi: • gli aspetti propriamente linguistici; • come i costrutti linguistici possono essere implementati ed il relativo costo; • gli aspetti architetturali che influenzano l'implementazione; • le tecniche di traduzione (compilazione). È raro che un singolo corso possa affrontare tutti e quattro questi aspetti. In par- ticolare, la descrizione degli aspetti architetturali costituisce un argomento suffi- 1 cientemente complesso ed elaborato da meritare una trattazione separata. Gli altri aspetti sono il contenuto primario di un corso generale sui linguaggi di program- mazione e costituiscono il contenuto principale di questo testo. .. La letteratura anglosassone, a differenza di quella in lingua italiana, è ricca . . . . . . . . . . . . . . . . ~~ xviii Introduzione lettore avanzato che conosca già diversi linguaggi di programmazione, che abbia una competenza non superficiale dei meccanismi di base fondamentali, che non si spaventi davanti a frammenti di codice espressi in linguaggi a lui ignoti (perché riesce a comprenderli per analogia o per differenza da quelli che già conosce). Si tratta di testi, dunque, che potremmo chiamare di ''linguaggi comparati": estesi, approfonditi, stimolanti. Ma troppo estesi e approfonditi (in una parola: difficili) per lo studente che inizia il suo cammino con un solo (o al massimo due) linguaggi di programmazione e che deve ancora approfondire concetti di base. 1 Questo testo intende colmare questa lacuna. Gli esperti vedranno che l'indi- ce degli argomenti ripercorre in larga misura i temi classici. Ma questi stessi temi sono trattati in modo elementare, cercando di assumere come prerequisiti solo il minimo indispensabile e sforzandosi di non fare un catalogo delle opzioni possi- bili nei diversi linguaggi di programmazione esistentì. Il lettore di riferimento è quello "he L-Ono~ct (bene) un l1nguagg10 (per e~e1np10 Pa~cal, C, C++.o Java)~ meglio se ha avuto anche una qualche esposizione ad un altro linguaggio o ad un altro paradigma. Si sono evitati riferimenti consistenti a linguaggi ormai desueti e gli esempi di codice sono solo raramente espressi in uno specifico linguaggio di programmazione: il testo usa con libertà una sorta di pseudolinguaggio (ispirato nella sua sintassi concreta a C e Java), cercando di descrivere così gli aspetti più rilevanti che uniscono i diversi linguaggi. Di tanto in tanto un "riquadro" a capo pagina presenta un approfondimento, o il richiamo di una nozione di base, o qualche dettaglio specifico dei linguag- gi più comuni (C, C++, Java 5.0; ML e LISP per i linguaggi funzionali; PRO- LOG per i linguaggi logici). Il materiale dei riquadri può quasi sempre essere tranquillamente omesso in una prima lettura. Tutti i capitoli presentano una breve serie di esercizì. intesi come banco di prova per la comprensione del materiale. Non vi sono esercizi davvero difficili o che richiedano più di una decina di minuti per esser risolti. Il Capitolo 5 (Fondamenti) affronta temi che solitamente non sono trattati in ' un testo di linguaggi di programmazione. E tuttavia naturale, discutendo di se- mantica statica e confrontando tra loro linguaggi, chiedersi quali siano i limiti del!' analisi statica dei programmi e se quello che si può fare in un linguaggio si possa fare anche in un altro. Invece che rimandare ad altri testi, vista la rilevan- za sia culturale sia pragmatica di queste questioni, abbiamo deciso di rispondere direttamente a queste domande. In modo informale, ma rigoroso, nel contesto di poche pagine viene presentata l'indecidibilità del problema della fermata e l'equi- valenza dei linguaggi di programmazione quanto alle funzioni calcolabili. Questo permette di esporre lo studente, che non sempre ha nel suo curriculum un cor- so completo sui ''fondamenti", ai risultati principali relativi alle limitazioni dei procedimenti di calcolo, che riteniamo fondamentali per la sua formazione. Insieme ai principi, il testo introduce anche ai principali paradigmi di pro- grammazione: quello orientato agli oggetti, quello funzionale, quello logico, quel- lo concorrente. La necessità di realizzare un testo introduttivo e, insieme, di man- tenerne l'estensione ìn un numero di pagine ragionevole, sp1ega l'esclusione di temi importanti, quali per esempio i linguaggi di scripting. • Introduzione XIX Uso del testo Il testo è in primo luogo un manuale universitario, ma è anche adatto allo studio personale del professionista che voglia approfondire la propria conoscenza dei meccanismi che stanno dietro ai linguaggi che utilizza. La scelta dei temi e lo stile di presentazione sono stati ampiamente influenzati dall' esperien- za di insegnamento di questi contenuti presso il corso di laurea in Informatica della Facoltà di Scienze Matematiche, Fisiche e Naturali del!' Alma Mater Studio rum - Università di Bologna. Nella nostra esperienza, il testo può coprire due moduli di sei crediti, posti al secondo o terzo anno della laurea triennale. Un modulo può essere dedicato agli aspetti relativi alle macchine astratte e alle tecniche di compilazione (Capitoli da 1 a 5); un altro può coprire gli aspetti fondamentali (diciamo i 4/5) dei Capitoli da 6 a 12 e accennare ad uno dei restanti paradigmi. Al crescere della maturità degli <.tudenti, aumenta ovviamente la quantità di materiale che può essere presentato. La seconda edizione La seconda edizione, oltre ad una revisione generale del materiale e alla correzione dei refusi, contiene tre capitoli del tutto nuovi. In primo luogo la semplice trattazione della sintassi del Capitolo 2 è stata estesa con la presentazione, sintetica ma non superficiale, dei linguaggi regolari e degli analizzatori lessicali (Capitolo 3) e, quindi, dei linguaggi liberi e degli analizzatori sintattici (Capitolo 4 ). Entrambi i capitoli presentano i principali risultati teorici e le loro applicazioni alla tecnologia dei compilatori. In questo modo, il testo può essere usato come unico manuale in un corso che voglia trattare in modo non superficiale anche dei tradùttori. I due capitoli hanno un carattere un po' più matematico degli altri, ma non richiedono nessun prerequisito che vada oltre il principio di induzione. Il terzo capitolo aggiunto a questa seconda edizione presenta la programma- zione concorrente. Anche se una trattazione esauriente di questa tematica richie- derebbe (almeno) un volume a sé, l'assenza di qualsiasi riferimento alla concor- renza ci è sembrata una lacuna troppo vistosa in un testo sui linguaggi di pro- grammazione, visto che una parte significativa del software oggi usa programmi concorrenti, dal livello del sistema operativo sino a quello dei servizi sul web. Il capitolo illustra le principali problematiche che si presentano passando dai pro- grammi sequenziali a quelli concorrenti, insieme alle relative soluzioni. Abbiamo cercato di offrire un panorama adeguato delle principali tecniche e dei costrutti linguistici per realizzare meccanismi di interazione, sincronizzazione e comuni- cazione fra programmi o processi concorrenti. Seguendo il principio informatore di tutto il testo non abbiamo fatto riferimento ad un linguaggio specifico, anche se abbiamo cercato di concretizzare alcune nozioni esaminando il caso dt Java. Per rendere il testo più agile e adattabile alle diverse esigenze, alcuni appro- 1 fondimenti non sono inclusi nel testo, ma sono disponibili sul sito www.ateneonline.1t/gabbr1elli. La loro presenza è indicata con l'icona Approfondimento xx Introduzione Ringraziamenti La nostra gratitudine a Giorgio Levi va ben al di là del fat- to che ha avuto la bontà di scrivere la Prefazione. Entrambi dobbiamo a lui le nostre prime conoscenze dei meccanismi che sottostanno ai linguaggi di pro~ grammazione: il suo insegnamento ritorna in questo libro in modo tutt'altro che marginale. Ugo Dal Lago ha composto parte delle figure usando METAPOST. Andrea Aquino, Sara Bergonzoni, Matteo Brucato, Ferdinanda Camporesi, Cinzia Di Giu- sto, Jacopo Mauro, Wilmer Ricciotti, Francesco Spegni e Paolo Tacchella hanno letto e commentato le bozze di alcuni capitoli. Un ringraziamento sincero ai tanti lettori che hanno segnalato refusi ed errori nella prima edizione. • Macchine astratte I 1necca111sm1 d'a~trdl1one gioca110 un ruolo cruciale nell"tnformat1ca in quanto, isolando gli aspetti rilevanti in un particolare contesto, permettono di dominare la complessità insita nella maggior parte dei sistemi di calcolo. Nell'ambito dei linguaggi di programmazione tali meccanismi sono fondamentali sia dal punto di vista teorico, dato che numerosi concetti importanti possono essere fonnalizzati opportunamente in termini d'astrazione, sia in senso pratico, visto che i linguaggi di programmazione odierni usano diffusamente costrutti per l'astrazione. Una delle nozioni più generali che coinvolgono l'astrazione è quella cli mac- china astratta. In questo capitolo vedremo come tale nozione sia intimamente collegata a quella di linguaggio di programmazione e come essa permetta cli de- scrivere che cosa sia l'implementazione di un linguaggio, senza per questo doverci addentrare nei dettagli specifici di una particolare implementazione. Per far questo descriveremo in termini generali l'interprete ed il compilatore di un linguaggio. Vedremo infine come le macchine astratte possono essere strutturate in gerarchie per descrivere e realizzare sistemi software complessi. ·t 1.1 La nozione di macchina astratta e l'interprete Il termine "macchina" in questo contesto si riferisce evidentemente alla macchina calcolatore. Come sappiamo, un calcolatore (elettronico, digitale) è una macchina fisica che permette di eseguire degli algoritmi, opportunamente formalizzati per poter essere "comprensibili" ali' esecutore. Intuitivamente una macchina astratta non è altro che un'astrazione del concetto di calcolatore fisico. Per poter essere effettivamente eseguiti gli algoritmi devono essere opportu- namente formalizzati in termini dei costrutti di un linguaggio di programmazione. In altri termini, gli algoritmi che vogliamo eseguire devono essere rappresentati mediante le istruzioni cli un opportuno linguaggio di programmazione C., linguag- gio che sarà definito formalmente da una specifica sintassi e da una precisa seman- tica (si veda il Capitolo 2). Per il momento non ci serve specificare ulteriormente la natura di C.: ci basta sapere che la sintassi di C. permette di utilizzare un certo insieme finito di costrutti, detti istruzioni, che permettono di comporre i program- mi. Un programma di C. (o programma scritto in C.) dunque non è altro che un 2 Capitolo 1 Interprete Controllo sequenza Dah Memoria Controllo Operaz1on1 dati . Programma Ge:.t1one memona Figura 1.1 La struttura di una macchina astratta. insieme finito di istruzioni di .C. Con queste premesse, vediamo una definizione centrale in questo capitolo. Definizione 1.1 (Macclùna Astratta) Supponiamo che sia dato un linguaggio di programmazione L. Definiamo una macchina astratta per ,C, e la indichiamo con Mc, un qualsiasi insieme di strutture dati e di algoritmi che pennettano di memoriz;zare ed eseguire programmi scritti in J:,, Quando non c'interessa specificare il linguaggio C, parleremo semplicemente M, di macchina astratta omettendo l'indice. Vedremo fra poco alcuni esempi di macchina astratta e come questa si possa effettivamente realizzare; per il momento soffermiamoci sulla sua struttura. Come illustrato in Figura 1.1. una generica macchina astratta M .e è composta da una memoria e da un interprete. La memoria serve per immagazzinare dati e programmi mentre l'interprete è il componente che esegue le istruzioni contenute nei programmi, come vediamo meglio nel prossimo paragrafo.