En programación informática , CAR ( car) / k ɑːr / ⓘ yCDR(cdr) ( / ˈ k ʌ d ər / ⓘ o / ˈ k ʊ d ər / ⓘ ) son operaciones primitivas encontrasexpresiones Sno atómicas") introducidas en ellenguaje de programación Lisp. Una celda de contras se compone de dospunteros; lacarextrae el primer puntero y lacdrextrae el segundo.
Por lo tanto, la expresión se evalúa como y se evalúa como .(car (cons x y))x(cdr (cons x y))y
Cuando se utilizan celdas cons para implementar listas enlazadas individualmente (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 esta razón, a las operaciones a veces se les da el nombre de primero y descanso o cabeza y cola .
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 IBM 704; el IBM 704 no tiene un registro de direcciones accesible para el programador y IBM denomina a los tres registros de modificación de direcciones "registros de índice".
El 704 y sus sucesores tienen una longitud de palabra de 36 bits y un espacio de direcciones de 15 bits . Estas computadoras tenían dos formatos de instrucción , 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 que el valor que se cargaría en un registro de índice se denominaba "decremento". [2] : pág. 8 El hardware 704 tenía instrucciones especiales para acceder a los campos de dirección y decremento en una palabra. [2] : pág. 26 Como resultado, fue eficiente usar esos dos campos para almacenar dentro de una sola palabra los dos punteros necesarios para una lista. [3] : Introducción.
Por tanto, "CAR" es "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 incluyeron funciones:
car("contenido de la parte de dirección del número de registro"),cdr("contenido de la parte decremental 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 de la memoria y extrajo los bits apropiados.
La macro del ensamblador 704 era : [8] [9] [10]car
LXD JLOC 4 # C( Decremento de JLOC ) → C( C ) # Carga el Decremento de 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 inicial 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 índice C en el decremento de AC La macro del ensamblador 704 cdrera: [8] [9] [10]
LXD JLOC 4 # C( Decremento de JLOC ) → C( C ) # Carga el Decremento de 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 inicial 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 índice C en el decremento de AC Una palabra de máquina podría volver a ensamblarse mediante cons , que requería 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 a (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 Lisps, por ejemplo Common Lisp y Scheme , definen sistemáticamente todas las variaciones de dos a cuatro composiciones de cary cdr.
Muchos lenguajes (particularmente los lenguajes funcionales y los lenguajes influenciados por el paradigma funcional ) utilizan una lista enlazada individualmente como estructura de datos básica y proporcionan primitivas o funciones similares a cary cdr. Estos se nombran de diversas formas first, y , etc. En Lisp, sin embargo, la celda de contras no se usa sólo para construir listas enlazadas sino también para construir estructuras de pares y pares anidados, es decir, la restcelda de contras no necesita ser una lista. En este caso, la mayoría de los demás lenguajes proporcionan primitivas diferentes, ya que normalmente distinguen las estructuras de pares de las estructuras de listas, ya sea de forma tipográfica o semántica. Particularmente en lenguajes escritos, las listas, los pares y los árboles tendrán diferentes funciones de acceso con diferentes firmas de tipo: en Haskell , por ejemplo, y se convierten en y cuando se trata de un tipo de par. Los análogos exactos de y son, por tanto, raros en otros idiomas. Clojure usa en lugar de y o en lugar de . Logo , por otro lado, utiliza en lugar de y en lugar de .headtailcdrcarcdrfstsndcarcdrfirstcarnextrestcdrfirstcarbutfirstcdr