Lisp (históricamente LISP , abreviatura de "procesamiento de listas") es una familia de lenguajes de programación con una larga historia y una notación de prefijo distintiva y completamente entre paréntesis . [3] Especificado originalmente en 1960, es el tercer lenguaje de programación de alto nivel más antiguo que aún se usa comúnmente, después de Fortran y COBOL . [4] [5] 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 uso general más conocidos son Common Lisp , Scheme , Racket y Clojure . [6] [7] [8]
Lisp se creó 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 estructuras de datos en árbol , gestión automática de almacenamiento , escritura dinámica , condicionales , funciones de orden superior , recursividad , el compilador autohospedado , [11] y el bucle lectura-evaluación-impresión . [12]
El nombre LISP deriva de "LISt Processor". [13] 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, dando lugar a macrosistemas que permiten a los programadores crear nueva sintaxis o nuevos lenguajes de dominio específico 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 está escrito como expresiones-s o listas entre paréntesis. Una llamada a 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 de Tecnología 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 computación por máquina, Parte I". [14] Demostró que con unos pocos operadores simples y una notación para funciones anónimas tomada de Church, se puede construir un lenguaje completo de Turing para algoritmos.
El lenguaje de procesamiento de información fue el primer lenguaje de inteligencia artificial , 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 utilizaba " expresiones M " entre corchetes que se traducirían a expresiones S. Por ejemplo, la expresión M es car[cons[A,B]]equivalente a la expresión S. Una vez que se implementó Lisp, los programadores rápidamente optaron por utilizar expresiones S y se abandonaron las expresiones M. Las expresiones M volvieron a surgir con intentos de corta duración 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 de evaluación de Lisp podría implementarse en código de máquina .
Según McCarthy [17]
Steve Russell dijo, mira, por qué no programo este eval ... y le dije, ho, ho, estás confundiendo teoría con práctica, este eval está pensado para lectura, no para computación. Pero él siguió adelante y lo hizo. Es decir, compiló la evaluación de mi artículo en código de máquina IBM 704 , corrigiendo errores , y luego lo anunció como un intérprete Lisp, que ciertamente lo era. Entonces en ese momento Lisp tenía esencialmente la forma que tiene hoy...
El resultado fue un intérprete Lisp funcional que podría usarse para ejecutar programas Lisp o, más correctamente, "evaluar expresiones Lisp".
Dos macros en lenguaje ensamblador para 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 registros de la unidad central de procesamiento (CPU) de la computadora . Los dialectos Lisp todavía usan cary cdr( / k ɑːr / y / ˈ k ʊ d ər / ) para las operaciones que devuelven el primer elemento de 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 40 -Mejora en velocidad con respecto a la del intérprete. [19] Este compilador introdujo el modelo Lisp de compilación incremental , en el que las funciones compiladas e interpretadas se pueden mezclar 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. [20]
Durante las décadas de 1980 y 1990, se hizo un gran esfuerzo para unificar el trabajo sobre nuevos dialectos Lisp (en su mayoría sucesores de Maclisp como ZetaLisp y NIL (Nueva implementación de Lisp) en un solo idioma. El nuevo lenguaje, 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 Information Technology Programming Language Common Lisp".
Desde sus inicios, Lisp estuvo estrechamente relacionado con la comunidad de investigación en 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 inteligencia artificial SHRDLU . En la década de 1970, cuando la investigación de la IA generó ramificaciones comerciales, el rendimiento de los sistemas Lisp existentes se convirtió en un problema creciente, ya que los programadores necesitaban estar familiarizados 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 determinado 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 que está estandarizado, las implementaciones conformes admiten el mismo lenguaje central, pero con diferentes extensiones y bibliotecas.
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 nueva actividad se ha centrado en implementaciones de Common Lisp , Scheme , Emacs Lisp , Clojure y Racket , e incluye el desarrollo de nuevas bibliotecas y aplicaciones portátiles.
Muchos nuevos programadores de Lisp se inspiraron en escritores como Paul Graham y Eric S. Raymond para desarrollar un lenguaje que otros consideraban anticuado. Los programadores de New Lisp a menudo describen el lenguaje como una experiencia reveladora y afirman ser sustancialmente más productivos que en otros lenguajes. [36] Este aumento en la conciencia puede contrastarse con el " invierno de la IA " y el breve avance de Lisp a mediados de la década de 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 soporte: CLiki es un 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 soporte de lisppaste, un bot IRC escrito en Lisp), Planet Lisp [39] recopila el contenido 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 una noticia semanal Servicio, noticias semanales de Lisp . Common-lisp.net es un sitio de alojamiento para proyectos Common Lisp de código abierto. Quicklisp [42] es un administrador de biblioteca para Common Lisp.
Se celebraron cincuenta años de Lisp (1958-2008) en LISP50@OOPSLA. [43] Hay reuniones locales periódicas de usuarios en Boston, Vancouver y Hamburgo. Otros eventos incluyen la Reunión Europea Common Lisp, el Simposio Europeo Lisp y una Conferencia Internacional Lisp.
La comunidad Scheme mantiene activamente más de veinte implementaciones . En la década de 2000 se desarrollaron varias implementaciones nuevas e importantes (Chicken, Gambit, Gauche, Ikarus, Larceny, Ypsilon). El estándar del Informe Revisado 5 sobre el Esquema de Lenguaje Algorítmico [44] fue ampliamente aceptado en la comunidad de Scheme. El proceso de Solicitudes de implementación de Scheme ha creado muchas bibliotecas y extensiones casi estándar para Scheme. Las comunidades de usuarios de implementaciones individuales de Scheme continúan 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 informática parece haber disminuido un poco. Algunas universidades ya no utilizan Scheme en sus cursos de introducción a la informática; [45] [46] El MIT ahora usa Python en lugar de Scheme para su programa de pregrado en ciencias de la computación y su curso en línea abierto masivo del MITx. [47] [48]
Hay varios dialectos nuevos de Lisp: Arc , Hy , Nu , Liskell y LFE (Lisp Flavored Erlang). El analizador de 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 del 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 dialecto Lisp grande utilizado para programar Lisp Machines ), pero fue diseñado para ser implementable 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, funciones, macros y otros elementos del lenguaje integrados, 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 comunes de Lisp están disponibles para apuntar a 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 propia 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 tiene 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 estilos imperativos, funcionales y de paso de mensajes, encuentran una expresión conveniente en Scheme. El esquema continúa evolucionando con una serie de estándares ( Informe n revisado sobre el esquema del lenguaje algorítmico) y una serie de solicitudes de implementación del esquema .
Clojure es un dialecto de Lisp que se dirige principalmente a la máquina virtual Java y Common Language Runtime (CLR), Python VM, Ruby VM YARV y a la compilación en JavaScript . Está diseñado para ser un lenguaje pragmático de propósito general. Clojure obtiene considerables influencias de Haskell y pone un fuerte énfasis en la inmutabilidad. [54] Clojure proporciona acceso a marcos y bibliotecas de Java, con sugerencias de tipo e inferencia de tipos 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 compatible con otros dialectos Lisp. [55]
Además, los dialectos Lisp se utilizan como lenguajes de programación en muchas aplicaciones, siendo los más conocidos Emacs Lisp en el editor 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 bajo el nombre genérico "Script-fu". [56] LIBREP, un intérprete Lisp de John Harper basado originalmente en el lenguaje Emacs Lisp , se ha integrado en el administrador de ventanas Sawfish . [57]
Lisp tiene dialectos oficialmente estandarizados: R6RS Scheme , R7RS Scheme , IEEE Scheme, [58] ANSI Common Lisp e ISO ISLISP .
Paul Graham identifica nueve aspectos importantes de Lisp que lo distinguían de lenguajes existentes como Fortran : [59]
Lisp fue el primer lenguaje donde la estructura del código del programa se representa fiel y directamente en una estructura de datos estándar, una cualidad mucho más tarde denominada " 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 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 formó parte de la especificación Algol 58 . Para Lisp, McCarthy utilizó la estructura de condiciones más general . [60] Algol 60 retomó if-then-else y lo popularizó.
Lisp influyó profundamente en Alan Kay , líder del equipo de investigación que desarrolló Smalltalk en Xerox PARC ; y, a su vez, Lisp fue influenciado por Smalltalk, y dialectos posteriores adoptaron características de programación orientada a objetos (clases de herencia, instancias de encapsulación, paso de mensajes, etc.) en la década de 1970. El sistema de objetos Flavors introdujo el concepto de herencia múltiple y mixin . El sistema de objetos Common Lisp proporciona herencia múltiple, múltiples métodos con envío múltiple y funciones genéricas de primera clase , lo que produce una forma flexible y poderosa de envío dinámico . Ha servido como modelo para muchos sistemas de objetos Lisp posteriores (incluido Scheme ), que a menudo se implementan mediante 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 sólo el segundo lenguaje. después de Smalltalk (y sigue siendo uno de los pocos lenguajes) que posee tal sistema de metaobjetos. 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 en Lisp estimuló el progreso en algoritmos modernos y sofisticados de recolección de basura, como la recolección de basura generacional. [62]
Edsger W. Dijkstra en su conferencia del Premio Turing de 1972 dijo:
Con unos pocos principios muy básicos en su base, [LISP] ha demostrado una estabilidad notable. Además de eso, LISP ha sido el portador de un número considerable de, en cierto sentido, nuestras aplicaciones informáticas más sofisticadas. LISP ha sido descrito en broma como "la forma más inteligente de hacer un mal uso de una computadora". Creo que esa descripción es un gran cumplido porque transmite todo el sabor de la liberación: ha ayudado a varios de nuestros semejantes más talentosos a tener pensamientos que antes eran imposibles. [63]
En gran parte debido a sus requisitos de recursos con respecto al hardware informático inicial (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 cierto 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 idiomas, no se hace distinción entre "expresiones" y "declaraciones" ; [ dudoso ] todo el código y los datos están escritos como expresiones. Cuando se evalúa una expresión , produce un valor (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 aceptación, y casi todos los Lisps hoy en día usan expresiones S para manipular código y 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, durante mucho tiempo los estudiantes le han dado a Lisp apodos como Lost In Stupid Parentheses o Lots of Irritating Superfluous Parentheses . [65] Sin embargo, la sintaxis de 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 tradicional entre paréntesis. 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 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 Lisp explotan esta característica utilizando sistemas macro, lo que permite la extensión del idioma casi sin límites.
Una lista Lisp se escribe con sus elementos separados por espacios en blanco y entre paréntesis. Por ejemplo, es una lista cuyos elementos son los tres átomos , y . 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 es necesario declararlos 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 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 a la lista . La "comilla" antes de 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 evaluar la expresión adjunta. Por ejemplo,(1 2 foo)foo
( lista 1 2 ( lista 3 4 )) evalúa a la lista . El tercer argumento es una lista; Las listas se pueden anidar.(1 2 (3 4))
Los operadores aritméticos se tratan de manera similar. La expresion
( + 1 2 3 4 ) se evalúa como 10. El equivalente bajo notación infija sería " ".1 + 2 + 3 + 4
Lisp no tiene noción de los operadores implementados en los lenguajes derivados de Algol. Los operadores aritméticos en Lisp son funciones variadas (o n-arias ), capaces de tomar cualquier número de argumentos. A veces se implementa un operador de incremento '++' de estilo C bajo el nombre incfque proporciona la sintaxis.
( incf x ) equivalente a (setq x (+ x 1))devolver 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 según el tercer argumento. Así, la expresión
( si es nulo ( lista 1 2 "foo" ) ( lista 3 4 "bar" )) evalúa a . Por supuesto, esto sería más útil si se hubiera sustituido por una expresión no trivial en lugar de .(3 4 "bar")nil
Lisp también proporciona 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" ' tiempo de tarea' ) evaluará a "James".
Otro operador especial, lambdase 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 son lambdauna lista de argumentos y la expresión o expresiones a las que se 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 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 tanto, la expresión
(( lambda ( arg ) ( + arg 1 )) 5 ) evalúa a 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 nombrada fen el entorno global. Es conceptualmente similar a la expresión:
( setf ( fdefinición 'f ) #' ( lambda ( a ) ( bloque f b... ))) ¿Dónde setfse utiliza una macro 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 y 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 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 en el código fuente pero que estaban escritos exactamente de la misma manera representaban el mismo objeto, [ cita necesaria ] 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 los estilos de programación evolucionaron, el concepto de átomo perdió importancia. [ cita necesaria ] Muchos dialectos aún conservan el predicado átomo para compatibilidad heredada , [ cita necesaria ] definiéndolo verdadero para cualquier objeto que no sea una desventaja.
Una lista Lisp se implementa como una lista enlazada individualmente . [66] Cada celda de esta lista se llama contras (en Scheme, un par ) y está compuesta por dos punteros , llamados auto y cdr . Estos son respectivamente equivalentes a los campos datay nextdiscutidos en la lista vinculada del artículo .
De las muchas estructuras de datos que se pueden construir a partir de celdas de contras, una de las más básicas se llama lista adecuada . Una lista adecuada es el nilsímbolo especial (lista vacía) o una contra en la que carapunta a un dato (que puede ser otra estructura de contras, como una lista) y apunta cdra otra lista adecuada.
Si se considera que un contras determinado es el encabezado de una lista vinculada, entonces su auto apunta al primer elemento de la lista y su cdr apunta al resto de la lista. Por esta razón, las funciones cary cdrtambién se llaman firsty restcuando se hace referencia a conses que forman parte de una lista enlazada (en lugar de, 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 conjunto de inconvenientes vinculados. Una variable que hace referencia a una lista determinada es simplemente un puntero a los primeros inconvenientes de la lista. Se puede recorrer una lista desplazándola hacia abajo ; es decir, tomando cdrs sucesivos para visitar cada contra de la lista; o utilizando cualquiera de varias funciones de orden superior para asignar una función a una lista.
Debido a que los conjuntos 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 los Lisps, excepto los más simplistas, tienen otras estructuras de datos, como vectores ( matrices ), tablas hash , estructuras, etc.
Las expresiones S entre paréntesis representan estructuras de listas vinculadas. Hay varias formas de representar la misma lista como una expresión S. Un contra se puede escribir en notación de par de puntos como , ¿dónde está el automóvil y el cdr? Se podría escribir una lista adecuada más larga en notación de pares de puntos. Esto se abrevia convencionalmente como en notación de lista . Una lista impropia [67] puede escribirse en una combinación de los dos, como ocurre con 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 proporciona muchos procedimientos integrados para acceder y controlar listas. Las listas se pueden crear directamente con el listprocedimiento, que toma cualquier número 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 de contras , 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 cómo se construyen las listas.
( contras 1 ' ( 2 3 )) ;Salida: (1 2 3) ( contras ' ( 1 2 ) ' ( 3 4 ) ;Salida: ((1 2) 3 4) El appendprocedimiento añade dos (o más) listas entre sí. Debido a que las listas Lisp son listas enlazadas, agregar dos listas tiene una complejidad de tiempo asintótica
( añadir ' ( 1 2 ) ' ( 3 4 )) ; Salida: (1 2 3 4) ( append ' ( 1 2 3 ) ' () ' ( a ) ' ( 5 6 )) ; Salida: (1 2 3 a 5 6) 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 consecuentes. 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 fooy barson y respectivamente. Sin embargo, la cola tiene la misma estructura en ambas listas. No es una copia; las celdas de contras apuntan 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 copiar puede mejorar drásticamente 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. Modificar una lista, como reemplazarla ccon a 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 esta misma razón.(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 están marcados con un signo de exclamación de advertencia, o "bang", como set-car!(léase set car bang ), que reemplaza el auto de un cons. En el dialecto Common Lisp, las funciones destructivas son comunes; el equivalente de set-car!lleva el nombre rplacade "coche de repuesto". 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 optimización cuando sea seguro hacerlo.
Lisp evalúa las expresiones ingresadas por el usuario. Los símbolos y las listas se evalúan según alguna otra expresión (generalmente más simple); por ejemplo, un símbolo se evalúa según el valor de la variable que nombra; evalúa a . Sin embargo, la mayoría de las otras formas se evalúan a sí mismas: si ingresan a Lisp, devuelve .(+ 2 3)555
Cualquier expresión también se puede marcar para evitar que sea evaluada (como es necesario para los símbolos y las listas). Este es el papel del quoteoperador especial, o su abreviatura '(una comilla). Por ejemplo, normalmente si se ingresa el símbolo foo, devuelve el valor de la variable correspondiente (o un error, si no existe dicha variable). Para referirse al símbolo literal, ingrese o, generalmente, .(quote foo)'foo
Tanto Common Lisp como Scheme también admiten el operador de comillas invertidas (denominado cuasicomillas en Scheme), ingresado con el `carácter ( acento grave ). Esto 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 . Si la variable tiene el valor entonces se evalúa como , mientras que se evalúa como . Las comillas invertidas se utilizan con mayor frecuencia para definir expansiones macro. [68] [69],@ snue(bar baz)`(foo ,snue)(foo (bar baz))`(foo ,@snue)(foo bar baz)
Las formas autoevaluables y las formas entre comillas son el equivalente de Lisp a los literales. Es posible modificar los valores de los literales (mutables) en el código del programa. Por ejemplo, si una función devuelve un formulario entrecomillado 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 ser constante () ' ( uno dos tres )) ( let (( cosas ( debería ser constante ))) ( setf ( tercera cosa ) 'bizarro )) ; ¡malo! ( debería ser constante ) ; regresa (uno dos extraño) Modificar una forma citada como esta generalmente se considera un 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, colocarlas en una memoria protegida contra escritura, etc.).
La formalización de las citas por parte 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 autorreferencia .
La familia Lisp se divide sobre el uso del alcance dinámico o estático (también conocido como léxico) . Clojure, Common Lisp y Scheme utilizan el alcance estático de forma predeterminada, mientras que newLISP , Picolisp y los lenguajes integrados en Emacs y AutoCAD utilizan el alcance dinámico. Desde la versión 24.1, Emacs utiliza alcance tanto dinámico como 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 usaría Lisp. el sistema Lisp subyacente.
Lisp usa esto para implementar un sistema de macros muy poderoso. 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 Lisp y, por lo tanto, pueden explotar todo el poder de Lisp.
Además, debido a que el código Lisp tiene la misma estructura que las listas, se pueden crear macros 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 Lisp 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 los idiomas. Por ejemplo, el Common Lisp Object System se puede implementar limpiamente como una extensión de 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 otros idiomas; por ejemplo, Java no admite 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 parte de la estructura de una lista que el intérprete atraviesa 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-whenque permite que el código esté presente durante el tiempo de compilación (cuando una macro lo necesitaría), pero no en el módulo emitido. [70]
Los lenguajes Lisp se utilizan a menudo 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 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 comando Lisp se denomina bucle de lectura, evaluación e 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 citas y 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 cuando se le solicita, lo traduce en una lista vinculada 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.(+ 1 2)read+
A foose leerá como un símbolo único. 123se leerá como el número ciento veintitrés. "123"se leerá como la cadena "123".
La evalfunción evalúa los datos y, como resultado, devuelve cero o más datos Lisp. 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 auto 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. 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))
El trabajo de la printfunción es representar la salida al usuario. Un resultado simple como 3este es trivial. Una expresión que se evaluara como una parte de la estructura de la lista requeriría printrecorrer la lista e imprimirla como una expresión S.
Para implementar un Lisp REPL, sólo 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.) Hecho esto, un REPL básico es una línea de código: .(loop (print (eval (read))))
Lisp REPL normalmente también proporciona edición de entrada, un historial de entrada, manejo de errores y una interfaz para el depurador.
Lisp generalmente se evalúa con entusiasmo . En Common Lisp , los argumentos se evalúan en orden aplicativo ("el más interno a la izquierda"), 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.
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, condes el precursor de if-then-elseestructuras posteriores).
Los programadores en el dialecto Scheme a menudo expresan bucles usando recursividad de cola . Los puntos comunes de Scheme en la informática académica han llevado a algunos estudiantes a creer que la recursividad de 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 con frecuencia tienen construcciones de iteración de estilo imperativo, desde doel bucle de Scheme hasta las expresiones complejas de Common Lisploop . Además, la cuestión clave que hace que esto sea un asunto objetivo más que 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 generalmente se recomienda el uso de la recursividad de cola 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 llamada 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) sea desaconsejado [72] en Common Lisp no es sólo 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 la corrección del programa (ya que la recursión de cola puede aumentar el uso de la pila en Common Lisp, con riesgo de desbordamiento de la pila ).
Algunas estructuras de control Lisp son operadores especiales , equivalentes a las palabras clave sintácticas de otros idiomas. Las expresiones que utilizan estos operadores tienen la misma apariencia superficial que las llamadas a funciones, pero difieren en que los argumentos no necesariamente se evalúan 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 otros lenguajes de programación importantes, Lisp permite implementar estructuras de control utilizando el lenguaje. Varias estructuras de control se implementan como macros Lisp, e incluso el programador que quiera saber cómo funcionan pueden ampliarlas macro.
Tanto Common Lisp como Scheme tienen operadores para 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 utilizando el call/ccprocedimiento, que permite a un programa guardar (y luego restaurar) un lugar particular en ejecución. Common Lisp no admite continuaciones reentrantes, pero sí 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 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, la misma tarea se puede realizar 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 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, generando el resultado .(11 22 33 44 55)
A continuación se muestran ejemplos de código Common Lisp.
El programa básico "¡ Hola, mundo! ":
( imprime "¡Hola, mundo!" ) La sintaxis Lisp se presta naturalmente a la recursividad. Los problemas matemáticos como la enumeración de conjuntos definidos recursivamente son sencillos 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 )) ( if ( 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 de 1 a n para fac = 1 luego ( * fac i ) finalmente ( retorno fac ))) La siguiente función invierte una lista. (La función inversa incorporada de Lisp hace lo mismo).
( defun -reverse ( lista ) ( let (( valor-retorno )) ( dolist ( lista e ) ( push e valor-retorno )) valor-retorno )) Se han construido varios sistemas y modelos de objetos encima, al lado 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] incluido
Genera , renombrado Open Genera, [76] 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 ; [77] [78] Mezzano; [79] Provisional; [80] [81] ChrysaLisp, [82] por desarrolladores de TAOS de Tao Systems. [83]
Lisp es un sobreviviente, ya que ha estado en uso durante aproximadamente un cuarto de siglo.
Entre los lenguajes de programación activos sólo Fortran ha tenido una vida más larga.
El proyecto PDP-6 comenzó a principios de 1963, como una máquina de 24 bits.
Creció a 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... Se envió un artículo que definía expresiones condicionales y proponía su uso en Algol a Comunicaciones de la ACM. pero fue arbitrariamente degradado a carta al editor, porque era muy breve.
Entonces no entendía la monstruosa idea de LISP sobre el metalenguaje tangible, pero me acerqué un poco a las ideas sobre lenguajes extensibles... La segunda fase de esto fue comprender finalmente LISP y luego usar esta comprensión para hacerlo mucho más bonito, más pequeño y más. subestructuras poderosas y de vinculación más tardía... Para mí, la programación orientada a objetos significa solo mensajería, retención y protección local y ocultación del proceso estatal, y vinculación tardía extrema de todas las cosas.
Se puede hacer en Smalltalk y en LISP.
Posiblemente existan otros sistemas en los que esto sea posible, pero no los conozco.
Definiciones de Wikcionario
Medios de los comunes
Citas de Wikiquote
Textos de Wikisource
Libros de texto de Wikilibros
Recursos de Wikiversidad