Car e cdr

Introdotte nel linguaggio di programmazione Lisp, car e cdr (pronunciato /ˈkʌdər/ o /ˈkʊdər/) sono operazioni primitive che operano su liste concatenate composte da celle cons. Una cella cons è composta da due puntatori; l'operazione car estrae il primo puntatore e l'operazione cdr ne estrae il secondo.

Così, l'espressione (car (cons x y)) restituisce x e (cdr (cons x y)) restituisce y.

Quando le celle cons vengono usate per implementare liste singolarmente concatenate (piuttosto che alberi o altre strutture più complesse), l'operazione car restituisce il primo elemento della lista mentre cdr ne restituisce il resto. Per questo motivo queste operazioni vengono a volte chiamate first (primo) e rest (resto) o head (testa) e tail (coda).

Origine dei nomi car e cdr

In origine Lisp fu implementato su un computer IBM 704, nei tardi anni cinquanta. L'hardware del 704 aveva la possibilità di dividere le parole macchina di 36 bit in quattro parti, una "parte indirizzo" (address part) e una "parte decremento" (decrement part) di 15 bit ognuna e una "parte prefisso" (prefix part) e una "parte etichetta" (tag part) di tre bit ciascuna. Alcuni predecessori del Lisp inclusero funzioni chiamate car (abbreviazione di Contents of the Address part of Register number), cdr, cpr e ctr, ognuna delle quali prendeva come argomento un indirizzo macchina, ne caricava la corrispondente parola dalla memoria ed estraeva i bit appropriati. La macro assembly dell'IBM 704 per realizzare cdr era

LXD JLOC 4
CLA 0,4
PDX 0,4
PXD 0,4

Una parola macchina poteva poi venire riassemblata dalla funzione cons, che prendeva quattro argomenti ($a,d,p$ e $t$). Nelle prime fasi progettuali del Lisp, le parti prefisso ed etichetta vennero scartate, lasciando solo car, cdr e quindi una cons con soli due argomenti.

I nomi first e rest sono alternative moderne comuni a car e cdr per la loro maggiore chiarezza, ma, oltre che per motivi storici e di abitudine, car e cdr continuano a essere utilizzati anche perché offrono il vantaggio di poter esprimere loro corte composizioni attraverso funzioni equivalenti con nomi corti e più o meno pronunciabili. Per esempio, (cadr '(1 2 3)) è equivalente a (car (cdr '(1 2 3)); il suo valore è 2 (il primo elemento del resto di (1 2 3)). In modo simile, (caar '((1 2) (3 4))) è lo stesso di (car (car '((1 2) (3 4)))); il suo valore è 1. La maggior parte delle implementazioni Lisp imposta un limite massimo al numero di forme composte che supportano; il Common LISP e lo Scheme, per esempio, forniscono forme con fino a quattro ripetizioni di $a$ e $d$. Mentre non risulta chiaro se forme composte complesse come (cadadr ...) risultino per un occhio non allenato più semplici da leggere rispetto alla forma estesa (car (cdr (car (cdr ...)))), queste forme composte risultano però convenienti per certi usi idiomatici, come disassemblare liste che rappresentano codice. Per esempio, data un'espressione lambda come la seguente:

 (lambda (a b) (una-cosa) (una-altra-cosa))

un programmatore Lisp esperto interpreterebbe

(let ((p1 (caadr form))
    (p2 (cadadr form))
    (body (cddr form))
...)

come l'estrazione del primo e del secondo parametro ($a$ e $b$) in $p1$ e $p2$ e l'estrazione della lista contenente il corpo dell'espressione lambda in body. Questo genere di "destrutturizzazione di una lista" è piuttosto comune, specialmente quando si scrivono macro, e le implementazioni Lisp moderne, come il Common Lisp, forniscono agevolazioni per realizzarle in maniera diretta. In Common Lisp, quel codice verrebbe espresso utilizzando la macro destructuring-bind come:

(destructuring-bind ((p1 p2) &body body) (rest form)
...)

Bibliografia

• (EN) Russel, S. (undated, c. late 1950's) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
• (EN) Frans Faase, The origin of CAR and CDR in LISP, su iwriteiam.nl, 10 gennaio 2006.
• (EN) Paul Graham, ANSI Common Lisp, Prentice Hall, 1996, ISBN 0-13-370875-6.

Voci correlate

• Lisp
• Cons (funzione)

Collegamenti esterni

• (EN) Denis Howe, Contents of Address part of Register, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (EN) Denis Howe, Contents of Decrement part of Register, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL