PROGRAMMA DEL CORSO DI
PROGRAMMAZIONE II
dott. Donato Malerba

Obiettivi. Il corso approfondisce alcune tecniche di programmazione utilizzabili nello sviluppo di applicazioni function-oriented, in cui la complessità prevalente del sistema riguarda le funzioni da realizzare. In particolare sono analizzate le tecniche di programmazione orientata agli oggetti, funzionale, logica, e concorrente, legate a nuovi paradigmi di programmazione che si sono affermati in diversi contesti. L’obiettivo è duplice: da una parte, illustrare i fondamenti teorici dei paradigmi, per i benefici di rigore e sistematicità che ne derivano, e dall’altra presentare alcuni strumenti operativi che supportano i diversi stili di programmazione, ovvero i linguaggi di programmazione. La prima metà del corso è dedicata alla programmazione sequenziale, utilizzata in applicazioni più tradizionali, mentre la seconda parte è rivolta alla programmazione concorrente, e in particolare ai meccanismi di sincronizzazione e comunicazione.

Prerequisiti: conoscenze di programmazione imperativa, sistemi operativi, logica matematica.

 
Programma del corso a.a. 1997-98

1. Introduzione ai paradigmi di programmazione.

I tre approcci alla programmazione: operazionale, definizionale e dimostrazionale. 2. Il paradigma imperativo. Fondamenti: la manipolazione sequenziale di dati in memoria. La struttura dei programmi, i dati (dichiarazioni, tipi primitivi, composti e ricorsivi, equivalenza dei tipi), le espressioni, i comandi, la gestione del flusso di controllo, la composizione (blocchi e sottoprogrammi), legame statico e dinamico.

Ambienti e linguaggi di programmazione.
Due linguaggi a confronto: C e Ada.

 3. Astrazione. Fondamenti: L'astrazione nella programmazione. Astrazione di funzione, di procedura, di controllo, e di selettore. Astrazione di dati:requisiti di astrazione e protezione. I moduli per l’incapsulamento dell’informazione e l'information hiding. Oggetti e classi di oggetti. Tipo astratto di dati vs. classe di oggetti. Astrazione generica. Specifiche algebriche e assiomatiche per i tipi di dati astratti.

Ambienti e linguaggi di programmazione.
I moduli in Modula-2, Turbo Pascal, C e Ada.

 4. La programmazione orientata agli oggetti. Fondamenti: oggetti, classi, ereditarietà, polimorfismo e message passing. Gerarchia di classi e gerarchia di interfacce.

Ambienti e linguaggi di programmazione.
Smalltalk: origini, sintassi di espressioni; i messaggi; i blocchi; selezione e ripetizione; i metodi; classi ed ereditarietà singola; il polimorfismo; le classi astratte; le classi predefinite; le metaclassi; l’ambiente a finestre; l’implementazione.
C++: dalle strutture alle classi; classi di oggetti ed eraditarietà multipla; template di classe e di funzione; classi derivate; le funzioni virtuali; i sottotipi; macro e funzioni in-line.
Visual C++: cenni. Caso di studio: il sistema WISDOM++.
Le standard template libraries.
Java: origini e motivazioni, classi, metodi, erediarietà singola, interfacce, i tipi di dati predefiniti, gli operatori, il flusso di controllo, dalle applicazioni agli applet.

 5. La programmazione funzionale. Fondamenti: L'approccio operazionale e quello definizionale. Sintassi del l-calcolo puro, le sostituzioni, la teoria formale, il teorema di Church-Rosser, teorema del punto fisso, le due regole computazionali del call-by-value e del call-by-name, un l-calcolo applicato, ML0.

Ambienti e linguaggi di programmazione.
Lisp e Scheme: le liste e funzioni per la loro manipolazione; definizione di funzioni; i condizionali; strutture dati in Common Lisp.
CLOS: classi e istanze; ereditarietà; selezione dei metodi; le funzioni generiche.

 6. La programmazione logica. Fondamenti: programmare per dimostrazioni, clausole e programmi definiti, le interrogazioni, semantica dei modelli e modello minimo di Herbrand, semantica del punto fisso e caratterizzazione di punto fisso del minimo modello di Herbrand, unificazione di termini, risoluzione binaria e proprietà, semantica operazionale e la risoluzione SLD. La negazione in programmazione logica: negazione per fallimento, completamento di un programma definito, correttezza della regola NF, programmi normali e stratificati.

Ambienti e linguaggi di programmazione logica.
Prolog: dalla programmazione logica al Prolog, la ricerca depth-first, sintassi del Prolog, liste e operazioni su liste, il principio di invertibilità, gli operatori, il cut, implementazione della negazione. Caso di studio: il problema della scimmia e della banana.

 7. Altri paradigmi di programmazione. Cenni ai paradigmi trasformazionale, form-based, dataflow, e constraint-based. 8. La programmazione concorrente. Fondamenti: I/O sovrapposto e computazione, multiprogrammazione e multitasking, problemi di programmazione concorrente, l'astrazione in programmazione concorrente, le dimostrazioni di correttezza per proprietà di sicurezza e di liveness. La programmazione concorrente mediante istruzioni load e store su sitemi a memoria condivisa: alcune semplici soluzioni al problema della mutua esclusione per due processi, l'algoritmo di Dekker, l'algoritmo del fornaio per la mutua esclusione fra N processi. Programmazione concorrente con semafori: soluzione al problema della mutua esclusione, soluzione al problema del produttore consumatore. Programmazione concorrente con monitor: soluzione al problema del produttore-consumatore, emulazione di monitor attraverso semafori, emulazione di semafori con monitor, soluzione al problema dei lettori e degli scrittori. Il problema dei cinque filosofi: soluzioni con semafori e con monitor.             Ambienti e linguaggi per la programmazione concorrente.
Generalità. Classi di applicazioni distribuite: parallele e ad alta prestazione; fault-tolerant; applicazioni che usano la specializzazione funzionale; applicazioni inerentemente distribuite. Requisiti per i sostegno alla programmazione distribuita. Ambienti per il calcolo distribuito. Definizione delle unità di parallelismo. Comunicazione e sincronizzazione fra processi: Message passing (implicita/esplicita, sincrona/asincrona, comunicazione punto a punto con rendez-vous e chiamate a procedure remote, broadcast/multicast) e condivisione dei dati (strutture distribuite di dati vs. variabili logiche condivise). Nondeterminismo nella sincronizzazione dei processi. Potenzialità dei linguaggi operazionali (imperativi e object-oriented) e dichiarativi (funzionali e logici) per la programmazione distribuita.
Casi di studio: la concorrenza in ADA, Java e Concurrent Prolog.
 
Principali testi e articoli di riferimento

1. Introduzione ai paradigmi di programmazione.

A.L. Ambler, M.H. Burnett, & B.A. Zimmerman
Operational Versus Definitional: A Perspective on Programming Paradigms
IEEE Computer, 25(9): 28-43, September 1992.
  2. Il paradigma imperativo.
 
C. Montangero, F. Turini
Introduzione alla Programmazione: Sintassi, Semantica e Metodo
Boringhieri, 1987.

H. E. Bal, D. Grune
Programming Languages Essentials (cap. 1-2)
Addison-Wesley, 1994

3. Astrazione dati.

E. Lodi, & G. Pacini
Introduzione alle Strutture di Dati (cap. 3-4)
Bollati Boringhieri, 1990.

M. Shaw
Abstraction Techniques in Modern Programming Languages
IEEE Software, 10-26, October 1984.

 D. A. Watt
Programming Language Concepts and Paradigms (cap. 5-6)
Prentice Hall, 1990.
 

 4. La programmazione orientata agli oggetti. C. Giustozzi, & S. Polini
OOP: Object Oriented Programming
Technimedia, 1991

G. Masini, A. Napoli, D. Colnet, D. Léonard, & K. Tombre
Linguaggi per la Programmazione a Oggetti (cap. 2-3, 6)
Gruppo Editoriale Jackson, 1989

R. Sethi
Linguaggi di Programmazione (cap. 5-6)
Zanichelli, 1994

B. Stroustrup
What is Object-Oriented Programming?
IEEE Software, May 1988.

B. Breedlove et al.
Web Programming Unleashed (cap. 5-8)
Sams.net, 1996
 

 5. La programmazione funzionale. R. Sethi
Linguaggi di Programmazione (cap. 7,12)
Zanichelli, 1994

G. Masini, A. Napoli, D. Colnet, D. Léonard, & K. Tombre
Linguaggi per la Programmazione a Oggetti (cap. 5)
Gruppo Editoriale Jackson, 1989
 

 6. La programmazione logica. U. Nilsson, & J. Maluszynski
Logic, Programming and Prolog (cap. 1-5)
Wiley, 1990

I. Bratko
Prolog Programming for Artificial Intelligence
Addison-Wesley, 1993.
 

 7. Altri paradigmi di programmazione. A.L. Ambler, M.H. Burnett, & B.A. Zimmerman
Operational Versus Definitional: A Perspective on Programming Paradigms
IEEE Computer, 25(9): 28-43, September 1992.
  8. La programmazione concorrente.
 
                M. Ben-Ari
                Principi di programmazione concorrente e distribuita (cap. 1-8, Appendice B)
                Jackson, 1991 H.E. Bal, J.G. Steiner, A.S. Tanembaum
Programming Languages for Distributed Computing Systems
ACM Computing Surveys, 21(3), 1989.

E. Shapiro
Concurrent Prolog: A Progress Report
IEEE Computer, 19(8), 1986

L. Lemay, C. L. Perkins
Teach Yourself Java in 21 days (cap. 18)
Sams.net, 1996

M. Carli
Java e il problema dei cinque filosofi
Computer Programming, Gennaio 1998.