Il concetto di Macchina Astratta

Formalmente una Macchina Astratta (Imperativa¹) è un insieme di strutture dati e algoritmi in grado di memorizzare ed eseguire programmi.

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 risultai delle varie istruzioni;
• un insieme di operazioni e strutture dati per la gestione della memoria.

Fig.1: Struttura di una Macchina Astratta

Le varie macchine astratte differiscono per il diverso modo di strutturare la memoria, per il diverso insieme di tipi primitivi che forniscono, per le diverse operazioni elementari che realizzano e per le diverse componenti di controllo e gestione; in generale cioe' per il diverso modo di gestire l'esecuzione di un programma.

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. Schematicamente:

Fig.2: Il ciclo Fetch-Execute

Il processo eseguito dall'interprete e' suddiviso in fasi. Inizialmente avviene l'acquisizione, mediante l'uso delle strutture dati preposte al controllo della sequenza, della prossima istruzione da eseguire (FETCH). Quindi l'istruzione viene decodificata e si acquisiscono i suoi eventuali operandi, ricorrendo al controllo sul trasferimento dei dati. A questo punto viene eseguita l'opportuna operazione primitiva e l'eventuale risultato viene memorizzato (grazie di nuovo al controllo del trasferimento dei dati). Se l'operazione eseguita non e' quella che fa arrestare l'interprete, il processo ricomincia.

A titolo esemplificativo, vediamo alcuni esempi.

Macchina fisica con architettura tradizionale
Esaminiamo i componenti di una macchina astratta corrispondente ad una macchina fisica con architettura tradizionale (il vostro PC per esempio). Operazioni primitive tipiche di queste macchine sono le operazioni aritmetico-logiche, le operazioni di manipolazione di stringhe di bit, le operazioni di lettura e scrittura di celle di memoria e registri. Le strutture dati usate per il controllo sequenza sono il registro contatore istruzioni (PC) e le strutture contenenti i punti di ritorno dei sottoprogrammi. La sequenza di esecuzione e' controllata da operazioni quali salti, condizionali, chiamate di e ritorni da sottoprogrammi. In una macchina hardware tradizionale, it controllo su trasferimento dei dati riguarda sostanzialmente le modalita' di indirizzamento degli operandi di un'operazione e la memorizzazione del risultato relativo. A tale scopo vengono usati i registri indice e le operazioni che realizzano le modalita' di indirizzamento indiretto.
Macchina fisica con architettura a pila
In una macchina con architettura a pila, la struttura dati fondamentale per il controllo sul trasferimento dei dati e' una pila (stack), da cui sono prelevati gli operandi e su cui sono memorizzati i risultati. Nelle tradizionali macchine a registri, in cui i programmi ed i dati vengono memorizzati staticamente, non esiste praticamente gestione della memoria. Nelle macchine con architettura a pila questa consiste nella gestione della pila stessa.
Ristorante
La nozione di macchina astratta e' ben piu' generica di quanto si possa credere. Infatti anche un ristorante, in un certo senso si puo' vedere come una macchina astratta. I programmi "eseguiti" da tale macchina sono composti da sequenze di ordinazioni di piatti (Es.: antipasto alla marinara; linguine al pesto; pepata di cozze; macedonia; limoncello). Supponiamo di avere un ristorante in cui ci sia un cuoco specializzato per ogni piatto ed un insieme di inservienti preposti a portare a tali cuochi gli ingredienti per i loro piatti. L'insieme dei cuochi puo' esser visto come l'inseme delle "operazioni" della macchina. La "memoria" della nostra macchina sara' il taccuino del cameriere. L'"interprete" del ristorante puo' essere il cameriere stesso che, letta la prima "istruzione" la "decodifica", dicendo agli inservienti quali ingredienti portare a quale cuoco. Ovviamente anche la dispensa dovra' esser vista come parte della memoria del ristorante (la parte che memorizza gli "argomenti" delle istruzioni. Un altro cameriere provvedera' a "memorizzare" sul nostro tavolo il risultato dell'esecuzione dell'istruzione.
Ovviamente certi esempi di macchine astratte necessitano di un minimo di elasticita' mentale per poter esser ricondotti al nostro schema formale.
Teniamo presente inoltre che in realta' quella che abbiamo fornito e' una descrizione della "realizzazione" della macchina astratta Ristorante.

Da notare come nella nostra definizione di macchina astratta non compaiano moduli per la gestione dell'Input/Output. Nulla ci vieterebbe di inserire anche questi nella nostra definizione. Essendoci pero' una enorme varieta' di possibilita' per l'Input/Output, tale concetto non si presta ad una generalizzazione ad un livello adeguato da poter essere inserito in una definizione che aspira ad essere la piu' generale possibile. Si potrebbe pensare di inserire operazioni particolari per l'I/O nell'insieme di operazioni fornite dalla macchina, oppure si potrebbe considerare una componente che gestisca l'interfacciamento della memoria con il "mondo esterno". Entrambe, e molte altre possibilita' vanno bene. Fare una scelta particolare in una definizione generale come la nostra non troverebbe giustificazione rispetto alle altre possibilita'.