En programación informática , cons( / ˈ k ɒ n z / o / ˈ k ɒ n s / ) es una función fundamental en la mayoría de los dialectos del lenguaje de programación Lisp . cons construye objetos de memoria que contienen dos valores o punteros a dos valores. Estos objetos se conocen como (cons) celdas, conses, s-expresiones no atómicas ("NATSes") o (cons) pares . En la jerga de Lisp, la expresión "to cons x onto y " significa construir un nuevo objeto con . El par resultante tiene una mitad izquierda, denominada (el primer elemento o contenido de la parte de dirección de r egister ) , y una mitad derecha, denominada (el segundo elemento o contenido de la parte de decremento de r egister ).(cons x y)carcdr
Está vagamente relacionado con la noción orientada a objetos de un constructor , que crea un nuevo objeto dados argumentos, y más estrechamente relacionado con la función constructora de un sistema de tipos de datos algebraicos .
La palabra "cons" y expresiones como "to cons onto" también forman parte de una jerga de programación funcional más general. A veces, los operadores que tienen un propósito similar, especialmente en el contexto del procesamiento de listas, se pronuncian "cons". (Un buen ejemplo es el ::operador en ML , Scala , F# , Lean , Coq y Elm o el :operador en Haskell , que agrega un elemento al comienzo de una lista).
Aunque las celdas cons se pueden utilizar para almacenar pares ordenados de datos, se utilizan más comúnmente para construir estructuras de datos compuestos más complejas, en particular listas y árboles binarios .
Por ejemplo, la expresión Lisp construye una celda que contiene 1 en su mitad izquierda (el llamado campo) y 2 en su mitad derecha (el campo). En la notación Lisp, el valor se ve así:(cons 1 2)carcdr(cons 1 2)
(1 . 2)
Tenga en cuenta el punto entre 1 y 2; esto indica que la expresión S es un "par de puntos" (un llamado "par cons"), en lugar de una "lista".
cons:( contras 42 ( contras 69 ( contras 613 cero ))) list:( lista 42 69 613 ) En Lisp, las listas se implementan sobre pares de cons. Más específicamente, cualquier estructura de lista en Lisp es:
(), que es un objeto especial normalmente llamado nil.cares el primer elemento de la lista y cuyo cdres una lista que contiene el resto de los elementos.Esto forma la base de una estructura de lista enlazada simple cuyo contenido se puede manipular con cons, cary cdr. Tenga en cuenta que niles la única lista que no es también un par cons. Como ejemplo, considere una lista cuyos elementos son 1, 2 y 3. Una lista de este tipo se puede crear en tres pasos:
nil, la lista vacíalo que equivale a la expresión única:
( contras 1 ( contras 2 ( contras 3 nula ))) o su forma abreviada:
( lista 1 2 3 ) El valor resultante es la lista:
(1 . (2 . (3 . cero)))
es decir
*--*--*--nulo | | | 1 2 3
que generalmente se abrevia como:
(1 2 3)
Por lo tanto, consse puede utilizar para agregar un elemento al principio de una lista enlazada existente. Por ejemplo, si x es la lista que definimos anteriormente, entonces se generará la lista:(cons 5 x)
(5 1 2 3)
Otro procedimiento de lista útil es append , que concatena dos listas existentes (es decir, combina dos listas en una sola lista).
También es fácil construir árboles binarios que solo almacenan datos en sus hojascons . Por ejemplo, el código:
( contras ( contras 1 2 ) ( contras 3 4 )) resultados en el arbol:
((1 . 2) . (3 . 4))
es decir
* / \ * */ \ / \1 2 3 4
Técnicamente, la lista (1 2 3) del ejemplo anterior también es un árbol binario, que resulta ser particularmente desequilibrado. Para comprobarlo, basta con reorganizar el diagrama:
*--*--*--nulo | | | 1 2 3
al siguiente equivalente:
* / \ 1 * / \ 2 * / \ 3 cero
Los contras pueden referirse al proceso general de asignación de memoria , en oposición al uso de operaciones destructivas del tipo que se usarían en un lenguaje de programación imperativo. [ cita requerida ] Por ejemplo:
Aceleré un poco el código poniendo efectos secundarios en lugar de hacerlo ridículamente contraproducente.
Dado que Lisp tiene funciones de primera clase , todas las estructuras de datos, incluidas las celdas cons, se pueden implementar mediante funciones. Por ejemplo, en Scheme :
( define ( cons x y ) ( lambda ( m ) ( m x y ))) ( define ( car z ) ( z ( lambda ( p q ) p ))) ( define ( cdr z ) ( z ( lambda ( p q ) q ))) Esta técnica se conoce como codificación Church . Reimplementa las operaciones cons , car y cdr , utilizando una función como la "celda cons". La codificación Church es una forma habitual de definir estructuras de datos en cálculo lambda puro , un modelo teórico abstracto de computación que está estrechamente relacionado con Scheme.
Esta implementación, si bien es académicamente interesante, es poco práctica porque hace que las celdas cons sean indistinguibles de cualquier otro procedimiento de Scheme, además de introducir ineficiencias computacionales innecesarias.
Sin embargo, el mismo tipo de codificación se puede utilizar para tipos de datos algebraicos más complejos con variantes, donde incluso puede resultar más eficiente que otros tipos de codificación. [1] Esta codificación también tiene la ventaja de ser implementable en un lenguaje tipado estáticamente que no tiene variantes, como Java , utilizando interfaces en lugar de lambdas.