S-expresión

Estructura de datos del árbol que representa la expresión S (* 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 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 como

1. un átomo de la forma x, o
2. una expresión de la forma (x. y) Donde x y Sí. Son S-expresiones.

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 las 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 de expresión S clásica. a menos que se proporcione una convención para la referencia cruzada (análoga a las claves externas de SQL, IDREF de XML, etc.). Los dialectos modernos de Lisp como Common Lisp y Scheme proporcionan dicha sintaxis a través de etiquetas de datos, con las que se pueden marcar los objetos, que luego pueden repetirse en otro lugar, lo que indica una estructura compartida en lugar de la duplicación de objetos, lo que permite al lector o impresor detectar y, por lo tanto, activar la evaluación o visualización de ciclos sin repetición infinita

#n=(x y. #n#)

La definición de un átomo varía según el contexto; en la definición original de John McCarthy, se suponía que existía "un conjunto infinito de símbolos atómicos distinguibles" representado como "cadenas de letras latinas mayúsculas y dígitos con espacios en blanco individuales incrustados" (un subconjunto de cadenas de caracteres y literales numéricos).

La mayoría de las notaciones modernas de sexpr permiten cadenas entre comillas más generales (por ejemplo, incluir puntuación o Unicode completo) y usan una notación abreviada para representar listas con más de 2 miembros, de modo que

(x y z)

significa

(x. (y. (z. NIL)))

NIL es el objeto especial de fin de lista (escrito alternativamente (), que es la única representación en Scheme).

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 usa 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 prefijos.

Tipos de datos y sintaxis

Hay muchas variantes del formato de expresión S, que admiten una variedad de sintaxis diferentes para diferentes tipos de datos. Los más admitidos son:

• Listas y pares: (1 () (2. 3) (4))
• Símbolos: with-hyphen ?@!$ a symbol with spaces
• Pendientes: "Hello, world!"
• Integers: -9876543210
• Números de punto flotante: -0.0 6.28318 6.022e23

El carácter # se usa a menudo para prefijar extensiones a la sintaxis, p. #x10 para enteros hexadecimales o #C para caracteres.

Usar en Lisp

Al representar el código fuente en Lisp, el primer elemento de una expresión S suele ser un operador o un 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 < code>(= 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 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 cualquiera de los casos, un carácter prohibido normalmente se puede incluir escapando de él con una barra invertida precedente. La compatibilidad con Unicode varía.

El caso recursivo de la definición s-expr se implementa tradicionalmente usando celdas cons.

Las expresiones S originalmente estaban pensadas solo para que las expresiones M manipularan los datos, pero la primera implementación de Lisp fue un intérprete de las codificaciones de expresiones S de expresiones M, y los programadores de Lisp pronto se acostumbraron a usar expresiones S. tanto para el código como para los 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.

Ejemplos de expresiones S de datos

Las listas anidadas se pueden escribir como expresiones S: ((jugo de leche) (mermelada de miel)) 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 este artículo) es típica. Los saltos de línea (caracteres de nueva línea) generalmente califican como separadores.

Esta es una gramática simple sin contexto para un pequeño subconjunto del inglés escrito como una expresión S (Gazdar/Melish, procesamiento de 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) muerto) ()V) empleados) ()NP) enfermeras) ()NP) pacientes) ()NP) Medicamentos) ()NP) "Dr Chan")

Ejemplo de expresiones S del código fuente

El código del programa se puede escribir en expresiones S, generalmente usando notación de prefijo.

Ejemplo en Common Lisp:

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

Las expresiones S se pueden leer en Lisp usando la función LEER. 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. 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 usando la función PPRINT (nota: con dos P, abreviatura de bonito-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 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 comillas simples, como en 'x, es azúcar sintáctica para una expresión S entre comillas, en este caso (quote x)< /código>.

Análisis

Las expresiones S a menudo se comparan con XML: la diferencia clave es que las expresiones S tienen solo una forma de contención, el par punteado, mientras que las etiquetas XML pueden contener atributos simples, otras etiquetas o CDATA, cada uno con una sintaxis diferente. 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.

Estandarización

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) e ISLISP.

Variante de Rivest

En mayo de 1997, Ron Rivest envió un borrador de Internet para que se considerara su publicación como RFC. El borrador definió una sintaxis basada en expresiones S de Lisp, pero pensada para el almacenamiento e intercambio de datos de propósito general (similar a XML) en lugar de específicamente para 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. Originalmente fue diseñado 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 la cadena sin procesar completa), una forma entrecomillada que permite caracteres de escape, hexadecimal, Base64 o se coloca directamente como un "ficha" si cumple ciertas condiciones. (Los tokens de Rivest difieren 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". Está diseñado para 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 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 destinada a transportar de manera segura una expresión S codificada canónicamente en un sistema que podría cambiar 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 de expresiones S de Rivest proporciona código fuente C para un analizador y un generador (disponible bajo la licencia MIT), que podría adaptarse e integrarse en otros programas. Además, no hay restricciones para implementar el formato de forma independiente.