Operat ,ii cu liste n Lisp [624918]

Operat ,ii cu liste ^ n Lisp
Bradea Octavia
PLF Avansat

Contents
1 Introducere 4
2 Despre limbajul Lisp 4
3 Expresii simbolice 4
3.1 Manipularea simbolurilor . . . . . . . . . . . . . . . . . . . . . 5
4 Liste 5
4.1 Reprezentarea listelor . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Operat ,ii cu liste . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2

Abstract
This is a simple paragraph at the beginning of the document. A
brief introduction to the main subject.
3

1 Introducere
2 Despre limbajul Lisp
LISP este un limbaj matematic formal, conceput ^ n anul 1956 de c atre John
McCarthy , numele lui deriv^ andu-se chiar din lucrul pe care este menit sa
^ l fac a: "LISt Processing", adica procesarea listelor. Limbajul LISP a fost
conceput ^ n principal pentru procesarea simbolic a a datelor. De-a lungul
timpului, a fost utilizat pentru teoria circuitului electric, logica matematic a,
calcule simbolice ^ n calculul diferent ,ial s ,i integral, precum s ,i creearea de
jocuri s ,i alte domenii ale inteligent ,ei articiale. LISP este diferit de celelate
limbaje de programare, deoarece toate datele sunt defapt expresii simbolice
denumite s ,i expresii S. Cea mai amre parte a memoriei este utilizat a pentru
a stoca aceste expresii sub forma de structuri de list a.
3 Expresii simbolice
Tipul elementar de expresie S este simbolul atomic. Aceste simboluri
sunt numite atomice, deorarece sunt luate ca un ^ ntreg s ,i nu pot
^ mp art ,ite ^ n caractere individuale.
Denition 1. Atom Un simbol atomic este un s ,ir de cel mult treizeci de
cifre s ,i litere majuscule; primul caracter trebuie s a e o liter a.
Exemple
Un alt tip de expresie S este lista.
Denition 2. Lista O list a este o expresie S care satisface predicatul
listp[x] = null[x] [not[atom[x]] / listp[cdr [x]]]
An S-expression of this form can be written (ml, m,, . . . mn), which stands
for the dot-notation expression (ml . (m, . . . . (mn NIL) . . . )) .
Exemple
Toate expresiile S sunt construite din simboluri atomice s ,i semnele de
punctuat ,ie: "(", ")" s ,i . . Pentru a forma expresii S de o complexitate mai
mare se vor combina mai multe expresii. Exemplu: code here…
Denition 3. Expresie S O expresie S este un simbol atomic sau este com-
pus a din mai multe elemente dup a cum urmeaz a: parantez a deschis a, o ex-
presie S, un punct, o expresie S si o parantez a ^ nchis a.
4

3.1 Manipularea simbolurilor
Manipularea simbolurilor se aseaman a lucrului cu cuvinte s ,i propozit ,ii. Dup a
cum am mentionat deja, atomii s ,i listele sunt expresii simbolice. A lucra cu
acestea ^ nseamna defapt, ^ n LISP, manipularea simbolurilor.
Un program de manipulare a simbolurilor foloseste expresiile simbolice pen-
tru a memora si a lucra cu date s ,i proceduri. Un astfel de program are
sect ,iuni care recunosc expresii simbolice particulare, le distruge pe cele vechi
s,i asambleaz a altele noi.
4 Liste
^In Lisp o list a se noteaz a ca un  sir de s-expresii separate prin spat ,ii  si ^ nchise
^ ntre paranteze. De exemplu:
( ) – lista vid a, notata s ,i cu nil;
( a b c d 10)
list a format a din cinci atomi, primii patru sunt nenumerici, iar ultimul este
numeric
( aceasta este ( o lista ) compusa ) – lista format a din patru elemente: doi
atomi, o list a (la r^ andul ei format a din doi atomi) s ,i ^ nc a un atom;
4.1 Reprezentarea listelor
Reprezentarea prin celule cons
Memoria unui computer obis ,nuit este format a din celule de memorie numero-
tate. Num arul unei anumite celule de memorie reprezint a adresa sa. Se poate
ca o celula de memorie sa cont ,in a adresa alteia, as ,adar, aceasta devine o list a.
Atomii s ,i listele pot  reprezentate ca s ,i colect ,ii de celule de memorie.
Listele sunt reprezentate prin notarea "caset a-s ,i-s ageat a", acum numit a s ,i
reprezentarea prin celule cons. Aceste reprezent ari constau ^ n grupuri de
c asut ,e cu pointeri ^ n st^ anga s ,i dreapta, pointerul din st^ anga reprezen^ and
chiar valoarea elementului din list a, iar pointerul din dreapta conecteaz a
membrii listei ^ ntre ei. O astfel de reprezentare se termin a cu simbolul " n"
sau cuv^ antul cheie "nil"; ^ nt^ alnirea acestora ^ nseamn a sfars ,itul listei.
Reprezentarea ^ n LISP a listei de mai sus, cu ajutorul specicatorului
"cons" se scrie dup a cum urmeaz a:
5

Figure 1: Reprezentarea listei ^ n celule de memorie
(cons t h i s
(cons i s
(cons a
(cons l i s t t n i l ) ) ) )
Se poate scrie o lista in LISP si cu ajutorul specicatorului "list"
(l i s t t h i s i s a l i s t t )
Liste cu punct
Celula cons ^ n care atat pointerul din st^ anga, c^ at s ,i pointerul din dreapta
indic a expresii-S atomice, poart a numele de pereche cu punct. O list a care
cont ,ine astfel de expresii este numit a list a cu punct.
Exemplu: pentru lista (1 2 3 . 4)
Figure 2: Reprezentarea listei cu punct
(cons 1
(cons 2
(cons 3 4 ) ) )
6

4.2 Operat ,ii cu liste
-ce e lista
-ce forma are
-elementele listei
-constantele t si nil
-car, cdr, cons
-structura interna : descriere arborescenta, simplicta, pe nivele
-functii pt liste
-comparatii intre cons, cad, car si functii
7