Introducere. Lucrul cu funcții

Mediul de lucru: Interpretorul OCaml

Vom ilustra În felul acesta, vom avea o perspectivă mai bună asupra limbajelor de programare și mai bune deprinderi de a scrie programe.

Vom folosi pentru aceasta limbajul de programare ML. Acesta e un limbaj funcțional: pe scurt, înseamnă că are funcția ca noțiune de bază și poate lucra cu funcții ca entități elementare, la fel ca și cu valori întregi, reale, etc.

Caml este un dialect al limbajului ML, iar OCaml e o implementare care oferă atăt un interpretor cât și un compilator.
Un interpretor poate rula (evalua) fragmente de program (expresii sau instrucțiuni) pe măsură ce ele sunt introduse.
Un compilator transformă programul sursă într-un fișier executabil care poate fi apoi executat de sine stătător.
Putem lansa interpretorul OCaml din linia de comandă (terminal) cu comanda ocaml .

Exemple simple în ML

Evaluarea unor expresii

La promptul # al interpretorului putem în general evalua expresii. Cele mai simple expresii sunt calculele cu numere, scrise în notația obișnuită din matematică. De exemplu, putem introduce 
# 2+3;;
iar interpretorul răspunde: 
- : int = 5
Semnul ;; (dublu punct-virgulă) trebuie introdus pentru a indica sfărșitul expresiei de evaluat. Răspunsul (de după semnul :) indică rezultatul, 5, și tipul acestuia, întreg: int . Spațiile în cadrul expresiei nu contează, putem scrie și 
# 2 + 3 ;;
- : int = 5
Cele două caractere ;; trebuie scrise însă unul după celălalt pentru fi interpretate ca sfârșit al textului de interpretat.

Definirea unor funcții

Funcțiile se definesc simplu, cu o sintaxă (regulă de scriere) apropiată de cea din matematică. Astfel, funcția f : Z → Z, f(x) = x + 3 se scrie în ML: 
let f x = x + 3
Cuvântul cheie let (engl. "fie") introduce o definiție, aici, pentru identificatorul f. Scrierea amintește de exprimarea: fie f dat de expresia ...
Spre deosebire de matematică, la definirea funcției nu se folosesc paranteze în jurul parametrului x. Dacă introducem această definiție, interpretorul răspunde: 
# let f x = x + 3;;
val f : int -> int = <fun>
Interpretorul indică faptul că a fost definit identificatorul f cu o valoare care e o funcție. La stânga săgeții -> e domeniul de definiție al funcției, int, și la dreapta săgeții domeniul de valori, tot int.

Odată definită funcția, ea poate fi folosită (apelată) într-o expresie. Nici aici nu sunt necesare parantezele în jurul argumentului, decât dacă acesta este o expresie complexă: 

# f 1;;
- : int = 4
# f(2+3);;
- : int = 8

Funcții anonime

Notația fun argument -> expresie definește în ML o funcție anonimă. Aceasta este o expresie de tip funcție și poate fi deci folosită în alte expresii. Putem evalua direct 
(fun x -> x + 3) 2;;
- : int = 5
fără a fi nevoie să dăm întâi un nume funcției. Acesta exemplu simplu ilustrează că în limbajul funcțional ML, o funcție (aici fun x -> x + 3) poate fi folosită la fel de simplu ca și orice altă valoare.

Revenind la notația fun, este echivalent să definim let f x = x + 3 sau 

# let f = fun x -> x + 3;;
val f : int -> int = <fun>

Mediul de lucru: editorul Emacs

Odată ce scriem exemple de program, e util să le salvăm pentru a le putea refolosi. Convențional, programele ML se scriu în fișiere text cu extensia .ml . Ele se pot edita cu orice editor de texte (sub Windows, de exemplu Notepad, nu Word care editează fișiere .doc cu formatare specifică). Folosim editorul Emacs, cu un pachet special pentru OCaml (tuareg-mode) care reprezintă programele ML colorate după regulile de sintaxă, și deci mai ușor de citit.

Cănd scriem un fișier program ML, nu e nevoie să încheiem fiecare definiție cu ;; ca în interpretor. E necesar să scriem ;; doar cănd după un șir de definiții scriem o evaluare de expresie, și pentru a separa evaluări succesive de expresii. De exemplu: 

let f x = x + 2
let g x = x - 3
;;
f 2;;
g 1

În Emacs, după ce am scris sau încărcat un fișier ML, cu comanda Ctrl-c Ctrl-b (dacă avem instalat pachetul tuareg-mode) se creează o subfereastră în care interpretorul OCaml e lansat pe programul ML din fereastra curentă. Apoi, la promptul # putem introduce comenzi OCaml (evalua expresii), la fel ca în interpretorul lansat din terminal. Astfel putem alterna între a scrie părti din program, a le interpreta cu Ctrl-c Ctrl-b și a rula diverse evaluări observând rezultatul.

Lucrul cu funcții (continuare)

Funcții de nivel superior (funcționale)

Fie funcția din matematică: iadd: Z×Z → Z, iadd(x, y) = x + y

Varianta cea mai uzuală de a transcrie această funcție într-un program ML este: 

# let iadd x y = x + y;;
val iadd : int -> int -> int = <fun>
Observăm că în tipul funcției, int -> int -> int, săgeata -> apare de două ori, pe cănd în exemplul dinainte apărea o singură dată, în stânga fiind tipul pentru domeniul de definiție, iar în dreapta tipul pentru domeniul de valori.

De fapt, suntem în același caz general: considerănd prima săgeată, la stânga ei e domeniul de definiție al funcției iadd, int, iar în dreapta ei, tipul domeniului de valori, int -> int. Deci, așa cum a fost scrisă, funcția f are un parametru întreg, iar rezultatul este el însuși o funcție, care ia ca parametru un întreg și returnează un întreg.
O astfel de funcție care returnează o funcție sau ia o funcție ca parametru se numește funcție de nivel superior (engl. higher-order function) sau funcțională. Ele sunt un lucru foarte natural în limbajele funcționale, deoarece acestea pot lucra cu funcții ca și cu orice alt tip de valori.

Apelând funcția iadd cu un argument pentru parametrul x, rezultatul iadd x este o funcție de un singur argument y, și anume fun y -> x + y, în care x nu mai e parametru, ci o valoare cunoscută (legată) furnizată deja (la apelul iadd x).

Alternativa: lucrul cu perechi

Putem defini o funcție de adunare și în alt fel: 
let iaddp (x, y) = x + y;;
val iaddp : int * int -> int = <fun>
Am definit de fapt o funcție cu un singur parametru de tip pereche de întregi: după cum indică și interpretorul, domeniul de definiție este int * int, adică produsul cartezian Z×Z . Deși mai apropiată de formularea matematică inițială, în scrierea programelor se folosesc deobicei funcții de nivel înalt, în afară de cazul când specificul problemei necesită lucrul cu perechi, triplete, etc.

Operatorii sunt funcții!

Operatorii înșiși sunt de fapt funcții, cu scrierea uzuală între operanzi (infix), nu la început (prefix) ca în apelul de funcție. În loc de 2 + 3 putem scrie 
(+) 2 3;;
- : int = 5
E nevoie de paranteze pentru (+), altfel expresia +2 3 ar fi incorectă (două valori alăturate, ca un apel de funcție, dar +2 e un număr, nu o funcție).
Mai mult, dacă furnizăm interpretorului doar 
# (+) ;;
- : int -> int -> int = <fun>
acesta ne spune că (+) e o funcție care ia un parametru int și produce ca rezultat o funcție (int -> int), care la răndul ei ia un parametru întreg și produce un rezultat întreg. De fapt, funcția (+) este identică cu funcția iadd definită înainte. Putem scrie: 

# let f = (+) 3;;
val f : int -> int = <fun>
# f 2;;
- : int = 5
# ((+) 2) 3;;
- : int = 5

Compunerea funcțiilor

Una din cele mai simple și larg folosite operații cu funcții este compunerea lor, în acest fel putem obține ușor funcții (prelucrări) complexe pornind de la funcții simple. În matematică, dacă f : A → B și g : C → A, compunerea f °g : C → B e definită prin relația (f °g)(x) = f(g(x)) . Deci, pornind de la o valoare x ∈ C se obține o valoare g(x) ∈ A, și apoi prin aplicarea lui f valoarea f(g(x)) ∈ B .

în OCaml putem defini o funcție de compoziție: 

# let comp f g x = f (g x);;
val comp : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
Vedem că tipul funcției comp este mai general decât cele întâlnite până acum. Funcția comp ia ca parametru o funcție (f) cu tipul 'a -> 'b și apoi o altă funcție (g) de tipul 'c -> 'a și produce o funcție (f °g) cu tipul 'c -> 'b . Aceste tipuri corespund cu cele din definiția matematică de mai sus, și reflectă faptul că domeniul de valori A al lui g trebuie să fie același cu domeniul de definiție al lui f . În OCaml, 'a, 'b, 'c sunt variabile de tip, care pot fi instanțiate (înlocuite) cu orice tip concret din limbaj (int, float, etc.).

Spunem că funcția comp este polimorfă (poate lua mai multe forme, în funcție de tipurile concrete substituite pentru 'a, 'b, 'c . Polimorfismul ne permite să scriem cod cât mai general, și e o noțiune deosebit de importantă care stă și la baza programării orientate pe obiecte.

Aplicarea repetată (compunerea unei funcții cu ea însăși)

În particular, dacă o funcție are același domeniu de definiție și de valori, poate fi compusă cu ea însăși: f °f, unde f : A → A . Pornind de la funcția de compunere comp putem defini o funcție de nivel superior care compune o funcție (dată ca parametru) cu ea însăși. 
# let appl2 f = comp f f;;
val appl2 : ('a -> 'a) -> 'a -> 'a = <fun>
În același fel, putem compune funcția appl2 cu ea însăși, obținând o funcție care aplică de 4 ori funcția primită ca parametru: 
# let appl4 = comp appl2 appl2;;
val appl4 : ('_a -> '_a) -> '_a -> '_a = <fun>
Putem scrie însă și direct 
# let appl4p = appl2 appl2;;
val appl4p : ('_a -> '_a) -> '_a -> '_a = <fun>
primul appl2 produce aplicarea de două ori a funcției argument, în acest caz tot appl2 . Putem urmări rezultatul folosind o funcție exemplu: 
# let f x = 2 * x + 1;;
val f : int -> int = <fun>
# appl4 f 0;;
- : int = 15
# appl4p f 0;;
- : int = 15
Exercițiul 1 (temă de casă)
Demonstrați, folosind definițiile de mai sus, că cele două variante de definire a cvadruplei aplicații produc într-adevăr același rezultat.

Exercițiul 2 (temă de casă)
Considerați următoarele definiții: 

let appl3 f = comp f (appl2 f)
let appl23c = comp appl2 appl3
let appl32c = comp appl3 appl2
let appl23p = appl2 appl3
let appl32p = appl3 appl2
Explicați ce reprezintă fiecare din funcționalele definite. Verificați rezultatul, aplicând fiecare din ele funcției f(x)=2*x+1 în punctul x=0.

Întregi și reali în ML

Pe lângă întregi, putem lucra în ML și cu reali, care au tipul float . ML e un limbaj puternic tipizat și ca atare face riguros diferența ître valori din cele douătipuri (deși matematic Z⊆R).

2 e o valoare întreagă, pentru o valoare reală trebuie să scriem 2.0 (sau prescurtat, 2.). La fel, operatorii + - * / lucrează doar cu întregi; pentru reali trebuie scris +. -. *. /. (toți operatorii sunt urmați de punct). ML nu face conversii implicite între întregi și reali; pentru a transforma un întreg în real folosim funcția float_of_int (sau echivalent, mai scurt, float). 

# float (3 * 2);;
- : float = 6.

Operații aritmetice cu funcții

În matematică (și ca urmare în programare) avem adesea nevoie să transpunem (generalizăm) o operații definită pentru anumite valori la funcții care produc astfel de valori (engl. lifting).

De exemplu, avem operațiile + - * / definite pe întregi. E natural să definim operațiile similare pentru funcții cu valori întregi. Pentru aceasta e suficient să definim, foarte general, o funcție lift care se aplică oricărui operator (funcție) op: 

# let lift op f g x = op (f x) (g x);;
val lift : ('a -> 'b -> 'c) -> ('d -> 'a) -> ('d -> 'b) -> 'd -> 'c = >fun>
Acum putem particulariza simplu, pentru adunarea a două funcții: 
# let iaddf = lift (+);;
val iaddf : ('_a -> int) -> ('_a -> int) -> '_a -> int = <fun>
# let faddf = lift (+.);;
val faddf : ('_a -> float) -> ('_a -> float) -> '_a -> float = <fun>
Funcția iaddf ia ca parametri două funcții cu același domeniu de definiție și valori întregi ('a -> int) și produce o funcție de același tip care e suma lor. La fel pentru faddf și funcții reale. Observăm că funcționala lift e polimorfă și poate fi aplicată unor operatori de diverse tipuri -- nu a trebuit s-o rescriem.

Putem verifica funcționalitatea adunării de mai sus cu următorul exemplu: 

let fsqrf f = lift ( *.) f f
let trig1 = lift (+.) (fsqrf cos) (fsqrf sin)
Prima definiție transpune operatorul produs pe reali *. făcând produsul unei funcții cu ea însăși (deci, pătratul funcției). A doua linie definește funcția cos2 x + sin2 x (numele variabilei nu e necesar explicit în cod) despre care știm că e funcția constantă 1. Putem verifica: 
# trig1 (atan 1);;
- : float = 1.
# trig1 (asin 0.5);;
- : float = 0.999999999999999889
Rezultatul ne atrage atenția că pe calculator nu avem întotdeauna operații matematice perfecte și pot apărea pierderi de precizie.

Partea întreagă și rotunjirea

OCaml dispune de funcțiile floor : float -> float care returnează partea întreagă ⌊ x ⌋ și ceil : float -> float (funcția plafon ⌈ x ⌉) care returnează cel mai mic întreg care e cel puțin egal cu x. Amândouă produc valori float (dar au, prin definiție, partea fracționară zero).
De asemenea există funcția int_of_float : float -> int (sau cu numele echivalent truncate), care trunchiază partea fractionară (deci trunchiază înspre zero indiferent de semn).

Exercițiul 3
Definiți funcția roundup care rotunjește un număr real la întreg (rotunjind în sus pentru părți fracționare de la 0.5 în sus).

Soluție (argumentați corectitudinea!) 

let roundup x = floor (x +. 0.5)
val roundup : float -> float = <fun>
După cum se vede din tipul funcției, aceasta produce (la fel ca și floor) un număr cu parte fracționară zero, ca număr real. Dacă vrem un număr întreg, putem să aplicăm rezultatului funcția truncate (sau int_of_float).

Exercițiul 4
(a) Scrieți o funcție care ia ca parametru un număr real și îl rotunjește la a doua zecimală (tot în sus, ca în cazul anterior).
(b) Fiind dat un preț net, exprimat ca număr întreg în bani, calculați valoarea TVA (24%) corespunzătoare (în lei, rotunjită la ban).
Utilizați compunerea de funcții, refolosind cât mai mult cod (și duplicând căt mai puțin).

Exercițiul 5 (temă de casă)
În New York, o călătorie cu transportul în comun costă $2.50. Se poate plăti cu un card încărcat cu o sumă de bani. La incărcare se primește un bonus de 5%, rotunjit la cent. Automatul de încărcare acceptă doar sume în multipli de 5 cenți. Care e suma minimă care trebuie incărcată pentru N călătorii ?

Marius Minea
Last modified: Thu Sep 19 18:00:00 EEST 2013