Introducere. Lucrul cu funcții

Mediul de lucru: Interpretorul OCaml

Vom ilustra

• • cum se aplică în domeniul informaticii noțiunile discutate la curs, și în particular

  • cum sunt legate de caracteristici ale limbajelor de programare

Î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 prompterul # 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

Aici și în cele ce urmează, când dăm astfel de exemple, # e prompterul interpretorului (nu trebuie introdus), iar rândurile cu - : reprezintă răspunsul dat de interpretor.

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 ;;

iar interpretorul răspunde

- : 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 definiția let f x = x + 3 interpretorul răspunde:

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ă).

Când scriem un fișier program ML, nu trebuie să încheiem fiecare definiție cu ;; ca în interpretor, unde prin aceasta îi indicăm să evalueze fragmentul scris până acum. E nevoie de ;; doar când altfel nu ar fi clar unde se termină o definiție sau expresie și începe următoarea: după un șir de definiții urmat de o evaluare de expresie, și pentru a separa evaluări de expresii. De exemplu:

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

Pentru a încărca apoi fișierul creat în interpretorul OCaml, în Emacs se poate instala un pachet special, tuareg-mode. Acesta reprezintă programele ML colorate după regulile de sintaxă, și deci mai ușor de citit. Pachetul are însă și comenzi care permit rularea interpretorului Ocaml direct în editor.

În Emacs, putem lucra astfel în două sub-ferestre: una în care scriem codul ML, și alta în care se rulează interpretorul OCaml. Secvențele de taste uzual folosite pentru a da comenzi în acest mod încep cuCtrl-c ('c' de la 'compilare').

Cel mai simplu e să evaluăm definițiile (de funcții) pe rând, pe măsură ce le scriem. După ce am scris de exemplu let f x = x + 2, cu comanda Ctrl-c Ctrl-e ('e' = evaluare) se evaluează definiiția din dreptul cursorului (acesta poate fi oriunde în cadrul sau după definiție). La prima execuție a acestei comenzi, în linia de jos a editorului (pentru comenzi și mesaje) apare mesajul OCaml toplevel to run: ocaml. Confirmăm cu tasta Enter că dorim să rulăm interpretorul. În jumătatea de jos a ecranului se indică faptul că definiția a fost evaluată: val f : int -> int = <fun> și apare prompterul # al interpretorului, la care putem evalua expresii, de exemplu f 3;;.

Alte comenzi utile:

• • Ctrl-c Ctrl-r ('r' = region): compilează regiunea de cod selectată (cu mouse sau taste)

  • Ctrl-c Ctrl-b ('b' = buffer): compilează întreg conținutul ferestrei active din editor

  • Ctrl-c Ctrl-t ('t' = type, dacă e instalat și pachetul 'merlin'): indică tipul identificatorului de sub cursor, sau al expresiei selectate

Î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.

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).

Tipărirea

Până acum ne-am folosit de faptul că interpretorul afișează automat rezultatul unei evaluări. Pentru a scrie șî rula programe de sine stătătoare sunt însă necesare funcții care să tipărească valori.

OCaml are funcții predefinite de tipărire pentru principalele tipuri de bază: print_int, print_float, print_char, print_string. Caracterul de linie nouă se reprezintă ca în C: '\n'. Putem de asemenea trece la linie nouă apelând print_newline().

Există și funcția printf, folosită asemănător ca în C, cu aceeași convenție că argumentele se scriu separat, nu cu virgulă:

printf "intreg: %d real: %f\n" 3 1.2 va tipări

"intreg: 3 real: 1.2" Pentru a folosi funcția printf trebuie însă înainte fie să deschidem modulul de bibliotecă Printf în care e definită:

open Printf

fie să folosim numele complet, având ca prefix numele modulului: Printf.printf "salut!"

Secvențierea

Uneori vrem să facem în program succesiv mai multe lucruri. OCaml nu are noțiunea de instrucțiune: nu executăm instrucțiuni ci doar evaluăm expresii. Chiar când tipărim ceva, rezultatul este o valoare, dar o valoare fără interes, notată () și care e unicul membru al tipului unit (oarecum similar cu void în C). Dacă dorim să evaluăm succesiv mai multe expresii, le înșiruim separate prin punct-virgulă. În acest caz, toate expresiile trebuie să fie de tip unit, mai puțin eventual ultima, care dă valoarea întregii expresii compuse. De exemplu funcția

let tip_arg x = print_int x; x își tipărește argumentul și îl returnează neschimbat.

Dacă în locul respectiv sintaxa limbajului permite o singură expresie, secvențierea de expresii trebuie grupată între paranteze ( ), de exemplu în ramurile then și else ale următoarei funcții care tipărește argumentul primit și îi returnează valoarea absolută:

open Printf let abs_print x = if x > 0 then ( printf "argument pozitiv: %d\n" x; x ) else ( printf "argument negativ: %d\n" x; -x )

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, 'csunt 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 ordin 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

Funcții de ordin 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 ordin 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).

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

Informatii suplimentare:

(* Asa se pun comentariile in OCaml *) 2 + 3;; (* dupa ce se evalueaza aceasta expresie, va scrie : int = 5 Adica expresie evaluata are valoarea 5 si este un intreg *) (* definirea unei functii *) let f x = x + 4;; (* Orice definitie incepe cu LET. Parametrii functiei se afla intre numele functiei si semnul =. Nu se grupeaza intre paranteze, nu se separa prin virgula Intre = si ;; se afla corpul functiei. Cand se evalueaza linia, va scrie: val f : int -> int = <fun> Adica o functie, numita f care primeste ca parametru un intreg si returneaza un intreg De unde stie ca x e intreg? pentru ca se face + 4 si de-aia x tre sa fie un intreg. Acest lucru se numeste inferenta de tipuri si e ceva Important: https://en.wikipedia.org/wiki/Type_inference *) (* apelarea functiei: *) f 4;; (* din nou, argumentele nu se grupeaza intre paranteze *) (* Functii cu mai multi parametrii *) let f x y = x + y;; f 2 3;; (* Nu se grupeaza nici parametrii, nici argumentele intre paranteze Cand se evalueaza definitia, va scrie: val f : int -> int -> int = <fun> *) (* Daca apelezi functia cu mai putini parametrii *) f 2;; (* cand se evalueaza, scrie: int -> int = <fun> Adica obtii o functie cu un singur parametru: g y = 2 + y. x a fost inlocuit cu 2. Deci ai putea face: *) let g = f 2;; (* Important: poti sa ai variabile de tip functie (nu doar intregi, siruri de caractere, etc.) Deci, daca ne uitam iarasi la val f : int -> int -> int = <fun>, asta inseamna ca e o functie care primeste un intreg si returneaza o functie care primeste un intreg si returneaza un intreg Cand aveti o functie un N parametrii, si o apelati f x1 x2 x3 ... xn, de fapt, sunt n functii cu un parametru ((((f x1) x2) x3) ... ) xn https://en.wikipedia.org/wiki/Currying *) (* Functii anonime *) let a = fun x -> x + 3;; (* asta inseamna ca e o variabila, a, a carei valoare este o functie cu un parametru intreg si care returneaza un intreg *) let a x = x + 3;; (* asta inseamna ca e o functie numita a cu un parametru intreg si care returneaza un intreg e o diferenta subtila intre cele 2 chestii. *) (* Functii care iau ca parametru alte functii. Daca variabilele pot fi de tip functie, si parametrii pot fi de tip functii *) let comp f g x = f (g x);; (* val comp : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun> Ce inseamna asta? stim deja ca inseamna ca e o functie cu 3 parametrii si returneaza o treaba. In corpul functiei, nu am facut nicio operatie cu parametrii ca sa facem pe compilator sa-si dea seama ca ele tre sa aibe un tip anume. De-aia OCaml le da niste tiprui generice. Ele nu trebuie sa aibe un tip anume, dar acele tipuri tre sa satisfaca niste constrangeri. Matematic, ca sa poti face f(g(x)), trebuie ca: f : A -> B g : C -> A si cand o apelezi f(g(x)), x trebuie sa fie un C Aia zice si OCaml. f : 'a -> 'b g : 'c -> 'a x : 'c toata expresia returneaza 'b Observati ca (g x) a fost grupat intre paranteze. Am facut aia pt ca intai vrem sa facem g de x, iar apoi, f de rezultatul lui g de x. Adica controlam ordinea evaluarii. *) let f x = x + 1;; let g x = x + 4;; comp f g 3;; (* Modelul de executie prin substitutie: ca sa vezi ce se intampla cand apelezi o functie, in programarea functionala poti oricand sa inlocuiesti apelul functiei cu corpul ei, inlocuind parametrii cu valorile lor. Adica: comp f g 3 f (g 3) f (3 + 4) f (7) 7 + 1 8 *) (* Discutie despre functii si parametrii *) let x = 4;; let f x = x + 2;; (* x din corpul functiei nu are nicio treaba cu x de dinafara care are valoarea 4. x din corpul functiei traieste de la = pana la ;; *) let f x = x + 4;; let g f = f + 2;; (* Pentru ca g are un parametru numit f, in corpul lui g nu voi putea folosi functia f definita mai sus pentru ca oricand voi scrie f in corpul lui g, va fi vorba despre acel parametru care e de tip intreg (pentru ca fac + 2 cu el) https://en.wikipedia.org/wiki/Scope_(computer_science) *) (* Diferenta intre printeaza si returneaza!! print - returneaza unit (), adica nimic daca vrei sa faci o functie care returneza parametrul + 1, faci: let f x = x + 1, si nu let f x = printf "%d" (x + 1) Prima varianta returneza un intreg si a doau il printeaza si returneaza unit. *) (* Equatie de gradul 2 *) open Printf;; let delta a b c = b *. b -. 4. *. a *. c;; let x1 delt a b = ((b *. (-1.) +. sqrt delt) /. (2. *. a));; let x2 delt a b = ((b *. (-1.) -. sqrt delt) /. (2. *. a));; let f a b c = if (delta a b c) < 0.0 then printf "nope" else printf "%f %f" (x1 (delta a b c) a b) (x2 (delta a b c) a b) ;; (* De notat: - spargerea problemei in sub probleme, in functii mai mici care fac mai putine chestii si care sunt mai usor de testat - folosirea acelor functii ca sa rezolvi ceva mai complex - gruparea cu paranteze ca sa controlam ordinea de evaluare Adica am facut (x1 (delta a b c) a b) pentru ca: - intai vreau sa fac delta a b c si sa obtin valoarea lui delta - dupaia vreau sa apelez x1 valoarea_lui_delta a b si sa obtin valoarea lui x1 Observati ca in definitia lui x1 si x2 am folosit un parametru pe care il cheama delt. Ala are rolu de delta. Dupa explicatiile de mai sus, e clar ca puteam sa-l denumesc delta si nu era nicio confuzie cu functia delta. *) (* O eroare care va putea sa apara in general. Daca as fi avut: open Printf;; let delta a b c = b *. b -. 4. *. a *. c;; let x1 delta a b c = ((b *. (-1.) +. sqrt (delta a b c)) /. (2. *. a));; let x2 delta a b c = ((b *. (-1.) -. sqrt (delta a b c)) /. (2. *. a));; let f a b c = if (delta a b c) < 0.0 then printf "nope" else printf "%f %f" (x1 (delta a b c) a b) (x2 (delta a b c) a b) atunci, pe linia cu else, as fi avut o eroare care zice ca expresia (delta a b c) e un floar, dar ca x1 are ca prim parametru o functie de tip float -> float -> 'a -> float (adica o functie cu 3 parametrii si care returneza float) De unde stie asta? pentru ca in definitia lui x1, fac delta a b c => delta e o functie cu 3 parametrii si pentru ca dupaia fac sqrt (delta a b c) => pt ca sqrt primeste un float => delta tre sa returneze un float Observati ca eroarea in acest program a aparut pentru ca am crezut ca delta returneaza un float dar de fapt nu face aia. Si am fi putut sa ne dam seama de asta daca citeam rezultatul evaluarii lui let x1 ... am fi vazut: val x1 : (float -> float -> 'a -> float) -> float -> float -> 'a -> float = <fun> si ne dadeam seama ca primu parametru e o functie. Bottom line: - cititi fiecare instructiune si rezultatul interpretarii ei! - testati bucatile mici inainte de a le folosi intr-o chestie mare! *)

//informatii luate de pe pagina laboratorului