Funcii i aritmetic [611453]

C1
Func]ii [i aritmetic\
Despre: c=teva `ntreb\ri pe care vi le pune]i atunci c=nd aborda]i un
nou limbaj, tipurile de date (arhi)cunoscute din alte limbaje, Tipurile
compuse, liste [i perechi, operatorii (opera]iile), Func]iile, func]ia
increment, Rularea unui program, variabilele folosite la signaturile
func]iilor [i semnul ->
R\spundem `n acest capitol la c=teva `ntreb\ri pe care vi le pune]i
atunci c=nd aborda]i un nou limbaj. Haskell 98 este un limbaj func]
ional pur, dar `n care se poate programna [i `n stil imperativ (vom
vedea c\ se folose[te o no]iune care a f\cut mult\ v=lv\ `n lumea
matematicienilor, monada – de fapt o anumit\ structur\ algebric\). ~n
Haskell 98 exist\ de asemenea o serie de no]iuni specifice program\rii
orientate obiect cum ar fi clas\, instan]\ a unei clase etc. Func]iile,
vom vedea, sunt polimorfice. Se pot descrie u[or de tot liste [i arbori,
reuniuni de tipuri ba chiar mul]imi ordonate [i liste infinite. (Interesant,
nu-i a[a ?) {i totul se scrie rapid [i compact (un algoritm Quicksort
`ncape `n doar patru-cinci r=nduri de program !) [i f\r\ aglomerarea
Securizarea sistemelor on-line (H6) – 10 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

aceea de paranteze cu care ne-au for]at s\ ne obi[nuim limbaje ca
Lisp (poreclit de unii "Limbajul InSuportabilelor Paranteze") sau ML.
Toate aceste concepte le vom prezenta r=nd pe r=nd, r\spunz=nd
una c=te una la ni[te `ntreb\ri pe care [i le pune cel care `nva]\ un
limbaj de programare. ~ncepem cu cele mai simple lucruri, cum ar fi
`ntrebarea dint=i:
– Cum se scriu `n Haskell tipurile de date (arhi)cunoscute din alte
limbaje: `ntregii, numerele reale [i alte tipuri comune ?
R\spunsurile vor fi detaliate, fiecare subcapitol dintr-un capitol fiind
centrat unei `ntreb\ri sau trat=nd, exhaustiv ori uneori tangen]ial, c=te
un subiect, caz `n care subiectul este ulterior reluat `ntr-un alt capitol.
Subiectul este anun]at de titlul subcapitolului `n cauz\.
De exemplu, `n capitolul I vom r\spunde printre altele la `ntreb\ri cum
ar fi :
– Cum se scriu `n Haskell operatorii ?
– Cum se scrie o func]ie simpl\ ?
– Cum se ruleaz\ un program ?
Ulterior vom trece la o serie de exemple, scriind mai `nt=i simple func]ii
`n Haskell, [i trec=nd gradat la exemple mai complicate. ~n primul
capitol ne vom ocupa printre altele de ni[te exemple care ilustreaz\:
– Felul cum se scriu func]iile
– Func]ia increment
– Func]ia factorial
Vom explica [i cum ve]i rula aceste exemple pe computerul
dumneavoastr\ dotat cu sistem de operare Linux. La realizarea
acestei c\r]i am folosit Mandrake Linux 8.2 (iar ulterior am trecut la
Mandrake Linux 10). Pute]i folosi orice distribu]ie cu condi]ia s\ ave]i
Securizarea sistemelor on-line (H6) – 11 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

inclus `n distribu]ie interpretorul Hugs sau s\-l instala]i ulterior. Hugs
este disponibil at=t ca arhiv\ zip c=t [i ca pachet .rpm. Teoretic
vorbind, aceste exemple pot fi rulate [i pe o ma[in\ Windows pentru
care de]ine]i software-ul necesar, o implementare de Haskell aliniat\
la standardul Haskell 98. Utilizatorii unor versiuni mai vechi sunt invita]
i s\ treac\ la Haskell 98, versiunile mai vechi fiind actualmente dep\-
[ite.
1.1. Tipurile Integer, Bool, Char [i altele; Tipurile compuse, liste [i
perechi
Atunci c=nd `ncepem `nv\]area unui limbaj, deoarece limbajul este
ceva destinat pentru a programa un calculator s\ prelucreze ni[te
date, unul dintre primele lucruri care ne-ar interesa este ce fel de date
putem prelucra cu acel limbaj [i cum se descriu ele. De obicei ne
intrereseaz\ s\ prelucr\m date din ni[te tipuri clasice: `ntregii,
numerele reale, valorile logice (numite uneori valori booleene),
simbolurile tipografice cunoscute sub denumitrea de "caractere" [i
citatele `ntre ghilimele, numite stringuri. Iat\ cum se numesc aceste
mul]imi de date – tipurile citate mai sus, `n Haskell 98:
Numerele `ntregi se numesc Integer sau Int.
Numerele reale sunt de mai multe feluri,re]ine]i deocamdat\ tipul
Float.
Valorile logice, booleene, dou\ la num\r (True [i False) formeaz\
tipul Bool.
Caracterele tipografice sunt elemente din tipul (care include [i
simbolurile), Char.
Securizarea sistemelor on-line (H6) – 12 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

Stringurile sunt de fapt liste de caractere iar tipul string se noteaz\ `n
consecin]\ ca un tip compus: [Char]. Parantezele p\trate
avertizeaz\ c\ este vorba de list\ de elemente de tipul descris `n
parantez\, ac]ion=nd deci ca un constructor de tipuri (cam cum era
perechea RECORD … END `n Pascal [i Oberon numai c\ aici se
declar\ liste nu structuri).
Nota]i [i faptul c\ `n biblioteca ce se `ncarc\ la pornirea interpretorului
(pe care v-o pute]i imagina deocamdat\ ca un fel de <stdio.h> din C,
cu toate c\ `n realitate ea ofer\ mult mai multe lucruri), bibliotec\
numit\ "Standard Prelude" sau mai pe scurt "Prelude" ve]i g\si [i alte
tipuri fie ele simple fie veritabile clase . V\ invit\m s\ le descoperi]i.
C\uta]i cuvinte ca Rational, Double…
Re]ine]i: Cele mai simple tipuri de sunt:
Integer (sau Int), Bool, Float, Char
iar stringurile formeaz\ tipul [Char] denumit cu aliasul String.
Deocamdat\ nu discut\m am\nunte subtile despre tipurile de date .
Acestea `ns\ exist\: de exemplu despre diferen]a `ntre Int [i Integer
programatorii h=r[`i]i v-ar spune c\ func]ile care folosesc pe unul sunt
pu]in mai mai rapide dec=t cele care `l folosesc pe cel\lalt.) Asemenea
diferen]e nu vor fi vizibile `n exemplele noastre. De asemenea, nu
punem `n discu]ie aici pe () un fel de tip cu un singur element notat
chiar cu (). Aceast\ valoare () va fi folosit\ la opera]ii de intrare/ie[ire.
Aten]ie: ~n Haskell numele tipurilor de date `ncep `ntotdeauna cu
Securizarea sistemelor on-line (H6) – 13 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

majuscul\. Regula este valabil\ [i pentru tipurile utilizator, motiv
pentru care ve]i scrie tipul Arbore cu A majuscul\, atunci c=nd ve]i
avea nevoie de un asemenea tip. ~n schimb func]iile se scriu cu
minuscul\, de exemplu o func]ie care incrementeaz\ o variabil\ o ve]i
numi inc. Haskell 98 este un limbaj din categoria celor `n care
minusculele [i majusculele au sens diferit, fiind asemenea din acest
punct de vedere cu limbajele C, Java [i Oberon .
Tipuri compuse: Pe l=ng\ modurile de a construi tipuri definite de
utilizator (pe care le vom prezenta `n alt capitol, Haskell permite
construirea de liste [i perechi. Acelea[i semne (paranteza p\trat\
respectiv cea rotund\ [i virgula care separ\ elementele) se folosesc [i
pentru a construi tipul compus din tipuri mai simple dar [i pentru a
construi valoarea compus\ din valori mai simple.
Exemple:
[Integer] – list\ de `ntregi iar [1,2,3] – lista format\ din 1 2 [i 3
(Char,Int) – perechi de Char [i Int ('b',4) – 'b' [i 4 `mperecheate
Aten]ie: Caracterele se scriu `ntre ghilimele simple, ob]inute cu tasta
de l=ng\ Enter. Cel\lalt fel de ghilimele simple, inverse, ce se ob]in cu
tasta de sub Escape, sunt folosite `n alt scop `n Haskell (la definirea
operatorilor infixa]i). Nu le confunda]i ! Vom remarca [i faptul c\
stringurile admit o scriere dubl\, at=t ca liste de caractere c=t [i ca
texte `ntre ghilimele duble. Ex. ['a','l','f','a'] versus ”alfa”.
Observa]ie: Elementele unei liste pot fi: – oric=t de multe
– dar de acela[i tip, unic
Securizarea sistemelor on-line (H6) – 14 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

Dar:Elementele unei perechi sunt: – exact dou\
– dar pot fi din dou\ tipuri
diferite dinainte precizate
Vom vedea `n capitolele urm\toare c\ utilizatorul poate :
– s\ introduc\ noi tipuri [i noi constructori de tip
– s\ redenumeasc\ tipuri (de exemplu [Char] se poate redenumi
String [i `n acest nume, String chiar se folose[te ca atare)
– s\ inventeze noi feluri de date, definind constructorii de date
(deoarece nu este obligatoriu s\ se folosesc acela[i nume de func]ie
pentru a descrie cum se compun at=t tipurile c=t [i valorile lor – dar
despre acestea discut\m `n alt capitol)
–exist\ [i al]i constructori de tip. Pe l`ng\ (), [] , exemplele
urm\toare `l vor folosi intensiv pe “->” ,cel care construie[te tipul
unei func]ii.
1.2. Operatorii (opera]iile)
Operatorii sunt grupa]i `n 10 clase de prioritate. Un operator, chiar [i
unul definit de utilizator (Da exist\ a[a o posibilitate `n Haskell !)
trebuie plasat `ntr-una din cele 10 clase de prioritate. ~n acest fel,
Haskell poate stabili corect ordinea opera]iilor dintr-o expresie,
indiferent ce operatori sunt implica]i. Unii operatori asociaz\ implicit la
st=nga, al]ii la dreapta. Operatorii infixa]i care au un nume format din
litere apar `n programe cu acest nume `ncadrat de ghilimele simple
inverse (de pe tasta cu semnul tilda). Regula aceasta este valabil\ [i
pentru operatorii defini]i de programator. Dac\ ve]i deschide cu un
editor de text fi[ierul
Securizarea sistemelor on-line (H6) – 15 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

/usr/share/hugs/lib/Prelude.hs (Standard Prelude) ve]i g\si acolo,
deja declara]i, o serie `ntreag\ de operatori. ~i vom comenta imediat
pe cei mai mul]i dintre ei, preciz=nd pentru fiecare printr-o pereche
liter\ – cifr\ dac\ e asociativ la dreapta (R) sau st=nga (L) [i ce nivel
de prioritate are.
Iat\ o mic\ list\ de operatori declara]i `n Standard Prelude :
R9 .
L9 !!
R8 ^ , ^^ , **
L7 * , / , `quot` , `rem` , `div` , `mod` , :% , %
L6 + , –
R5 :
4 ==, /=, <=, <, >=,>, `elem`, `notElem`
R3 &&
R2 ||
L1 >> , >>=
R1 =<<
R0 $, $! , `seq`
Recunoa[te]i imediat aici: pe nivelul 6 sunt adunarea [i sc\derea iar
ace[ti operatori asociaz\ la st=nga. ~n Haskell a+b+c este deci `n]
eles ca (a+b)+c . Pe nivelul 7 g\si]i `nmul]irea, `mp\r]irea [i
operatorii care calculeaz\ c=tul [i restul. Operatorii `div` [i `mod`
sunt similari cu omologii lor din Pascal. div face `mp\r]i-rea `ntreag\ [i
ob]ine c=tul iar mod ob]ine restul.
Remarca]i c\ operatorul care implementeaz\ no]iunea de "diferit" este
Securizarea sistemelor on-line (H6) – 16 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

scris `n Haskell “/=” , spre deosebire de alte limbaje (Pascal, C,
Oberon). Observa]i c\ rela]iile de apartenen]\ care exprim\ no]iuni ca
"a fi element" [i "a nu fi element" au denumiri formate din litere:
`elem` respectiv `notElem`.
Opera]iile logice, conjunc]ia [i disjunc]ia se noteaz\ ca `n C [i le g\si]i
pe nivelele de prioritate 2 [i 3.
Operatorii de pe nivelul 1 servesc la scrierea opera]iilor dintr-o
monad\. Aceste structuri algebrice, monadele, provin din teoria
categoriilor [i se poate lucra (nativ) cu ele `n Haskell 98 deorece
clasele corespunz\toare sunt predefinite `n Prelude. Un exemplu g\si]i
`n capitolul 6. Poate n-a]i [tiut c\, de exemplu, un model de sistem
care face calcule, model `n care calculele dau valori [i modific\ o
memorie (ca atribuirile) se implementeaz\ imediat `n Haskell ca o
monad\.
Nu uita]i c\ Haskell este un limbaj func]ional, care opereaz\ cu func]ii
de la date la rezultate (acestea put=nd fi din tipuri diferite). Un calcul
f\cut de un program este p=n\ la urm\ o asemenea func]ie. Vom
vedea c\ operatorul >>= este compunerea `n succesiune a dou\
calcule. Ceea ce se ob]ine depinde evident de cele dou\ calcule.
Operatorul >>= , (pronun]at "bind") exprim\ doar felul cum se
combin\, cum se succed ele.
. – este compunerea func]iilor
^ – este ridicarea la putere
`quot` – similar\ ca nume cu o func]ie din Lisp
`div` – `mp\r]irea `ntreag\
`mod` – restul dat de `mp\r]irea `ntreag\
+ , – – adunarea [i sc\derea, supra`nc\rcate
Securizarea sistemelor on-line (H6) – 17 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

: – cons, ad\ugarea unui elment `n capul
unei liste
==, /=, <=, <, >=,>- rela]iile, compara]iile, supra`nc\rcate
`elem`, `notElem`- apartenen]a [i neapartenen]a la o list\
(mul]ime)
&& – conjunc]ia
|| – disjunc]ia, (nega]ia se noteaz\ cu not )
>> , >>=- operatori pentru monade
(de obicei `nl\n]uiesc calculele fiind
cumva similari lui ";" din limbajele
imperative. Pot fi redefini]i `n instan]ele
claselor monadice pentru a ob]ine
diverse efecte)
=<< – la fel dar cu operanzii `n ordine inversa
Cu ajutorul lor sunt defini]i [i al]i operatori, de exemplu folosindu-se
operatorul “:” (pronun]at “cons” ca `n Lisp) este definit\ concatenarea
a dou\ liste sau a dou\ stringuri, notat\ cu ++ . Ve]i folosi frecvent
acest operator.
1.3. Func]iile. Exemplul Nr.1, func]ia increment.
Matematicianul care face o declara]ie de func]ie va scrie `nt=i
semn\tura acesteia (adic\ schema de tipuri c\reia func]ia i se
conformeaz\). ~n Haskell ea se nume-[te chiar tipul func]iei, deoarece
"->" este [i el un constructor de tipuri, capabil s\ `mbine dou\ tipuri [i
s\ ob]in\ altul. (Ob]in=ndu-se astfel o "func]ie de la … la…").
Securizarea sistemelor on-line (H6) – 18 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

Exemplu: f : Z -> Z prin rela]ia f(x) = x + 1 se scrie `n
Haskell:
f:: Integer -> Integer
f x= x + 1
Cap1Par3Ex1.hs
Pentru a-l testa, scrie]i acest mic program cu un editor de text :
Cap1Par3Ex1.hs
Pute]i alege orice editor dori]i din cele disponibile (kwrite, gedit,
emacs, xemacs, vi, pico). Salva]i programul sub numele
Cap1Par3Ex1.hs.
C=teva explica]ii sunt aici [i acum necesare:
Alinierea pe vertical\, este extrem de important\. ~n limbaje ca
Pascal, C sau Oberon [i multe altele, un programator putea scrie tot
programul pe un singur r=nd, f\r\ ca aceasta s\ deranjeze
compilatorul sau interpretorul. Acest lucru nu se poate face `n Haskell
deoarece Haskell, pentru a elimina acele paranteze care ne cople[esc
`n Lisp sau ML, folose[te un concept revolu]ionar: sintaxa
bidimensional\. Iat\ ce trebuie s\ [ti]i deocamdat\ despre ea:
Trecerea pe r=ndul urm\tor, dar mai la st=nga dec=t pe precedentul
Securizarea sistemelor on-line (H6) – 19 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

r=nd echivaleaz\ cu o `nchidere de structur\ sau parantez\. E ca [i
cum s-ar pune automat `n Lisp parantez\ `nchis\. (Re]ine]i c\ Haskell
este un limbaj cu sintax\ bidimensional\!). Aceast\ aranjare `n pagin\
se nume[te cu termenul englezesc “layout”. Este chiar posibil ca
interpretorul s\ semnaleze prezen]a incorect\ a unei paranteze pe
care dumneavoastr\ n-a]i scris-o, din cauza unei asemenea erori de
layout. ~n asemenea cazuri verifica]i alinierea pe vertical\ [i ave]i grij\
ca nu cumva unele r=nduri s\ `nceap\ mult prea din st=nga. Pare un
dezavantaj dar lipsa acelor paranteze din Lisp merit\ pre]ul acesta,
dup\ p\rerea mea. Practic, este esen]ial s\ alinia]i corect pe vertical\
tot ce este `n interiorul unei substructuri sintactice, sau, dac\ sunte]i
`ncep\tor, s\ p\stra]i alinierile pe vertical\ din exemplele nostre [i s\
programa]i cam `n acela[i stil (sau unul mai bun). Nota]i [i faptul c\,
urmare a sintaxei bidimensionale, `n Haskell este important s\ pune]i
spa]iile `n anumite locuri. Un tab este considerat egal cu 8 spa]ii, motiv
pentru care trecerea la un editor de text pentru care TAB-ul are alt
num\r de spa]ii poate creea unele probleme. Sfatul meu pentru
`ncep\tori: Lucra]i cu tasta SPACE nu cu tasta TAB c=nd ave]i nevoie
de spa]ii.
Extensia fi[ierelor con]in=nd surse de program Haskell este .hs . Mai
exist\ o extensie .lhs pentru "literate – Haskell" acele texte de lucr\ri `n
care totul este comentariu cu excep]ia liniilor care `ncep cu > [i
formeaz\ ele `nsele programul. (~n Cap 6. se folose[te acest stil de
scriere.)
Securizarea sistemelor on-line (H6) – 20 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006

Pornirea interpretorului Hugs.
Hugs este numele interpretorului Haskell 98 livrat `mpreun\ cu
distribu]iile de Linux. Nu este `ns\ inclus `n toate distribu]iile oferite
spre download. Eu l-am g\sit inclus `n distribu]iile Mandrake 8.2 [i
Mandrake 10. ~l puteti lansa cu una din comenzile:
hugs
hugs <numefi[ier>
hugs “<numefi[ier>”
Ghilimele sunt necesare dac\ numele de fi[ier con]ine spa]ii.
Observati `n imaginea de mai sus c\ fiind lansat cu comanda
hugs Cap1Par3Ex1.hs
interpretorul deschide [i citeste programe din dou\ fisiere: Standard
Prelude [i fi-[ierul dat de noi `n linia de comand\.
~n paragraful urm\tor vom explica cum s\ rula]i exemplele incluse `n
aceast\ carte.
Securizarea sistemelor on-line (H6) – 21 – 13 Helv-DRAFT Dan Popa, 5 nov. 2006