Expresión S

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.

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.

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

El código fuente de los programas puede ser escrito como expresiones-S, normalmente 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.

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.

• Expresión-M
• CAR y CDR
• cons
• Expresiones S canónicas
• XML

Implementaciones en software libre:

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