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