Esercizi sulle Macchine Astratte



Esercizio 1


Ho un sistema di calcolo in cui il livello superiore implementa una macchina astratta il cui linguaggio e' il linguaggio JAVA. Voglio implementare sopra questo livello la macchina astratta corrispondente al linguaggio di microprogrammazione Mic-1. Posso farlo? Se si, perche' cio' e' possibile ed in che modo posso realizzarlo?

  • Soluzione.


    Esercizio 2

    La componente "memoria" di una Macchina Astratta deve necessariamente essere realizzata in hardware? Perche'?

  • Soluzione.


    Esercizio 3

    HASKELL e' un linguaggio di programmazione funzionale, basato cioe' su un modello computazionale differente da quello che e' alla base dei linguaggi di programmazione imperativi.
    La nozione di Macchina Astratta per linguaggi di programmazione come HASKELL (MAF, Macchina Astratta Funzionale) e' simile a quella descritta nel corso?
    Una MAF ha le stesse componenti di una MA ?
    se si, le componenti di una MAF hanno funzioni differenti dalle relative componenti di una MA?
    oppure una MAF e' essenzialmente diversa da una MA?
    se si, pensare a come potrebbe essere la sua struttura.

    Esercizio 4

    Si consideri il linguaggio di programmazione che abbia programmi definiti dalla seguente grammatica: 
    Programma ::=  Istr | Istr;Programma
Istr ::=   m[Index]<-0 | m[Index]<-1 | m[Index]<-m[Index] | if B then Istr 
        | input(Index) | output(Index) 
B ::= m[Index]=0 | m[Index]=1 | m[Index]=m[Index]
Index ::= 0,1,2,3
    dove il significato delle istruzioni e' il seguente: 
    m[x] <- 0     (nella cella di memoria di indirizzo x poni 0)
m[x] <- 1     (nella cella di memoria di indirizzo x poni 1)
m[x] <- m[y]  (nella cella di memoria di indirizzo x poni il contenuto della
               cella di indirizzo y)
if B then I   (se B e' vera allora esegui I)
input(Index)  (leggi da tastiera un valore ammissibile e inseriscilo in m[Index]
output(Index  (scrivi su monitor il valore in m[Index]
    Index, potendo essere solo 0,1,2,3, inplica che la memoria per i dati associata al nostro linguaggio ha solo quattro celle. Inoltre queste celle della parte di memoria riservata ai dati sono formate da un unico bit (possiamo memorizzarci solo 0 oppure 1).
    Ovviamente questo linguaggio non e' universale (non ha la potenza computazionale per descrivere qualsiasi algoritmo).

    Dire, motivando dettagliatamente la risposta, perche' la Macchina Astratta associata al linguaggio descritto puo' essere realizzata SOLAMENTE in Hardware.

  • Soluzione.
    Esercizio 5

    (a) Descrivere la componente Interprete delle Macchine Astratte.

    (b) Potrebbe accadere che nell'implementazione della MA del livello 5 di un sistema di calcolo la componente memoria sia esattamente la componente memoria del livello 3 ?


  • Soluzione.


    Esercizio 6

    E' possibile avere delle macchine astratte senza la componente Interprete?
    Motivare brevemente la risposta.

  • Soluzione.


    Esercizio 7


    (a) E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio Java?
    Motivare brevemente la risposta.
    (b) Dire perche' e' indispensabile che in un sistema di calcolo organizzato a livelli esista il livello 6.

  • Soluzione.


    Esercizio 8

    (a) Avete cinque righe a disposizione (scritte normali e non una di piu') per dirmi perche' e' conveniente organizzare a livelli i sistemi di calcolo.
    (b) Dire perche' in un sistema di calcolo organizzato a livelli almeno un livello deve essere necessariamente realizzato per compilazione (traduzione).
  • Soluzione.


    Esercizio 9

    Qual'e' il numero teorico massimo di livelli in un sistema di calcolo? Perche'?

  • Soluzione.


    Esercizio 10

    Perche' in un sistema di calcolo strutturato a livelli non puo' esserci piu' di un livello realizzato per traduzione?
  • Soluzione.

    Esercizio 11

    Spiegare perche' in una macchina astratta realizzata al livello 1 di un sistema di calcolo, la componente "gestione della memoria" e' praticamente inesistente.
  • Soluzione.

    Esercizio 12

    (a) In quali casi e' possibile avere un sistema di calcolo organizzato a livelli in cui tutti i livelli sono realizzati in hardware?

    (b) In un sistema di calcolo organizzato a livelli, cosa si intende quando si dice che "un livello non e' completamente coperto da quello superiore"? Fornire un possibile esempio.
  • Soluzione.

    Esercizio 13

    (a) Riguardo molti microprocessori si parla di backward compatibility (compatibilita'). Visto che un microprocessore puo' esser visto come la realizzazione hardware (di parte) di una macchina astratta, qual e', secondo voi, il significato di backward compatibility in termini di macchine astratte? in altre parole, cosa significa che una macchina astratta e' backward compatible?

    (b) La Macchina di Turing e' alla base della nostra definizione di Macchina Astratta. Quindi una Macchina di Turing potrebbe esser vista anche come una semplicissima macchina astratta. Dire brevemente cosa fa l'interprete di una macchina di Turing.
    In una macchina di Turing universale ci sono sempre due interpreti, uno, per modo di dire, "hardware", e l'altro "software". E' vero? Perche'?

  • Soluzione.

    Esercizio 14

    Una cucina dotata di tutto, compresa una persona che sta cucinando, puo' esser vista come la realizzazione hardware di una macchina astratta? Se si, identificarne la varie componenti. Se no, spiegarne il motivo.
  • Soluzione.

    Esercizio 15
    E' possibile che una macchina astratta che tipicamente sarebbe realizzata in hardware venga realizzata per traduzione o compilazione su una macchina astratta corrispondente ad un linguaggio ad alto livello come Java o C?

    Esercizio 16
    (a) Si consideri la struttura a livelli di un calcolatore.
  • Si motivi l'introduzione di tale struttura.
  • Si spieghi cos'e' il semantic gap.
  • Possibile soluzione. (by Camillo Bosco)

    (b) Si veda un'impresa di costruzioni come un sistema di calcolo che realizza edifici abitabili. Si descrivano almeno 2 dei suoi livelli di macchina astratta (uno puo' essere il livello "muratore").
  • Possibile soluzione. (by Camillo Bosco)

    Esercizio 17

    Cosa si intende per "realizzazione" di una Macchina Astratta per interpretazione? e per compilazione (traduzione)?
    Esercizio 18

    Delle varie fasi del ciclo di un interprete in una macchina astratta, qual e' quella piu' lenta a venire eseguita? Perche'?

  • Possibile soluzione.
    Esercizio 19
    E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio Java? Motivare brevemente la risposta.
    Dire poi perche' in un sistema di calcolo organizzato a livelli almeno un livello deve essere necessariamente realizzato per compilazione (traduzione).
  • Soluzione.
    Esercizio 20
    Cosa significa, in un sistema di calcolo a livelli, che "un livello che realizza una macchina astratta non copre del tutto il livello sottostante"?

    Esercizio 21
    Descrivere le componenti Interprete e Controllo Sequenza di una generica macchina astratta.
    Esercizio 22
    Si consideri la seguente frase presa dalle note del corso:
    "La gerarchia di macchine astratte di un sistema di calcolo
    non termina necessariamente con l'implementazione di un linguaggio di programmazione HLL L."
    Commentarla, spiegandone il significato.
    Esercizio 23
    Commentare e chiarire il senso della seguente frase: "È da notare che nella pratica non è 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."
    Esercizio 24
    Si consideri un sistema a livelli contenente i livelli L1, L2 ed L3.
    L1 e' realizzato in hardware e tale che il tempo di esecuzione di un'istruzione di L1 e' di K secondi.
    I livelli L2 ed L3 sono invece interpretati. Ogni istruzione di L2 viene realizzata con n istruzioni di L1. Ogni istruzione di L3 viene realizzata con n istruzioni di L2.
    Il linguaggio L3 e' m volte piu' potente del linguaggio L2 (per ogni cosa che fa un'istruzione di L3, ce ne vogliono m di L2 per fare la stessa cosa. In breve, lo stesso algoritmo si realizza in L2 con un programma m volte piu' lungo di uno equivalente in L3).
    Siano P3 e P2 due programmi semanticamente equivalenti scritti, rispettivamente, in L3 e L2 (semanticamente equivalenti significa che calcolano la stessa cosa).
    Fornire delle espressioni che esprimano il tempo di esecuzione di P3 e di P2 in modo da poter confrontare tali tempi tra loro e poter decidere (fissati n ed m) se, dal punto di vista della velocita' di esecuzione, convenga eseguire P3 sul livello 3 oppure P2 sul livello 2.
    Giustificare brevemente la soluzione proposta.
  • Soluzione.
    Esercizio 25
    Descrivere brevemente cosa si intende per "struttura a livelli dei sistemi di calcolo".
    Esercizio 26
    Si consideri la seguente frase presa dalle note del corso:
    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 puo' risolversi in un guadagno di prestazioni, dovuto alla maggiore efficienza della realizzazione di alcune componenti della macchina astratta rispetto ad altri.
    E' un'affermazione condivisibile? Giustificare brevemente la risposta.
    Esercizio 27

    Si consideri il linguaggio di programmazione, che chiameremo VSL (Veeery Simple Language), che ha i programmi definiti dalla seguente grammatica: 
    Programma ::=  Istr; | Istr;Programma
Istr ::=  m[x]<-0 | m[x]<-1 | m[x]<-m[y] | m[x]<-m[y]ANDm[z] | m[x]<-m[y]ORm[z] |  if B then Istr
B ::= m[x]=0 | m[x]=1 | m[x]=m[y]
    dove il significato delle istruzioni e' il seguente: 
    m[x] <- 0     (nella cella di memoria di indirizzo x poni 0)
m[x] <- 1     (nella cella di memoria di indirizzo x poni 1)
m[x] <- m[y]  (nella cella di memoria di indirizzo x poni il contenuto della
               cella di indirizzo y)
m[x] <- m[y]ANDm[z]  (nella cella di memoria di indirizzo x poni l'OR del contenuto della
               cella di indirizzo y con quello della cella z)
m[x] <- m[y]ORm[z]  (nella cella di memoria di indirizzo x poni l'OR del contenuto della
               cella di indirizzo y con quello della cella z)
    Inoltre x, y e z possono avere come valori solo 0, 1, 2, 3. Questo significa che la memoria per i dati associata al nostro linguaggio ha solo quattro celle. Inoltre queste celle della parte di memoria riservata ai dati sono formate da un unico bit (possiamo memorizza rci solo 0 oppure 1).
    Ovviamente questo linguaggio non e' universale (non ha la potenza computazionale per descrivere qualsiasi algoritmo).

    Realizzare modo compilativo la macchina astratta VSL sopra la macchina astratta JAVA.
    Realizzare modo interpretativo la macchina astratta VSL sopra la macchina astratta JAVA.
  • Realizzazione compilativa, by Danilo Vaccalluzzo.
    Esercizio 28

    Che relazione esiste tra le Macchine di Turing ed il concetto di Macchina Astratta Imperativa? Ogni macchina astratta e' comunque imperativa, o possono esserci altre nozioni di macchina astratta? Giustificare.
    Esercizio 29

    Fornire la definizione di Macchina Astratta.
    Esercizio 30

    Descrivere le possibili realizzazioni di macchine astratte. Descrivere inoltre il concetto di struttura a livelli dei sistemi di calcolo e discutere dei vantaggi della struttura a livelli.
    Esercizio 31

    (a) Fornire la definizione di Macchina Astratta e descriverne le componenti.

    (b) Come e' possibile realizzare una macchina astratta? Cosa si intende per organizzazione a livelli di un sistema di calcolo?

    (c) E' possibile avere un sistema di calcolo organizzato a livelli in cui esistano tre livelli corrispondenti alla macchina astratta del linguaggio C++?
    Motivare brevemente la risposta.
    Esercizio 32

    Implementare in modo compilativo ed in modo interpretativo il linguaggio WHILE di [SR]
    Esercizio XX


    Esercizio XX