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 .
# 2+3;;iar interpretorul răspunde:
- : int = 5Semnul ;; (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 = 5Cele două caractere ;; trebuie scrise însă unul după celălalt pentru fi interpretate ca sfârșit al textului de interpretat.
let f x = x + 3Cuvântul cheie let (engl. "fie") introduce o definiție, aici, pentru identificatorul f. Scrierea amintește de exprimarea: fie f dat de expresia ...
# 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
(fun x -> x + 3) 2;; - : int = 5fă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>
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.
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).
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.
(+) 2 3;; - : int = 5E 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).
# (+) ;; - : 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
î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.
# 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 = 15Exercițiul 1 (temă de casă)
Exercițiul 2 (temă de casă, săpt. 2)
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 appl2Explicaț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.
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.
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.999999999999999889Rezultatul ne atrage atenția că pe calculator nu avem întotdeauna operații matematice perfecte și pot apărea pierderi de precizie.
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 (temă de casă)
(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 (opțional)
Î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 ?