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 cu Ctrl-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
)

Exercițiul 1 Scrieți o funcție care ia ca parametri trei întregi a, b, c și tipărește soluțiile ecuației de gradul doi ax²+bx+c=0, sau un mesaj dacă nu există soluții reale. Folosiți funcția predefinită sqrt : float -> float pentru rădăcina pătrată și nu uitați conversiile de la întreg la real unde sunt necesare. Folosiți secvențierea când trebuie tipărite două soluții.

Exercițiul 2 Scrieți o funcție care returnează minimul/maximul a trei valori date ca parametri. Folosiți funcțiile predefinite min respectiv max care funcționează cu orice valori de același tip. Remarcați tipul funcției scrise și verificați că funcționează și cu întregi și cu reali (și chiar cu șiruri), însă nu cu un amestec.

Exercițiul 3 Scrieți o funcție care determină dacă un an (întreg) dat ca parametru e bisect, returnând un boolean. Dacă un an e bisect sau nu se poate determina după următoarele reguli (va trebui sa le reformulați sau reordonați pentru a scrie funcția):
a) un an divizibil la 4 e bisect, altfel nu
b) prin excepție de la a), anii divizibili cu 100 nu sunt bisecți
c) prin excepție de la b), anii divizibili cu 400 sunt bisecți

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

Exerciții propuse

Exercițiul 4 Mediana
Scrieți o funcție care calculează mediana a trei valori (valoarea aflată între celelalte două).
Încercați să scrieți cod cât mai simplu, și să nu-l repetați. Puteți folosi o funcție auxiliară care calculează mediana a trei numere, pentru care știm că primul e mai mic sau egal decât al doilea.

Exercițiul 5
În matematică, am extins uneori operatorul + de la numere la funcții, defining funcția f + g prin relația (f + g)(x) = f(x) + g(x)
a) Definiți în ML o funcție care ia ca parametru două funcții f și g și returnează funcția definită ca suma lor prin relația de mai sus.
b) Scrieți o funcție mai generală, care primește ca parametru și operatorul binar (o funcție de două argumente) care e aplicată (valorilor) celor două funcții. Verificați că o puteți folosi cu operatorul (+) și ( *) pentru a calcula suma și produsul.
În scrierea operatorului ( *) trebuie un spațiu între ( și * pentru a nu fi interpretat ca și comentariu. În ML, comentariile sunt încadrate între (* și *).

Marius Minea

Last modified: Tue Sep 27 15:55:00 EEST 2016