S-Expressions

1.1. Historical Notes

The S-expression technology described here was originally developed for "SDSI" (the Simple Distributed Security Infrastructure by Lampson and Rivest [SDSI]) in 1996, although the origins clearly date back to McCarthy's [LISP] programming language. It was further refined and improved during the merger of SDSI and SPKI [SPKI] [RFC2692] [RFC2693] during the first half of 1997. S-expressions are similar to, but more readable and flexible than, Bernstein's "net-strings" [BERN].¶

Although made publicly available as a file named draft-rivest-sexp-00.txt on 4 May 1997, this document was not actually submitted to the IETF as that time. Version -00 of this Internet Draft was a modernized version of that file. Version -01 has some further polishing and corrections.¶

1.2. Conventions Used in This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

4.1. Verbatim representation

A verbatim encoding of an octet string consists of three parts:¶

• the length (number of octets) of the octet-string, given in decimal, most significant digit first, with no leading zeros.¶
• a colon ":"¶
• the octet string itself, verbatim.¶

There are no blanks or whitespace separating the parts. No "escape sequences" are interpreted in the octet string. This encoding is also called a "binary" or "raw" encoding.¶

Here are some sample verbatim encodings:¶

    3:abc
    7:subject
    4:::::
    12:hello world!
    10:abcdefghij
    0:

4.2. Quoted-string representation

The quoted-string representation of an octet-string consists of:¶

• an optional decimal length field¶
• an initial double-quote (")¶
• the octet string with "C" escape conventions (\n, etc)¶
• a final double-quote (")¶

The specified length is the length of the resulting string after any escape sequences have been handled. The string does not have any "terminating NULL" that C includes, and the length does not count such a character.¶

The length is optional.¶

The escape conventions within the quoted string are as follows (these follow the "C" programming language conventions, with an extension for ignoring line terminators of just LF or CRLF and more restrictive octal and hexadecimal value formats):¶

    \a     -- audible alert (bell)
    \b     -- backspace
    \t     -- horizontal tab
    \v     -- vertical tab
    \n     -- new-line
    \f     -- form-feed
    \r     -- carriage-return
    \"     -- double-quote
    \'     -- single-quote
    \?     -- question mark
    \\     -- back-slash
    \ooo   -- character with octal value ooo (all three
              digits MUST be present)
    \xhh   -- character with hexadecimal value hh (both
              digits MUST be present)
    \<carriage-return>   -- causes carriage-return
              to be ignored.
    \<line-feed>         -- causes linefeed to be
              ignored.
    \<carriage-return><line-feed>   -- causes
              CRLF to be ignored.
    \<line-feed><carriage-return>   -- causes
              LFCR to be ignored.

Here are some examples of quoted-string encodings:¶

    "subject"
    "hi there"
    7"subject"
    3"\n\n\n"
    "This has\n two lines."
    "This has \
     one."
    ""

4.3. Token representation

An octet string that meets the following conditions may be given directly as a "token".¶

• it does not begin with a digit¶
• it contains only characters that are: alphabetic (upper or lower case); numeric; or one of the eight "pseudo-alphabetic" punctuation marks:¶

        -   .   /   _   :  *  +  =

(Note: upper and lower case are not equivalent.)¶

(Note: A token may begin with punctuation, including ":").¶

Here are some examples of token representations:¶

    subject
    not-before
    class-of-1997
    //microsoft.com/names/smith
    *

4.4. Hexadecimal representation

An octet-string may be represented with a hexadecimal encoding consisting of:¶

• an (optional) decimal length of the octet string¶
• a sharp-sign "#"¶
• a hexadecimal encoding of the octet string, with each octet represented with two hexadecimal digits, most significant digit first. There MUST be an even number of such digits.¶
• a sharp-sign "#"¶

There may be whitespace inserted in the midst of the hexadecimal encoding arbitrarily; it is ignored. It is an error to have characters other than whitespace and hexadecimal digits.¶

Here are some examples of hexadecimal encodings:¶

    #616263#    -- represents "abc"
    3#616263#   -- also represents "abc"
    # 616
      263 #     -- also represents "abc"

4.5. Base-64 representation

An octet-string may be represented in a base-64 coding [RFC4648] consisting of:¶

• an (optional) decimal length of the octet string¶
• a vertical bar "|"¶
• the base-64 [RFC4648] encoding of the octet string.¶
• a final vertical bar "|"¶

The base-64 encoding uses only the characters¶

    A-Z  a-z  0-9  +  /  =

It produces four characters of output for each three octets of input. If the input has one or two left-over octets of input, it produces an output block of length four ending in two or one equals signs, respectively. Output routines compliant with this standard MUST output the equals signs as specified. Input routines MAY accept inputs where the equals signs are dropped.¶

There may be whitespace inserted in the midst of the base-64 encoding arbitrarily; it is ignored. It is an error to have characters other than whitespace and base-64 characters.¶

Here are some examples of base-64 encodings:¶

    |YWJj|       -- represents "abc"
    | Y W
      J j |      -- also represents "abc"
    3|YWJj|      -- also represents "abc"
    |YWJjZA==|   -- represents "abcd"
    |YWJjZA|     -- also represents "abcd"

4.6. Display hint

Any octet string may be preceded by a single "display hint".¶

The purposes of the display hint is to provide information on how to display the octet string to a user. It has no other function. Many of the MIME types work here.¶

A display-hint is an octet string surrounded by square brackets. There may be whitespace separating the octet string from the surrounding brackets. Any of the legal formats may be used for the octet string.¶

Here are some examples of display-hints:¶

    [image/gif]
    [URI]
    [charset=unicode-1-1]
    [text/richtext]
    [application/postscript]
    [audio/basic]
    ["http://abc.com/display-types/funky.html"]

In applications an octet-string that is untyped may be considered to have a pre-specified "default" mime type. The mime type¶

    "text/plain; charset=iso-8859-1"

is the standard default.¶

4.7. Equality of octet-strings

Two octet strings are considered to be "equal" if and only if they have the same display hint and the same data octet strings.¶

Note that octet-strings are "case-sensitive"; the octet-string "abc" is not equal to the octet-string "ABC".¶

An untyped octet-string can be compared to another octet-string (typed or not) by considering it as a typed octet-string with the default mime-type.¶

6.2. Basic transport representation

There are two forms of the "basic transport" representation:¶

• the canonical representation¶
• an [RFC4648] base-64 representation of the canonical representation, surrounded by braces.¶

The transport mechanism is intended to provide a universal means of representing S-expressions for transport from one machine to another.¶

Here are some examples of an S-expression represented in basic transport mode:¶

    (1:a1:b1:c)

    {KDE6YTE6YjE6YykK}

The second example above is the same S-expression as the first encoded in base-64.¶

There is a difference between the brace notation for base-64 used here and the || notation for base-64'd octet-strings described above. Here the base-64 contents are converted to octets, and then re-scanned as if they were given originally as octets. With the || notation, the contents are just turned into an octet-string.¶

6.3. Advanced transport representation

The "advanced transport" representation is intended to provide more flexible and readable notations for documentation, design, debugging, and (in some cases) user interface.¶

The advanced transport representation allows all of the representation forms described above in Section 4, include quoted strings, base-64 and hexadecimal representation of strings, tokens, representations of strings with omitted lengths, and so on.¶

8.1. List-structure memory representation

Here there are separate records for simple-strings, strings, and lists. An S-expression of the form ("abc" "de") would require two records for the simple strings, two for the strings, and two for the list elements. This is a fairly conventional representation, and details are omitted here.¶

8.2. Array-layout memory representation

Here each S-expression is represented as a contiguous array of bytes. The first byte codes the "type" of the S-expression:¶

    01   octet-string

    02   octet-string with display-hint

    03   beginning of list (and 00 is used for "end of list")

Each of the three types is immediately followed by a k-byte integer indicating the size (in bytes) of the following representation. Here k is an integer that depends on the implementation, it might be anywhere from 2 to 8, but would be fixed for a given implementation; it determines the size of the objects that can be handled. The transport and canonical representations are independent of the choice of k made by the implementation.¶

Although the length of lists are not given in the usual S-expression notations, it is easy to fill them in when parsing; when you reach a right-parenthesis you know how long the list representation was, and where to go back to fill in the missing length.¶

    01 <length> <octet-string>

    01 0003 a b c

    02 <length>
      01 <length> <octet-string>    /* for display-type */
      01 <length> <octet-string>    /* for octet-string */

    [gif] #61626364#

    02 000d
      01 0003  g  i  f
      01 0004 61 62 63 64

    03 <length> <item1> <item2> <item3> ... <itemn> 00

    03 001b
      01 0003 a b c
      02 0009
        01 0001 d
        01 0002 e f
      03 0005
        01 0001 g
      00
    00

A.1. -00 Changes

This sub-section summarizes significant changes between the original 1997 -00 version of this document and the 2023 version submited to the IETF.¶

1. Convert to XML v3.¶
2. Update Ron Rivest author information and, with his permission, add Donald Eastlake as an author.¶
3. Add minimal "IANA Considerations" and "Security Considerations" sections.¶
4. Since implementation requirements terminology is used, add the usual paragraph about it as a sub-section of Section 1 and add references to [RFC2119] and [RFC8174].¶
5. Divide references into Normative and Informational and update base-64 reference to be to [RFC4648].¶
6. Add a couple of sentence to the "Historical note" section about the history of -00 versions of the draft.¶

A.2. Changes from -00 to -01

1. Fix glitches and errors in the BNF.¶
2. Add Acknowledgements section to list Marc Petit-Huguenin (who provided BNF improvements) and John Klensin.¶
3. Update code references in Section 9 and add to Informative References section. Note: The code in the Malkiewicz github repository may be the code that was originally at http://theory.lcs.mit.edu/~rivest/sexp.html¶
4. Add this Change History Appendix.¶
5. Move "Historical Notes" which were formerly a separate section at the end of the document up to be a sub-section of Section 1.¶
6. Add references to [LISP], [RFC2692], and [RFC2693].¶
7. Add simple security considerations.¶
8. Minor editorial fixes/improvements.¶