Expresión S

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Representación en forma de árbol de la s-expression (* 2 (+ 3 4)), que también es equivalente a la expresión en notación de infijo 2*(3+4)

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 expresiones-S son, probablemente, conocidas por su uso en la familia Lisp de lenguajes de programación. Su representación textual habitual son secuencias delimitadas por paréntesis de cadenas de caracteres, separadas por espacios, como en (= 4 (+ 2 2)), que representa la expresión lógica escrita como 4==2+2 en el lenguaje de programación C y en otros lenguajes relacionados.

En Lisp, el primer elemento de cada expresión S es un operador y el resto de elementos son tratados como datos. Esta forma se denomina notación prefija notación Polaca Cambridge. Debido a la estrecha relación entre las expresiones-S y su representación textual, el término expresión-S es usado en informalmente para referirse también a su escritura.

Otros usos de las expresiones-S en los lenguajes de prograació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 sintáxis y los tipos de datos soportados varían entre los diferentes lenguajes.

Actualmente, en Lisp, las expresiones-S son usadas tanto para alacenar el código fuente y los datos (ver McCarthy Recursive Functions of Symbolic Expressions). 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[editar]

Las expresiones-S se definen, recursivamente, como un tipo de dato simple llamado "átomo", o una lista de expresiones-S. Los átomos suelen incluir números, arreglos, cadenas de caracteres y símbolos.

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. 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. Normalmente, sin embargo, se utiliza 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, que son a su vez expresiones-S.

Ejemplo[editar]

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[editar]

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 muchos otros tipos de datos, esto singifica 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. (1.0 + 3.1), por ejemplo, no es programa Lisp válido, ya que Lisp usa una notación prefija y el número en coma flotante 1.0 no es una operación válida.

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

Estandarización[editar]

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 sólo 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[editar]

  1. [1] Sperber, Dybvig, Flatt, Van Straaten, Findler, Matthews, "Revised6 Report on the Algorithmic Language Scheme
  2. 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
  3. rivest sexp, Google Scholar (search)

Véase también[editar]

Enlaces externos[editar]

Implementaciones en software libre:

  • sfsexp the small, fast s-expression library on Sourceforge
  • minilisp, by Léon Bottou.