Riassunto Teoria Linguaggi

Macchina astratta

Una macchina astratta non è altro che un'astrazione del concetto di calcolatore fisico. Ovvero, è una macchina fisica (calcolatore) che permette di eseguire degli algoritmi formalizzati in termini di costrutti di un linguaggio di programmazione, che possono essere comprensibili all'esecutore.

Le componenti principali di una macchina astratta sono:

• Un interprete
• Una memoria, destinata a contenere il programma che deve essere eseguito e i dati su cui si sta operando
• Un insieme di operazioni primitive (cioè funzionalità che si assume la macchina sia in grado di fornire) utili all'elaborazione dei dati primitivi (ovvero dati sui quali la macchina astratta sa lavorare)
• Un insieme di operazioni e strutture dati che gestiscono il flusso di controllo, ovvero che governano l'ordine secondo il quale le operazioni, descritte dal programma, vengono eseguite
• Un insieme di operazioni e strutture dati per il controllo del trasferimento dei dati, che si occupa di recuperare gli operandi e memorizzare i risultati delle varie istruzioni
• Un insieme di operazioni e strutture dati per la gestione della memoria

La componente fondamentale che dà alla macchina astratta la capacità di eseguire programmi è l'interprete: esso coordina il lavoro delle altre parti della macchina astratta eseguendo un semplice ciclo FETCH/EXECUTE, finché non viene eseguita una particolare istruzione primitiva (detta HALT) che ne provoca l'arresto immediato. Il processo eseguito dall'interprete è suddiviso in fasi:

• Operazioni per l’elaborazione dei dati primitivi: ovvero operazioni che permettono di manipolare dati primitivi, cioè che siano rappresentabili in modo diretto nella macchina. Ad esempio, i numeri.
• Operazioni e strutture dati per il controllo di sequenze di esecuzione delle operazioni: ovvero l’interprete dispone di strutture dati opportune che sono manipolate con operazioni particolari, volte a gestire il flusso di esecuzione delle istruzioni.
• Operazioni e strutture dati per il controllo del trasferimento dei dati: servono per controllare come i dati devono essere trasferiti dalla memoria all’interprete e viceversa.
• Operazioni e strutture dati per la gestione della memoria: ovvero tutte quelle operazioni relative all’allocazione di memoria per i dati e per i programmi.

Implementazione

Considerando un generico linguaggio L che si vuole implementare, ovvero di cui si vuole realizzare una macchina astratta ML. Possiamo supporre di avere a disposizione una macchina astratta M0L0, che chiameremo macchina ospite che è già stata realizzata e che quindi ci permette di usare direttamente i costrutti del suo linguaggio.

Due sono i tipi di implementazione possibili:

• Implementazione interpretativa pura: in questo caso viene realizzato un interprete di ML mediante un insieme di istruzioni in L0. Ovvero si realizza un programma che è un interprete, scritto in L0, che interpreta tutte le possibili istruzioni di L. In questo caso, quindi, non vi è una traduzione esplicita dei programmi scritti in L. Vi è solo un procedimento di decodifica.
• Implementazione compilativa pura: in questo caso invece l’implementazione di L avviene traducendo esplicitamente i programmi scritti in L in programmi scritti in L0. La traduzione è eseguita dal compilatore.

Confronto fra le due tecniche

• Implementazione interpretativa pura
  • Svantaggi
    • Scarsa efficienza: overhead per la codifica
    • Replica della traduzione
  • Vantaggi
    • Maggiore flessibilità
    • Facilità di sviluppo e debugging
    • Memoria ridotta (solo sorgente)
• Implementazione compilativa pura
  • Svantaggi
    • Minore flessibilità
    • Perdita di informazioni sulla sorgente
    • Minore facilità di debugging degli errori a runtime
  • Vantaggi
    • Una sola traduzione
    • Esecuzione più efficiente

Macchina intermedia

Per colmare il divario tra macchina ML e macchina HOST (ospite), si progetta un’apposita macchina intermedia MI che viene realizzata sulla macchina HOST. A questo punto, la traduzione dei programmi in L avverrà in termini del linguaggio di MI, e successivamente il programma per MI così ottenuto verrà eseguito tramite interpretazione sulla macchina HOST.

Nel progetto della macchina intermedia bisogna tenere conto di due requisiti di efficienza:

• Velocità di simulazione della macchina intermedia MI sulla macchina HOST
• Compattezza del codice prodotto nel linguaggio della macchina MI

Per soddisfare tali requisiti, tipicamente MI è solo un'estensione della macchina HOST, nel senso che ne condivide l'interprete e ne potenzia alcuni aspetti mediante un insieme di routine note come Run-Time System, atto a colmare, negli aspetti, la differenza delle due macchine.

Un esempio concreto si ha per il linguaggio di programmazione Java, dove la macchina intermedia è la JVM (Java Virtual Machine), il cui linguaggio è detto Bytecode, mentre il run-time system viene detto Java Runtime Environment.

A seconda di quanto il livello intermedio si sia spostato verso il livello sorgente o ospite si hanno tre casi di implementazione:

• ML = MI (implementazione puramente interpretativa)
• ML != MI != MO:
  • Se l'interprete della MI è sostanzialmente diverso dall’interprete della MO (implementazione di tipo interpretativo)
  • Se l'interprete della MI è sostanzialmente uguale all’interprete della MO (implementazione di tipo compilativo)
• MI = MO (implementazione puramente compilativa)

Vantaggi

• Ridurre la scarsa efficienza della macchina realizzata emulando via software strutture dati, algoritmi e soprattutto l’interprete.
• Ridurre lo spazio di memoria necessario e incrementare la velocità.

Problema della fermata

Il problema della fermata chiede se sia sempre possibile, descritto un algoritmo e un determinato input finito, stabilire se l’algoritmo in questione termini o continui la sua esecuzione all’infinito. È stato dimostrato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input.

Supponiamo un programma C con input un qualsiasi algoritmo a avente un input finito d, è in grado di stabilire se a termina in tempo finito (valore true) o se non termina (valore false).

boolean C(a, d):
    return halts(a(d));

Essendo sia a che d sequenze indistinte di simboli per la macchina, possiamo passare come secondo parametro di C lo stesso algoritmo a, ovvero eseguire C(a, a).

Sia ora loop un programma che non termina mai: possiamo costruire un altro algoritmo che chiameremo K, che prendendo in ingresso a esegue loop (non restituendo alcun valore) se C(a, a) restituisce true, mentre ritorna false se C(a, a) restituisce false. Ovvero:

boolean K(a):
    if C(a, a) loop();
    else return false;

In pratica K termina (restituendo il valore false) solo se l'algoritmo a con input a non termina, altrimenti K continua a eseguire loop (ciclando all'infinito) non restituendo alcun valore.

A questo punto, se passiamo come input dell'algoritmo K lo stesso K (ovvero K(K)), tale algoritmo termina (restituendo il valore false) solo se l'algoritmo K con input K non termina. Ovvero, abbiamo che K(K) termina se e solo se K(K) non termina! Siamo giunti a una contraddizione, che prova essere assurda l'ipotesi iniziale che esista un algoritmo C che, dato un qualsiasi algoritmo a e un suo input d, è in grado di stabilire se a(d) termina o non termina.

Indecidibilità

Esistono molte proprietà importanti dei programmi che non possono essere determinate in modo meccanico da nessun algoritmo; una tra queste è il problema della fermata.

Calcolabilità

Una funzione è calcolabile quando esiste un programma che la calcola. L'indecidibilità del problema della fermata afferma che esistono funzioni non calcolabili.

Parzialità

Le funzioni espresse da un programma possono essere indefinite su alcuni argomenti, in corrispondenza di quei dati di input per i quali il programma non termina.

Turing completezza

Ogni linguaggio di programmazione general purpose (adatto a più utilizzi) calcola lo stesso insieme di funzioni, quelle calcolate dalle macchine di Turing.

Esistono più funzioni che algoritmi

Usando un semplice argomento di cardinalità è abbastanza semplice vedere che l’insieme di tutti i possibili programmi (finiti) che possiamo scrivere in L è numerabile, ossia può essere messo in corrispondenza biunivoca con i numeri naturali. In termini più formali possiamo dire che la cardinalità dell’insieme di tutti i programmi scrivibili in L è eguale alla cardinalità dei numeri naturali.

Consideriamo adesso F contenente tutte le funzioni N → {0, 1}. Un importante teorema dovuto a Cantor ci dice che tale insieme non è numerabile, ossia ha una cardinalità strettamente maggiore di quella di N, per cui, dato che ogni programma può esprimere un’unica funzione, non riusciremo mai ad esprimere tutte le funzioni in F con programma di L.

Nome

Non è altro che una sequenza di caratteri usata per rappresentare o denotare un oggetto. Uno stesso oggetto può avere più nomi (aliasing).

Astrazione sui dati

Definendo un nome per una variabile di un linguaggio imperativo si introduce un identificatore simbolico per una locazione di memoria, astraendo così dai dettagli di basso livello relativi agli indirizzi di memoria.

Statico e dinamico

Si distinguono due fasi principali usando questi due termini. Statico si riferisce a tutto quello che avviene prima dell’esecuzione; Dinamico tutto quello che avviene al momento dell’esecuzione. Ad esempio, la gestione statica della memoria è quella operata dal compilatore, mentre quella dinamica è quella realizzata da opportune operazioni eseguite dalla macchina astratta a tempo d’esecuzione.

Ambiente

È l’insieme delle associazioni fra nomi e oggetti denotabili esistenti a run-time in uno specifico punto del programma e in uno specifico momento dell’esecuzione. (referecing environment). Permette di determinare quale sia l’associazione corretta. L’ambiente non esiste a livello della macchina fisica, ma nel linguaggio di alto livello e quindi deve essere simulata nell’implementazione del linguaggio.

Dichiarazione

È un costrutto che permette di introdurre un’associazione nell’ambiente.

Blocco

È una regione testuale del programma identificata da...