(* 2 (+ 3 4))En programación de computadoras , 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 listas anidadas ( estructuradas en árbol ). Las expresiones S fueron inventadas y popularizadas por el lenguaje de programación Lisp , que las utiliza tanto para el código fuente como para los datos.
En la sintaxis habitual entre paréntesis de Lisp, una expresión S 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 las cuales es 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 puede representarse en la notación clásica de expresión S a menos que se proporcione una convención para las referencias cruzadas (análoga a Claves foráneas de SQL , IDREF SGML / XML , etc.). Los dialectos Lisp modernos, como Common Lisp [2] y Scheme [3], proporcionan dicha sintaxis a través de etiquetas de referencia , con las cuales se pueden marcar objetos, que luego pueden repetirse en otros lugares, indicando una estructura compartida en lugar de duplicada, lo que permite al lector o impresor detectar y De este modo se activa la evaluación o visualización de ciclos sin recurrencia infinita.
#n=(x y . #n#)La definición de átomo varía según el contexto; en la definición original de John McCarthy , [1] se suponía 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 entrecomilladas 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)representa
(x . (y . (z . NIL)))NILes el objeto especial de fin de lista (escrito alternativamente (), que es la única representación en el esquema [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 utiliza como representación de texto de WebAssembly . Los detalles de la sintaxis y los tipos de datos admitidos varían en los diferentes idiomas, pero la característica más común entre estos idiomas es el uso de expresiones S y notación de prefijo.
Existen muchas variantes del formato de expresión S, que admiten una variedad de sintaxis diferentes para diferentes tipos de datos. Los más apoyados 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 anteponer extensiones a la sintaxis, por ejemplo, #x10para enteros hexadecimales o #\Cpara caracteres.
Al representar el código fuente en Lisp, el primer elemento de una expresión S suele ser un operador o nombre de función y los elementos restantes se tratan como argumentos. Esto se llama "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 señaló anteriormente, la definición precisa de "átomo" varía según los lenguajes tipo LISP. Una cadena entrecomillada normalmente puede contener cualquier cosa menos una comilla, mientras que un átomo identificador sin comillas normalmente puede contener cualquier cosa menos comillas, espacios en blanco, paréntesis, corchetes, llaves, barras invertidas y punto y coma. En cualquier caso, normalmente se puede incluir un carácter prohibido escapándolo con una barra invertida precedente. La compatibilidad con Unicode varía.
El caso recursivo de la definición s-expr se implementa tradicionalmente utilizando celdas contras .
Las expresiones S originalmente estaban destinadas solo a que los datos fueran manipulados por expresiones M , pero la primera implementación de Lisp fue un intérprete de codificaciones de expresiones M de expresiones S, y los programadores de Lisp pronto se acostumbraron a usar expresiones S para ambos códigos. y datos. Esto significa que Lisp es homoicónico ; es decir, la representación principal 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 utilizada en Lisp (y en este artículo) es típica. Los saltos de línea (caracteres de nueva línea) normalmente se consideran separadores. Esta es una gramática simple y libre de contexto para un pequeño subconjunto de inglés escrito como una expresión S (Gazdar/Melish, Procesamiento del lenguaje natural en Lisp), donde S=oración, NP=Frase nominal, VP=Frase 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, normalmente utilizando notación de prefijo. Ejemplo en Common Lisp :
( defun factorial ( x ) ( if ( zerop x ) 1 ( * x ( factorial ( - x 1 ))))) Las expresiones S se pueden leer en Lisp usando la función READ. READ lee la representación textual de una expresión S y devuelve datos Lisp. La función IMPRIMIR se puede utilizar para generar una expresión S. Luego, la salida se puede leer con la función LEER, 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 bonitas impresas usando la función PPRINT (nota: con dos P, abreviatura de bonita -impresión).
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 usa 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 azúcar sintáctico para una expresión S entre comillas , en este caso (quote x).
Las expresiones S a menudo se comparan 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 uno de los cuales usa una sintaxis diferente. Otra es que las expresiones S no definen un mecanismo de referencia, donde 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 expresión S. Estos incluyen Common Lisp (documento estándar ANSI 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 ser considerado para su publicación como RFC . El borrador definió 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 a la 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 pensado para su uso 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 palabra por palabra (la longitud de la cadena seguida de dos puntos y toda la cadena sin formato), una forma entrecomillada que permita caracteres de escape, hexadecimal , Base64 , o colocarse 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 segundos tienen un significado sintáctico específico).
El borrador de Rivest define una representación canónica "a efectos de firma digital". Su objetivo es ser compacto, más fácil de analizar y único para cualquier expresión S abstracta. Solo permite cadenas textuales y prohíbe los espacios en blanco como formato de cadenas externas. Finalmente está la "representación de transporte básica", que es la forma canónica o está codificada igual que Base64 y rodeada de llaves , esta última destinada a transportar de forma segura una expresión S codificada canónicamente en un sistema que podría cambiar el espaciado (por ejemplo, un correo electrónico sistema que tiene líneas de 80 caracteres de ancho y envuelve cualquier cosa más larga que eso).
Este formato no se ha adaptado ampliamente 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 código fuente C para un analizador y generador (disponible bajo licencia MIT ), que podría adaptarse e integrarse en otros programas. [8] Además, no existen restricciones para implementar el formato de forma independiente.