LISP face parte din clasa limbajelor funcţionale.

LISP = LISt Programming.

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

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.

În LISP procedura este specificată întotdeauna în capul listei

urmată de argumente => notaţia prefix.

- O PROCEDURA 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.

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.

Expresie

/\

/  \

/     \

/       \

/          \

Atom          Listă

/\                

/  \                

/    \                

/        \                

Număr        Simbol                

/\                             

/   \                             

/       \                             

/           \                             

Întreg        Real                            

Probleme

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

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

Având expresia:

(A B C)

(CAR '(A B C))    ;  ' == QUOTE inhibă evaluarea

returnează

A

iar

(CDR '(A B C))

returnează

(B C)

Caracterul '  inhibă evaluarea unei liste.

(CAR L) - returnează primul element al listei L

(CDR L) - returnează lista formată din restul elementelor

(CAR '((A B) C))

(A B)

(CDR '((A B) C))

(C)

                                      -------

                             ----->| CAR |----> A

                             |        -------

             (A B C) ==|

                             |        -------

                             ----->| CDR |----> (B C)

                                      -------

Al doilea element al listei se obţine astfel:

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

B

'(A B C) == (QUOTE (A B C))

Probleme

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)))))

4. Evaluaţi:

(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))))))

5. Scrieţi secvenţ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)

(cadar '((((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:

(SETQ L '(A B))

(A B)

L

(APPEND L L)

(A B A B)

(APPEND '(A) '() '(B) '())

(A B)

LIST construieşte o listă din argumentele sale:

(LIST L L)

((A B) (A B))

(LIST 'L L)

(L (A B))

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

(CONS A '(B C))

(A B C)

(CONS (CAR L) (CDR L)) == L

                             -------

                    ----->| CAR |----> A ---------

                    |         -------                   |        --------

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

                    |        -------                    |        --------

                    ----->| CDR |----> (B C) -----

                             -------

Urmăriţi evaluările:

(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

(LIST 'L L)

(L (A B))

(CONS 'L L)

(L A B)

Probleme

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 '(A B))

2

(LENGTH '((A B) (C D)))

2

(LENGTH L)

2

(LENGTH (APPEND L L))

4

REVERSE inversează o listă:

(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. noua> <expr. veche> <lista>)

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

(A A C)

LAST returnează o listă ce conţine ultimul element:

(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 număr? >-------->| Returnează numărul. |

  --------------------           ---------------------------        -----------------------------------

          |                                  |

          |                                  | Nu

          | Nu                            V

          |                  -------------------------------

          |                  | Ret. valoarea lui S. |

          |                  -------------------------------

         V

   ------------------------------                -------------------------------

< Este QUOTE primul >     Da    | Returnează al doilea |

< atom din S?            >----------->| element din S.          |

  -------------------------------                --------------------------------

          |

          | Nu

         V

  -------------------------               -----------------------

< Indică primul      >    Da     | Nu evaluază   |

< element din S o  >---------->| argumentele   |

< tratare specială? >            | - caz special. |

  --------------------------              -----------------------

         |

         | Nu

        V

 ----------------------------------------

 | Foloseşte EVAL pe toate |

 | elementele lui S în           |

 | afară de primul.               |

 -----------------------------------------

                 |

                 |

                V

 ----------------------------------

 | Aplică primul element  |

 | al lui S valorilor            |

 | rezultate şi returnează |

 | rezultatul.                   |

 ------------------------------------

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

NOUA 9)

ZERO

0

OPT

8

(SETQ A 'B)

B

(SETQ B 'C)

C

A

B

B

C

(EVAL A)

C