CONS construieşte noi liste folosind celule libere

LISP păstrează o listă de celule libere din care se consumă la cerere celule. (La epuizarea celulelor libere se execută un algoritm "garbage collection").

CONS ia prima celulă din lista de celule libere şi îi modifică pointerul de legătură cu următoarea celulă.

Exemplu

Presupunem că avem

(setq exemplu '(b c))

Evaluarea lui

(cons ă exemplu)

va scoate din capul listei de celule libere o celulă al cărui conţinut va fi "a" iar pointerul către celula următoare va fi la adresa celulei al cărei conţinut este "b" din lista (b c). Se va retuna adresa celulei ce conţine pe "a" (capul noii liste).

APPEND construieşte o nouă listă prin copiere

Să presupunem că evaluăm expresiile:

(setq abc '(a b c))

(setq xyz '(x y z))

Avem acum două liste, (a b c) şi (x y z) al căror adresă de început este memorată de abc respectiv xyz.

Ce se întâmplă la evaluarea expresiei (setq abcxyz (append abc xyz)) ; ?

Ceea ce am fi tentaţi să credem, dar nu se întâmplă, este următorul lucru: lista (a b c) este legată de lista (x y z) prin faptul că pointerul ce indică celula următoare a lui "c" (care

iniţial este nil) va pointa începutul listei (x y z) (deci valoarea lui xyz), iar ceea ce retunează append este valoarea lui abc. Dacă lucrurile descrise mai sus s-ar întâmpla atunci după

evaluarea expresiei listele pointate de abc şi abcxyz vor fi identice lucru care nu se întâmplă.

Felul în care append lucrează este următorul: creează o nouă lista copiind lista (a b c) (folosind desigur celule libere), iar listei nou creeate îi modifică ultimul pointer legându-l la

inceputul liste (x y z), după care reurnează începutul noii liste.

Astfel primele trei celule din lista (a b c x y z) sunt copii ale celulelor din lista (a b c) pe când ultimele trei celule sunt exact celulele din lista (x y z).

NCONC, RPLACA, RPLACD şi DELETE

Aceste predicate alterează conţinutul celulelor de memorie şi trebuie folosite cu mare atenţie.

NCONC face exact ceea ce am fost tentaţi să credem că face APPEND. Concatenează două liste modificând ultima celulă a primei liste şi nu prin copiere.

(setq abcxyz (nconc abc xyz))

(a b c x y z)

abc

(a b c x y z)

xyz

NCONC, la fel ca şi APPEND, poate lua mai multe argumente alterând sfârşitul fiecărei liste în afară de ultima.

RPLACA primeşte două argumente din care primul trebuie să fie o listă. Alterează această listă înlocuind conţinutul primei celule cu al doilea argument. Numele provine de la RePLAce CAr.

RPLACD este complementar, alterează restul listei (pointerul către celula următoare al primei celule).

DELETE elimină apariţiile primului argument în primul nivel al celui de al doilea argument.

(delete ă '(a b b a b))

(b b b)

EQUAL diferă de EQL

Pentru EQL două liste sunt identice doar dacă sunt reprezentate în aceleaşi celule de memorie. Copiile nu sunt considerate identice de către EQL, dar sunt considerate egale de către EQUAL.

Probleme

1. REVERSE inversează o listă prin copiere. Scrieţi o procedură REV care inversează o listă fără să o copieze.