Canonical S-expressions
Encyclopedia
A Canonical S-expression (or csexp) is a binary encoding form of a subset of general S-expression
S-expression
S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...

. It was designed for use in SPKI - to retain the power of S-expressions, while achieving the compactness of a binary form and maximizing the speed of parsing.

An S-expression is composed of atoms, which are byte strings, and parentheses used to delimit lists or sub-lists. S-expressions are fully recursive. Typically, S-expressions are encoded as text, with spaces delimiting atoms and quotation marks used to surround atoms that contain spaces.

Atoms in a Canonical S-expression are encoded as length-prefixed byte strings. The length of the following byte string is expressed as an ASCII decimal number followed by a ":".

The sexp

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

becomes the csexp

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

There is no white space to be normalized - thus the adjective canonical - and the atoms can be any binary string. So, a cryptographic hash value or a public key modulus that would have to be encoded in base64
Base64
Base64 is a group of similar encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation...

 or some other printable encoding can be expressed in csexp as its binary bytes.

Binary byte strings can represent various encodings. A csexp includes a non-S-expression construct for indicating the encoding of a string, when that encoding is not obvious. Any atom in csexp can be prefixed by a single atom in square brackets - such as "[4:JPEG]" or "[7:UNICODE]".

Finally, while csexps generally permit empty lists, empty atoms, and so forth, certain uses of csexps impose additional restrictions. For example, csexps as used in SPKI have one limitation compared to csexps 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
XML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

.

Comparisons to other encodings

There are other encodings in common use:
  1. XML
    XML
    Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

  2. ASN.1
  3. JSON
    JSON
    JSON , or JavaScript Object Notation, is a lightweight text-based open standard designed for human-readable data interchange. It is derived from the JavaScript scripting language for representing simple data structures and associative arrays, called objects...



Generally, csexp 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 give csexp its main advantage. In addition to the parsing advantage, there are other differences.

csexp vs. XML

A csexp is roughly as expressive as XML. This is not surprising, since XML is described as an ASCII form for S-expressions. However, csexp does not have a concept like XML attributes (within an element). When encoding in csexp, one must plan on a representation for such attributes.

A csexp, like a general sexp, is fully recursive. XML, however, has limitations on recursive use of element names.

The first atom in a csexp list - the equivalent of an XML element name - can be any atom in any encoding (e.g., a JPEG, a UNICODE string, a WAV file, ...). XML element names are constrained to use a subset of the printable character set.

XML merges a sequence of strings within one element into a single string, while csexp allows a sequence of atoms within a list and those atoms remain separate from one another.

Finally, csexp is inherently binary while XML is printable - so binary quantities in XML must be encoded, for example using base64
Base64
Base64 is a group of similar encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation...

.

csexp 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 csexp structure, like an XML document, carries its own semantics (encoded in element names), and the parser for a csexp 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.

Links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK