Appunti di Linguaggi di Programmazione

Materiale ausiliario di supporto per lo studio dell'esame di linguaggi di programmazione

La nozione di macchina astratta

Un calcolatore è una macchina fisica che permette di eseguire degli algoritmi. Una macchina astratta è un'astrazione del concetto di calcolatore fisico. Per essere eseguiti gli algoritmi devono essere rappresentati mediante le istruzioni di un opportuno linguaggio di programmazione L. Un programma scritto in L è un insieme finito di istruzioni di L. Una macchina astratta M è un insieme di strutture dati e di algoritmi che permettano di memorizzare ed eseguire programmi scritti in L. Una macchina astratta è composta da una memoria e da un interprete. La memoria immagazzina dati e programmi mentre l'interprete esegue le istruzioni contenute nei programmi.

Interprete

L'interprete compie delle operazioni specifiche che dipendono dal particolare linguaggio che deve essere interpretato. Ci sono quattro categorie di operazioni che l'interprete esegue:

• Operazioni per elaborare i dati primitivi: i numeri e le operazioni aritmetiche.
• Operazioni e strutture dati per il controllo della sequenza di esecuzione delle operazioni: servono per gestire il flusso di esecuzione delle istruzioni presenti in un programma mediante particolari operazioni diverse da quelle che manipolano i dati.
• Operazioni e strutture dati per il controllo del trasferimento dei dati: controlla i dati che devono essere trasferiti dalla memoria all'interprete e viceversa.
• Operazioni e strutture dati per la gestione della memoria: riguarda tutte le operazioni relative all'allocazione di memoria per i dati e per i programmi.

Il ciclo di esecuzione dell'interprete è costituito dalle seguenti fasi:

1. Acquisizione della prossima istruzione da eseguire dalla memoria.
2. Decodifica dell'istruzione.
3. Individuare l'operazione richiesta e quali sono gli operandi.
4. Sono prelevati gli operandi ed eseguita l'operazione richiesta.
5. Memorizza il risultato e passa all'istruzione successiva.

Un linguaggio macchina è il linguaggio compreso dall'interprete della macchina astratta.

Implementazione di un linguaggio

Una macchina astratta corrisponde univocamente a un linguaggio, il suo linguaggio macchina. Inversamente, dato un linguaggio, vi sono infinite macchine astratte che hanno L come proprio linguaggio macchina. Tali macchine differiscono tra loro nel modo in cui l'interprete è realizzato e nelle strutture dati che utilizzano. Implementare un linguaggio di programmazione significa realizzare una macchina astratta che abbia L come linguaggio macchina.

Realizzare una macchina astratta

Una macchina astratta deve essere realizzata mediante uno dei seguenti tre metodi:

• Realizzazione in Hardware: questa realizzazione è sempre possibile e abbastanza semplice, si tratta infatti di realizzare mediante dispositivi fisici una macchina fisica tale che il suo linguaggio macchina coincida con L. Questo ha il vantaggio di avere un'esecuzione molto veloce ma solo sui linguaggi a basso livello o dedicati. Invece non è possibile realizzare linguaggi di alto livello. Inoltre, tale macchina una volta realizzata non può essere più modificata.
• Simulazione in Software: è una realizzazione delle strutture dati e di algoritmi di M mediante programmi scritti in un altro linguaggio implementato su un'altra macchina. Quindi possiamo realizzare la macchina M con programmi scritti nell'altro linguaggio che interpretano i costrutti scritti in L simulando le funzionalità di M. In questo caso avremmo la massima flessibilità, potendo cambiare con facilità i programmi che realizzano i costrutti di M. Tuttavia, avremmo prestazioni inferiori, in quanto la realizzazione di M passa attraverso un'altra macchina.
• Emulazione in Firmware: emulare le strutture dati e gli algoritmi di M mediante microprogrammi, la macchina astratta è simulata mediante opportuni programmi che sono poi eseguiti da una macchina fisica, ma tali programmi sono dei microprogrammi invece che programmi di un linguaggio di alto livello. Questi microprogrammi usano un linguaggio di basso livello e risiedono in un'opportuna memoria di sola lettura per poter essere eseguiti dalla macchina fisica ad alta velocità anche se inferiore alla soluzione hardware. Però la flessibilità è inferiore a quella software perché richiede opportuni dispositivi per riscrivere le memorie sulle quali i microprogrammi sono memorizzati.

Implementazione: il caso ideale

Per implementare un linguaggio L, ovvero di cui si vuole realizzare una macchina astratta M, possiamo supporre di avere a disposizione una macchina astratta ospite, che è già stata realizzata e che quindi ci permette di usare direttamente i costrutti del suo linguaggio macchina ospite. L'implementazione avviene sulla macchina ospite mediante una traduzione del linguaggio L nel linguaggio ospite. Ci sono due modalità di implementazione:

• Interpretativa pura: si realizza l'interprete di M mediante un insieme di istruzioni in L, cioè un programma che è un interprete scritto nel linguaggio ospite che interpreta tutte le possibili istruzioni di L. Una volta che tale interprete sia realizzato, per eseguire un programma scritto nel linguaggio L con un certo dato in input, dovremo semplicemente eseguire, sulla macchina ospite, il programma con il programma scritto nel linguaggio L e i dati come input. Nell'implementazione interpretativa pura di L non vi è una traduzione esplicita dei programmi scritti in L. Vi è solo un procedimento di decodifica.
• Compilativa pura: l'implementazione di L avviene traducendo esplicitamente i programmi scritti in linguaggio sorgente in programmi scritti in linguaggio oggetto. La traduzione è eseguita da un opportuno programma detto compilatore. Per eseguire un programma scritto il L con un dato input dovremmo prima eseguire il compilatore con il programma come input e dopo eseguire il programma appena compilato sulla macchina ospite.

Vantaggi e svantaggi dei due tipi di implementazione

L'implementazione interpretativa pura ha come svantaggio principale una scarsa efficienza, dato che per eseguire il programma l'interprete deve effettuare al momento dell'esecuzione una decodifica dei costrutti del linguaggio. Inoltre, per ogni nuova occorrenza di uno stesso comando, l'interprete deve effettuare una nuova decodifica. D'altro canto offre dei vantaggi in termini di flessibilità, infatti, interpretare al momento dell'esecuzione permette di interagire in modo diretto con l'esecuzione del programma. Inoltre, lo sviluppo di un interprete è più semplice di quello di un compilatore. Infine, l'implementazione interpretativa permette di usare una quantità di memoria molto ridotta, dato che il programma è memorizzato solo nella sua versione sorgente e non viene prodotto nuovo codice.

Nell'implementazione compilativa pura la traduzione del programma sorgente in un programma oggetto avviene separatamente dall'esecuzione di quest'ultimo. Se trascuriamo il tempo necessario alla compilazione, l'esecuzione risulterà più efficiente. Inoltre, la decodifica di un'istruzione del linguaggio viene fatta dal compilatore una sola volta. Uno degli svantaggi maggiori risiede nella perdita di informazioni riguardo alla struttura del programma sorgente, perdita che rende più difficile l'interazione con il programma a tempo di esecuzione, infatti, se a run-time si verificasse un errore, potrebbe essere difficile determinare qual è il comando che lo ha causato. In questo caso è più difficile realizzare strumenti di debugging, quindi si ha una flessibilità minore.

Implementazione: il caso reale e la macchina intermedia

Nelle implementazioni dei linguaggi reali sono quasi sempre presenti entrambe le componenti. Supponiamo di avere un linguaggio L che deve essere implementato e di disporre di una macchina ospite già realizzata. Fra la macchina che vogliamo realizzare e la macchina ospite esiste un ulteriore livello formato dal linguaggio intermedio e dalla relativa macchina intermedia. Abbiamo sia un compilatore che traduce da L al linguaggio intermedio, sia un interprete che gira sulla macchina ospite e che simula la macchina intermedia. Un generico programma, creato con il linguaggio L, per essere eseguito è prima tradotto dal compilatore in un programma del linguaggio intermedio. Quindi questo programma è eseguito dall'interprete: nel caso in cui il linguaggio intermedio e il linguaggio macchina ospite non siano molto distanti, per simulare la macchina intermedia può bastare l'interprete della macchina ospite, esteso da opportuni programmi detti supporto a run-time.

Gerarchia di macchine astratte

Si usano spesso gerarchie di macchine astratte in cui ogni macchina usa le funzionalità del livello sottostante e offre nuove funzionalità al livello soprastante. La generica macchina M è implementata sfruttando le funzionalità, cioè il linguaggio, della macchina sottostante; contemporaneamente M fornisce il proprio linguaggio alla macchina sovrastante. Spesso tale gerarchia ha lo scopo di mascherare i livelli inferiori: M può solo accedere alle risorse della macchina subito inferiore, e non a tutte le altre. Una tale strutturazione è utile per dominare la complessità del sistema e permette una certa indipendenza fra i vari livelli.

Descrivere un linguaggio di programmazione

Livelli di descrizione

La descrizione di un linguaggio può avvenire in tre livelli:

• Sintassi (o grammatica): "Quali frasi sono corrette?"; una volta definito l'alfabeto, sono individuate le sequenze corrette di simboli che costituiscono le parole (token) del linguaggio. Dopo la sintassi descrive quali sequenze di parole costituiscano frasi legali.
• Semantica: "Cosa significa una frase corretta?"; attribuisce un significato ad ogni frase corretta.
• Pragmatica: "Come usare una frase corretta?"; frasi con lo stesso significato possono essere usate in modo diverso da utenti diversi.
• Implementazione: "Come eseguire una frase corretta, in modo da rispettarne la semantica?"; il processo le frasi "operative" del linguaggio realizzano lo stato di cose di cui parliamo.

Grammatica e sintassi

Fissato un insieme finito A, chiamato alfabeto, indichiamo con A^* l'insieme di tutte le stringhe finite su A (^* è detto stella di Kleene). Un linguaggio formale su A non è altro che un sottoinsieme di A^*. Una grammatica libera da contesto è una quadrupla (NT, T, R, S) dove:

• NT è un insieme finito di simboli non terminali;
• T è un insieme finito di simboli terminali;
• R è un insieme finito di produzioni (o regole);
• S è il simbolo di partenza appartenente ai NT.

La forma normale di Backus e Naur (BNF) è una notazione per descrivere la grammatica, dove si usano astrazioni per rappresentare classi di strutture sintattiche. La grammatica è formata da un insieme di regole: una regola ha una parte sinistra (LHS) e una parte destra (RHS), che consistono di simboli terminali e non terminali. Una regola può avere più di una parte destra separata dal simbolo "|".

Una derivazione consiste nella ripetuta applicazione di regole di una grammatica. Ogni stringa di simboli presenti nella derivazione si chiama forma di frase; una forma di frase fatta di soli terminali si chiama semplicemente frase. Una singola regola di derivazione mette in relazione di derivazione diretta due forme di frasi: P => bPb. La derivazione, quindi, non è altro che la chiusura transitiva della relazione => e si indica con =>^*: P => aPa => abPba => abba, quindi P =>^* abba.

Un albero è una struttura costituita da un insieme di nodi interni, da nodi foglie e dal nodo radice. Un grafo connesso è formato dai nodi e dagli archi che li collegano. Un albero di derivazione è una rappresentazione gerarchica di una derivazione, dove:

• Nodo radice: S
• Nodi interni: NT
• Nodi foglia: T

Una derivazione sinistra (destra) è una derivazione dove, in ogni forma di frase intermedia, si espande il non-terminale più a sinistra (destra), tuttavia ci sono derivazioni che non sono né sinistre né destre. Una grammatica è ambigua se e solo se esiste almeno una forma di frase prodotta attraverso due o più alberi di derivazione distinti. Tuttavia, una stringa può avere più derivazioni distinte senza che la grammatica sia ambigua, però non può avere più di due derivazioni canoniche dello stesso tipo.

La forma normale di Backus e Naur estesa (EBNF) introduce delle nuove specifiche quali:

• Le parti opzionali sono poste tra parentesi quadre;
• Le parti destre alternative sono poste tra parentesi tonde e separate con barre verticali;
• Ripetizioni di zero o più elementi sono poste tra parentesi graffe.

Vincoli sintattici contestuali

La correttezza sintattica di una frase dipende dal contesto nel quale si trova e non si possono esprimere con una grammatica libera. Degli esempi sono il dichiarare un identificatore prima dell'uso, o nel caso di un assegnamento, il tipo di un'espressione deve essere compatibile con quello della variabile a cui si assegna. La necessità di gestire i vincoli della sintassi contestuale porta alla nozione di semantica statica: ossia verificabile sul testo del programma sorgente.

Compilatori

L'analisi lessicale (scanning o lexing) è implementata dal sottoprogramma scanner o lexer. Lo scopo è quello di leggere sequenzialmente i simboli di ingresso di cui è composto il programma e di raggruppare tali simboli in unità logicamente significative, che chiamiamo token, che sono l'analogo delle parole del dizionario di un linguaggio naturale. Lo strumento tecnico che si usa per l'analisi lessicale è una classe di grammatiche generative: le grammatiche regolari (o lineari).

L'analizzatore sintattico (o parser), costruita la lista di token, cerca di costruire un albero di derivazione per tale lista. Ogni foglia corrisponde a un token, e tali foglie lette da sinistra verso destra, devono costituire una frase corretta nel linguaggio. Se la stringa in ingresso non è una stringa corretta secondo la grammatica del linguaggio, il parse non sarà in grado di costruire l'albero e riporterà un errore, abortendo la compilazione.

L'analisi semantica sottopone l'albero di derivazione ai relativi controlli contestuali. Man mano che vengono fatti, l'albero viene aumentato con la relativa informazione. Per gli identificatori, le informazioni sono anche registrate nella tabella dei simboli. Le fasi successive si dividono in:

1. Generazione della forma intermedia:
   • Visita dell'albero per generare il codice;
   • Codice in forma intermedia;
2. Ottimizzazione del codice:
   • Rimozione codice inutile;
   • Espansioni delle chiamate di sottoprogrammi;
   • Fattorizzazione delle espressioni;
   • Ottimizzazione dei cicli;
3. Generazione del codice:
   • Generazione del codice;
   • Ulteriore fase di ottimizzazione.

Semantica

La semantica è nata dall'esigenza di mediare tra due istanze contrapposte: la ricerca dell'esattezza e della flessibilità. I metodi formali per la semantica si dividono in due categorie: le semantiche denotazionali e quelle operazionali. Quella denotazionale fa uso di funzioni e tecniche logico-matematiche. Quella operazionale fa uso di un formalismo a basso livello usando automi, assiomi, stati e transizioni. Lo stato è un modello di memoria che mantiene in memoria i valori delle variabili. Nello stato corrente una certa variabile ha un certo valore. Le operazioni possibili sono l'assegnazione di un nuovo valore a una variabile e il ritrovamento del valore di una variabile. La transizione esprime un passo di trasformazione sullo stato del programma, provocato dall'esecuzione di un programma. Cioè il passaggio da uno stato a un altro. Esistono anche transizioni composte e transizioni condizionali. Le computazioni sono una sequenza di transizioni concatenate non ulteriormente estendibile in cui ogni transizione è permessa da qualche regola. Ci sono due tipi di computazioni: quelle determinanti o finite e quelle divergenti o infinite (loop).

Fondamenti e calcolabilità

Il problema della fermata

Dobbiamo capire se esiste un analizzatore statico capace di scoprire se un programma, su un certo dato di ingresso, possa andare in ciclo. Un analizzatore statico è un programma usato come sottoprogramma all'interno di un compilatore. Si dimostra come non esista alcuna procedura di decisione capace di verificare se un altro programma termina su un input. Questo risultato va sotto il nome di indecidibilità del problema della fermata.

Espressività dei linguaggi di programmazione

Alcune funzioni sono calcolabili, altre non lo sono. Alcuni programmi possono registrare un errore se il risultato del programma è indefinito, però non si possono riportare errori se il programma non termina. Non esiste alcun programma che funzioni per argomenti arbitrari, che termini sempre o che discrimini gli argomenti che sono soluzione del problema da quelli che non lo sono. Esistono funzioni che non sono calcolabili mediante una Macchina di Turing. Secondo la tesi di Church, tutte le funzioni calcolabili lo sono tramite un sistema formale equivalente alla Macchina di Turing o alle funzioni ricorsive.

I nomi e l'ambiente

Un nome non è altro che una sequenza di caratteri usata per rappresentare qualche altra cosa e permette di astrarre sia aspetti relativi ai dati, sia aspetti relativi al controllo. La gestione corretta dei nomi richiede sia regole semantiche precise che meccanismi implementativi adeguati.