Canonical S-expressions
A Canonical S-expression (or
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
) is a binary encoding form of a subset of general S-expression (or sexp). It was designed for use in SPKI to retain the power of S-expressions and ensure canonical form for applications such as digital signatures while achieving the compactness of a binary form and maximizing the speed of parsing.
The particular subset of general S-expressions applicable here is composed of atoms, which are byte strings, and parentheses used to delimit lists or sub-lists. These S-expressions are fully recursive.
While S-expressions are typically encoded as text, with spaces delimiting atoms and quotation marks used to surround atoms that contain spaces, when using the canonical encoding each atom is encoded as a length-prefixed byte string. No whitespace separating adjacent elements in a list is permitted. The length of an atom is expressed as an ASCII decimal number followed by a ":".
Example
The sexp
(this "Canonical S-expression" has 5 atoms)
becomes the
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
(4:this22:Canonical S-expression3:has1:55:atoms)
No quotation marks are required to escape the space character internal to the atom "Canonical S-expression", because the length prefix clearly points to the end of the atom. There is no whitespace separating an atom from the next element in the list.
Properties
- Uniqueness of canonical encoding: Forbidding whitespace between list elements and providing just one way of encoding atoms ensures that every S-expression has exactly one encoded form. Thus, we can decide whether two S-expressions are equivalent by comparing their encodings.
- Support for binary data: Atoms can be any binary string. So, a cryptographic hash value or a public key modulus that would otherwise have to be encoded in base64 or some other printable encoding can be expressed in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
as its binary bytes.
- Support for type-tagging encoded information: A
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
includes a non-S-expression construct for indicating the encoding of a string, when that encoding is not obvious. Any atom in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
can be prefixed by a single atom in square brackets – such as "[4:JPEG]" or "[24:text/plain;charset=utf-8]".
Interpretation and restrictions
While
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
generally permit empty lists, empty atoms, and so forth, certain uses of
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
impose additional restrictions. For example,
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
as used in SPKI have one limitation compared to
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
in general: every list must start with an atom, and therefore there can be no empty lists.
Typically, a list's first atom is treated as one treats an element name in XML.
Comparisons to other encodings
There are other encodings in common use:
- XML
- ASN.1
- JSON (and YAML that includes "JSON as an official subset", with the superset, meant to be more human-readable.)
Generally,
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
has a parser one or two decimal orders of magnitude smaller than that of either XML or ASN.1. This small size and corresponding speed{{citation needed|date=January 2014} dvantage. In addition to the parsing advantage, there are other differences.
===
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
vs. XML ===
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
and XML differ in that
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
is a data-representation format, while XML includes a data-representation format and also a schema mechanism. Thus, XML can be "configured" for particular kinds of data, which conform to some grammar (say, HTML, ATOM, SVG, MathML, or new ones as needed). It has languages for defining document grammars: DTD is defined by the XML standard itself, while XSD, RelaxNG, and Schematron are commonly used with XML for additional features, and XML can also work with no schema.
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
data can of course be operated on by schemas implemented at a higher level, but provides no such mechanism itself.
In terms of characters and bytes, a
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
"string" may have any byte sequence whatsoever (because of the length prefix on each atom), while XML (like regular Lisp S-expressions, JSON, and literals in programming languages), requires alternate representations for a few characters (such as "<" and most control characters). This, however, has no effect on the range of structures and semantics that can be represented. XML also provides mechanisms to specify how a given byte sequence is intended to be interpreted: Say, as a Unicode UTF-8 string, a JPEG file, or an integer;
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
leaves such distinctions to external mechanisms.
At the most basic level, both
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
and XML represent trees (as do most other external representations). This is not surprising, since XML can be described as a differently-punctuated form for LISP-like S-expressions, or vice versa.[1]
However, XML includes additional semantics, which are commonly achieved in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
by various conventions rather than as part of the language. First, every XML element has a name (
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
applications commonly use the first child of each expression for this). Second, XML provides data typing, firstly via the schema grammar. A schema can also, however, distinguish integers, strings, data objects with types (e.g. JPEG) and (especially with XSD) other types).
An XML element may also have attributes, a construct that
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
does not share. To represent XML data in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
, one must choose a representation for such attributes; an obvious one is to reserve the second item in each S-expression for a list of (name value) pairs, analogous to the LISP association list. The XML ID and IDREF attributes have no equivalent in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
, but can be easily implemented by a
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
application program.
Finally, an XML element may contain comments and/or processing instructions.
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
has no specific equivalents, but they are trivial to represent, merely by reserving a name for each. For example, naming them "*COM" and "*PI" (the "*" prevents ever colliding with XML element type names):
(4:*COM15:Text of comment) (3:*PI6:target11:font="helv")
Both
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
and XML are fully recursive.
The first atom in a
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
list, by convention roughly corresponds to an XML element type name in identifying the "type" of the list. However, in
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
this can be any atom in any encoding (e.g., a JPEG, a Unicode string, a WAV file, …), while XML element names are identifiers, constrained to certain characters, like programming-language identifiers.
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
's method is obviously more general; on the other hand, Identifying what encoding such an item is in, and thus how to interpret it, is determined only by a particular user's conventions, meaning that a
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
application must build such conventions for itself, in code, documentation, and so forth.
Similarly,
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
atoms are binary (consisting of a length prefix followed by totally arbitrary bytes), while XML is designed to be human-readable (while arguably less so than JSON or YAML) – so arbitrary bytes in XML must be encoded somehow (for example, a bitmapped image can be included using base64). This means that storing large amounts of non-readable information in uncompressed XML takes more space; on the other hand, it will survive translation between alternate character sets (including transmission through network hosts that may apply differing character sets, line-end conventions, etc.).
It has been suggested that XML "merges" a sequence of strings within one element into a single string, while
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
allows a sequence of atoms within a list and those atoms remain separate from one another; but this is incorrect.[2] Exactly like S-expressions and
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
, XML has a notion of a "sequence of strings" only if the "strings" are separated somehow:
<s>String A</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)
===
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
vs. ASN.1 ===
ASN.1 is a popular binary encoding form. However, it expresses only syntax (data types), not semantics. Two different structures – each a SEQUENCE of two INTEGERS – have identical representations on the wire (barring special tag choices to distinguish them). To parse an ASN.1 structure, one must tell the parser what set of structures one is expecting and the parser must match the data type being parsed against the structure options. This adds to the complexity of an ASN.1 parser.
A
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
structure carries some indication of its own semantics (encoded in element names), and the parser for a
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
structure does not care what structure is being parsed. Once a wire-format expression has been parsed into an internal tree form (similar to XML's DOM), the consumer of that structure can examine it for conformance to what was expected. An XML document without a schema works just like
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
in this respect, while an XML document with them can work more like ASN.1.
External links
- Ron Rivest's sexp page
- Ron Rivest's IETF-draft describing S-expressions
- Template:Sum RFC
- [http://theworld.com/~cme/html/spki.html#Code various uses of
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
, including s2x: translating
- REDIRECT Template:Lang unset italics
This page is a redirect. The following categories are used to track and monitor this redirect:
|
to XML]
Notes and references
- ↑ This similarity was known to the framers of XML. For example, Steven DeRose discussed it in The SGML FAQ Book: Understanding the Relationship of SGML and XML, Kluwer Academic Publishers, 1997. ISBN 978-0-7923-9943-8.
- ↑ The SAX interface to XML allows an XML parser to break up (single) text strings any way it likes. Some implementations (incorrectly) return multiple lines as single text nodes, which may have led to this common misunderstanding.
 |  |
