Architettura di un Compilatore

Il comportamento di un compilatore può essere schematizzato in due fasi: front end e back end.

Prendiamo per esempio il seguente programma.
int main(){
int i = 0;
}

Stadio di front end

Analisi lessicale : Attraverso un'analizzatore lessicale, spesso chiamato scanner o lexer, il compilatore divide il codice sorgente in tanti pezzetti chiamati token.
Lo scanner legge una sequenza di caratteri ('i','n','t',' ','m','a','i','n','(',')','{',etc.)
rimuove i commenti e spazi bianchi e crea una sequenza di tokens('int','main','(',')','{','int',etc.)
I token sono gli elementi minimi (non ulteriormente divisibili) di un linguaggio, ad esempio parole chiave (for, while), nomi di variabili (pippo), operatori (+, -, <<).
Analisi sintattica : L'analisi sintattica prende in ingresso la sequenza di token generata nella fase precedente ed esegue il controllo sintattico che verifica se i la grammatica(insieme di regole) definita per un linguaggio e' rispettata.
Es.le keyword devono precedere gli identificatori
Analisi semantica : L'analisi semantica si occupa di controllare il significato del progranna. Es. riconosce le occorenze di uno stesso identificatore, viene effettuato il type checking,controllare che gli identificatori siano stati dichiarati prima di essere usati,etc.
Come supporto a questa fase viene creata una tabella dei simboli (symbol table) che contiene informazioni su ogni identificatore presente nel programma,es. nome, scope, tipo etc.
Non tutte le regole semantiche sono applicate a compile time. Per esempio riferimenti a oggetti validi deve essere fatto a run-time
Questo processo di cotnrollo statico della semantica produce l'albero sintattico astratto (AST).
Ogni nodo dell' AST è arricchito con delle informazioni chiamate annotazioni, quali i puntatori a identificatori alla Symbol Table.
In questo stadio può essere presente una prima fase di ottimizzazione

Stadio di back end

Anche lo stadio di back end si divide in più fasi:
Generazione del codice intermedio: Dall'albero di sintassi viene generato il codice intermedio.
Possono essere fatti ottimizazioni al codice intermedio.
Generazione del codice target: In questa fase il compilatore traduce il codice intermedio nella forma del linguaggio target(assembly o macchina).
Per generare codice assembly o il linguaggio macchina il generatore di codice accede alla symbol table per assegnare locazioni a variabili e attraversando l'albero sintattico astratto genera le istruzioni(load,store,aritmetico-logiche,etc) relative al programma.

Ref.
Programming Launguage Pragmatics, Michael L. Scott, University of Rochester

Daniele Licari

Compilazione vs Interpretazione

Ad un livello molto alto di astrazione possiamo considerare la compilazione ed l'esecuzione di un programma scritto in un linguaggio di alto livello, come segue:

Programma(Codice) Sorgente → Compilatore → Programma Target
Input → Programma Target → Output

Il compilatore traduce il programma di alto livello in uno equivalente Target( tipicamente in linguaggio macchina ).
Il compilatore utilizzato nei sistemi operativi produce object files che oltre al linguaggio macchina contiene informazioni per il runtime, riallocazione, stack unwinding, commenti, tabella dei simboli (nomi di variabili e funzioni) per il linking e/o debugging.

Uno stile alternativo d' implementazione per i linguaggi di altro livello è l' interpretazione

(Programma(Codice) Sorgente, Input ) → Interpretazione → Output

Nei programmi interpretati le decisioni vengono prese a run-time(tempo di esecuzione), a regola una decisione presa a compile-time(a tempo di compilazione) non deve essere ri-presa a run-time; ne' segue che, generalmente, la compilazione e' più' performante dell'interpretazione.
Es.
Il compilatore può' garantire che una variabile x ha una indirizzo di memoria '0xF' e genera il linguaggio macchina in modo tale che quando il programma sorgente si riferisce a x lo trova sempre nella locazione di memoria '0xF'.
Di contro un interprete ha bisogno di accedere ad una tabella, ogni volta che vuole utilizzare x, per trovare la sua locazione.


Un interprete si occupa anche della dell'esecuzione del programma sorgente per mezzo di una macchina intermedia(virtuale) che a run-time legge uno o più statements alla volta e li compila o interpreta in linguaggio macchina.
In questo caso siamo di fronte ad una implementazione mista.

Programma(Codice) Sorgente → Compilazione → Programma Intermedio
(Programma Intermedio, Input ) → Macchina Virtuale → Output

Alcuni linguaggio che usano la virtual machine sono : Java, C#, VB.net, Python, Perl.
Nel caso in cui la macchina intermedia coincide con la macchina concreta abbiamo l traduzione pura, es. l'assembler.


Nella maggior parte dei linguaggi interpretati viene eseguita una fase iniziali(preprocessor) nella quale vengono eliminati i commenti,gli spazi vuoti, insiemi di caratteri vengono trasformati in tokens (keyword, identificatori, numeri, simboli) e vengono espanse le macro.
Nelle prime versioni di Basic il manuale suggeriva di eliminare i commenti per migliorare le performance.

I linguaggi di alto livello che utilizzano la compilazione pura, in genere contano sull'esistenza di librerie di sotto-routines che non sono parte del programma originario. Es. includono funzioni matematiche o di I/O.
Il compilatore si appoggia su un programma separato chiamato linker, che compone le librerie appropriate al programma finale
Es. Linker

programma → Compilatore → Linguaggio macchina incompleto
(Linguaggio macchina incompleto,Librerie di routunes ) → Linker → Linguaggio macchina completo.

Molti compilatori generano il codice assembly anziche' codice macchina per facilitarne il debugger dato che piu' facile da leggere.
Es. Compilatore C++

Programma Sorgente → Preprocessor → Programma Sorgente Modificato (Espande macro, toglie spazi)
Programma sorgente Modificato → Compilatore c++ → Codice C
Codice C → Compilatore C → Linguaggio Assembly
Linguaggio Assembly → Assembler → linguaggio macchina

In molte macchine l'insieme di istruzioni assembly non sono implementato ad hardware ma vengono interpretate, dall'interprete firmware, in istruzioni di basso livello chiamate “micro istruzioni” implementate ad hardware.
Di conseguenza abbiamo il seguente schema:

Linguaggio Assembly → Assembler → Microlinguaggio
Microlinguaggio → Firmware → Linguaggio macchina

Ref.
Programming Launguage Pragmatics, Michael L. Scott, University of Rochester
slide, http://www.di.unipi.it/~levi/corsoMP/corso2/sld010.htm

Daniele Licari

Breve storia sui linguaggi di programmazione

I primi calcolatori elettronici, nati nel 1940, erano enormi, riempivano una stanza, consumavano tantissima energia e costavano milioni di dollari.
A quel tempo i programmatori scrivevano codice direttamente in linguaggio macchina.
Il linguaggio macchina è una sequenza di bit direttamente controllato da processore per eseguire istruzioni di add, compare e move sui dati.

Es. la somma tra due registri in linguaggio macchina
0000 00ss ssst tttt dddd d000 0010 0000

Successivamente nasce l'assembly ideato per consentire di esprimere operazioni con abbreviazioni menmoniche.

Es. la somma tra due registri in linguaggio assembly
add $d, $s, $t
MIPS Instruction Reference

Inizialmente il linguaggio assembly era caratterizzato da una corrispondenza uno ad uno tra istruzioni menmoniche e istruzioni linguaggio macchina.
Ognuna dell’istruzione assembly veniva codificata nell'istruzione corrispondente del linguaggio macchina.
La traduzione( interpretazione ) tra linguaggio menmonico e linguaggio macchina è affidato ad un processo di sistema chiamato assemblatore(assembler).
Con lo sviluppo dei computers diventava veramente frustrante per i programmatori doversi riscrivere il programma in ogni assembly per poterlo far eseguire su architetture diverse.
Così matura l'idea di avere un linguaggio indipendente dalla macchina.
L'obbiettivo viene raggiunto negli anni '50 con Fortran il primo linguaggio d’alto livello indipendente dalla macchina, seguirono altri linguaggio con Lisp ed Angol.
La traduzione da linguaggio d’alto livello in linguaggio assembly o linguaggio macchina è effettuata da un processo di sistema chiamato compilatore(compiler).
Il compilatore è, sostanzialmente, più complicato dell'assembler, la corrispondenza uno a uno con le istruzioni del linguaggio macchina non esiste più quando il sorgente è di alto livello. Ricordiamo che il linguaggio assembly e' soltanto un'interpretazione menmonica del linguaggio macchina e può essere scavalcato in modo da far produrre direttamente al compilatore linguaggio macchina, ma si preferisce far generare codice assembly per comodità e poter utilizzare più facilmente il debugger.
Inizialmente Fortran non ha avuto tanto successo perché i programmatori preferivano scrivere programmi più efficienti direttamente in assembly, ma con lo sviluppo dei computer, il crescere della complessità dell'hardware e il miglioramento della tecnologia dei compilatori si è arrivato al punto che il codice generato dalla compilazione risulta essere migliore da quello implementato da un sviluppatore assembly.

Ref.
Programming Launguage Pragmatics, Michael L. Scott, University of Rochester

Daniele Licari

Il polimorfismo Ad-hoc( o non universale )

Le funzioni che utilizzano il polimorfismo Ad-hoc possono eseguire codice differente per tipi differenti di argomenti e di conseguenza possono comportarsi in modo diverso a secondo del tipo.
Ci sono due generi di polimorfismo ad-hoc overloading("sovraccarico") e coercion("coercisione")

Nell' overloading viene utilizzato lo stesso nome di funzione per denotare funzioni differenti, e si utilizza il contesto(tipo parametri,tipo ritorno,..) per decidere a quale funzione riferisce una particolare istanza del nome.
Un preprocessing del programma andrà ad eliminare l’overloading assegnando nomi differenti alle diverse funzioni.
Es.
void print(int x)
void print(String x)

Vegono trasformati dal preprocessore in
void print_Int(int x)
void print_String(String x)

In questo senso l’overlodiang risulta essere una convenzione sintattica.

La coercion e’ invece una operazione semantica necessaria per convertire l’argomento di una funzione al tipo previsto per la stessa, in situazioni che potrebbero portare ad un errore sui tipi.
La coercion può' essere prevista staticamente, a compile-time, o dinamicamente, dà test a run-time sugli argomenti delle funzioni.

Il polimorfismo Ad-hoc, in questo esempio, può’ essere spiegato in tre modi differenti
Es. Abbiamo le seguenti espressioni:
3 + 4
3.0 + 4
3 + 4.0
3.0 + 4.0

1. l’ operando “+” e’ sovraccaricato quattro volte , uno per ogni combinazione di tipi di argomenti
2. l’ operando “+” e’ sovraccaricato due volte, quando l’argomento è di tipo intero o reale e l’argomento intero e “coerciso” al tipo reale
3. l’operatore “+” e’ definito solo per la somma sui reali e gli argomenti interi sono sempre “coercisi” ai corrispondenti reali

Bibliografia
[CW85] Luca Cardelli, Peter Wegner, "On Understanding Types, Data Abstraction, and Polymorphism", ACM Computer Surveys, December 1985.

Daniele Licari

Tipi Generici in Java,C#,C++

Come si è potuto intuire, il polimorfismo usato nella programmazione generica è del tipo parametrico. Vale la pena soffermarci per analizzare le differenze dei tipi generici nei linguaggi C++, Java e C#.

Tipi genenici in C# [MSDN]
In C#, quando un tipo generico viene compilato in MSIL (Microsoft intermediate language), contiene metadati che lo identificano come dotato di parametri di tipo.
Le modalità di utilizzo di MSIL per un tipo generico, differiscono a seconda che il parametro di tipo fornito sia un tipo di valore o un tipo di riferimento.
Quando un tipo generico viene costruito con un tipo di valore come parametro, viene creato un tipo generico specializzato con il parametro/parametri forniti, sostituendoli nelle posizioni appropriate in MSIL. I tipi generici specializzati vengono creati una volta per ogni tipo di valore univoco utilizzato come parametro.
Es.1

/* Viene generata dal compilatore una versione specializzata della classe Stack,in seguito, ad ogni occorrenza di uno stack con valori int, viene riutilizzato la classe specializzata Stack generata */
Stack<int> stack;
Stack<short> stack; // Generata un’altra versione specializzata della classe Stack per short

Se il parametro di tipo fornito è un tipo di riferimento. viene generata una versione specializzata della classe che archivia riferimenti a oggetti.
Per ogni successiva occorrenza di un classe con il parametro di tipo di riferimento, diversamente dai tipi di valore, non viene creata un'altra versione specializzata della classe con tipo generico, ma riutilizza la versione specializzata generata in precedenza sostituendo il nuovo tipo di riferimento.
Es.2

class Pluto{} class Pippo{}
/*viene generata una versione specializzata della classe Stack,la quale archivia riferimenti a oggetti di tipo Pluto*/
Stack<Pluto> stackOne = new Stack<Pluto>();
Stack<Pippo> stackTwo = new Stack<Pippo>();/* viene creata un'istanza della versione specializzata della classe Stack generata in precedenza e viene impostata la variabile Pippo per fare riferimento ad essa */

C# per l’implementazione dei tipi generici, usa la condivisione del codice(Code Sharing) per i tipi referenziali, mentre usa la specializzazione del codice(Code Specialization) per i tipi primitivi.


Tipi genenici in C++
La tecnica che utilizza C++ per rappresentare i tipi generici è chiamata Code Specialization(specializzazione di codice). Il compilatore genera una specializzazione della classe parametrica per ogni istanza di un tipo parametrizzato.
Es.3

/* stack, stackOne, stackTwo hanno una versione specializzata della classe Stack diversa tra loro */
std::Stack<int> stack = new std::Stack<int>() ;
std::Stack<Pluto> stackOne = new std::Stack<Pluto>();
std::Stack<Pippo> stackTwo = new std::Stack<Pippo>();


Tipi genenici in Java
L’estensione di Java che permette l’uso dei generici si chiama GJ, sviluppato a partire da Java Pizza; per la rappresentazione dei tipi generici usa la condivisione del codice(Code Sharing), ovvero viene generato il codice per una sola rappresentazione del tipo parametrico e poi vengono mappate le varie istanze concrete su di esso, gestendo i controlli e le conversioni dove sia necessario.

Es.4
/* il compilatore crea una versione specializzata della classe Stack */
Stack<Integer> stack = new Stack<Integer>() ;
/*viene creata un'istanza della versione specializzata della classe Stack generata in precedenza e viene impostata la variabile Pluto per fare riferimento ad essa */
Stack stackOne<Pluto> = new Stack<Pluto>();
/* uguale al commento precedente, ma viene impostata la variabile Pippo */
Stack stackTwo<Pippo> = new Stack<Pippo>();

L’approccio usato nei generici in java a condivisione di codice, limita la generalizzazione ai soli riferimenti e rifiuta a compile-time le istanze generiche che utilizzano i tipi primitivi.
Es. In Java non possiamo dichiarare uno Stack, ma si deve dichiare Stack;
Cosa differente accade nei linguaggi C# e C++, dove vengono create rappresentazioni specializzate.

[MSDN] http://msdn.microsoft.com/

Daniele Licari

Il polimorfismo per inclusione/sottotipi

Il polimorfismo per inclusione/sottotipi è legato fortemente al concetto di ereditarietà. Gli oggetti appartenenti ad una classe derivata appartengono anche alla classe base (quindi la classe derivata è inclusa nella classe base) e ne hanno tutte le proprietà e funzioni, le quali vengono in questo modo riutilizzate per tipi diversi.
La maggior parte dei linguaggi ad oggetti è basata sull'idea che una sottoclasse equivalga ad un sottotipo. Questa idea è spesso ricordata con il nome di Principio di Sostituibilità di Liskov [Lis88].
La definizione data è comportamentale: B è un sottotipo di A se un oggetto di una sottoclasse può essere utilizzato al posto di un'istanza della superclasse, lasciando immutato il comportamento [logico] del programma.
La possibilità che le classi derivate possano ridefinire i metodi e le proprietà dei propri antenati, implica che a seconda del tipo di oggetto su cui è invocato il metodo, oggetti appartenenti alla stessa gerarchia rispondano diversamente alle stesse istruzioni.
Con il polimorfismo subtype bisogna prestare attenzione ai binary methods [BCCLP95], metodi di una classe che prendono come parametri la superclasse, perché possono provocare un comportamento scorretto a run time causato dalla perdita di informazioni sul tipo a compile time. Analizziamo un esempio per intenderci meglio:

Es.3 in Java scriviamo: [GC]

Vector v = new Vector();
v.addElement(new Integer(2));
v.addElement("Pippo");
Integer i = (Integer)v.elementAt(1); // secondo elemento aggiunto

Il parametro del metodo void addElement(Object x) può contenere ogni tipo di oggetti. Quando viene aggiunto un oggetto al vettore si perdono, a compile time, le informazioni sul tipo dell’elemento.
Se tento di castare un elemento con un tipo diverso,come nella riga 4 dell’Esempio 3, Il codice verrebbe compilato senza problemi, ma l’assegnamento a run-time darebbe un errore.

Bibliografia
[BCCLP95] Kim Bruce, Luca Cardelli, Giuseppe Castagna, Gary T. Leavens, Benjamin Pierce, "On Binary Methods", Technical Report, Ecole Normale Supérieure, Paris, 1995.
[Lis88] Barbara Liskov, "Data Abstraction and Hierarchy", ACM SIGPLAN Notices, May 1988.
[GC] Giuseppe Attardi, Antonio Cisternino, Polymorphism

Daniele Licari

Data-Base di suole di scarpe contro i criminali

Le impronte delle scarpe sono le più comuni prove lasciate sulla scena di un crimine. Gli esperti che si occupano di identificarle sono in un numero limitato e soprattutto la tecnologia a loro disposizione non è cosi precisa come quella dei film polizieschi e delle serie tv (C.S.I, R.I.S. , etc).
La situazione viene complicata dalla presenza di piccoli sassolini incastrati nella suola e dalla usura delle stesse, rendendo distorta l’impronta.

Il professore di informatica Sargur Srihari , ha sviluppato un motore di ricerca su un data-base contenente le immagini delle suole di scarpe presenti in molti siti di e-commerce. E’ riuscito a catalogare nel DB oltre 10.000 suole di scarpe
Lo stesso Sargur Srihari è rimasto sorpreso di vedere che molti rivenditori di scarpe on-line includono immagini di suole di scarpe del loro catalogo.
Ora lui lavora su algoritmi di patter matching per individuare il modello della scarpa partendo da un immagine parziale di suola.
Il dipartimento di giustizia Americano ha versato 300.000$( quasi 239.000 € ) nelle tasche del professore per continuare la ricerca.

E pensare che in Italia i ricercatori siano mal pagati per ricerche ben più costruttive di queste. Ma si sà la ricerca in iTAGLIA è un optional.

Leggi l'articolo completo su wired.com