Macchina astratta

In informatica il termine macchina astratta indica un modello teorico di hardware o software, in grado di eseguire operazioni, memorizzarne il risultato e seguire il flusso dell'algoritmo.

Le macchine astratte sono usate nella teoria della computabilità per analizzare la computabilità e la complessità degli algoritmi. Attraverso l'uso di macchine astratte è infatti possibile calcolare la quantità di risorse (tempo, memoria, ecc) necessari per eseguire una determinata operazione, senza dover costruire un sistema reale.

Il più famoso esempio di macchina astratta è la macchina di Turing, ma esistono esempi più completi, con struttura dati, registri e un set di istruzioni completo, come la macchina RAM, che permette l'accesso casuale a posizioni di memoria indicizzati o la più nota macchina astratta C.

Una macchina astratta può anche riferirsi ad un progetto di un microprocessore, che deve ancora essere (o non è destinato ad essere) implementato come hardware. Una macchina astratta implementata come software di simulazione, o per la quale esiste un interprete si chiama macchina virtuale.

Definizione

In termini di input e di output una macchina astratta tipica consiste in un insieme di operazioni ammissibili, utilizzate per trasformare l'input in output.

Fornire una definizione dettagliata e nello stesso tempo valida allo scopo di inquadrare qualsiasi architettura di computer presente e futura è un'impresa tutt'altro che semplice, (se non impossibile), dal momento che ogni macchina astratta dipende da un determinato modello computazionale. Le macchine astratte basate sul modello di Turing sono dette imperative, alla base di tale modello c'è il concetto di istruzione. Esistono altri modelli computazionali che descrivono stili di programmazione e macchine astratte differenti da quelle imperative, (per esempio: logica, funzionale, orientata agli oggetti, ecc...)

Riserviamo maggiore attenzione alle macchine astratte imperative poiché la maggior parte delle macchine reali è basata sul modello dell'architettura di von Neumann. Ciò non è dovuto alla migliore qualità del modello imperativo, ma ad un fatto puramente tecnologico. Nella definizione di macchina astratta imperativa ritroviamo tutti in concetti già presenti nel formalismo della macchina di Turing universale.

Formalmente una macchina astratta (imperativa) è un insieme di strutture dati e algoritmi in grado di memorizzare ed eseguire programmi. Le componenti principali sono:

• un interprete;
• una memoria, che contiene il programma e i dati;
• un insieme di operazioni primitive;
• un controllo di sequenza, che ha il compito di acquisire le istruzioni seguendo il flusso dell'algoritmo;
• un'unità per il controllo del trasferimento dei dati, che si occupa di recuperare gli operandi, e di memorizzare il risultato;

schema dell'interprete

L'interprete

La componente fondamentale che dà alla macchina la capacità di eseguire programmi è l'interprete, esso è un semplice algoritmo detto anche ciclo di FETCH/EXECUTE, che attraverso il coordinamento delle altre parti della macchina astratta permette l'esecuzione delle istruzioni finché non viene eseguita l'istruzione primitiva ALT che provoca l'uscita dal ciclo e l'arresto della macchina.

La struttura dell'interprete è sempre la stessa per qualsiasi macchina astratta, quello che cambia sono le altre componenti.

Realizzare una macchina astratta

Esistono 3 tecniche per realizzare una macchina astratta.

• hardware
• interpretazione
• compilazione

Realizzazione in hardware

La realizzazione in hardware è in linea di principio sempre possibile, ma è opportuna solo per macchine astratte relativamente semplici. La motivazione è di natura economica, realizzare in hardware macchine astratte complesse è molto costoso.

Realizzazione per interpretazione

Può avvenire via firmware e via software (attraverso un emulatore). Via firmware gli algoritmi e le strutture dati si realizzano mediante microprogramma, in una macchina ospite microprogrammabile. Il microprogramma è vincolato dalle caratteristiche della macchina, ma risulta molto più veloce rispetto alla realizzazione via software, che non è vincolata dalle caratteristiche della macchina.

Realizzazione per compilazione

Il programma viene tradotto per intero nel linguaggio della macchina ospite. La traduzione è eseguita da un programma detto compilatore.

I moderni calcolatori

La differenza di potenza espressiva fra la macchina astratta che vogliamo realizzare e la macchina astratta ospite (HOST) è detta semantic gap. Spesso il semantic gap tra la macchina da realizzare e la macchina HOST è così grande che per rendere il sistema efficiente è conveniente realizzare macchine astratte intermedie.

Si forma così una vera e propria gerarchia di macchine astratte, dove al livello più basso ci sono i circuiti elettronici e al livello più alto vi è la macchina astratta al "livello" utente. In questa gerarchia di macchina astratte un ruolo fondamentale è svolto dal sistema operativo che ha il compito di mettere a disposizione dell'utente un'interfaccia software per accedere all'hardware, gestire le componenti hardware e i programmi che vengono eseguiti su di esso.

I moderni calcolatori sono realizzati combinando tutte e tre le tecniche. Uno schema molto usato prevede inizialmente una fase compilativa, seguita da una fase di interpretazione e infine dalla realizzazione in hardware. Un esempio è il linguaggio di programmazione Java. Gli scopi di tale stratificazione sono molteplici: gestire la complessità, aumentare la flessibilità e minimizzare i costi.

Voci correlate

• Architettura di von Neumann
• macchina di Turing
• macchina di Turing universale
• macchina virtuale
• Automa (informatica)

Collegamenti esterni

• università di Pisa (PDF), su di.unipi.it.
• università di Catania, su dmi.unict.it. URL consultato il 2 febbraio 2010 (archiviato dall'url originale il 16 agosto 2009).