Codificación CDR

En informática, la codificación CDR es una representación de datos comprimidos para listas enlazadas de Lisp . Fue desarrollada y patentada por el Laboratorio de Inteligencia Artificial del MIT , e implementada en hardware informático en varias máquinas Lisp derivadas del MIT CADR .

La codificación CDR es, de hecho, una idea bastante general; siempre que un objeto de datos A termina en una referencia a otra estructura de datos B , podemos colocar la estructura B en sí allí, superponiéndose y extendiéndose hasta el final de A. Al hacer esto, liberamos el espacio requerido por la referencia, que puede acumularse si se hace muchas veces, y también mejoramos la localidad de la referencia , mejorando el rendimiento en las máquinas modernas. La transformación es especialmente efectiva para las listas basadas en cons para las que fue creada; liberamos aproximadamente la mitad del espacio para cada nodo en el que realizamos esta transformación.

No siempre es posible realizar esta sustitución, porque puede que no haya un espacio libre lo suficientemente grande más allá del final de A. Por lo tanto, algunos objetos terminarán en una referencia real y otros con el objeto referenciado, y la máquina debe poder determinar, leyendo la celda final, cuál es. Esto se puede lograr con cierta ineficiencia en el software mediante el uso de punteros etiquetados , que permiten etiquetar específicamente como tal a un puntero en una posición final, pero se hace mejor en hardware.

En presencia de objetos mutables , la codificación CDR se vuelve más compleja. Si se actualiza una referencia para que apunte a otro objeto, pero actualmente hay un objeto almacenado en ese campo, el objeto debe reubicarse, junto con cualquier otro puntero a él. Estos movimientos no solo suelen ser costosos o imposibles, sino que con el tiempo provocan la fragmentación del almacenamiento. Este problema se suele evitar utilizando la codificación CDR solo en estructuras de datos inmutables .

• Mark Kantrowitz; Barry Margolin (eds.). "(2-9) ¿Qué es la codificación CDR?". FAQ: Preguntas frecuentes sobre Lisp . Advameg, Inc . Consultado el 9 de octubre de 2011 .
• L. Peter Deutsch: Una máquina LISP con programas muy compactos. IJCAI 1973, páginas 697 - 703
• Greenblatt, R., Informe de progreso de la máquina LISP, memo 444, AILab., MIT, Cambridge, Mass., agosto de 1977.
• L. Peter Deutsch: Experiencia con un sistema Interlisp microprogramado. MICRO 11: Actas del 11.º taller anual sobre microprogramación, noviembre de 1978, páginas 128-129
• Allen, John (1978). La anatomía del ceceo . McGraw-Hill.Páginas 399-401