S-выражения: Формат сериализации данных

Введение

Формат сериализации данных

В компьютерном программировании S-выражение (или символическое выражение, сокращенно sexpr или sexp) — это выражение в нотации, подобной именованной, для представления вложенных списков (данных, имеющих древовидную структуру). S-выражения были изобретены и получили распространение благодаря языку программирования Lisp, который использует их как для исходного кода, так и для данных.

Анализ

S-выражения часто сравниваются с XML: одно из ключевых отличий заключается в том, что S-выражения имеют только один способ организации данных – точечную пару, в то время как теги XML могут содержать простые атрибуты, другие теги или CDATA, каждый из которых использует свой синтаксис. Другое отличие состоит в том, что S-выражения не определяют механизм ссылок, в то время как XML предоставляет понятие уникальных идентификаторов и ссылок на них. Для простых задач S-выражения проще, чем XML, но для более сложных задач XML имеет язык запросов, известный как XPath, а также множество инструментов и сторонних библиотек для упрощения работы с данными XML.

Стандартизация

Стандарты для некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI INCITS 226 1994 (R2004)), Scheme (R5RS и R6RS) и ISLISP. В мае 1997 года Рон Ривест представил проект для Интернета на рассмотрение в качестве RFC. Проект определял синтаксис, основанный на S-выражениях Lisp, но предназначенный для хранения и обмена данными общего назначения (подобно XML), а не конкретно для программирования. Он так и не был утвержден как RFC, но впоследствии был процитирован и использован в других RFC (например, RFC 2693) и ряде других публикаций. Изначально он предназначался для использования в SPKI. Формат Ривеста определяет S-выражение как последовательность октетов (серию байтов) или конечный список других S-выражений. В нем описаны три формата обмена данными для представления этой структуры. Один из них – "продвинутый транспорт", который очень гибок в плане форматирования и синтаксически похож на выражения в стиле Lisp, но не идентичен им. Например, продвинутый транспорт позволяет представлять последовательности октетов буквально (длина строки, двоеточие и вся необработанная строка), использовать экранированные формы, шестнадцатеричное представление, Base64 или помещать их непосредственно как "токены", если они соответствуют определенным условиям. (Токены Ривеста отличаются от токенов Lisp тем, что первые служат только для удобства и эстетики и обрабатываются точно так же, как и другие строки, в то время как вторые имеют конкретное синтаксическое значение.) Проект Ривеста определяет каноническое представление "для целей цифровой подписи". Оно предназначено для компактности, простоты разбора и уникальности для любого абстрактного S-выражения. Он допускает только буквальные строки и запрещает использование пробелов для форматирования вне строк. Наконец, существует "базовое транспортное представление", которое представляет собой либо каноническую форму, либо кодировку Base64, заключенную в фигурные скобки. Последнее предназначено для безопасной передачи канонически закодированного S-выражения в системе, которая может изменять интервалы (например, в почтовой системе с 80-символьными строками, где строки длиннее обрезаются). Этот формат не получил широкого распространения за пределами SPKI (некоторые пользователи – GnuPG, libgcrypt, Nettle и GNU lsh). Веб-страница S-выражений Ривеста предоставляет исходный код на C для парсера и генератора (доступный по лицензии MIT), который можно адаптировать и встраивать в другие программы. Кроме того, нет ограничений на независимую реализацию этого формата.

Standards for some Lisp derived programming languages include a specification for their S expression syntax. These include Common Lisp (ANSI standard document ANSI INCITS 226 1994 (R2004)), Scheme (R5RS and R6RS), and ISLISP. In May 1997, Ron Rivest submitted an Internet Draft to be considered for publication as an RFC. The draft defined a syntax based on Lisp S expressions but intended for general purpose data storage and exchange (similar to XML) rather than specifically for programming. It was never approved as an RFC, but it has since been cited and used by other RFCs (e. g. RFC 2693) and several other publications. It was originally intended for use in SPKI. 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.) Rivest's draft defines a canonical representation "for digital signature purposes". It's intended to be compact, easier to parse, and unique for any abstract S expression. It 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). This format has not been widely adapted for use outside of SPKI (some of the users being GnuPG, libgcrypt, Nettle, and GNU lsh). Rivest's S expressions web page provides C source code for a parser and generator (available under the MIT license), which could be adapted and embedded into other programs. In addition, there are no restrictions on independently implementing the format.