Cflp

Laborator

Facultatea de Automatica şi Calculatoare

Departamentul de Calculatoare

	Home	Lucrarea 1	Lucrarea 2	Lucrarea 3	Lucrarea 4	Lucrarea 5	Lucrarea 6	Lucrarea 7
		Lucrarea 8	Lucrarea 9	Lucrarea 10	Lucrarea 11	Lucrarea 12	Lucrarea 13	Proiect	Orar

Lucrarea 10

Subiecte

ML

ML (Meta-Language) este un set de limbaje de programare avansată, făcând parte din familia limbajelor de programare funcţionale. Limbajul este o combinaţiie a proprietăţilor LISP şi Algol, şi este primul limbaj care include tipizarea polimorfică. ML a fost proiectată la universitatea Edinburgh în 1973.
La fel ca la lisp şi ML are mai multe dialecte (Standard ML, Lazy ML, CAML, etc.)
Dialectul CAML (original Categorical Abstract Machine Language) este o versiune franceză de ML şi suportă printre altele şi programarea orientată pe obiecte (varianta OCAML), precum şi programarea iterativă.
Original ML a fost un limbaj construit pentru a scrie programe care manipulează alte programe – ca compilatoare şi interpretoare, dar întretimp a devenit un limbaj sine stătător, utilizat mai frecvent în verificarea programelor şi în demonstrarea automată a teoremelor matematice, dar are aplicatibilitate mare şi in implementarea rapidă a aplicaţiilor WEB, protocoalelor de comunicaţie sau calcule distriuite.

Proprietăţi CAML

Limbaj funcţional
Funcţiile sunt tratare ca restul tipurilor de date, ele putând fi parametrul sau rezultatul altor funcţii. Programarea funcţională permite programarea fară efecte secundare.
Tipuri de date bine definite
Limbajul pune la dispoziţia programatorului un set de tipuri de date şi operatori necesare manevrării acestor tipuri. Este posibilă definirea noii tipuri de variabile.
Limbaj puternic tipizat
Declaraţia tipului unei variabile nu este necesară, tipul fiind determinat automat. Chiar în timpul compilări – şi nu în timpul rulări – se verifică corectitudinea parametrilor funcţiilor.
Tipuri polimorfice
Este posibilă declararea funcţiilor cu parametri a cărui tip nu este precizat, fiind posibila executarea lor cu orice tip.
Potrivirea de şabloane
ML permite scrierea de programe bazate pe reguli (vezi labortarul 11).
Colectarea automată a deşeurilor
G estionarea memoriei se face automat de limbaj
Securitate
Se face o verificare a corectitudinii codului chiar la introducerea (compilarea acesteia)
Proprietăţii imperative
Mecanisme de manipularea a tablourilor i a variabilelor care îşi schimb conţinutul.
Recuperarea din erori
Mecanism de tratarea a excepţiilor.
Programarea orientată pe obiecte
CAML are facilităţi de POO.

Pornire CAML

Sub sistemul de operare Linux, CAML poate rula în emacs ca process inferior asemănator interpretorului xlispstat. Pentru rularea interpretorului trebuie să porniţi procesul inferior caml cu M-x run-caml. (Necesită acceptarea interpretorului ocaml prin apăsarea tastei Enter).
În zonele de lucru în care editaţi codul ML trebuie să aveţi modul caml. Puteţi schimba modul curent în modul caml prin M-x caml-mode.

Sub sistemul de operare Windows CAML nu are facilităţi de interfaţare cu emacs. CAML se rulează doar ca interpretor care citeşte linie cu line comenzile. Puteţi porni caml prin selectarea iconului Objective Caml de pe desktop. După porninire apare interpretorul ML în mod interactiv: într-un ciclu de citire – evaluare – afişare, utilizatorul introducând o expresie, aceasta va fi evaluată iar rezultatul este afişat. # semnifică prompterul după care pot fi scrise funcţii ML. Interpretorul va tipării răspunsul pe o linie nouă. În laborator sub Windows Caml este instalat doar pe calculatoarele Taurus, Cancer, Aquarius, Pisces din cauza limitării spaţiului pe disk.

Expresie simplă în ML

# 2+3;;
- : int = 5

Exempele sunt date sub formă comandă-răspuns. Liniile care încep cu # trebuie intorduse (fără #) şi evaluate; răspunsul (obţinut după M-C-X sau Enter) este indicat cu o culoare mai deschisă.

O expresie putem să scriem pe mai multe linii; expresia terminând cu ;;, care determină evaluarea expresiei şi afişarea rezultatului.

Tipuri primitive

Numere întregi şi reale

În CAML există două tipuri de numere: numere întregi şi numere reale. Cele două sunt tipuri diferite, fiecare având un set operaţii diferite:
Întregi:

+	adunare
-	scădere
*	înmulţire
/	împărţire întreagă
mod	restul împărţirii

Numere reale:

+.	adunare
-.	scădere
*.	înmulţire
/.	împărţire întreagă
**	ridicare la putere

Operaţii
# 2 + 3;; - : int = 5 # 4.0 +. 5.5;; - : float = 9.5 # 4.0 +. 5;; Characters 7-8: 4.0 +. 5;; ^ This expression has type int but is here used with type float

Problema 1
Evaluaţi exemplele de mai sus.

Tipurile de caracter şi şir de caractere

Caractere sunt coduri ASCI între 0 şi 255. Ele sunt specificate între semnele de apostrof.
Stringurile sunt şiruri de caractere de lungime maximă 2²⁴-6.
Operatorul ^ concatenează două şiruri.

Caractere şi stringuri
# 'a';; - : char = 'a' # "rezultatul" ^ " este " ^ "un string";; - : string = "rezultatul este un string"

Tipul boolean

Tipul boolean are valoare true sau false.
Operaţii permise:

&& sau &	şi logic
\|\| sau or	sau logic
not	nu logic

Operatori logici
# true && false;; - : bool = false # false or not (2=3);; - : bool = true

Problema 2.
Evaluaţi exemplele de mai sus.

Operatorii logici evaluează argumentele doar până când rezultatul operaţiei poate fi determinată. Restul parametrilor nu sunt evaluate.

Operatori de comparare

Operatori =, <, <=, >, >=, <> sunt polimorfi, ele pot să compare numere, caractere sau şiruri.

Operatori de compaţie
# 5 < 6;; - : bool = true # "beta" > "alfa";; - : bool = true

Liste

Listele sunt structuri de date infinite: sunt vide sau formate din elementul din capul listei şi lista restul elementelor. Toate elementele unei liste sunt de acelaşi tip.

Liste
# [];; - : 'a list = [] # [1;2;3];; - : int list = [1; 2; 3]

Observaţie: int list semnifică că rezultatul este o listă de întregi, iar ‘a list semnifică că rezultatul este o listă de tip nespecificat. Tipul elementului putând să fie orice.

Operatorul :: adaugă un nou element la începutul unei liste.
Operatorul @ concatenează două liste.

Operatori cu liste
# 1::2::3::[];; - : int list = [1; 2; 3] # ['a';'b'] @ ['c';'d';'e'];; - : char list = ['a'; 'b'; 'c'; 'd'; 'e']

Problema 3.
Evaluaţi exemplele de mai sus.

Alte operaţii asupra listelor sunt definite în biblioteca List. Funcţiile hd şi tl returnează primul element a listei respectiv coada listei fără primul element.

Head şi tail

# List.hd [1;2;3;4];;
- : int = 1
# List.tl [1;2;3;4];;
- : int list = [2; 3; 4]

N-tuple

Agregarea valorilor a mai multor tipuri pot forma n-tuple. N-tupele se scriu sub forma unei enumerare de valori despărţite prin virgule în interiorul unei paranteze rotunde.

N-tuple
# (2,'D',3,"trei") ;; - : int char * int * string = (2, 'D', 3, "trei")*

Structuri condiţionale

La fel ca şi în alte limbaje şi în ML există structuri condiţionale. Spre deosebire de limbajele iterative evaluarea unei expresii condiţionate ML rezultă o valoare.
Sintaxa:
if expr1 then expr2 else expr3
Evaluare expresiei va rezulta expr2 în caz că expr1 este evaluată la adevărat şi expr3 în caz că expr1 este falsă.

IF ... THEN ... ELSE
# if 2=3 then 2 else 3;; - : int = 3

Variabile globale

Folosirea primitivei let determină legarea valori rezultate a unei expresii la o variabilă.

LET
# let a = 5 * 2;; val a : int = 10 # a ;; - : int = 10

Declarări paralele pot fi făcute folosind sintaxa:
let var1 = expr1
and var2 = expr2
...
and varn = exprn ;;
Variabile declarate nu vor vedea pe restul variabilelor declarate pană la terminarea lui let.

LET paralel
# let a = 1;; val a : int = 1 # let a = 2 and b = a + 1;; val a : int = 2 val b : int = 2 # a + b ;; - : int = 4

Este posibil şi declararea secvenţială a variabilelor, ele având acces la toate declaraţiile anterioare. În acest caz scriem mai multe instrucţiuni let unul după celălalt. Secvenţia de declaraţie va terminată de ;;.

LET secvenţial

# let z = 1
let u = z+2;;
val z : int = 1
val u : int = 3

Declaraţii locale

Declaraţiile locale au rolul de a limita domeniul de existenţă a variabilelor.
Declaraţiile locale se fac folosind primitiva let cu sintaxa mai sus prezentată, expresia asignată fiind urmată de in şi de expresia în care vrem sa fie vizibilă declaraţia.

Definiţie locală
# let x = 1 and y = 2 in x+y;; - : int = 3

Funcţii

O funcţie se defineşte după sintaxa:
function p -> expr
Această definiţie este foarte asemănătoare cu definiţile lambda din LISP.
Expresia specificată cu function rezultă o funcţie apelabilă:

Definiţie de funcţii
# function x -> x + 1 ;; - : int -> int = <fun> # (function x -> x + 1) 2;; - : int = 3

Expresia la rândul ei poate să fie o altă funcţie.

Definiţie de funcţii

În exemplul următor se vor da exemple cu declaraţia funcţiilor cu mai mulţi parametri.

# function x -> (function y -> x + y + 1) ;;
- : int -> int -> int = <fun>
# function x -> function y -> x + y + 1 ;; (* declaratie echivanenta*)
- : int -> int -> int = <fun>
# (function x -> function y -> x + y + 1) 2;; (* rezulta functia y -> 2 + y + 1 *)
- : int -> int = <fun>
# (function x -> function y -> x + y + 1) 2 5;;
- : int = 8

Funcţiile pot avea ca parametru şi n-tuple.

Definiţie de funcţii

# (function (x,y) -> x + y+ 1) (2,5);;
- : int = 8

Observaţie: această declaraţie este fundamental diferită de cea precedentă, funcţia asteptând un singur parametru, o pereche de numere, pe când declaraţiile precedente aşteaptau doi parametri.

Pentru compactitate în CAML poate fi folosită cuvântul cheie fun.
fun p1 p2 ...pn -> expr
este echivalentă cu
function p1 ->function p2 ->... -> function pn -> expr

Definiţie de funcţii
# (fun x y -> x + y + 1) 2 5;; - : int = 8

În declaraţiile de mai sus funcţiile nu aveau asignată o nume, o expresie function returnează o funcţie, care cu let poate fi legat de o nume:

Definiţie de funcţie
# let addinc = function x -> function y -> x + y + 1;; val addinc : int -> int -> int = <fun> # addinc 2 5;; - : int = 8

Este permisă şi o scriere mai compactă:
let name p1 ... pn = expr
echivalent cu
let name = function p1 -> -> function pn -> expr

Definiţie de funcţie
# let addinc x y = x + y + 1;; val addinc : int -> int -> int = <fun>

În cazul în care vrem să definim funcţii recursive atunci numele asignată funcţiei cu un let trebuie să fie precedată de cuvântul cheie rec.

Factorial
# let rec fact=function n -> if n=0 then 1 else nfact (n-1);; val fact : int -> int = <fun>* # fact 3;; 6

Problema 4.
Implementaţi în ML funcţia lui fibonacii.

Problema 5.

Implementaţi funcţia ackerman.

ack(x,y)= ack(x-1, ack(x,y-1)), dacă x>0, y>0
ack (x-1,1), dacă x>0, y=0
y+1, dacă x=0

Problema 6.

Scrieţi funcţia geninterval, care primeşte doi parametri s şi e şi retunrează o listă formată din numerele întregi între s şi e.

# geninterval 3 8;;
- : int list = [3; 4; 5; 6; 7; 8]

Problema 7.

Definiţi funcţiile my_not, my_and şi my_or făra a utiliza operatorii not, and sau or.

# my_and (3=3) (4=4);;
- : bool = true

Problema 8.

Scrieţi funcţia digits care transformă un număr întreg într-o listă de formată din cifrele sale.

# digits 123;;
- : int list = [1; 2; 3]

Problema 9.

Scrieţi funcţia maxim care calculează maximul dintr-o listă. Puteţi folosi funcţia max, care returnează maximul dintre doi parametri.

# maxim [2;3;1;7;5];;
- : int = 7

Problema 10.
Definiţi funcţia CMDC, cel mai mare divizor comun.

Instare OCAML

Puteţi obţine ultima distribuţie de de ocaml de aici. Versiunile 3.07, instalate în laborator, pentru Linux RH7.3 şi Windows se găsesc şi pe acest site.

Sub Windows

Aduceţi arhiva ocaml de pe siteul INRA sau versiunea de la serverul local. Porniţi arhiva şi urmăriţi paşii de instalare. Sub Windows nu există posibilitatea de interfaţare cu emacs!

Sub Linux

Aduceţi arhiva precompilartă sau sursele de la INRA. Versiunea precompilată RPM pentru Linux Redhat 7.3 se găseşte local aici. Instalaţi arhiva adusă. Pentru interfaţara cu emacs trebui sa adăugaţi următoarele linii în fişierul .emacs din directorul home a utilizatorului:

(setq auto-mode-alist (cons '("\\.ml[iylp]?" . caml-mode)
               auto-mode-alist))
(autoload 'caml-mode "caml"
               "Major mode for editing Caml code." t)
(autoload 'run-caml "inf-caml"
               "Run an inferior Caml process." t)
(autoload 'camldebug "camldebug"
               "Run the Caml debugger." t)

Aici găsiţi fişierul .emacs care conţine liniile adiţionale necesare pentru xlispstat şi ocaml.

Probleme

Problema 1. Operaţii cu tipuri numerice

Problema 2. Operaţii logice

Problema 3. Operaţii cu liste

Problema 4. Funcţia lui Fibonacii

Problema 5. Funcţia lui Ackerman

Problema 6. Generator de liste

Problema 7. Operatori logici

Problema 8. Numere mari

Problema 9. Maximul unei list

Problema 10. Cel mai mare divizor comun