Lisp (históricamente LISP , una abreviatura de "procesamiento de listas") es una familia de lenguajes de programación con una larga historia y una notación de prefijo distintiva, completamente entre paréntesis . [3] Originalmente especificado a fines de la década de 1950, es el segundo lenguaje de programación de alto nivel más antiguo que todavía se usa comúnmente, después de Fortran . [4] [5] Lisp ha cambiado desde sus inicios y han existido muchos dialectos a lo largo de su historia. Hoy, los dialectos Lisp de propósito general más conocidos son Common Lisp , Scheme , Racket y Clojure . [6] [7] [8]
Lisp fue creado originalmente como una notación matemática práctica para programas de computadora , influenciada por (aunque no derivada originalmente de) [9] 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). [10] Como uno de los primeros lenguajes de programación, Lisp fue pionero en muchas ideas en informática , incluidas las estructuras de datos de árbol , la gestión automática del almacenamiento , la tipificación dinámica , los condicionales , las funciones de orden superior , la recursión , el compilador autoalojado , [11] y el bucle de lectura-evaluación-impresión . [12]
El nombre LISP deriva de "LISt Processor" (Procesador de listas enlazadas). [13] Las listas enlazadas son una de las principales estructuras de datos de Lisp , y el código fuente de Lisp está formado por listas. Por lo tanto, los programas de Lisp pueden manipular el código fuente como una estructura de datos, dando lugar a los sistemas de macros que permiten a los programadores crear nuevas 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 expresiones s o listas entre paréntesis. Una llamada a una 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 fque toma tres argumentos se llamaría como .(f arg1 arg2 arg3)
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 "Funciones recursivas de expresiones simbólicas y su cálculo por máquina, parte I". [14] Demostró que con unos pocos operadores simples y una notación para funciones anónimas tomada prestada de Church, se puede construir un lenguaje Turing-completo para algoritmos.
Information Processing Language 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 recursión, que llegaron a usarse en Lisp.
La notación original de McCarthy utilizaba " expresiones M " entre corchetes que se traducirían en expresiones S. A modo de ejemplo, la expresión M car[cons[A,B]]es equivalente a la expresión S. Una vez que se implementó Lisp, los programadores rápidamente optaron por utilizar expresiones S y las expresiones M se abandonaron. Las expresiones M resurgieron con los intentos efímeros de MLisp [15] de Horace Enea y CGOL de Vaughan Pratt .(car (cons A B))
Lisp fue implementado por primera vez por Steve Russell en una computadora IBM 704 usando tarjetas perforadas . [16] Russell había leído el artículo de McCarthy y se dio cuenta (para sorpresa de McCarthy) de que la función eval de Lisp podía implementarse en código máquina .
Según McCarthy [17]
Steve Russell me dijo: mira, ¿por qué no programo este eval ...? y yo le dije: jo, jo, estás confundiendo la teoría con la práctica, este eval está pensado para leer, no para computar. Pero él siguió adelante y lo hizo. Es decir, compiló el eval de mi artículo en código de máquina IBM 704 , corrigió errores y luego lo promocionó como un intérprete de Lisp, lo que ciertamente era. Así que en ese momento Lisp tenía esencialmente la forma que tiene hoy...
El resultado fue un intérprete Lisp funcional que podía utilizarse para ejecutar programas Lisp o, más apropiadamente, "evaluar expresiones Lisp".
Dos macros de lenguaje ensamblador para el IBM 704 se convirtieron en las operaciones primitivas para descomponer listas: car ( Contenido de la parte Dirección del número de Registro) y cdr ( Contenido de la parte Decremento del número de Registro), [18] donde "registro" se refiere a los registros de la unidad central de procesamiento (CPU) de la computadora . Los dialectos Lisp aún usan cary cdr( / k ɑːr / y / ˈ k ʊ d ər / ) para las operaciones que devuelven el primer elemento en una lista y el resto de la lista, respectivamente.
El primer compilador Lisp completo, 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 a una velocidad 40 veces superior a la del intérprete. [19] 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 es mucho más cercano al estilo Lisp moderno que el código anterior de McCarthy.
Las rutinas de recolección de basura fueron desarrolladas por el estudiante de posgrado del MIT Daniel Edwards, antes de 1962. [20]
Durante las décadas de 1980 y 1990, se realizó un gran esfuerzo para unificar el trabajo sobre los nuevos dialectos Lisp (en su mayoría sucesores de Maclisp como ZetaLisp y NIL (Nueva Implementación de Lisp)) en un solo lenguaje. El nuevo lenguaje, Common Lisp , era en cierta medida 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 Information Technology Programming Language Common Lisp".
Desde sus inicios, Lisp estuvo estrechamente vinculado a la comunidad de investigación de inteligencia artificial , especialmente en los sistemas PDP-10 [21] . Lisp se utilizó como implementación del lenguaje Micro Planner , que se utilizó en el famoso sistema de IA SHRDLU . En la década de 1970, a medida que la investigación de IA generó ramificaciones comerciales, el rendimiento de los sistemas Lisp existentes se convirtió en un problema creciente, 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. [22]
A lo largo de 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 defunpara nombrar una función, pero Scheme usa define. [23] Sin embargo, dentro de un dialecto estandarizado, las implementaciones conformes admiten el mismo lenguaje central, pero con diferentes extensiones y bibliotecas.
Después de haber declinado un poco en la década de 1990, Lisp ha experimentado un resurgimiento de interés después de 2000. La mayor parte de la nueva actividad se ha centrado en las implementaciones de Common Lisp , Scheme , Emacs Lisp , Clojure y Racket , e incluye el desarrollo de nuevas bibliotecas y aplicaciones portables.
Muchos programadores nuevos de Lisp se inspiraron en escritores como Paul Graham y Eric S. Raymond para dedicarse a un lenguaje que otros consideraban anticuado. Los nuevos programadores de Lisp a menudo describen el lenguaje como una experiencia reveladora y afirman que son sustancialmente más productivos que otros lenguajes. [36] Este aumento de la conciencia puede contrastarse con el " invierno de la IA " y el breve auge de Lisp a mediados de los años 1990. [37]
En 2010 [actualizar], había once implementaciones de Common Lisp mantenidas activamente. [38]
La comunidad de código abierto ha creado una nueva infraestructura de apoyo: CLiki es una wiki que recopila información relacionada con Common Lisp, el directorio Common Lisp enumera recursos, #lisp es un canal IRC popular y permite compartir y comentar fragmentos de código (con el apoyo de lisppaste, un bot de IRC escrito en Lisp), Planet Lisp [39] recopila los contenidos de varios blogs relacionados con Lisp, en LispForum [40] los usuarios discuten temas de Lisp, Lispjobs [41] es un servicio para anunciar ofertas de trabajo y hay un servicio de noticias semanal, Weekly Lisp News . Common-lisp.net es un sitio de alojamiento para proyectos Common Lisp de código abierto. Quicklisp [42] es un administrador de bibliotecas para Common Lisp.
Los cincuenta años de Lisp (1958-2008) se celebraron en LISP50@OOPSLA. [43] Hay reuniones de usuarios locales periódicas 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 Scheme mantiene activamente más de veinte implementaciones . En la década de 2000 se desarrollaron varias implementaciones nuevas importantes (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon). El estándar de Scheme Revised 5 Report on the Algorithmic Language Scheme [44] fue ampliamente aceptado en la comunidad Scheme. El proceso de Solicitudes de Implementación de Scheme ha creado muchas bibliotecas y extensiones cuasi estándar para Scheme. Las comunidades de usuarios de implementaciones individuales de Scheme siguen creciendo. En 2003 se inició un nuevo proceso de estandarización del lenguaje que condujo al estándar R 6 RS Scheme en 2007. El uso académico de Scheme para la enseñanza de la informática parece haber disminuido un poco. Algunas universidades ya no utilizan Scheme en sus cursos introductorios de informática; [45] [46] El MIT ahora utiliza Python en lugar de Scheme para su programa de informática de pregrado y el curso masivo abierto en línea MITx. [47] [48]
Hay varios dialectos nuevos de Lisp: Arc , Hy , Nu , Liskell y LFE (Lisp Flavored Erlang). El analizador para Julia está implementado 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".
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 influencias principales fueron Lisp Machine Lisp , Maclisp, NIL , S-1 Lisp , Spice Lisp y Scheme. [49] Tiene muchas de las características de Lisp Machine Lisp (un gran dialecto de Lisp utilizado para programar máquinas Lisp ), 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 . Hay implementaciones de Common Lisp disponibles para diferentes plataformas como LLVM , [50] la máquina virtual Java , [51] x86-64, PowerPC, Alpha, ARM, Motorola 68000 y MIPS, [52] y sistemas operativos como Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD y Heroku. [53]
Scheme es un dialecto de alcance estático y recursivo de cola propiamente dicho 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 características estándar pero con ciertas características de implementación (como optimización de llamadas de cola y continuaciones completas ) no especificadas en Common Lisp. Una amplia variedad de paradigmas de programación, incluidos los estilos imperativos, funcionales y de paso de mensajes, encuentran una expresión conveniente en Scheme. Scheme continúa evolucionando con una serie de estándares (Informe revisado sobre el lenguaje algorítmico Scheme) y una serie de Solicitudes de implementación de Scheme .
Clojure es un dialecto de Lisp que se dirige principalmente a la máquina virtual Java , Common Language Runtime (CLR), Python VM, Ruby VM YARV y la compilación a JavaScript . Está diseñado para ser un lenguaje pragmático de propósito general. Clojure obtiene influencias considerables de Haskell y pone un gran énfasis en la inmutabilidad. [54] Clojure proporciona acceso a los marcos y bibliotecas de Java, con sugerencias de tipo opcionales e inferencia de tipo , de modo que las llamadas a Java pueden evitar la reflexión y habilitar operaciones primitivas rápidas. Clojure no está diseñado para ser compatible con versiones anteriores de otros dialectos de Lisp. [55]
Además, los dialectos de Lisp se utilizan como lenguajes de scripting en muchas aplicaciones, siendo los más conocidos Emacs Lisp en el editor Emacs , AutoLISP y posteriormente 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 scripting integrado. Algunos ejemplos son SIOD y TinyScheme , ambos integrados con éxito en el procesador de imágenes GIMP bajo el nombre genérico "Script-fu". [56] LIBREP, un intérprete de Lisp de John Harper basado originalmente en el lenguaje Emacs Lisp , ha sido integrado en el gestor de ventanas Sawfish . [57]
Lisp tiene dialectos estandarizados oficialmente: Esquema R6RS , Esquema R7RS , Esquema IEEE, [58] ANSI Common Lisp e ISO ISLISP .
Paul Graham identifica nueve aspectos importantes de Lisp que lo distinguen de lenguajes existentes como Fortran : [59]
Lisp fue el primer lenguaje en el que la estructura del código del programa se representa de forma fiel y directa en una estructura de datos estándar, una cualidad que mucho más tarde se denominó " homoiconicidad ". De este modo, las funciones de Lisp se pueden manipular, alterar o incluso crear dentro de un programa Lisp sin necesidad de manipulaciones de nivel inferior. Esto se considera generalmente una de las principales ventajas del lenguaje en lo que respecta a su poder expresivo, y lo hace adecuado para macros sintácticas y evaluación metacircular .
McCarthy inventó un condicional que utiliza 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 de Algol 58. Para Lisp, McCarthy utilizó la estructura más general cond . [60] Algol 60 adoptó 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 encapsulantes, paso de mensajes, etc.) en la década de 1970. El sistema de objetos Flavors introdujo el concepto de herencia múltiple y el mixin . El Common Lisp Object System proporciona herencia múltiple, métodos múltiples con múltiples envíos y funciones genéricas de primera clase , lo que produce una forma flexible y poderosa de envío 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 fue solo el segundo lenguaje después de Smalltalk (y todavía es uno de los pocos lenguajes) en poseer un sistema de metaobjetos de este tipo. Muchos años después, Alan Kay sugirió que, como resultado de la confluencia de estas características, sólo Smalltalk y Lisp podían considerarse sistemas de programación orientados a objetos correctamente concebidos. [61]
Lisp introdujo el concepto de recolección automática de basura , en el que el sistema recorre el montón en busca de memoria no utilizada. El uso de Lisp estimuló el progreso de los algoritmos de recolección de basura sofisticados y modernos, como la recolección de basura generacional. [62]
Edsger W. Dijkstra dijo en su conferencia del Premio Turing de 1972:
Con unos pocos principios muy básicos como base, [LISP] ha demostrado una estabilidad notable. Además de eso, LISP ha sido el vehículo de un número considerable de, en cierto sentido, nuestras aplicaciones informáticas más sofisticadas. Se ha dicho en broma que LISP es "la forma más inteligente de hacer un 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 muchos de nuestros compañeros humanos más dotados a pensar cosas que antes eran imposibles. [63]
En gran medida debido a sus requerimientos 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. [64]
Lisp es un lenguaje orientado a expresiones . A diferencia de la mayoría de los demás lenguajes, no se hace distinción entre "expresiones" y "declaraciones" ; [ dudoso – discutir ] todo el código y los datos se escriben como expresiones. Cuando se evalúa una expresión , produce un valor (posiblemente varios valores), que luego se puede incorporar a otras expresiones. Cada valor puede ser de cualquier tipo de datos.
El artículo de McCarthy de 1958 introdujo dos tipos de sintaxis: expresiones simbólicas ( S-expresions , sexps), que reflejan la representación interna del código y los datos; y metaexpresiones ( M-expresions ), que expresan funciones de las S-expresiones. Las M-expresiones nunca fueron bien recibidas, y casi todos los Lisp actuales utilizan S-expresiones para manipular tanto el código como los datos.
El uso de paréntesis es la diferencia más obvia de Lisp con otras familias de lenguajes de programación. Como resultado, los estudiantes han dado apodos a Lisp como Perdido en paréntesis estúpidos o Montones de paréntesis superfluos irritantes . [65] Sin embargo, la sintaxis de expresión S también es responsable de gran parte de la potencia 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 tradicional de paréntesis. Puede extenderse 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 expresiones le da al lenguaje una gran flexibilidad. Como las funciones de Lisp se escriben como listas, se pueden procesar exactamente como datos. Esto permite escribir fácilmente programas que manipulen otros programas ( metaprogramación ). Muchos dialectos de Lisp aprovechan esta característica mediante sistemas de macros, lo que permite una extensión del lenguaje casi sin límites.
Una lista Lisp se escribe con sus elementos separados por espacios en blanco y rodeados por paréntesis. Por ejemplo, es una lista cuyos elementos son los tres átomos , y . Estos valores están tipificados 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.(1 2 foo) 12foo
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, utilizando la notación de prefijo . 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" (ver más abajo). El resto de la lista son los argumentos. Por ejemplo, la función listdevuelve sus argumentos como una lista, por lo que la expresión
( lista 1 2 ( cita foo )) evalúa la lista . La "comilla" antes del en el ejemplo anterior es un "operador especial" que devuelve su argumento sin evaluarlo. Cualquier expresión sin comillas se evalúa recursivamente antes de que se evalúe la expresión que la encierra. Por ejemplo,(1 2 foo)foo
( lista 1 2 ( lista 3 4 )) se evalúa como la lista . El tercer argumento es una lista; las listas pueden estar anidadas.(1 2 (3 4))
Los operadores aritméticos se tratan de manera similar. La expresión
( + 1 2 3 4 ) evalúa a 10. El equivalente bajo notación infija sería " ".1 + 2 + 3 + 4
Lisp no tiene noción de operadores como los implementados en lenguajes derivados de Algol. Los operadores aritméticos en Lisp son funciones variádicas (o n-arias ), capaces de tomar cualquier número de argumentos. Un operador de incremento '++' estilo C a veces se implementa bajo el nombre de incfsintaxis que da
( incluye x ) equivalente a (setq x (+ x 1)), devolviendo el nuevo valor de x.
Los "operadores especiales" (a veces llamados "formas especiales") proporcionan la estructura de control de Lisp. Por ejemplo, el operador especial iftoma 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. Por lo tanto, la expresión
( si es nulo ( lista 1 2 "foo" ) ( lista 3 4 "bar" )) evalúa como . Por supuesto, esto sería más útil si se hubiera sustituido una expresión no trivial en lugar de .(3 4 "bar")nil
Lisp también ofrece operadores lógicos and , or y not . 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 'tiempo ) evaluará a "James".
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 utiliza para crear funciones: los argumentos lambdason una lista de argumentos y la expresión o expresiones que evalúa la función (el valor devuelto es el valor de la última expresión que se evalúa). La expresión
( lambda ( arg ) ( + arg 1 )) se evalúa como una función que, cuando se aplica, toma un argumento, lo vincula argy devuelve el número uno mayor que ese argumento. Las expresiones lambda no se tratan de manera diferente a las funciones con nombre; se invocan de la misma manera. Por lo tanto, la expresión
(( lambda ( arg ) ( + arg 1 )) 5 ) 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 utilizando la macro defun.
( defun foo ( a b c d ) ( + a b c d )) (defun f (a) b...)define una nueva función nombrada fen el entorno global. Es conceptualmente similar a la expresión:
( setf ( fdefinition 'f ) #' ( lambda ( a ) ( bloque f b... ))) donde setfes una macro utilizada para establecer el valor del primer argumento de un nuevo objeto de función. es una definición de función global para la función denominada . es una abreviatura de operador especial, que devuelve un objeto de función.fdefinition 'ffdefinitionf#'function
En el LISP original había dos tipos de datos fundamentales : átomos y listas. Una lista era una secuencia finita y ordenada de elementos, donde cada elemento era 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 un elemento de datos en el procesamiento simbólico . Por ejemplo, la lista contiene tres elementos: el símbolo , la lista y el número 2.(FOO (BAR 1) 2)FOO(BAR 1)
La diferencia esencial entre átomos y listas era que los átomos eran inmutables y únicos. Dos átomos que aparecían en diferentes lugares del código fuente pero que estaban escritos exactamente de la misma manera representaban el mismo objeto, [ cita requerida ] 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 los dialectos Lisp posteriores y evolucionaron los estilos de programación , el concepto de átomo perdió importancia. [ cita requerida ] Muchos dialectos aún conservaron el predicado átomo para compatibilidad heredada , [ cita requerida ] definiéndolo como verdadero para cualquier objeto que no sea un cons.
Una lista Lisp se implementa como una lista enlazada simple . [66] Cada celda de esta lista se denomina cons (en Scheme, un par ) y está compuesta por dos punteros , llamados car y cdr . Estos son respectivamente equivalentes a los campos datay nextdiscutidos en el artículo lista enlazada .
De las muchas estructuras de datos que se pueden construir a partir de celdas cons, una de las más básicas se denomina lista propia . Una lista propia es el nilsímbolo especial (lista vacía) o un cons en el que carapunta a un dato (que puede ser otra estructura cons, como una lista) y cdrapunta a otra lista propia.
Si se toma un cons dado como la cabeza 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, las funciones carand cdrtambién se llaman firstand restcuando se hace referencia a conses que son parte de una lista enlazada (en lugar de, por ejemplo, un árbol).
Por lo tanto, una lista de 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 cons enlazados. Una variable que hace referencia a una lista dada es simplemente un puntero a los primeros cons de la lista. El recorrido de una lista se puede hacer haciendo un cdring hacia abajo en la lista; es decir, tomando cdrs sucesivos para visitar cada cons de la lista; o usando cualquiera de varias funciones de orden superior para mapear una función sobre una lista.
Debido a que las conses y las listas son tan universales en los sistemas Lisp, es un error común creer que son las únicas estructuras de datos de Lisp. De hecho, todos los sistemas Lisp, excepto los más simples, tienen otras estructuras de datos, como vectores ( matrices ), tablas hash , estructuras, etc.
Las S-expresiones entre paréntesis representan estructuras de listas enlazadas. Hay varias formas de representar la misma lista como una S-expresión. Una cons se puede escribir en notación de pares de puntos como , donde es el car y el cdr. Una lista propia más larga se puede escribir en notación de pares de puntos. Esto se abrevia convencionalmente como en notación de lista . Una lista impropia [67] se puede escribir en una combinación de los dos - como para la lista de tres conses cuyo último cdr es (es decir, la lista en forma completamente especificada).(a . b)ab(a . (b . (c . (d . nil))))(a b c d)(a b c . d)d(a . (b . (c . d)))
Lisp ofrece muchos procedimientos integrados para acceder a listas y controlarlas. Las listas se pueden crear directamente con el listprocedimiento, que acepta cualquier cantidad de argumentos y devuelve la lista de estos argumentos.
( lista 1 2 'a 3 ) ;Salida: (1 2 a 3) ( lista 1 ' ( 2 3 ) 4 ) ;Salida: (1 (2 3) 4) Debido a la forma en que se construyen las listas a partir de pares cons , el consprocedimiento se puede utilizar para agregar un elemento al principio de una lista. El consprocedimiento es asimétrico en la forma en que maneja los argumentos de la lista, debido a la forma en que se construyen las listas.
( cons 1 ' ( 2 3 )) ;Salida: (1 2 3) ( cons ' ( 1 2 ) ' ( 3 4 )) ;Salida: ((1 2) 3 4) El appendprocedimiento agrega dos (o más) listas entre sí. Debido a que las listas de Lisp son listas enlazadas, agregar dos listas tiene una complejidad temporal asintótica.
( añadir ' ( 1 2 ) ' ( 3 4 )) ;Salida: (1 2 3 4) ( añadir ' ( 1 2 3 ) ' () ' ( a ) ' ( 5 6 )) ;Salida: (1 2 3 a 5 6) Las listas de Lisp, al ser listas enlazadas simples, pueden compartir estructura entre sí. Es decir, dos listas pueden tener la misma cola , o secuencia final de conses. Por ejemplo, después de la ejecución del siguiente código de Common Lisp:
( setf foo ( lista 'a 'b 'c )) ( setf bar ( cons 'x ( cdr foo ))) Las listas fooy barson y respectivamente. Sin embargo, la cola es la misma estructura en ambas listas. No es una copia; las celdas cons que apuntan a y están en las mismas ubicaciones de memoria para ambas listas.(a b c)(x b c)(b c)bc
Compartir la estructura en lugar de copiarla puede dar lugar a una mejora espectacular del rendimiento. Sin embargo, esta técnica puede interactuar de forma no deseada con funciones que alteran las listas que se les pasan como argumentos. Alterar una lista, por ejemplo, reemplazando el ccon un goose, afectará a la otra:
( setf ( tercer foo ) 'ganso ) Esto cambia fooa , pero por lo tanto también cambia a – un resultado posiblemente inesperado. Esto puede ser una fuente de errores y las funciones que alteran sus argumentos están documentadas como destructivas por este mismo motivo.(a b goose)bar(x b goose)
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!(read set car bang ), que reemplaza el car de un cons. En el dialecto Common Lisp, las funciones destructivas son habituales; el equivalente de set-car!se llama así rplacapor "replace car". 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 cuando sea seguro hacerlo.
Lisp evalúa expresiones que son ingresadas por el usuario. Los símbolos y listas evalúan a otra expresión (generalmente, más simple); por ejemplo, un símbolo evalúa al valor de la variable que nombra; evalúa a . Sin embargo, la mayoría de las otras formas evalúan a sí mismas: si se ingresa en Lisp, devuelve .(+ 2 3)555
También se puede marcar cualquier expresión para evitar que se evalúe (como es necesario para los símbolos y las listas). Esta es la función del quoteoperador especial, o su abreviatura '(una comilla). Por ejemplo, normalmente si se introduce el símbolo foo, devuelve el valor de la variable correspondiente (o un error, si no existe dicha variable). Para hacer referencia al símbolo literal, se introduce o, normalmente, .(quote foo)'foo
Tanto Common Lisp como Scheme también admiten el operador de comillas invertidas (denominado quasiquote en Scheme), que se introduce con el `carácter ( acento grave ). Es casi lo mismo que las comillas simples, excepto que permite evaluar expresiones e interpolar sus valores en una lista entre comillas con los operadores de coma , sin comillas y coma-at ,@ splice . Si la variable snuetiene el valor , se evalúa como , mientras que se evalúa como . Las comillas invertidas se utilizan con mayor frecuencia para definir expansiones de macros. [68] [69](bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)
Las formas autoevaluables y las formas entrecomilladas son el equivalente de los literales en Lisp. Es posible modificar los valores de los literales (mutables) en el código del programa. Por ejemplo, si una función devuelve una forma entrecomillada y el código que llama a la función modifica la forma, esto puede alterar el comportamiento de la función en invocaciones posteriores.
( defun debe ser constante () ' ( uno dos tres )) ( let (( cosas ( debería-ser-constante ))) ( setf ( tercera cosas ) 'extraño )) ; ¡malo! ( debería ser constante ) ; devuelve (uno dos extraño) Modificar una forma citada de esta manera generalmente se considera un mal estilo y ANSI Common Lisp lo define como erróneo (dando como resultado un comportamiento "indefinido" en los archivos compilados, porque el compilador de archivos puede fusionar constantes similares, ponerlas en una memoria protegida contra escritura, etc.).
La formalización de la cita de Lisp ha sido señalada por Douglas Hofstadter (en Gödel, Escher, Bach ) y otros como un ejemplo de la idea filosófica de la autorreferencia .
La familia Lisp se divide en función del uso de ámbito 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 ámbito dinámico como el léxico.
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.) que utilizaría el sistema Lisp subyacente.
Lisp utiliza esto para implementar un sistema de macros muy potente. Al igual que otros lenguajes de macros, como el definido por el preprocesador de 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 de C, las macros son funciones de Lisp y, por lo tanto, pueden aprovechar toda la potencia de Lisp.
Además, debido a 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, todo lo que Lisp puede hacer con una estructura de datos, las macros Lisp lo pueden hacer con el código. Por el contrario, en la mayoría de los demás lenguajes, la salida del analizador es puramente interna a la implementación del lenguaje y no puede ser manipulada por el programador.
Esta característica facilita el desarrollo de lenguajes eficientes dentro de lenguajes. Por ejemplo, el sistema de objetos Common Lisp se puede implementar de forma clara como una extensión del lenguaje mediante macros. Esto significa que si una aplicación necesita un mecanismo de herencia diferente, puede utilizar un sistema de objetos diferente. Esto contrasta marcadamente con la mayoría de los demás lenguajes; por ejemplo, Java no admite la herencia múltiple y no hay una forma razonable de agregarla.
En las implementaciones simplistas de Lisp, esta estructura de lista se interpreta directamente para ejecutar el programa; una función es literalmente un fragmento de una estructura de lista que el intérprete recorre al ejecutarla. Sin embargo, la mayoría de los sistemas Lisp importantes también incluyen un compilador. El compilador traduce la estructura de lista en código de máquina o bytecode 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 puede 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-whenque permite que el código esté presente durante el tiempo de compilación (cuando una macro lo necesitaría), pero no presente en el módulo emitido. [70]
Los lenguajes Lisp suelen utilizarse con una línea de comandos interactiva , que puede combinarse con un entorno de desarrollo integrado (IDE). El usuario escribe expresiones en la línea de comandos o indica al IDE que las transmita al sistema Lisp. Lisp lee las expresiones introducidas, las evalúa e imprime el resultado. Por este motivo, la línea de comandos de Lisp se denomina bucle de lectura, evaluación e impresión ( REPL ).
El funcionamiento básico de REPL es el siguiente. Se trata de una descripción simplista que omite muchos elementos de un Lisp real, como las comillas y las macros.
La readfunción acepta expresiones S textuales como entrada y las analiza en una estructura de datos interna. Por ejemplo, si escribe el texto en el indicador, lo traduce en una lista enlazada con tres elementos: el símbolo , el número 1 y el número 2. Resulta que esta lista también es un fragmento válido de código Lisp; es decir, se puede evaluar. Esto se debe a que el nombre de la lista nombra una función: la operación de suma.(+ 1 2)read+
A foose leerá como un solo símbolo. 123se leerá como el número ciento veintitrés. "123"se leerá como la cadena "123".
La evalfunción evalúa los datos y devuelve cero o más datos Lisp como resultado. La 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 sencillo describir la evaluación como interpretación: para evaluar una lista cuyo car nombra una función, evalprimero se evalúa cada uno de los argumentos dados en su cdr y luego se aplica la función a los argumentos. En este caso, la función es la suma y al aplicarla a la lista de argumentos se obtiene la respuesta . Este es el resultado de la evaluación.(1 2)3
El símbolo foose evalúa como el valor del símbolo foo. Los datos como la cadena "123" se evalúan como la misma cadena. La lista se evalúa como la lista (1 2 3).(quote (1 2 3))
La printfunción tiene como función representar la salida al usuario. Un resultado tan simple como 3este es trivial. Una expresión que se evaluara como un fragmento de una estructura de lista requeriría printrecorrer la lista e imprimirla como una expresión S.
Para implementar un REPL de Lisp, solo es necesario implementar estas tres funciones y una función de bucle infinito. (Naturalmente, la implementación de evalserá compleja, ya que también debe implementar todos los operadores especiales como ifo lambda). Una vez hecho esto, un REPL básico es una línea de código: .(loop (print (eval (read))))
El REPL de Lisp normalmente también proporciona edición de entrada, un historial de entrada, manejo de errores y una interfaz con el depurador.
Lisp se evalúa habitualmente con entusiasmo . En Common Lisp , los argumentos se evalúan en orden aplicativo ('más a la izquierda más al interior'), 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.
Originalmente, Lisp 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-elseestructuras posteriores).
Los programadores en el dialecto Scheme a menudo expresan bucles utilizando recursión de cola . La similitud de Scheme en la informática académica ha llevado a algunos estudiantes a creer que la recursión de cola es la única forma, o la más común, de escribir iteraciones en Lisp, pero esto es incorrecto. Todos los dialectos Lisp que se ven a menudo tienen construcciones de iteración de estilo imperativo, desde el dobucle de Scheme hasta las expresiones complejas de Common Lisploop . 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 las llamadas de cola y, por lo tanto, la razón por la que el uso de la recursión de cola generalmente se fomenta para Scheme es que la práctica está expresamente respaldada por la definición del lenguaje. Por el contrario, ANSI Common Lisp no requiere [71] la optimización comúnmente denominada eliminación de llamadas de cola. Por lo tanto, el hecho de que el estilo recursivo de cola como reemplazo casual para el uso de construcciones de iteración más tradicionales (como do, dolisto loop) se desaconseje [72] en Common Lisp no es solo una cuestión de preferencia estilística, sino potencialmente una cuestión 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 la recursión de cola puede aumentar el uso de la pila en Common Lisp, con el riesgo de desbordamiento de pila ).
Algunas estructuras de control de Lisp son operadores especiales , equivalentes a las palabras clave sintácticas de otros lenguajes. Las expresiones que utilizan estos operadores tienen la misma apariencia superficial que las llamadas a funciones, pero difieren 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 lenguajes de programación principales, Lisp permite implementar estructuras de control mediante el lenguaje. Varias estructuras de control se implementan como macros de Lisp, e incluso pueden ser ampliadas por el programador que desee saber cómo funcionan.
Tanto Common Lisp como Scheme tienen operadores para el flujo de control no local. Las diferencias entre estos operadores son algunas de las diferencias más profundas entre los dos dialectos. Scheme admite continuaciones reentrantes mediante el call/ccprocedimiento, que permite que un programa guarde (y luego restaure) un lugar particular en la ejecución. Common Lisp no admite continuaciones reentrantes, pero sí admite varias formas de manejar 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 recursión 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 Scheme se asemeja 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 lenguajes (como un forbucle en C), en Lisp se puede lograr la misma tarea con una función de orden superior. (Lo mismo sucede con muchos lenguajes de programación funcional).
Un buen ejemplo es una función que en Scheme se llama mapy en Common Lisp se llama mapcar. Dada una función y una o más listas, mapcaraplica la función sucesivamente a los elementos de las listas en orden, recopilando los resultados en una nueva lista:
( mapacar #' + ' ( 1 2 3 4 5 ) ' ( 10 20 30 40 50 )) Esto aplica la +función a cada par correspondiente de elementos de la lista, produciendo el resultado .(11 22 33 44 55)
A continuación se muestran ejemplos de código Common Lisp.
El programa básico " ¡Hola, mundo! ":
( imprimir "¡Hola, mundo!" ) La sintaxis de Lisp se presta naturalmente a la recursión. 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 ) ( if ( zerop 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 recursión de cola :
( defun factorial ( n & opcional ( acc 1 )) ( si ( zerop n ) acc ( factorial ( 1- n ) ( * acc n )))) Compare los ejemplos anteriores con una versión iterativa que utiliza la macro de Common Lisploop :
( defun factorial ( n ) ( bucle para i desde 1 hasta n para fac = 1 entonces ( * fac i ) finalmente ( devuelve fac ))) La siguiente función invierte una lista. (La función reverse incorporada de Lisp hace lo mismo).
( defun -reverse ( lista ) ( let (( valor-de-retorno )) ( dolist ( e lista ) ( push e valor-de-retorno )) valor-de-retorno )) Se han creado varios sistemas y modelos de objetos sobre, junto con o dentro de Lisp, incluidos
Varios sistemas operativos , incluidos los sistemas basados en lenguajes , se basan en Lisp (utilizan características, convenciones, métodos, estructuras de datos, etc. de Lisp) o están escritos en Lisp, [75] incluidos:
Genera , renombrado Open Genera, [76] por Symbolics ; Medley, escrito en Interlisp, originalmente una familia de sistemas operativos gráficos que se ejecutaban en las estaciones de trabajo Star posteriores de Xerox ; [77] [78] Mezzano; [79] Interim; [80] [81] ChrysaLisp, [82] por los desarrolladores de TAOS de Tao Systems. [83] y también Guix
Lisp es un superviviente, ya que lleva utilizándose alrededor de un cuarto de siglo. Entre los lenguajes de programación activos, sólo Fortran ha tenido una vida más larga.
y fascinantes es LISP (que significa "List Processing"), que fue inventado por John McCarthy en la época en que se inventó Algol. Posteriormente, LISP ha gozado de gran popularidad entre los trabajadores de la inteligencia artificial.
El proyecto PDP-6 comenzó a principios de 1963, como una máquina de 24 bits. Creció hasta los 36 bits para LISP, un objetivo de diseño.
(defun f (x) x)(define f (lambda (x) x))o(define (f x) x)Clojure es un Lisp que no está limitado por la compatibilidad con versiones anteriores
Inventé expresiones condicionales en relación con un conjunto de rutinas de movimientos legales de ajedrez que escribí en FORTRAN para el IBM 704 en el MIT durante 1957-58... Un artículo que definía expresiones condicionales y proponía su uso en Algol fue enviado a Comunicaciones de la ACM pero fue arbitrariamente degradado a una carta al editor, porque era muy breve.
En aquel momento no entendía la idea monstruosa de LISP de un metalenguaje tangible, pero me acerqué un poco a las ideas sobre lenguajes extensibles... La segunda fase de esto fue finalmente entender LISP y luego usar esta comprensión para hacer subestructuras mucho más bonitas, más pequeñas, más poderosas y con más enlaces tardíos... Para mí, OOP significa solo mensajería, retención local, protección y ocultamiento de procesos de estado y enlaces tardíos extremos de todas las cosas. Se puede hacer en Smalltalk y en LISP. Es posible que haya otros sistemas en los que esto sea posible, pero no los conozco.
Definiciones de Wikcionario
Medios de comunicación de Commons
Citas de Wikiquote
Textos de Wikisource
Libros de texto de Wikilibros
Recursos de Wikiversidad