common-lisp
Contras celdas y listas

Listas como convención

Algunos idiomas incluyen una estructura de datos de lista. Common Lisp, y otros idiomas de la familia Lisp, hacen un uso extensivo de las listas (y el nombre Lisp se basa en la idea de un procesador LISt). Sin embargo, Common Lisp no incluye realmente un tipo de datos de lista primitiva. En cambio, las listas existen por convención. La convención depende de dos principios:

1. El símbolo nil es la lista vacía.
2. Una lista no vacía es una celda de contras cuyo automóvil es el primer elemento de la lista y cuyo CDR es el resto de la lista.

Eso es todo lo que hay en las listas. Si has leído el ejemplo llamado ¿Qué es una celda de contras? , entonces sabes que una celda de contras cuyo coche es X y cuyo CDR es Y puede escribirse como (X. Y) . Eso significa que podemos escribir algunas listas basadas en los principios anteriores. La lista de los elementos 1, 2 y 3 es simplemente:

(1 . (2 . (3 . nil)))

Sin embargo, debido a que las listas son tan comunes en la familia de lenguajes Lisp, existen convenciones de impresión especiales que van más allá de la simple notación de par de puntos para las celdas de contras.

1. El símbolo nil también se puede escribir como () .
2. Cuando el cdr de una celda de contras es otra lista (ya sea () o una celda de contras), en lugar de escribir la celda de una cons con la notación de par de puntos, se utiliza la "notación de lista".

La notación de la lista se muestra más claramente mediante varios ejemplos:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

La idea es que los elementos de la lista se escriban en orden sucesivo entre paréntesis hasta que se alcance el cdr final de la lista. Si el cdr final es nulo (la lista vacía), entonces se escribe el paréntesis final. Si el cdr final no es nulo (en cuyo caso la lista se denomina lista impropia ), se escribe un punto y luego se escribe el cdr final.

¿Qué es una célula contras?

Una celda de contras, también conocida como un par de puntos (debido a su representación impresa), es simplemente un par de dos objetos. Una función de contras es creada por la función cons , y los elementos del par se extraen utilizando las funciones car y cdr .

(cons "a" 4)

Por ejemplo, esto devuelve un par cuyo primer elemento (que puede extraerse con un car ) es "a" , y cuyo segundo elemento (que puede extraerse con cdr ) es 4 .

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

Contras celdas se pueden imprimir en notación de par de puntos :

(cons 1 2)
;;=> (1 . 2)

Las celdas de contras también se pueden leer en notación de par de puntos, para que

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(La forma impresa de las celdas contras también puede ser un poco más complicada. Para más información, consulte el ejemplo sobre celdas cons en forma de listas).

Eso es; contras celdas son solo pares de elementos creados por la función cons , y los elementos pueden extraerse con car y cdr . Debido a su simplicidad, las celdas contras pueden ser un bloque de construcción útil para estructuras de datos más complejas.

Dibujando células de contras

Para comprender mejor la semántica de las recomendaciones y listas, a menudo se utiliza una representación gráfica de este tipo de estructuras. Una celda de contras generalmente se representa con dos cuadros en contacto, que contienen dos flechas que apuntan a los valores de car y cdr , o directamente los valores. Por ejemplo, el resultado de:

(cons 1 2)   
;; -> (1 . 2)

Se puede representar con uno de estos dibujos:

Tenga en cuenta que estas representaciones son puramente conceptuales y no denotan el hecho de que los valores están contenidos en la celda, o están apuntados desde la celda: en general, esto depende de la implementación, el tipo de los valores, el nivel de optimización, etc. En el resto del ejemplo usaremos el primer tipo de dibujo, que es el que se usa más comúnmente.

Entonces, por ejemplo:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

se representa como:

mientras:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

se representa como:

Aquí hay una estructura en forma de árbol:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

El último ejemplo muestra cómo esta notación puede ayudarnos a comprender aspectos semánticos importantes del lenguaje. Primero, escribimos una expresión similar a la anterior:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

que se puede representar de la manera habitual como:

Luego, escribimos una expresión diferente, que aparentemente es equivalente a la anterior, y esto parece confirmado por la representación impresa del resultado:

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

Pero, si dibujamos el diagrama, podemos ver que la semántica de la expresión es diferente, ya que la misma celda es el valor tanto de la parte del car como de la parte cdr de los cons exteriores (esto es, la cell-a es compartida ) :

y el hecho de que la semántica de los dos resultados es realmente diferente a nivel de idioma se puede verificar mediante las siguientes pruebas:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

El primer eq es falso, ya que car y cdr de c1 son estructuralmente iguales (es cierto por equal ), pero no son "idénticos" (es decir, "la misma estructura compartida"), mientras que en la segunda prueba el resultado es verdadero ya que car y cdr de c2 son idénticos , es decir, son la misma estructura .