Lisp (lenguaje de programación)

Compartir Imprimir Citar
Familia de idiomas

Lisp (históricamente LISP) es una familia de lenguajes de programación con una larga historia y una notación de prefijo distintiva, completamente entre paréntesis. Originalmente especificado en 1960, Lisp es el segundo lenguaje de programación de alto nivel más antiguo que aún se usa comúnmente, después de Fortran. Lisp ha cambiado desde sus inicios y han existido muchos dialectos a lo largo de su historia. Hoy en día, los dialectos Lisp de propósito general más conocidos son Common Lisp, Scheme, Racket y Clojure.

Lisp se creó originalmente como una notación matemática práctica para programas informáticos, influenciada por (aunque no derivado originalmente de) la notación del cálculo lambda de Alonzo Church. Rápidamente se convirtió en un lenguaje de programación favorito para la investigación de inteligencia artificial (IA). Como uno de los primeros lenguajes de programación, Lisp fue pionero en muchas ideas en ciencias de la computación, incluidas estructuras de datos de árbol, gestión de almacenamiento automático, escritura dinámica, condicionales, funciones de orden superior, recursividad, el compilador de alojamiento propio y el read-eval-print. círculo.

El nombre LISP deriva de "LISt Processor". Las listas enlazadas son una de las principales estructuras de datos de Lisp, y el código fuente de Lisp está hecho de listas. Por lo tanto, los programas Lisp pueden manipular el código fuente como una estructura de datos, lo que da lugar a los sistemas macro que permiten a los programadores crear una nueva sintaxis o nuevos lenguajes específicos de dominio integrados en Lisp.

La intercambiabilidad de código y datos le da a Lisp su sintaxis reconocible al instante. Todo el código del programa se escribe como s-expresiones, o listas entre paréntesis. Una llamada de función o forma sintáctica se escribe como una lista con el nombre de la función o del operador primero y los argumentos a continuación; por ejemplo, una función f que toma tres argumentos se llamaría como (f arg1 arg2 arg3).

Historia

John McCarthy (top) y Steve Russell

John McCarthy comenzó a desarrollar Lisp en 1958 mientras estaba en el Instituto Tecnológico de Massachusetts (MIT). McCarthy publicó su diseño en un artículo en Communications of the ACM en abril de 1960, titulado "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Demostró que con unos pocos operadores simples y una notación para funciones anónimas prestada de Church, uno puede construir un lenguaje completo de Turing para algoritmos.

El lenguaje de procesamiento de información fue el primer lenguaje de IA, de 1955 o 1956, y ya incluía muchos de los conceptos, como el procesamiento de listas y la recursividad, que llegaron a usarse en Lisp.

La notación original de McCarthy usaba "expresiones M" entre paréntesis; eso se traduciría en expresiones S. Como ejemplo, la expresión M car[cons[A,B ]] es equivalente a la expresión S (coche (contras A B)). Una vez que se implementó Lisp, los programadores optaron rápidamente por usar expresiones S y se abandonaron las expresiones M. Las expresiones M volvieron a surgir con intentos efímeros de MLisp de Horace Enea y CGOL de Vaughan Pratt.

Lisp fue implementado por primera vez por Steve Russell en una computadora IBM 704 utilizando tarjetas perforadas. Russell había leído el artículo de McCarthy y se dio cuenta (para sorpresa de McCarthy) de que la función Lisp eval podía implementarse en código de máquina.

Según McCarthy:

Steve Russell dijo, mira, ¿por qué no programo esto? eval... y le dije, ho, ho, eres la teoría confusa con la práctica, esto eval está destinado a la lectura, no para el cálculo. Pero siguió adelante y lo hizo. Es decir, compiló el eval en mi papel en el código de máquina IBM 704, arreglando errores, y luego lo anunció como un intérprete de Lisp, que ciertamente fue. Así que en ese momento Lisp tenía esencialmente la forma que tiene hoy...

El resultado fue un intérprete de Lisp funcional que podría utilizarse para ejecutar programas de Lisp o, más correctamente, "evaluar expresiones de Lisp".

Dos macros en lenguaje ensamblador para el IBM 704 se convirtieron en las operaciones primitivas para descomponer listas: car (Contenido de la parte de Dirección del Número de Registro) y cdr (Contenido de la parte de Decremento de Registro número), donde "registrar" se refiere a los registros de la unidad central de procesamiento (CPU) de la computadora. Los dialectos Lisp todavía usan car y cdr (y) para las operaciones que devuelve el primer elemento de una lista y el resto de la lista, respectivamente.

El primer compilador completo de Lisp, escrito en Lisp, fue implementado en 1962 por Tim Hart y Mike Levin en el MIT, y podía compilarse simplemente haciendo que un intérprete LISP existente interpretara el código del compilador, produciendo una salida de código de máquina capaz de ejecutarse con una mejora de 40 veces en la velocidad con respecto a la del intérprete. Este compilador introdujo el modelo Lisp de compilación incremental, en el que las funciones compiladas e interpretadas pueden entremezclarse libremente. El lenguaje utilizado en el memorando de Hart y Levin está mucho más cerca del estilo Lisp moderno que el código anterior de McCarthy.

Las rutinas de recolección de basura fueron desarrolladas por el estudiante graduado del MIT Daniel Edwards antes de 1962.

Durante las décadas de 1980 y 1990, se hizo un gran esfuerzo para unificar el trabajo en los nuevos dialectos de Lisp (en su mayoría sucesores de Maclisp como ZetaLisp y NIL (Nueva Implementación de Lisp) en un solo idioma. El nuevo idioma, Common Lisp, era algo compatible con los dialectos que reemplazó (el libro Common Lisp the Language señala la compatibilidad de varias construcciones). En 1994, ANSI publicó el estándar Common Lisp, "ANSI X3.226-1994 Tecnología de la información Lenguaje de programación Common Lisp".

Cronología

Timeline of Lisp dialects
  • v
  • t
  • e
1955 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2020
LISP 1, 1,5, LISP 2(abandonado)
Maclisp
Interlisp
MDL
Lisp Machine Lisp
Plan R5RS R6RS R7RS pequeño
NIL
ZIL (Zork Implementation Language)
Franz Lisp
Lisp común ANSI standard
Le Lisp
MIT Plan
T
Chez Scheme
Emacs Lisp
AutoLISP
PicoLisp
Gambit
EuLisp
ISLISP
OpenLisp
PLT Plan Racket
GNU Guile
Visual LISP
Clojure
Arc
LFE
Hy

Conexión a la inteligencia artificial

Desde su inicio, Lisp estuvo estrechamente conectado con la comunidad de investigación de inteligencia artificial, especialmente en los sistemas PDP-10. Lisp se utilizó como implementación del lenguaje Micro Planner, que se utilizó en el famoso sistema de inteligencia artificial SHRDLU. En la década de 1970, a medida que la investigación de IA generaba ramificaciones comerciales, el rendimiento de los sistemas Lisp existentes se convirtió en un problema cada vez mayor, ya que los programadores necesitaban familiarizarse con las ramificaciones de rendimiento de las diversas técnicas y opciones involucradas en la implementación de Lisp.

Genealogía y variantes

Durante sus sesenta años de historia, Lisp ha generado muchas variaciones sobre el tema central de un lenguaje de expresión S. Además, cada dialecto dado puede tener varias implementaciones; por ejemplo, hay más de una docena de implementaciones de Common Lisp.

Las diferencias entre dialectos pueden ser bastante visibles; por ejemplo, Common Lisp usa la palabra clave defun para nombrar una función, pero Scheme usa define. Sin embargo, dentro de un dialecto que está estandarizado, las implementaciones compatibles admiten el mismo lenguaje central, pero con diferentes extensiones y bibliotecas.

Dialectos históricamente significativos

Una máquina Lisp en el Museo MIT
4.3 BSD de la Universidad de Wisconsin, mostrando la página de hombre para Franz Lisp

2000 al presente

Después de haber disminuido un poco en la década de 1990, Lisp ha experimentado un resurgimiento del interés después de 2000. La mayor parte de la actividad nueva se ha centrado en implementaciones de Common Lisp, Scheme, Emacs Lisp, Clojure y Racket, e incluye el desarrollo de nuevas bibliotecas portátiles. y aplicaciones.

Muchos programadores nuevos de Lisp se inspiraron en escritores como Paul Graham y Eric S. Raymond para buscar un lenguaje que otros consideraban anticuado. Los programadores de New Lisp a menudo describen el lenguaje como una experiencia reveladora y afirman que es sustancialmente más productivo que en otros lenguajes. Este aumento de la conciencia puede contrastarse con el "invierno de la IA" y la breve ganancia de Lisp a mediados de la década de 1990.

A partir de 2010, había once implementaciones de Common Lisp mantenidas activamente. Scieneer Common Lisp es una nueva implementación comercial bifurcada de CMUCL con un primer lanzamiento en 2002.

La comunidad de código abierto ha creado una nueva infraestructura de soporte: CLiki es un wiki que recopila información relacionada con Common Lisp, el directorio de Common Lisp enumera los recursos, #lisp es un canal de IRC popular y permite compartir y comentar fragmentos de código (con soporte por lisppaste, un bot de IRC escrito en Lisp), Planet Lisp recopila el contenido de varios blogs relacionados con Lisp, en LispForum los usuarios discuten temas de Lisp, Lispjobs es un servicio para anunciar ofertas de trabajo y hay un servicio de noticias semanal, Weekly Lisp Noticias. Common-lisp.net es un sitio de alojamiento para proyectos Common Lisp de código abierto. Quicklisp es un administrador de bibliotecas para Common Lisp.

Los cincuenta años de Lisp (1958–2008) se celebraron en LISP50@OOPSLA. Hay reuniones regulares de usuarios locales en Boston, Vancouver y Hamburgo. Otros eventos incluyen la Reunión Europea de Lisp Común, el Simposio Europeo de Lisp y una Conferencia Internacional de Lisp.

La comunidad de Scheme mantiene activamente más de veinte implementaciones. Varias implementaciones nuevas significativas (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon) se han desarrollado en la década de 2000 (década). El Informe revisado5 sobre el estándar Algorithmic Language Scheme de Sche fue ampliamente aceptado en la comunidad de Scheme. El proceso de solicitudes de implementación de Scheme ha creado muchas bibliotecas cuasi estándar y extensiones para Scheme. Las comunidades de usuarios de implementaciones individuales del Esquema continúan creciendo. Un nuevo proceso de estandarización del idioma se inició en 2003 y condujo al estándar R6RS Scheme en 2007. El uso académico de Scheme para enseñar informática parece haber disminuido un poco. Algunas universidades ya no utilizan Scheme en sus cursos de introducción a la informática; El MIT ahora usa Python en lugar de Scheme para su programa de licenciatura en ciencias de la computación y el curso masivo abierto en línea de MITx.

Hay varios dialectos nuevos de Lisp: Arc, Hy, Nu, Liskell y LFE (Lisp Flavored Erlang). El analizador de Julia se implementa en Femtolisp, un dialecto de Scheme (Julia está inspirada en Scheme, que a su vez es un dialecto de Lisp).

En octubre de 2019, Paul Graham publicó una especificación para Bel, "un nuevo dialecto de Lisp."

Dialectos principales

Common Lisp y Scheme representan dos corrientes principales de desarrollo de Lisp. Estos lenguajes incorporan opciones de diseño significativamente diferentes.

Common Lisp es un sucesor de Maclisp. Las principales influencias fueron Lisp Machine Lisp, Maclisp, NIL, S-1 Lisp, Spice Lisp y Scheme. Tiene muchas de las características de Lisp Machine Lisp (un gran dialecto de Lisp que se usa para programar Lisp Machines), pero fue diseñado para ser implementado de manera eficiente en cualquier computadora personal o estación de trabajo. Common Lisp es un lenguaje de programación de propósito general y, por lo tanto, tiene un gran estándar de lenguaje que incluye muchos tipos de datos integrados, funciones, macros y otros elementos del lenguaje, y un sistema de objetos (Common Lisp Object System). Common Lisp también tomó prestadas ciertas características de Scheme, como el alcance léxico y los cierres léxicos. Las implementaciones de Common Lisp están disponibles para apuntar a diferentes plataformas, como LLVM, la máquina virtual de Java, x86-64, PowerPC, Alpha, ARM, Motorola 68000 y MIPS, y sistemas operativos como Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD y Heroku.

Scheme es un dialecto del lenguaje de programación Lisp inventado por Guy L. Steele, Jr. y Gerald Jay Sussman. Fue diseñado para tener una semántica excepcionalmente clara y simple y pocas formas diferentes de formar expresiones. Diseñado aproximadamente una década antes que Common Lisp, Scheme es un diseño más minimalista. Tiene un conjunto mucho más pequeño de funciones estándar pero con ciertas funciones de implementación (como la optimización de llamadas de seguimiento y continuaciones completas) no especificadas en Common Lisp. Una amplia variedad de paradigmas de programación, incluidos los estilos imperativo, funcional y de paso de mensajes, encuentran una expresión conveniente en Scheme. Scheme sigue evolucionando con una serie de estándares (Informe revisadon sobre el Scheme de lenguaje algorítmico) y una serie de Solicitudes de Scheme para la implementación.

Clojure es un dialecto reciente de Lisp que se dirige principalmente a la máquina virtual Java y Common Language Runtime (CLR), Python VM, Ruby VM YARV y compilación en JavaScript. Está diseñado para ser un lenguaje pragmático de propósito general. Clojure atrae considerables influencias de Haskell y pone un énfasis muy fuerte en la inmutabilidad. Clojure brinda acceso a marcos y bibliotecas de Java, con sugerencias de tipo e inferencia de tipo opcionales, de modo que las llamadas a Java puedan evitar la reflexión y permitir operaciones primitivas rápidas. Clojure no está diseñado para ser retrocompatible con otros dialectos de Lisp.

Además, los dialectos de Lisp se utilizan como lenguajes de secuencias de comandos en muchas aplicaciones, siendo los más conocidos Emacs Lisp en el editor de Emacs, AutoLISP y más tarde Visual Lisp en AutoCAD, Nyquist en Audacity y Scheme en LilyPond. El pequeño tamaño potencial de un intérprete de Scheme útil lo hace particularmente popular para secuencias de comandos integradas. Los ejemplos incluyen SIOD y TinyScheme, los cuales se han integrado con éxito en el procesador de imágenes GIMP con el nombre genérico "Script-fu". LIBREP, un intérprete de Lisp de John Harper basado originalmente en el lenguaje Emacs Lisp, se ha integrado en el administrador de ventanas Sawfish.

Dialectos estandarizados

Lisp tiene dialectos oficialmente estandarizados: R6RS Scheme, R7RS Scheme, IEEE Scheme, ANSI Common Lisp e ISO ISLISP.

Innovaciones lingüísticas

Paul Graham identifica nueve aspectos importantes de Lisp que lo distinguen de lenguajes existentes como Fortran:

Lisp fue el primer lenguaje en el que la estructura del código del programa se representa fiel y directamente en una estructura de datos estándar, una cualidad que mucho más tarde se denominó "homoiconicidad". Por lo tanto, las funciones Lisp se pueden manipular, alterar o incluso crear dentro de un programa Lisp sin manipulaciones de nivel inferior. Esto generalmente se considera una de las principales ventajas del lenguaje con respecto a su poder expresivo, y hace que el lenguaje sea adecuado para macros sintácticas y evaluación metacircular.

McCarthy inventó un condicional que usaba una sintaxis if-then-else para un programa de ajedrez escrito en Fortran. Propuso su inclusión en ALGOL, pero no se hizo parte de la especificación Algol 58. Para Lisp, McCarthy usó la estructura cond más general. Algol 60 tomó if-then-else y lo popularizó.

Lisp influyó profundamente en Alan Kay, el líder del equipo de investigación que desarrolló Smalltalk en Xerox PARC; y, a su vez, Lisp fue influenciado por Smalltalk, con dialectos posteriores que adoptaron características de programación orientada a objetos (clases de herencia, instancias encapsuladas, paso de mensajes, etc.) en la década de 1970. El sistema de objetos Flavours introdujo el concepto de herencia múltiple y el mixin. El sistema de objetos Common Lisp proporciona herencia múltiple, métodos múltiples con despacho múltiple y funciones genéricas de primera clase, lo que produce una forma flexible y poderosa de despacho dinámico. Ha servido como plantilla para muchos sistemas de objetos Lisp posteriores (incluido Scheme), que a menudo se implementan a través de un protocolo de metaobjetos, un diseño metacircular reflexivo en el que el sistema de objetos se define en términos de sí mismo: Lisp era solo el segundo idioma. después de Smalltalk (y sigue siendo uno de los pocos lenguajes) en poseer tal sistema de metaobjetos. Muchos años después, Alan Kay sugirió que, como resultado de la confluencia de estas características, solo Smalltalk y Lisp podrían considerarse sistemas de programación orientados a objetos correctamente concebidos.

Lisp introdujo el concepto de recolección automática de elementos no utilizados, en el que el sistema recorre el montón en busca de memoria no utilizada. El progreso en los sofisticados algoritmos de recolección de basura modernos, como la recolección de basura generacional, fue estimulado por su uso en Lisp.

Edsger W. Dijkstra en su conferencia del Premio Turing de 1972 dijo:

Con unos pocos principios muy básicos en su fundación, [LISP] ha mostrado una notable estabilidad. Además, LISP ha sido el portador de un número considerable de nuestras aplicaciones informáticas más sofisticadas. LISP ha sido describido de manera de broma como "la forma más inteligente de mal uso de un ordenador". Creo que esa descripción es un gran cumplido porque transmite todo el sabor de la liberación: ha ayudado a varios de nuestros seres humanos más dotados a pensar pensamientos imposibles.

En gran parte debido a sus requisitos de recursos con respecto al hardware informático temprano (incluidos los primeros microprocesadores), Lisp no se volvió tan popular fuera de la comunidad de IA como Fortran y el lenguaje C descendiente de ALGOL. Debido a su idoneidad para aplicaciones complejas y dinámicas, Lisp disfrutó de un resurgimiento del interés popular en la década de 2010.

Sintaxis y semántica

Nota: Los ejemplos de este artículo están escritos en Common Lisp (aunque la mayoría también son válidos en Scheme).

Expresiones simbólicas (expresiones S)

Lisp es un lenguaje orientado a la expresión. A diferencia de la mayoría de los otros idiomas, no se hace distinción entre "expresiones" y "declaraciones"; todo el código y los datos se escriben como expresiones. Cuando se evalúa una expresión, produce un valor (en Common Lisp, posiblemente varios valores), que luego se puede incrustar en otras expresiones. Cada valor puede ser cualquier tipo de datos.

El artículo de McCarthy de 1958 introdujo dos tipos de sintaxis: Expresiones simbólicas (expresiones S, sexps), que reflejan la representación interna de código y datos; y Metaexpresiones (expresiones M), que expresan funciones de expresiones S. Las expresiones M nunca encontraron favor, y casi todos los Lisps hoy en día usan expresiones S para manipular tanto el código como los datos.

El uso de paréntesis es la diferencia más obvia de Lisp con respecto a otras familias de lenguajes de programación. Como resultado, los estudiantes han dado durante mucho tiempo apodos a Lisp como Perdido en paréntesis estúpidos, o Muchos paréntesis superfluos irritantes. Sin embargo, la sintaxis de la expresión S también es responsable de gran parte del poder de Lisp: la sintaxis es simple y consistente, lo que facilita la manipulación por computadora. Sin embargo, la sintaxis de Lisp no se limita a la notación de paréntesis tradicional. Se puede ampliar para incluir notaciones alternativas. Por ejemplo, XMLisp es una extensión de Common Lisp que emplea el protocolo de metaobjetos para integrar expresiones S con el lenguaje de marcado extensible (XML).

La dependencia de las expresiones le da al lenguaje una gran flexibilidad. Debido a que las funciones de Lisp se escriben como listas, se pueden procesar exactamente como datos. Esto permite escribir fácilmente programas que manipulan otros programas (metaprogramación). Muchos dialectos de Lisp explotan esta función utilizando sistemas de macros, lo que permite la extensión del lenguaje casi sin límites.

Listas

Una lista Lisp se escribe con sus elementos separados por espacios en blanco y entre paréntesis. Por ejemplo, (1 2 foo) es una lista cuyos elementos son los tres átomos 1, 2 y foo. Estos valores se escriben implícitamente: son, respectivamente, dos números enteros y un tipo de datos específico de Lisp llamado "símbolo", y no tienen que declararse como tales.

La lista vacía () también se representa como el átomo especial nil. Esta es la única entidad en Lisp que es a la vez un átomo y una lista.

Las expresiones se escriben como listas, usando notación de prefijos. El primer elemento de la lista es el nombre de una función, el nombre de una macro, una expresión lambda o el nombre de un "operador especial" (vea abajo). El resto de la lista son los argumentos. Por ejemplo, la función list devuelve sus argumentos como una lista, por lo que la expresión 

 ()lista 1 2 ()cita Foo)

se evalúa en la lista (1 2 foo). La "cita" antes de foo en el ejemplo anterior hay un "operador especial" que devuelve su argumento sin evaluarlo. Las expresiones sin comillas se evalúan recursivamente antes de que se evalúe la expresión que las encierra. Por ejemplo, 

 ()lista 1 2 ()lista 3 4)

se evalúa en la lista (1 2 (3 4)). Tenga en cuenta que el tercer argumento es una lista; las listas se pueden anidar.

Operadores

Los operadores aritméticos se tratan de manera similar. La expresion 

 ()+ 1 2 3 4)

se evalúa como 10. El equivalente en notación infija sería "1 + 2 + 3 + 4".

Lisp no tiene noción de operadores implementados en lenguajes derivados de Algol. Los operadores aritméticos en Lisp son funciones variádicas (o n-arias), capaces de tomar cualquier cantidad de argumentos. Un estilo C '++' El operador de incremento a veces se implementa con el nombre incf dando sintaxis 

 ()incf x)

equivalente a (setq x (+ x 1)), devolviendo el nuevo valor de x.

"Operadores especiales" (a veces llamados "formularios especiales") proporcionan la estructura de control de Lisp. Por ejemplo, el operador especial if toma tres argumentos. Si el primer argumento no es nulo, se evalúa como el segundo argumento; de lo contrario, se evalúa como el tercer argumento. Así, la expresión 

 ()si Nil ()lista 1 2 "foo") ()lista 3 4 "bar")

se evalúa como (3 4 "barra") . Por supuesto, esto sería más útil si se hubiera sustituido una expresión no trivial en lugar de ninguno.

Lisp también proporciona operadores lógicos y, o y no. Los operadores and y or realizan una evaluación de cortocircuito y devolverán su primer argumento nulo y no nulo respectivamente. 

 ()o ()y "cero" Nil "Nunca") "James" 'tarea' Hora)

se evaluará como "James".

Expresiones lambda y definición de funciones

Otro operador especial, lambda, se utiliza para vincular variables a valores que luego se evalúan dentro de una expresión. Este operador también se usa para crear funciones: los argumentos para lambda son una lista de argumentos y la expresión o expresiones a las que evalúa la función (el valor devuelto es el valor de la última expresión que se evalúa). La expresion 

 ()lambda ()arg) ()+ arg 1)

se evalúa como una función que, cuando se aplica, toma un argumento, lo vincula a arg y devuelve el número uno mayor que ese argumento. Las expresiones lambda no se tratan de forma diferente a las funciones con nombre; se invocan de la misma manera. Por lo tanto, la expresión 

 ()lambda ()arg) ()+ arg 1) 5)

se evalúa como 6. Aquí, estamos haciendo una aplicación de función: ejecutamos la función anónima pasándole el valor 5.

Las funciones con nombre se crean almacenando una expresión lambda en un símbolo usando la macro defun. 

 ()defun Foo ()a b c d) ()+ a b c d)

(defun f (a) b...) define una nueva función llamada f en el entorno global. Es conceptualmente similar a la expresión: 

 ()setf ()fdefinición 'f) # '()lambda ()a) ()bloque f b...))

donde setf es un macro utilizada para establecer el valor del primer argumento fdefinition 'f a un nuevo objeto de función. fdefinition es una definición de función global para la función denominada f. #' es un abreviatura de función operador especial, que regresa un objeto de función.

Átomos

En el LISP original había dos tipos de datos fundamentales: átomos y listas. Una lista era una secuencia ordenada finita de elementos, donde cada elemento es un átomo o una lista, y un átomo era un número o un símbolo. Un símbolo era esencialmente un elemento con nombre único, escrito como una cadena alfanumérica en el código fuente y utilizado como nombre de variable o como elemento de datos en el procesamiento simbólico. Por ejemplo, la lista (FOO (BAR 1) 2) contiene tres elementos: el símbolo FOO, la lista (BAR 1), y el número 2.

La diferencia esencial entre los átomos y las listas era que los átomos eran inmutables y únicos. Dos átomos que aparecían en diferentes lugares en el código fuente pero que estaban escritos exactamente de la misma manera representaban el mismo objeto, mientras que cada lista era un objeto separado que podía modificarse independientemente de otras listas y podía distinguirse de otras listas mediante operadores de comparación.

A medida que se introdujeron más tipos de datos en dialectos Lisp posteriores y evolucionaron los estilos de programación, el concepto de átomo perdió importancia. Muchos dialectos aún conservaron el predicado átomo para la compatibilidad heredada, definiéndolo verdadero para cualquier objeto que no sea una desventaja.

Consejos y listas

Esquema de caja y puntero para la lista (42 69 613)

Una lista Lisp se implementa como una lista enlazada individualmente. Cada celda de esta lista se llama contras (en Scheme, un par) y está compuesta por dos punteros, llamados automóvil y cdr. Estos son respectivamente equivalentes a los datos y siguiente campos discutidos en el artículo lista enlazada.

De las muchas estructuras de datos que se pueden construir a partir de celdas contras, una de las más básicas se llama lista adecuada. Una lista adecuada es el nil (lista vacía) símbolo, o una contra en la que el coche apunta a un dato (que puede ser otra estructura contras, como una lista), y el cdr apunta a otra lista adecuada.

Si se toma un cons dado como el encabezado de una lista enlazada, entonces su car apunta al primer elemento de la lista y su cdr apunta al resto de la lista. Por este motivo, el coche y Las funciones cdr también se denominan primero y rest cuando se refiera a conses que son parte de una lista enlazada (más bien que, digamos, un árbol).

Por lo tanto, una lista Lisp no es un objeto atómico, como lo sería una instancia de una clase contenedora en C++ o Java. Una lista no es más que un agregado de consensos vinculados. Una variable que se refiere a una lista dada es simplemente un puntero a las primeras contras de la lista. Se puede recorrer una lista cdring down de la lista; es decir, tomando sucesivas cdrs para visitar cada contra de la lista; o usando cualquiera de varias funciones de orden superior para mapear una función sobre una lista.

Debido a que las convenciones y las listas son tan universales en los sistemas Lisp, es un error común pensar que son las únicas estructuras de datos de Lisp. De hecho, todos excepto los Lisps más simples tienen otras estructuras de datos, como vectores (matrices), tablas hash, estructuras, etc.

Las expresiones S representan listas

Las expresiones S entre paréntesis representan estructuras de listas enlazadas. Hay varias formas de representar la misma lista como una expresión S. Una contra se puede escribir en notación de pares punteados como (a . b), donde a es el coche y b el cdr. Se podría escribir una lista adecuada más larga (a . (b . (c . (d . nil)))) en notación de pares punteados. Esto se abrevia convencionalmente como (a b c d) en notación de lista. Se puede escribir una lista incorrecta en una combinación de los dos, como (a b c . d) para la lista de tres conses cuyo último cdr es d (es decir, la lista (a . (b . (c . d))) en forma completamente especificada).

Procedimientos de procesamiento de listas

Lisp proporciona muchos procedimientos integrados para acceder y controlar listas. Las listas se pueden crear directamente con la lista procedimiento, que toma cualquier número de argumentos, y devuelve la lista de estos argumentos. 

 ()lista 1 2 'a 3) ; Producto: (1 2 a 3)
 ()lista 1 '()2 3) 4) ; Producto: (1 (2 3) 4)

Debido a la forma en que las listas se construyen a partir de pares de contras, cons se puede utilizar para agregar un elemento al principio de una lista. Tenga en cuenta que el procedimiento cons es asimétrico en cómo maneja los argumentos de lista, debido a cómo se construyen las listas. 

 ()cons 1 '()2 3) ; Producto: (1 2 3)
 ()cons '()1 2) '()3 4) ; Producto: ((1 2) 3 4)

El append procedimiento anexa dos (o más) listas entre sí. Debido a que las listas de Lisp están vinculadas listas, pendiente de dos listas tiene complejidad de tiempo asintotica O()n){displaystyle O(n)}

 ()apéndice '()1 2) '()3 4) ; Producto: (1 2 3 4)
 ()apéndice '()1 2 3) '() '()a) '()5 6) ; Producto: (1 2 3 a 5 6)

Estructura compartida

Las listas Lisp, al ser listas enlazadas simples, pueden compartir estructura entre sí. Es decir, dos listas pueden tener la misma cola, o secuencia final de consecuencias. Por ejemplo, después de la ejecución del siguiente código Common Lisp: 

()setf Foo ()lista 'a 'b 'c)()setf bar ()cons 'x ()cdr Foo))

las listas foo y bar son (a b c) y (x b c) respectivamente. Sin embargo, la cola (b c) es la misma estructura en ambas listas. No es una copia; las celdas contras que apuntan a b y c están en las mismas ubicaciones de memoria para ambas listas.

Compartir la estructura en lugar de copiar puede brindar una mejora drástica en el rendimiento. Sin embargo, esta técnica puede interactuar de formas no deseadas con funciones que alteran las listas que se les pasan como argumentos. Alterar una lista, como reemplazar c con un ganso, afectará al otro: 

 ()setf ()tercero Foo) 'goose)

Esto cambia foo a (a b goose), pero por lo tanto también cambia barra a (x b goose): un resultado posiblemente inesperado. Esto puede ser una fuente de errores, y las funciones que alteran sus argumentos se documentan como destructivas por esta misma razón.

Los aficionados a la programación funcional evitan las funciones destructivas. En el dialecto Scheme, que favorece el estilo funcional, los nombres de las funciones destructivas se marcan con un signo de exclamación de advertencia, o "bang", como set-car! (léase set car bang), que reemplaza al coche de un contras. En el dialecto Common Lisp, las funciones destructivas son comunes; el equivalente de set-car! se llama rplaca para "reemplazar coche". Sin embargo, esta función rara vez se ve, ya que Common Lisp incluye una función especial, setf, para facilitar la definición y el uso de funciones destructivas. Un estilo frecuente en Common Lisp es escribir código funcionalmente (sin llamadas destructivas) al crear prototipos, y luego agregar llamadas destructivas como una optimización donde sea seguro hacerlo.

Formularios de autoevaluación y cotización

Lisp evalúa las expresiones ingresadas por el usuario. Los símbolos y las listas se evalúan como alguna otra expresión (por lo general, más simple); por ejemplo, un símbolo se evalúa como el valor de la variable que nombra; (+ 2 3) se evalúa como 5. Sin embargo, la mayoría de los otros formularios se evalúan a sí mismos: si ingresa 5 en Lisp, devuelve 5 .

Cualquier expresión también se puede marcar para evitar que se evalúe (como es necesario para los símbolos y las listas). Esta es la función del quote operador especial, o su abreviatura ' (una comilla). Por ejemplo, generalmente si ingresa el símbolo foo, devuelve el valor de la variable correspondiente (o un error, si no existe tal variable). Para hacer referencia al símbolo literal, ingrese (quote foo) o, normalmente, 'foo.

Tanto Common Lisp como Scheme también admiten el operador backquote (denominado quasiquote en Scheme), ingresado con el carácter ` (acento grave). Esto es casi lo mismo que las comillas simples, excepto que permite que las expresiones sean evaluadas y sus valores interpolados en una lista citada con la coma , sin comillas y coma en ,@ empalme operadores. Si la variable snue tiene el valor (bar baz) luego `(foo ,snue) se evalúa como (foo (barra baz)), mientras que `(foo ,@snue) se evalúa como (foo barra baz). La comilla inversa se usa con mayor frecuencia para definir expansiones macro.

Los formularios de autoevaluación y los formularios citados son el equivalente de los literales de Lisp. Puede ser posible modificar los valores de los literales (mutables) en el código del programa. Por ejemplo, si una función devuelve un formulario entre comillas y el código que llama a la función modifica el formulario, esto puede alterar el comportamiento de la función en invocaciones posteriores. 

()defun debería estar de acuerdo. () '()uno dos. tres)()Deja ()cosas ()debería estar de acuerdo.)) ()setf ()tercero cosas) "Bizarro") ; malo!()debería estar de acuerdo.) ; retornos (uno dos extraños)

La modificación de un formulario citado como este generalmente se considera de mal estilo, y ANSI Common Lisp lo define como erróneo (lo que resulta en un comportamiento "indefinido" en los archivos compilados, porque el compilador de archivos puede fusionar constantes similares, guardarlos en una memoria protegida contra escritura, etc.).

Douglas Hofstadter (en Gödel, Escher, Bach) y otros han señalado la formalización de la cita de Lisp como un ejemplo de la idea filosófica de la autorreferencia.

Alcance y cierre

La familia Lisp se divide por el uso de alcance dinámico o estático (también conocido como léxico). Clojure, Common Lisp y Scheme utilizan el ámbito estático de forma predeterminada, mientras que newLISP, Picolisp y los lenguajes integrados en Emacs y AutoCAD utilizan el ámbito dinámico. Desde la versión 24.1, Emacs utiliza tanto el alcance dinámico como el léxico.

Estructura de la lista del código del programa; explotación por macros y compiladores

Una distinción fundamental entre Lisp y otros lenguajes es que en Lisp, la representación textual de un programa es simplemente una descripción legible por humanos de las mismas estructuras de datos internas (listas enlazadas, símbolos, números, caracteres, etc.) ser utilizado por el sistema Lisp subyacente.

Lisp usa esto para implementar un sistema macro muy poderoso. Al igual que otros lenguajes de macros como el definido por el preprocesador C (el preprocesador de macros para los lenguajes de programación C, Objective-C y C++), una macro devuelve código que luego se puede compilar. Sin embargo, a diferencia de las macros del preprocesador C, las macros son funciones de Lisp y, por lo tanto, pueden explotar todo el poder de Lisp.

Además, dado que el código Lisp tiene la misma estructura que las listas, las macros se pueden crear con cualquiera de las funciones de procesamiento de listas del lenguaje. En resumen, cualquier cosa que Lisp pueda hacer con una estructura de datos, las macros de Lisp pueden hacer con el código. Por el contrario, en la mayoría de los otros lenguajes, la salida del analizador es puramente interna a la implementación del lenguaje y no puede ser manipulada por el programador.

Esta función facilita el desarrollo de lenguajes eficientes dentro de otros idiomas. Por ejemplo, el sistema de objetos Common Lisp se puede implementar limpiamente como una extensión del lenguaje usando macros. Esto significa que si una aplicación necesita un mecanismo de herencia diferente, puede usar un sistema de objetos diferente. Esto está en marcado contraste con la mayoría de los otros idiomas; por ejemplo, Java no admite la herencia múltiple y no existe una forma razonable de agregarla.

En implementaciones simplistas de Lisp, esta estructura de lista se interpreta directamente para ejecutar el programa; una función es literalmente una pieza de estructura de lista que es atravesada por el intérprete al ejecutarla. Sin embargo, la mayoría de los sistemas Lisp importantes también incluyen un compilador. El compilador traduce la estructura de la lista en código de máquina o código de bytes para su ejecución. Este código puede ejecutarse tan rápido como el código compilado en lenguajes convencionales como C.

Las macros se expanden antes del paso de compilación y, por lo tanto, ofrecen algunas opciones interesantes. Si un programa necesita una tabla precalculada, entonces una macro podría crear la tabla en tiempo de compilación, por lo que el compilador solo necesita generar la tabla y no necesita llamar al código para crear la tabla en tiempo de ejecución. Algunas implementaciones de Lisp incluso tienen un mecanismo, eval-when, que permite que el código esté presente durante el tiempo de compilación (cuando una macro lo necesita), pero no presente en el módulo emitido.

Evaluación y ciclo de lectura-evaluación-impresión

Los lenguajes Lisp a menudo se usan con una línea de comando interactiva, que se puede combinar con un entorno de desarrollo integrado (IDE). El usuario escribe expresiones en la línea de comando o indica al IDE que las transmita al sistema Lisp. Lisp lee las expresiones ingresadas, las evalúa e imprime el resultado. Por esta razón, la línea de comandos de Lisp se denomina bucle de lectura-evaluación-impresión (REPL).

El funcionamiento básico del REPL es el siguiente. Esta es una descripción simplista que omite muchos elementos de un Lisp real, como las comillas y las macros.

La función leer acepta S-expresiones textuales como entrada y las analiza en una estructura de datos interna. Por ejemplo, si escribe el texto (+ 1 2) en el aviso, leer traduce esto en una lista enlazada con tres elementos: el símbolo + , el número 1 y el número 2. Sucede que esta lista también es una pieza válida de código Lisp; es decir, se puede evaluar. Esto se debe a que el carro de la lista nombra una función: la operación de suma.

Tenga en cuenta que foo se leerá como un solo símbolo. 123 se leerá como el número ciento VEINTITRES. "123" se leerá como la cadena "123".

La función eval los datos, devolviendo cero o más datos Lisp como resultado. Evaluación no tiene por qué significar interpretación; algunos sistemas Lisp compilan cada expresión en código de máquina nativo. Sin embargo, es simple describir la evaluación como interpretación: para evaluar una lista cuyo coche nombra una función, eval primero evalúa cada uno de los argumentos dados en su cdr, luego aplica la función a los argumentos. En este caso, la función es una suma y se aplica a la lista de argumentos (1 2) produce la respuesta 3. Este es el resultado de la evaluación.

El símbolo foo evalúa al valor del símbolo foo. Datos como la cadena "123" evalúa a la misma cadena. La lista ( cita (1 2 3)) se evalúa como la lista (1 2 3).

Es el trabajo de imprimir función para representar la salida para el usuario. Para un resultado simple como 3 esto es trivial Una expresión que evalúe una parte de la estructura de la lista requeriría que print recorrer la lista e imprimirla como una expresión S.

Para implementar un Lisp REPL, solo es necesario implementar estas tres funciones y una función de bucle infinito. (Naturalmente, la implementación de eval será complejo, ya que también debe implementar todos los operadores especiales como if o lambda.) Hecho esto, un REPL básico es una línea de código: (bucle (imprimir (evaluar (leer)))).

Lisp REPL normalmente también proporciona edición de entrada, un historial de entrada, manejo de errores y una interfaz para el depurador.

Lisp suele evaluarse con entusiasmo. En Common Lisp, los argumentos se evalúan en orden aplicativo ('más a la izquierda más adentro'), mientras que en Scheme el orden de los argumentos no está definido, lo que deja espacio para la optimización por parte de un compilador.

Estructuras de control

Lisp originalmente tenía muy pocas estructuras de control, pero se agregaron muchas más durante la evolución del lenguaje. (El operador condicional original de Lisp, cond , es el precursor de if-then-else estructuras.)

Los programadores en el dialecto Scheme a menudo expresan bucles usando recursividad de cola. El carácter común de Scheme en la informática académica ha llevado a algunos estudiantes a creer que la recursividad de la cola es la única forma, o la más común, de escribir iteraciones en Lisp, pero esto es incorrecto. Todos los dialectos de Lisp que se ven a menudo tienen construcciones de iteración de estilo imperativo, desde Scheme do bucle al complejo loop expresiones. Además, la cuestión clave que hace que esto sea un asunto objetivo en lugar de subjetivo es que Scheme establece requisitos específicos para el manejo de llamadas de cola y, por lo tanto, la razón por la que el uso de la recursividad de cola generalmente se recomienda para Scheme es que la práctica está respaldada expresamente por la definición del lenguaje. Por el contrario, ANSI Common Lisp no requiere la optimización comúnmente denominada eliminación de llamada de cola. Por lo tanto, el hecho de que el estilo recursivo de cola sea un reemplazo casual para el uso de construcciones de iteración más tradicionales (como hacer, dolist o loop) en Common Lisp no es solo una cuestión de preferencia estilística, sino potencialmente de eficiencia (ya que una aparente llamada de cola en Common Lisp puede no compilarse como un simple salto) y corrección del programa (ya que tail la recursividad puede aumentar el uso de la pila en Common Lisp, con el riesgo de desbordamiento de la pila).

Algunas estructuras de control Lisp son operadores especiales, equivalentes a otros lenguajes' palabras clave sintácticas. Las expresiones que utilizan estos operadores tienen la misma apariencia superficial que las llamadas a funciones, pero se diferencian en que los argumentos no se evalúan necesariamente o, en el caso de una expresión de iteración, pueden evaluarse más de una vez.

A diferencia de la mayoría de los principales lenguajes de programación, Lisp permite implementar estructuras de control utilizando el lenguaje. Varias estructuras de control se implementan como macros de Lisp, e incluso el programador puede ampliarlas si desea saber cómo funcionan.

Tanto Common Lisp como Scheme tienen operadores para flujo de control no local. Las diferencias en estos operadores son algunas de las diferencias más profundas entre los dos dialectos. Scheme admite continuaciones de reingreso utilizando procedimiento call/cc, que permite que un programa guarde (y luego restaure) un lugar particular en ejecución. Common Lisp no admite continuaciones de reentrada, pero admite varias formas de manejar las continuaciones de escape.

A menudo, el mismo algoritmo se puede expresar en Lisp en un estilo imperativo o funcional. Como se señaló anteriormente, Scheme tiende a favorecer el estilo funcional, utilizando recursividad de cola y continuaciones para expresar el flujo de control. Sin embargo, el estilo imperativo todavía es bastante posible. El estilo preferido por muchos programadores de Common Lisp puede parecer más familiar para los programadores acostumbrados a lenguajes estructurados como C, mientras que el preferido por Schemers se parece más a los lenguajes puramente funcionales como Haskell.

Debido a la herencia temprana de Lisp en el procesamiento de listas, tiene una amplia gama de funciones de orden superior relacionadas con la iteración sobre secuencias. En muchos casos en los que se necesitaría un bucle explícito en otros idiomas (como un for en C) en Lisp, la misma tarea se puede lograr con una función de orden superior. (Lo mismo ocurre con muchos lenguajes de programación funcionales).

Un buen ejemplo es una función que en Scheme se llama map y en Common Lisp se llama mapcar . Dada una función y una o más listas, mapcar aplica la función sucesivamente a las listas' elementos en orden, recogiendo los resultados en una nueva lista: 

 ()mapacar # '+ '()1 2 3 4 5) '()10 20 30 40 50)

Esto aplica el + a cada par correspondiente de elementos de la lista, dando como resultado (11 22 33 44 55).

Ejemplos

Aquí hay ejemplos de código Common Lisp.

El mensaje básico "¡Hola, mundo!" programa: 

()impresión "¡Hola, Mundo!")

La sintaxis de Lisp se presta naturalmente a la recursividad. Los problemas matemáticos como la enumeración de conjuntos definidos recursivamente son fáciles de expresar en esta notación. Por ejemplo, para evaluar el factorial de un número: 

()defun factorial ()n) ()si ()cerop n) 1 ()* n ()factorial ()1- n))))

Una implementación alternativa ocupa menos espacio de pila que la versión anterior si el sistema Lisp subyacente optimiza la recursividad de la cola: 

()defun factorial ()n profesionales ()acc 1) ()si ()cerop n) acc ()factorial ()1- n) ()* acc n)))

Compare los ejemplos anteriores con una versión iterativa que utiliza bucle: 

()defun factorial ()n) ()bucle para i desde 1 a n para fac = 1 entonces ()* fac i) finalmente ()retorno fac))

La siguiente función invierte una lista. (La función reverse incorporada de Lisp hace lo mismo). 

()defun - Reverso ()lista) ()Deja ()rentabilidad) ()lista ()e lista) ()empujar e rentabilidad) rentabilidad)

Sistemas de objetos

Se han creado varios sistemas y modelos de objetos encima, al lado o en Lisp, que incluyen:

Sistemas operativos

Varios sistemas operativos, incluidos los sistemas basados en lenguaje, se basan en Lisp (usan características, convenciones, métodos, estructuras de datos, etc.) de Lisp o están escritos en Lisp, incluidos:

Genera, renombrado Open Genera, por Symbolics; Medley, escrito en Interlisp, originalmente una familia de sistemas operativos gráficos que se ejecutaban en las posteriores estaciones de trabajo Star de Xerox; entresuelo; Provisional; ChrysaLisp, por los desarrolladores de Tao Systems' TAOS.