Cflp

Laborator

Facultatea de Automatica si Calculatoare 

Departamentul de Calculatoare

 

Home Lucrarea 1 Lucrarea 2 Lucrarea 3 Lucrarea 4 Lucrarea 5 Proiect
  Lucrarea 6 Lucrarea 7 Lucrarea 8 Lucrarea 9 Lucrarea 10  

 

      Lucrarea 2
 

 

 

 

 

 

Subiecte

 

 

 

 

 

 

Scopul acestui capitol este să explice crearea de noi proceduri şi realizarea evaluărilor condiţionate.

 

Recapitulând, termenii de program, procedură şi primitivă au sensuri puţin diferite. Un program este o colecţie de proceduri, o procedură specifică felul în care se face un calcul iar o

primitivă este o procedură predefinită de limbaj.

 

DEFUN permite construirea de noi proceduri

Sintaxa:

(DEFUN <numele procedurii>

(<parametru 1> <parametru 2> ... <parametru n>)

<corpul procedurii>)

 

DEFUN nu îşi evaluează argumentele, ci doar stabileşte o procedură care va putea fi mai târziu utilizată. Numele procedurii trebuie să fie un simbol. Lista ce urmează după numele procedurii se numeşte lista de parametrii. Când o procedură va fi apelată împreună cu

argumentele sale într-o expresie simbolică, valoarea fiecărui parametru din procedură va fi determinat de valoarea agrumentului corespunzător din expresie.

 

De exemplu procedura următoare transformă temperatura dată din grade Fahrenheit în grade Celsius:

 

(defun f-to-c (temp)

(/ (- temp 32) 1.8))

f-to-c

 

DEFUN va returna numele funcţiei ce tocmai a fost definită, dar partea utilă se realizează prin efecte laterale. La apel valoarea argumentului devine valoarea temporară a parametrului procedurii.

 

- Procesul de pregătire a spaţiului de memorie pentru valorile parametrilor se numeşte LEGARE. Parametrii sunt legaţi la apelul procedurilor.

 

- Procesul de stabilire a unei valori se numeşte ATRIBUIRE. LISP întotdeauna atribuie valori parametrilor imediat după legare.

 

(defun exchange (pair)

(list (cadr pair) (car pair))) ; Inversează elementele

exchange

 

Comentariile în LISP se realizează cu ; De la ; până la sfârşitul liniei este comentariu.

 

Probleme

 

1. Unii sunt deranjaţi de numele primitivelor critice CAR, CDR şi CONS. Definiţi noi proceduri my-first, my-rest şi construct care realizează acelaşi lucru. Puteţi defini şi my-second, my-third,etc.

 

2. Definiţi rotate-left care primeşte o listă ca argument şi returnează o nouă listă în care primul element al listei de intrare este ultimul element al listei returnate.

 

(rotate-left '(a b c))

(b c a)

(rotate-left (rotate-left '(a b c)))

(c a b)

 

3. Definiţi rotate-right.

 

4. Un palindrom este o listă care conţine aceeaşi secvenţă de elemente atunci când este citită atât de la stânga la dreapta cât şi de la dreapta la stânga. Definiţi palindrom care primeşte o listă ca argument şi returnează un palindrom de lungime dublă.

 

5. Definiţi ec2 care primeşte trei parametrii a, b şi c şi returnează o listă ce conţine cele două rădăcini ale ecuaţiei de gradul doi a*x^2+b*x+c=0, folosind formula:

 

          -b+-sqrt(b*b-4*a*c)

    x= -----------------------------

                    2*a

 

PREDICATELE sunt proceduri ce returnează valoare de adevăr

 

Definiţii mai complicate necesită folosirea unor proceduri numite predicate. Un predicat este o procedură care returnează o valoare ce semnalează adevărat sau fals. Fals este întotdeauna semnalat de nil. Adevărat este deseori semnalat de un simbol special t, dar practic orice diferit de nil semnalează adevărat.

 

Obs: t şi nil sunt simboluri speciale, valorile lor fiind legate tot la t şi nil. Astfel valoarea lui t este t şi valoarea lui nil e nil.

 

ATOM este un predicat care testează dacă argumentul este un atom.

LISTP testează dacă argumentul este o listă.

 

Dacă avem:

(setq digits '(zero unu doi trei patru cinci sase sapte opt noua))

ATOM şi LISTP lucrează în felul următor:

 

(atom 'digits)

t

(atom 'cinci)

t

(atom digits)

nil

(atom '(zero unu doi trei patru cinci sase sapte opt noua))

nil

(listp 'digits)

nil

(listp 'cinci)

nil

(listp digits)

t

(listp '(zero unu doi trei patru cinci sase sapte opt noua))

t

 

EQUAL ia două argumente şi returnează t dacă sunt egale, altfel returnează nil:

 

(equal digits digits)

t

(equal 'digits 'digits)

t

(equal digits '(zero unu doi trei patru cinci sase sapte opt noua))

t

(equal digits 'digits)

nil

 

Predicatul = verifică dacă două numere sunt egale.

(= 3.14 2.71)

nil

(= (* 5 5) (+ (* 3 3) (* 4 4)))

t

 

Trebuie să subliniem acum o caracteristică foarte importantă:

- nil şi lista vidă () sunt complet echivalente: nil == (), ele satisfac predicatul EQUAL:

(equal nil '())

t

 

Obs:

- prin convenţie lista vidă este tipărită ca nil.

- pot apare erori de programare din cauză că (atom '()) este t. Aceasta deoarece nil este considerat atom.

 

Lista vidă este singura expresie care este atât listă cât şi atom. Atât (atom nil) cât şi (listp nil) returnează t.

 

Predicatul NULL verifică dacă argumentul este lista vidă:

(null '())

t

(null t)

nil

(null digits)

nil

(null 'digits)

nil

 

Predicatul MEMBER testează dacă un atom este elementul unei liste.

(member <atom> <lista>)

 

Ar fi natural ca member să returneze t dacă atomul aparţine listei. De fapt member returnează fragmentul din listă care începe cu atomul găsit. Ideea este de a returne ceva care este diferit de nil şi ar putea fi util mai departe.

 

(member 'cinci digits)

(cinci sase sapte opt noua)

(member 'zece digits)

nil

 

Primul argument trebuie să fie un element în primul nivel al celui de al doilea argument, nu "îngropat" undeva în listă:

 

(member 'cinci '((zero doi patru sase opt) (unu trei cinci sapte)))

nil

 

În exemplul următor se exploatează faptul că MEMBER returnează ceva util:

 

(length (cdr (member 'cinci digits)))

4

 

Pentru exemplele următoare vom stabili:

 

(setq zero 0 unu 1 doi 2 trei 3 patru 4 cinci 5 sase 6 sapte 7 opt 8 noua 9)

9

 

Predicatul NUMBERP testează dacă argumentul este un număr:

 

(numberp 3.14)

t

(numberp cinci)

t

(numberp 'cinci)

nil

(numberp digits)

nil

(numberp 'digits)

nil

 

Predicatele < şi > aşteaptă ca argumentele să fie numere şi testează dacă sunt ordonate strict descrescător sau crescător:

(> cinci 2)

t

(> 2 cinci)

nil

(< 2 cinci)

t

(< 2 2)

nil

(> cinci patru trei doi unu)

t

(> trei unu patru)

nil

(> 3 1 4)

nil

 

Predicatul ZEROP testează daca argumentul este numărul zero.

(zerop zero)

t

(zerop 'zero)

error

(zerop cinci)

nil

 

Predicatul MINUSP testează dacă un număr este negativ:

(minusp unu)

nil

(minusp (- unu))

t

(minusp zero)

nil

 

Predicatul EVENP testează dacă un număr este par:

(evenp (* 9 7 5 3))

nil

 

Observaţi că majoritatea predicatelor folosesc la sfâsitul numelui P ca mnemonică pentru predicat. Excepţie face ATOM.

 

 

Probleme

 

6. Definiţi propria versiune a predicatului EVENP. Puteţi folosi primitiva REM care returnează restul împărţirii întregi a două numere.

 

7. Definiţi predicatul PALINDROMP care testează dacă argumentul este un palindrom.

 

8. Definiţi predicatul NOT-REALP care ia trei parametrii şi returnează t dacă b*b-4*a*c < 0.

 

 

Predicate logice

 

NOT returnează t doar dacă argumentul este nil.

 

(not nil)

t

(not t)

nil

(setq pets '(dog cat))

(not (member 'dog pets))

nil

(not (member ţiger pets))

t

 

AND returnează diferit de nil doar dacă toate argumentele sunt diferite de nil. OR returnează diferit de nil dacă cel putin unul din argumente este diferit de nil. Ambele iar orice număr de

argumente.

 

(and t t nil)

nil

(or t t nil)

t

(and (member 'dog pets) (member ţiger pets))

nil

(or (member 'dingo pets) (member ţiger pets))

nil

 

Argumentele pentru AND şi OR nu sunt tratate în mod standard:

- AND îşi evaluează argumentele de la stânga la dreapta. Daca întâlneşte nil se opreşte, argumentele rămase nu mai sunt evaluate! Altfel AND returnează valoarea ultimului argument.

- OR îşi evaluează argumentele de la stânga la dreapta. Daca întâlneşte ceva diferit nil se opreşte, argumentele rămase nu mai sunt evaluate! Altfel OR returnează nil.

Ambele predicate returnează ultima valoare calculată în caz de

succes.

 

(and (member 'dog pets) (member 'cat pets))

(cat)

(or (member 'dog pets) (member ţiger pets))

(dog cat)

 

Selectarea alternativelor. Primitiva COND

 

Sintaxa lui COND este:

(COND (<test 1> ... <rezultat 1>)

(<test 2> ... <rezultat 2>)

...

(<test n> ... <rezultat n>))

Simbolul COND este urmat de un număr oarecare de liste fiecare conţinând un test şi o expresie de evaluat. Fiecare listă se numeşte o clauză. Ideea este de a parcurge clauze evaluând testul fiecăreia, pâna când valoarea unui test este diferită de nil, în

acest caz evaluânduse şi restul clauzei.

Există două cazuri speciale:

- dacă testul nici unei clauze nu este diferit de nil, COND returnează nil.

- dacă clauza conţine doar testul se returnează valoarea testului.

 

În exemplul următor, presupunând că L este o listă, rezultatul este simbolul EMPTY dacă L este vidă altfel NOT-EMPTY:

 

(cond ((null L) 'EMPTY)

(t 'NOT-EMPTY))

 

Deasemenea se poate scrie:

(cond (L 'NOT-EMPTY)

(t 'EMPTY))

 

Observaţi că NULL şi NOT sunt practic primitive echivalente:

(NOT X) == (NULL X)

 

 

Probleme

 

9. Exprimaţi (abs X), (min A B) şi (max A B) cu ajutorul lui COND.

 

10. Exprimaţi (not U), (or X Y Z) şi (and A B C) cu ajutorul lui COND.

 

11. Care este valoarea următoarei forme:

(cons (car nil) (cdr nil))

 

COND şi DEFUN

 

Vrem să definim o procedură care primeşte două argumente: un atom şi o listă, şi returnează o listă având atomul pus în capul listei doar dacă nu este deja în listă. Altfel returnează lista

nemodificată.

(defun adjoin (item bag)

(cond ((member item bag) bag) ; este deja în listă?

(t (cons item bag)))) ; adaugă in capul listei.

adjoin

 

t va apărea de multe ori ca test pentru ultima clauză a unui COND prentru a defini ce trebuie făcut dacă nici o clauză nu a fost evaluată.

 

Probleme

 

12. Definiţi MEDIAN-OF-THREE, o procedură care primeşte trei

argumente numerice şi returnează pe cel din mijloc ca valoare

(adică pe cel care nu e cel mai mic şi nu e cel mai mare).