Diario delle Lezioni 2020-21

Martedì 29 settembre 2020 - Lezione 1

Introduzione Algoritmi e programmi: la rilevanza dello studio dei Linguaggi di Programmazione.
Analisi di problemi del C che rendono difficile valutare la correttezza dei programmi.

FP1 Introduzione ai linguaggi funzionale: l'archetipo teorico, il \lambda-calcolo.
Combinatori I, K, S. Computazione e computazioni non terminanti. Punti fissi.

Martedì 6 ottobre 2020 - Lezione 2

FP2 Introduzione ad Haskell: lambda calcolo in Haskell
Introduzione ai tipi di Haskell: polimorfismo e termini non tipabili
Strategia di valutazione: call-by-name
Funzioni: cittadini di prima classe.

OOP1 Introduzione agli oggetti: metafora degli oggetti come automi: stato nascosto e interfaccia
Classi come descrittori degli oggetti: definizioni di classi in C++
Regole di visibilità: private e public.
Costruttori. Overloading.

Martedì 13 ottobre 2020 - Lezione 3

OOP2 Programmazione di un tipo di dati astratto in C++: i numeri razionali
Invarianti di tipo di dato.
Oggetti sull'Heap e oggetti sullo Stack
Ridefinizione di operatori in C++

Martedì 20 ottobre 2020 - Lezione 4

OOP2 Ereditarietà e Sottotipaggio: la gerarchia dei punti
Costruttori e supercostruttori. Metodi e supermetodi.
Lookup dinamico dei metodi virtual.

FP3 Programmazione su naturali e liste in Haskell
Pattern matching.
Funzionali sulle liste: fold.

Martedì 27 ottobre 2020 - Lezione 5

FP4 Ancora funzionali su liste in Haskell: map, zipWith.
Applicazioni: prodotto scalare e prodotto tra matrici.
Haskellophilìa: Clausola where e list comprehension.

OOP3 Pensare le soluzioni a oggetti: architettura dell'applicazione Scacchi.
Esecuzione come scambio messaggi. Delegation.
Riuso del codice: spingere in codice in alto nella gerarchia delle classi.

Diario delle Lezioni 2019-20

Giovedì 26 settembre 2019 - Lezione 1

Algoritmi e programmi: la rilevanza dello studio dei Linguaggi di Programmazione.
Analisi di problemi del C che rendono difficile valutare la correttezza dei programmi. Introduzione ai linguaggi di programmazione funzionale e a oggetti.

Esercizio: usare la funzione scambia senza variabile di appoggio e scrivere un programma selectSort che azzera tutto il vettore, mentre funziona se viene usata un'altra funzione scambia.

Giovedì 3 ottobre 2019 - Lezione 2

FP 1: Introduzione ai linguaggi funzionali.
La funzione identità e il suo tipo. Polimorfismo e type inference.
Il combinatore K e il suo tipo.
Funzioni cittadini di prima classe.
Il combinatore D: termini non tipabili.
Alcune funzioni sulle liste: sum e length. Definizioni di funzioni per pattern matching.
Funzionali sulle lise: map e fold. Liste di funzioni.

Esercizi:
1. Scrivere un programma che calcola il prodotto scalare di due liste.
2. Scrivere map usando fold e senza decomporre liste via pattern matching.
3. Argomentare sul perché non si può scrivere fold in termini di map.

Giovedì 10 ottobre 2019 - Lezione 3

FP 2: Vari esempi di prodotto scalare, zipWith.
Pattern mathcing sugli interi: attenzione all'ordine con cui scrivere i casi di una definizione. Pattern matching non esaustivo.
Ancora su call-by-name: perché un myAnd con la semantica di && si potrebbe scrivere in Haskell. E in C no.
Definizioni e riduzioni. Confluenza e strategie di riduzione: outermost-leftmost è terminante.
Zucchero sintattico per Matematici: list comprehension. Alcuni esempi. fattori, primi, prodotto cartesiano.

Esercizi:
1. Scrivere un programma che genera numeri primi.

Giovedì 17 ottobre 2019 - Lezione 4

OOP 1: Introduzione alla programmazione a oggetti. Metafora degli oggetti come macchina con interfaccia e stato nascosto.
Esempio: programmare i razionali: tipi astratti di dato.
Il costrutto class: parti pubbliche e private nella definizione di una classe.
Invarianti di tipo di dato.
Creazione di oggetti: metodi costruttori. Oggetti sull'heap e sullo stack.
Costruttori e metodi overloaded.
Architettura generale dell'applicazione sugli scacchi. La classe Pezzo.

Esercizi:
1. Completare la classe Razionale.

Giovedì 24 ottobre 2019 - Lezione 5

OOP 2: Classi e sottoclassi: Esempio Pezzo e Alfiere.
Relazione di sottotipaggio tra i tipi definiti da una classe e la sua sottoclasse.
Metodi overriden: Esempio: puoiMuovere.
Il dynamic method lookup: i metodi virtual.
Costruttori delle sottoclassi e chiamate ai costruttori delle super classi.
Tipiche tecniche di programmazione: oggetti che passano il proprio riferimento.
Tipiche tecniche di programmazione: delegation. Esempio: il metodo print().

Esercizi:
1. Scrivere una gerarchia di almeno 3 sottoclassi per dimostrare gli effetti del dynamic method lookup.
Far vedere che anche chiamate a metodo generate dall'esecuzione di un metodo, vengono guidate dal primo oggetto ricevente.

Giovedì 31 ottobre 2019 - Lezione 6

FP 3: Riscaldamento in Haskell: pattern matching sui booleani.
foldr e (alcune del)le sue sorelle: foldl e foldr1.
Esempi: reverse quadratica (per ricorsione esplicita e usando foldr `raccogliendo' i risultati delle chiamate ricorsive)
e reverse efficiente con uso di parametro ausiliario per memorizzare i risultati
che corrisponde al `calcolo in avanti' di foldl.
Tipi (polimorfismo limitato): alcune osservazioni sulle classi di Haskell (Eq a), (Ord a), Num: loro relazioni coi tipi degli OOP.
Un grande classico: quicksort in Haskell: perla o propaganda?

Esercizi:
1. Scrivere quicksort in C sulle liste.
Ovviamente potete ``tradurre'' in C l'algoritmo Haskell visto a lezione,
ma che tipo di liste servono per avere un programma che sia fedele a Quicksort originale?

Giovedì 7 novembre 2019 - Lezione 7

FP 4: Computazioni lazy in Haskell
Definire la lista dei numeri naturali.
Lista dei numeri di Fibonacci.
Attenzione a scrivere definizioni produttive (cioè che producono almeno tanto input quanto ne consumano)
Un esempio un po' più complesso, gli Hamming numbers.
Generalizzazione degli Hamming Numbers a un insieme di generatori arbitrario.
Generare ciascun Hamming Number una sola volta
La principessa delle sequenze infinite: generazione dello stream dei numeri primi in Haskell.

Uno scritto sulla generazione di sequenze infinite: Computing Integer Sequences
Uno scritto sulla generazione dei numeri primi: Three Euler's Sieve and a Fast Prime Generator

Giovedì 14 novembre 2019 - Lezione 8

OOP 3: Overloading di operatori in Haskell. Esempio ==.
Overloading ed ereditarietà.
Introduzione ai Template (strutture dati generiche). Esempio classe Stack.

Esercizio: implementare le liste in C++. Provare a scrivere una funzione List<List> powerset()
che genera la lista di tutte le sottoliste (interpretare una lista come un insieme e assumere gli elementi tutti diversi.
Provare a scrivere la stessa funzione in Haskell (di tipo [a]->[ [a] ]).

Errata Corrige: overloading non estende alle classe derivate in C++!!!
Dalla pagina di FAQ su C++ di Soustrup: Why doesn't overloading work for derived classes?

Giovedì 21 novembre 2019 - Lezione 9

OOP 4: Precisazione sull'overloading nelle classi derivate in C++.
Standard Template Library: uso di alcune strutture dati nel progetto scacchi.
Uso di iteratori. Metodi per determinare lo scacco al Re e lo scacco matto nel progetto Scacchi.

Giovedì 29 novembre 2019 - Lezione 10

OOP 5: Copy constructor e distruttori.
Definizione di iteratori come inner class della struttura dati su cui iterano. Esempio: Stack .

Esercizio: definire l'iteratore costante per gli Stack.
Esercizio (facoltativo): definire gli alberi in C++ e alcuni iteratori su di essi (visite).

Giovedì 5 dicembre 2019 - Lezione 11

FP 5: Definizione di tipi induttivi in Haskell. Esempi: booleani, naturali, liste e alberi.
Definizione di classi in Haskell.

Esercizio: definire una funzione Haskell di codifica dagli alberi n-ari in alberi binari (e la sua inversa).

Giovedì 12 dicembre 2019 - Lezione 12

FP 6: Classe Functor. Maybe, List, e Tree come istanze di Functor.
Funtori applicativi.
La classe Monad applicate al tipo Maybe. Esempio: valutatore di espressioni.
Osservazioni sulla gestione di caratteristiche non-funzionali in Haskell.

Esercizio: definire la classe Applicative per le liste in modo che fmap2 sia zipWith, fmap3 sia zipWith3 etc.

Giovedì 19 dicembre 2019 - Lezione 13

OOP 6: Eredità multipla in C++. Utilità e problemi. Soluzioni alternative: interfacce in Java.
Eccezioni: sollevamento, cattura, trattamento.
Alcune tipiche tecniche sul trattamento di Eccezioni: masking, reflecting.

Diario delle Lezioni 2018-19

Nell'anno accademico 2018-19, le lezioni saranno divise in due.
Approssimativamente 1h sarà dedicato alla Programmazione a Oggetti (in C++) e
la mezz'ora rimanente verrà dedicato alla Programmazione Funzionale (in Haskell).

Mercoledì 26 settembre 2018 - Lezione 1

Algoritmi e programmi: la rilevanza dello studio dei Linguaggi di Programmazione.
Esempio: funzione C che verifica se una lista è palindroma confrontando L con reverse(L): cosa può andare storto.

OOP: Tipi di dato in C e tipi di dato astratti (à la ADA). Tipo di dato = struttura dati + operazioni.
Programmazione a Oggetti: slogan dei progettisti SmallTalk.
Metafora degli oggetti come automi con interfaccia.

FP: Introduzione ai linguaggi funzionali.
Computazione come riduzione di espressioni. Assenza della memoria.
Definizioni e riduzioni. Confluenza e strategie di riduzione.
Cenni ai tipi e all'inferenza di tipo.
Breve storia della programmazione funzionale (I): il Lambda-cacolo.

Mercoledì 3 ottobre 2018 - Lezione 2

OOP: Architettura generale dell'applicazione filo conduttore, gli Scacchi in C++
Introduzione al concetto di classe.
Classi e sottoclassi. Esempi: Scacchiera, Pezzo, e i pezzi veri e propri.
Definizioni di classe e metodi. Visibilità: public e private.
Metodi con lo stesso nome: overloading. Esempi: puoiMuovere(Casella, Casella, Scacchiera)
e puoiMuovere(Casella, Scacchiera).

FP: Prime funzioni in Haskell e loro tipi: identità, proiezione primo elemento.
Tipi polimorfi. Funzioni non terminanti e strategia di riduzione.
Il tipo di dato principe in Haskell: le liste. Notazioni. Funzione length e pattern matching.

Codici Haskell Lezione 2

Mercoledì 10 ottobre 2018 - Lezione 3

OOP: Sottoclassi ed ereditarietà: la classe Cavallo.
Specializzazione dei metodi: overriding.
Il problema dell'invocazione dei metodi in presenza di overriding: dynamic method lookup e virtual.
Pro e cons di static vs dynamic binding: flessibilità vs efficienza.

FP: Ancora funzioni su liste: head e tail: pattern non esaustivi ed eccezioni.
Funzioni appendi e rovescia. Clausola where.
Funzione palindroma. Type classes: polimorfismo limitato.
Esempio: tipo (Eq a) dei tipi che ammettono uguaglianza.
Definizione ricorsiva di liste infinite. Primi cenni alla laziness.

Codici Haskell Lezione 3

Mercoledì 17 ottobre 2018 - Lezione 4

OOP Ripasso sul virtual. I due metodi puoiMuovere(). Lookup del metodo riparte sempre dal primo oggetto ricevente.
Il puntatore all'oggetto stesso this.
Approfondimenti sulla relazione di sottotipaggio e assegnazioni ben tipate. Prudenza del type-checker.
Creazione di oggetti: costruttori: necessità e invocazione (con la new e quando allocati sullo Stack).
Costruttore di Default. Costruttori protected: classi da cui non si vogliono creare oggetti.
Invocazione del costruttore della super-classe, problemi col costruttore di default.

FP: Alcune piccole utilità: equazioni guardate, pattern, funzioni anonime (lambda espressioni).
Funzioni di ordine superiore map e reduce (o foldr).
Definizione di map usando reduce. Applicazione al calcolo del prodotto scalare.

Codici Haskell Lezione 4

Mercoledì 24 ottobre 2018 - Lezione 5

OOP Alcune classi dell'applicazione Scacchi: Scacchiera e Casella.
Tipica tecnica di programmazione: delegation. Esempio: metodo void print().
Metodi virtual puri. Esempio: il metodo print() nella classe Pezzo. Campi pubblici/privati e un diffuso malcostume: metodi setters e getters.
Un po' di zucchero sintattico: ridefinizione degli operatori predefiniti dal linguaggio.

FP: Zucchero sintattico per matematici: List comprehension.
Ridefinizione di funzioni su liste usando map, foldr e foldl.
foldr come generalizzazioni delle ricorsioni che calcolano il risultato al "ritorno" delle chiamate ricorsive.
foldl come generalizzazioni delle ricorsioni che calcolano il risultato all'"andata" delle chiamate ricorsive.
Esempio di famoso algoritmo in Haskell: quicksort. Limiti della versione Haskell.

Codici Haskell Lezione 5

Mercoledì 31 ottobre 2018 - Lezione 6

Discussione riassuntiva dei concetti introdotti nelle Lezioni 1-5.
Virtù composizionali della programmazione a oggetti e riuso del codice.
L'impatto di: metodi virtuali, regole di visibilità, sottotipaggio, ereditarietà.
Impatto sul riuso del codice.
Virtù composizionali della programmazione funzionale.
L'impatto di: tipi polimorfi, funzioni di ordine superiore, funzioni de-curryficate, astrazione.
Un esempio: moltiplicazione di matrici in Haskell. (vedi codici lezione precedente).

Mercoledì 7 novembre 2018 - Lezione 7

Nella settimana degli esoneri, discussione ed esercizi in Haskell e in C++.

Mercoledì 14 novembre 2018 - Lezione 8

OOP Puntatori e references: confronto ed esempi.
Passaggio per valore di oggetti: copy constructor.
Distruzione di oggetti: distruttori e delete. Lifetime degli oggetti.

FP: Introduzione alla valutazione lazy.
Alcuni esempi notevoli: streams dei naturali, potenze, numeri di fibonacci

Mercoledì 21 novembre 2018 - Lezione 9

OOP Polimorfismo generico in C++: Templates.
Esempio di definizione di un template: gli Stack in C++.
Introduzione all'uso di eccezioni: sollevamento, cattura, trattamento.

FP: Alcuni interessanti problemi di generazione di streams: Hamming numbers.

Uno scritto sulla generazione di sequenze infinite: Computing Integer Sequences

Mercoledì 28 novembre 2018 - Lezione 10

OOP Introduzione all'uso di iteratori su strutture dati.
Stack con iteratori.
Introduzione alle STL (= Standard Template Library). Applicazioni al progetto scacchi: metodo allMoves.

FP: La principessa delle sequenze infinite: generazione dello stream dei numeri primi in Haskell.
Uno scritto sulla generazione dei numeri primi: Three Euler's Sieve and a Fast Prime Generator

Mercoledì 5 dicembre 2018 - Lezione 11

OOP Applicazione di concetti visti: metodi move e scaccoMatto.

FP: -.

Mercoledì 12 dicembre 2018 - Lezione 12

OOP: Revisione delle principali classi della Standard Template Library: vecotr, deque, arrayList.
Il caso della classe stack.
Cenni agli Algorithms. Il problema della modifica di una struttura dati durante una scansione di un iteratore: const_iterator.

FP: Definizione di tipi in Haskell. type, data, Maybe.
Alcuni esempi di tipi induttivi: naturali, liste, alberi.

Mercoledì 19 dicembre 2018 Lezione annullata (Festa di Matematica).

Mercoledì 9 gennaio 2019 - Lezione 13

Classi in Haskell. Classi pre-definite (Eq, Ord, Num, etc.).
Definizioni di classi e istanze.
Confronti con C++ (ereditarietà multipla) e Java (interfacce).

Mercoledì 16 gennaio 2019 - Lezione 14

OOP ?.

FP: Derivazioni di programmi da specifici. Esempio: minimo intero libero in una lista.

Diario delle Lezioni 2017-18

Nell'anno accademico 2017-18, il contenuto delle lezioni è stato del tutto analogo alle lezioni
tenute nell'anno accademico 2016-17. Sono state tenute 11 lezioni a cominciare da giovedì 5 ottobre (in aula G)
e poi tutti i mercoledì (in aula F, escluso il primo novembre).

Nel mese di gennaio sono state svolte 2 lezioni di introduzione alla programmazione funzionale in Haskell (10 e 17 gennaio),
che non saranno parte del programma di Esame.

Mercoledì 10 gennaio 2018 - Lezione 12

Breve introduzione al Lambda-calcolo: sintassi, beta-regola.
Alcuni esempi: identità, proiettori, termini non terminanti, numerali di Church, operatore di punto fisso.
A taste of Haskell: sintassi, tipi polimorfi, riduzione.
Confluenza e strategia di valutazione call by name.
Introduzione alle liste e alla ricorsione su liste.
Laziness: generazione (lazy) di tutti i numeri di fibonacci in una riga.

Mercoledì 17 gennaio 2018 - Lezione 13

Ordine superiore: permutatore di argomenti di una funzione (binaria).
Ancora esempi di programmazione su liste: prodotto scalare tra vettori (come liste).
Esempio notevole di ordine superiore: moltiplicazione tra matrici (come liste di liste).
Esempio notevole della concisione dei programmi Haskell: qSort.
Ancora sui tipi polimorfi: tipo principale e termini tipabili in Haskell: x x where x = \y -> y.

Diario delle Lezioni 2016-17

I numeri in grassetto puntano ai capitoli del libro Thinking in C++ che trattano l'argomento considerato.

Diario delle Lezioni 2015-16

Per l'anno accademico 2015-16 non è stato compilato un dettagliato Diario delle Lezioni,
in larga parte analogo a quello sottostante relativo all'anno accademico 2014-15,
anche se gli argomenti sono stati presentati in un ordine leggermente diverso.

Nell'anno accademico 2015-16, tuttavia, sono stati inoltre affrontati, con più dettaglio, i seguenti argomenti:

• Copy Constructor e problematiche relative al passaggio di oggetti come parametro per valore [11];
• Carrellata sulle principali librerie di strutture dati (Standard Template Library, STL) e iteratori [4], vol. 2.

Diario delle Lezioni 2014-15