Skip to main content

S-Expressions
draft-rivest-sexp-05

Document Type Active Internet-Draft (individual)
Authors Ronald L. Rivest , Donald E. Eastlake 3rd
Last updated 2024-03-20 (Latest revision 2024-03-18)
RFC stream Internet Engineering Task Force (IETF)
Intended RFC status Informational
Formats
Stream WG state (None)
Document shepherd (None)
IESG IESG state I-D Exists
Consensus boilerplate Unknown
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-rivest-sexp-05
Network Working Group                                          R. Rivest
Internet-Draft                                                 MIT CSAIL
Intended status: Informational                               D. Eastlake
Expires: 19 September 2024                        Futurewei Technologies
                                                           18 March 2024

                             S-Expressions
                          draft-rivest-sexp-05

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.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 19 September 2024.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Rivest & Eastlake       Expires 19 September 2024               [Page 1]
Internet-Draft                S-Expressions                   March 2024

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Historical Notes  . . . . . . . . . . . . . . . . . . . .   4
     1.2.  Uses of S-Expressions . . . . . . . . . . . . . . . . . .   4
     1.3.  Conventions Used in This Document . . . . . . . . . . . .   5
   2.  S-expressions -- informal introduction  . . . . . . . . . . .   5
   3.  Character set . . . . . . . . . . . . . . . . . . . . . . . .   6
   4.  Octet string representations  . . . . . . . . . . . . . . . .   7
     4.1.  Verbatim representation . . . . . . . . . . . . . . . . .   7
     4.2.  Quoted-string representation  . . . . . . . . . . . . . .   8
     4.3.  Token representation  . . . . . . . . . . . . . . . . . .   9
     4.4.  Hexadecimal representation  . . . . . . . . . . . . . . .  10
     4.5.  Base-64 representation  . . . . . . . . . . . . . . . . .  10
     4.6.  Display hint  . . . . . . . . . . . . . . . . . . . . . .  11
     4.7.  Equality of octet-strings . . . . . . . . . . . . . . . .  12
   5.  Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . .  12
   6.  Representation types  . . . . . . . . . . . . . . . . . . . .  13
     6.1.  Canonical representation  . . . . . . . . . . . . . . . .  13
     6.2.  Basic transport representation  . . . . . . . . . . . . .  13
     6.3.  Advanced transport representation . . . . . . . . . . . .  14
   7.  ABNF for syntax . . . . . . . . . . . . . . . . . . . . . . .  14
     7.1.  ABNF for canonical transport  . . . . . . . . . . . . . .  14
     7.2.  ABNF for basic transport  . . . . . . . . . . . . . . . .  14
     7.3.  ABNF for advanced transport . . . . . . . . . . . . . . .  15
   8.  In-memory representations . . . . . . . . . . . . . . . . . .  16
     8.1.  List-structure memory representation  . . . . . . . . . .  16
     8.2.  Array-layout memory representation  . . . . . . . . . . .  16
       8.2.1.  Octet string  . . . . . . . . . . . . . . . . . . . .  17
       8.2.2.  Octet-string with display-hint  . . . . . . . . . . .  17
       8.2.3.  List  . . . . . . . . . . . . . . . . . . . . . . . .  18
   9.  Implementations . . . . . . . . . . . . . . . . . . . . . . .  18
   10. Restricted S-expressions  . . . . . . . . . . . . . . . . . .  18
   11. Security Considerations . . . . . . . . . . . . . . . . . . .  19
   12. IANA Considerations . . . . . . . . . . . . . . . . . . . . .  19
   13. Normative References  . . . . . . . . . . . . . . . . . . . .  19
   14. Informative References  . . . . . . . . . . . . . . . . . . .  19
   Appendix A.  Change History . . . . . . . . . . . . . . . . . . .  21
     A.1.  -00 Changes . . . . . . . . . . . . . . . . . . . . . . .  21
     A.2.  Changes from -00 to -01 . . . . . . . . . . . . . . . . .  22
     A.3.  Changes from -01 to -02 . . . . . . . . . . . . . . . . .  22
     A.4.  Changes from -02 to -03 . . . . . . . . . . . . . . . . .  22
     A.5.  Changes from -03 to -04 . . . . . . . . . . . . . . . . .  23
     A.6.  Changes from -04 to -05 . . . . . . . . . . . . . . . . .  23
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  23
   Contributors  . . . . . . . . . . . . . . . . . . . . . . . . . .  23
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  23

Rivest & Eastlake       Expires 19 September 2024               [Page 2]
Internet-Draft                S-Expressions                   March 2024

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 containing the following:

   *  the octet-string "snicker"

   *  the octet-string "abc"

   *  a sub-list containing two elements: the hexadecimal constant #03#
      (i.e., 0x03) and the base-64 constant |YWJj| (which is the same as
      "abc")

   This document 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 1.1 below has notes of this history of this document.
   Section 1.2 describes some current uses.

Rivest & Eastlake       Expires 19 September 2024               [Page 3]
Internet-Draft                S-Expressions                   March 2024

   Subsequent Sections of this document cover material as follows:

   *  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 an ABNF 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 restricted
      S-expressions.
   *  Section 11 briefly describes Security Considerations.

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, that file was never actually submitted to the
   IETF.  Version -00 of this document was a modernized version of that
   file.  Version -01 had some further polishing and corrections.  The
   further significant changes made in this document were changing the
   original BNF notation to ABNF [RFC5234] (see Section 7) and, when it
   has not been otherwise constrained by the application, changing the
   default character set in Section 4.6 to UTF-8 [RFC4648].

1.2.  Uses of S-Expressions

   S-expressions are in active use today between GnuPG [GnuPG] and
   Ribose's RNP [Ribose].  Ribose has implemented C++ software to
   compose and parse S-expressions [RNPGP_SEXPP] and, in fact,
   references this document.  The GNU software is here [Libgcrypt] and
   there are other implementations (see Section 9.

   S-expressions are used/referenced in the following RFCs:

   *  [RFC9208] IMAP QUOTA Extension

Rivest & Eastlake       Expires 19 September 2024               [Page 4]
Internet-Draft                S-Expressions                   March 2024

   *  [RFC3275] XML-Signature Syntax and Processing

   *  [RFC2693] for [SPKI]

   *  [RFC1203] IMAP v3

   *  [RFC1176] IMAP v2

   In addition, S-Expressions are the inspiration for the encodings in
   other protocols.  For example, Section 6 of [CDDLfreezer] or
   [RFC3259].

1.3.  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.

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"

   The above 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 simple string.

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

Rivest & Eastlake       Expires 19 September 2024               [Page 5]
Internet-Draft                S-Expressions                   March 2024

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

   As we see, there is variability possible in the encoding of an
   S-expression.  In some applications, 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" or "basic" 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; as specified herein, the canonical
   encoding is the same as the transport encoding, for example.  In this
   document we provide (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 ASCII [RFC0020]:

   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

Rivest & Eastlake       Expires 19 September 2024               [Page 6]
Internet-Draft                S-Expressions                   March 2024

          ) 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" and "quoted string" 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.

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:

Rivest & Eastlake       Expires 19 September 2024               [Page 7]
Internet-Draft                S-Expressions                   March 2024

       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" [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" [C] programming language conventions, with an
   extension for ignoring line terminators of just LF, CRLF, or LFCR and
   more restrictive octal and hexadecimal value formats):

Rivest & Eastlake       Expires 19 September 2024               [Page 8]
Internet-Draft                S-Expressions                   March 2024

       \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:

           -   .   /   _   :  *  +  =

Rivest & Eastlake       Expires 19 September 2024               [Page 9]
Internet-Draft                S-Expressions                   March 2024

   (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.

Rivest & Eastlake       Expires 19 September 2024              [Page 10]
Internet-Draft                S-Expressions                   March 2024

   *  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 [RFC2046] 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:

Rivest & Eastlake       Expires 19 September 2024              [Page 11]
Internet-Draft                S-Expressions                   March 2024

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

   Unless some other type is specified for the application of use, an
   octet-string that is untyped may be considered to have a pre-
   specified "default" MIME [RFC2046] typeas follows:

       "text/plain; charset=utf-8"

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 type specified for the applications or, in the absence of
   such specificaion, the default type specified in Section 4.6 .

5.  Lists

   Just as with octet-strings, there are several ways to represent a
   list.  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))

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

Rivest & Eastlake       Expires 19 September 2024              [Page 12]
Internet-Draft                S-Expressions                   March 2024

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.1.  Canonical representation

   This canonical representation is used for digital signature purposes,
   transmission, etc.  It is uniquely defined for each S-expression.  It
   is not particularly readable, but that is not the point.  It is
   intended to be very easy to parse, to be reasonably economical, and
   to be unique for any S-expression.

   The "canonical" form of an S-expression represents each octet-string
   in verbatim mode, and represents each list with no blanks separating
   elements from each other or from the surrounding parentheses.

   Here are some examples of canonical representations of S-expressions:

       (6:issuer3:bob)

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

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

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.
   The base-64 encoding would be appropriate if the channel over which
   the S-expression is being sent might be sensitive to bytes of some
   special values such as a byte of all zero bits (NULL) or a byte of
   all one bits (DEL).

Rivest & Eastlake       Expires 19 September 2024              [Page 13]
Internet-Draft                S-Expressions                   March 2024

   Here are two 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 single 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.

7.  ABNF for syntax

   ABNF is the Augmented Backus-Naur Form for syntax specifications as
   defined in [RFC5234].  We give separate ABNF's for canonical, basic,
   and advanced forms of S-expressions.  The rules below in all caps are
   defined in Appendix A of [RFC5234].

7.1.  ABNF for canonical transport

   sexp     =  raw / ("(" *sexp ")")

   raw      =  decimal ":" *OCTET
                  ; the length followed by a colon and the exact
                  ;  number of OCTET indicated by the length

   decimal  =  %x30 / (%x31-39 *DIGIT)

7.2.  ABNF for basic transport

Rivest & Eastlake       Expires 19 September 2024              [Page 14]
Internet-Draft                S-Expressions                   March 2024

   sexp           =  canonical / base-64-raw

   canonical      =  raw / ("(" *canonical ")")

   raw            =  decimal ":" *OCTET
                        ; the length followed by a colon and the exact
                        ;  number of OCTET indicated by the length

   decimal        =  %x30 / (%x31-39 *DIGIT)

   base-64-raw    =  "{" 3*base-64-char "}"

   base-64-char   =  ALPHA / DIGIT / "+" / "/" / "="

7.3.  ABNF for advanced transport

   sexp           =  *whitespace value *whitespace

   whitespace     =  SP / HTAB / vtab / CR / LF / ff

   vtab           =  %x0B   ; vertical tab

   ff             =  %x0C   ; form feed

   value          =  string / ("(" *(value / whitespace) ")")

   string         =  [display] *whitespace simple-string

   display        =  "[" *whitespace simple-string *whitespace "]"

   simple-string  =  raw / token / base-64 / base-64-raw /
                           hexadecimal / quoted-string

   raw            =  decimal ":" *OCTET
                        ; the length followed by a colon and the exact
                        ;  number of OCTET indicated by the length

   decimal        =  %x30 / (%x31-39 *DIGIT)

   token          =  (ALPHA / simple-punc) *(ALPHA / DIGIT /
                        simple-punc)

   simple-punc    =  "-" / "." / "/" / "_" / ":" / "*" / "+" / "="

   base-64        =  [decimal] "|" *(base-64-char / whitespace) "|"

   base-64-char   =  ALPHA / DIGIT / "+" / "/" / "="

Rivest & Eastlake       Expires 19 September 2024              [Page 15]
Internet-Draft                S-Expressions                   March 2024

   base-64-raw    =  [decimal] "{" 1*(base-64-char / whitespace) "}"
                        ; at least 3 base-64-char

   hexadecimal    =  [decimal] "#" *(HEXDIG / whitespace) "#"
                        ; even number of hexadecimal digits

   quoted-string  =  [decimal] DQUOTE *(printable / escaped) DQUOTE

   escaped        =  backslash (%x3F / %x61 / %x62 / %x66 / %x6E /
                     %x72 / %x74 / %x76 / DQUOTE / quote / backslash /
                     3(%x30-37) / (%x78 2HEXDIG) / CR / LF /
                     (CR LF) / (LF CR))

   backslash      =  %x5C

   printable      =  %x21-26 / %x28-7E

   quote          =  %x27   ; single quote

8.  In-memory representations

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

   *  "list-structure"

   *  "array-layout"

   We only sketch these here, as they are only suggestive.  The
   [SexpCode] code illustrates these styles in more detail.

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:

Rivest & Eastlake       Expires 19 September 2024              [Page 16]
Internet-Draft                S-Expressions                   March 2024

       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 lengths 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.

8.2.1.  Octet string

   This is represented as follows:

       01 <length> <octet-string>

   For example (here k = 2)

       01 0003 a b c

8.2.2.  Octet-string with display-hint

   This is represented as follows:

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

   For example, the S-expression

       [gif] #61626364#

   would be represented as (with k = 2)

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

Rivest & Eastlake       Expires 19 September 2024              [Page 17]
Internet-Draft                S-Expressions                   March 2024

8.2.3.  List

   This is represented as

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

   For example, the list (abc [d]ef (g)) is represented in memory as
   (with k=2)

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

9.  Implementations

   At this time there is code available that is intended to read and
   parse some or all of the various S-expression formats specified here.
   In particular, see the following likely incomplete list:

   *  Project GNU's [Libgcrypt].

   *  Ribose's RNP [RNPGP_SEXPP].

   *  Github project of J.  P.  Malkiewicz [SexpCode].

   *  The Inferno implementation [Inferno].

10.  Restricted S-expressions

   This document has described S-expressions in general form.
   Application writers may wish to restrict their use of S-expressions
   in various ways as well as to specify a different default display
   hint.  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

Rivest & Eastlake       Expires 19 September 2024              [Page 18]
Internet-Draft                S-Expressions                   March 2024

   *  no lists having another list as its first element

   *  no base-64 or hexadecimal encodings

   *  fixed limits on the size of octet-strings

11.  Security Considerations

   As a pure data representation format, there are few security
   considerations to S-expressions.  A canonical form is required for
   the reliable verification of digital signatures.  This is provided in
   Section 6.1.

12.  IANA Considerations

   This document requires no IANA actions.

13.  Normative References

   [C]        Kernighan, B. and D. Ritchie, "The C Programming
              Language", ISBN 0-13-110370-9, 1988.

   [RFC0020]  Cerf, V., "ASCII format for network interchange", STD 80,
              RFC 20, DOI 10.17487/RFC0020, October 1969,
              <https://www.rfc-editor.org/info/rfc20>.

   [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>.

   [RFC5234]  Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax
              Specifications: ABNF", STD 68, RFC 5234,
              DOI 10.17487/RFC5234, January 2008,
              <https://www.rfc-editor.org/info/rfc5234>.

   [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>.

14.  Informative References

Rivest & Eastlake       Expires 19 September 2024              [Page 19]
Internet-Draft                S-Expressions                   March 2024

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

   [CDDLfreezer]
              Borman, C., "A feature freezer for the Concise Data
              Definition Language (CDDL)", work in progress, 12
              September 2023, <https://datatracker.ietf.org/doc/draft-
              bormann-cbor-cddl-freezer/>.

   [GnuPG]    Free Software Foundation, Inc., "The GNU Privacy Guard",
              <https://www.gnupg.org/>.

   [Inferno]  Uriel, "Inferno S-expressions",
              <http://man.cat-v.org/inferno/6/sexprs>.

   [Libgcrypt]
              GnuPG, "The Libgcrypt Library", Libgcrypt version 1.10.2,
              6 April 2023,
              <https://www.gnupg.org/documentation/manuals/gcrypt/>.

   [LISP]     Levin, M. and J. McCarthy, "LISP 1.5 Programmer's Manual",
              ISBN-13 978-0-262-12011-0, ISBN-10 0262130114, 15 August
              1962.

   [RFC1176]  Crispin, M., "Interactive Mail Access Protocol: Version
              2", RFC 1176, DOI 10.17487/RFC1176, August 1990,
              <https://www.rfc-editor.org/info/rfc1176>.

   [RFC1203]  Rice, J., "Interactive Mail Access Protocol: Version 3",
              RFC 1203, DOI 10.17487/RFC1203, February 1991,
              <https://www.rfc-editor.org/info/rfc1203>.

   [RFC2046]  Freed, N. and N. Borenstein, "Multipurpose Internet Mail
              Extensions (MIME) Part Two: Media Types", RFC 2046,
              DOI 10.17487/RFC2046, November 1996,
              <https://www.rfc-editor.org/info/rfc2046>.

   [RFC2692]  Ellison, C., "SPKI Requirements", RFC 2692,
              DOI 10.17487/RFC2692, September 1999,
              <https://www.rfc-editor.org/info/rfc2692>.

   [RFC2693]  Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas,
              B., and T. Ylonen, "SPKI Certificate Theory", RFC 2693,
              DOI 10.17487/RFC2693, September 1999,
              <https://www.rfc-editor.org/info/rfc2693>.

Rivest & Eastlake       Expires 19 September 2024              [Page 20]
Internet-Draft                S-Expressions                   March 2024

   [RFC3259]  Ott, J., Perkins, C., and D. Kutscher, "A Message Bus for
              Local Coordination", RFC 3259, DOI 10.17487/RFC3259, April
              2002, <https://www.rfc-editor.org/info/rfc3259>.

   [RFC3275]  Eastlake 3rd, D., Reagle, J., and D. Solo, "(Extensible
              Markup Language) XML-Signature Syntax and Processing",
              RFC 3275, DOI 10.17487/RFC3275, March 2002,
              <https://www.rfc-editor.org/info/rfc3275>.

   [RFC9208]  Melnikov, A., "IMAP QUOTA Extension", RFC 9208,
              DOI 10.17487/RFC9208, March 2022,
              <https://www.rfc-editor.org/info/rfc9208>.

   [Ribose]   Ribose Group Inc., "Open-source projects for developers
              and designers", 13 April 2023, <https://open.ribose.com/>.

   [RNPGP_SEXPP]
              RNP, R., "S-Expressions parser and generator library in
              C++ (SEXP in C++)", version 0.8.7, 28 June 2023,
              <https://github.com/rnpgp/sexpp>.

   [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>.

   [SexpCode] Malkiewicz, J., "SEXP---(S-expressions)", 10 June 2015,
              <https://github.com/jpmalkiewicz/rivest-sexp>.

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

Appendix A.  Change History

   RFC Editor Note: Please delete this section before publication.

A.1.  -00 Changes

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

   1.  Convert to XML v3.

   2.  Update Ron Rivest author information and, with his permission,
       add Donald Eastlake as an author.

Rivest & Eastlake       Expires 19 September 2024              [Page 21]
Internet-Draft                S-Expressions                   March 2024

   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 sentences 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.

A.3.  Changes from -01 to -02

   1.  Change default MIME Type in Section 4.6 to have charset=utf-8
       [RFC4648].

   2.  Change BNF to ABNF and add reference to [RFC5234].

   3.  Move Marc Petit-Huguenin to a Contributors section for his work
       on the ABNF.

A.4.  Changes from -02 to -03

Rivest & Eastlake       Expires 19 September 2024              [Page 22]
Internet-Draft                S-Expressions                   March 2024

   1.  Add current S-expression usage Section 1.2.

   2.  Add the white book [C] as a reference.

   3.  Add reference to the Ribose RNP code [RNPGP_SEXPP].

   4.  Minor editorial improvements.

A.5.  Changes from -03 to -04

   Trivial keep-alive update.

A.6.  Changes from -04 to -05

   1.  Add reference to Inferno implementation.

   2.  Eliminate remaining references to being a "proposal".

   3.  Emphasize that a particular application can specify a different
       default display hint.

   4.  Add reference to RFC 0020 for ASCII.

   5.  Minor editorial improvements.

Acknowledgements

   The comments and suggestions of the following are gratefully
   acknowledged: John Klensin and Caleb Malchik.

Contributors

   Special thanks to the following contributor:

   Marc Petit-Huguenin
   Impedance Mismatch LLC
   Email: marc@petit-huguenin.org

Authors' Addresses

   Ronald L. Rivest
   MIT CSAIL
   32 Vassar Street, Room 32-G692
   Cambridge, Massachusetts 02139
   United States of America
   Email: rivest@mit.edu
   URI:   https://www.csail.mit.edu/person/ronald-l-rivest

Rivest & Eastlake       Expires 19 September 2024              [Page 23]
Internet-Draft                S-Expressions                   March 2024

   Donald E. Eastlake 3rd
   Futurewei Technologies
   2386 Panoramic Circle
   Apopka, Florida 32703
   United States of America
   Phone: +1-508-333-2270
   Email: d3e3e3@gmail.com

Rivest & Eastlake       Expires 19 September 2024              [Page 24]