Personal tools

Programare functionala

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (small fix)
 
(13 intermediate revisions by one user not shown)
Line 7: Line 7:
 
<br>
 
<br>
 
'''O viziune rezumat asupra lambda calculului'''.
 
'''O viziune rezumat asupra lambda calculului'''.
(Nota: link-urile rosii sunt pagini inca nescrise)
 
 
 
<br>
 
<br>
   
Un limbaj de programare are la baza functionarii sale un model de calcul. Altfel spus cand programam niste calcule intr-un limbaj de programare undeva, ''la susbsol'' :) niste valori sunt prinse intr-un joc al combinarii lor cu ajutorul unor operatii. Aceste operatii impreuna cu multimile de valori formeaza niste structuri algebrice (aici putem cita grupuri, corpuri, inele de numere intregi reale etc.) O caracteristica suplimentara a acestor calcule este ca ele se fac in ordinea aplicarii operatiilor.
+
Un limbaj de programare are la baza functionarii sale un [[model de calcul]]. Altfel spus cand programam niste calcule intr-un limbaj de programare undeva, ''la subsol'' :) niste valori sunt prinse intr-un joc al combinarii lor cu ajutorul unor operatii. Aceste operatii impreuna cu multimile de valori formeaza niste [[structuri algebrice]] (aici putem cita grupuri, corpuri, inele de numere intregi reale etc.) O caracteristica suplimentara a acestor calcule este ca ele se fac in ordinea aplicarii operatiilor.
 
<br>
 
<br>
   
 
Bun, dar prin ce este deosebita programarea functionala ?
 
Bun, dar prin ce este deosebita programarea functionala ?
Raspunsul este: Foloseste un model de calcul, (care are o intreaga teorie dezvoltata despre el - e teoria lambda calcul, vedeti ''[[Ce este lambda calculul ?]]'') care nu se bazeaza pe o multime de ''numere'' ci pe o multime de ''functii'' (adesea anonime - se numesc [[abstractii]] ) scrise in asa-numita lambda notatie si pe operatii cu ele. Acestor formule (lambada expresii) li se mai spune si lambada-termi.
+
Raspunsul este: Foloseste un model de calcul, (care are o intreaga teorie dezvoltata despre el - e teoria lambda calculului, vedeti ''[[Ce este lambda calculul ?]]'') care nu se bazeaza pe o multime de ''numere'' ci pe o multime de ''functii'' (adesea anonime - se numesc [[abstractii]] ) scrise in asa-numita [[lambda notatie]] si pe operatii cu ele. Acestor formule (lambda expresii) li se mai spune si lambda-termi.
 
<br>
 
<br>
   
 
Ce calitati are aceasta multime de lambda termi ?
 
Ce calitati are aceasta multime de lambda termi ?
- Poate manipula cu aceeasi usurinta si numere, valori logice, perechi, n-uple cat si functii. (De fapt manipuleaza numai functii dar un subset de functii se comporta izomorf cu multimea numerelor inzestrata cu operatii. Alt subset de functii se comporta izomorf cu multimea valorilor booleene inzestrata cu operatii logice. Alte lambda-expresii simuleaza functionarea n-uplelor. s.a.m.d)
+
- Poate manipula cu aceeasi usurinta si numere, valori logice, perechi, n-uple cat si functii. (De fapt manipuleaza numai functii dar un subset de functii se comporta identic adica izomorf cu multimea numerelor inzestrata cu operatii. Alt subset de functii se comporta izomorf cu multimea valorilor booleene inzestrata cu operatii logice. Alte lambda-expresii simuleaza functionarea n-uplelor. s.a.m.d)
De fapt manipuleaza numai lambda expresii. In final noi insa putem obtine si folosi limbaje functionale (cum este Haskell) care ne dau acea senzatie a usurintei cu care exprima si manipuleaza si functii si n-uple si valori.
+
De fapt teoria manipuleaza numai lambda expresii si variabile. In final noi insa putem obtine si folosi limbaje functionale (cum este Haskell) care ne dau acea senzatie a usurintei cu care exprima si manipuleaza si functii si n-uple si valori si alte structuri de date.
   
 
Cum putem scrie succesiuni de calcule ? Sunt ele succesiuni de expresii separate ca de obicei prin egal ?
 
Cum putem scrie succesiuni de calcule ? Sunt ele succesiuni de expresii separate ca de obicei prin egal ?
- Da. Se scriu asemenea succesiuni de calcule in lambda calcul. Au insa niste reguli speciale de a transforma o formula in alta: alfa-conversia, beta-conversia, eta-conversia. Daca simplificam formulele (regulile actionand numai intr-un singu sens, de la formula complicata la cea simpla - sa zicem ;) ) atunci regulile se numesc reduceri. (beta reducere, eta reducere).
+
- Da. Se scriu asemenea succesiuni de calcule in lambda calcul. Au insa niste reguli speciale de a transforma o formula in alta: alfa-conversia, beta-conversia, eta-conversia. Daca simplificam formulele (regulile actionand numai intr-un singur sens, de la formula complicata la cea simpla - sa zicem ;) ) atunci regulile se numesc [[reduceri]]. ([[beta reducere]], [[eta reducere]]). Nu exista [[alfa reducere]], alfa conversia schimband o formula intr-una similara, cu alte nume de variabile. Deci nu se poate spune care e mai simpla si in ce sens se face reducerea.
 
- Egalul este de fapt o echivalenta intre formule care pastreaza neschimbata functia asociata (semantica formulei - daca vreti). Calculele constau in succesiuni de alfa, beta si /sau eta conversii intre formule echivalente separate prin semnul egal. Asa cum egalitatea expresiilor aritmetice (in aritmetica intregilor de exemplu) pastreaza neafectata valoarea expresiei adusa pe rand la alte forme, la fel , in lambda calcul, echivalenta de formule (lambda termi) pastreaza neschimbata functia denotata de acestia. Dar demonstratia acestui fapt nu este triviala.
 
- Egalul este de fapt o echivalenta intre formule care pastreaza neschimbata functia asociata (semantica formulei - daca vreti). Calculele constau in succesiuni de alfa, beta si /sau eta conversii intre formule echivalente separate prin semnul egal. Asa cum egalitatea expresiilor aritmetice (in aritmetica intregilor de exemplu) pastreaza neafectata valoarea expresiei adusa pe rand la alte forme, la fel , in lambda calcul, echivalenta de formule (lambda termi) pastreaza neschimbata functia denotata de acestia. Dar demonstratia acestui fapt nu este triviala.
   
 
Cum sa ne imaginam universul lambda termilor ?
 
Cum sa ne imaginam universul lambda termilor ?
 
- Ca un univers de notatii pentru functii. Cititi materiale despre sintaxa lambda expresiilor.
 
- Ca un univers de notatii pentru functii. Cititi materiale despre sintaxa lambda expresiilor.
 
   
   
Line 36: Line 33:
 
1.[http://www.math.uaic.ro/~gonti/Cursuri/ProgramareFunctionala/ProgrFunct.pdf Nou e-book pe NET:] Gontineac Mihai, ''Programare Functionala'' O introducere utilizand limbajul Haskell - Ed. Alexandru Myller, Iasi a avut candva (pe dienai.ro) o serie de capitole. Acum (oct 2008) este gazduit [http://www.math.uaic.ro/~gonti/Cursuri/ProgramareFunctionala/ProgrFunct.pdf aici datorita domnului profesor Mihai Gontineac] , caruia ii multumim pe aceasta cale. (Atat lui cat si editorului de la Editura Alexandru Myller, Iasi.)
 
1.[http://www.math.uaic.ro/~gonti/Cursuri/ProgramareFunctionala/ProgrFunct.pdf Nou e-book pe NET:] Gontineac Mihai, ''Programare Functionala'' O introducere utilizand limbajul Haskell - Ed. Alexandru Myller, Iasi a avut candva (pe dienai.ro) o serie de capitole. Acum (oct 2008) este gazduit [http://www.math.uaic.ro/~gonti/Cursuri/ProgramareFunctionala/ProgrFunct.pdf aici datorita domnului profesor Mihai Gontineac] , caruia ii multumim pe aceasta cale. (Atat lui cat si editorului de la Editura Alexandru Myller, Iasi.)
   
2.Gordon Mike, ''Introduction to Functional Programming'' care ar trebui sa fie disponibila in format pdf [http://www.cl.cam.ac.uk/users/mjcg undeva pe aici
+
2.Gordon Mike, ''Introduction to Functional Programming'' care ar trebui sa fie disponibila in format pdf:
- link extern] Sau incercati aici: [http://www.scribd.com/doc/221707/Introduction-to-Functional-Programming-Lambda-Calculus Introduction-to-Functional-Programming]
+
*[http://www.haskell.org/wikiupload/a/a5/Notes_Functional_programming.pdf Cea mai scurta versiune a fisierului.] Recomandata !.
  +
*[http://www.haskell.org/wikiupload/2/2a/MikeGordon.pdf Ori pe Haskell.org]
  +
*[http://www.cl.cam.ac.uk/users/mjcg Candva Prof. M.Gordon a avut o copie si in acest site (link extern).]
  +
  +
O traducere a capitolului intai au incercat sa faca - si au reusit in limita conditiilor existente - Stefania Ifrim si Hedviga Hurjui, din anul III, Informatica, de la Univ. din Bacau. Sub rezerva unor corecturi care ar (putea) fi necesare v-o oferim aici:
  +
*la [http://www.haskell.org/wikiupload/a/a4/Capitolul_1_byMike_Gordon_translated_draft.pdf <Download> Traducere a capitolului 1]. Oferita asa cum este. Simtiti-va liberi s-o corectati acolo unde exprimarea nu e cea mai fericita.
  +
'''12 oct 2009:''' Am inceput revizuirea traducerii cursului Profesorului M. Gordon. Primele doua pagini sunt [http://www.haskell.org/wikiupload/7/74/Capitolul_1_-_v0.2_Mike_Gordon_pg_1-2.pdf aici]. Vor urma altele.
   
 
3.Hudak Paul, ''Conception, Evolution and, Application of Functional Programming Languages'' ACM Computing Surveys, vol 21, no 3 , Sept 1989 - disponibila in format [http://www.cs.berkeley.edu/~jcondit/pl-prelim/hudak89functional.pdf pdf].
 
3.Hudak Paul, ''Conception, Evolution and, Application of Functional Programming Languages'' ACM Computing Surveys, vol 21, no 3 , Sept 1989 - disponibila in format [http://www.cs.berkeley.edu/~jcondit/pl-prelim/hudak89functional.pdf pdf].
Line 44: Line 41:
   
 
5.Hughes John ''Why Functional Programming Matters'' Comput. J. 32(2): 98-107 (1989) [http://www.cs.chalmers.se/~rjmh/Papers/whyfp.pdf download pdf ]
 
5.Hughes John ''Why Functional Programming Matters'' Comput. J. 32(2): 98-107 (1989) [http://www.cs.chalmers.se/~rjmh/Papers/whyfp.pdf download pdf ]
  +
  +
6. [http://www.cs.uiowa.edu/~slonnegr/plf/Book/Chapter5.pdf Capitolul al V-lea.] din:
  +
Slonneger, Kenneth.
  +
Formal syntax and semantics of programming languages: a laboratory
  +
based approach / Kenneth Slonneger, Barry L. Kurtz.
  +
p.cm.
  +
Includes bibliographical references and index.
  +
ISBN 0-201-65697-3
  +
1.Programming languages (Electronic computers)--Syntax.
  +
2.Programming languages (Electronic computers)--Semantics.
  +
I. Kurtz, Barry L. II. Title.
  +
QA76.7.S59 1995
  +
005.13'1--dc20
  +
[http://www.cs.uiowa.edu/~slonnegr/plf/Book/ Poate fi luat si de pe pagina web a volumului, de aici.] In acest capitol al V-lea gasiti o introducere bunisoara in lambda calcul.
  +
  +
   
 
----
 
----
Line 49: Line 62:
 
'''Ordinea de studiu a bibliografiei: '''
 
'''Ordinea de studiu a bibliografiei: '''
   
3 (recomandata, prima, e o introducere) - EN
+
3 (Prima parte recomandata , este o introducere) - EN
   
2 (cursul, partea principala dar nu suficienta pentru a trece examenul) - EN
+
2 (Cursul, partea principala dar nu suficienta pentru a trece examenul) - EN
   
4 (ultima parte, tehnici avansate de lucru cu fold-uri) -EN
+
4 (Ultima parte, tehnici avansate de lucru cu fold-uri) -EN
   
1 (ACUM ar trebui s-o gasiti, este lectura complementara,) -RO *
+
1 (Acum ar trebui s-o gasiti, este o lectura complementara, de asemenea cei care nu stiu bine limba engleza si studentii de la IFR trebuie s-o aiba in vedere.) -RO *
   
5 (de citit ”Just for fun with Haskell”). - EN
+
5 (De citit ”Just for fun with Haskell”). - EN
  +
  +
6 Un capitol alternativ care prezinta tot o introducere in lambda calcul. Se poate citi in paralel cu 2.
  +
  +
----
  +
Recapitulare rapida: Puteti urmari prezentarea a III-a din seria de prezentari .ppt ?
  +
  +
L03-LambdaCalculus.pdf<br>19-Sep-2006 11:47<br>97K<br>
  +
<br>[http://csg.csail.mit.edu/6.827/handouts/L03-LambdaCalculus.ppt] <- Click aici ca sa vedeti prezentarea.
  +
  +
Daca da, si tot ce este acolo vi se pare familiar, aveti sanse reale la o nota de trecere. ;)
  +
----
  +
Nota: cuvintele gri soarece sunt link-uri catre pagini inexistente sau care vor fi
  +
adaugate ulterior. Nu dati click pe ele. Este inutil deocamdata.
  +
Cuvintele rosii sunt link-uri catre pagini active.
 
----
 
----
 
Pagina indexata la indexul [[Category:Ro]] [http://www.haskell.org/haskellwiki/Category:Ro Categories:Ro]
 
Pagina indexata la indexul [[Category:Ro]] [http://www.haskell.org/haskellwiki/Category:Ro Categories:Ro]

Latest revision as of 16:18, 13 March 2011

Haskell -Programarea functională

Programarea functionala (en. Functional programming - vedeti si in Enciclopedia Wikipedia )
sau
O viziune rezumat asupra lambda calculului.

Un limbaj de programare are la baza functionarii sale un model de calcul. Altfel spus cand programam niste calcule intr-un limbaj de programare undeva, la subsol :) niste valori sunt prinse intr-un joc al combinarii lor cu ajutorul unor operatii. Aceste operatii impreuna cu multimile de valori formeaza niste structuri algebrice (aici putem cita grupuri, corpuri, inele de numere intregi reale etc.) O caracteristica suplimentara a acestor calcule este ca ele se fac in ordinea aplicarii operatiilor.

Bun, dar prin ce este deosebita programarea functionala ? Raspunsul este: Foloseste un model de calcul, (care are o intreaga teorie dezvoltata despre el - e teoria lambda calculului, vedeti Ce este lambda calculul ?) care nu se bazeaza pe o multime de numere ci pe o multime de functii (adesea anonime - se numesc abstractii ) scrise in asa-numita lambda notatie si pe operatii cu ele. Acestor formule (lambda expresii) li se mai spune si lambda-termi.

Ce calitati are aceasta multime de lambda termi ? - Poate manipula cu aceeasi usurinta si numere, valori logice, perechi, n-uple cat si functii. (De fapt manipuleaza numai functii dar un subset de functii se comporta identic adica izomorf cu multimea numerelor inzestrata cu operatii. Alt subset de functii se comporta izomorf cu multimea valorilor booleene inzestrata cu operatii logice. Alte lambda-expresii simuleaza functionarea n-uplelor. s.a.m.d) De fapt teoria manipuleaza numai lambda expresii si variabile. In final noi insa putem obtine si folosi limbaje functionale (cum este Haskell) care ne dau acea senzatie a usurintei cu care exprima si manipuleaza si functii si n-uple si valori si alte structuri de date.

Cum putem scrie succesiuni de calcule ? Sunt ele succesiuni de expresii separate ca de obicei prin egal ? - Da. Se scriu asemenea succesiuni de calcule in lambda calcul. Au insa niste reguli speciale de a transforma o formula in alta: alfa-conversia, beta-conversia, eta-conversia. Daca simplificam formulele (regulile actionand numai intr-un singur sens, de la formula complicata la cea simpla - sa zicem ;) ) atunci regulile se numesc reduceri. (beta reducere, eta reducere). Nu exista alfa reducere, alfa conversia schimband o formula intr-una similara, cu alte nume de variabile. Deci nu se poate spune care e mai simpla si in ce sens se face reducerea. - Egalul este de fapt o echivalenta intre formule care pastreaza neschimbata functia asociata (semantica formulei - daca vreti). Calculele constau in succesiuni de alfa, beta si /sau eta conversii intre formule echivalente separate prin semnul egal. Asa cum egalitatea expresiilor aritmetice (in aritmetica intregilor de exemplu) pastreaza neafectata valoarea expresiei adusa pe rand la alte forme, la fel , in lambda calcul, echivalenta de formule (lambda termi) pastreaza neschimbata functia denotata de acestia. Dar demonstratia acestui fapt nu este triviala.

Cum sa ne imaginam universul lambda termilor ? - Ca un univers de notatii pentru functii. Cititi materiale despre sintaxa lambda expresiilor.


Bibliografie minimala, in ordine alfabetică


1.Nou e-book pe NET: Gontineac Mihai, Programare Functionala O introducere utilizand limbajul Haskell - Ed. Alexandru Myller, Iasi a avut candva (pe dienai.ro) o serie de capitole. Acum (oct 2008) este gazduit aici datorita domnului profesor Mihai Gontineac , caruia ii multumim pe aceasta cale. (Atat lui cat si editorului de la Editura Alexandru Myller, Iasi.)

2.Gordon Mike, Introduction to Functional Programming care ar trebui sa fie disponibila in format pdf:

O traducere a capitolului intai au incercat sa faca - si au reusit in limita conditiilor existente - Stefania Ifrim si Hedviga Hurjui, din anul III, Informatica, de la Univ. din Bacau. Sub rezerva unor corecturi care ar (putea) fi necesare v-o oferim aici:

12 oct 2009: Am inceput revizuirea traducerii cursului Profesorului M. Gordon. Primele doua pagini sunt aici. Vor urma altele.

3.Hudak Paul, Conception, Evolution and, Application of Functional Programming Languages ACM Computing Surveys, vol 21, no 3 , Sept 1989 - disponibila in format pdf.

4.Hutton Graham, (link reactualizat) A tutorial on the universality and expressiveness of fold . J.F.P 1(1)-000 January 1993 - Cambridge Univ. Press

5.Hughes John Why Functional Programming Matters Comput. J. 32(2): 98-107 (1989) download pdf

6. Capitolul al V-lea. din:

   Slonneger, Kenneth.
   Formal syntax and semantics of programming languages: a laboratory
   based approach / Kenneth Slonneger, Barry L. Kurtz.
   p.cm.
   Includes bibliographical references and index.
   ISBN 0-201-65697-3
   1.Programming languages (Electronic computers)--Syntax.
   2.Programming languages (Electronic computers)--Semantics.
   I. Kurtz, Barry L. II. Title.
   QA76.7.S59 1995
   005.13'1--dc20

Poate fi luat si de pe pagina web a volumului, de aici. In acest capitol al V-lea gasiti o introducere bunisoara in lambda calcul.



Ordinea de studiu a bibliografiei:

3 (Prima parte recomandata , este o introducere) - EN

2 (Cursul, partea principala dar nu suficienta pentru a trece examenul) - EN

4 (Ultima parte, tehnici avansate de lucru cu fold-uri) -EN

1 (Acum ar trebui s-o gasiti, este o lectura complementara, de asemenea cei care nu stiu bine limba engleza si studentii de la IFR trebuie s-o aiba in vedere.) -RO *

5 (De citit ”Just for fun with Haskell”). - EN

6 Un capitol alternativ care prezinta tot o introducere in lambda calcul. Se poate citi in paralel cu 2.


Recapitulare rapida: Puteti urmari prezentarea a III-a din seria de prezentari .ppt ?

L03-LambdaCalculus.pdf
19-Sep-2006 11:47
97K

[1] <- Click aici ca sa vedeti prezentarea.

Daca da, si tot ce este acolo vi se pare familiar, aveti sanse reale la o nota de trecere. ;)


Nota: cuvintele gri soarece sunt link-uri catre pagini inexistente sau care vor fi adaugate ulterior. Nu dati click pe ele. Este inutil deocamdata. Cuvintele rosii sunt link-uri catre pagini active.


Pagina indexata la indexul Categories:Ro


<= Inapoi la pagina principala Ro/Haskell.

<- Inapoi la inceputul paginii 'Intrebarile incepatorului Ro/Haskell'.