\documentclass[a4paper, 12pt]{article}
\usepackage{amssymb}
\usepackage{natbib}
\usepackage{float}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[italian]{babel}

\title{Note su\\ Macchine Astratte\thanks{Le presenti note sono parzialmente basate sulle note del prof. Levi dell'Universita' di Pisa. LaTeX editing by Andrea Maugeri.}}
%\author{N. Fazio, A. Nicolosi e F. Barbanera}
\date{}
\begin{document}
\maketitle

\begin{abstract}
    Nelle presenti note, partendo dalla definizione del modello computazionale delle Macchine di Turing, si arriva alla nozioni di Macchina Astratta\footnote{Al posto del termine "Macchina Astratta"  spesso si utilizza quello di "Macchina Vituale (Virtual Machine)".}, realizzazione di macchine astratte e sistemi a livelli di macchine astratte. Queste ultime nozioni possono essere utilizzate come riferimento generale per inquadrare la maggior parte degli argomenti che si affronteranno nel corso di Architettura degli elaboratori 
    \end{abstract}
    %(le presenti note possono essere viste anche come materiale integrativo del Cap.1 del testo di A.S.Tanenbaum "Structured Computer Organization - Architettura dei calcolatori, un approccio strutturato".
    \newpage
    \tableofcontents{}
    \newpage
\section{Cosa vuol dire computare?}
    Nonostante possa sembrare banale, \`e tutt'altro che facile dare una definizione allo stesso tempo formale e generale del concetto di \textbf{computazione}. \newline 
    Possiamo dire che computare significa ridurre una informazione da una forma implicita ad una forma esplicita in modo effettivo, ovvero rielaborare un insieme di ``informazioni'' al fine di presentarli in una forma di pi\`u diretta comprensione.\newline L'approccio classico alla formalizzazione del concetto di calcolo \`e fondato sull'idea di fornire delle regole meccanizzabili, che esprimano il procedimento necessario all'esplicitazione dell'informazione iniziale in modo effettivo.
    Nel processo di calcolo entrano quindi in gioco entit\`a come:
    \begin{itemize}
        \item dati
        \item passo elementare di computazione (effettivo, meccanizzabile, discreto)
    \end{itemize}
    Diversi modi di formalizzare questi elementi portano a diversi \textbf{modelli computazionali}. Un modello computazionale \`e un formalismo matematico in cui viene rappresentato in modo astratto, ma preciso, un particolare modo di intendere in concetto di input, di output, di passo elementare di computazione e di come organizzare un insieme di passi elementari di computazione in una descrizione di un procedimento effettivo (algoritmo) che permetta di rendere esplicito il contenuto informativo all'inizio presente solo in forma implicita.
    \`E da sottolineare come il concetto generale di \textbf{computazione} possa essere formalizzato in vari modi, dando origine a differenti modelli computazionali, ognuno dei quali utilizza particolati nozioni specifiche per rappresentare i concetti pi\`u generali. \newline
    I modelli computazionali storicamente sviluppati e studiati sono numerosi. Si va dal formalismo delle funzioni ricorsive, al lambda-calcolo, alle Unlimited Register Machines (URM), alle macchine di Turing. Le Macchine di Turing sono automi (nel senso descritto del testo di Ausiello, 2.5.1) ed in particolare automi con la massima potenza computazionale.
    \subsection{Nota sugli automi a stati finiti}
        La teoria degli automi \`e quella che viene utilizzata nella Teoria dei Linguaggi Formali per quanto riguarda l'approccio riconoscitivo alla definizione dei linguaggi. Le computazioni descritte dagli automi utilizzati nella teoria dei linguaggi formali sono computazioni che, preso un input, restituiscono un output di tipo YES o NO, oppure non terminano (si potrebbe far vedere che questo tipo di computazioni non sono concettualmente differenti da quelle che, preso un input, restituiscono un output su un certo codominio). Nella teoria degli automi (come, del resto, in altri modelli computazionali) \`e possibile restringere il modello computazionale con dei vincoli che ne limitino la potenza espressiva dal punto di vista delle computazioni rappresentabili. Abbiamo per esempio, come indicato nel testo di Ausiello et al. 2.5.3 gli Automi a Stati Finiti, gli Automi a Pila, ecc. \newline Per quanto riguarda gli automi a stati finiti (vedi Ausiello et al. 3.1) che riconoscono le stringhe appartenti a linguaggi regolari, \`e possibile modificare leggermente questo formalismo in modo che le computazioni eseguite permettano, anzich\`e accettare o meno una stringa, di produrre una stringa su un opportuno insieme di caratteri di output.
        \`E sufficiente che, nella definizione di automa a stati finiti, si aggiunga un insieme Z di caratteri di output, si elimini la nozione di stato (o stati) finale e si faccia in modo che la funzione di transizione $\delta$ sia del tipo
        $\delta$ : $\Sigma$ $\times$ K $\-->$ K $\times$ Z
        Tale funzione permette ora di associare, al carattere correntemente letto ed allo stato interno attuale, lo stato successivo ed un carattere di output.
        Nella rappresentazione degli automi come diagramma degli stati (o grafo di transizione, chiamato anche diagramma di flusso in alcune soluzioni degli esercizi) basta quindi indicare sopra gli archi orientati non solo il carattere letto, ma anche il carattere di output prodotto dalla transizione rappresentata dall'arco orientato. Negli automi a stati finiti cos\`i descritti si pu\`o vedere che le computazioni effettuate possono prendere in input anche stringhe potenzialmente infinite, restituendo passo passo, un carattere per volta, stringhe di output infinite. Questa versione degli Automi a Stati Finiti \`e estremamente importante, poich\`e \`e con questi automi che si riesce a descrivere il comportamento dei circuiti sequenziali (che studierete nel corso di Architettura degli Elaboratori). Esistono inoltre procedure automatizzabili che, presa una specifica di funzionamento rappresentata attraverso un automa a stati finiti, permettono di sintetizzare il circuito sequenziale che realizza fisicamente tale specifica.
        \subsection{L'analisi di Alan Turing del concetto di \textit{procedura effettiva}}
            Il tentativo di Turing di formalizzare \textbf{la classe di tutte le procedure effettive} risale al 1936 e port\`o alla nozione di Macchina di Turing. La sua importanza sta nel fatto che si tratta della prima anlisi che descriva come ha luogo la computazione; inoltre tale analisi port\`o ad una astrazione convincente ed ampiamente accettata del concetto di procedura effettiva.
            \`E degno di nota che questa analisi di Turing avvenne prima delle invenzioni dei moderni computer. \newline
            Diamo adesso un estratto della analisi di Turing. Si osservi che con il termine calcolatore Turing si riferisce ad un uomo che sta risolvendo un problema computazionale in maniera meccanica, e non ad una macchina.
            \begin{quote}
                [...] Il procedimento del calcolo \`e normalmente realizzato scrivendo dei simboli su carta. [...] Suppor\`o che la computazione avvenga su di un foglio unidimensionale, ovvero su di un nastro suddiviso in caselle.\newline Suppor\`o inoltre che il numero di simboli che possono essere scritti sia finito. [...] Le conseguenze di questa restrizione sul numero di simboli non sono rilevanti. \`E sempre possibile usare una sequenza di simboli al posto di un singolo simbolo. 
                [...] Il comportamento del calcolatore in ogni istante \`e determinato dai simboli che egli sta osservando e dal suo stato mentale in quel dato istante. Possiamo supporre che ci sia un limite B al numero di simboli o celle che il calcolatore riesce ad osservare in un dato momento. Se vuole osservare qualcosa in pi\`u, dovr\`a effettuare pi\`u osservazioni successive. Supporremo anche che il numero di stati mentali di cui \`e necessario tenere conto sia finito. [...] Ancora una volta, tale restrizione non ha conseguenze rilevanti, poich\`e l'uso di stati mentali pi\`u complessi pu\`o essere evitato annotando pi\`u simboli sul nastro.\newline Immaginiamo di scomporre le operazioni realizzate dal calcolatore in operazioni di base cos\'i elementari da risultare difficile una loro ulteriore scomposizione. Ciascuna di tali operazioni consister\`a di un qualche cambiamento del sistema fisico costituito dal calcolatore e dal suo nastro. Conosciamo lo stato del sistema se conosciamo la sequenza dei simboli sul nastro, quali di essi sono osservati dal calcolatore, e lo stato mentale del calcolatore. Possiamo supporre che in ogni operazione di base non venga alterato pi\`u di un simbolo.\newline [...] A parte questa possibilit\`a di modificare simboli, le operazioni di base devono includere il cambiamento della distribuzione delle caselle osservate. [...] Penso sia raggionevole supporre che (le nuove celle) possano essere solo celle la cui distanza dalla pi\`u vicina delle celle precedentemente osservate non ecceda una certa quantit\`a prefissata L.\newline[...] Le operazioni di base devono perci\`o includere: 
                \begin{enumerate}
                    \item Cambiamento del simbolo di una delle caselle osservate.
                    \item Cambiamento di una delle caselle osservate con un'altra casella nello spazio di L celle di distanza da una di quelle precedentemente osservate.
                \end{enumerate} 
                Potrebbe succedere che qualcuno di questi cambiamenti comporti necessariamente il cambiamento dello stato mentale. Pi\`u in generale, le operazioni di base dovranno quindi essere le seguenti:
                \begin{enumerate}
                    \item Un possibile cambiamento (a.) di un simbolo, insieme con un possibile cambiamento di stato mentale.
                    \item Un possibile cambiamento (b.) di una delle caselle osservate, insieme con un possibile cambiamento di stato mentale.
                \end{enumerate}
                Quale operazione venga in effetti eseguita \`e determinato dallo stato mentale del calcolatore e dai simboli osservati.\newline[...] Possiamo adesso costruire una macchina che svolga il lavoro del calcolatore. Ad ogni stato mentale del calcolatore corrisponde una configurazione della macchina. La macchina osserver\`a le B celle corrispondenti alle B celle osservate dal calcolatore. Ad ogni mossa, la macchina potr\`a cambiare un simbolo su una delle celle osservate, o potr\`a spostare l'attenzione da una delle B celle osservate ad un'altra distante non pi\`u di L celle da una qualunque di quelle precedntemente osservate. [...]
            \end{quote}
            Successivamente a questa analisi, Turing e Church indipententemente formularono la cosiddetta Tesi di Church-Turing:
            \begin{quote}
                Ogni funzione intuitivamente computabile \`e computabile con una Macchina di Turing.
            \end{quote}
            Tale tesi non si presta ad una dimostrazione matematica, poich\`e identifica una nozione intuitiva (quella di procedura effettiva), con un concetto matematico (quello di macchina di Turing). Tuttavia esistono varie ragioni per ritenerla valida, la pi\`u importante delle quali \`e il fatto che tutti gli altri modelli computazionali (di cui ne abbiamo elencati alcuni all'inizio della sezione) che sono stati proposti come formalizzazione del concetto di procedura effettiva, si sono rivelati essere equivalenti alle Macchine di Turing. \\
            Nonostante le differenze nel formalismo, i vari modelli computazionali hanno delle caratteristiche comuni, quali: 
            \begin{itemize}
                \item Esiste solo una quantit\`a finita di "costrutti" che possono essere combinati per fornire una descrizione finita di ogni procedura effettiva.
                \item La computazione procede in maniera discreta, passo dopo passo.
                \item La computazione avviene in maniera deterministica, ovvero senza fare ricorso a metodi casuali
                (anche se esistono il realta' modelli computazionali non deterministici).
                \item Sebbene non vi sia un limite a priori sulla quantit\`a di memoria o di tempo a disposizione, ogni computazione finita non deve basarsi su di una quantit\`a infinita di tempo e/o spazio.
                \item Ogni passo nella computazione coinvolge solo una quantit\`a finita di dati.
            \end{itemize}

\section{Le Macchine di Turing come modello computazionale}
    Uno dei primi modelli computazionali ad essere stato proposto \`e quello dovuto al matematico e logico inglese Alan Turing.\newline Nel 1936 Turing, nel tentativo di formalizzare la nozione di \textbf{procedura effettiva}, analizz\`o il comportamento di un essere umano quando risolve un problema di calcolo seguendo un metodo meccanico.\newline Egli riconobbe l'essenza di tale attivit\`a nella capacit\`a di scrivere su un foglio (grande quanto necessario) usando un numero finito di simboli, con la possibilit\`a di riconsiderare il lavoro gi\`a svolto. Per tenere traccia del lavoro gi\`a svolto, \`e opportuno non solo potere rileggere i simboli scritti in precedenza sul foglio, ma anche potere avere una sorta di \textit{stato mentale}, influenzato da tutte le azioni precedenti e in grado di condizionare le scelte successive. Da questa analisi Turing dedusse che una macchina per computare dovesse disporre:
    \begin{itemize}
        \item di un \textit{nastro infinito}, suddiviso in celle, ciascuna capace di contenere un qualunque simbolo.
        \item  di una \textit{testina movibile}, atta a leggere e/o scrivere quintuple sul nastro. 
        \item di una scatola nera, nota come \textit{controllo finito}, per memorizzare lo stato mentale corrente.
    \end{itemize}
    Le operazioni elementari che una tale macchina doveva essere in grado di eseguire erano:
    \begin{itemize}
        \item cambiare il simbolo sotto la testina.
        \item spostare la testina in modo da agire su una delle celle adiacenti a quella corrente.
    \end{itemize}
    Secondo Turing era inoltre necessario che, congiuntamente a tali operazioni, la macchina fosse in grado di cambiare il proprio stato; pertanto assumeva che, pi\`u in generale, la macchina dovesse essere in grado, a seconda dello stato corrente e del simbolo letto dalla testina, di:
    \begin{itemize}
        \item cambiare il simbolo sotto la testina e lo stato corrente e spostare la testina di una cella.
    \end{itemize} 
    Per consentire alla macchina di scegliere, in base alla situazione corrente, quale azione eseguire, era necessario dotarla di un \textbf{programma}, inteso come insieme di regole, dette \textbf{quintuple}, della forma (q1, a, b, M, q2) da interpretare come segue: 
    \begin{itemize}
        \item Nello stato \textbf{q1}, leggendo il simbolo a, passa allo stato \textbf{q2} e scrivi il simbolo b sul nastro, poi sposta la testina a sinistra o a destra o rimani inerte, a seconda che \textbf{M} sia \textbf{S} (Sinistra), \textbf{D} (Destra) o \textbf{I} (Inerte).
    \end{itemize}
    Per descrivere la situazione in cui si trova una macchina di Turing in un certo momento basta fornirne la \textbf{Configurazione Istantanea}, ovvero il contenuto del nastro, la posizione della testina e lo stato corrente. Nell'ambito di questo modello una computazione altro non \`e che una sequenza di configurazioni istantanee, di cui la prima (detta \textbf{Configurazione Iniziale}) codifica l'input e lo stato iniziale, mentre ogni altra configurazione istantanea \`e ottenuta da quella immediatamente precedente eseguendo, di volta in volta, l'unica quintupla applicabile. Si noti che non necessariamente una tale sequenza \`e finita, poich\`e la macchina si arresta solo quando nessuna quintupla pu\`o essere applicata: in tal caso l'ultima configurazione (detta \textbf{Configurazione Finale}) \`e quella che codifica l'output. \newline\`E bene tener presente che esistono molte versioni (tutte computazionalmente equivalenti) della macchina di Turing. Per esempio si pu\`o definire la Macchina du Turing in modo che utilizzi quadruple anzich\`e quintuple. Analizzando le caratteristiche della Macchina di Turing, si nota che tale modello computazionale introduce, in maniera formale ma semplice e essenziale, alcuni elementi tipici della programmazione imperativa, quali: \newline \newline \newline \textbf{locazione}
        \par Le celle del nastro di una Macchina di Turing hanno la stessa logica di funzionamento delle locazioni, in quanto contengono un \textit{valore} che pu\`o essere aggiornato in maniera \textit{distruttiva} (ovvero sostituito senza che sia possibile risalire al valore precedente).
    \newline \newline \textbf{assegnamento}
        \par Le quintuple del tipo (q1, a, b, M, q2), che sostituiscono il simbolo \textbf{a} con il nuovo simbolo \textbf{b}, realizzano l'assegnamento del valore \textbf{b} alla locazione corrispondente alla cella sotto la testina.
    \newline  \newline \textbf{memoria}
        \par Data la corrispondenza fra celle e locazioni, il nastro non \`e altro che una sorta di memoria lineare infinita ad accesso sequenziale, nel senso che per poter accedere ad una determinata locazione \`e necessario spostare la testina fino a raggiungere la cella corrispondente.\newline \newline \textbf{stato} \par Gi\`a nella definizione delle Macchine di Turing incontriamo il concetto di stato, come elemento che condiziona le scelte che la macchina opera durante il calcolo, e di configurazione, come descrizione della situazione in cui la macchina si trova in un dato istante.
            \newline \newline \textbf{iterazione}
                \par una computazione, dato il numero finito di quintuple avviene attraverso l'iterazione dell'\textit{esecuzione} delle quintuple (che possono venire interpretate come una sorta di istruzioni della macchina). \newpage
\section{La nascita del dualismo \textit{Hardware-Software}}
Nella concezione originale di Turing, i programmi per le Macchine di Turing (TM) erano parte integrante del controllo finito; per ogni problema che si volesse risolvere, bisognava definire un'opportuna TM, che poteva prendere in input i dati da elaborare, ma non poteva essere riprogrammata per eseguire un calcolo diverso da quello per cui era stata pensata.
\begin{figure}[ht]
    \centering
    \includegraphics[width=6.66cm, height=3.36cm] {fig1}
    \caption{Una generica Macchina di Turing}
    \label{fig:turing1}
\end{figure}
Ci\`o era in accordo con l'intento iniziale di Turing, che non era quello di realizzare fisicamente le sue macchine, ma quello di determinare quale fosse l'insieme di funzioni per cui era possibile, in linea di principio, costruire un'apposita TM.\newline Successivamente Turing, considerando il fatto che una macchina di Turing si pu\`o rappresentare attraverso una stringa di simboli (basta dare una rappresentazione lineare della tabella che descrive la funzione di transizione, per esempio scrivendo una dopo l'altra le quintuple che corrispondono alle varie caselle della tabella di transizione), dimostr\`o che \`e possibile definire una Macchina di Turing Universale che, dati in ingresso la descrizione di una TM e il relativo input, simula il comportamento della prima: nasce cos\`i l'idea di una vera e propria macchina programmabile:
\begin{figure}[ht]
    \centering
    \includegraphics[width=6.66cm, height=3.36cm] {fig2.jpg}
    \caption{Macchina di Turing Universale}
    \label{fig:turing2}
\end{figure}
\newline La dimostrazione dell'esistenza di una TM universale segna anche la nascita del dualismo \textit{hardware-software}, cio\`e della contrapposizione fra ci\`o che \`e fisicamente realizzato e ci\`o che \`e descrizione formale delle operazioni da svolgere. Da quanto detto sopra si nota come hardware e software nascono come equivalenti: quello che si pu\`o fare via software \`e anche realizzabile in hardware, e viceversa. La nozione di MT universale \`e concettualmente alla base del modello di architettura di Von Neuman (architettura \textbf{stored program}) che prende il nome da chi la propose, il matematico \href{http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Von_Neumann.html}{\textbf{John Von Neumann}}. In tale tipo di architettura la CPU (Central Processing Unit) \`e preposta all'interpretazione del programma memorizzato in un'altra componente fisica, la RAM (\textit{Random Access Memory}). Schematicamente:
\begin{figure}[ht]
    \centering
    \includegraphics[width=6.66cm, height=3.36cm] {fig3.jpg}
    \caption{Architettura di Von Neumann}
    \label{fig:turing3}
\end{figure}
\newline Gi\`a in questa architettura sono presenti \textit{in nuce} tutte quelle componenti presenti nella maggior parte delle architetture sviluppate fino ai giorni nostri. \`E possibile fornire una descrizione astratta e, volendo, pi\`u dettagliata dei moduli che la compongono (per esempio analizzando le funzionalit\`a della CPU si possono identificare ulteriori componenti al suo interno). Il nostro obiettivo nelle presenti note \`e proprio quello arrivare ad una definizione del concetto di Macchina Astratta Imperativa, una descrizione cio\`e il pi\`u generale possibile delle componenti che formano le architetture basate sul modello di Von Neuman, alla cui base abbiamo visto esserci il modello computazionale delle Macchine di Turing.\newline 
Si noti come non sia possibile fornire una definizione di Macchina Astratta in generale, poich\`e alla base di una Macchina Astratta c'\`e sempre un particolare Modello Computazionale. Le Macchine Astratte basate sul modello di Turing vengono dette \underline{imperative} poich\`e alla base di tale modello c'\`e il concetto di \underline{comando} (istruzione). Vedremo in seguito come esista una precisa corrispondenza tra Macchine Astratte e linguaggi di programmazione. I linguaggi di programmazione \underline{imperativi} sono appunto quelli corrispondenti appunto a macchine astratte \underline{imperative}.\newline Appare abbastanza evidente come, partendo da differenti modelli computazionali, si possa pervenire a differenti nozioni di Macchina Astratta (per esempio: \underline{funzionale}, \underline{object-oriented}, \underline{logica}, \underline{parallelo/concorrente}) L'attenzione che noi riserveremo alle macchine astratte imperative non \`e tanto dovuto alla "migliore qualita" del modello di Turing rispetto ad altri, ma al fatto che la stragrande maggioranza delle architetture concrete sono basate sul modello di Von Neuman e questo \`e dovuto a motivazioni puramente di carattere \underline{tecnologico}.\newline Nella definizione di macchina di Turing, essendo questa un modello computazionale, tutto \`e ridotto al minimo necessario e descritto in modo molto formale. Se vogliamo arrivare ad una definizione di schema di macchina per calcolare basato su questo modello occorre isolare le "componenti" della macchina di Turing e descriverle in modo pi\`u generale possibile (attraverso un procedimento di "astrazione"). Quello che otteniamo non \`e pi\`u un modello computazionale, ma uno schema in cui poter inserire tutte le macchine basate sul modello computazionale imperativo (anche quelle che non calcolano tutte le funzioni calcolabili).\newline Per fare questo, non partiamo dalla definizione di macchina di Turing vera e propria, ma da quella di macchina di Turing Universale in cui abbiamo:
\begin{itemize}
    \item una memoria (il nastro) che contiene dati e programmi. Questi sono rappresentati e strutturati in un modo semplicissimo nelle MT. Ma si pu\`o pensare di poterle strutturare e rappresentare in altro modo, magari utilizzando il supporto di particolari procedure e strutture, se ce ne fosse bisogno.
    \item un modo di recuperare gli argomenti delle operazioni. Nelle MT questo modo \`e semplicemente leggere quel che c'\`e sotto la testina. Per\`o se vogliamo astrarre, possiamo pensare che, in generale, le operazioni possono recuperare gli argomenti in vari modi dalla memoria, utilizzando opportuni procedimenti e strutture.
    \item un modo per determinare qual'\`e la prossima istruzione da eseguire. In generale qualcosa che, servendosi magari di determinate strutture, determini qual \`e il flusso della sequenza di istruzioni da eseguire.
    \item qualcosa che, utilizzando tutto ci\`o che \`e a disposizione e coordinandolo opportunamente, permetta l'esecuzione dei programmi.
\end{itemize}
Sulla base di questo, nella prossima sezione daremo la nostra definizione di Macchina Astratta imperativa.
\section{Il concetto di Macchina Astratta}
Formalmente una \textbf{Macchina Astratta} (Imperativa\footnote{D'ora in avanti ometteremo il termine "imperativo", visto che non ci occuperemo di macchine astratte di altro genere. Da sottolineare come la definizione fornita non sia assolutamente l'unica n\`e da considerarsi "la migliore".}) \`e:
\begin{quote} {\it un insieme di strutture dati e algoritmi in grado di memorizzare ed eseguire programmi.}
\end{quote}
 Le componenti principali di una macchina astratta sono:
\begin{itemize}
    \item un \textit{interprete}
    \item una \textit{memoria}, destinata a contenere il programma che deve essere eseguito e i dati su cui si sta operando.
    \item insieme di \textit{operazioni primitive} (cio\`e funzionalit\`a 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).
    \item un insieme di operazioni e strutture dati che gestiscono il \textit{flusso di controllo}, ovvero che governano l'ordine secondo il quale le operazioni, descritte dal programma, vengono eseguite.
    \item un insieme di operazioni e strutture dati per il \textit{controllo del trasferimento dei dati}, che si occupa di recuperare gli operandi e memorizzare i risultai delle varie istruzioni.
    \item un insieme di operazioni e strutture dati per la \textit{gestione della memoria}.
\end{itemize}
\begin{figure}[ht]
    \centering
    \includegraphics[width=8.66cm, height=5.36cm] {fig4.jpg}
    \caption{Struttura di una Macchina Astratta}
    \label{fig:turing4}
\end{figure}
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 cio\`e per il diverso modo di gestire l'esecuzione di un programma. La componente fondamentale che d\'a alla macchina astratta la capacit\`a di eseguire programmi \`e l'\textbf{interprete}: esso coordina il lavoro delle altre parti della macchina astratta eseguendo un semplice ciclo \textit{FETCH}/\textit{EXECUTE}, finch\`e non viene eseguita una particolare istruzione primitiva (detta \textit{HALT}) che ne provoca l'arresto immediato. Schematicamente:
\begin{figure}[ht]
    \centering
    \includegraphics[width=8.66cm, height=10.36cm] {fig5.jpg}
    \caption{Il ciclo Fetch-Execute}
    \label{fig:turing5}
\end{figure}
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 (\textit{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.
\subsection*{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 modalit\`a 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 modalit\`a di indirizzamento indiretto.
\subsection*{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.
\subsection*{Ristorante}
    La nozione di macchina astratta \`e ben pi\`u generica di quanto si possa credere. Infatti anche un ristorante, in un certo senso si pu\`o 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 pu\`o esser visto come l'inseme delle "operazioni" della macchina. La "memoria" della nostra macchina sar\`a il taccuino del cameriere. L' "interprete" del ristorante pu\`o essere il cameriere stesso che, letta la prima "istruzione" la "decodifica", dicendo agli inservienti quali ingredienti portare a quale cuoco. Ovviamente anche la dispensa dovr\`a esser vista come parte della memoria del ristorante (la parte che memorizza gli "argomenti" delle istruzioni. Un altro cameriere provveder\`a a "memorizzare" sul nostro tavolo il risultato dell'esecuzione dell'istruzione.
Ovviamente certi esempi di macchine astratte necessitano di un minimo di elasticit\`a mentale per poter esser ricondotti al nostro schema formale.
Teniamo presente inoltre che in realt\`a quella che abbiamo fornito \`e una descrizione della "realizzazione" della macchina astratta Ristorante. \newline \newline 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 per\`o una enorme variet\`a di possibilit\`a 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 pi\`u 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 possibilit\`a vanno bene. Fare una scelta particolare in una definizione generale come la nostra non troverebbe giustificazione rispetto alle altre possibilit\`a.
\section{Linguaggi di Programmazione e Macchine Astratte}
Come visto nella definizione, una macchina astratta esegue programmi memorizzati al suo interno. Il \textit{linguaggio macchina} (\textit{LM}) di una macchina astratta \textit{M} \`e il linguaggio in cui si esprimono tutti i programmi interpretabili dall'interprete di \textit{M}. \textit{LM} definisce quindi l'insieme delle strutture dati che realizzano la rappresentazione interna dei programmi eseguibili da \textit{M}. \`E bene mettere in evidenza che quelli che normalmente chiamiamo programmi in \textit{LM} non sono altro che particolari dati primitivi su cui opera l'interprete di M. Spesso per\`o \`e pi\`u conveniente pensare ad un programma in termini di \textit{stringhe di caratteri}. L'insieme di queste versioni dei programmi forma il cosiddetto \textit{LMEST} (\textit{Linguaggio Macchina \textbf{EST}erno}).\newline
\`E importante notare che sia il programma espresso in forma direttamente memorizzabile nella macchina, sia la sua versione mnemonica, sono due rappresentazioni dello stesso oggetto: \textbf{il programma astratto}. Quindi useremo il termine linguaggio macchina ad indicare indifferentemente \textit{LM} o \textit{LMEST} (un esempio di \textit{LM} sono i vari livelli di tensione nei bit di una memoria fisica, mentre il suo \textit{LMEST} sar\`a un insieme di stringhe di caratteri "0" e "1").
Il compito di realizzare la conversione dal linguaggio \textit{LMEST} al linguaggio \textit{LM} \`e facilmente automatizzabile ed \`e svolto dal \textit{LOADER} (cos\`i detto perch\`e carica il programma nella memoria della macchina astratta).\newline Cos\`i come data una macchina astratta resta definito un linguaggio di programmazione (il suo linguaggio macchina), analogamente dato un linguaggio di programmazione resta definita una macchina astratta che ne supporta le caratteristiche principali e che ha il dato linguaggio come suo linguaggio macchina. \`E da notare che gli \textit{High Level Language} o \textit{HLL} (cio\`e quei linguaggi che consentono al programmatore di esprimere i propri algoritmi in una forma molto vicina a quella in cui li ha pensati) definiscono macchine astratte tanto pi\`u complesse quanto maggiore \`e la potenza espressiva del linguaggio in questione.
Ad esempio, un linguaggio che ha come tipo primitivo il tipo astratto \textit{Lista}, avr\`a associata una macchina astratta che disporr\`a di opportune istruzioni macchina elementari per la realizzazione delle varie operazioni sulle liste (\textit{Head}, \textit{Tail}, \textit{isNull}), e che avr\`a una organizzazione della memoria capace di gestire l'allocazione dinamica dello spazio per le liste in maniera automatica.\newline
Di conseguenza la realizzazione in \textit{hardware} \`e opportuna solo per macchina astratte relativamente semplici, mentre nel caso di una macchina astratta associata ad un linguaggio di alto livello questa scelta \`e poco conveniente, e risulta preferibile una realizzazione non hardware.\newline
Nella prossima sezione affronteremo le varie possibilit\`a di realizzazione di Macchine Astratte.
\section{Realizzazione delle Macchine Astratte}
    Affinch\`e i programmi scritti in un dato linguaggio di programmazione L possano essere eseguiti, \`e necessario che la corrispondente macchina astratta venga implementata. Fondamentalmente \`e possibile adoperare tre tecniche:
    \begin{itemize}
        \item realizzazione hardware
        \item interpretazione (emulazione)
        \item traduzione (compilazione)
    \end{itemize}
    \subsection*{Realizzazione hardware}
        Con questa tecnica si realizzano in hardware tutte le componenti della macchina. In linea di principio tale tecnica \`e sempre possibile. E comprensibile per\`o che venga utilizzata solo macchina astratte relativamente semplici, a causa di considerazioni di carattere pratico, quali la scarsa flessibilit\`a della realizzazione in hardware e l'elevato costo di progettazione e realizzazione in hardware di componenti dalle funzionalit\`a molto complesse.\newline Ovviamente l'evoluzione delle tecniche di integrazione dei circuiti ha reso possibile (e render\`a possibile sempre pi\`u in futuro) la realizzazione hardware di macchine sempre di maggior complessit\`a.
    \subsection*{Realizzazione interpretativa}
        A differenza della precedente, questa seconda tecnica, come anche la terza, richiede l'esistenza di una macchina gi\`a realizzata (\textit{macchina ospite}). La tecnica interpretativa consiste nel realizzare tutte le componenti della macchina (cio\`e tutti gli algoritmi e le strutture dati che li definiscono) mediante programmi e strutture dati del linguaggio della macchina ospite.
        Di questo tipo di realizzazione ne esistono in realt\`a due tipi:
        \begin{itemize}
            \item emulazione via \textbf{firmware}
            \item emulazione via \textbf{software}
        \end{itemize}
        In linea di principio queste sono entrambe emulazioni software, la differenza consiste nel tipo della macchina ospite (microprogrammata nel primo caso) e nella realizzazione fisica della memoria che contiene i programmi che realizzano la le strutture dati e gli algoritmi della macchina. \underline{Nel primo caso} la macchina ospite \`e realizzata in hardware e la parte programmi della memoria di tale macchina \`e una memoria ad alta velocit\`a, solitamente di sola lettura, realizzata sullo stesso chip che contiene le altre componenti della macchina. Una tale macchina ospite \`e detta microprogrammata ed \`e estremamente semplice (le operazioni non sono altro che semplici operazioni su registri). I programmi di tale macchina ospite che realizzano gli algoritmi e le strutture dati della macchina che si vuole realizzare vengono chiamati \textit{microprogrammi}.
        \underline{Nel secondo caso} invece non c'\`e alcun vincolo su come sia realizzata la macchina ospite (e in particolare la sua memoria).
        \textit{Le due tecniche di emulazione differiscono sostanzialmente nelle prestazioni della macchina astratta emulata}, in particolare rispetto alla velocit\`a di esecuzione, che nel caso firmware \`e paragonabile a quella della realizzazione in hardware puro. Ovviamente la realizzazione nel caso firmware offre minore flessibilit\`a in caso di future modifiche o estensioni della macchina realizata.
        \`E bene sottolineare che la realizzazione tramite firmware, molto in voga fino a non molti anni fa, sta lentamente tramontando, o si limita a porzioni sempre pi\`u piccole della macchina da realizzare. Questo a causa dell'affermarsi dei principi che sono alla base delle architetture \textit{RISC}.
        Quando parliamo di realizzazione interpretativa \`e bene fare sempre attenzione, quando parliamo di interprete, a quale macchina facciamo riferimento: la componente interprete della macchina che vogliamo ottenere \`e realizzata da un programma scritto nel linguaggio della macchina ospite la cui esecuzione \`e affidata alla componente interprete della macchina ospite. 
    \subsection*{Realizzazione compilativa}
        La tecnica compilativa si basa sulla idea di tradurre una volta per tutte l'intero programma scritto in \textit{L} in un programma funzionalmente equivalente scritto nel linguaggio della macchina ospite. Il compito di eseguire tale traduzione \`e eseguito da un programma detto \textbf{compilatore}. In una realizzazione compilativa, uno si chiede: "si, ma dove sono le componenti della macchina che realizziamo?". In realt\`a \`e come se ci fossero, perch\`e noi dall'esterno vediamo esattamente gli effetti di una macchina realizzata.

\section{Macchine Intermedie e Struttura a livelli dei computer moderni}
    La differenza di potenza espressiva fra una macchina astratta che vogliamo realizzare e la macchina che abbiamo a disposizione per tale realizzazione (\textit{Macchina Ospite} o \textit{HOST}) \`e detta \textbf{semantic gap}. Spesso il \textit{semantic gap} tra la macchina da realizzare e la macchina \textit{HOST} \`e talmente grande che \`e opportuno introdurre una o pi\`u macchine astratte intermedie.\newline
    Tipicamente, nell'implementare un linguaggio di programmazione (cio\`e la sua corrispondente macchina astratta) non si procede mai per pura compilazione o pura interpretazione su una data macchina \textit{HOST}. La pura interpretazione potrebbe non essere soddisfacente a causa della scarsa efficienza della macchina realizzata emulando via software strutture dati, algoritmi e soprattutto l'interprete. Anche una realizzazione puramente compilativa a causa di un notevole \textit{semantic gap} potrebbe portare a produrre programmi per la macchina ospite di dimensioni eccessive e magari lenti, senza considerare le difficolt\`a che si possono incontrare per sviluppare dei traduttori tra linguaggi eccessivamente diversi. Uno schema implementativo molto usato prevede fasi sia compilative che interpretative; la situazione, relativamente ad una realizzazione compilativa sopra una interpretativa \`e rappresentata nella figura seguente.
    \begin{figure}[ht]
        \centering
        \includegraphics[width=10.66cm, height=5cm] {fig9.jpg}
        \caption{ Implementazione di L mediante traduzione nel linguaggio di una macchina intermedia M\ped{I} e simulazione di M\ped{I} sulla macchina \textit{HOST}.}
        \label{fig:turing9}
    \end{figure}
    Per colmare il divario fra la macchina \textit{ML} e la macchina \textit{HOST}, si progetta un'apposita \textit{macchina intermedia M\ped{I}} che viene realizzata sulla macchina \textit{HOST}. A questo punto la traduzione dei programmi in \textit{L} avverr\`a in termini del linguaggio di \textbf{M\ped{I}}, e successivamente il programma per \textit{M\ped{I}} cos\'i ottenuto verr\`a eseguito tramite interpretazione sulla macchina \textit{HOST}.
    Nel progetto della macchina intermedia bisogna tenere conto di due requisiti di efficienza:
    \begin{enumerate}
        \item velocit\`a di simulazione della \textit{Macchina Intermedia M\ped{I}} sulla macchina \textit{HOST}.
        \item compattezza del codice prodotto nel linguaggio della macchina M\ped{I}.
    \end{enumerate}
    Per soddisfare tali requisiti, tipicamente M\ped{I} \`e solo un'estensione della macchina \textit{HOST}, nel senso che ne condivide l'interprete, e ne potenzia alcuni aspetti mediante un insieme di routine note come \textit{Run-Time System}, atto a colmare, negli aspetti, la differenza delle due macchine.\newline Tornando alla \href{fig:turing9}{Fig. 6}, notiamo che la pura interpretazione e la pura compilazione si hanno nei casi estremi caratterizzati rispettivamente dal fatto che la M\ped{I} coincida con la macchina ML o la macchina \textit{HOST}.\newline
    Un esempio concreto di applicazione di questo schema si ha per il linguaggio di programmazione Java. In questo caso, la macchina intermedia M\ped{I} \`e la JVM (\textit{Java Virtual Machine}\footnote{\`E bene tener presente la possibile ambiguit\`a che potrebbe generare questo nome. La Java Virtual Machine infatti non \`e la macchina astratta corrispondente al linguaggio JAVA, bens\`i la macchina intermedia per JAVA.}), il cui linguaggio \`e detto \textbf{Bytecode}, mentre il Run-Time System viene detto Java RunTime Enviroment. Per quanto riguarda la macchina \textit{HOST} , nella pratica si hanno diverse realizzazione: dal PentiumII all'UltraSPARC, al PicoJavaII.\newline
    Non necessariamente la realizzazione di ML sulla macchina intermedia deve essere compilativa. Ci possono essere svariati motivi per avere sia ML che la macchina intermedia realizzati entrambi per interpretazione.\newline
    Nello sviluppo dei nostri sistemi di calcolo in genere il procedimento descritto viene generalizzato, portando ad insieme di livelli di macchine astratte che si frappongono fra la macchina realizzata in hardware e la macchina astratta del "livello" utente, che potrebbe essere quella corrispondente ad un \textit{HLL} o ad un particolare applicativo (per esempio il programma "Office" o il sistema di gestione utilizzato dalla vostra banca altro non sono che particolari macchine astratte).Gli scopi di tale stratificazione sono molteplici: gestire la complessit\`a di progettazione, aumentare la flessibilit\`a del sistema ecc.
    \begin{figure}[ht]
        \centering
        \includegraphics[width=10cm, height=8cm] {fig6.jpg}
        \caption{Gerarchia di macchine astratte}
        \label{fig:turing6}
    \end{figure}
    \newline Il livello pi\`u basso rappresenta il computer reale e il linguaggio macchina che esso \`e in grado di eseguire direttamente. Ciascuno dei livelli superiori rappresenta una macchina astratta, i cui programmi devono essere o \underline{tradotti} in termini di istruzioni di uno dei livelli inferiori (non necessariamente del livello immediatamente al di sotto), o \underline{interpretati} da un programma che gira su di una macchina astratta di livello strettamente inferiore.\newline
    \`E da notare che nella pratica non \`e raro che un livello realizzi una macchina astratta che non copre del tutto il livello sottostante ma ne potenzia alcune delle caratteristiche, lasciandone trasparire del tutto altre.\newline
    \`E possibile, cio\`e, che alcune delle componenti della macchina siano esattamente quelle della macchina ospite, mentre altre siano completamente diverse o magari delle semplici estensioni. Nella seguente figura \`e schematizzata la possibilit\`a di una macchina, per esempio hardware, sulla quale \`e realizzata un'altra macchina attraverso emulazione via firmware solo di alcune sue componenti. Su quest'ultima \`e poi realizzata una ulteriore macchina che ha alcune componenti realizzate in software, mentre altre sono esattamente le stesse della macchina sottostante o di quella del livello ancora inferiore.
     \begin{figure}[ht]
        \centering
        \includegraphics[width=4cm, height=4cm] {fig8.jpg}
        \caption{Il livello L\ped{0} non è del tutto coperto dai livelli superiori}
        \label{fig:turing7}
    \end{figure}
    Un semplice e chiaro esempio di livello che non copre i livelli sottostanti lo potrete trovare quando affronterete il paragrafo 5.5.10 del Tanenbaum: The picoJava II Instructions. Vedrete come l'hardware dell'architettura picoJava II non realizza completamente le istruzioni del linguaggio JVM. Alcune di esse sono infatti ralizzate con microprogrammi, mentre altre, attraverso alune trap ad un software handler, sono realizzate in software. Quindi \`e come se esistesse una macchina astratta JVM\ped{0} realizzata in hardware, sulla quale \`e realizzata una macchina JVM\ped{1} e su quest'ultima la JVM completa. Ovviamente in tale semplice caso le parti firmware di JVM\ped{1} e software si JVM non coprono alcuna parte di JVM\ped{0}, semplicemente la estendono. Un tipico computer moderno si pu\`o quindi pensare come una serie di macchine astratte realizzate una sopra l'altra, ciascuna in grado di fornire funzionalit\`a via via pi\`u potenti.
    Per chiarire le idee sulla complessit\`a di questa decomposizione in livelli, esaminiamo una \underline{possibile} stratificazione dei comuni PC. \`E da notare tuttavia che non \`e in alcun modo necessario che un sistema di calcolo abbia un numero prefissato di livelli di astrazione: quella che segue \`e solo una possibile soluzione, che mostra come ogni livello colmi la sua parte di semantic gap.
    \begin{figure}[ht]
        \centering
        \includegraphics[width=8cm, height=6cm] {fig7.jpg}
        \caption{Un esempio di gerarchia di macchine astratte 
        (di lato, il modo in cui sono realizzate)}
        \label{fig:turing8}
    \end{figure}
    Nello schema non sono rappresentati i livelli sottostanti la \textbf{logica digitale}.\newline
    Le componenti fondamentali del \textit{livello 0} sono le cosiddette \underline{porte logiche} (\textit{GATES}): a partire da raggruppamenti di esse si formano i registri e le memorie. Le \textit{GATES} sono dispositivi elettronici che, pur appartenendo al mondo analogico, costituiscono il ponte verso il mondo digitale, poich\`e esse tipicamente realizzano funzionalit\`a (Not, And, Or, ...) che sono ben formalizzabili in termini di una teoria discreta nota come \textbf{Algebra di Boole}.\newline
    Collezioni di \underline{registri} e \underline{circuiti digitali} che realizzano funzionalit\`a aritmetico-logiche sono alla base del livello 1. Qui troviamo altri elementi di interesse come il \underline{datapath} e le strutture che presiedono al suo controllo. 
    A questo livello inizia a diventare chiara l'idea di \textbf{flusso di informazione} poich\`e sequenze di bit viaggiano da una componente all'altra (della macchina astratta di questo livello) venendo eventualmente elaborate.\newline
    Il linguaggio del \textit{livello 2} \`e quello cui tipicamente ci si riferisce quando si parla di \textbf{linguaggio macchina} di un certo computer. In termini tecnici, questo livello \`e noto come \textit{ISA Level} (\textit{Istruction Set Architecture Level}); tipiche istruzioni di questo livello sono \textit{ADD}, \textit{MOVE}, \textit{SUB}, ... \newline
    Questo livello \`e di solito direttamente implementato in hardware nelle architetture \textit{RISC}, mentre \`e tipicamente \`e realizzato mediante interpretazione firmware nelle architetture \textit{CISC}.\newline
    Il \textit{livello 3} evidenzia quella caratteristica precedentemente notata di non coprire del tutto i livelli sottostanti: si tratta del livello del \textbf{Sistema Operativo} (\textit{SO}). In esso la maggior parte delle istruzioni dell'\textit{ISA level} sono disponibili tali e quali; sono inoltre presenti nuove operazioni, che consentono un livello di astrazione notevolmente pi\`u alto nell'ambito della gestione della memoria e del flusso di controllo.\newline
    Tre delle principali funzionalit\`a offerte dal Sistema Operativo sono:
    \begin{itemize}
        \item il concetto di \textit{FILE}: a questo livello si realizza il salto qualitativo verso una memoria molto strutturata e organizzata gerarchicamente (\textbf{File System}) in cui informazioni complesse possono essere immagazzinate e recuperate con grande facilit\`a.
        \item la \textit{MEMORIA VIRTUALE}: il Sistema Operativo offre ai livelli di astrazione superiore una macchina astratta con una quantit\`a di memoria principale di gran lunga superiore a quella effettiva, liberando cos\`i il programmatore dai limiti fisici derivanti dalla particolare dotazione della macchina.
        \item l'astrazione di \textit{PROCESSO} e il \textit{MULTITASKING}: la possibilit\`a di avere pi\`u "pezzi" di programma (\textbf{processi}) in esecuzione indipendente e (pseudo-)parallela \`e una delle caratteristiche che si \`e andata affermando negli anni; \`e tale meccanismo che rende possibili funzionalit\`a quali la stampa in background o la garbage collection, etc.\newline
        Questo in linea di principio significa che il livello del Sistema Operativo in realt\`a pu\`o mettere a disposizione non una singola, ma molteplici macchine astratte.
    \end{itemize}
    La programmazione dei livelli introdotti fino a questo momento \`e tipicamente compito di una cerchia ristretta di programmatori (i cosiddetti sistemisti), poich\`e si tratta di macchine astratte che sono state ideate non perch\`e interessanti in s\`e, ma in quanto necessarie per riuscire a gestire la complessit\`a dell'implementazione delle macchine astratte di livello superiore.\newline
    Il \textit{livello 4} segna quindi una rottura con i livelli precedenti: si tratta del livello dell'\textbf{assembly}, il primo che presenti qualche caratteristica (sebbene elementare) dei linguaggi di programmazione moderni (uso di etichette, mnemonici per le istruzioni, presenza di macro, variabili globali, procedure, etc...).\newline 
    Tipicamente il livello 4 \`e realizzato sulle macchine sottostanti mediante il meccanismo di traduzione realizzato da un pezzo software (tipicamente scritto in ISA level language) noto come \textbf{ASSEMBLY language}.
    Tale livello si pu\`o definire come il pi\`u basso utilizzabile dal programmatore di applicazioni eseguite dal sistema di calcolo. Ad ogni modo \`e al \textit{livello 5} che generalmente entrano in gioco gli HLL: C, Java, C++, Haskell, Prolog, etc... Si tratta del livello pi\`u vario, dove troviamo tutte le possibili soluzioni implementative, anche per macchine astratte relative allo stesso linguaggio: ad esempio, esistono varianti sia interpretate che compilate del BASIC.\newline
    
    Come accennato in precedenza l'avvento di Java ha portato alla nascita di un livello intermedio tra quelli del linguaggio ad alto livello e quello dell'assembly. Infatti prima di essere eseguiti, i programmi Java vengono tradotti in \textit{bytecode}, ovvero nel linguaggio macchina della \textit{Java Virtual Machine} (JVM), che \`e realizzata mediante interpretazione sui livelli sottostanti; successivamente saranno i bytecode cos\`i ottenuti che verranno eseguiti sulla \textit{JVM}. I vantaggi di questa tecnica hanno recentemente portato alla implementazione di molti linguaggi di programmazione (anche non Object Oriented) sulla JVM, piuttosto che sui livelli 2-3-4: sostanzialmente la JVM si sta affermando come macchina astratta standard all'interno della stratificazione tipica dei moderni sistemi di calcolo.\newline
    Teniamo a precisare ancora una volta che i livelli appena descritti sono una tra le infinite possibilit\`a teoriche di strutturazione a livelli di un sistema di calcolo.
    \subsection*{Programmazione delle Macchine Astratte}
        Riguardo la programmazione \`e talvolta possibile imbattersi (sempre pi\`u raramentente, per fortuna) in affermazioni del seguente tipo:
        \begin{quote}
            Una programmazione consapevole ed adeguata per una particolare realizzazione di una macchina astratta \`e possibile solo se l'utente conosce non solo la struttura della macchina astratta, ma anche quali componenti sono stati realizzati direttamente in hardware, quali emulati, quali interpretati. Infatti, scegliere un modo piuttosto che un altro di realizzare un algoritmo pu\`o risolversi in un guadagno di prestazioni, dovuto alla maggiore efficienza della realizzazione di alcune componenti della macchina astratta rispetto ad altri.
        \end{quote}
    Gi\`a il fatto che questa sia una affermazione eccessivamente generica (che non fa cio\`e riferimento a particolari contesti in cui poter essere utilizzata) dovrebbe insospettirci. L'Informatica \`e la metafora della vita e nella vita non si pu\`o fare alcuna affermazione che sia valida a prescindere da specifici contesti. 
Ergo, \`e possibile che in particolari contesti l'affermazione citata possa esser vera (pensiamo per esempio al caso di programmare una macchina astratta corrispondente al sistema di controllo della temperatura del nocciolo di una centrale atomica; ovviamente bisogna sfruttare al massimo tutte le possibilit\`a di velocizzare la routine che, identificato un insolito aumento di temperatura, metta in moto tutte le procedure di sicurezza). In generale per\`o sappiamo che non esiste solo la velocit\`a di esecuzione di un programma come unico parametro di valutazione; per esempio c'\`e anche la trasportabilit\`a di un programma. Un programma che abbia buone prestazioni solo perch\`e fa affidamento si certe caratteristiche della realizzazione della macchina astratta su cui gira, potrebbe avere prestazioni scadentissime su altre realizzazioni della stessa macchina. Questa considerazione \`e ancora pi\`u importante se si considera come sia sempre pi\`u rilevante oggi il concetto di codice mobile.
In generale quindi dobbiamo dire che nel programmare una macchina astratta dobbiamo far riferimento solo alla sua specifica, non alla sua realizzazione.
\subsection{Al di sotto della Logica Digitale}
    Per poter inquadrare tutti gli aspetti dei sistemi di calcolo \`e possibile descrivere anche dei livelli sottostanti il livello 0. I livelli al di sotto della logica digitale costituiscono l'anello di congiunzione fra i fenomeni fisici e le tecniche per l'automazione del calcolo. Possiamo quindi identificare il \textbf{livello -1} (\textit{Il livello dell'elettronica circuitale}) e quello \textbf{-2} (\textit{Il livello della Fisica dello stato solido}). Pertanto, a \textit{livello -2} i soggetti di interesse sono la \underline{struttura fisica dei solidi} e \underline{le propriet\`a dei semiconduttori} (o, in futuro, le propriet\`a di trasmissione della luce delle microfibre ottiche). Argomenti che appartengono prettamente all'ambito della Fisica e dei quali pertanto non ci si occupa in un corso di Architettura degli Elaboratori.\newline
    Sfruttando le conoscenze proprie del \textit{livello -2} \`e possibile progettare e realizzare quei \underline{dispositivi elettronici} (transistor, diodi, MOS, ...) che sono gli attori principali del \textit{livello -1}. In questo livello si studia come combinare convenientemente pi\`u dispositivi elettronici per ottenere le cosiddette \underline{porte logiche} (\textit{GATES}), pervenendo cos\`i agli elementi di base del livello della logica digitale. \`E importante osservare che i \textit{livelli -2} e \textit{-1} sono dei livelli di astrazione fortemente diversi dai livelli al di sopra della logica digitale, poich\`e non si tratta di descrizione di Macchine Astratte. In altri termini, mentre \`e possibile parlare, ad esempio, della Macchina Astratta associata al \textit{livello 2}, non ha senso parlare di Macchina Astratta del \textit{livello -1} e \textit{-2} (in realt\`a, come esercizio puramente speculativo, si pu\`o anche provare a vedere tali livelli come macchine astratte). Per rendere pi\`u chiara la differenza fra i meccanismi di astrazione al di sopra e al di sotto della logica digitale, possiamo considerare l'analogia seguente (che come tutte le analogie non informatiche \`e da prendere con le pinze). Vogliamo realizzare una \textbf{macchina astratta teatrale} a cui, dato in pasto il testo di un'opera teatrale (il programma) lo metta in scena (lo "esegue"). Per far questo prendiamo delle persone (il livello 0) e coordinandole attraverso l'uso di un regista otteniamo la nostra macchina (a livello 1). Utilizzando il livello 1 potremmo anche realizzare una macchina pi\`u complessa, una macchina cio\`e le cui istruzioni siano non le battute di un testo, ma titoli di intere opere. Questa "macchina" pi\`u complessa si pu\`o realizzare "estendendo quella del livello 1" attraverso una biblioteca di opere e qualcuno che preso il titolo di un'opera lo "interpreti" andando nello scaffale giusto a prendere il testo dell'opera in questione e portando il testo al regista.
    Ora in questo "sistema a livelli", se volessimo considerare dei livelli inferiori allo 0 quali potrebbero essere? Essendo delle persone gli elementi del livello 0, il \textit{\textbf{livello -1} potrebbe essere quello degli \underline{organi} che compongono un persona umana, \textbf{quello -2} quello dei \underline{tessuti} che compongono i vari organi, \textbf{quello -3} quello delle \underline{cellule}}.\newline 
    Analizzando la gerarchia appena descritta nella sua totalit\`a, appare evidente come, sebbene si tratti di livelli di astrazione costruiti intorno all'uomo, il meccanismo di astrazione su cui si basano i livelli \`e del tutto diverso al di sopra e al di sotto di esso.\newline
    Ritornando alla stratificazione dei sistemi di calcolo, ci si rende conto che i livelli -1 e -2 sono utili perch\`e ci aiutano a capire il funzionamento del livello della logica digitale, ma non perch\`e costituiscano esempi di realizzazione di Macchime Astratte, in quanto sono basati su un meccanismo di astrazione differente. \`e anche per questo motivo, oltre che per quelli gi\`a citati precedentemente, che non ce ne occupiamo in dettaglio.
\section{Programmazione e Livelli di Astrazione}
    La gerarchia di macchine astratte di un sistema di calcolo non termina necessariamente con l'implementazione di un linguaggio di programmazione \textit{HLL} \textit{L}. Infatti un qualunque programma in \textit{L} aggiunge un ulteriore livello alla gerarchia estendendo la macchina astratta associata a \textit{L} (o nel caso \textit{L} non sia interpretato, \textit{la macchina intermedia di L}) in alcuni dei suoi componenti, simulando generalmente nuove operazioni e nuovi tipi di dato. Da questo punto di vista quindi qualunque attivit\`a di programmazione pu\`o essere considerata come una attivit\`a di definizione e di realizzazione di macchine astratte.\newline Vedere la programmazione in un certo linguaggio come estensione della macchina astratta ad esso associata evidenzia il fatto che la potenza e la flessibilit\`a di un linguaggio di programmazione dipendono dai meccanismi di astrazione che il linguaggio stesso offre.
    Praticamente tutti i linguaggi forniscono un meccanismo di astrazione (sia esso procedura, funzione o subroutine), che permette di definire nuove operazioni. Solo alcuni linguaggi (tipicamente quelli \textbf{object-oriented}) possiedono meccanismi soddisfacenti per la definizione di nuovi tipi di dato astratti. Infine la possibilit\`a di estendere le altre componenti della macchina astratta (\textit{contollo di sequenza}, \textit{controllo sul trasferimento dati}, \textit{gestione della memoria}), non \`e stata ancora realizzata in nessuno dei linguaggi di programmazione maggiormente in uso. Si potrebbe pensare che, anche se il linguaggio non fornisce un particolare meccanismo di astrazione, sia comunque possibile simulare in esso un qualunque costrutto; tuttavia in questo caso l'estensione risulter\`a di pi\`u complessa realizzazione per il programmatore e di pi\`u difficile utilizzo da parte dell'utente rispetto alla corrispondente estensione ottenuta con un linguaggio di programmazione che possiede meccanismi di astrazione adeguati.

\end{document}