Benutzer:Ferada/S-expression
Der Begriff S-Expression oder sexp (S(ymbolischer) Ausdruck) bezeichnet eine Konvention zur Darstellung semistrukturierter Daten durch menschenlesbaren Text.
Verwendung
S-Expressions sind vermutlich am besten durch ihre Nutzung in der Lispsprachfamilie (einschließlich Scheme) bekannt. Zum anderen werden sie in von Lisp abgeleiteten Sprachen wie DSSSL und als Auszeichnungssprache in Kommunikationsprotokollen wie IMAP oder John McCarthys CBCL verwendet. Die Details der Syntax und unterstützten Datentypen variiert in den verschiedenen Sprachen, aber am weitesten verbreitet ist die Nutzung von S-Expressions als geklammerte Präfixnotation (auch bekannt als polnische Notation).
S-Expressions werden in Lisp für Code wie für Daten verwendet (siehe McCarthy Recursive Functions of Symbolic Expressions[1]). S-Expressions waren ursprünglich zur Datenmanipulation durch M-Expressions gedacht, aber die erste Lispimplementation war ein Interpreter für S-Expressions die M-Expressions kodierten, sodass sich die Programmierer an die Nutzung von S-Expressions für Code und Daten gewöhnten. Eine vergleichbare Behandlung von Code und Daten ist unter anderem im JSON-Datenformat sichtbar, das im Grunde seine Daten ebenfalls durch Syntaxelemente der Sprache strukturiert.
Syntax
S-Expressions können entweder einzelne Objekte wie Zahlen, Lispatome inklusive der Spezialfälle nil (leere Liste, boolscher Wert falsch) und t (boolscher Wert wahr), oder Cons Paare, geschrieben als (x . y), sein. Längere Listen werden aus geschachtelten Cons-Paaren zusammengesetzt, zum Beispiel (1 . (2 . (3 . nil))), was kürzer als (1 2 3) geschrieben werden kann.
cons ist dabei eine Funktion, die ein 2-Tupel aus den übergebenen Werten erstellt. Die verschaltelten Tupel werden dann zur Konstruktion einer einfach verketteten Liste verwendet.
Eine übliche Syntaxerweiterung in Lispbasierten Sprachen ist die Schreibweise von
(quote (define x 1))
als
'(define x 1)
(quoten), was die Gleichbehandlung von Code- und Datenform unterstreicht.
Standardisierung
Im Mai 1997 veröffentlichte Ron Rivest einen Internet-Draft der zur Publikation als RFC berücksichtigt werden sollte[2]. Der Entwurf definiert eine Syntax auf Basis von Lisp S-Expressions zur Datenspeicherung und -austausch (vergleichbar mit XML), die ursprünglich zur Nutzung in Public Key Infrastructure vorgesehen war. Der Entwurf wurde niemals als RFC angenommen, wird aber seitdem zitiert und von anderen RFCs[3] und Publikationen[4] wird. Abgesehen davon ist das Format außerhalb von PKI nicht weit verbreitet.
Rivests Format definiert S-Expressions als Oktetstring (eine Serie von Bytes) oder endliche Liste anderer S-Expressions. Er beschreibt drei Austauschformate zur Beschreibung dieser Struktur:
- zum einen den "advanced transport", dessen Formatierung sehr flexibel und syntaktisch den von Lisp bekannten Ausdrücken ähnlicher ist. Das Format erlaubt zum Beispiel Oktetstrings entweder unformatiert, in gequoteter Form, hexadecimal oder Base64-kodiert einzubetten
Rivest's format defines an S-expression as being either an octet-string (a series of bytes) or a finite list of other S-expressions. It describes three interchange formats for expressing this structure. One is the "advanced transport", which is very flexible in terms of formatting, and is syntactically similar to Lisp-style expressions, but they are not identical. The advanced transport, for example, allows octet-strings to be represented verbatim (the string's length followed by a colon and the entire raw string), a quoted form allowing escape characters, hexadecimal, Base64, or placed directly as a "token" if it meets certain conditions. (Rivest's tokens differ from Lisp tokens in that the former are just for convenience and aesthetics, and treated exactly like other strings, while the latter have specific syntactical meaning.) Another interchange format, intended to be more compact, easier to parse, and unique for any abstract S-expression, is the "canonical representation" which only allows verbatim strings, and prohibits whitespace as formatting outside strings. Finally there is the "basic transport representation", which is either the canonical form or the same encoded as Base64 and surrounded by braces, the latter intended to safely transport a canonically-encoded S-expression in a system which might change spacing (e.g. an email system which has 80-character-wide lines and wraps anything longer than that).
Implementierungen
Aufgrund der Ähnlichkeit mit XML gibt es eine Reihe von Bibliotheken für Lisp, die die Integration in die Sprache einfacher machen. Formate wie SXML definieren außerdem eigene Standards, nach denen XML-Dokumente und auf S-Expressions basierende Formate ineinander konvertiert werden können.
Ein typisches Beispiel generiert eine XHTML-Seite (benutzt CL-WHO[5] von Edi Weitz):
(with-html-output (*standard-output*)
(princ "<?xml version='1.0' encoding='utf-8'?>")
(princ "<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.1//EN\" \"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd\">")
(:html :xmlns "http://www.w3.org/1999/xhtml"
(:head (:title "Hallo, Welt!"))
(:body
(:h1 "Eine große Überschrift")
(:p :id "test"
"Hallo, Welt!"))))
Literatur
Weblinks
- Matthew Sottiles sexpr-Bibliothek
- Ron Rivests Webseite enthält Quelltext
- Das Common Lisp Wiki hat eine Liste von XML-Bibliotheken auf S-Expressionbasis.
