S-Expressions

Abstract

This memo describes a data structure called "S-expressions" that are suitable for representing arbitrary complex data structures. We make precise the encodings of S-expressions: we give a "canonical form" for S-expressions, described two "transport" representations, and also describe an "advanced" format for display to people.¶

1. Introduction

S-expressions are data structures for representing complex data. They are either byte-strings ("octet-strings") or lists of simpler S-expressions. Here is a sample S-expression:¶

    (snicker "abc" (#03# |YWJj|))

It is a list of length three:¶

• the octet-string "snicker"¶
• the octet-string "abc"¶
• a sub-list containing two elements: the hexadecimal constant #03# and the base-64 constant |YWJj| (which is the same as "abc")¶

This note gives a specific proposal for constructing and utilizing S-expressions. The proposal is independent of any particular application.¶

Here are the design goals for S-expressions:

generality:

S-expressions should be good at representing arbitrary data.¶

readability:

it should be easy for someone to examine and understand the structure of an S-expression.¶

economy:

S-expressions should represent data compactly.¶

tranportability:

S-expressions should be easy to transport over communication media (such as email) that are known to be less than perfect.¶

flexibility:

S-expressions should make it relatively simple to modify and extend data structures.¶

canonicalization:

it should be easy to produce a unique "canonical" form of an S-expression, for digital signature purposes.¶

efficiency:

S-expressions should admit in-memory representations that allow efficient processing.¶

Section 2 gives an introduction to S-expressions.¶

Section 3 discusses the character sets used.¶

Section 4 presents the various representations of octet-strings.¶

Section 5 describes how to represent lists.¶

Section 6 discusses how S-expressions are represented for various uses.¶

Section 7 gives a BNF syntax for S-expressions.¶

Section 8 talks about how S-expressions might be represented in memory.¶

Section 9 briefly describes implementations for handling S-expressions.¶

Section 10 discusses how applications might utilize S-expressions.¶

Section 11 gives historical notes on S-expressions.¶

Section 12 gives references.¶

2. S-expressions -- informal introduction

Informally, an S-expression is either:¶

• an octet-string, or¶
• a finite list of simpler S-expressions.¶

An octet-string is a finite sequence of eight-bit octets. There may be many different but equivalent ways of representing an octet-string¶

abc   

-- as a token¶

"abc" 

-- as a quoted string¶

#616263#

-- as a hexadecimal string¶

3:abc 

-- as a length-prefixed "verbatim" encoding¶

{MzphYmM=}

-- as a base-64 encoding of the verbatim encoding (that is, an encoding of "3:abc")¶

|YWJj|

-- as a base-64 encoding of the octet-string "abc"¶

These encodings are all equivalent; they all denote the same octet string.¶

We will give details of these encodings later on, and also describe how to give a "display type" to a byte string.¶

A list is a finite sequence of zero or more simpler S-expressions. A list may be represented by using parentheses to surround the sequence of encodings of its elements, as in:¶

    (abc (de #6667#) "ghi jkl")

As we see, there is variability possible in the encoding of an S-expression. In some cases, it is desirable to standardize or restrict the encodings; in other cases it is desirable to have no restrictions. The following are the target cases we aim to handle:¶

• a "transport" encoding for transporting the S-expression between computers.¶
• a "canonical" encoding, used when signing the S-expression.¶
• an "advanced" encoding used for input/output to people.¶
• an "in-memory" encoding used for processing the S-expression in the computer.¶

These need not be different; in this proposal the canonical encoding is the same as the transport encoding, for example. In this note we propose (related) encoding techniques for each of these uses.¶

3. Character set

We will be describing encodings of S-expressions. Except when giving "verbatim" encodings, the character set used is limited to the following characters in US-ASCII:¶

Alphabetic:

A B ... Z a b ... z

¶

numeric:

0 1 ... 9

¶

whitespace:

space, horizontal tab, vertical tab, form-feed
  carriage-return, line-feed

¶

The following graphics characters, which we call "pseudo-alphabetic":

    - hyphen or minus
    . period
    / slash
    _ underscore
    : colon
    * asterisk
    + plus
    = equal

¶

The following graphics characters, which are "reserved punctuation":

    ( left parenthesis
    ) right parenthesis
    [ left bracket
    ] right bracket
    { left brace
    } right brace
    | vertical bar
    # number sign
    " double quote
    & ampersand
    \ backslash

¶

The following characters are unused and unavailable, except in "verbatim" encodings:

    ! exclamation point
    % percent
    ^ circumflex
    ~ tilde
    ; semicolon
    ' apostrophe
    , comma
    < less than
    > greater than
    ? question mark

¶

4. Octet string representations

This section describes in detail the ways in which an octet-string may be represented.¶

We recall that an octet-string is any finite sequence of octets, and that the octet-string may have length zero.¶

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

    \b      -- backspace
    \t      -- horizontal tab
    \v      -- vertical tab
    \n      -- new-line
    \f      -- form-feed
    \r      -- carriage-return
    \"      -- double-quote
    \'      -- single-quote
    \\      -- 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.

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

        -   .   /   _   :  *  +  =

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

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

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

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

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

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

5. Lists

Just as with octet-strings, there are several ways to represent an S-expression. Whitespace may be used to separate list elements, but they are only required to separate two octet strings when otherwise the two octet strings might be interpreted as one, as when one token follows another. Also, whitespace may follow the initial left parenthesis, or precede the final right parenthesis.¶

Here are some examples of encodings of lists:¶

    (a b c)

    ( a ( b c ) ( ( d e ) ( e f ) )  )

    (11:certificate(6:issuer3:bob)(7:subject5:alice))

    ({3Rt=} "1997" murphy 3:{XC++})

6. Representation types

There are three "types" of representations:¶

• canonical¶
• basic transport¶
• advanced transport¶

The first two MUST be supported by any implementation; the last is optional.¶

    (6:issuer3:bob)

    (4:icon[12:image/bitmap]9:xxxxxxxxx)

    (7:subject(3:ref5:alice6:mother))

    (1:a1:b1:c)

    {KDE6YTE6YjE6YykA}

7. BNF for syntax

We give separate BNF's for canonical and advanced forms of S-expressions. We use the following notation:¶

    <x>*          means 0 or more occurrences of <x>
    <x>+          means 1 or more occurrences of <x>
    <x>?          means 0 or 1 occurrences of <x>
    parentheses   are used for grouping, as in (<x> | <y>)*

For canonical and basic transport:¶

<sexpr>         :: <string> | <list>
<string>        :: <display>? <simple-string> ;
<simple-string> :: <raw> ;
<display>       :: "[" <simple-string> "]" ;
<raw>           :: <decimal> ":" <bytes> ;
<decimal>       :: <decimal-digit>+ ;
    -- decimal numbers should have no unnecessary leading zeros
<bytes>         -- any string of bytes, of the indicated length
<list>          :: "(" <sexp>* ")" ;
<decimal-digit> :: "0" | ... | "9" ;

For advanced transport:¶

<sexpr>         :: <string> | <list>
<string>        :: <display>? <simple-string> ;
<simple-string> :: <raw> | <token> | <base-64> |
                       <hexadecimal> | <quoted-string> ;
<display>       :: "[" <simple-string> "]" ;
<raw>           :: <decimal> ":" <bytes> ;
<decimal>       :: <decimal-digit>+ ;
    -- decimal numbers should have no unnecessary leading zeros
<bytes>         -- any string of bytes, of the indicated length
<token>         :: <tokenchar>+ ;
<base-64>       :: <decimal>? "|"( <base-64-char> |
                       <whitespace> )* "|" ;
<hexadecimal>   :: "#" ( <hex-digit> | <white-space> )* "#" ;
<quoted-string> :: <decimal>? <quoted-string-body>
<quoted-string-body> :: "\"" <bytes> "\""
<list>          :: "(" ( <sexp> | <whitespace> )* ")" ;
<whitespace>    :: <whitespace-char>* ;
<token-char>    :: <alpha> | <decimal-digit> | <simple-punc> ;
<alpha>         :: <upper-case> | <lower-case> | <digit> ;
<lower-case>    :: "a" | ... | "z" ;
<upper-case>    :: "A" | ... | "Z" ;
<decimal-digit> :: "0" | ... | "9" ;
<hex-digit>     :: <decimal-digit> |
                       "A" | ... | "F" | "a" | ... | "f" ;
<simple-punc>   :: "-" | "." | "/" | "_" |
                       ":" | "*" | "+" | "=" ;
<whitespace-char> :: " " | "\t" | "\r" | "\n" ;
<base-64-char>  :: <alpha> | <decimal-digit> |
                       "+" | "/" | "=" ;
<null>          :: "" ;

8. In-memory representations

For processing, the S-expression would typically be parsed and represented in memory in a more more amenable to efficient processing. We suggest two alternatives:¶

• "list-structure"¶
• "array-layout"¶

We only sketch these here, as they are only suggestive. The code referenced below illustrates these styles in more detail.¶

    01   octet-string

    02   octet-string with display-hint

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

    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

9. Code

There is code available for reading and parsing the various S-expression formats proposed here.¶

See http://theory.lcs.mit.edu/~rivest/sexp.html¶

10. Utilization of S-expressions

This note has described S-expressions in general form. Application writers may wish to restrict their use of S-expressions in various ways. Here are some possible restrictions that might be considered:¶

• no display-hints¶
• no lengths on hexadecimal, quoted-strings, or base-64 encodings¶
• no empty lists¶
• no empty octet-strings¶
• no lists having another list as its first element¶
• no base-64 or hexadecimal encodings¶
• fixed limits on the size of octet-strings¶

11. Historical note

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] 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. This is a modernized version of that file.¶

12. IANA Considerations

This document requires no IANA actions.¶

13. Security Consideration

TBD¶

14. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.

[RFC4648]

Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, <https://www.rfc-editor.org/info/rfc4648>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.

15. Informative References

[BERN]

Bernstein, D., "Netstrings", Work in progress, 1 February 1997, <https://www.ietf.org/archive/id/draft-bernstein-netstrings-02.txt>.

[SDSI]

Rivest, R. and B. Lampson, "A Simple Distributed Security Architecture", working document, SDSI version 1.1, 2 October 1996, <https://people.csail.mit.edu/rivest/pubs/RL96.ver-1.1.html>.

[SPKI]

"SPKI--A Simple Public Key Infrastructure", <http://www.clark.net/pub/cme/html/spki.html>.