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
|
