stringtranslate.com

CAR y CDR

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 .

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 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:

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.

704 macros

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]

Composiciones

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 ɑː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.

Otros lenguajes informáticos

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.

Referencias

  1. ^ 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 parte de dirección y decremento de una celda cons, pero luego omite la "parte de" en la explicación de McCarthy.
  2. ^ ab 704 - máquina electrónica de procesamiento de datos http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf
  3. ^ ab McCarthy, John (12 de febrero de 1979). "Historia de Lisp".
  4. ^ McCarthy (1960, págs. 26-27) analiza los registros en la lista libre y en la recolección de basura.
  5. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985), Manual del programador de LISP 1.5 (segunda edición), Cambridge, Massachusetts: MIT Press, ISBN 978-0-262-13011-0, página 36, ​​describe las celdas cons como palabras con campos de "dirección" y "decremento" de 15 bits.
  6. ^ Un lenguaje de procesamiento de listas compilado en Fortran
  7. ^ Un lenguaje de procesamiento de listas compilado en Fortran; transcripción HTML
  8. ^ ab Fragmentos de las PÁGINAS LISP DE NILS: http://t3x.dyndns.org/LISP/QA/carcdr.html
  9. ^ ab Memo 6 del laboratorio de IA del MIT https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf
  10. ^ ab CODIFICACIÓN para la COMPUTADORA MIT-IBM 704 http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf
Notas