Entità denotabili Elementi di un linguaggio di programmazione a cui posso assegnare un nome "Le entità denotabili possono essere entità i cui nomi sono definiti {{c1::dal linguaggio di programmazione}} e i cui nomi sono definiti {{c1::dall'utente.}}" "Definiti dal linguaggio: tipi primitivi, operazioni primitive...
Definiti dall'utente: variabili, parametri, procedure, tipi, costanti simboliche, classi, oggetti..." Binding Un binding è una associazione fra un nome e una entità del linguaggio. Lo scope di un binding... Lo scope di un binding definisce quella parte del programma nella quale il binding è attivo. Static binding Si riferisce ad una associazione attivata prima di mandare il programma in esecuzione dynamic binding si riferisce ad una associazione attivata dopo aver mandato il programma in esecuzione. "Se i linguaggi ""compilati"" cercano di risolvere il binding staticamente..." "I linguaggi ""interpretati"" devono risolvere il binding dinamicamente." Ambiente "L'ambiente è definito come l'insieme delle associazioni nome-entità esistenti a run time in uno specifico punto del programma, e in uno specifico momento dell'esecuzione." Dichiarazioni "Le dichiarazioni sono il costrutto linguistico che permette di introdurre associazioni nell'ambiente." Aliasing Nomi diversi per uno stesso oggetto Blocchi Un blocco è una regione testuale del programma che può contenere dichiarazioni Blocco associato ad una funzione corpo della funzione con le dichiarazioni dei parametri formali Blocco in-line Meccanismo per raggruppare i comandi (ad esempio corpo di un ciclo). Ambiente locale "l'insieme delle associazioni dichiarate locamente al blocco, compreso le eventuali associazioni relative ai parametri." Ambiente non locale "associazioni dei nomi che sono visibili all'interno del blocco ma non dichiarati nel blocco stesso." Ambiente globale associazioni per i nomi usabili da tutte le componenti che costituiscono il programma. "L'ambiente può cambiare a run time, ma i cambiamenti avvengono in precisi momenti:" entrando in un blocco (creazione di associazioni per i nomi locali, disattivazione delle associazioni per i nomi ridefiniti).
uscendo dal blocco (distruzione delle associazioni locali, riattivazione delle associazioni per i nomi che erano stati ridefiniti). Naming creazione di associazione fra nome e oggetto denotato. Referencing "Riferimento a un oggetto denotato mediante il suo nome (uso del nome per accedere all'oggetto)." Disattivazione di associazione fra nome e oggetto denotato (la nuova associazione maschera la vecchia). Riattivazione di associazione "fra il nome e oggetto denotato (una vecchia associazione che er mascherata è riattivata all'uscita da un blocco)." Unnaming "distruzione di associazione fra nome e oggetto denotato (ad esempio, all'uscita di un blocco)." Ambiente (env) Il tipo polimorfo utilizzato sia in fase di progettazione del linguaggio che nelle implementazioni per mantenere il binding tra nomi e valori di un opportuno tipo. Un ambiente [$$]\Sigma[/$$] è una collezione di binding. Astrattamente, un ambiente, è una funzione del tipo... Ide -> Value + Unbound Dato un ambiente [$$]\Sigma: Ide \leftarrow Value + Unbound[/$$], [$$]\Sigma(x)[/$$] denota "Il valore v associato a nell'ambiente, oppure il valore speciale unbound." "[$$]\Sigma [x = v][/$$] indica l'ambiente in cui" Ad ogni occorrenza di x, x assume valore v. Da cosa è determinato lo scope statico o lessicale? è determinato dalla struttura sintattica del programma. Da cosa è determinato lo scope dinamico? "E' determinato dalla struttura a tempo di esecuzione." Per quale ambiente differiscono scope statico e dinamico? "Differiscono solo per l'ambiente non locale." Una dichiarazione locale in un blocco è visibile - In quel blocco
- In tutti i blocchi in esso annidati (salvo ri-dichiarazioni). La regola di visibilità è basata su cosa nello scoping statico? E su cosa nello scoping dinamico? Sul testo del programma (scoping statico)
Sul flusso di esecuzione (scope dinamico). Le componenti di un interprete sono "Lo scanner, il parser, il type checker e l'interprete vero e proprio." Lo scanner svolge... "L'analisi lessicale" Il parser svolge "L'analisi grammaticale" Il type checker svolge Il controllo dinamico dei tipi "L'interprete svolge" "L'esecuzione del codice" "Lo scanner (o tokenizzatore) trasforma la {{c1::rappresentazione testuale dell'espressione}} (stringa) in {{c2::una lista di token}}." Lo scanner controlla che non si utilizzino Simboli non previsti. Lo scanner non effettua Un controllo grammaticale. "Il parser controlla che l'espressione sia" sintaticamente corretta (appartenga al linguaggio definito dalle regole BNF). Il parser genera "L'abstract syntax tree (AST)." Come si realizza un parser per un linguaggio semplice? La grammatica viene resa non ambigua, e se il linguaggio è molto semplice, si implementa un parser a discesa ricorsiva. Come si realizza un parser per un linguaggio non molto semplice? Dopo aver reso la grammatica non ambigua, si usa un parser generator, ovvero un software che genera il codice del parser a partire dalla grammatica. "Nell'implementazione di un parser si crea una funzione per ogni" categoria sintattica. "Nell'implementazione di un parser le funzioni sono..." mutualmente ricorsive. "Nel parser, le funzioni si richiamano l'un l'altra. Queste funzioni ____ per generare l'albero di sintassi astratta." Consumano token Nel parser, ogni chiamata di funzione restituisce... "Un nodo dell'AST. In questo modo l'AST corrisponde all'albero delle chiamate." SOS sta per Structural Operational Semantics La Structural Operational Semantics è "Semantica perchè è una descrizione del significato del linguaggio.
Operativa perchè  descrive il comportamento dei programmi attraverso una relazione di transizione (cattura le operazioni che vengono svolte passo-passo durante l'esecuzione).
Strutturale perchè la relazione di transizione è definita utilizzando regole di inferenza basate sulla struttura sintattica." Nella semantica small-step ogni passo della relazione di transizione esegue una singola operazione. Nella semantica small-step ogni computazione è una sequenza di passi. Nella semantica big-step cosa descrive la relazione di transizione? "Descrive in un solo passo l'intera computazione." Nella semantica big-step, dove sono descritte le singole operazioni? "sono descritte nell'albero di derivazione di quella transizione." Quali sono le componenti di una Macchina di Von Neumann? Ha due componenti principali:
- Memoria, dove sono memorizzati programmi e dati
- Unità centrale di elaborazione, che ha il compito di eseguire i programmi immagazzinati in memoria, prelevando le istruzioni e eseguendole. Macchina astratta un sistema virtuale che rappresenta il comportamento di una macchina fisica La macchina astratta individua "L'insieme delle risorse necessarie per l'esecuzione dei programmi,
Un insieme di istruzioni specificamente progettato per operare queste risorse." Una macchina astratta per un linguaggio funzionale è caratterizzata da tre elementi: "Lo stack per gestire le chiamate di funzioni
L' environment per gestire le associazioni nome-valore
Il closure per rappresentare il valore di una funzione." La macchina astratta è una collezione di strutture dati e algoritmi. Quali sono le sue componenti? "Interprete
Memoria
controllo
operazioni ""primitive""." La componente di controllo svolge i seguenti ruoli: Acquisire la prossima istruzione
Aquisire operandi e memorizzare risultati delle operazioni
gestire chiamate e ritorni dai sottoprogrammi
Gestire i thread
Mantenere le associazioni nome-valore
Gestire dinamicamente la memoria. "L'interprete è un programma che prende {{c1::il programma da eseguire}} sottoforma di {{c1::albero di sintassi astratta}} e lo esegue ispezionando la struttura del programma." Se è una macchina astratta, Lè "il suo linguaggio macchina, ovvero il linguaggio che ha come stringhe legali tutti i programmi interpretabili dall'interprete di M." Il compilatore trasforma codice di alto livello in codice di basso livello. La front end di un compilatore legge il programma sorgente e determina la sua struttura sintattica e semantica. La back end di un compilatore Genera il codice nel linguaggio macchina, di un programma equivalente al sorgente. Le due fasi principali del front-end di un compilatore Sono la fase dello scanner, o tokenizzazione (analisi semantica) e la fase di parser (analisi sintattica). Modularizzare Spezzettare i programmi in programmi più piccoli Astrazione procedurale Possibilità di scomporre un problema in sottoproblemi da risolvere con specifiche procedure/funzioni. Tipi di dato astratti Un tipo di dato astratto è tale che le sue istanze possono essere manipolate in modi che dipendono dalla sua semantica (il suo corportamento), e non dalla sua realizzazione. Come si può usare la modularità sotto il profilo delle tecniche di compilazione? Sono utili la compilazione separata e il linking Nel paradigma ad oggetti, il sistema software è un insieme di oggetti cooperanti Gli oggetti sono caratterizzati da due elementi: Uno stato
e un insieme di funzionalità. Nel paradigma a oggetti, come comunicano gli oggetti? Si scambiano messaggi Da cosa è rappresentato lo stato di un oggetto? Lo stato di un oggetto è solitamente rappresentato da un gruppo di attributi, proprietà o variabili. Cosa è la proprietà di incapsulamento? Idealmente, lo stato di un oggetto non dovrebbe essere accessibile dagli altri oggetti. In un linguaggio basato sul paradigma object-oriented, lo stato del programma dovrebbe corrispondere... "all'insieme degli stati degli oggetti che lo compongono" Le funzionalità di un oggetto "Sono rappresentate da un gruppo di metodi/funzioni che l'oggetto mette a disposizione degli altri oggetti." Cosa è il comportamento di un oggetto da un punto di vista di messaggi? è il modo in cui un oggetto risponde ad un messaggio ricevuto da un altro oggetto. Il comportamento di un oggetto è composto da due cose principali "L'invio di un messaggio codificato come chiamata di metodo
Risposta ad un messaggio codificato come restituzione del risultato." Oltre ad avere uno stato e delle funzionalità, gli oggetti sono caratterizzati anche da Identità (nome), ciclo di vita, e locazione (di memoria). Le differenze principali tra OOP e Paradigma Imperativo sono due: - Differente struttura dei programmi (insieme di classi vs insieme di comandi).
- Differente modello di esecuzione (memoria organizzata diversamente). Concetto: Astrazione ragionare sul comportamento di un oggetto senza conoscerne la rappresentazione interna. Cosa è un interfaccia, rispetto ad un oggetto? Che cosa un oggetto mette a disposizione degli altri. Ereditarietà come un oggetto può fare proprie le funzionalità di un altro oggetto, ad esempio estendendolo. Principio di sostituzione Quando un oggetto può essere usato al posto di un altro in maniera trasparente e controllata. Il polimorfismo in OOP "Un oggetto può processare altri oggetti di ""tipi diversi"", quindi è polimorfo." "I due approcci principali all'OOP sono:" Object Based e Class Based "Descrivi l'approccio object-based all'OOP. Descrivi parallelismi agli oggetti in altri linguaggi, spiega come è possibile accedere ai campi di un oggetto." Gli oggetti sono simili ai record
I campi (membri/proprietà/variabili) possono essere associati a funzioni.
Un metodo può accedere ai campi con il riferimento this. "Approccio class-based all'OOP" Un linguaggio basato sulle classi prevede un concetto di classe a cui corrispondono dei costrutti linguistici
Una classe definisce il contenuto degli oggetti di un certo tipo.
Gli oggetti vengono creati come istanze di una certa classe. "L'approccio object based è flessibile perchè" "Non è necessario scrivere il codice della classe prima di creare l'oggetto, e si possono creare tante varianti di un oggetto, senza scrivere tante classi." "L'approccio object-based crea una difficoltà perchè" "rende difficile capire quale sarà il tipo dell'oggetto ed ostacola i controlli di tipo statici." "L'approccio class based richiede al programmatore una maggiore disciplina perchè..." deve implementare le classi prima di creare gli oggetti "L'approccio class-based consente un maggiore controllo perchè..." consente i controlli di tipo statici sugli oggetti, che prende il nome di nominal typing. "L'eredità è una funzionalità che permette di definire una classe" sulla base di una classe preesistente I linguaggi object based, mantengono, per ogni oggetto una lista di Prototipi, che sono tutti gli oggetti da cui eredita funzionalità Proprietà di Subtyping "un oggetto B che è l'estensione di un oggetto A dovrebbe poter essere usato dovunque si possa usare A." Subtyping strutturale: un oggetto B è sottotipo di un oggetto A, se contiene Almeno tutti i membri pubblici presenti in A. Subtyping nominale: un tipo-classe B è sottotipo di un tipo-classe A se la classe B è stata definita sintatticamente come estensione della classe A. Nel nominal subtyping, il tipo di un oggetto corrisponde alla classe da cui è stato instanziato. Il structural subtyping è più flessibile perchè... 1. Non è necessario dire chi estende chi
2. Favorisce il polimorfismo. Il Nominal Subtyping è più rigoroso perchè "1. Mette in relazione di sottotipo solo classi che il programmatore ha dichiarato essere in questa relazione.
2. E' più semplice verificare per l'interprete." Un oggetto in Ocaml è un valore costituito da campi e metodi In Ocaml il tipo di un oggetto è creato da i metodi che esso contiene. "L'eredità per estensione è un tipo di eredità {{c1::semplice}}. Una classe può implementare più interfacce, ma può estendere una sola {{c2::superclasse}}." "Il metodo di object equals permette di confrontare due oggetti dal punto di vista dei {{c1::contenuti}}, mentre confrontare gli oggetti con '==' corrisponde a valutare se {{c2::i riferimenti a quegli oggetti sono uguali}}" Il modificatore {{c1::protected}} rende i membri visibili alle sotto classi senza renderli pubblici Dynamic Dispatch "E' una soluzione che permette di scegliere, tra metodi della stessa firma, quello ridefinito più recentemente." Overriding "Risalendo la gerarchia delle classi, si potrebbero incontrare più metodi con la stessa firma. L'overriding è il fenomeno per cui le classi hanno ridefinito metodi delle superclassi.
In questo caso la JVM esegue il primo metodo incontrato risalendo la gerarchia. (definito più recentemente)." Sharing strutturale nel dynamic dispatch La tabella della sottoclasse riprende la scrittura della tabella della superclasse. In pratica, se un metodo è alla riga due nella superclasse, allora è alla riga due nella sottoclasse. Il Dinamic Dispatch fa in modo che le chiamate di metodo possano essere eseguite in tempo "costante, senza visita dell'albero delle classi, e accesso diretto tramite offset e puntatore." Cosa sono le specifiche di un metodo pubblico? Sono le condizioni sui parametri e sul risultato, e il comportamento atteso del metodo. Cosa significa definire le specifiche di una classe? Significa esprimere in modo non ambiguo il comportamento atteso dei metodi pubblici di una classe.  Precondizioni (//REQUIRES) "condizioni sui parametri che devono essere soddisfatte all'inizio dell'esecuzione del metodo." Postcondizioni (//EFFECTS) "condizioni sul risultato e sul valore delle variabili che devono essere soddisfatte al termine dell'esecuzione del metodo, assumendo che all'inizio fossero vere le precondizioni." Principio di Sostituzione di Liskov Un oggetto di un sottotipo può sostituire un oggetto del supertipo senza influire sul comportamento dei programmi che usano il supertipo. Regola della segnatura Gli oggetti del sottotipo devono avere tutti i metodi del super-tipo.
Le signature dei metodi del sotto-tipo devono essere compatibili con quelle del supertipo. La regola dei metodi dice che le chiamate dei metodi del sotto-tipo devono... comportarsi come le chiamate dei corrispondenti metodi del super-tipo. La regola delle proprietà Il sottotipo deve preservare tutte le proprietà che possono essere provate sugli oggetti del supertipo. La macchina di Turing Universale (UTM) "E' una macchina di Turing capace di simulare il comportamento di una qualunque macchina di Turing." Un linguaggio di programmazione è detto Turing Completo se... "E' in grado di calcolare qualsiasi funzione calcolabile da una macchina di Turing" La architettura Von Neumann ha due componenti principali: Una memoria e una CPU. Programmazione funzionale La programmazione funzionale è un paradigma di programmazione il cui il flusso di esecuzione del programma assume la forma di una serie di valutazioni di funzioni matematiche. "Il punto principale di forza del paradigma funzionale è l'assenza di" effetti collaterali delle funzioni, che comporta una facile verifica della correttezza del programma Qual è il modello di calcolo più potente conosciuto? La macchina di Turing Il currying è una trasformazione che traduce una funzione con diversi parametri in una sequenza di funzioni che prendono ciascuna un singolo argomento. Un funzionale è "una funzione che restituisce un'altra funzione." La sintassi del lambda calcolo è la seguente: "Una variabile è
L'astrazione funzionale, ovvero la dichiarazione di una funzione
Oppure una applicazione, cioè la chiamata di funzione" Variabili legate Le variabili in una lambda-espressione che sono introdotte in un qualche lambda sono legate da quel lambda. Le variabili che non sono associate a una dichiarazione con qualche lambda sono dette libere. "L'insieme FV delle variabili libera di una lambda espressione è definito da tre equazioni" "Le variabili libere di una variabile x sono x.
Le variabili libere di espressione due applicata ad espressione due sono l'unione delle variabili libere di ciascuna.
Le variabili libere di una funzione ""lambda x ritorna e"" sono le variabili libere di e eccetto x." Alpha equivalenza Espressioni alpha-equivalenti rappresentano lo stesso programma. La alpha-conversione è la sostituzione di una variabile legata... "con un'opportuna variabile fresca." La valutazione di ([$$](\lambda x . e1) e2[/$$] Consiste nel valutare e1 dove ogni occorrenza di x in e1 è rimpiazzata da e2. Call by value o ordine applicativo "l'espressione del parametro attuale è valutata prima di essere associata al parametro formale." Call by name, o ordine normale (pigro) "l'espressione del parametro attuale non viene valutata prima di essere associata al parametro formale." Capture-avoiding substitution "Se in due espressioni c'è la stessa variabile, ma in un contesto è una variabile libera, e nell'altra è una variabile legata, si deve alpha-convertire la prima, introducendo una variabile fresca, per ottenere una sostituzione che eviti il problema." Beta riduzione "Se ho un'espressione del tipo ""lambda di x ritorna e1"" e ci applico ""e2"", la valutazione restituisce e1, in cui ad ogni occorrenza di x la si sostituisce con e2." La beta riduzione è una call-by-value o una call-by-name? "E' lazy, una call-by-name." Beta-equivalenza Due lambda espressioni sono beta equivalenti quando sono indistinguibili dal punto di vista computazionale: calcolano gli stessi risultati. Teorema di Church-Rosser "L'ordine in cui vengono scelte le beta riduzioni non influiscono sul risultato finale." Memory safety I puntatori alla memoria puntano sempre ad una memoria valida (allocata e di type/dimensione corretta). Perché la memory safety implica correttezza? Un programma memory unsafe può avere comportamenti errati e impredicibili. Descrivi la proprietà di memory containment Se un pezzo di memoria è allocato, o è raggiungibile dal root-set del programma o sarà deallocato. Perché il memory containment permette una performance migliore? Un programma con leak di memoria potrebbe andare incontro a terminazione non corretta a causa della mancanza di memoria. "L'aspetto chiave di Rust è" il type safety con concorrenza e gestione manuale della memoria, senza Garbage collector. Cosa vuol dire che Rust è expression oriented? "Le espressioni sono l'elemento centrale del linguaggio." Immutabilità in Rust Di default le variabili sono immutabili ma è possibile definire variabili mutabili con la parola chiave mut. I tipi scalari di rust sono i (interi), char, bool, f (float) Danglin references Indica un riferimento che punta ad una locazione di memoria non più valida. In Rust, il controllo dei tipi garantisce che non ci siano... Puntatori che puntano a memoria che è già stata liberata. "In Rust, i pattern di programmazione ""memory unsafe""" non sono permessi. Qual è la proprietà di Ownership in Rust? Che i dati sullo heap hanno un unico proprietario. Lifetime (Rust) "E' un elemento che determina l'essere live di un dato sullo heap." La ownership di Rust ha tre regole:
  1. Ogni valore in Rust ha un proprietario.
  2. Il proprietario è unico.
  3. Quando il proprietario esce dallo scope, il valore viene eliminato.
Cosa è drop()? Che cosa fa? "E' una funzione che elimina le variabili non più in uso. Drop viene chiamata automaticamente alla fine di ogni blocco." Secondo il concetto di ownership in Rust il tipo di una variabile non solo rappresenta {{c1::informazioni}} sui

valori che la variabile può assumere, ma anche la {{c2::proprietà/ownership}} delle risorse associate alla variabile. Quando una {{c1::variabile}} viene trasmessa a funzioni o thread la proprietà viene {{c2::trasferita}} o spostata con essa. "In Rust esiste il concetto di ""prestito""" In pratica la notazione sintattica &s1 ci permette di creare un riferimento al valore s1 ma non lo possiede. Questo significa che il valore non verrà droppato quando la reference esce dallo scope. Il lifetime è un parametro di tipo che descrive lo scope in cui un dato è valido, che a sua volta definisce la liveness dei dati nello heap. Un programma concorrente contiene due o più {{c1::processi}} o threads, che lavorano assieme per eseguire una applicazione In programmazione concorrente ciascun (sotto)processo è un {{c1::programma sequenziale}} I (sotto)processi comunicano tra loro utilizzando {{c1::variabili condivise}} (shared memory) o scambiandosi {{c2::messaggi}} (message passing). "L'astrazione della programmazione concorrente è l'idea che i (sotto)processi sono in {{c1::esecuzione contemporanea}}." I sistemi multiprocessore: "" Mentre nella programmazione parallela si hanno N cpu e N task contemporaneamente, nella programmazione concorrente si hanno 1 CPU e N task contemporaneamente. La concorrenza e il parallelismo sono accumunati da un aspetto: Esecuzione non sequenziale del programma. "L'interleaving ha ruolo al livello del linguaggio macchina, e non del linguaggio ad alto livello" Sono le operazioni assembler ad alternarsi, non i comandi del linguaggio di alto livello. In concorrenza, i processi possono operare in parallelo solo su {{c1::locazioni di memoria}} distinte. La concorrenza (interleaving) è una astrazione che consente di fare molte analisi dei programmi che varranno anche in situazioni di {{c1::parallelismo}}. Possiamo usare la concorrenza come astrazione che
  1. descrive il comportamento di processi tramite interleaving,
  2. formalizzandoli come sistemi di transizioni non deterministici
  3. ottenuti dalla semantica del linguaggio di alto livello.
"L'astrazione della concorrenza cattura anche aspetti del {{c1::parallelismo}}" "L'astrazione della concorrenza cattura anche aspetti di interleaving {{c1::al livello macchina}}." Shared Memory Nel message passing i processi accedono ad aree {{c1::diverse}} della memoria, ma possono {{c2::inviarsi messaggi}} e sincronizzarsi usando servizi di {{c3::inter process communication}} (IPC) messi a disposizione dal {{c4::Sistema Operativo}}. Meccanismi di sincronizzazione, per esempio sono Nella memoria di un programma, qual è la Static Area? "Un'area di memoria di dimensione fissa, con contenuti determinati e allocati a compilazione." Quanto è grande il run-time stack? Qual è il compito principale del run-time stack? "
  1. E' di dimensione variabile, perchè contiene i records di attivazione.
  2. Si occupa della gestione dei sottoprogrammi.
" Quanto è grande lo heap? Qual è il suo compito principale? Solitamente sono allocati staticamente Quando si chiama un sottoprogramma a run-time, in che modo vengono registrate le sue informazioni? Per ogni istanza di un sottoprogramma a run-time abbiamo un record di attivazione contenente le informazioni relative a tale istanza. Queste informazioni si trovano sullo stack. Nello stack, ogni blocco interno al programma ha un record di attivazione. Quando si possono allocare posizioni di memoria nello heap? I blocchi di memoria possono essere allocati e deallocati in momenti arbitrari. Lo heap è necessario quando il programma permette Lo heap è una regione di memoria i cui blocchi di memoria possono essere {{c1::allocati}} e deallocati in momenti {{c2::arbitrari}} Quali sono le due problematiche principali della gestione dello heap? "All'inizio del programma lo heap contiene un {{c1::solo blocco}} della dimensione dello heap." Ad ogni {{c1::richiesta di allocazione}} si cerca nello heap un blocco di dimensione opportuna. La strategia di allocazione first fit cerca: Il primo blocco grande abbastanza. La strategia di allocazione best fit cerca: il blocco di dimensione più piccola, grande abbastanza. "Se nell'allocazione nello heap il blocco scelto è molto più grande di quello che serve" viene diviso in due e la parte inutilizzata è aggiunta alla LL. Quando un blocco è deallocato viene restituito alla LL. La gestione della memoria esplicita viola il principio di {{c1::astrazione}} dei linguaggi di programmazione Obbliga ad occuparsi di cosa accade ad un livello più basso. Si può chiamare il garbage collector una astrazione linguistica? No, non fa parte del linguaggio di programmazione, ma è una parte della macchina virtuale. Le tecniche GC di tracing identificano...
Le celle che sono diventate garbage.
La tecnica di GC più recente è il {{c1::generational GC}} Il Java Generics è un meccanismo di {{c1::astrazione linguistica}} che consente la definizione di classi e metodi {{c2::parametrici}} rispetto al tipo che utilizzano I metodi di una classe generica possono usare le {{c1::variabili di tipo}} dichiarate dalla classe. I metodi generici possono anche dichiarare dei propri {{c1::tipi generici}}. Una collezione in Java può essere... modificabile o non modificabile, con ripetizioni o senza, con struttura lineare o ad albero, elementi ordinati o non ordinati. A cosa servono i tipi al livello di progetto? "Organizzano l'informazione" A cosa servono i tipi al livello di programma? Identificano e prevengono errori. "In che modo i tipi organizzano l'informazione?" "" In che modo i tipi prevengono errori? "" In che modo i tipi permettono ottimizzazioni? I dati sono denotabili se Possono essere associati ad un nome. I dati sono esprimibili se possono essere il risultato della valutazione di una espressione. I dati sono memorizzabili se possono essere memorizzati (e modificati) in una variabile. Un tipo di dato è una  collezione di valori. I valori di un tipo di dato sono rappresentati da opportune strutture dati e da un insieme di operazioni per manipolarli. I descrittori di dato sono etichette ad ogni variabile che descrive il suo tipo. Sono necessari se e solo se "L'informazione sui tipi è ""a tempo di esecuzione""." Un array è una funzione da interi ad un altro tipo di dato. La mancanza di correttezza dei dati permette agli attaccanti di sfruttare bug per alterare maliziosamente il comportamento del programma. Unificazione "l'unificazione è un processo algoritmico di risoluzione di equazoni tra espressioni simboliche (espressioni che contengono variabili)." La soluzione di un problema di unificazione è una sostituzione che assegna un valore simbolico ad ogni variabile. I valori esprimibili sono Il risultato della valutazione di espressioni Un ambiente è una associazione ide evT env "Nell'ambiente di un interprete i valori devono avere anche l'informazione sul tipo per consentire" il type checking dinamico. Den of ide rappresenta Una entità denotabile, ovvero una variabile. La funzione Den(i) ritorna il valore associato alla variabile i. "Con let possiamo cambiare l'ambiente in punti arbitrari. Il let indica" "l'inizio di un nuovo blocco." Nel mark-sweep ogni cella prevede spazio per un {{c1::bit di marcatura}} Nel mark-sweep, garbage può essere {{c1::generato}} dal programma Non esistono interventi preventivi. "Nel mark-sweep, l'attivazione del GC causa la {{c1::sospensione}} del programma in esecuzione." Nella operazione di marking si parte dal {{c1::root set}} e si marcano le celle {{c2::live}}. Nella operazione di sweep, tutte le celle non marcate come live sono {{c1::garbage}} e sono restituite alla {{c2::lista libera}}. Avviene il reset del {{c3::bit di marcatura}} sulle celle live. I pro del metodo di mark-sweep sono che I contro del mark-sweep sono che "" "L'algoritmo di Cheney è un algoritmo di garbage collection che opera" "suddividendo la memoria heap in due parti, il ""from space"" e il ""to-space""." "Nell'algoritmo di Cheney (copying collection), quante parti dello heap sono attive?" Solo una parte dello heap è attiva, e permette di allocare nuove celle. "Nell'algoritmo di Cheney, quando viene attivato il garbage collector, le celle live" vengono copiate nella seconda porzione dello heap. "Alla fine dell'operazione di copia, Il GC copying collection scambia i {{c1::ruoli}} tra le due parti dello heap." La parte non attiva diventa attiva e viceversa. Il copying collector è buono perchè "E' efficace nella allocazione di porzioni di spazio di dimensioni differenti. Evita la frammentazione." Il copying collector ha una caratteristica negativa: la duplicazione dello heap. Funziona bene se si ha tanta memoria. Il generational garbage collector si basa sul principio che La maggior parte delle celle che muoiono sono giovani. Il generational GC divide lo heap in un insieme di generazioni I tre passi fondamentali del generational GC sono Quali sono quattro degli obbiettivi fondamentali di Rust? Rust si concentra su type safety, memory safety, concorrenza e performance. Rust è un linguaggio ad alto livello? Rust si integra con linguaggi ad alto livello, ma controlla dati a basso livello. Questo lo rende più potente. Come fare a capire se un oggetto è in utilizzo? "Se ci sono dei puntatori verso l'oggetto, allora sta essendo utilizzato." Cosa è il reference counter di un oggetto? "E' un numero che è allocato allo stesso tempo di ogni oggetto. E' il numero che conta quanti puntatori attivi esistono verso l'oggetto." Quando il reference count di un oggetto è 0? "Quando non ci sono puntatori all'oggetto." Cosa fa il garbage collector quando il reference counter di un oggetto è zero? Libera il suo spazio sullo heap e lo restituisce alla lista libera. Quali sono i punti negativi del reference counting? Questa tecnica non riesce a deallocare strutture circolari, perchè i loro contatori non sono mai uguali a zero. Il metodo reference counting è efficiente? No, perché non dipende dalla dimensione dello heap ma da quante dichiarazioni fa il programma. "Cosa è il root_set nell'algoritmo mark-and-sweep?" "E' l'insieme di puntatori che sono attivi e presenti nello stack." "Come funziona la fase mark dell'algoritmo mark-and-sweep?" Per capire quali riferimenti sono inutilizzati, gli oggetti nello heap sono segnati come inattivi. Poi, partendo dal root-set, le strutture dati vengono attraversate ricorsivamente. Gli oggetti trovati vengono segnati come attivi. Come funziona la fase di sweep del mark-and-sweep? Gli oggetti segnati come attivi sono lasciati, mentre gli altri sono restituiti alla lista libera. "Quale metodi GC lavorano durante l'esecuzione del programma?" Ad esempio, reference counting. Quali metodi GC vengono utilizzati solo quando sta per finire la memoria sullo heap? Il mark-and-sweep. Qual è il problema di frammentazione con gli algoritmi di GC più comuni? Quando si libera la memoria, si libera in posti a caso, quindi le postazioni di memoria libere possono essere troppo piccole. Cosa è un sistema di transizioni non deterministici? Mostra transizioni alternative, e considera tutte le possibili transizioni. La concorrenza è una astrazione perché quando consideriamo i sistemi di transizioni... partiamo dalla semantica del linguaggio di alto livello. Cosa è la strategia di busy waiting? "Un thread continua a controllare se l'altro ha scritto il messaggio in memoria, così da sincronizzarsi." Il busy waiting è efficiente? Perchè? No, perchè il thread che aspetta consuma tempo solo per testare ripetutamente un valore. Cosa è il runtime di un linguaggio? "E' un pezzo di codice che implementa porzioni del modello di esecuzione di un linguaggio di programmazione." Il runtime di un linguaggio di programmazione può mettere a disposizione servizi di {{c1::segnalazione}} tra thread. Ad esempio sleep() wakeup(). Cosa succede quando un processo chiama receive()? Si mette in attesa di ricevere messaggi. Cosa succede quando un processo chiama send(x)? Il processo producer sblocca il processo consumer e gli passa il valore di x. Chi può usufruire dei meccanismi di sincronizzazione a livello di runtime del linguaggio? Solo i thread, i processi usano il sistema operativo. "Nel garbage collector di OCaml esamina regolarmente lo heap a partire da un {{c1::root set}} di valori ai quali l'applicazione ha sempre accesso (ad esempio i valori che si trovano nello stack)." Il GC di OCaml mantiene un {{c1::grafo diretto}} in cui i blocchi dello heap sono nodi, ed esiste un vertice da b1 a b2 se un campo di b1 è un puntatore a b2. OCaml usa un GC generazionale. Il suo heap è diviso in due regioni: OCaml usa un garbage collector piccolo e veloce nel minor heap. Cosa utilizza per il major heap? Il metodo mark-and-sweep. In cosa consiste la fase sweep del mark-and-sweep in OCaml? "Scannerizza pezzi dell'heap e identifica i blocchi morti che non erano ancora stati marcati." In cosa consiste la fase compact nel mark-and-sweep di OCaml? I blocchi vivi sono relocati in un heap appena allocato per eliminare i buchi nella lista libera. Qual è la differenza tra heap e stack? Lo stack contiene variabili che sono state inizializzate prima del runtime, mentre lo heap quelle che sono state inizializzate a runtime. Le variabili globali sono allocate... (staticamente/dinamicamente) staticamente Le variabili locali dei sottoprogrammi sono allocate... (staticamente/dinamicamente) Staticamente. Gli oggetti che sono allocati con new sono allocati... (staticamente/dinamicamente) Dinamicamente "Se un'entità ha un indirizzo assoluto che è mantenuto per tutta l'esecuzione del programma, allora è allocata..." Staticamente. Le tabelle usate dal supporto a run-time sono allocate... staticamente. Ogni blocco ha il suo record di attivazione che è allocato {{c1::dinamicamente}} nello {{c2::stack}}. "L'allocazione esplicita di memoria a run-time avviene nello {{c1::heap}}" Quali sono le tecniche GC di tracing? Sono la mark-sweep e la copy collection. Quale tecnica di GC coesiste con la gestione della memoria esplicita da programma? Il reference counting. Quali tecniche di GC riescono a gestire le strutture circolari? Le tecniche di tracing "Il root set è l'insieme dei dati ""attivi"", ovvero..." variabili statiche e variabili allocate sul run-time stack. Reachable active data Tutti i dati raggiungibili dal root set seguendo i puntatori. "L'opposto di una cella live / attiva è" una cella garbage / inattiva "L'algoritmo copying collection, anche detto {{c1::Algoritmo di Cheney}} è un algoritmo di GC che opera suddividendo la memoria heap in {{c2::due parti}}." "L'algoritmo copying-collection è un algoritmo della categoria di {{c1::tracing}}." Quale area è più piccola nel generational GC? "L'area Old." Descrivi brevemente il metodo reference counting. Descrivi brevemente il metodo mark and sweep. "Descrivi brevemente l'algoritmo di Cheney, o copying collection." "" Descrivere brevemente il Generational GC. Cosa è un meccanismo di locking? "E' qualcosa che blocca l'esecuzione di un processo durante l'esecuzione di un'altro." Cosa è la mutua esclusione? "E' la proprietà di evitare che due processi modifichino contemporaneamente la stessa locazione di memoria." mutex "E' una entità astratta (token, testimone) che serve a garantire la mutua esclusione" A cosa si associa un mutex? Si associa ad ogni area di memoria da condividere. La primitiva lock serve a bloccare un thread. In quale momento un thread deve fare lock sul mutex associato? Prima di iniziare ad utilizzare una locazione condivisa. In quale momento il thread fa unlock sul mutex associato? Quando non sta più utilizzando la locazione di memoria condivisa. Cosa vuol dire coarse grained locking? Un mutex è associato a più locazioni (ad esempio un solo mutex per tutte le locazioni). Cosa vuol dire fine-grained locking? "C'è un mutex per poche locazioni, ad esempio un mutex diverso per ogni locazione." Se la strategia coarse-grained fa corrispondere un solo mutex a molte locazioni, qual è un suo pro? richiede meno lavoro al singolo thread, perchè si effettuano meno operazioni di lock. Se la strategia coarse-grained fa corrispondere un solo mutex a molte locazioni, qual è un suo contro? Riduce la concorrenza, perchè blocca anche threads che accedono a locazioni di memoria diverse.
La strategia fine-grained predispone ad un tipo particolare di errore:
Il deadlock Deadlock "Situazione in cui il programma si blocca (definitivamente) a causa dell'uso improprio dei lock." Il deadlock viene causato da "situazioni di attesa circolare (ogni thread aspetta l'altro)." Cosa significa attesa circolare? "E' una situazione in cui i threads si bloccano a vicenda, quindi bloccando l'esecuzione." Qual è uno dei motivi per cui le operazioni in esecuzione si bloccano e devono essere uccise? Il deadlock. Cosa è la deadlock prevention al livello del compilatore? "Si stabiliscono delle regole controllabili staticamente sull'uso dei lock che garantiscano che non avvengono deadlocks." Cosa è la deadlock avoidance al livello runtime? "E' un metodo per cui il supporto a runtime del linguaggio si accorge quando il programma sta per andare in deadlock, e cambia l'esecuzione del thread." Cosa è il deadlock recovery, al livello runtime? Il programma viene lasciato libero di andare in deadlock, ma se accade il runtime se ne accorge e ripristina uno stato senza deadlock. Il two phase locking è una disciplina che assume che esista un ordinamento dei mutex. Quali sono le sue regole? Se un thread vuole acquisire e rilasciare un certo numero di mutex, deve fare i rispettivi lock in ordine crescente, e gli unlock in ordine decrescente. "E' possibile acquisire n mutex, rilasciarne una parte e aquisirne altri, secondo la 2PL?" No, perchè le sequenze di lock e unlock devono essere eseguite completamente. Secondo il modello originale di multithreading di Java, quanti stack ci sono per thread? Ogni thread ha il proprio stack. Secondo il modello originale di multithreading di Java, quanti heap esistono per thread? Esiste un solo heap condiviso tra tutti i thread. Nelle versioni recenti di Java, chi gestisce lo scheduling dei thread? la JVM sfrutta i servizi di threading del Sistema Operativo. "Quali sono le conseguenze dell'utilizzo dei servizi di threading del Sistema Operativo, da parte della JVM?" "L'esecuzione parallela è consentita se sono disponibili più processori/core." Cosa è la Concurrency API in Java? "E' una libreria standard dedicata alla concorrenza. Può usare un'ampia gamma di modelli di concorrenza e parallelismo." Qual è il tipo di un thread in Java? "E' un oggetto di tipo Thread." Un thread in Java deve avere almeno due metodi: Il metodo run() e il metodo start(). In quali casi non è necessario fare il lock su un oggetto? Quando si utilizzano solo operazioni atomiche. Quanti mutex per oggetto ci sono in Java? Ogni oggetto dispone di un lock. A cosa serve il modificatore syncronized in Java? Permette di acquisire il lock su un oggetto, quindi di eseguire un metodo in mutua esclusione. "L'esecuzione di un metodo ""sincronizzato"" permette l'esecuzione di chiamate dello stesso metodo?" No, è bloccante sia sullo stesso metodo che su altri metodi sincronizzati sullo stesso oggetto. Il modificatore syncronized fa acquisire il lock per tutta la durata del metodo. Applica una strategia coarse-grained o fine-grained? coarse grained. Come si può sincronizzare un singolo blocco in Java? Si usa la parola chiave syncronized prima di un blocco di testo. Come scegliere quali collezioni usare in un programma Java? Se il programma è concorrente, bisogna scegliere le collezioni sincronizzate, altrimenti quelle non sincronizzate. "A cosa serve l'accesso sincronizzato?" A coordinare i thread in modo tale che collaborino. "Cos'è l'ambiente locale?" Un modello di cooperazione che non prevede il concetto di memoria condivisa Nel modello di ambiente globale, ogni thread ha il {{c1::proprio stato}} per-thread (es. stack e registri del thread), ed entrambi condividono lo {{c2::shared state}} (es.: variabili condivise nello heap). I thread cooperanti leggono e scrivono nello {{c1::Shared State}}. "Nel modello dell'ambiente locale, il conceto di memoria condivisa {{c1::non esiste}}." Nel modello di ambiente locale i thread si {{c1::chiedono a vicenda}} i dati, e si passano {{c2::una copia.}} Nel modello di ambiente locale bisogna stabilire un {{c1::canale di comunicazione}} dove i thread si passano informazioni. Come si può modularizzare un programma sotto il profilo linguistico? "Con l'astrazione procedurale, ovvero scomporre il problema in sottoproblemi da risolvere con specifiche procedure/funzioni." Come si può modularizzare un programma sotto il profilo dei tipi di dato? Con i tipi di dato astratti. Proprietà di incapsulamento. Idealmente, lo stato di un oggetto non dovrebbe essere accessibile dagli altri oggetti. "Cosa è l'identità di un oggetto?" "E' il nome che individua l'oggetto." Cosa è il ciclo di vita di un oggetto? Se è garbage o è live. "Cos'è la locazione di un oggetto?" "E' la locazione di memoria che occupa." Cosa è lo stato di un oggetto? Il valore dei suoi parametri. Cosa sono le funzionalità di un oggetto? Sono le funzioni che mette a disposizione degli altri oggetti. "Cosa è l'approccio compilazione+interpretazione di Java?" La compilazione genera un bytecode intermedio, che può essere interpretato in ogni architettura che possegga la JVM. Quali controlli sono consentiti in Java e da cosa? "Statici dal compilatore, dinamici dall'interprete." Il nucleo imperativo di Java è simile ad un altro linguaggio "E' simile al C." In Java, perchè le variabili devono essere dichiarate e inizializzate, prima di essere usate? Perchè Java effettua un controllo statico. In Java, posso ridichiarare in un blocco una variabile già dichiarata in un blocco più esterno (vero/falso) falso. No shadowing. Come si definisce una variabile globale in Java? Non esistono variabili globali. Come si dichiara un puntatore in Java? Non esistono i puntatori in Java. "C'è il rischio di ""uscire da un array"" in Java?" "No, se l'indice è maggiore della lunghezza Java solleva un'eccezione di ArrayIndexOutOfBounds." Di cosa consiste una classe? Di variabili e metodi, tra cui costruttori. Come decidere come separare le classi? "Ogni tipologia di ""entità"" che ha un comportamento autonomo, o un insieme di comportamenti correlati, dovrebbe essere una classe." Il compilatore fa i suoi controlli statici sul tipo {{c1::apparente}} perchè il tipo {{c1::effettivo}} potrebbe non essere noto al tempo di compilazione. Se il tipo effettivo non è chiaro, si può testare il tipo effettivo con un {{c1::controllo a runtime}} e forzare il compilatore con un {{c2::type cast}}. Cosa è la cast o coercion tra due classi? "E' l'operazione di convertire una classe in un'altra." Il cast tra due classi si può fare solo se tra le due esiste una relazione di sottotipo, cioè "se una esplicitamente implementa o estende l'altra." La conversione da sottotipo a supertipo (upcast) è {{c1::implicita}}: questo significa che Non è richiesto il cast. La conversione da supertipo a sottotipo (downcast) è {{c1::esplicita}}, ovvero Richiede un cast esplicito. "Cosa codificano i membri (variabili e metodi) d'istanza? Cosa implementano?" codificano lo stato di ogni singolo oggetto e implementano le operazioni che lavorano su tale stato. Cosa codificano i membri (variabili e metodi) statici codificano informazioni e operazioni al livello di classe, ossia variabili condivise, e metodi che non operano sul singolo stato. Quante variabili di istanza sono presenti in memoria? In tante copie quanti sono gli oggetti Quante volte sono ripetute le variabili statiche  in memoria? Una variabile statica è presente una ed una sola volta in memoria. A quali variabili può accedere un metodo di istanza? Può accedere sia alle variabili di istanza che a quelle statiche. A quali variabili può accedere un metodo statico? Può accedere solo alle variabili statiche. La Java Virtual Machine, nella sua memoria, ha tre aree: "" "Cosa è l'ambiente delle classi nella JVM?" "E' un'area di memoria che contiene il codice dei metodi e le variabili statiche di classe." Come si può accedere agli oggetti creati con new? Attraverso dei riferimenti memorizzati nelle variabili locali. Una classe che non estende altre classi, implicitamente estende la classe di default {{c1::Object}}. "Il metodo {{c1::toString()}} restituisce una {{c2::rappresentazione testuale}} dell'oggetto." "Il metodo {{c1::equals(obj)}} confronta l'oggetto corrente con l'oggetto {{c2::obj}}." "Il metodo {{c1::clone()}} crea {{c2::una copia}} dell'oggetto." "Quando evochiamo un metodo, il metodo deve essere presente {{c1::nella classe}} che descrive il {{c2::tipo apparente}} dell'oggetto, ossia quello della dichiarazione." Perchè il nome dei parametri formali e il tipo del risultato del metodo non fanno parte della firma? Perchè non possono essere dedotti dalla chiamata. Perchè due metodi con la stessa firma non possono stare nella stessa classe? La firma contiene informazioni che possono essere dedotte dalla chiamata, e sono utilizzate per capire quale metodo chiamare. Cosa succede se il metodo chiamato non viene trovato? Avviene un errore in fase di compilazione. Se la JVM vuole delle informazioni sul tipo effettivo di un dato, dove guarda? "Nel descrittore del dato in memoria, che era stato inizializzato al momento della creazione dell'oggetto." Cosa sono le tabelle dei metodi, o dispatch vector? Sono tabelle di puntatori al codice dei metodi. Cosa è lo sharing strutturale? "E' il concetto per cui la tabella di una sottoclasse riprende la struttura della tabella della superclasse, aggiungendo righe per i nuovi metodi." "L'operazione di dispatching dei metodi si può risolvere staticamente perchè {{c1::il compilatore}} determina {{c2::l'offset}} del metodo nella tabella, ovvero la sua posizione." "Durante il dispatching dei metodi, l'offset è determinato sul {{c1::tipo apparente}} dell'oggetto." "A tempo di esecuzione, la JVM accede alla tabella della classe che è il {{c1::tipo effettivo}} dell'oggetto. Ci accede usando {{c2::l'offset}} determinato a tempo di compilazione." Se durante il dispatching, il tipo effettivo fosse diverso da quello apparente, corrisponderà comunque ad una sua {{c1::sottoclasse}}, e grazie allo {{c2::sharing strutturale}} la JVM accederà comunque al metodo giusto. Il dynamic dispatch funziona nel modo per cui se la sottoclasse ha fatto {{c1::overriding}} del metodo, il puntatore in tabella riferirà alla {{c2::nuova versione}} del metodo. "Come fa un metodo non statico ad accedere alle variabili di istanza dell'oggetto?" "Il compilatore aggiunge this come parametro implicito, quindi a tempo di esecuzione sarà passato il riferimento all'oggetto su cui il metodo è chiamato." Un tipo di dato è una collezione di {{c1::valori}} "Un tipo di dato è rappresentato da un'opportuna {{c1::struttura dati}} e un insieme di {{c2::operazioni}} per manipolarli." I descrittori di dato non servono se "L'informazione sui tipi è conosciuta totalmente a tempo di compilazione." Su Ocaml il type checking è statico, quindi viene svolto dal {{c1::compilatore}}. Quali sono i tipi di base di un linguaggio? Bool, char, int e real. Quali sono alcuni esempi di tipi composti? Record, Record varianti, array, insieme, puntatore. In C, i record si chiamano... struct. Funzione polimorfa Una funzione è polimorfa se ha la caratteristica di essere applicabile ad argomenti di tipo diverso. Cosa sono le precondizioni di un metodo? "Sono condizioni sui parametri e sul valore delle variabili che devono essere soddisfatte all'inizio dell'esecuzione del metodo." Cosa sono le postcondizioni di un metodo? "Sono le condizioni sul risultato e sul valore delle variabili che devono essere soddisfatte al termine dell'esecuzione." La sottoclasse deve soddisfare non solo le proprie specifiche, ma anche quelle della sua superclasse. "Cosa è l'eccezione ParseError?" "E' l'eccezione che solleva lo scanner se trova un simbolo non previsto." Cosa chiede la regola della segnatura? Come si fa a verificare la regola della segnatura in Java? Il compilatore di Java controlla la presenza di tutti i metodi del supertipo nel sottotipo. Secondo la regola della segnatura, il metodo del sottotipo può sollevare più eccezioni del metodo del supertipo? No, può sollevare meno eccezioni. Il return type di un metodo di un sottotipo deve essere uguale al quello del supertipo? No, può essere più specifico. Esiste un algoritmo per verificare se il principio di sostituzione di liskov vale tra due classi? No, è un problema indecidibile. Però può verificare le regole indotte dal LSP. Un sottotipo può rafforzare le precondizioni dei metodi che sono riscritti? No, ma le può indebolire. Un sottotipo può rafforzare le postcondizioni del metodo che riscrive? Sì, non diminuisce la compatibilità. Regola dei metodi. Le chiamate dei metodi del sottotipo devono comportarsi come le chiamate dei corrispondenti metodi del super-tipo. I Java Generics sono un {{c1::meccanismo di astrazione}} linguistica che consente la definizione di {{c2::classi}} e metodi {{c3::parametrici}} rispetto al {{c4::tipo}} che utilizzano. "Quale entità verifica l'utilizzo corretto dei generici?" Il compilatore. Il polimorfismo esiste al livello di interprete? No, il compilatore elimina i parametri di tipo, e il risultato è un normale class file senza polimorfismo parametrico. Cosa vuol dire polimorfismo parametrico? Significa che i parametri formali di una classe o un metodo possono essere di più tipi. A cosa servono le collezioni in Java? Spesso in un programma dobbiamo rappresentare e manipolare gruppi di valori oppure oggetti di uno stesso tipo. Cosa è una collezione? Chiamiamo collezione un gruppo di oggetti omogenei, cioè dello stesso tipo. Cosa è un array in Java? "E' una collezione modificabile, lineare, di dimensione non modificabile." A cosa serve avere una varietà ampia di strutture dati con controlli statici? A verificare la correttezza delle operazioni. Cosa è il Java Collections Framework? "E' architettura che definisce una gerarchia di interfacce e classi, che realizzano una ricca varietà di collezioni." La Java Collection Framework è composta da tre elementi: Quali sono i vantaggi del JCF? In {{c1::Java}} è possibile definire una classe come estensione di {{c2::una singola}} altra classe esistente usando la parola chiave {{c3::extends}}. "Cosa è l'ereditarietà multipla?" "E' la possibilità di ereditare da più classi." Cosa è il diamond problem? Ereditare da due superclassi che possono a loro volta avere una superclasse in comune. "Come fa C++ a risolvere l'ereditarietà multipla?" Dà la possibilità di disambiguare. "Come fa Python a gestire l'ereditarietà multipla?" Linearizza le gerarchie di classi. Cosa è mixin? "E' una composizione di classi." Quale struttura dati usa Java per gestire interfacce multiple? Una tabella delle interfacce o itable. Quante itable ci sono per classe? Ogni classe ha una itable. Cosa si trova dentro la itable di una classe? I dispatch vectors di tutte le interfacce implementate. In Java, nel caso di interfacce multiple, dove si tengono i link al codice dei metodi implementati? Nella itable. "Se una classe implementa più interfacce, cosa succede se il tipo apparente dell'oggetto è quello della classe?" La chiamata si svolge normalmente. "Se una classe implementa più interfacce, cosa succede se il tipo apparente dell'oggetto è quello dell'interfaccia?" Il compilatore compila il codice in modo che il metodo sia raggiunto tramite la itable. In python, cosa succede se una gerarchia di classi non è linearizzabile? Succede un errore a runtime. Cosa vuol dire che un metodo è di istanza? "Un metodo di istanza è specifico ad un oggetto, e agisce sullo stato dell'oggetto." Da una classe possiamo ottenere molteplici {{c1::istanze}}, che sono {{c2::oggetti}}. In Java, per ciascuna {{c1::istanza}} si hanno variabili di nomi {{c2::identici}} dai valori {{c3::distinti}}, cioè che puntano a {{c4::locazioni di memoria}} differenti. Se vogliamo che una variabile sia la medesima per tutte le istanze di una {{c1::classe}} la dobbiamo definire come {{c2::statica}}. Cosa è il tipo ide? "E' una stringa che indica i nomi delle variabili." Cosa è il tipo Tname? "E' il tipo che contiene i nomi dei tipi." Quali sono i tipi di MiniCaml? Intero, Booleano, Stringa, Chiusura, Chiusura Ricorsiva, Unbound. Cosa è il tipo exp in MiniCaml? "E' il tipo delle espressioni." Se dovessi scrivere un interprete, come definiresti il tipo ambiente? "type 't env -> ide -> 't ;;" Cosa è il tipo evT in MiniCaml? "E' il tipo dei tipi esprimibili, cioè tipi che possono essere risultato di una funzione eval." Scrivi il prototipo della funzione bind. Bind (s: evT env) (x: ide) (v: evT) Cosa ritorna una funzione bind? Un nuovo ambiente. Esprimi a parole il contenuto della funzione bind di MiniCaml "La funzione bind ritorna un nuovo ambiente, ossia una funzione ide -> 't. Dati i parametri s, un ambiente, x, un nome, e v, un valore,
bind restituisce un nuovo ambiente che, preso un nome i, restituisce v, se i = x, altrimenti restituisce il valore di i in s.

Riassunto: bind(s, x, v) restituisce amb t.c. amb(i) = v se e solo se x = i, altrimenti restituisce il valore di i in esse." Come si fa una nuova funzione primitiva in MiniCaml? "Si crea una funzione che fa il typechecking, e restituisce un oggetto in ""formato minicaml"", ovvero qualcosa del tipo Nometipo(valore)." Cosa è Den(i)? "E' una espressione in cui i è il nome di una variabile." Come si valuta Den(i)?
(Qual è il risultato di eval Den(i) amb ?) "Si restituisce il valore della variabile i nell'ambiente corrente." Come si valuta Prod(e1, e2)? Si restituisce il risultato della funzione primitiva di prodotto. Come si valuta IfThenElse(e1, e2, e3)? "Chiamiamo g il valore di e1.
Se g è booleano, ed è vero, allora si valuta e2.
Se g è booleano, ed è falso, si valuta e3.
Altrimenti c'è stato un errore." "Cosa fa un'espressione Let in MiniCaml?" "Aggiunge una nuova associazione all'ambiente." Traduci Let(i, e, ebody) in un linguaggio di programmazione normale. Let i = e in ebody. "Come si valuta un'espressione del tipo Let (varname, value, letbody) in MiniCaml?" Prima si crea un nuovo ambiente in cui il nome corrisponde al valore dato, poi si valuta il corpo in questo nuovo ambiente. Qual è il valore di una funzione in MiniCaml? La sua chiusura, ovvero la combinazione tra la funzione e il suo ambiente corrente. Cosa è Letrec? "E' una espressione di MiniCaml che serve a definire una funzione ricorsiva." Quali sono gli elementi di una Letrec? Sono il nome di una funzione, il nome del suo parametro formale, il suo corpo e il corpo del let. Come si calcola il valore di una Letrec? (con parametri f, arg, fbody, letbody) "Prima si crea un ambiente in cui il nome f corrisponde alla chiusura di f con il suo corpo e il suo argomento nell'ambiente corrente. A questo punto si può valutare il corpo del rec nell'ambiente ottenuto." Quali argomenti prende una apply? Una funzione e un argomento. "Come funziona l'apply di una funzione non ricorsiva, con parametri f e arg?" "Si valuta la funzione, ottenendo una chiusura con valori(arg, fbody, fDeclEnv), ovvero parametro formale, corpo di una funzione, ambiente di dichiarazione. Si valuta l'argomento nell'ambiente corrente, si crea un nuovo ambiente con la nuova associazione, e si valuta la funzione nell'ambiente ottenuto." "Come fa l'Apply di una funzione ricorsiva?" "Si calcola la sua chiusura, che avrà come argomenti il nome della funzione, un parametro formale, il corpo della funzione, e l'ambiente di dichiarazione.
Si valuta il parametro formale, si calcola un nuovo ambiente con la corrispondenza tra nome di funzione e chiusura di funzione, chiamato ambiente ricorsivo.
Si aggiunge all'ambiente ricorsivo la corrispondenza tra parametro formale e parametro attuale, e poi si valuta il corpo della funzione nell'ambiente ottenuto." "Se volessi introdurre un nuovo tipo di funzione, quante parti dell'interprete dovresti cambiare?" Il tipo delle espressioni, il tipo dei valori esprimibili, e la funzione eval. Cosa dovrei aggiungere al tipo exp, se aggiungessi un nuovo tipo di funzione? La dichiarazione del nuovo tipo di funzione. Che cambiamenti dovrei introdurre in evT, se volessi aggiungere un nuovo tipo di funzione? Una nuova chiusura, e probabilmente un nuovo valore di ritorno. Che cambiamenti dovrei introdurre in eval, se volessi aggiungere un nuovo valore di funzione? "Dovrei aggiungere la dichiarazione di funzione, e modificare l'apply." "
Traduci in Italiano." "Il valore di BothFun, nell'ambiente gamma, è una chiusura che contiene le caratteristiche di BothFun e anche l'ambiente corrente." "
Traduci a parole." "Il valore di una Applicazione su due espressioni e1 e e2 è uguale alla coppia v1, v2
Se
" "Riassumi le regole operazionali di sintassi astratta di una espressione ""if then else"".
(esempio: Ifthenelse(cond, e1, e2))" "Nell'ambiente gamma, Ifthenelse(cond, e1, e2) vale:
Un valore v1
se in gamma la condizione è vera, e1 ha valore v1.
Un valore v2,
se in gamma la condizione è falsa, e2 ha valore v2." Descrivi la semantica operazionale del blocco.
(Let(x, e1, e2)) "Con Let(x, e1, e2), siamo dicendo ""fai corrispondere il nome x al valore di e1 nel blocco e2.
In gamma, il let ha valore v2 se:
in gamma, e1 ha valore v1,
in gamma a cui si aggiunge (e1 = v1), e2 ha valore v2." "Come si esprime l'astrazione funzionale in MiniCaml?" "Con Fun(""x"", fbody), dove x è un parametro formale, e fbody è il corpo della funzione." Stiamo introducendo le astrazioni funzionali in MiniCaml per la prima volta. Cosa dobbiamo aggiungere ai valori esprimibili? "La chiusura di una funzione nell'ambiente corrente." Da cosa è composta la chiusura di una funzione unaria non ricorsiva? "Il nome del parametro formale (ide), il codice della funzione dichiarata(exp), l'ambiente al momento della dichiarazione(evT env)." "Descrivi le regole operazionali dell'astrazione di funzione." In gamma, una funzione con parametro x, e corpo e, vale una chiusura (x, e, gamma). "Descrivi le regole operazionali dell'applicazione di funzione.
(Apply(Den(""f""), arg))" "(Apply(Den(""f""), arg)) significa ""applica alla funzione di nome f l'argomento arg"".
L'applicazione in gamma ha valore v se
" Da cosa è composta la dichiarazione di una funzione ricorsiva Letrec? Da il nome della funzione, il parametro formale, il corpo della funzione e il corpo del let. Stiamo aggiungendo la dichiarazione di funzione ricorsiva a MiniCaml. Come dobbiamo cambiare il tipo evT? Dobbiamo aggiungere un nuovo valore esprimibile: RecClosure. Da cosa è composto un valore RecClosure? "Da il nome di una funzione, un parametro formale, il corpo di una funzione e l'ambiente di dichiarazione." Discutere le caratteristiche di structural e nominal subtyping nella programmazione ad oggetti. "Nello structural subtyping, la relazione di sottotipo dipende dalla struttura dei due oggetti: se l'oggetto B ha tutti i membri pubblici dell'oggetto A, allora è un suo sottotipo. Nel nominal subtyping è necessario dichiarare esplicitamente un oggetto come estensione di un altro." "Si consideri l'algoritmo di Garbage collection mark&sweep. Discutere la nozione di root_set da cui parte la visita del grafo." "Il root set è l'insieme delle variabili statiche, e delle variabili allocate sullo stack, che contengono riferimenti a dati allocati sullo heap. Partendo dal root set, e seguendo i puntatori, è possibile determinare quali dati sullo heap sono attivi, e quali garbage." Spiegare sinteticamente quali siano i vantaggi e gli svantaggi di una strategia di locking coarse grain e fine grain. Una strategia coarse grain utilizza poche mutex per molte locazioni di memoria. Permette ai thread di lavorare di meno, perché possono bloccare più locazioni in meno passaggi. Tuttavia riduce la concorrenza, perché si possono bloccare threads senza che ce ne sia bisogno. La strategia fine grain, in cui una mutex è associata a poche locazioni di memoria, è più specifica, ma rende più possibile che ci siano deadlocks, ovvero che il thread si blocchi permanentemente per una situazione di attesa circolare. Cosa è il principio di sostituzione di Liskov? "L'enunciato del principio di sostituzione di Liskov è che un oggetto di un sottotipo può sostituire un oggetto del supertipo in maniera trasparente (senza influire sul comportamento).
Il sottotipo deve
- Avere tutti i metodi del supertipo.
- I metodi del sottotipo devono comportarsi come quelli del supertipo.
- I metodi del sottotipo devono avere tutte le proprietà testabili del supertipo." Qual è la differenza tra scanner e parser? "Lo scanner è un analizzatore lessicale, quindi verifica che i termini del codice facciano parte del linguaggio di programmazione.
Il parser, o tokenizer, effettua una analisi sintattica, quindi verifica che che il codice rispetti la grammatica del linguaggio, e genera l'AST, ovvero l'albero di sintassi astratta." Cosa fa un typechecker? Il typechecker verifica la correttezza dei tipi. Quindi verifica se le variabili tipate assumono valori ammessi, e se le operazioni che vengono svolte su queste variabili sono consentite dal tipo. Perchè, e in che modo, i modificatori public e private consentono di realizzare meccanismi di incapsulamento? "Le variabili, che sono la rappresentazione interna dell'oggetto, sono private.
L'accesso esterno è consentito solo tramite metodi pubblici, che sono limitati e controllati.
Non si sa cosa fanno i metodi, ma solo quale risultato daranno.
Esistono anche metodi privati, che sono ausiliari." "Cosa vuol dire che un'interfaccia contiene una specifica astratta della classe?" Che indica quali membri pubblici la classe deve contenere. "Il tipo {{c1::apparente}} è quello usato dal compilatore per fare i suoi controlli, mentre il tipo {{c1::effettivo}} è il tipo che l'oggetto avrà a runtime." Classe astratta "E' una classe che contiene almeno un metodo presente ma non implementato." Descrivi come funziona il dynamic dispatch. "Quando il compilatore trova la chiamata di un metodo, determina la sua posizione in tabella (dispatch vector), sulla base del tipo apparente.
Siccome gli stessi metodi hanno le stesse posizioni in tabella, sia nella sottoclasse, che nella superclasse, il compilatore non ha bisogno di sapere il tipo effettivo.
Quando l'interprete chiamerà il metodo sul tipo effettivo, non ci saranno errori, anche in caso di overriding, perchè il puntatore riferirà alla nuova versione del metodo." Il principio di sostituzione di Liskov (LSP) implica tre regole da seguire: Cosa è un iteratore? "E' un'astrazione che permette di estrarre uno alla volta gli elementi di una collezione, senza esporne la rappresentazione." Per cosa sta mutex? Per primitiva di mutua esclusione.