En la programación de ordenadores , CAR ( car
) / k ɑr / ( escuchar ) y CDR ( cdr
) ( / k ʌ d ər / ( escuchar ) o / k ʊ d ər / ( escuchar ) ) son operaciones primitivas sobre Contras células (o " expresiones S no atómicas ") introducidas en el lenguaje de programación Lisp . Una celda de contras se compone de dos punteros; la operación de automóvil extrae el primer puntero y la operación de cdr extrae el segundo.
Por lo tanto, la expresión se evalúa y se evalúa como .(car (cons x y))
x
(cdr (cons x y))
y
Cuando se utilizan celdas de contras para implementar listas enlazadas individualmente (en lugar de árboles y otras estructuras más complicadas ), la operación del automóvil 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 primero y resto o cabeza y cola .
Etimología
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 al 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 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 una disminución o recuento. 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á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 en una sola palabra los dos punteros necesarios para una lista. [3] : Introducción.
Por tanto, "CAR" es "Contenido de la parte 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 decreciente del número de registro"),cpr
("contenido de la parte del prefijo del número de registro"), yctr
("contenido de la etiqueta parte 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.
704 macros
La macro del ensamblador 704 para car
fue: [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 de CA recibe la dirección de inicio de la lista PAX 0 , 4 # C (Dirección de CA) → C (C) # Carga la dirección de CA en el Registro de índice C PXD 0 , 4 # C (C) → C (Decremento de CA) # Borra CA y carga el Registro de índice C en la disminución de CA
La macro del ensamblador 704 para cdr
fue: [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 de CA recibe la dirección de inicio de la lista PDX 0 , 4 # C (Decremento de CA) → C (C) # Carga el Decremento de CA en el Registro de índice C PXD 0 , 4 # C (C) → C (Decremento de CA) # Borra CA y carga el Registro de índice C en la disminución de CA
Una palabra de máquina se puede reensamblar mediante contras , que requiere 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]
Composiciones
A las composiciones de car
y cdr
se 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
. Del mismo modo, (caar '((1 2) (3 4)))
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 car
y cdr
.
Otros lenguajes informáticos
Muchos lenguajes (particularmente los lenguajes funcionales y los lenguajes influenciados por el paradigma funcional ) utilizan una lista enlazada como estructura básica de datos y proporcionan primitivas o funciones similares a car
y cdr
. Estos se nombran de diversas formas first
y rest
, head
y tail
, etc. En Lisp, sin embargo, la celda contras no se usa solo para construir listas enlazadas sino también para construir estructuras de pares y pares anidados, es decir, la cdr
celda de contras no necesita ser una lista. En este caso, la mayoría de los otros lenguajes proporcionan primitivas diferentes, ya que normalmente distinguen las estructuras de pares de las estructuras de lista, ya sea de forma tipográfica o semántica. Particularmente en los lenguajes tipados, las listas, los pares y los árboles tendrán diferentes funciones de acceso con diferentes firmas de tipo: en Haskell , por ejemplo, car
y se cdr
convertirán fst
y snd
cuando se trate de un tipo de par. Análogos exactos de car
y, por cdr
lo tanto, son raros en otros idiomas. Clojure usa primero en lugar de car y luego o resto en lugar de cdr.
Referencias
- ^ Véase, por ejemplo, Mitchell, John C. (2003), Conceptos en lenguajes de programación , Cambridge University Press, págs. 28-29, ISBN 9781139433488, Sección 3.4, Innovaciones en el diseño de Lisp . La referencia identifica el IBM 704 y explica correctamente la dirección y la parte decreciente de una celda de contras, pero luego omite la "parte de" en la explicación de McCarthy.
- ^ a b 704 - máquina de procesamiento de datos electrónicos http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
- ^ a b McCarthy, John (12 de febrero de 1979). "Historia de Lisp" .
- ^ McCarthy (1960 , págs. 26-27) analiza los registros en la lista libre y en la recolección de basura.
- ^ McCarthy, John; Abrahams, Paul W .; Edwards, Daniel J .; Hart, Timothy P .; Levin, Michael I. (1985), LISP 1.5 Programmer's Manual (segunda edición), Cambridge, Massachusetts: MIT Press, ISBN 978-0-262-13011-0, página 36, describe las celdas contra como palabras con campos de "dirección" y "disminución" de 15 bits.
- ^ Un lenguaje de procesamiento de listas compilado por Fortran
- ^ Un lenguaje de procesamiento de listas compilado por Fortran; Transcripción HTML
- ^ a b Porciones de NILS 'LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html
- ^ a b MIT AI Lab Memo 6 ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
- ^ a b CODIFICACIÓN para la COMPUTADORA MIT-IBM 704 ftp://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
- Notas
- Russell, Steve . "Programas de escritura y depuración" (PDF) . Centro de Computación RLE y MIT. Publicaciones CSAIL y archivo digital (Memo). AI Memo , no. 6. Cambridge , Massachusetts: Laboratorio de Inteligencia Artificial del MIT . OCLC 35415961 . Consultado el 20 de julio de 2017 .
- Faase, Frans (10 de enero de 2006). "El origen de CAR y CDR en LISP" .
- Graham, Paul (1996). ANSI Common Lisp . Prentice Hall. ISBN 978-0-13-370875-2.
- Barski, Conrad (2010). Land of Lisp: aprende a programar en Lisp, ¡un juego a la vez! . San Francisco, CA: No Starch Press, Inc. ISBN 978-1-59327-281-4.