Proposte
Nell’a.a. 2003 èstato tenuto, in forma sperimentale, il solo
modulo Linguaggi Funzionali: Struttura di 3 crediti. I seminari
consigliati per tale corso sono quelli indicati da: Seminario 03-n.
L’indice n è progressivo ed è attribuito secondo la rilevanza per il corso
tenuto: più è basso l’indice, maggiore è la rilevanza per la discussione
finale.
APPLICAZIONI
Un sistema
operativo, O.S., e' una collezione di procedure per la gestione della
"bare machine" di un calcolatore e un linguaggio per utilizzare
alcune di tali procedure.La gestione include la comunicazione con le
periferiche, la definizione della struttura e la relativa gestione del file
system, la definizione della struttura dei processi e la relativa gestione
dei processi. Queste considerazioni ci conducono ad una visione di un
O.S. come un sistema altamente strutturato in una gerarchia di sottosistemi
con differenti visibilità l'uno dell'altro. A partire dall'interfaccia con la
"bare machine" che fornisce un insieme di primitive, un O.S.
contiene procedure per la definizione, implementazione e gestione di nuove
strutture che formeranno la nuova base per realizzare nuovi componenti del
O.S. stesso.Utilizzare un linguaggio funzionale per descrivere ad ogni
passo: "definizione, implementazione, gestione" significa
utilizzare i benefici della programmazione funzionale quali:
1.
tipi
con la possibilita' di definire in modo preciso la segnatura di ogni
operazione introdotta
2.
tipi
astratti e concreti con la possibilita' di esprimere nuove strutture in modo
formale (e senza condizionamenti legati alle strutture dati del linguaggio)
3.
ordine
superiore con la possibilita' di rimandare all'uso di valori funzionali il
compito di non avere ragioni per la scelta di una particolare
rappresentazione dei valori che nondimeno dobbiamo trattare
4.
trasparenza
con la possibilita' di esaminare componenti e comprenderne le funzionalita
senza la necessita' di conoscere il contesto in cui essi saranno utilizzati
5.
metodologie
con la possibilita' di utilizzare tutte le metodologie di programmazione ad
oggi introdotte per sviluppare programmi (inclusa object-oriented con le
dovute considerazioni)
6.
certificabilita'
con la possibilita' di verificare la correttezza di tutto o di parte di quanto
definito.
Seminari
- Seminario1.1 - Definizione di UNIX in un approccio funzionale: interfaccia
con la "bare machine", il file system, i processi. [10]
- Seminario1.2 - Definizione di UNIX in un approccio funzionale: gestione dei
processi, socket [10, 7]
- Seminario 03-1 – Non solo S.O.: Altre applicazioni sono descritte in
[31]
METODOLOGIE
Le classi in
Haskell consentono l'introduzione di funzioni parametriche rispetto a
costruttori di tipo: Ad esempio class zipper f
where fzip:: (a -> b)
-> f a -> bintroduce fzip proprio come una di tali funzioni.
Questa forma di astrazione si chiama funzione politipica, ed è stata studiata
come base per una nuova metodol0gia di programmazione. La nuova metodologia risiede sulla
semplicita' e chiarezza con la quale e' possibile dare forma a "scritture"
usualmente non esprimibili nei linguaggi funzionali. Cio' risulta in
programmi maggiormente strutturati, le cui parti sono facilmente estendibili,
modificabili e certificabili.
Seminari
-
Seminario3 - Moduli: confronto tra ML e Haskell [14]
-
Seminario4.1 - Si presentano la metodologia e i meccanismi proposti (in ML,
Haskell) per il supporto alla programmazione politipica [9,4]
-
Seminario4.2 - Si discute un'applicazione non banale della metodologia nella
scrittura algoritmi genetici [4,11]
ESPRESSIVITÀ e
DICHIARATIVITÀ
Piu' volte
richiamata per giustificarte la presenza di questo o quel meccanismo in un
linguaggio o per giusticare talune differenze tra linguaggi di uno stessa
classe, l'espressività è accettata come una proprietà più intuitiva che
formalmente formulabile. Seminari
- Seminario18 - Significato di espressività: ragionevoli formulazioni [24,30]
-
Seminario 03-10 - Espressività nel linguaggio funzionale [35,30]
- Seminario 03-2 – Gli strumenti quanto aiutano? [32,31]
-
Seminario 03-4 (2 pers.) – ERLAG: Come arricchire espressività per
programmare concorrenza [20]
-
Seminario 03-5 (2 pers.) – NESL: Come arricchire espressività per
programmare parallelismo massiccio [34]
Nata
nell'ambito della verifica di proprieta' e dei sistemi di specifica formali e
di rapida prototipazione, la programmazione equazionale rientra nella classe
della programmazione applicativa. Il seminario discuterà gli aspetti
fondamentali di questo tipo di programmazione focalizzando le differenze con
i linguaggi funzionali.
Seminari
-
Seminario19 – Term Rewriting e Programmazione Equazionale: proprietà e
differenze rispetto alla programmazione funzionale [25]
-
Seminario 03-6 (2 pers.)– Hol: Un linguaggio per funzioni, teorie e
prove [27]
Nata nell'ambito dell'utomatizzazione
dei processi di dimostrazione formale di formule del primo ordine, e basata
su un'interpretazione applicativa di forme semplificate della risoluzione, la
programmazione logica ha meccanismi operazionali e supporta metodologie di
programmazione che la distinguono dall'usuale programmazione funzionale e la
rendono piu' simile alla programmazione equazionale. Il seminario discutera'
gli aspetti fondamentali di questo tipo di programmazione focalizzando le
diffenze con i linguaggi funzionali
Seminari
- Seminario20 – Programmazione Logica: proprietà e differenze con i linguaggi
funzionali [26]
PROGRAMMAZIONE FUNZIONALE con STATO
L'essenza
stessa di linguaggio funzionale da un lato non richiede e dall'altro
impedisce di avere una nozione di stato nella struttura del linguaggio.
Cio' non significa tuttavia, che la programmazione funzionale e' relegata ad
applicazioni che non coinvolgono strutture con stato, infatti e' possibile:
1. esprimere lo stato come un valore funzionale: variabile
imperativa
var x = v ==> let x = \f
-> \n -> (f n) in (x '= v)
where
'= = \n -> \f -> (f n) ----- update
x ==> #x
where # = \x -> x
(\n -> n) ----- fetch
2. ospitare programmazione imperativa (e relative metodologie
di programazione)
x = E; C ==> x '= <E>; <C>
where (;) = \a -> \c -> a . (\x -> c)
(.) = \f
-> \g -> \v -> g(f x) ------ sequenzializzazione
3. programmare con entita' che hanno effetti laterali (I/0,
comunicazione): continuazioni, streams, monadi, programmazione reattiva
- interoperare
con sistemi di programmazione imperativa e con riflessione
Seminari
- Seminario6 - Programmazione imperativa nei linguaggi funzionali:
problemi, applicazioni, soluzioni [17]
-
Seminario7 - Uso delle monadi per incapsulare lo stato: Un approccio
sistematico [16]
-
Seminario8 - Parser basato sulle monadi: descrizione di un'applicazione [8]
-
Seminario9 - Programmazione Event driven: descrizione di un'applicazione per
WEB server. [12]
-
Seminario10 – Interoperabilità: un approccio all'interoperabilita' tra
ambiente Java e Haskell [13]
- Seminario 03-3 – Come emulare un calcolo high order in Java [33]
PROGRAMMAZIONE FUNZIONALE con CONTROLLO
La
dichiarativa' dei linguaggi funzionali conduce ad esprimere le funzioni
calcolate mediante programmi descrittivi anzichè prescrittivi: una forma di
astrazione sul controllo che evita la necessita' di occuparsi, durante la
stesura del programma, di tutti quegli aspetti legati alla
"macchina" e al suo "esecutore", per concentrarsi invece
sul problema per il quale il programma è pensato. Ci sono tuttavia:
1. problemi che hanno una propria
nozione di controllo: fornire una soluzione per questi problemi significa
fornire un programma in grado di trattare anche gli aspetti legati a tale
controllo.
2. sistemi a componenti
etrogenee: operare in tali sistemi puo' richiedere di definire programmi
funzionali in grado di trattare con aspetti di controllo generati da altri
componenti.
Il controllo,
insieme allo stato, rientra in quella classe di programmazione per effetti
laterali che e' alla base della struttura dei linguaggi imperativi, ma
che può essere nei linguaggi funzionali mantenendo le proprieta' di
trasparenza referenziale dei programmi.Seminari
- Seminario11.1 - Programmazione parallela funzionale: problemi e
soluzioni [5,18]
-
Seminario11.2 - Programmazione parallela funzionale: studio di una
soluzione [6]
-
Seminario13 - Programmazione concorrente in Haskell [15]
- Seminario14 - Processi e canali: studio di
una soluzione [1]
- Seminario 03-9 – ERLAG: Un
linguaggio per il coordinamento di processi per reti cellulari [20]
FONDAMENTI
1)
La realizzazione di macchine funzionali ha da sempre coinvolto l'interesse di
molti ricercatori e certamente e' alla base di una piu ampia conoscenza della
struttura di un linguaggio funzionale. Sono numerose le proposte diverse
avanzate e le realizzazioni prodotte, estremamente interessanti sono tuttavia
gli approcci seguiti. Seminari
- Seminario 03.11 – AMBER machine: variante della SECD machine,
ridisegnata a 20 anni di distanza, questa macchina e' basata sulla nozione di
chiusura e contiene meccanismi per supportare meccanismi di moderni linguaggi
funzionali, come grafica e oggetti persistenti. Focalizzeremo lo studio sugli
aspetti relativi alla gestione dell'ambiente [21]
-
Seminario 03-12 – SKIM machine: Una delle prime macchine a riduzione,
basata sui combinatori S-K-I riproposti da Turner come linguaggio intermedio
per compilare linguaggi funzionali [22]
-
Seminario 03-13 – CAM machine: basata su combinatori categoriali,
questa macchina mostra un'altro modo di realizzare macchine a riduzione di
grafo. Macchine a riduzione non richiedono una gestione esplicita
dell'ambiente e tanto meno chiusure, e sono oggi considerate l'approcio
migliore [23]Alcuni di questi approcci si muovono
all'interno di una metodologia formale che giustifica di volta in volta le
scelte operate. Seminari
- Seminario15.1 - Macchine funzionali: uno studio sistematico [2]
-
Seminario15.2 - Macchine funzionali: un progetto [2]2)
Le classi di tipi introdotte in Haskell offrono una sistemazione a molti
differenti problemi: overloading di operatori, stato e controllo
(monadi), metodologie innovative (programmazione monadica,
programmazione politipica). Cosa sono le classi di tipi da un punto di vista
del nucleo di un linguaggio funzionale? Seminari
- Seminario17 - Classi di tipi in Haskell: macroespansione [3]
-
Seminario 03-7 – Tipi e Sottotipi: Sistema dei tipi [28]
-
Seminario 03-8 – Tipi in Haskell: inferenza e implementazione [29]
3)
Il Lambda calcolo fornisce un modello semantico ai linguaggi funzionali, non l'unico,
ma certamente uno dei piu' noti ed espressivi per formalizzare la semantica.
Lo stesso nucleo di un linguaggio funzionale e' Lambda calcolo con termini
tipati, sole alfa e beta riduzioni ed esteso o con assiomi non propri per
naming ricorsivi o con un operatore di punto fisso.
Studiare
le relazioni tra questi formalismi è certamente interessante anche dal punto
di vista dell'espressività. In questo contesto si colloca anche, la relazione
tra termini tipati e operatori di punto fisso esprimibili nel formalismo
stesso. Correlata con tale relazione è la possibilità di
"implementare" Lambda calcolo (non tipato) nel Lambda calcolo
tipato.
Seminari
-
Seminario18 - Implementazione di Lambda calcolo (non tipato con sole alfa e
beta riduzioni) nel nucleo di Haskell (puro o con data domain):
rappresentazione dei termini, alfa e beta riduzione, l'operatore di punto
fisso di Church [19]
References
[1] Breitinger S. and Loogen R. Channel
Structures in the Parallel Functional Eden, 1997, Glaskow FP workshop. (.pdf)
[2] Douence R.
and Fradet P. A systematic Study of Functional Language Implementations, ACM
TOPLAS, 20(2):344-387. (.pdf)
[3] Hall, C.
et al. Type classes in Haskell, 1994, LNCS 788. (.pdf)
[4] Halembeek
J., Comparing approaches to polytypic programming, 1999, Master's thesis,
Utrecht University. (.pdf)
[5] Hammond
K. Parallel Functional Programming: An Introduction, Dep. Comp. Science,
1994, 1th Symp on Paralle Symbolic Comp. (.pdf)
[6] Hammond,
K. et al. Automatic Spark Strategies and Granularity for a Parallel
Functional Language Reducer, 1994, COMPAR, LNCS 854. (.pdf)
[7] Hardin,
T. et al. Functional Runtime Systems within the Lambda-Sigma calculus,
Journal of Functional Programming, 1998, 8(2):131-176. (.pdf)
[8] Hutton G.
and Meijer E. A library of monadic parser combinators, 1996. (.pdf) (http://www.dcs.glasgow.ac.uk/jfp/bibliography/Authors/meijererik.html)
[9] Jeuring,
J. and Jansson, P. Polytypic programming, 1996, LNCS 1129. (.pdf) (http://www.cs.chalmers.se/~patrikj/poly)
[10] Leroy
X., Programmation du Systeme Unix en Caml, 1992, tech. rep. 197, INRIA.
(.pdf)
[11] Mans,
V. Genetic algorithms in Haskell with polytypic programming, 1997, Master's
thesis, Goteborg University. (.pdf)
[12] Meijer,
E. Server side web scripting in Haskell, Journal of Functional Programming,
2000, 10(1):1-18. (.pdf)
[13] Meijer,
E. LAMBADA: Haskell as a better JAVA, Electronic Notes in Theoretical
Computer Science, 2001, 41(1). (.pdf)
[14]
Nicklish, J. An Exploration of Modular Programs, 1996, Glaskow FP workshop.
(.pdf)
[15] Peyton
Jones, S. Concurrent Haskell, 1996, 23th ACM POPL.(.pdf) (http://research.microsoft.com/Users/simonpj)
[16] Peyton
Jones S. and Launchbury, State in Haskell, 1995, J. Lisp and Symbolic
Computation 8(4):293-341. (.pdf)
[17] Peyton
Jones, S.a nd Wadler P. Imperative Functional Programming, 1992, 19thACM
POPL. (.pdf)
[18]
Peterson, J. Parallel Functional Reactive Programming, 2000, Practical
Aspect of Declarative Languages,LNCS 1753. (.pdf) (http://haskell.org/frp)
[19]
Barendregt, H. Functional Programming and Lambda Calculus, 1990,
Handbook of Theoretical Computer Science, vol. A, Elsevier Sc. Pub., 322-363
[20] Armstrong, J et al.. Concurrent Programming in ERLANG, Prentice
Hall (pdf) (http://www.ericsson.se/erlang)
[21] L. Cardelli, The AMBER
machine, Combinators and Functional Programming Languages, 1985, LNCS 242, pp
48-70.
[22] T.J.W. Clarke, P. Gladstone,
C. MacLean and A.C. Norman, SKIM - The S,K,I Reduction Machine, Lisp Conf.,
1980. pp. 128-135
[23] G. Cousineau, P.-L. Curien,
Combinateur Categorique et implementation de language Fonctionnels, 1985,
LNCS 242, pp 85-103
[24] M. Felleisen, On the Expressive
Power of Programming Languages, ESOP conf. 1990, LNCS 432, pp. 134-151.
[25] N.Dershowitz and J-P
Jouannaud, Rewriting Systems, Handbook of TCS - Formal Models and Semantics,
vol. B, 1990, pp. 243-320.
[26] K. Apt, Logic Programming,
Handbook of TCS - Formal Models and Semantics, vol. B, 1990, pp. 493-574.
[27] R.D. Arthan, HOL Formalized:
Language and Overview, Lemma1 Ltd 2002 – DS/FMU/IED/SPC001; issue 2.7.(http://www.lemma-one.com/ProofPower/specs/spc001.pdf)
[28] L. Damas and R. Miner,
Principal Type Schemes for Functional Programs, 9-th ACM POPL, 1982,
207-212.(
http://portal.acm.org)
[29] M. P. Jones, Typing Haskell
in Haskell, Haskell Workshop, 1999 (http://www.haskell.org)
[30] J. C. Mitchell, On
Abstraction and the expressive power of programming languages, J. Science of
Computer Programming, 21, 1993, 141-163.
[31] P. Wadler, An Angry
half-dozen, ACM Sigplan Notices, 33-2, 1998, 25-30
[32] P. Wadler, Why no one uses
functional languages, ACM Sigplan Notices, 33-8, 1998, 23-27
[33] A. Setzer, Java as a
Functional Programming Language, Proc of TYPES 2002, LNCS 2646, 279-298
[34] G.E. Blelloch, NESL: A
Nested Data-Parallel Language – v.3.1, CMU-CS-95-170, 1995 (http://www-2.cs.cmu.edu/~scandal)
[35] J. Hughes, Why Functional
Programming Matters, Computer Journal, 32, 1989, 98-107
|