En programación informática , CAR ( car) / k ɑːr / yCDR(cdr) (/ ˈ k ʌ d ər / o/ ˈ k ʊ d ər / ) son operaciones primitivas sobreconsexpresiones Sno atómicas") introducidas en ellenguaje de programación Lisp. Una celda cons está compuesta por dospunteros; lacarextrae el primer puntero y lacdrextrae el segundo.
Por lo tanto, la expresión evalúa a , y evalúa a .(car (cons x y))x(cdr (cons x y))y
Cuando se utilizan celdas cons para implementar listas enlazadas simples (en lugar 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 este motivo, a las operaciones a veces se les dan los nombres first y rest o head y tail .
Lisp se implementó originalmente en la computadora IBM 704 , a fines de la década de 1950.
La explicación popular de que CAR y CDR significan "Contenido del registro de direcciones" y "Contenido del registro de decremento" [1] no coincide del todo con la arquitectura del IBM 704; el IBM 704 no tiene un registro de direcciones accesible para el programador y los tres registros de modificación de direcciones son llamados "registros de índice" por IBM.
El 704 y sus sucesores tienen una longitud de palabra de 36 bits y un espacio de dirección de 15 bits . Estas computadoras tenían dos formatos de instrucciones , uno de los cuales, el Tipo A, tenía un prefijo de código de operación corto de 3 bits y dos campos de 15 bits separados por una etiqueta de 3 bits. El primer campo de 15 bits era la dirección del operando y el segundo contenía un decremento o conteo. La etiqueta especificaba uno de los tres registros de índice . La indexación era un proceso sustractivo en el 704, por lo tanto, el valor que se cargaba en un registro de índice se llamaba "decremento". [2] : p. 8 El hardware del 704 tenía instrucciones especiales para acceder a los campos de dirección y decremento en una palabra. [2] : p. 26 Como resultado, era eficiente usar esos dos campos para almacenar dentro de una sola palabra los dos punteros necesarios para una lista. [3] : Intro.
Por lo tanto, "CAR" significa "Contenido de la parte de dirección del registro". El término "registro" en este contexto se refiere a "ubicación de memoria". [4] [5]
Los precursores [6] [7] de Lisp incluían funciones:
car("contenido de la parte de dirección del número de registro"),cdr("contenido de la parte de decremento del número de registro"),cpr("contenido de la parte del prefijo del número de registro"), yctr("contenido de la parte de etiqueta del número de registro"),cada uno de los cuales tomó una dirección de máquina como argumento, cargó la palabra correspondiente desde la memoria y extrajo los bits apropiados.
La macro ensambladora 704 para fue: [8] [9] [10]car
LXD JLOC 4 # C( Decremento de JLOC ) → C( C ) # Carga el Decremento de la ubicación JLOC en el Registro de índice C CLA 0 , 4 # C( 0 - C( C ) ) → C( AC ) # El registro AC recibe la dirección de inicio de la lista PAX 0 , 4 # C( Dirección de AC ) → C( C ) # Carga la Dirección de AC en el Registro de índice C PXD 0 , 4 # C( C ) → C( Decremento de AC ) # Borra AC y carga el Registro de índice C en el Decremento de AC La macro ensambladora 704 para cdrfue: [8] [9] [10]
LXD JLOC 4 # C( Decremento de JLOC ) → C( C ) # Carga el Decremento de la ubicación JLOC en el Registro de índice C CLA 0 , 4 # C( 0 - C( C ) ) → C( AC ) # El registro AC recibe la dirección de inicio de la lista PDX 0 , 4 # C( Decremento de AC ) → C( C ) # Carga el Decremento de AC en el Registro de índice C PXD 0 , 4 # C( C ) → C( Decremento de AC ) # Borra AC y carga el Registro de índice C en el Decremento de AC Una palabra de máquina podría ser reensamblada por cons , que tomaba cuatro argumentos ( a , d , p , t ).
Las partes de prefijo y etiqueta se eliminaron en las primeras etapas del diseño de Lisp, dejando CAR, CDR y un CONS de dos argumentos. [3]
A las composiciones de cary cdrse les pueden dar nombres cortos y más o menos pronunciables de la misma forma. En Lisp, (cadr '(1 2 3))es el equivalente de (car (cdr '(1 2 3))); su valor es 2. De manera similar, (caar '((1 2) (3 4)))(pronunciado / ˈ k eɪ ɑːr / ) es lo mismo que (car (car '((1 2) (3 4)))); su valor es 1. La mayoría de los Lisp, por ejemplo Common Lisp y Scheme , definen sistemáticamente todas las variaciones de dos a cuatro composiciones de cary cdr.
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 cary cdr. Estas se nombran de diversas formas firsty rest, heady tail, etc. En Lisp, sin embargo, la celda cons no se usa solo para construir listas enlazadas sino también para construir estructuras de pares y pares anidados, es decir, el cdrde una celda cons no necesita ser una lista. En este caso, la mayoría de los otros lenguajes proporcionan primitivas diferentes ya que típicamente distinguen estructuras de pares de estructuras de listas ya sea tipificada o semánticamente. Particularmente en lenguajes tipificados, listas, pares y árboles tendrán todas diferentes funciones de acceso con diferentes firmas de tipo: en Haskell , por ejemplo, cary cdrse convierten en fsty sndcuando se trata de un tipo de par. Los análogos exactos de cary cdrson por lo tanto raros en otros lenguajes. Clojure usa firsten lugar de cary nexto resten lugar de cdr. Logo , por otro lado, usa firsten lugar de cary butfirsten lugar de cdr.