(* 2 (+ 3 4)) En programación informática , una expresión S (o expresión simbólica , abreviada como sexpr o sexp ) es una expresión en una notación del mismo nombre para datos de lista anidada ( estructurados en árbol ). Las expresiones S fueron inventadas y popularizadas por el lenguaje de programación Lisp , que las usa tanto para código fuente como para datos.
En la sintaxis entre paréntesis habitual de Lisp, una S-expresión se define clásicamente [1] como
x, o(x . y)Esta definición refleja la representación de LISP de una lista como una serie de "celdas", cada una de ellas un par ordenado . En listas simples, y apunta a la siguiente celda (si la hay), formando así una lista . La cláusula recursiva de la definición significa que tanto esta representación como la notación de expresión S pueden representar cualquier árbol binario . Sin embargo, la representación puede, en principio, permitir referencias circulares, en cuyo caso la estructura no es un árbol en absoluto, sino un gráfico cíclico , y no se puede representar en la notación clásica de expresión S a menos que se proporcione una convención para referencia cruzada (análoga a las claves externas de SQL , IDREF de SGML / XML , etc.). Los dialectos modernos de Lisp como Common Lisp [2] y Scheme [3] proporcionan dicha sintaxis a través de etiquetas de datos , con las que se pueden marcar objetos, que luego pueden recurrir en otro lugar, lo que indica una estructura compartida en lugar de duplicada, lo que permite al lector o la impresora detectar y, por lo tanto, activar la evaluación o visualización de ciclos sin recurrir infinitamente.
#n=(x y . #n#)La definición de un átomo varía según el contexto; en la definición original de John McCarthy , [1] se asumió que existía "un conjunto infinito de símbolos atómicos distinguibles " representados como "cadenas de letras latinas mayúsculas y dígitos con espacios en blanco incrustados" (un subconjunto de cadenas de caracteres y literales numéricos ).
La mayoría de las notaciones sexpr modernas permiten cadenas entre comillas más generales (por ejemplo, incluyendo puntuación o Unicode completo ) y utilizan una notación abreviada para representar listas con más de 2 miembros, de modo que
(x y z)significa
(x . (y . (z . NIL)))NILes el objeto especial de final de lista (escrito alternativamente (), que es la única representación en Scheme [4] ).
En la familia de lenguajes de programación Lisp, las expresiones S se utilizan para representar tanto el código fuente como los datos. Otros usos de las expresiones S se encuentran en lenguajes derivados de Lisp, como DSSSL , y como marcado en protocolos de comunicación como IMAP y CBCL de John McCarthy . También se utilizan como representación de texto de WebAssembly . Los detalles de la sintaxis y los tipos de datos admitidos varían en los diferentes lenguajes, pero la característica más común entre estos lenguajes es el uso de expresiones S y la notación de prefijo.
Existen muchas variantes del formato de expresión S, que admiten una variedad de sintaxis diferentes para distintos tipos de datos. Las más admitidas son:
(1 () (2 . 3) (4))with-hyphen ?@!$ |a symbol with spaces|"Hello, world!"-9876543210-0.0 6.28318 6.022e23El carácter #se utiliza a menudo para prefijar extensiones a la sintaxis, por ejemplo, #x10para números enteros hexadecimales o #\Cpara caracteres.
Al representar código fuente en Lisp, el primer elemento de una expresión S es comúnmente un operador o nombre de función y los elementos restantes se tratan como argumentos. Esto se denomina "notación de prefijo" o " notación polaca ". Como ejemplo, la expresión booleana escrita 4 == (2 + 2)en C se representa como (= 4 (+ 2 2))en la notación de prefijo basada en s-expr de Lisp.
Como se indicó anteriormente, la definición precisa de "átomo" varía entre lenguajes similares a LISP. Una cadena entre comillas puede contener cualquier cosa excepto comillas, mientras que un identificador sin comillas, átomo, puede contener cualquier cosa excepto comillas, espacios en blanco, paréntesis, corchetes, llaves, barras invertidas y punto y coma. En cualquier caso, un carácter prohibido puede incluirse normalmente escapándolo con una barra invertida precedente. La compatibilidad con Unicode varía.
El caso recursivo de la definición de s-expr se implementa tradicionalmente utilizando cons cells .
Las expresiones S fueron pensadas originalmente solo para que los datos fueran manipulados por expresiones M , pero la primera implementación de Lisp fue un intérprete de codificaciones de expresiones S de expresiones M, y los programadores de Lisp pronto se acostumbraron a usar expresiones S tanto para código como para datos. Esto significa que Lisp es homoicónico ; es decir, la representación primaria de los programas es también una estructura de datos en un tipo primitivo del propio lenguaje.
Las listas anidadas se pueden escribir como expresiones S: ((milk juice) (honey marmalade))es una expresión S de dos elementos cuyos elementos también son expresiones S de dos elementos. La notación separada por espacios en blanco que se utiliza en Lisp (y en este artículo) es típica. Los saltos de línea (caracteres de nueva línea) suelen considerarse separadores. Esta es una gramática simple e independiente del contexto para un pequeño subconjunto del inglés escrito como una expresión S (Gazdar/Melish, Procesamiento del lenguaje natural en Lisp), donde S=oración, SN=sintagma nominal, VP=sintagma verbal, V=verbo:
((( S ) ( NP VP )) (( VP ) ( V )) (( VP ) ( V NP )) (( V ) murió ) (( V ) empleado ) (( NP ) enfermeras ) (( NP ) pacientes ) (( NP ) Medicenter ) (( NP ) "Dr Chan" )) El código del programa se puede escribir en expresiones S, generalmente utilizando notación de prefijo. Ejemplo en Common Lisp :
( defun factorial ( x ) ( si ( zerop x ) 1 ( * x ( factorial ( - x 1 ))))) Las expresiones S se pueden leer en Lisp utilizando la función READ. READ lee la representación textual de una expresión S y devuelve datos Lisp. La función PRINT se puede utilizar para generar una expresión S. La salida se puede leer con la función READ, cuando todos los objetos de datos impresos tienen una representación legible. Lisp tiene representaciones legibles para números, cadenas, símbolos, listas y muchos otros tipos de datos. El código del programa se puede formatear como expresiones S impresas de forma bonita utilizando la función PPRINT (nota: con dos P, abreviatura de pretty -print).
Los programas Lisp son expresiones S válidas, pero no todas las expresiones S son programas Lisp válidos. (1.0 + 3.1)es una expresión S válida, pero no un programa Lisp válido, ya que Lisp utiliza notación de prefijo y un número de punto flotante (aquí 1.0) no es válido como operación (el primer elemento de la expresión).
Una expresión S precedida por una comilla simple, como en 'x, es un azúcar sintáctico para una expresión S entre comillas , en este caso (quote x).
Las expresiones S se comparan a menudo con XML : una diferencia clave es que las expresiones S tienen solo una forma de contención, el par de puntos, mientras que las etiquetas XML pueden contener atributos simples, otras etiquetas o CDATA , cada una con una sintaxis diferente. Otra diferencia es que las expresiones S no definen un mecanismo de referencia, mientras que XML proporciona una noción de identificadores únicos y referencias a ellos. Para casos de uso simples, las expresiones S son más simples que XML, pero para casos de uso más avanzados, XML tiene un lenguaje de consulta llamado XPath , muchas herramientas y bibliotecas de terceros para simplificar el manejo de datos XML.
Los estándares para algunos lenguajes de programación derivados de Lisp incluyen una especificación para su sintaxis de expresiones S. Entre ellos se encuentran Common Lisp (documento estándar ANSI INCITS 226-1994 (R2004)), Scheme (R5RS y R6RS [5] ) e ISLISP .
En mayo de 1997, Ron Rivest presentó un borrador de Internet [6] para que se considerara su publicación como RFC . El borrador definía una sintaxis basada en expresiones S de Lisp pero destinada al almacenamiento e intercambio de datos de propósito general (similar a XML ) en lugar de específicamente para programación. Nunca fue aprobado como RFC, pero desde entonces ha sido citado y utilizado por otros RFC (por ejemplo, RFC 2693) y varias otras publicaciones. [7] Originalmente estaba destinado a usarse en SPKI .
El formato de Rivest define una expresión S como una cadena de octetos (una serie de bytes ) o una lista finita de otras expresiones S. Describe tres formatos de intercambio para expresar esta estructura. Uno es el "transporte avanzado", que es muy flexible en términos de formato y es sintácticamente similar a las expresiones de estilo Lisp, pero no son idénticas. El transporte avanzado, por ejemplo, permite que las cadenas de octetos se representen textualmente (la longitud de la cadena seguida de dos puntos y la cadena completa), una forma entre comillas que permite caracteres de escape, hexadecimal , Base64 o se colocan directamente como un "token" si cumple ciertas condiciones. (Los tokens de Rivest se diferencian de los tokens de Lisp en que los primeros son solo por conveniencia y estética, y se tratan exactamente como otras cadenas, mientras que los últimos tienen un significado sintáctico específico).
El borrador de Rivest define una representación canónica "para fines de firma digital". Se pretende que sea compacta, más fácil de analizar y única para cualquier expresión S abstracta. Solo permite cadenas textuales y prohíbe los espacios en blanco como formato fuera de las cadenas. Finalmente, está la "representación de transporte básica", que es la forma canónica o la misma codificada que Base64 y rodeada de llaves ; esta última tiene como objetivo transportar de forma segura una expresión S codificada canónicamente en un sistema que podría cambiar el espaciado (por ejemplo, un sistema de correo electrónico que tiene líneas de 80 caracteres de ancho y envuelve cualquier cosa más larga que eso).
Este formato no ha sido ampliamente adaptado para su uso fuera de SPKI (algunos de los usuarios son GnuPG , libgcrypt, Nettle y GNU lsh). La página web S-expressions de Rivest proporciona el código fuente en C para un analizador y generador (disponible bajo la licencia MIT ), que podría adaptarse e integrarse en otros programas. [8] Además, no existen restricciones para implementar el formato de forma independiente.