CAR y CDR

car y cdr son operaciones primitivas sobre las celdas cons (o "expresiones S no atómicas") introducidas en el lenguaje de programación Lisp. Una celda cons se compone de dos punteros, la operación car extrae el primer puntero, y la operación cdr extrae el segundo.

Por lo tanto, la expresión (car (cons x y)) se evalúa como x , y (cdr (cons x y)) se evalúa como y.

Cuando las celdas cons son usadas para implementar listas enlazadas simples (en vez de árboles y otras estructuras más complicadas), la operación car devuelve el primer elemento de la lista, mientras que cdr devuelve el resto de la lista. Por esta razón, a las operaciones a veces se le dan los nombres de first y rest o head y tail (primero y resto o cabeza y cola).

Lisp fue implementado originalmente en el computador IBM 704, a finales de los años 1950. El hardware del 704 tuvo un soporte especial para dividir una palabra de máquina de 36-bits en cuatro partes, una "address part" y "decrement part" ("parte dirección" y "parte decremento") de 15 bits cada una y una "prefix part" y "tag part" ("parte prefijo" y "parte tag") de tres bits cada una.

Precursores de Lisp incluye funciones:

• car abreviación de "Contents of the Address part of Register number" (Contenido de la parte dirección del número de registro),
• cdr "Contents of the Decrement part of Register number" (contenido de la parte decremento del número de registro),
• cpr "Contents of the Prefix part of Register number" (contenido de la parte prefijo del número de registro), y
• ctr "Contents of the Tag part of Register number" (contenido de la parte tag del número de registro),

cada uno de ellos tomaba una dirección de máquina como argumento, cargado la palabra correspondiente desde la memoria, y extrayendo los bits apropiados.

El macro de ensamblador del 704 para la instrucción cdr era:

LXD JLOC, 4
CLA 0,4
PDX 0,4
PXD 0,4[1]​

Una palabra de máquina puede ser reensamblada por cons, que tomaba cuatro argumentos (a, d, p, t).

En las etapas iniciales del diseño de Lisp, las partes prefijo y tag eran descartadas dejando CAR, CDR, y un CONS de dos argumentos.^[2]​

Los nombres alternativos first y rest, que se remontan al menos a 1959,^[3]​ a veces son preferidos a car y cdr. Sin embargo, car y cdr tienen la ventaja de que cortas composiciones de funciones pueden dar nombres cortos y más o menos pronunciables de la misma forma. En Lisp, (cadr '(1 2 3)) es equivalente a (car (cdr '(1 2 3))); su valor es 2 (el primer elemento del resto de (1 2 3) ). Similarmente, (caar '((1 2) (3 4))) es lo mismo que (car (car '((1 2) (3 4)))); su valor es 1. La mayoría de los Lisps establecen un límite en el número de formas compuestas que soportan; Common Lisp y Scheme proporcionan formas con hasta cuatro repeticiones de la a y d. Sin embargo, otras composiciones pueden ser fácilmente definidas por el usuario.

Muchos lenguajes (particularmente lenguajes funcionales y lenguajes influenciados por el paradigma funcional) usan una lista enlazada simple como una estructura de datos básica, y proporcionan primitivas o funciones similares a car y cdr. Estas son nombradas como first y rest, head y tail, etc. En Lisp, sin embargo, la celdas cons no sólo son usadas para construir listas enlazadas, sino también para construir estructuras par y par anidadas, es decir, la cdr de una celda cons no necesita ser una lista. En este caso, la mayoría de los otros lenguajes proporciona diferentes primitivas, pues ellos distinguen estructuras par de estructuras de lista sea tipeado o semánticamente. Particularmente en lenguajes tipeados, las listas, pares, y los árboles todos tienen diferentes funciones de acceso con firmas de tipo diferentes: en Haskell, por ejemplo, el car y cdr se convierten en fst y snd cuando se trata de un tipo par. Analogías exactas del car y cdr son, por lo tanto, raras en otros lenguajes.

Notas

• Russel, S. (undated, c. late 1950s) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
• Faase, Frans (10 de enero de 2006). «The origin of CAR and CDR in LISP». 
• Graham, Paul (1996). ANSI Common Lisp. Prentice Hall. ISBN 0-13-370875-6. 
• Barski, Conrad (2010). Land of Lisp : learn to program in Lisp, one game at a time!. San Francisco, CA: No Starch Press, Inc. ISBN 978-1-59327-281-4.