Linguaggi di Programmazione I e II 2010/2011

There are two ways of constructing a software design: one way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.

[C. A. R. Hoare]

Indice

Finalità del corso

I corsi di Linguaggi I e II, intendono fornire una conoscenza delle caratteristiche dei vari paradigmi di programmazione, cercando il più possibile di evitare di concentrarsi su uno specifico linguaggio, andando bensì a presentare i principi che guidano la progettazione, realizzazione e implementazione dei moderni linguaggi di programmazione. Con solida conoscenza delle caratteristiche “universali” si potranno così in futuro imparare nuovi linguaggi in pochissimo tempo.

A questa visione generale si giunge attraverso la descrizione dei principali paradigmi di programmazione:

• imperativo,
• funzionale,
• logico e
• logico-funzionale.

Questi paradigmi, oltre a essere esaminati nei loro aspetti pragmatici più immediati, sono analizzati e confrontati sulla base dei principi generali, in modo tale da permettere una comprensione critica della maggior parte dei linguaggi di uso comune. In questo modo si intende sviluppare uno spirito critico che permetta di arrivare ad una programmazione consapevole in cui saper scegliere il paradigma più adatto a seconda del problema da risolvere e sapere quali costrutti di un linguaggio usare, e (soprattutto) a quale costo.

I due corsi inoltre intendono fornire una conoscenza relativamente approfondita (soprattutto dell'aspetto programmativo) dei paradigmi di programmazione dichiarativa (funzionale, logico e logico-funzionale) che, grazie alla loro espressività, si prestano naturalmente quale base di sviluppo di software corretto. Si mostrerà come caratteristiche quali high-order e non-determinismo possano essere sfruttate per scrivere codice compatto, elegante e flessibile (riutilizzabile).

Il corso di Linguaggi I, in particolare, tratterà innanzitutto i concetti generali, fornendo una conoscenza “language independent” delle caratteristiche di tutti i paradigmi. Si vedranno poi il paradigma imperativo e i meccanismi di supporto a “run-time” dei linguaggi imperativi. Dopodiché si illustreranno le caratteristiche del paradigma funzionale (specialmente l'high-order programming).

Il corso di Linguaggi II, in particolare, illustrerà i modelli d'esecuzione dei linguaggi funzionale e poi completerà la presentazione dei paradigmi dichiarativi: logico e logico-funzionale (specialmente il non-deterministic high-order programming).

Programma

Linguaggi 1 (VERSIONE PRELIMINARE)

• Paradigma Imperativo
  • Macchine astratte, Interpretazione e Compilazione
  • Descrivere un linguaggio di Programmazione (Sintassi e Semantica)
  • I nomi e l'ambiente
  • La gestione della memoria
  • Strutturare il controllo
  • Astrarre sul controllo (Metodi di passaggio dei parametri)
  • Strutturare i dati
  • Type checking monomorfo e polimorfo
  • Un esempio di Macchina Astratta: P-code Machine
    • Per informazioni dettagliate e approfondimenti si vedano:
      • i capitoli 10 e 12 del libro Pascal Implementation , Pemberton&Daniels
      • Sezione 6.2 (Icode) del libro The GENTLE Compiler Construction System
      • Per sperimentare è disponibile l'implementazione (freeware) The P4 compiler, in particolare:
        • pint.pas Assembler and interpreter of Pascal code, K. Jensen, N. Wirth, Ch. Jacobi, ETH
        • pcode.pas
• Paradigma Funzionale
  • Introduzione alla Programmazione Funzionale.
  • High-order Programming.
  • Il linguaggio Haskell (tutorial, libro online, prelude, file usato a lezione per le demo, miei esempi 2008/01/03).
    [Si vedano inoltre i corsi online della Microsoft]
    • list comprehensions, partial applications of curried functions, sections, non-strict functions, infinite data structures, case expressions, pattern matching
    • Types, Classes and Overloading
    • Haskell's monadic I/O
    • Standard Haskell Classes
    • Monads
    • Modules

Linguaggi 2 (VERSIONE PRELIMINARE)

• Modelli di esecuzione del paradigma funzionale
  • Sistemi di riscrittura, Pattern Matching
• Paradigma Logico
  • Introduzione alla Programmazione Logica: Unificazione, SLD-derivations
  • Semantica denotazionale della Programmazione Logica.
  • Non-deterministic Programming
  • Il linguaggio Prolog (file usato a lezione per le demo, alcune implementazioni: GProlog, Swi-Prolog e Sicstus,).
  • Warren Abstract Machine (testo di riferimento, slides sull'evoluzione della memoria mostrate a lezione, syllabus, istruzioni, alcuni esempi di compilazioni di programmi prolog in linguaggio WAM si possono trovare nei testi dei compiti)
• Paradigma Logico-Funzionale
  • Programmazione Logico Funzionale: narrowing (needed narrowing).
  • High-order Non-deterministic Programming.
  • Il linguaggio Curry (tutorial, un implementazione: MCC/AquaCurry, file usato a lezione per le demo, nqueens, miei esempi 2006/03/24).

Bibliografia

• M. Gabbrielli e S. Martini. Linguaggi di Programmazione - Principi e Paradigmi. McGraw-Hill. ISBN 88-386-6261-4
• P. Hudak, J. Peterson, J. Fasel. A Gentle Introduction to Haskell 98. 1999
• L. Sterling, E. Shapiro. The art of Prolog, MIT Press, 1986.

Libri e Testi di consultazione

• Paradigma imperativo
  • D.W. Barron (Ed). PASCAL: The Language and Its Implementation. John Wiley & Sons Ltd, 1981
  • F. W. Schröer The GENTLE Compiler Construction System. R. Oldenbourg Verlag, 1997, ISBN 3-486-24703-4
• Paradigma funzionale
  • B. O'Sullivan, D. Stewart, J. Goerzen. Real World Haskell. O'Reilly Media, 2008.
  • B. Wadler. Introduction to Functional Programming using Haskell. ISBN: 0134843460, Prentice Hall PTR, 1998
  • Terese. TERESE LITE. Vrije Universiteit, 2006. (estratto dal libro Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003)
• Paradigma Logico
  • K. R. Apt, From Logic Programming to Prolog, International Series in Computer Science, Prentice Hall, 1997.
  • Hassan Aït-Kaci. Warren's Abstract Machine: A Tutorial Reconstruction, MIT Press, 1991, ISBN 0-262-01123-9. FUORI STAMPA
• Paradigma Logico-Funzionale
  • M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice, Journal of Logic Programming, 19&20:583-628, 1994.
  • S. Antoy, R. Echahed, M. Hanus. A Needed Narrowing Strategy, Journal of the ACM, 2000.

Esercizi di Programmazione

Per chi volesse esercitarsi a programmare in uno dei paradigmi visti a lezione ho scritto alcuni esercizi a difficoltà (più o meno) crescente. Vi consiglio fortemente di non scriverli solo su carta ma provare ad eseguirli (ci sono ottime implementazioni freeware disponibili sia di Prolog che di Haskell). Quando poi siete ragionevolmente sicuri di aver fatto un programma funzionante secondo la specifica (che implica averlo provato a calcolatore), se volete avere i miei commenti su quanto avete fatto (e, se siete a buon punto, avere le mie soluzioni) mandatemi via mail quanto avete fatto oppure (anche meglio) portatemi tutto a ricevimento. Didatticamente reputo controproducente mettervi on-line le mie soluzioni perchè altrimenti restereste influenzati dalla mia soluzione prima di metabolizzarne una vostra. Inoltre vi sconsiglio di fare tutti gli esercizi e mandarmi tutto in blocco alla fine: meglio fare 2/3 esercizi e poi, prima di affrontare quelli più complessi, verificare quanto appreso per poi trarre profitto dall'esperienza fatta nell'affrontare i nuovi esercizi ed evitare di ripetere gli stessi errori.

• Haskell: Il file aggiornato contenente la lista di Esercizi di programmazione Hakell si può scaricare da Materiale Diddattico
  • Nella Home di Haskell potere trovare moltissima documentazione sul linguaggio e i links a varie implementazioni freeware, fra cui GHC.
  • Consiglio l'uso di hlint sui vostri programmi per imparare ad evitare certi tipi di errori
  • Per non impararsi molte informazioni tecniche a memoria si può usare il comodissimo Hoogle (sia on-line che in locale)
• Prolog: Il file aggiornato contenente la lista di Esercizi di programmazione Prolog si può scaricare da Materiale Diddattico
  • Ci sono ottime implementazioni freeware di Prolog, ad esempio gprolog e swi-prolog
• Curry: Per iniziare si possono riadattare gli esercizi di programmazione Hakell, avendo cura di evitare il non-determinismo (implicito) non voluto. Poi si possono affrontare gli esercizi di programmazione Curry che sfruttano le caratteristiche peculiari del paradigma logico-funzionale, testo scaricabile da Materiale Diddattico.
  • Nella Home di Curry potere trovare moltissima documentazione sul linguaggio e i links alle implementazioni MCC (Münster Curry Compiler, per MacOSX usate l'ottimo AquaCurry) e PAKCS (che si basa su Sicstus o su Swi-Prolog e si può usare via interfaccia web).

Implementazioni free

Modalità d'esame

L'esame di Linguaggi 1 o 2 si compone di una prova scritta ed (eventualmente) di una prova orale (soprattutto per discriminare le situazioni "di confine" o, in ogni caso, "sospette" e/o dare la possibilità di alzare il voto rispetto allo scritto).

Iscrizioni Necessarie!!!

Si ricorda che sia per potersi presentare alle prova scritta che a quella orale è necessaria l'iscrizione elettronica (mediante il sito S3). Mi riserverò la facoltà di non ammettere allo scritto i non iscritti.

Prova Scritta:

La prova scritta richiede di:

• svolgere degli esercizi analoghi a quelli presentati nelle esercitazioni e a quelli dati per casa (inclusi quelli qui)
• rispondere ad alcune domande sugli argomenti trattati nelle lezioni.

Ogni volta che si consegna per la correzione una prova scritta si cancella il voto precedente.
Le prove vanno redatte secondo le seguenti modalità (pena la non validità della prova):

• entrambe i fogli con il testo devono essere consegnati con scritte le proprie generalità, scritte nell'apposito spazio e non dove capita!
• la soluzione della parte relativa a P-CODE o WAM deve essere fisicamente separata dalle altre soluzioni!
• le soluzioni devono essere motivate/giustificate in modo preferibilmente sintetico ma comunque necessariamente completo (in particolare quanto presente nelle bozze delle soluzioni messe on-line sicuramente non basta)
• riguardo agli esercizi di programmazione
  • non sono ammessi short-cuts del tipo "idem come sopra" (la necessità di simili artifici tra l'altro dovrebbe suggerire che forse la soluzione è fatta male)
  • i tipi delle funzioni vanno scritti vicino alle funzioni a cui si riferiscono
  • bisogna rispettare il case (maiuscolo/minuscolo) previsto dalle sintassi dei rispettivi linguaggi e quindi non è ammesso scrivere in stampatello tutto maiuscolo o minuscolo (che non permetterebbe di distinguere il case)
  • non è ammesso mescolare le sintassi dei vari linguaggi

Prova Orale (se necessaria) e Registrazione Voto Esame:

La prova orale consiste nella discussione di alcuni degli argomenti trattati a lezione.
Per poter sostenere la prova orale o registrare il voto dell'esame (se la prova orale non fosse necessaria e non si intendesse sostenerla), è necessario aver superato una prova scritta da meno di un anno.
Se durante la prova scritta non fosse stata fissata una data per l'orale basta accordarsi via mail.
Nel caso la prova orale non venga superata o si decida di non accettare il voto, lo scritto rimane valido al fine di sostenere un secondo esame orale.
La registrazione viene eseguita on-line quindi qualora (potendo) si volesse registrare il voto proposto ricevuto via Sindy basta accettarlo, da Sindy stesso, e a quel punto verrà automaticamente registrato.

Sia alla prova scritta, quanto quella orale, è ammesso l'uso di qualsiasi materiale didattico (libri, appunti,...) purché cartaceo.

Testi degli esami passati

Potete inoltre scaricare in formato elettronico (parte dei) testi dei compiti passati:

Esami di Linguaggi 1

1. testo del compito del 27/01/2011 su Materiale Diddattico
2. testo del compito del 22/02/2010 su Materiale Diddattico
3. testo del compito del 01/02/2010 su Materiale Diddattico
4. testo del compito del 07/09/2009
5. testo del compito del 17/07/2009
6. testo del compito del 01/07/2009
7. testo del compito del 26/02/2009
8. testo del compito del 02/02/2009
9. testo del compito del 17/09/2008
10. testo del compito del 11/07/2008
11. testo del compito del 10/04/2008
12. testo del compito del 20/12/2007
13. testo del compito del 05/12/2007
14. testo del compito del 17/09/2007
15. testo del compito del 13/07/2007
16. testo del compito del 13/04/2007
17. testo del compito del 23/03/2007
18. testo del compito del 12/01/2007
19. testo del compito del 18/12/2006
20. testo esercizio P-Code Pascal del 02/12/2004
21. testo esercizio P-Code Pascal del 08/09/2004
22. testo esercizio P-Code Pascal del 06/07/2004
23. testo esercizio P-Code Pascal del 23/06/2004

Esami di Linguaggi 2

1. testo del compito del 15/06/2010 su Materiale Diddattico
2. testo del compito del 22/02/2010 su Materiale Diddattico
3. testo del compito del 07/09/2009
4. testo del compito del 17/07/2009
5. testo del compito del 01/07/2009
6. testo del compito del 17/06/2009
7. testo del compito del 17/09/2008
8. testo del compito del 11/07/2008 (con soluzione WAM)
9. testo del compito del 10/04/2008
10. testo del compito del 28/03/2008 (con soluzione WAM)
11. testo del compito del 17/09/2007
12. testo del compito del 03/09/2007
13. testo del compito del 13/07/2007
14. testo del compito del 13/04/2007 (con soluzione WAM)
15. testo del compito del 23/03/2007 (con soluzione WAM)