Laborator 3

3.1 Atomi simbolici. Evaluare. Funcii LISP de atribuire.

Dup cum am menionat n primul laborator, obiectele primare cu care opereaz LISP-ul sunt atomii. Acetia pot fi numere ntregi cuprinse ntre -32768 si 32767 sau hexazecimale, simboluri sau iruri de caractere (texte).

De asemenea, anumite caractere speciale sunt considerate atomice; de exemplu LPAR si RPAR (parantezele rotunde care pot fi utilizate i cu numele lor simbolic), PERIOD (.), SLASH (/), QUOTE (), ...

Valorile de adevr t i nil sunt i ele considerate atomice. Exist un predicat LISP, atom, care returneaz t (true) dac argumentul lui

este atomic i nil altfel. Exemplu: - (atom 2) t - (atom exemplu) t - (atom nil) t - (atom period) t Domeniul de utiliyare al limbajului LISP fiind calculul simbolic, un program

scris n acest limbaj va prelucra expresii simbolice, programul nsui fiind o succesiune de expresii simbolice. Echivalentul LISP al identificatorilor de variabile din alte limbaje de programare (de exemplu Pascal sau C) este simbolul care este i el considerat o data de tip atomic. Simbolul va desemna o valoare dinamic, deci care poate fi supus modificrilor n cursul execuiei programului LISP. Un simbol este reprezentat printr-un ir de caractere, semne sau cifre cu condiia ca primul caracter s nu fie cifr.

Putem evalua direct anumite expresii sau atomi prin simpla tastare a obiectului supus evalurii:

- 7 7 - exemplu exemplu - (+ 4 7) 11 sau - (+,4,7) 11 Astfel, un atom numeric sau ir de caractere este evaluat prin coninutul su.

Dac este vorba despre o list, atunci ea poate fi evaluat, deci este evaluabil, dac primul argument al ei este numele unei funcii predefinite sau definite de utilizator. n acest caz, vor fi mai nti evaluate toate argumnetele funciei i apoi va fi aplicat funcia propriu-zis valorilor argumentelor ei.

Dar exist o funcie LISP predefinit care ne permite evaluarea. Aceast functie este EVAL i ea are urmtoara sintax:

(eval arg) Astfel:

- (eval 3) 3 - (eval a) nil

Simbolul a nedesemnnd nici o valoare, pointeaz spre nil; de aceea rezultatul evalurii este nil.

Funcia eval st la baza funcionrii interpretorului LISP read-eval-print. O alt funcie pentru controlul evalurii este quote, care are un efect contrar

lui eval i anume nghearea evalurii, adic returneaz expresia argument neevaluat. Ca si notaie echivalent, funcia poate fi apelat prin utilizarea simbolului (apostrof).

- (quote a) a - ( (4 5)) (4 5)

Deci, simbolul a care nu desemneaz deocamdat nici un fel de dat, este introdus n urma aplicrii funciei quote fr a fi evaluat. Dac am ncerca s evalum direct acest simbol a vom obine un mesaj de eroare care ne spune c simbolul respectiv nu desembeaz nici o valoare.

- a unbound

spre deosebire de cazul n care utilizm funcia eval: - (eval a) nil

care, de fapt realizeaz o dubl evaluare a argumentului. S vedem cum putem asigna unui astfel de simbol o anumit valoare

(echivalentul atribuirii de valori variabilelor din alte limbaje de programare). Pentru aceasta exist instruciunea set cu varianta setq. Sintaxa:

(set arg1 arg2) Prin aceast instruciune, valoarea celui de-al doilea argument devine valoarea

primului argument evaluat n prealabil. Pentru a opri evaluarea oricrui argument din cele dou nu avem dect s utilizm funcia quote sub forma ei simbolic.

Exemplu: - (set a 3) 3 - a 3 - (eval a) 3

Nu este permis modificarea valorilor atomilor. De exemplu, dac nu oprim evaluarea lui a; care n acest moment desemneaz atomul numeric 3, i ncercm o

operatie de atribuire: - (set a 5)

va fi semnalat eroare, deoarece lui 3 nu-i putem atribui valoarea 5. O variant a funciei set este setq care implicit oprete evaluarea primului

argument, fiind mai sigur n utilizare i evitnd erorile ce pot interveni din neatenia programatorului.

Sintaxa: (setq arg1 arg2)

Valoarea celui de-al doilea argument devine valoarea pentru primul argument neevaluat. Ca i avantaj suplimentar, aceast funcie permite atribuiri multiple:

- (setq a1 2 a2 10 a3 5) 5

ceea ce este echivalent cu: - (set a1 2) 2 - ( set a2 10) 10 - (set a3 5) 5

S urmrim n continuare urmtorul exemplu: - (setq a 3) (1) 3 - (setq b a) (2) a - (set b 4) (3) 4

Dac acum ncercm evaluarea direct a lui a i b vom avea urmtoarea surpriz:

- b a - a 4 - (eval b) 4

Care este explicaia? Prima instruciune (1) a iniializat simbolul a la valoarea 3; deci n acest

moment o evaluare direct a lui a returneaz valoarea 3. Instruciunea (2) iniializeaz b la valoarea a (simbolul a neevaluat). Deci b=a. Apoi, ultima instruciune (3) atribuie lui b evaluat; adic simbolului a, (deoarece lipsete apostroful din faa lui b) valoarea 4. Deci, operaia efectuat este: a=4 i nu b=4! Valoarea lui b rne a dar a nu mai este acum 3, ci 4 i, n consecin, o evaluare (dubl) a lui b va conduce la rezultatul egal cu 4.

Schematic, cele 3 instruciuni pot fi reprezentate ca n figura 3.1.

O atribuire ca cea descris mai sus se numete atribuire indirect i este util cnd dorim s iniializm simboluri ale cror nume nu le cunoatem dar tim c ele sunt valori ale altor simboluri ale cror nume l cunoatem. 3.2. 3.3. Structuri de liste n LISP i PROLOG Listele sunt nlnuiri de celule care pot fi la rndul lor atomi sau liste. Acestea pot fi apoi grupate n alte liste cu structuri complexe oferind astfel utilizatorului posibilitatea manipulrii unor obiecte cu structuri ierarhizate.

n LISP listele sunt reprezentate ntre paranteze rotunde, iar elementele listei sunt separate fie prin spaii fie prin virgule.

Exemplu: (1,2,3) (1 (2 3) 4 ((5))) n limbajul LISP, o iniializare a unui simbol l cu o list se realizeaz utiliznd

instruciunea set sau setq: - (setq l (1 2 3 4)) (1 2 3 4) - (set l1 (1 (2 3) 4 ((5) 6 (7)))) (1 (2 3) 4 ((5) 6 (7))) Prin ultima instruciune am fcut ca simbolul l1 s pointeze ctre o list

imbricat a crei structur poate fi reprezentat ca n figura 3.2.

a 3

b a 3

b a 4

Fig. 3.1 Prezentarea schematica a instruciunilor

3.3.1. Funciile car, cdr, c..r Acste funcii sunt utilizate pentru a pune n eviden anumite elemente sau subliste ale ueni liste argument. Funcia car retuneaz primul element al unei liste, fie c acesta este un atom sau o sub-list. Sintaxa: (car arg) Funcia cdr returneaz lista argumentelor din care a fost eliminat primul element. Deci, n mod sigur, rezultatul ntors va fi o list sau nil, n cazul n care lista argument are un singur element. Sintaxa: (cdr lista_argument) Exemplu: - (setq l (1 2 3)) (1 2 3) - (car l) 1 - (cdr l) (2 3) - l (1 2 3) Dup cum se observ aceste funcii sunt nedistructive, adic lista argument rmne nemodificat. De asemenea, s-a utilizet apostroful naintea listei introduse pentru a bloca evaluarea ei i pentru a o considera ca atare i nu ca o expresie evaluabil.

1 4

2 3 6

7

5

(1 (2 3) 4 ((5) 6 (7)))

Fig. 3.2. Reprezentarea unei structuri de liste

- (setq l ((1) 2)) ((1) 2) - (car l) (1) - (cdr l) (2) Dar aceste funcii se pot combina: - (car (cdr l)) (4) 2 Ordinea evalurii este cea invers fa de cea n care sunt scrise funciile; n cazul instruciunii anterioare, se evalueaz mai nti (cdr l) obinndu-se lista (2), iar apoi asupra acestui rezultat se aplic funcia car: (car (2)), iar rezultatul final este 2. Instruciunea (4) se mai poate scrie i astfel: - (cadr l) 2 adic se procedeaz la o compactare a succesiunii funciilor, respectnd ordinea de apariie a acestora. - (setq l (1 2 (3 4) 5)) (1 2 (3 4) 5) - (cdr (car (cdr (cdr l)))) (4) este echivalent cu: - (cdaddr l)

(4) S vedem cum a fost executat aceast instruciune: 1. (cdr l) (2 (3 4) 5) - lista cu 3 elemente: 2, (3 4), 5; 2. (cdr (cdr l)) ((3 4) 5) - lista cu 2 elemante: (3 4), 5; 3. (car (cdr (cdr l))) (3 4) - lista cu 2 elemente: 3,4; 4. (cdaddr l) (4) - lista cu 1 element: 4; Observaie: numrul maxim de funcii car i/sau cdr ce pot fi compactate ntr-o singur funcie c..r este patru: cXXXXr. 3.4. Probleme propuse

1. S se iniializeze simbolurile l1, l2 i l3 cu urmtoarele structuri de liste, reprezentate n fig. 3.3, fig. 3.4, fig. 3.5

7

6

5

4 3

2 1

8

Fig. 3.4. Lista l2

1

4

3

2

Fig. 3.3 Lista l1

2. Pentru listele de mai sus s se scrie instruciunile care izoleaz urmatoarele

elemente respectiv sub-liste: Din l1: 3 l2: (6) 7 l3: 7

1

2

3

4

5

6

7

Fig. 3.5. Lista l3