Introduzione alla Programmazione Funzionale

Questa e' la home page del corso "Introduzione alla Programmazione Funzionale".

Lezioni:

Questo e' il tentativo di orario per il corso:

• Prima Lezione: 2021/11/23, 9:30 -> 12:00
  • Introduzione al corso
  • Primi esempi ed esercizi: Massimo Comune Divisore e Torri di Hanoi
• Seconda Lezione: 2021/11/30, 9:30 -> 12:00
  • Le basi della programmazione funzionale: la ricorsione
• Terza Lezione: 2021/12/03, 10:00 -> 12:30
  • Programmazione funzionale: principi fondamentali
  • Introduzione al currying
• Quarta Lezione: 2021/12/07, 10:00 -> 12:30
  • Approfondimenti sul currying
  • Esempio su calcolo della derivata: funzioni che approssimano la funzione derivata
  • Breve introduzione al lambda calcolo
• Quinta Lezione: 2021/12/10, via Maffi Aula 11, 10:00 -> 12:30
  • Esercizi su lambda-calcolo e riduzione di lambda-espressioni complesse tramite tool automatici
  • Primi esperimenti con Haskell
• Sesta Lezione: 2021/12/14, via Maffi Aula 5, 9:30 -> 12:00 (OKKIO! L'orario e' cambiato ancora!)
  • Tipi di dato algebrici
  • Tipi di dato che modellano azioni di I/O
• Settima Lezione: 2021/12/17, sede centrale Aula 10, 10:00 -> 12:30
• Ottava Lezione: 2021/12/21, sede centrale Aula 10, 10:00 -> 12:30
  • Poche parole finali sui linguaggi di programmazione funzionali

Esempi ed esercizi:

• Primo esempio: calcolo del massimo comune divisore
  • Implementazione iterativa: l'algoritmo di Euclide
  • Implementazione ricorsiva
  • Implementazione puramente funzionale
  Questo codice puo' essere testato usando una semplice funzione main ed un header file che descrive l'interfaccia software della funzione gcd()
• Secondo esempio: soluzione del problema delle torri di Hanoi
  • soluzione in C
  • soluzione piu' complessa, con un output piu' interessante
  • soluzione funzionale, in C++. Una simile soluzione in C e' sicuramente meno leggibile e mostra l'importanza dei garbage collector nella programmazione funzionale.
• Terzo esempio: fattoriale ed uso dello stack
  • implementazione non tail-recursive
  • implementazione tail-recursive (compilare con gcc -O1 -S fact1.c)
  Questo codice puo' essere testato usando una semplice funzione main ed un header file che descrive l'interfaccia software della funzione gcd()
• Quarto esempio: contatore implementato tramite chiusure
  • Soluzione (errata) in C, che evidenzia la differenza fra chiusure a puntatori a funzioni
  • Soluzione in C++, che evidenzia come le lambda expression del C++ implementino correttamente il concetto di chiusura
• Quinto esempio: passaggio dei parametri. Problema con il passaggio per valore in C++ e possibile soluzione.
• Sesto esempio: currying. Funzione somma curryificata e usando una coppia per gli argomenti.
• Settimo esempio: calcolo del Massimo Comun Divisore in Haskell. Il codice mostra varie implementazioni definendo la funzione tramite lambda (ed usando la tecnical del currying per gestire i due argomenti) o usando la definizione semplificata senza lambda.
• Ottavo esempio: il fattoriale tail recursive in Haskell.
• Nono esempio: soluzione delle torri di Hanoi in Haskell:
  • Prima soluzione, usando "muovi 0 dischi" come base induttiva
  • Seconda soluzione, usando "muovi 1 disc0" come base induttiva
  • Terza soluzione, usando "muovi 0 dischi" come base induttiva e definendo la funzione per casi
  • Quarta soluzione, usando "muovi 1 disco" come base induttiva e definendo la funzione per casi
• N-esimo esempio: come dire "Hello" in Haskell:
  • Versione minimale
  • Versione con blocco "do"
  • Versione simil-imperativa
  • Programma che chiede il nome
  • Altra versione, che sembra effettuare assegnamenti!
• Qualche esempio sui tipi di dato ricorsivi in Haskell:
  • Implementaione dei numeri naturali secondo Peano in Haskell...
    • ...Ed in C++!
  • Implementazione di una lista di interi o lista generica come tipo di dato ricorsivo in Haskell
  • Funzioni per operare sulle stringhe in Haskell
  • Liste immutabili in C: header file, definizioni di base, funzioni per operare sulle liste (con relativo header file) e programma di test (per confronto, implementazione tradizionale di liste non immutabili)
• E per finire, un po' di esempi su Scala:
  • Di' ciao
  • Calcolo del Massimo Comun Divisore (versione alternativa)
  • Controversie su ordine di valutazione e purezza funzionale

Dispense:

• Breve introduzione alla programmazione funzionale
• Qualche definizione di concetti riguardanti i linguaggi di programmazione
• Qualche dettaglio in piu' sul lambda calcolo
• Piccola introduzione ad Haskell
• I tipi di dato ricorsivi

Link:

• Proposta di introdurre le chiusure nel prossimo standard C e sua estensione
• I fixed point combinator sono un'infinita' numerabile!
• Esempio di riduttore automatico per il lambda calcolo. Provare per esempio

  2 = \f x -> f (f x)

  3 = \f x -> f (f (f x))

  add = \m.\n.\f.\x.(n f)((m f) x)

  add 2 3

• Home del compilatore haskell di Glasgow

Esame:

L'esame sara' basato su un breve orale (riguardante gli argomenti discussi nel corso), durante il quale potro' chiedere di scrivere codice usando un linguaggio di programmazione funzionale a scelta dello studente. Alternativamente, gli studenti che lo desiderano potranno decidere di presentare un piccolo progetto, basando l'esame su una discussione del progetto stesso. In questo caso, devono contattarmi via email prima di cominciare lo sviluppo del progetto.

Ho arbitrariamente fissato tre date peg gli appelli di esame, il 2 Febbraio, il 10 Giugno ed il 5 Settembre; gli studenti che intendessero sostenere l'esame in altri giorni possono comunque farlo; devono solo contattarmi per fissare appelli di esame in date diverse da quelle gia' proposte.