Expresión S
Una expresión-S, S-expresión o sexp (de Expresión Simbólica) es una notación en forma de texto, para representar una estructura de datos de árbol, basada en listas anidadas, en donde cada sublista es un subárbol. Las S-expresiones son, probablemente, mejor conocidas por su uso en la familia de lenguajes de programación Lisp. Su representación textual habitual son secuencias de cadenas de caracteres, delimitadas por paréntesis, y separadas por espacios, como en (= 4 (+ 2 2)), que representa la expresión lógica escrita en C y en otros lenguajes relacionados, 4==2+2.
(* 2 (+ 3 4)), que también es equivalente a la expresión en notación de infijo 2*(3+4)En notación polaca o prefija (la cual Lisp usa), el primer elemento de una S-expresión es un operador (un primitivo) y el resto de elementos, los operandos (los datos). Debido a la estrecha relación entre las expresiones-S y su representación textual, el término es usado informalmente también para referirse a su escritura.
Otros usos de las expresiones-S en los lenguajes de programación derivados de Lisp, como DSSSL, y como base para protocolos como IMAP y el CBCL de John McCarthy. Sin embargo, los detalles de la sintaxis y los tipos de datos soportados varían entre los diferentes lenguajes.
Actualmente, en Lisp, las expresiones-S son usadas tanto para almacenar el código fuente y los datos (ver ). Sin embargo originalmente sólo fueron concebidas para datos que serían manipulados por expresiones-M, pero la primera implementación de Lisp fue un intérprete de una codificación de expresiones-M usando expresiones-S, y los programadores Lisp pronto prefirieron usar expresiones-S tanto para el código como para los datos.
Definición
Las expresiones-S se definen, recursivamente como:
- un tipo de dato simple, al cual se le llama "átomo" (números, listas, cadenas de caracteres y símbolos).
- una lista de expresiones-S. Una expresión-S podría ser una lista de expresiones-S, que a su vez podrían ser listas, y así se pueden obtener expresiones anidadas con un nivel de profundidad arbitrario.
Listas.
En Lisp, estas listas se construyen a partir de un tipo de dato más básico llamado cons pair, escrito como (x . y). El primer elemento del cons es el primer elemento de la lista, y el segundo elemento es el resto de la lista; las listas, por tanto, se forman anidando cons, por ejemplo: (1 . (2 . (3 . nil))). El símbolo especial nil marca el final de una lista. Sin embargo, normalmente se usa la notación (1 2 3), por ser más compacta. Las listas anidadas también se pueden escribir como expresiones-S:
((leche zumo) (miel mermelada))
Es una lista de dos elementos; cada elemento de la lista también es, una expresión-S.
Ejemplo de Lista
Esto es una gramática simple, escrita como una expresión-S (Gazdar/Melish, Natural Language Processing in Lisp):
(((S) (NP) (VP)) ((VP) (V)) ((VP) (V) (NP)) ((V) died) ((V) employed) ((NP) nurses) ((NP) patients) ((NP) Medicenter) ((NP) Dr Chan)) Expresiones-S en Lisp
El código fuente de los programas puede ser escrito como expresiones-S, normalente usando notación prefija. Como en el siguiente ejemplo en Common Lisp:
(defun factorial (x) (if (zerop x) 1 (* x (factorial (- x 1))))) Las expresiones-S pueden ser leídas en Lisp usando la función READ. Esta función lee la representación textual de una expresión-S y devuelve como dato Lisp.
La función PRINT puede ser usada para escribir la representación textual de los datos a expresiones-S. Lisp tiene una representación leible para números, cadenas, símbolos, listas y otros tipos de datos; esto significa que estructuras de datos formadas por estos tipos y escritas con PRINT, pueden ser leídas de nuevo con READ. El código fuente de los programas puede ser formateado más elegantemente usando la función PPRINT.
Los programas Lisp son expresiones-S válidas, pero no toda expresión-S válida es un programa Lisp; por ejemplo:
(1.0 + 3.1)
no es programa Lisp válido, porque no usa notación prefija.
Una expresión-S precedida por una comilla simple, como en 'x, es un azúcar sintáctico para una expresión-S citada, en este caso, (quote x); a estos se les conoce como símbolos.
Estandarización
Los estándares para algunos lenguajes de programación derivados del Lisp incluyen una especificación para su sintaxis expresión S. Estos incluyen el Common Lisp (ANSI standard document ANSI INCITS 226-1994 (R2004)), Scheme (R5RS y R6RS[1]) y el ISLISP.
En mayo de 1997, Ron Rivest presentó un borrador de Internet[2] para ser considerado para su publicación como un RFC. El borrador define una sintaxis basada en expresiones S del Lisp pero diseñado para almacenamiento e intercambio de datos de propósito general (similar a XML), en vez de específicamente para la programación. Nunca fue aprobado como un RFC, pero desde entonces ha sido citado y usado por otros RFCs (ej. RFC 2693) y varias otras publicaciones.[3] Originalmente fue pensado para uso en SPKI.
El formato de Rivest define una S-expresión como una cadena de octetos (una serie de bytes) o una lista finita de otras S-expresiones. Describe tres formatos de intercambio para expresar esta estructura. Uno es el "transporte avanzado", que es muy flexible en cuanto a formato y es sintácticamente similar a las expresiones al estilo Lisp, pero no son idénticos. El transporte avanzado, por ejemplo, permite a las cadenas de octetos ser representadas textualmente (con la longitud de la cadena seguida de dos puntos y luego la cadena), una forma con comillas permitiendo caracteres de escape, hexadecimales, Base64, o directamente como un "token" si cumple con ciertas condiciones. (Los tokens de Rivest se diferencian de los tokens de Lisp porque los primeros son solo por conveniencia y estética y tratados exactamente igual que otras cadenas, mientras que los últimos tienen significado sintáctico específico). Otro formato de intercambio, pensado para ser más compacto, más fácil de analizar y único para cualquier S-expresión abstracta, es la "representación canónica" que sólo permite cadenas literales y prohíbe el espacio en blanco como formateo de cadenas exteriores. Finalmente, existe la "representación de transporte básico", que es la forma canónica o el mismo codificado como Base64 y rodeado de llaves, este último destinado a transportar de manera segura una expresión S canónicamente codificada en un sistema que podría cambiar el espaciado (ej. un sistema de correo electrónico que tiene líneas de 80 caracteres de ancho y continúa en la línea siguiente con cualquier cosa más larga que eso).
Este formato no ha sido ampliamente adaptado para su uso fuera del SPKI. La página web de la S-expresiones de Rivest proporciona el código fuente de C para un parser y generador (disponible bajo la licencia MIT, que podía ser adaptado y empotrado en otros programas. Además, no existen restricciones sobre implementar independientemente el formato.
Referencias
- [1] Sperber, Dybvig, Flatt, Van Straaten, Findler, Matthews, "Revised6 Report on the Algorithmic Language Scheme
- S-Expressions, Network Working Group, Internet Draft, Expires November 4, 1997 - R. Rivest, May 4, 1997 draft-rivest-sexp-00.txt, Ronald L. Rivest, CSAIL MIT website
- rivest sexp, Google Scholar (search)
Véase también
Enlaces externos
Implementaciones en software libre:
- sfsexp the small, fast s-expression library on Sourceforge
- minilisp, by Léon Bottou.