De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Estructura de datos de árbol que representa la expresión S(* 2 (+ 3 4))

En programación informática , las expresiones S (o expresiones simbólicas , abreviadas como sexprs ) son una notación para datos de listas anidadas ( estructuradas en árbol ), 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 [1] como

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

La segunda parte recursiva de la definición representa un par ordenado , lo que significa que las expresiones S pueden representar cualquier árbol binario , aunque las expresiones S que contienen ciclos no pueden representarse a la inversa como árboles binarios.

La definición de á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 individuales" (es decir, cadenas de caracteres y literales numéricos ) . La mayoría de las notaciones sexpr modernas utilizan además una notación abreviada para representar listas en expresiones S, de modo que

(x y z)

representa

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

donde NILes la especial de final de lista de objeto (alternativamente escrito (), que es la única representación en el Esquema [2] ).

En la familia Lisp de lenguajes de programación, las expresiones S se utilizan para representar tanto el código fuente como los datos. Otros usos de S-expresiones están en idiomas derivados de Lisp como DSSSL , y como margen de utilidad en protocolos de comunicación como IMAP y John McCarthy 's CBCL . 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.

Tipos de datos y sintaxis [ editar ]

Hay 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:

  • Listas y pares :(1 () (2 . 3) (4))
  • Simbolos :with-hyphen ?@!$ a\ symbol\ with\ spaces
  • Cuerdas :"Hello, world!"
  • Enteros :-9876543210
  • Números de coma flotante :-0.0 6.28318 6.022e23

El carácter #se utiliza a menudo para prefijar extensiones a la sintaxis, por ejemplo, #x10para enteros hexadecimales o #\Cpara caracteres.

Usar en Lisp [ editar ]

Cuando se representa el código fuente en Lisp, el primer elemento de una expresión-S es comúnmente un operador o nombre de función y cualquier elemento restante se trata 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 en los lenguajes similares a LISP. Una cadena entre comillas normalmente puede contener cualquier cosa menos una cita, 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 anterior. La compatibilidad con Unicode varía.

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

Las expresiones-S estaban 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 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.

Ejemplos de expresiones S de datos [ editar ]

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 este artículo) es típica. Los saltos de línea (caracteres de nueva línea) generalmente se califican como separadores.

Esta es una gramática simple sin 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 sustantiva, VP = Frase verbal, V = Verbo :

((( S )  ( NP  VP ))  (( VP )  ( V ))  (( VP )  ( V  NP ))  (( V )  falleció )  (( V )  empleado )  (( NP )  enfermeras )  (( NP )  pacientes )  (( NP )  Medicenter )  (( NP )  "Dr. Chan" ))

Ejemplo de expresiones S de código fuente [ editar ]

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  ( 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 PRINT se puede utilizar para generar una expresión S. A continuación, 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 de programa puede formatearse como expresiones S bastante impresas utilizando la función PPRINT (nota: con dos Ps, 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 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).

Analizando [ editar ]

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 de puntos, y son mucho más fáciles de analizar, mientras que las etiquetas XML pueden contener atributos simples, otras etiquetas o CDATA , cada una utilizando una sintaxis diferente.

Estandarización [ editar ]

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

Variante de Rivest [ editar ]

Ver también: Expresiones S canónicas

En mayo de 1997, Ron Rivest envió un Borrador de Internet [4] para que se considerara su publicación como RFC . El borrador definía una sintaxis basada en expresiones Lisp S pero pensada para el almacenamiento e intercambio de datos de uso 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. [5] 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 literalmente (la longitud de la cadena seguida de dos puntos y toda la cadena sin formato), una forma entre comillas que permite caracteres de escape, hexadecimal , Base64, o se coloca directamente como un "token" si cumple con ciertas condiciones. (Los tokens de Rivest se diferencian de los 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 "con fines de firma digital". Está diseñado para ser compacto, más fácil de analizar y exclusivo para cualquier expresión S abstracta. Solo permite cadenas textuales y prohíbe los espacios en blanco como formato de cadenas externas. Por último, 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 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 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 generador (disponible bajo la licencia MIT ), que podría adaptarse e integrarse en otros programas. [6] Además, no existen restricciones sobre la implementación independiente del formato.

Ver también [ editar ]

  • contras
  • COCHE y CDR
  • Fexpr
  • Cálculo lambda
  • Expresión M
  • Expresiones S canónicas
  • Comparación de formatos de serialización de datos

Referencias [ editar ]

  1. ↑ a b John McCarthy (1960/2006). Funciones recursivas de expresiones simbólicas Archivado el 2 de febrero de 2004 en la Wayback Machine . Publicado originalmente en Comunicaciones de la ACM .
  2. ^ "Informe revisado ^ 5 sobre el esquema de lenguaje algorítmico" . schemers.org .
  3. ^ Sperber, Michael; Dybvig, R. Kent; Flatt, Matthew; Van Straaten, Anton; Findler, Robby; Matthews, Jacob (12 de agosto de 2009). "Informe revisado6 sobre el esquema de lenguaje algorítmico". Revista de programación funcional . 19 (S1): 1–301. CiteSeerX 10.1.1.372.373 . doi : 10.1017 / S0956796809990074 . 
  4. ^ Expresiones-S , Grupo de trabajo en red, Borrador de Internet, Vence el 4 de noviembre de 1997 - R. Rivest, 4 de mayo de 1997 draft-rivest-sexp-00.txt, Ronald L. Rivest, sitio web de CSAIL MIT
  5. ^ rivest sexp , Google Scholar (búsqueda)
  6. ^ "SEXP (expresiones-S)" . people.csail.mit.edu .

Enlaces externos [ editar ]

  • sfsexp la pequeña y rápida biblioteca de expresiones S para C / C ++ en Github
  • minilisp , de Léon Bottou.
  • Las expresiones S en Rosettacode tienen implementaciones de lectores y escritores en muchos idiomas.