Macchina astratta con IL termine macchina ci riferiamo ad un calcolatore



Scaricare 0.52 Mb.
13.11.2018
Dimensione del file0.52 Mb.



Macchina astratta

  • con il termine macchina ci riferiamo ad un calcolatore

  • hardware---macchina fisica

  • hardware--software

  • In ogni caso e’ una macchina astratta che esegue programmi di un linguaggio di programmazione



Linguaggio macchina

  • programmi: costituiti a partire da istruzioni di un linguaggio

  • una macchina astratta esegue programmi di un linguaggio L

  • chiamiamo L il linguaggio macchina della macchina astratta



una collezione di strutture dati ed algoritmi in grado di memorizzare ed eseguire programmi

  • una collezione di strutture dati ed algoritmi in grado di memorizzare ed eseguire programmi

  • componenti della macchina astratta

    • interprete
    • memoria (dati e programmi)
    • controllo
    • operazioni “primitive”


una collezione di strutture dati ed algoritmi per

  • una collezione di strutture dati ed algoritmi per

    • acquisire la prossima istruzione (gestendo cicli, loop)
    • gestire le chiamate ed i ritorni dai sottoprogrammi
    • acquisire gli operandi e memorizzare i risultati delle operazioni
    • mantenere le associazioni fra nomi e valori denotati
    • gestire dinamicamente la memoria
    • …...


contiene sia i dati che i programmi che devono essere eseguiti

  • contiene sia i dati che i programmi che devono essere eseguiti

  • la gestione della memoria dipende dal tipo di linguaggio

  • per i linguaggi ad alto livello e’ complicata, istruzionche allocano e deallocano in memoria

  • necessarie strutture dati tipo stack, heap



controllo

  • controllo



M macchina astratta

  • M macchina astratta

  • LM linguaggio macchina di M

    • è il linguaggio che ha come stringhe legali tutti i programmi interpretabili dall’interprete di M
  • i programmi sono particolari dati su cui opera l’interprete

  • ai componenti di M corrispondono componenti di LM

    • tipi di dato primitivi
    • costrutti di controllo
      • per controllare l’ordine di esecuzione
      • per controllare acquisizione e trasferimento dati


implementare un linguaggio L vuol dire realizzare la macchina astratta che ha L come linguaggio macchina

  • implementare un linguaggio L vuol dire realizzare la macchina astratta che ha L come linguaggio macchina

  • tipicamente, la macchina astratta la dovremo realizzare su una macchina gia’ esistente, macchina ospite

  • la macchina ospite avra’ un suo linguaggio macchina



M macchina astratta

  • M macchina astratta

  • i componenti di M sono realizzati mediante strutture dati ed algoritmi implementati nel linguaggio macchina di una macchina ospite MO, già esistente (implementata)

  • il lingaggio della macchina ospite potrebbe essere di basso o alto livello



M macchina astratta LM linguaggio macchina di M

  • M macchina astratta LM linguaggio macchina di M

  • L linguaggio ML macchina astratta di L

  • implementazione di L =

    • realizzazione di ML su una macchina ospite MO
  • se L è un linguaggio ad alto livello ed MO è una macchina “fisica”

    • l’interprete di ML è necessariamente diverso dall’interprete di MO
      • ML è realizzata su MO in modo interpretativo
      • l’implementazione di L si chiama interprete
      • esiste una soluzione alternativa basata su tecniche di traduzione (compilatore?)


L linguaggio ad alto livello

  • L linguaggio ad alto livello

  • ML macchina astratta di L

  • MO macchina ospite

  • implementazione di L 1: interprete (puro)

    • ML è realizzata su MO in modo interpretativo
    • scarsa efficienza, soprattutto per colpa dell’interprete (ciclo di decodifica)
  • implementazione di L 2: compilatore (puro)

    • i programmi di L sono tradotti in programmi funzionalmente equivalenti nel linguaggio macchina di MO
    • i programmi tradotti sono eseguiti direttamente su MO
      • ML non viene realizzata
    • il problema è quello della dimensione del codice prodotto
  • due casi limite che nella realtà non esistono quasi mai



L linguaggio ad alto livello

  • L linguaggio ad alto livello

  • ML macchina astratta di L

  • MI macchina intermedia

  • LMI linguaggio intermedio

  • MO macchina ospite

  • traduzione dei programmi da L al linguaggio intermedio LMI+

  • realizzazione della macchina intermedia MI su MO



ML = MI interpretazione pura

  • ML = MI interpretazione pura

  • MO = MI traduzione pura

    • possibile solo se la differenza fra MO e ML è molto limitata
      • L linguaggio assembler di MO
    • in tutti gli altri casi, c’è sempre una macchina intermedia che estende eventualmente la macchina ospite in alcuni componenti


quando l’interprete della macchina intermedia MI coincide con quello della macchina ospite MO

  • quando l’interprete della macchina intermedia MI coincide con quello della macchina ospite MO

  • che differenza c’è tra MI e MO?

    • il supporto a tempo di esecuzione (rts)
      • collezione di strutture dati e sottoprogrammi che devono essere caricati su MO (estensione) per permettere l’esecuzione del codice prodotto dal traduttore (compilatore)
    • MI = MO + rts
  • il linguaggio LMI è il linguaggio macchina di MO esteso con chiamate al supporto a tempo di esecuzione



il supporto a tempo di esecuzione contiene

  • il supporto a tempo di esecuzione contiene

    • varie strutture dati
      • la pila dei records di attivazione
        • ambiente, memoria, sottoprogrammi, …
      • la memoria a heap
        • puntatori, ...
    • i sottoprogrammi che realizzano le operazioni necessarie su tali strutture dati
  • il codice prodotto è scritto in linguaggio macchina esteso con chiamate al rts



quando l’interprete della macchina intermedia MI non coincide con quello della macchina ospite MO

  • quando l’interprete della macchina intermedia MI non coincide con quello della macchina ospite MO

  • esiste un ciclo di interpretazione del linguaggio intermedio LMI realizzato su MO

    • per ottenere un codice tradotto più compatto
    • per facilitare la portabilità su diverse macchine ospiti
      • si deve riimplementare l’interprete del linguaggio intermedio
      • non è necessario riimplementare il traduttore


nel compilatore non c’è di mezzo un livello di interpretazione del linguaggio intermedio

  • nel compilatore non c’è di mezzo un livello di interpretazione del linguaggio intermedio

    • sorgente di inefficienza
      • la decodifica di una istruzione nel linguaggio intermedio (e la sua trasformazione nelle azioni semantiche corrispondenti) viene effettuata ogni volta che si incontra l’istruzione
  • se il linguaggio intermedio è progettato bene, il codice prodotto da una implementazione mista ha dimensioni inferiori a quelle del codice prodotto da un compilatore

  • un’implementazione mista è più portabile di un compilatore

  • il supporto a tempo di esecuzione di un compilatore si ritrova quasi uguale nelle strutture dati e routines utilizzate dall’interprete del linguaggio intermedio



è un’implementazione mista

  • è un’implementazione mista

    • traduzione dei programmi da Java a byte-code, linguaggio macchina di una macchina intermedia chiamata Java Virtual Machine
    • i programmi byte-code sono interpretati
    • l’interprete della Java Virtual Machine opera su strutture dati (stack, heap) simili a quelle del rts del compilatore C
      • la differenza fondamentale è la presenza di una gestione automatica del recupero della memoria a heap (garbage collector)
    • su una tipica macchina ospite, è più semplice realizzare l’interprete di byte-code che l’interprete di Java
      • byte-code è più “vicino” al tipico linguaggio macchina


interprete puro

  • interprete puro

    • ML = MI
    • interprete di L realizzato su MO
    • alcune implementazioni (vecchie!) di linguaggi logici e funzionali
      • LISP
  • compilatore

    • macchina intermedia MI realizzata per estensione sulla macchina ospite MO (rts, nessun interprete)
      • C, C++, PASCAL
  • implementazione mista

    • traduzione dei programmi da L a LMI
    • i programmi LMI sono interpretati su MO
      • Java
      • i “compilatori” per linguaggi funzionali e logici (ML)


la traduzione genera codice in un linguaggio più facile da interpretare su una tipica macchina ospite

  • la traduzione genera codice in un linguaggio più facile da interpretare su una tipica macchina ospite

  • ma soprattutto può effettuare una volta per tutte (a tempo di traduzione, staticamente) analisi, verifiche e ottimizzazioni che migliorano

    • l’affidabilità dei programmi
    • l’efficienza dell’esecuzione
  • varie proprietà interessate

    • inferenza e controllo dei tipi
    • controllo sull’uso dei nomi e loro risoluzione “statica”
    • ….


dipende dalla semantica del linguaggio

  • dipende dalla semantica del linguaggio

  • certi linguaggi (LISP) non permettono praticamente nessun tipo di analisi statica

  • altri linguaggi funzionali più moderni (ML) permettono di inferire e verificare molte proprietà (tipi, nomi, …) durante la traduzione, permettendo di

    • localizzare errori
    • eliminare controlli a tempo di esecuzione
      • type-checking dinamico nelle operazioni
    • semplificare certe operazioni a tempo di esecuzione
      • come trovare il valore denotato da un nome


Java è fortemente tipato

  • Java è fortemente tipato

  • le relazioni di subtyping permettono che una entità abbia un tipo vero (actual type) diverso da quello apparente (apparent type)

    • tipo apparente noto a tempo di traduzione
    • tipo vero noto solo a tempo di esecuzione
    • è garantito che il tipo apparente sia un supertype di quello vero
  • di conseguenza, alcune questioni legate ai tipi possono solo essere risolte a tempo di esecuzione

    • scelta del più specifico fra diversi metodi overloaded
    • casting (tentativo di forzare il tipo apparente ad un suo possibile sottotipo)
    • dispatching dei metodi (scelta del metodo secondo il tipo vero)
  • controlli e simulazioni a tempo di esecuzione



questo corso si interessa di linguaggi, concentrandosi su due aspetti

  • questo corso si interessa di linguaggi, concentrandosi su due aspetti

    • semantica formale
      • sempre in forma eseguibile, implementazione ad altissimo livello
    • implementazioni o macchine astratte
      • interpreti e supporto a tempo di esecuzione
  • perché la semantica formale?

    • definizione precisa del linguaggio indipendente dall’implementazione
      • il progettista la definisce
      • l’implementatore la utilizza come specifica
      • il programmatore la utilizza per ragionare sul significato dei propri programmi
  • perché le macchine astratte?

      • il progettista deve tener conto delle caratteristche possibili dell’implementazione
      • l’implementatore la realizza
      • il programmatore la deve conoscere per utilizzare al meglio il linguaggio


la maggior parte dei corsi e dei libri sui linguaggi si occupano di compilatori

  • la maggior parte dei corsi e dei libri sui linguaggi si occupano di compilatori

  • perché noi no?

    • il punto d vista dei compilatori verrà mostrato in un corso fondamentale della laurea magistrale
    • delle cose tradizionalmente trattate con il punto di vista del compilatore, poche sono quelle che realmente ci interessano
  • per capire meglio, guardiamo la struttura di un tipico compilatore







Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale