Канонические S-выражения

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

Конкретное подмножество общих S-выражений, применимых здесь, состоит из атомов , которые представляют собой байтовые строки, и круглых скобок, используемых для разделения списков или подсписков. Эти S-выражения полностью рекурсивны.

В то время как S-выражения обычно кодируются как текст с пробелами, разделяющими атомы, и кавычками, используемыми для окружения атомов, содержащих пробелы, при использовании канонического кодирования каждый атом кодируется как байтовая строка с префиксом длины. Пробелы, разделяющие соседние элементы в списке, не допускаются. Длина атома выражается десятичным числом ASCII, за которым следует знак «:».

Пример

сексп

(this "Canonical S-expression" has 5 atoms)

становится csexp

(4:this22:Canonical S-expression3:has1:55:atoms)

Кавычки не требуются для экранирования символа пробела, внутреннего для атома «Каноническое S-выражение», поскольку префикс длины явно указывает на конец атома. Нет пробела, отделяющего атом от следующего элемента в списке.

Характеристики

Уникальность канонического кодирования . Запрет пробелов между элементами списка и предоставление только одного способа кодирования атомов гарантирует, что каждое S-выражение имеет ровно одну закодированную форму. Таким образом, мы можем решить, эквивалентны ли два S-выражения, сравнивая их кодировки.
Поддержка двоичных данных : атомами может быть любая двоичная строка. Таким образом, криптографическое хэш-значение или модуль открытого ключа, которые в противном случае пришлось бы закодировать в base64 или какой-либо другой печатной кодировке, могут быть выражены в csexp в виде двоичных байтов.
Поддержка закодированной информации с маркировкой типа : csexp включает в себя конструкцию, отличную от S-выражения, для указания кодировки строки, когда эта кодировка не очевидна. Любой атом в csexp может иметь префикс одного атома в квадратных скобках, например «[4:JPEG]» или «[24:text/plain;charset=utf-8]».

Интерпретация и ограничения

Хотя csexp обычно допускают пустые списки, пустые атомы и т. д., некоторые виды использования csexp налагают дополнительные ограничения. Например, csexp, используемый в SPKI, имеет одно ограничение по сравнению с csexp в целом: каждый список должен начинаться с атома, и поэтому пустых списков быть не может.

Обычно первый атом списка рассматривается так же, как имя элемента в XML .

Сравнение с другими кодировками

Существуют и другие широко используемые кодировки:

XML
АСН.1
JSON (и YAML , который включает «JSON как официальное подмножество», с надмножеством, предназначенным для более удобного чтения человеком .)

Как правило, синтаксический анализатор csexp на один или два десятичных порядка меньше, чем у XML или ASN.1. ^{[ нужна ссылка ]} Этот небольшой размер и соответствующая скорость ^{[ нужна ссылка ]} дать csexp его главное преимущество. Помимо преимуществ синтаксического анализа, есть и другие различия.

csexp против XML

csexp и XML отличаются тем, что csexp — это формат представления данных, тогда как XML включает в себя формат представления данных, а также механизм схемы. Таким образом, XML можно «настроить» для определенных типов данных, которые соответствуют некоторой грамматике (скажем, HTML , ATOM , SVG , MathML или новым, по мере необходимости). Он имеет языки для определения грамматик документов: DTD определяется самим стандартом XML, тогда как XSD , RelaxNG и Schematron обычно используются с XML для дополнительных функций, а XML также может работать без схемы. Данные csexp, конечно, могут обрабатываться схемами, реализованными на более высоком уровне, но сами по себе такого механизма не предусмотрены.

Что касается символов и байтов, «строка» csexp может иметь любую последовательность байтов (из-за префикса длины каждого атома), в то время как XML (например, обычные S-выражения Lisp, JSON и литералы в языках программирования) требует альтернативных представления нескольких символов (например, «<» и большинства управляющих символов). Однако это не влияет на диапазон структур и семантики, которые могут быть представлены. XML также предоставляет механизмы, позволяющие указать, как следует интерпретировать данную последовательность байтов: скажем, как строку Unicode UTF-8 , файл JPEG или целое число; csexp оставляет такие различия внешним механизмам.

На самом базовом уровне и csexp, и XML представляют деревья (как и большинство других внешних представлений). Это неудивительно, поскольку XML можно описать как форму с разной пунктуацией для LISP-подобных S-выражений или наоборот. ^[1]

Однако XML включает дополнительную семантику, которая обычно реализуется в csexp посредством различных соглашений, а не как часть языка. Во-первых, каждый элемент XML имеет имя (приложения csexp обычно используют для этого первый дочерний элемент каждого выражения). Во-вторых, XML обеспечивает типизацию данных, в первую очередь через грамматику схемы. Однако схема также может различать целые числа, строки, объекты данных типов (например, JPEG) и (особенно XSD ) других типов).

Элемент XML также может иметь атрибуты — конструкцию, которая не является общей для csexp. Чтобы представить данные XML в csexp, необходимо выбрать представление таких атрибутов; очевидный вариант — зарезервировать второй элемент в каждом S-выражении для списка пар (имя-значение), аналогично списку LISP ассоциаций . Атрибуты XML ID и IDREF не имеют эквивалента в csexp, но могут быть легко реализованы с помощью прикладной программы csexp.

Наконец, элемент XML может содержать комментарии и/или инструкции по обработке. csexp не имеет конкретных эквивалентов, но их легко представить, просто зарезервировав для каждого имя. Например, назвав их «*COM» и «*PI» («*» предотвращает конфликты с именами типов элементов XML):

(4:*COM15:Text of comment)
(3:*PI6:target11:font="helv")

И csexp, и XML полностью рекурсивны.

Первый атом в списке csexp по соглашению примерно соответствует имени типа элемента XML при идентификации «типа» списка. Однако в csexp это может быть любой атом в любой кодировке (например, JPEG, строка Unicode, файл WAV и т. д.), тогда как имена элементов XML являются идентификаторами, ограниченными определенными символами, например идентификаторами языка программирования. Метод csexp, очевидно, более общий; с другой стороны, определение того, в какой кодировке находится такой элемент, и, следовательно, как его интерпретировать, определяется только соглашениями конкретного пользователя, а это означает, что приложение csexp должно создавать такие соглашения для себя, в коде, документации и т. д. .

Точно так же атомы csexp являются двоичными (состоят из префикса длины, за которым следуют совершенно произвольные байты ), тогда как XML спроектирован так, чтобы быть удобочитаемым для человека (хотя, возможно, в меньшей степени, чем JSON или YAML ) – поэтому произвольные байты в XML должны быть каким-то образом закодированы (для например, растровое изображение можно включить с помощью base64 ). Это означает, что хранение больших объемов нечитаемой информации в несжатом XML занимает больше места; с другой стороны, он выдержит преобразование между альтернативными наборами символов (включая передачу через сетевые узлы, которые могут применять разные наборы символов, соглашения о конце строки и т. д.).

Было высказано предположение, что XML «объединяет» последовательность строк внутри одного элемента в одну строку, тогда как csexp допускает последовательность атомов внутри списка, и эти атомы остаются отдельными друг от друга; но это неверно. ^[2] Точно так же, как S-выражения и csexp, XML имеет понятие «последовательность строк», только если «строки» каким-либо образом разделены:

<s>String A&lt;/s><s>String B</s>
  versus
<s>String AString B</s>

("String A" "String B")
 versus
("String AString B")

(8:String A8:String B)
 versus
(16:String AString B)

csexp против ASN.1

ASN.1 — популярная форма двоичного кодирования. Однако он выражает только синтаксис (типы данных), а не семантику. Две разные структуры, каждая из которых представляет собой ПОСЛЕДОВАТЕЛЬНОСТЬ двух ЦЕЛЫХ ЧИСЛЕННЫХ чисел, имеют одинаковое представление в сети (за исключением выбора специальных тегов для их различения). Чтобы проанализировать структуру ASN.1, необходимо сообщить синтаксическому анализатору, какой набор структур он ожидает, и синтаксический анализатор должен сопоставить анализируемый тип данных с параметрами структуры. Это усложняет анализатор ASN.1.

Структура csexp содержит некоторую информацию о своей собственной семантике (закодированную в именах элементов), и анализатор структуры csexp не заботится о том, какая структура анализируется. После того как выражение проводного формата преобразовано во внутреннюю древовидную форму (аналогично DOM XML), потребитель этой структуры может проверить ее на соответствие ожидаемому результату. XML-документ без схемы в этом отношении работает так же, как csexp, тогда как XML-документ с ними может работать больше как ASN.1.

Внешние ссылки

Примечания и ссылки

^ Это сходство было известно создателям XML . Например, Стивен ДеРоуз обсуждал это в книге «Часто задаваемые вопросы по SGML: понимание взаимосвязи SGML и XML» , Kluwer Academic Publishers, 1997. ISBN 978-0-7923-9943-8 .
^ Интерфейс SAX для XML позволяет XML анализатору разбивать (отдельные) текстовые строки любым удобным для него способом. Некоторые реализации ^{[ нужна ссылка ]} (неправильно) возвращать несколько строк как отдельные текстовые узлы, что могло привести к этому распространенному недоразумению.

[1] Это сходство было известно создателям XML . Например, Стивен ДеРоуз обсуждал это в книге «Часто задаваемые вопросы по SGML: понимание взаимосвязи SGML и XML» , Kluwer Academic Publishers, 1997. ISBN 978-0-7923-9943-8 .

[2] Интерфейс SAX для XML позволяет XML анализатору разбивать (отдельные) текстовые строки любым удобным для него способом. Некоторые реализации ^{[ нужна ссылка ]} (неправильно) возвращать несколько строк как отдельные текстовые узлы, что могло привести к этому распространенному недоразумению.

[1]

[2]