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 2

Subiecte

LISP

CAR, CDR

APPEND,
LIST,
CONS

LENGTH, LAST, REVERSE, SUBST

Probleme

L I S P

�n LISP procedurile şi datele au aceeaşi structură: lista generalizată.

obiectele fundamentale se numesc ATOMI;
grupe de atomi şi liste formează LISTE;
atomii şi listele sunt numite EXPRESII SIMBOLICE.

LISP �nseamnă manipulare de simboluri.

�n LISP procedura este specificată �ntotdeauna �n capul listei urmată de argumente => notaţia prefix.

o PROCEDURĂ este o entitate de bază care specifică felul �n care se realizează un lucru;
o procedură predefinită de limbaj se numeşte PRIMITIVA
o colecţie de proceduri care lucrează �mpreună se numeşte PROGRAM;
o descriere abstractă a unei proceduri sau a unui program, neexprimată �n termenii unui anume limbaj de programare, se numeşte ALGORITM.

C�nd o paranteză st�ngă şi una dreaptă �nconjoară ceva, numim rezultatul o listă şi vorbim de elementele sale.

De exemplu lista (+ 3.14 2.71) are trei elemente: +, 3.14 şi 2.71.

Exemple LISP

LISP evaluează o listă presupun�nd că primul element este o procedură iar restul elementelor sunt parametrii.

(+ 3.14 2.71)
5.85
(* 9 3)
27
(/ 27 3)
9
(MAX 2 4 3)
4
(MIN 2 4 3)
2
(EXPT 2 3) ; ridicare la putere
8
(SQRT 4.0) ; rădăcină pătrată
2.0
(ABS -5)
5
(- 8)
-8
Consider�nd expresia:
(+ (* 2 2) (/ 2 2))
se observă uşor că se evaluează la 5.

Atomii de tipul: 27, 3.14 se numesc ATOMI NUMERICI.
Atomii de tipul: +, MAX se numesc ATOMI SIMBOLICI.

Formarea unei expresii în lisp:

                                         Expresie
                                               /\
                                              /  \
                                             /    \
                                            /      \
                                           /        \
                                     Atom      Lista
                                                     /\
                                                    /  \
                                                   /    \
                                                  /      \
                                          Numar    Simbol
                                              /\
                                             /  \
                                            /    \
                                           /      \
                                        �ntreg Real

Problema 1.

Identificaţi următoarele obiecte (atom, listă, nici una):

ATOM
(ACESTA ESTE UN ATOM)
(ACEASTA ESTE O LISTA)
((A B) (C D))
3
(3)
(LIST 3)
(/ (+ 3 1) (- 3 1))
)(
((()))
(() ())
((())
())( ((A B C

Problema 2.

Evaluaţi următoarele forme:

(/ (+ 3 1) (- 3 1))
(* (MAX 3 4 5) (MIN 3 4 5))
(MIN (MAX 3 1 4) (MAX 2 7 1))

Primitivele CAR şi CDR

(CAR L) - returnează primul element al listei L
(CDR L) - returnează lista formată din restul elementelor

Av�nd expresia: (A B C)
(CAR '(A B C))
returnează
A
Notă: Se observă că: '(A B C) == (QUOTE (A B C))şi functia QUOTE returneaza parametrul fucţiei.

Iar (CDR '(A B C)) returnează (B C).

CAR şi CDR

(CAR '((A B) C))
(A B)
(CDR '((A B) C))
(C)

                             -------
                    ----->| CAR |----> A ---------
                    |         -------                   |        --------
    (A B C) ==|                                   |==>| CONS |--> (A B C)
                    |        -------                    |        --------
                    ----->| CDR |----> (B C) -----
                             -------

Al doilea element al listei se obţine astfel:
(CAR (CDR '(A B C)))
B

Problema 3.

Evaluaţi următoarele forme:

(CAR '(P H W))
(CDR '(B K P H))
(CAR '((A B) (C D)))
(CDR '((A B) (C D)))
(CAR (CDR '((A B) (C D))))
(CDR (CAR '((A B) (C D))))
(CDR (CAR (CDR '((A B) (C D)))))
(CAR (CDR (CAR '((A B) (C D)))))

Problema 4.

Evaluaţi şi argumentaţi rezultatul obţinut:

(CAR (CDR (CAR (CDR '((A B) (C D) (E F))))))
(CAR (CAR (CDR (CDR '((A B) (C D) (E F))))))
(CAR (CAR (CDR '(CDR ((A B) (C D) (E F))))))
(CAR (CAR '(CDR (CDR ((A B) (C D) (E F))))))
(CAR '(CAR (CDR (CDR ((A B) (C D) (E F))))))
'(CAR (CAR (CDR (CDR ((A B) (C D) (E F))))))

Problema 5.

Scriecţi secvencţele de CAR şi CDR care scot simbolul C din expresiile:

(A B C D)
((A B) (C D))
(((A) (B) (C) (D)))
(A (B) ((C)) (((D))))
((((A))) ((B)) (C) D)
((((A) B) C) D)

Putem folosi primitive compuse de forma CXXR, CXXXR, unde X poate fi A (pentru CAR) sau D (pentru CDR).

(CADR '(A B C)) == (CAR (CDR '(A B C)))

Atomii simbolici pot avea valori Unui atom simbolic i se poate atribui o valoare (număr sau simbol sau listă) la care acel atom simbolic va fi evaluat. Acest lucru se realizează cu procedura SETQ (prin efect lateral!).

(SETQ L '(A B))
L
(A B)
'L
L
(CAR L)
A
(CDR L)
(B)

Procedurile APPEND, LIST şi CONS

APPEND uneşte liste.

APPEND
(SETQ L '(A B)) (A B) L (A B) (APPEND L L) (A B A B) (APPEND '(A) '() '(B) '()) (A B)

LIST construieşte o listă din argumentele sale:

LIST
(LIST L L) ((A B) (A B)) (LIST 'L L) (L (A B))

CONS inserează un nou prim element �ntr-o listă:

CONS
(CONS 'A '(B C)) (A B C) (CONS (CAR L) (CDR L)) ; == L (A B)

                             -------
                    ----->| CAR |----> A ---------
                    |         -------                   |        --------
    (A B C) ==|                                   |==>| CONS |--> (A B C)
                    |        -------                    |        --------
                    ----->| CDR |----> (B C) -----
                             -------

APPEND, LIST, CONS

Urmăriţi evaluăile:

(APPEND '(A B) '(C D))
(A B C D)
(LIST '(A B) '(C D))
((A B) (C D))
(CONS '(A B) '(C D))
((A B) C D)
(APPEND L L)
(A B A B)
(LIST L L)
((A B) (A B))
(CONS L L)
((A B) A B)
(APPEND 'L L)

Error ('L nu este o listă)
(LIST 'L L)
(L (A B))
(CONS 'L L)
(L A B)

Problema 6.

Evaluaţi formele:

(APPEND '(A B C) '())
(LIST '(A B C) '())
(CONS '(A B C) '())

Procedurile LENGTH, REVERSE, SUBST şi LAST

LENGTH returnează lungimea unei liste.

LENGTH
(LENGTH '(A B)) 2 (LENGTH '((A B) (C D))) 2 (LENGTH L) 2 (LENGTH (APPEND L L)) 4

REVERSE inversează o listă:

REVERSE
(REVERSE '(A B)) (B A) (REVERSE '((A B) (C D))) ((C D) (A B))

SUBST �nlocuieşte o expresie cu alta �ntr-o listă:

(SUBST <expr.nouă> <expr. veche> <listă>)

SUBST
(SUBST 'A 'B '(A B C)) (A A C)

LAST returnează o listă ce concţe ultimul element:

LAST
(LAST '(A B C)) (C) (LAST '((A B) (C D))) ((C D))

Evaluarea formelor

C�nd interpretorul LISP primeşte o formă o trimite primitivei EVAL, care evaluază toate argumentele după care apelează procedura din capul listei.

� --------------------�� �Da � -------------------------- �Da � -----------------------------------
< Este S atom? >---->< Este S numar? >-------->| Returneaza numarul. |
� -------------------- ��������� ---------------------------���� �� -----------------------------------
��������� |�������������������������������� �|
��������� | �������������������������������� | Nu
��������� | Nu �������������������������� V
��������� |����������������� ------------------------------- 
��������� | ���������������� | Ret. valoarea lui S. |
��������� |���������������� �-------------------------------
�������� V
�� ------------------------------ �������������� -------------------------------
< Este QUOTE primul > ��� Da�� �| Returneaza al doilea |
< atom din S? ���������� >----------->| element din S. �������� |
� -------------------------------�������������� �--------------------------------
��������� |
��������� | Nu
�������� V
� -------------------------������������� �-----------------------
< Indica primul ���� >�� �Da ��� | Nu evaluaza � |
< element din S o �>---------->| argumentele � |
< tratare speciala? > ���������� | - caz special. |
� --------------------------��� ��������� -----------------------
�������� |
�������� | Nu
������� V
�-----------------------------------------
�| Foloseste EVAL pe toate   |
�| elementele lui S �n �������� � |
�| afara de primul. ��������� �� �� |
�------------------------------------------
���������������� |
���������������� |
��������������� V
��------------------------------------
�| Aplica primul element �|
�| al lui S valorilor ���������� |
�| rezultate si returneaza |
�| rezultatul. ����������������� |
�------------------------------------

Exemple de evaluare

(SETQ ZERO 0 UNU 1 DOI 2 TREI 3 PATRU 4 CINCI 5 SASE 6 SAPTE 7 OPT 8 NOUA 9)

9
ZERO
0
OPT
8
(SETQ A 'B)
B
(SETQ B 'C)
C
A
B
B
C
(EVAL A)
C

Procedura EVAL provoacă �ncă o evaluare a argumentelor.

Probleme

Problema 1. Atomi şi liste.

Problema 2. Atomi simbolici. Funcţii.

Problema 3. CAR şi CDR 1.

Problema 4. CAR şi CDR 2.

Problema 5. CAR şi CDR 3.

Problema 6. APPEND şi LIST

Problema 7. Evaluaţi exemplele de la LENGTH, REVERSE, SUBST, LASTşi CONS

Problema 8. Evaluaţi exemplele de la Evaluarea formelor