Programmazione II - Corso B [PR2-B-14]

Introduzione al corso

Lucidi: PR2B-2014-01-Introduzione.pdf, fino a pag. 21.

Informazioni logistiche, Materiale didattico, Modalità di esame, Contenuti del corso: 1) Metodologie di programmazione orientata agli oggetti, 2) Paradigmi di programmazione e loro implementazione.

Programmazione, astrazioni e linguaggi

Lucidi: PR2B-2014-01-Introduzione.pdf, tutti
PR2B-2014-02-ParadigmiAstrazione.pdf

Letture: Capitolo 1 di [PDJ]

Paradigmi di programmazione, Principi dell'object-oriented programming, Information hiding, Programming by contract, Meccanismi di astrazione, Astrazione per parametrizzazione e per specifica.

Ripasso di OCaml: compilazione, tipi non modificabili, generici
Lezione tenuta dal Prof. Ferrari

Lucidi: PR2B-2014-03-TipiOCaml.pdf, fino a pag. 43 (Generic BST)

Letture: Capitoli 2-8 di [PLT]

Ripasso di OCaml; Programmare con i tipi di dato; Astrazione sui dati; Tipi di dato ricorsivi; Alberi binari; Compilazione e esecuzione di programmi in OCaml (ocamlc e ocamlrun); Alberi binari di ricerca; Funzioni generiche; Alberi e Alberi binari di ricerca generici.
Esempi di programmazione in OCaml (zip file) TreesOcaml.zip

Abstract Collections in OCaml; Verso i Tipi Mutabili

Lucidi: PR2B-2014-03-TipiOCaml.pdf, tutto
PR2B-2014-04-TipiMutabili.pdf, fino a pag 10

Letture: Capitoli 13-14 di [PLT]

Programmazione di Abstract Data Types con Moduli in OCaml; Insiemi generici; Introduzione a record mutabili e aliasing.

Tipi Mutabili; ASM per OCaml, Concetti basici di Java

Lucidi: PR2B-2014-04-TipiMutabili.pdf, tutto
PR2B-2014-04b-ASM-animazione.pdf
PR2B-2014-05-versoJava.pdf, fino a pag 22

Letture: Capitolo 15 di [PLT]

La Abstract Stack Machine per OCaml: workspace, stack e heap; Tipi primitivi e non in OCaml; Rappresentazione dell'aliasing. Da Value-Oriented Programming a Object Oriented Programming; Terminologia; Dichiatazione di Classi; Compilazione ed Esecuzione in Java; Creazione di oggetti; NULL; Costrutti di controllo.

Esercitazione su OCaml

Sviluppo di implementazioni del tipo di dati generico a' set

Esercitazione svolta su computer portatili degli studenti. Si consiglia di caricarli a sufficienza per mancanza di prese elettriche. Istallare OCaml.
File utili: MySet.ml, testMySet.ml

Lezione tenuta dal Prof. Ferrari
Overview di Java, per differenze rispetto a OCaml

Lucidi: PR2B-2014-05-versoJava.pdf, tutto
PR2B-2014-06-004-OCAMLvsJAVA.pdf, fino a pag 22

Letture: Capitolo 19-20-21 di [PLT]

Tipi primitivi in Java; Interfacce e relazione implements. Metodi e variabili statici (di classe); metodi e variabili di istanza; Realizzazione di tipi di dati ricorsi, di pattern matching e di funzioni higher-order à la OCaml in Java; Stringhe in Java.

Lezione tenuta dal Prof. Ferrari
La Abstract Stack Machine per Java

Lucidi:
PR2B-2014-07-005-JavaASM.pdf,

Letture: Capitolo 23-24 di [PLT]

La ASM per Java; Allocazione di oggetti e di array nello heap; Esempi di valutazione di frammenti Java e di aliasing; Ereditarietà e subtyping; Principio di sostituzione; Costruttori e super; THIS; Casting; Metodi della classe Object; Tipo statico e dinamico di una espressione.

Dynamic dispatch; Eccezioni in Java

Lucidi:
PR2B-2014-08-006-DynamicDispatch.pdf,
PR2B-2014-09-007-Eccezioni.pdf, fino a pag. 13.

Letture: Capitolo 25 di [PLT]

Dynamic dispatch (o dynamic binding); Tabella dei metodi; Rappresentazione nella ASM delle tabelle dei metodi e della gerarchia delle classi; Animazione di esecuzione di un frammento Java nella ASM. Situazioni anomale in programmazione; Eccezioni in Java; Lanciare e catturare un'eccezione; Struttura di messaggi di errore;

Eccezioni in Java

Lucidi:
PR2B-2014-09-007-Eccezioni.pdf.

Letture: Capitolo 28 di [PLT] (anche Capitolo 4 di [PDJ])

Gestione delle eccezioni in Java; Comportamento default; Comando throw; Gerarchia di eccezioni; Clausola throws; Costrutto try-catch-finally; Eccezioni checked e unchecked.

Lezione a corsi riuniti
Esercitazione su Java

File da scaricare:

• Istruzioni.txt
• Input.java
• Benvenuto.java
• expr1.ml
• Test1.java

Portare i propri computer, ben caricati. Istallare una distribuzione di Java (vedere i link di sopra). Per l'esercitazione si useranno i comandi javac (compilatore) e java (interprete), eseguiti da linea di comando. Per scrivere i programmi si può usare un qualunque editor di testo.

Animazione della Abstract Stack Machine: OCaml e Java
Specifica di Tipi di Dati Astratti in Java

Lucidi:
PR2B-2014-04b-ASM-animazione.pdf
PR2B-2014-10-007bis-EccezioniSimul.pdf
PR2B-2014-11-008-AstrazioniDatiSpecifica.pdf, slides 1-24 e 35-38.

Letture: Capitoli 3 e 5 (fino pag. 83) di [PDJ]

Evoluzione della Abstract Stack Machine per valutazione di espressioni OCaml e esecuzione metodi Java con lancio di eccezione; Astrazione procedurale in Java (per parametrizzazione e specifica); Abstract Data Types (ADT): definizione; ADT come astrazione di dati per specifica; Struttura della specifica; Esempi: IntSet, Vector; Esempio di ADT specificato con assiomi/equazioni: Stack of Items.

Specifica e Implementazione di Tipi di Dati Astratti in Java

Lucidi:
PR2B-2014-11-008-AstrazioniDatiSpecifica.pdf, tutto
PR2B-2014-12-09-AstrazioniDatiImplementazione.pdf
PR2B-2014-13-010-Reasoning.pdf, fino a pag. 4.

Letture: Capitolo 5 (fino pag. 111) di [PDJ]

Specifica di Tipi di Dati Astratti; Esempio: Polinomi (non modificabili). Implementazione di TDA: Scelta della rappresentazione; Tipi record in Java (Pair); Implementazione di IntSet con Vector; Impl. di Poly con array; Impl. di Poly con Vector di Pair. Ragionare su TDA: Modificabilità.

Ragionare sui Tipi di Dati Astratti

Lucidi:
PR2B-2014-13-010-Reasoning.pdf

Letture: Capitolo 5 (tutto) di [PDJ]

Ragionare su TdA: Categorie di operazioni; Adeguatezza di astrazione; Proprietà di astrazione; Correttezza di implementazione; Funzione di Astrazione; Invariante di Rappresentazione; Metodi toString() e repOk(); Correttezza di implementazione: rispetto a Invariante di rep; rispetto a specifica dei metodi.

Gerarchie di tipi in Java

Lucidi:
PR2B-2014-15-011-Gerarchie.pdf, PR2B-2014-16-012-Gerarchie2.pdf

Letture: Capitolo 7 di [PDJ]

Gerarchie di tipo; Astrazione per specifica applicata ai tipi di dati; Esempi di specifica e implementazione di sottotipi, con superclasse concreta, astratta e interfaccia; Ereditarietà multipla e singola; Gerarchia di tipi per implementazioni multiple; Principio di sostituzione: regola della segnatura, del metodo e della proprieta'.

Java generics

Lucidi:
PR2B-2014-17-013-Generics.pdf

Letture: Generics in the Java Programming Language, di Gilad Bracha.

Classi e interfacce generiche in Java; Parametri di tipo; L'interfaccia Comparable; Vincoli di tipo (extends); Metodi generici; Compatibilità per assegnamento in Java; Compatibilità e principio di sostituzione; Tipi covarianti e contravarianti; Wildcards: ?, extends, super; Differenze tra wildcards e Object; Type erasure; Compilazione di Java Generics.

Esercitazione su implementazione di Tipi di Dati Astratti

File da scaricare:

• Istruzioni.txt
• Input.java
• EuroInput.java
• OrderedIntList.java
• IntBST.java
• IntLinkedList.java

Portare i propri computer, ben caricati. Istallare una distribuzione di Java (vedere i link di sopra). Per l'esercitazione si useranno i comandi javac (compilatore) e java (interprete), eseguiti da linea di comando. Per scrivere i programmi si può usare un qualunque editor di testo.

Esercitazione su specifica e implementazione di Tipi di Dati Astratti, anche generici

File da scaricare:

• Istruzioni.txt

AVVISO: Visite guidate al Museo degli Strumenti per il Calcolo

Prima verifica intermedia Elenco iscritti alla prova con aula

La prova di verifica verterà su specifica, implementazione e dimostrazione di correttezza di Tipi di Dati Astratti in Java.
Testo: ES2014-01.pdf.

• La prova inizierà alle ore 14:00 precise
• Per prendere parte alla prova è obbligatorio iscriversi alla pagina http://compass2.di.unipi.it/didattica/inf31/share/orario/Appelli/ almeno 24 ore prima
• Gli studenti che si sono iscritti per l'appello straordinario si devono presentare in Aula B, e devono identificarsi presso il docente.
• Non è consentito usare dispense, libri, appunti o computer durante la prova intermedia.

Collezioni, Java Collection Framework e Iteratori

Lucidi: PR2B-2014-19-CollezioniIteratori.pdf, fino a pag. 30.

Collezioni: motivazioni; il Java Collections Framework; Interfacce Collection, List, Set, Queue, Map; Classi ArrayList, Vector,LinkedList; Classi di utilità Arrays e Collections; Iteratori: motivazioni; Interfaccia Iterator: specifica e uso; il comando for-each; Modifiche concorrenti; Esempi di specifica di iteratori.

Iteratori

Lucidi: PR2B-2014-19-CollezioniIteratori.pdf, tutto.
Iteratore su array: classi ArrayIterator.java e Test.java.
Letture: Capitolo 6 di [PDJ],
Tutorial su Java Collections Framework.pdf

Esempi di uso di iteratori; Implementazione di iteratori; Classi interne statiche e non; Funzione di astrazione e invariante di rappresentazione per classi che definiscono iteratori. Esercizio: sviluppo di un iteratore per Array.

Correzione prima verifica

Correzione: ES2014-01-SOL.pdf.
File java:

• CoinsCollection.java
• CoinsCollectionImpl.java
• CoinsCollectionImplAlt.java
• TestCoinsCollection.java

Nota: La lezione inizierà alle ore 12 per sospensione dell'attività didattica per Assemblea Studentesca di Ateneo.

Macchine Astratte, Linguaggi, Interpretazione, Compilazione

Lucidi: PR2B-2014-20-MacchineAstratte.pdf
Letture: Capitolo 1 di [LPPP]

Macchine astratte; Interpretazione; Compilazione.

Interpreti, Compilatori e Semantica Operazionale

Lucidi: PR2B-2014-21-SemOp-Espressioni.pdf
Letture:

• Semantica Operazionale eseguibile: Mike Grant Zachary Palmer Scott Smith, Principles of Programming Languages, Cap2: Operational Semantics fino a pag 15
  
• Semantica Operazionale BigStep e SmallStep, Note di Matthew Hennessy.
• Intermediate Representation, by Fred Chow, Com. ACM 56 (12) 2013

Per altra documentazione, si veda il corso Programmazione II su Moodle (https://elearning.di.unipi.it/moodle/). Per l'accesso si chieda la chiave al docente.

Valutazione di Espressioni: Type Checking ed Eliminazione della Ricorsione

Lucidi: PR2B-2014-22-TypeChecking-Ricorsione.pdf
File OCaml (anche per esercizio in lucido 18, pag 9):

• IntLetExp.ml interprete ricorsivo per espressioni con Let
• typecheck.ml Type Checking
• InterpreteIterativo.ml

Risultati Prima Verifica Intermedia del 31 marzo 2014

Strutturare i dati nei linguaggi di programmazione I
Lezione tenuta dal Prof. Ferrari

Lucidi: PR2B-2014-23-Dati.pdf
Letture: Capitolo 8 di [LPPP]

Tipi di Dati; Type Checking statico e dinamico; Inferenza di tipo; Polimorfismo; Descrittori di dato; Termini e Pattern Matching; Tipi Scalari; Tipi Composti; Puntatori

Strutturare i dati nei linguaggi di programmazione II
Lezione tenuta dal Prof. Ferrari

Tipi di dati di Sistema; Pila limitata non modificabile: specifica, semantica (tipo di dato algebrico) e implementazione (con array); Lista di interi: specifica, implementazione a heap; Pila limiatata modificabile: specifica, semantica (con riperimenti a pile non modificabili) e implementazione (con array); Programmi come dati; Meccanismi per definizione di nuovi tipi.

Nomi, Bindings, Ambienti

Lucidi: PR2B-2014-24-Nomi.pdf
Letture: Capitolo 4 di [LPPP]

Nomi nei linguaggi di programmazione; Oggetti denotabili; Bindings; Ambiente; Ambiente locale, non locale e globale; Scope o portata di un binding; Scoping statico o dinamico; Specifica, semantica e implementazione di ambienti polimorfi in OCaml.

Controllo di Sequenza: Espressioni e Comandi

Lucidi: PR2B-2014-25-ExpCom.pdf, fino a lucido n. 33.
Letture: Capitolo 6 di [LPPP]

Espressioni semplici con operazioni primitive; Operatori come funzioni parziali;Operatori non stretti; Valutazione: regola interna e regola esterna; Frammento funzionale: sintassi di espressioni, valori esprimibili, ambienti, type checking, semantica e implementazione dei singoli operatori, semantica delle espressioni. Frammento imperativo: sintassi di espressioni e comandi; valori esprimibili, denotabili e memorizzabili; specifica e implementazione della memoria; domini di valori e casting; semantica delle espressioni con ambiente e memoria.

Controllo di Sequenza: Comandi
Gestione Record di Attivazione per Blocchi e Procedure

Lucidi: PR2B-2014-25-ExpCom.pdf, tutto
PR2B-2014-26-AR.pdf, fino a lucido 43
Letture: Capitolo 5 di [LPPP]

Semantica operazionale e interprete OCaml di semplici comandi: assegnamento, condizionale, while, sequenza di comandi. Macro, macroespansione; Subroutine statiche Fortran; Copy rule statica e dinamica; Record di attivazione; Stack di RdA; Call/return di sottoprogramma; Blocchi; Funzioni e procedure; Cenni su passaggio di parametri per valore e per riferimento); Gestione di RdA con scoping statico; Costruzione della catena statica a runtime.

Gestione Record di Attivazione per Blocchi e Procedure
Interprete operazionale di Let e funzioni nel linguaggio didattico

Lucidi: PR2B-2014-26-AR.pdf, tutto
PR2B-2014-27-FunDid.pdf, fino a lucido 8

Funzioni come parametri e come risultato di funzione; Chiusura; Funzioni con Stato; Scoping dinamico; Eliminazione dei nomi da record di attivazione; Traduzione con indirizzo base + offset. Estensione di linguaggio didattico funzionale con Let, astrazione e applicazione di funzione; Semantica e interprete operazionale del Let.

Interprete operazionale di Let e funzioni nel linguaggio didattico
Passaggio di parametri

Lucidi:PR2B-2014-27-FunDid.pdf, tutto
PR2B-2014-28-ParPass.pdf, fino a lucido 16
Letture: Capitolo 7 di [LPPP], prima parte

Semantica operazionale e Interprete per Astrazione Funzionale e Applicazione di Funzione, con scoping statico e dinamico; Definizioni ricorsive; Scoping statico: Necessità di diversa definizione dell'ambiente non locale nella chiusura; Il costrutto Rec e costruzione di astrazione funzionale come punto fisso; Excursus: Definizioni Ricorsive come Punti Fissi di Funzionali; Costruzione iterativa del punto fisso per approssimazioni successive. Meccanismo di Passaggio di Parametri; Parametri formali e attuali; Modalità di passaggio ottenute con binding di formali a attuali nell'ambiente: per Costante, Riferimento, Oggetto, Funzione, Procedura; Parametri con valori default e varargs; Passaggio per valore.

Esercitazione su OCaml e interprete operazione del linguaggio didattico

File da scaricare:

• Istruzioni.txt
• Imp-Operazionale.ml
• Esempi.ml

Esercitazione svolta su computer portatili degli studenti. Si consiglia di caricarli a sufficienza per mancanza di prese elettriche.

Passaggio di parametri
Supporto a runtime per classi e oggetti

Lucidi: PR2B-2014-28-ParPass.pdf, tutto
PR2B-2014-29-Objx.pdf, fino a lucido 38 Letture: Capitolo 10 di [LPPP]

Passaggio di parametri per valore-risultato, e confronto con passaggio per riferimento; Passaggio per nome. Da strutture dati dinamiche e procedure a classi e oggetti; Paradigma OO: oggetti, ereditarietà, polimorfismo e dynamic binding; Implementazione di classi e oggetti; Liste di tabelle di metodi; vtables in c e JAVA; Compilazione separata di classi in Java; Constant pool per risoluzione di riferimenti a tempo di loading; Istruzioni per invocazione di metodi in bytecode; Ereditarietà multipla.

Supporto a runtime per classi e oggetti
Gestione della memoria

Lucidi:PR2B-2014-29-Objx.pdf, tutti.
PR2B-2014-30-GCv1.pdf, fino a lucido 16.
Letture: Capitolo 8, sezione 11 di [LPPP]

Class loading in Java; Stack inspection per sicurezza; Controllo degli accessi; Codice trusted e untrusted; Meccanismo di privilegi/permissions. Gestione della memoria: heap vs. stack; Heap con blocchi di dimensione fissa/variabile; Lista libera; Frammentazione; Identificazione del garbage.

Garbage collection
Confronto tra i supporti a run time di vari linguaggi

Lucidi:PR2B-2014-30-GCv1.pdf, tutti.
PR2B-2014-31-RTS.pdf.
Letture: Capitolo 13 di [LPPP]

Algoritmi di Garbage Collection; Reference Counting; Mark-Sweep; Copying collection; Approcci basati su generazioni. Confronto tra supporto a runtime di vari linguaggi: Fortran, Algol, Pascal, C, Java, C#, ML, LISP.

Esercitazione a classi riunite

File da scaricare:

• Istruzioni.pdf
• Imp-Operazionale.ml

Esercitazione svolta su computer portatili degli studenti. Si consiglia di caricarli a sufficienza per mancanza di prese elettriche.

Seconda verifica intermedia

• La prova inizierà alle ore 14:00
• Per prendere parte alla prova è obbligatorio iscriversi alla pagina http://compass2.di.unipi.it/didattica/inf31/share/orario/Appelli/ almeno 24 ore prima
• Non è consentito usare dispense, libri, appunti o computer durante la prova intermedia.