<?xml version='1.0' encoding='utf-8'?>
<rfc xmlns:xi="http://www.w3.org/2001/XInclude" version="3" category="info" docName="draft-rivest-sexp-13" number="9804" ipr="trust200902" obsoletes="" submissionType="IETF" xml:lang="en" updates="" consensus="true" tocInclude="true" symRefs="true" sortRefs="true" prepTime="2025-06-17T13:39:10" indexInclude="true" scripts="Common,Latin" tocDepth="3">
  <link href="https://datatracker.ietf.org/doc/draft-rivest-sexp-13" rel="prev"/>
  <link href="https://dx.doi.org/10.17487/rfc9804" rel="alternate"/>
  <link href="urn:issn:2070-1721" rel="alternate"/>
  <front>
    <title abbrev="SPKI S-Expressions">Simple Public Key Infrastructure (SPKI) S-Expressions</title>
    <seriesInfo name="RFC" value="9804" stream="IETF"/>
    <author fullname="Ronald L. Rivest" initials="R." surname="Rivest">
      <organization showOnFrontPage="true">MIT CSAIL</organization>
      <address>
        <postal>
          <street>32 Vassar Street, Room 32-G692</street>
          <city>Cambridge</city>
          <region>Massachusetts</region>
          <code>02139</code>
          <country>United States of America</country>
        </postal>
        <email>rivest@mit.edu</email>
        <uri>https://www.csail.mit.edu/person/ronald-l-rivest</uri>
      </address>
    </author>
    <author fullname="Donald E. Eastlake 3rd" initials="D." surname="Eastlake 3rd">
      <organization showOnFrontPage="true">Independent</organization>
      <address>
        <postal>
          <street>2386 Panoramic Circle</street>
          <city>Apopka</city>
          <region>Florida</region>
          <code>32703</code>
          <country>United States of America</country>
        </postal>
        <phone>+1-508-333-2270</phone>
        <email>d3e3e3@gmail.com</email>
      </address>
    </author>
    <date month="06" year="2025"/>
    <area>ART</area>
    <keyword>Sexp</keyword>
    <keyword>Sexpression</keyword>
    <keyword>S-expression</keyword>
    <abstract pn="section-abstract">
      <t indent="0" pn="section-abstract-1">This memo specifies the data structure representation that was
  devised to support Simple Public Key Infrastructure (SPKI)
  certificates, as detailed in RFC 2692, with the intent that it be more widely
  applicable. It has been and is being used elsewhere. There are
  multiple implementations in a variety of programming languages. Uses
  of this representation are referred to in this document as
  "S-expressions".  This memo makes precise the encodings of these
  SPKI S-expressions: It gives a "canonical form" for them, describes
  two "transport" representations, and also describes an "advanced"
  format for display to people.</t>
    </abstract>
    <boilerplate>
      <section anchor="status-of-memo" numbered="false" removeInRFC="false" toc="exclude" pn="section-boilerplate.1">
        <name slugifiedName="name-status-of-this-memo">Status of This Memo</name>
        <t indent="0" pn="section-boilerplate.1-1">
            This document is not an Internet Standards Track specification; it is
            published for informational purposes.  
        </t>
        <t indent="0" pn="section-boilerplate.1-2">
            This document is a product of the Internet Engineering Task Force
            (IETF).  It represents the consensus of the IETF community.  It has
            received public review and has been approved for publication by the
            Internet Engineering Steering Group (IESG).  Not all documents
            approved by the IESG are candidates for any level of Internet
            Standard; see Section 2 of RFC 7841. 
        </t>
        <t indent="0" pn="section-boilerplate.1-3">
            Information about the current status of this document, any
            errata, and how to provide feedback on it may be obtained at
            <eref target="https://www.rfc-editor.org/info/rfc9804" brackets="none"/>.
        </t>
      </section>
      <section anchor="copyright" numbered="false" removeInRFC="false" toc="exclude" pn="section-boilerplate.2">
        <name slugifiedName="name-copyright-notice">Copyright Notice</name>
        <t indent="0" pn="section-boilerplate.2-1">
            Copyright (c) 2025 IETF Trust and the persons identified as the
            document authors. All rights reserved.
        </t>
        <t indent="0" pn="section-boilerplate.2-2">
            This document is subject to BCP 78 and the IETF Trust's Legal
            Provisions Relating to IETF Documents
            (<eref target="https://trustee.ietf.org/license-info" brackets="none"/>) 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.
        </t>
      </section>
    </boilerplate>
    <toc>
      <section anchor="toc" numbered="false" removeInRFC="false" toc="exclude" pn="section-toc.1">
        <name slugifiedName="name-table-of-contents">Table of Contents</name>
        <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1">
          <li pn="section-toc.1-1.1">
            <t indent="0" pn="section-toc.1-1.1.1"><xref derivedContent="1" format="counter" sectionFormat="of" target="section-1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-introduction">Introduction</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.1.2">
              <li pn="section-toc.1-1.1.2.1">
                <t indent="0" keepWithNext="true" pn="section-toc.1-1.1.2.1.1"><xref derivedContent="1.1" format="counter" sectionFormat="of" target="section-1.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-uses-of-s-expressions">Uses of S-Expressions</xref></t>
              </li>
              <li pn="section-toc.1-1.1.2.2">
                <t indent="0" keepWithNext="true" pn="section-toc.1-1.1.2.2.1"><xref derivedContent="1.2" format="counter" sectionFormat="of" target="section-1.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-formalization">Formalization</xref></t>
              </li>
              <li pn="section-toc.1-1.1.2.3">
                <t indent="0" keepWithNext="true" pn="section-toc.1-1.1.2.3.1"><xref derivedContent="1.3" format="counter" sectionFormat="of" target="section-1.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-historical-note">Historical Note</xref></t>
              </li>
              <li pn="section-toc.1-1.1.2.4">
                <t indent="0" pn="section-toc.1-1.1.2.4.1"><xref derivedContent="1.4" format="counter" sectionFormat="of" target="section-1.4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-conventions-used-in-this-do">Conventions Used in This Document</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.2">
            <t indent="0" pn="section-toc.1-1.2.1"><xref derivedContent="2" format="counter" sectionFormat="of" target="section-2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-s-expressions-informal-intr">S-expressions -- Informal Introduction</xref></t>
          </li>
          <li pn="section-toc.1-1.3">
            <t indent="0" pn="section-toc.1-1.3.1"><xref derivedContent="3" format="counter" sectionFormat="of" target="section-3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-character-set">Character Set</xref></t>
          </li>
          <li pn="section-toc.1-1.4">
            <t indent="0" pn="section-toc.1-1.4.1"><xref derivedContent="4" format="counter" sectionFormat="of" target="section-4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-octet-string-representation">Octet-String Representation Types</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.4.2">
              <li pn="section-toc.1-1.4.2.1">
                <t indent="0" pn="section-toc.1-1.4.2.1.1"><xref derivedContent="4.1" format="counter" sectionFormat="of" target="section-4.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-verbatim-representation">Verbatim Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.2">
                <t indent="0" pn="section-toc.1-1.4.2.2.1"><xref derivedContent="4.2" format="counter" sectionFormat="of" target="section-4.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-quoted-string-representatio">Quoted-String Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.3">
                <t indent="0" pn="section-toc.1-1.4.2.3.1"><xref derivedContent="4.3" format="counter" sectionFormat="of" target="section-4.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-token-representation">Token Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.4">
                <t indent="0" pn="section-toc.1-1.4.2.4.1"><xref derivedContent="4.4" format="counter" sectionFormat="of" target="section-4.4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-hexadecimal-representation">Hexadecimal Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.5">
                <t indent="0" pn="section-toc.1-1.4.2.5.1"><xref derivedContent="4.5" format="counter" sectionFormat="of" target="section-4.5"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-base-64-representation-of-o">Base-64 Representation of Octet-Strings</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.6">
                <t indent="0" pn="section-toc.1-1.4.2.6.1"><xref derivedContent="4.6" format="counter" sectionFormat="of" target="section-4.6"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-display-hints-and-internati">Display-Hints and Internationalization</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.7">
                <t indent="0" pn="section-toc.1-1.4.2.7.1"><xref derivedContent="4.7" format="counter" sectionFormat="of" target="section-4.7"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-comparison-of-octet-strings">Comparison of Octet-Strings</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.5">
            <t indent="0" pn="section-toc.1-1.5.1"><xref derivedContent="5" format="counter" sectionFormat="of" target="section-5"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-lists">Lists</xref></t>
          </li>
          <li pn="section-toc.1-1.6">
            <t indent="0" pn="section-toc.1-1.6.1"><xref derivedContent="6" format="counter" sectionFormat="of" target="section-6"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-s-expression-representation">S-Expression Representation Types</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.6.2">
              <li pn="section-toc.1-1.6.2.1">
                <t indent="0" pn="section-toc.1-1.6.2.1.1"><xref derivedContent="6.1" format="counter" sectionFormat="of" target="section-6.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-base-64-representation-of-s">Base-64 Representation of S-Expressions</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.2">
                <t indent="0" pn="section-toc.1-1.6.2.2.1"><xref derivedContent="6.2" format="counter" sectionFormat="of" target="section-6.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-canonical-representation">Canonical Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.3">
                <t indent="0" pn="section-toc.1-1.6.2.3.1"><xref derivedContent="6.3" format="counter" sectionFormat="of" target="section-6.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-basic-transport-representat">Basic Transport Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.4">
                <t indent="0" pn="section-toc.1-1.6.2.4.1"><xref derivedContent="6.4" format="counter" sectionFormat="of" target="section-6.4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-advanced-transport-represen">Advanced Transport Representation</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.7">
            <t indent="0" pn="section-toc.1-1.7.1"><xref derivedContent="7" format="counter" sectionFormat="of" target="section-7"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-abnf-of-the-syntax">ABNF of the Syntax</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.7.2">
              <li pn="section-toc.1-1.7.2.1">
                <t indent="0" pn="section-toc.1-1.7.2.1.1"><xref derivedContent="7.1" format="counter" sectionFormat="of" target="section-7.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-abnf-for-advanced-transport">ABNF for Advanced Transport</xref></t>
              </li>
              <li pn="section-toc.1-1.7.2.2">
                <t indent="0" pn="section-toc.1-1.7.2.2.1"><xref derivedContent="7.2" format="counter" sectionFormat="of" target="section-7.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-abnf-for-canonical">ABNF for Canonical</xref></t>
              </li>
              <li pn="section-toc.1-1.7.2.3">
                <t indent="0" pn="section-toc.1-1.7.2.3.1"><xref derivedContent="7.3" format="counter" sectionFormat="of" target="section-7.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-abnf-for-basic-transport">ABNF for Basic Transport</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.8">
            <t indent="0" pn="section-toc.1-1.8.1"><xref derivedContent="8" format="counter" sectionFormat="of" target="section-8"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-restricted-s-expressions">Restricted S-Expressions</xref></t>
          </li>
          <li pn="section-toc.1-1.9">
            <t indent="0" pn="section-toc.1-1.9.1"><xref derivedContent="9" format="counter" sectionFormat="of" target="section-9"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-in-memory-representations">In-Memory Representations</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.9.2">
              <li pn="section-toc.1-1.9.2.1">
                <t indent="0" pn="section-toc.1-1.9.2.1.1"><xref derivedContent="9.1" format="counter" sectionFormat="of" target="section-9.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-list-structure-memory-repre">List-Structure Memory Representation</xref></t>
              </li>
              <li pn="section-toc.1-1.9.2.2">
                <t indent="0" pn="section-toc.1-1.9.2.2.1"><xref derivedContent="9.2" format="counter" sectionFormat="of" target="section-9.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-array-layout-memory-represe">Array-Layout Memory Representation</xref></t>
                <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.9.2.2.2">
                  <li pn="section-toc.1-1.9.2.2.2.1">
                    <t indent="0" pn="section-toc.1-1.9.2.2.2.1.1"><xref derivedContent="9.2.1" format="counter" sectionFormat="of" target="section-9.2.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-octet-string">Octet-String</xref></t>
                  </li>
                  <li pn="section-toc.1-1.9.2.2.2.2">
                    <t indent="0" pn="section-toc.1-1.9.2.2.2.2.1"><xref derivedContent="9.2.2" format="counter" sectionFormat="of" target="section-9.2.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-octet-string-with-display-h">Octet-String with Display-Hint</xref></t>
                  </li>
                  <li pn="section-toc.1-1.9.2.2.2.3">
                    <t indent="0" pn="section-toc.1-1.9.2.2.2.3.1"><xref derivedContent="9.2.3" format="counter" sectionFormat="of" target="section-9.2.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-list">List</xref></t>
                  </li>
                </ul>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.10">
            <t indent="0" pn="section-toc.1-1.10.1"><xref derivedContent="10" format="counter" sectionFormat="of" target="section-10"/>. <xref derivedContent="" format="title" sectionFormat="of" target="name-security-considerations">Security Considerations</xref></t>
          </li>
          <li pn="section-toc.1-1.11">
            <t indent="0" pn="section-toc.1-1.11.1"><xref derivedContent="11" format="counter" sectionFormat="of" target="section-11"/>. <xref derivedContent="" format="title" sectionFormat="of" target="name-iana-considerations">IANA Considerations</xref></t>
          </li>
          <li pn="section-toc.1-1.12">
            <t indent="0" pn="section-toc.1-1.12.1"><xref derivedContent="12" format="counter" sectionFormat="of" target="section-12"/>. <xref derivedContent="" format="title" sectionFormat="of" target="name-references">References</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.12.2">
              <li pn="section-toc.1-1.12.2.1">
                <t indent="0" pn="section-toc.1-1.12.2.1.1"><xref derivedContent="12.1" format="counter" sectionFormat="of" target="section-12.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-normative-references">Normative References</xref></t>
              </li>
              <li pn="section-toc.1-1.12.2.2">
                <t indent="0" pn="section-toc.1-1.12.2.2.1"><xref derivedContent="12.2" format="counter" sectionFormat="of" target="section-12.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-informative-references">Informative References</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.13">
            <t indent="0" pn="section-toc.1-1.13.1"><xref derivedContent="Appendix A" format="default" sectionFormat="of" target="section-appendix.a"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-implementations">Implementations</xref></t>
          </li>
          <li pn="section-toc.1-1.14">
            <t indent="0" pn="section-toc.1-1.14.1"><xref derivedContent="" format="none" sectionFormat="of" target="section-appendix.b"/><xref derivedContent="" format="title" sectionFormat="of" target="name-acknowledgements">Acknowledgements</xref></t>
          </li>
          <li pn="section-toc.1-1.15">
            <t indent="0" pn="section-toc.1-1.15.1"><xref derivedContent="" format="none" sectionFormat="of" target="section-appendix.c"/><xref derivedContent="" format="title" sectionFormat="of" target="name-contributors">Contributors</xref></t>
          </li>
          <li pn="section-toc.1-1.16">
            <t indent="0" pn="section-toc.1-1.16.1"><xref derivedContent="" format="none" sectionFormat="of" target="section-appendix.d"/><xref derivedContent="" format="title" sectionFormat="of" target="name-authors-addresses">Authors' Addresses</xref></t>
          </li>
        </ul>
      </section>
    </toc>
  </front>
  <middle>
    <section numbered="true" removeInRFC="false" toc="include" pn="section-1">
      <name slugifiedName="name-introduction">Introduction</name>
      <t indent="0" pn="section-1-1">This memo specifies the data structure representation that was
  devised to support Simple Public Key Infrastructure (SPKI) certificates <xref target="RFC2692" format="default" sectionFormat="of" derivedContent="RFC2692"/>, with the intent that it be more
  widely applicable (see <xref target="history" format="default" sectionFormat="of" derivedContent="Section 1.3"/>, "Historical Note"). It is
  suitable for representing arbitrary, complex data structures and has
  been and is being used elsewhere. Uses of this representation herein
  are referred to as "S-expressions".</t>
      <t indent="0" pn="section-1-2">This memo makes precise the encodings of these SPKI
  S-expressions: It gives a "canonical form" for them, describes two
  "transport" representations, and also describes an "advanced" format
  for display to people. There are multiple implementations of
  S-expressions in a variety of programming languages including Python,
  Ruby, and C (see <xref target="Code" format="default" sectionFormat="of" derivedContent="Appendix A"/>).</t>
      <t indent="0" pn="section-1-3">These S-expressions are either octet-strings or
  lists of simpler S-expressions.  Here is a sample S-expression:</t>
      <sourcecode markers="false" pn="section-1-4">
    (snicker "abc" (#03# |YWJj|))
</sourcecode>
      <t indent="0" pn="section-1-5">It is a list of length three containing the following:</t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-1-6">
        <li pn="section-1-6.1">the octet-string "snicker"</li>
        <li pn="section-1-6.2">the octet-string "abc"</li>
        <li pn="section-1-6.3">a sub-list containing two elements: The hexadecimal constant
  #03# (which represents a one-octet-long octet-string with the 
  value of that octet being 0x03) and the base-64 constant |YWJj| (which
  represents the same octet-string as "abc")</li>
      </ul>
      <t indent="0" pn="section-1-7">This document specifies how to construct and use these
S-expressions.</t>
      <t indent="0" pn="section-1-8">The design goals for S-expressions were as follows:</t>
      <ul spacing="normal" bare="false" empty="false" indent="3" pn="section-1-9">
        <li pn="section-1-9.1">Generality: S-expressions should be good at representing
arbitrary data.</li>
        <li pn="section-1-9.2">Readability: It should be easy for someone to examine and
understand the structure of an S-expression.</li>
        <li pn="section-1-9.3">Economy: S-expressions should represent data
compactly.</li>
        <li pn="section-1-9.4">Transportability: S-expressions should be easy to transport
over communication media (such as email) that are known to be less
than perfect.</li>
        <li pn="section-1-9.5">Flexibility: S-expressions should make it relatively
simple to modify and extend data structures.</li>
        <li pn="section-1-9.6">Canonicalization: It should be easy to produce a unique
"canonical" form of an S-expression, for digital signature
purposes.</li>
        <li pn="section-1-9.7">Efficiency: S-expressions should admit in-memory
representations that allow efficient processing.</li>
      </ul>
      <t indent="0" pn="section-1-10">For implementors of new applications and protocols other
technologies also worthy of consideration include the following: XML <xref target="XML" format="default" sectionFormat="of" derivedContent="XML"/>, CBOR <xref target="RFC8949" format="default" sectionFormat="of" derivedContent="RFC8949"/>, and JSON <xref target="RFC8259" format="default" sectionFormat="of" derivedContent="RFC8259"/>.</t>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-1.1">
        <name slugifiedName="name-uses-of-s-expressions">Uses of S-Expressions</name>
        <t indent="0" pn="section-1.1-1">The S-expressions specified herein are in active use today between
GnuPG <xref target="GnuPG" format="default" sectionFormat="of" derivedContent="GnuPG"/> and Ribose's RNP <xref target="Ribose" format="default" sectionFormat="of" derivedContent="Ribose"/>.
Ribose has implemented C++ software to compose and parse these
S-expressions <xref target="RNPGP_SEXPP" format="default" sectionFormat="of" derivedContent="RNPGP_SEXPP"/>.  The GNU software is the Libgcrypt library <xref target="Libgcrypt" format="default" sectionFormat="of" derivedContent="Libgcrypt"/>, and there are other implementations (see
<xref target="Code" format="default" sectionFormat="of" derivedContent="Appendix A"/>).</t>
        <t indent="0" pn="section-1.1-2">S-expressions are also used or referenced in the following RFCs:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-1.1-3">
          <li pn="section-1.1-3.1">
            <xref target="RFC2693" format="default" sectionFormat="of" derivedContent="RFC2693"/> for <xref target="SPKI" format="default" sectionFormat="of" derivedContent="SPKI"/></li>
          <li pn="section-1.1-3.2">
            <xref target="RFC3275" format="default" sectionFormat="of" derivedContent="RFC3275"/> XML-Signature Syntax and
  Processing</li>
        </ul>
        <t indent="0" pn="section-1.1-4">In addition, S-expressions are the inspiration for the encodings in
other protocols. For example, <xref target="RFC3259" format="default" sectionFormat="of" derivedContent="RFC3259"/> or <xref section="6" target="I-D.bormann-cbor-cddl-freezer" format="default" sectionFormat="of" derivedLink="https://datatracker.ietf.org/doc/html/draft-bormann-cbor-cddl-freezer-15#section-6" derivedContent="CDDL-freezer"/>.</t>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-1.2">
        <name slugifiedName="name-formalization">Formalization</name>
        <t indent="0" pn="section-1.2-1"><xref target="I-D.petithuguenin-ufmrg-formal-sexpr" format="default" sectionFormat="of" derivedContent="Formal"/> is an Internet-Draft that shows
  a formal model of SPKI S-expressions and formally demonstrates
  that the examples and ABNF in this document are correct.</t>
      </section>
      <section anchor="history" numbered="true" removeInRFC="false" toc="include" pn="section-1.3">
        <name slugifiedName="name-historical-note">Historical Note</name>
        <t indent="0" pn="section-1.3-1">The S-expressions described here were originally developed for
"SDSI" (the Simple Distributed Security Infrastructure by Lampson and
Rivest <xref target="SDSI" format="default" sectionFormat="of" derivedContent="SDSI"/>) in 1996, although their origins date
back to McCarthy's <xref target="LISP" format="default" sectionFormat="of" derivedContent="LISP"/> programming language.  They
were further refined and improved during the merger of SDSI and SPKI
<xref target="SPKI" format="default" sectionFormat="of" derivedContent="SPKI"/> <xref target="RFC2692" format="default" sectionFormat="of" derivedContent="RFC2692"/> <xref target="RFC2693" format="default" sectionFormat="of" derivedContent="RFC2693"/> during the first half of 1997.  S-expressions are
more readable and flexible than Bernstein's "netstrings" <xref target="BERN" format="default" sectionFormat="of" derivedContent="BERN"/>, which were developed contemporaneously.</t>
        <aside pn="section-1.3-2">
          <t indent="0" pn="section-1.3-2.1">Although a specification was 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. This document is a clarified and
  modernized version of that document.</t>
        </aside>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-1.4">
        <name slugifiedName="name-conventions-used-in-this-do">Conventions Used in This Document</name>
        <t indent="0" pn="section-1.4-1">
    The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQUIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
    "<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to be interpreted as
    described in BCP 14 <xref target="RFC2119" format="default" sectionFormat="of" derivedContent="RFC2119"/> <xref target="RFC8174" format="default" sectionFormat="of" derivedContent="RFC8174"/> 
    when, and only when, they appear in all capitals, as shown here.
        </t>
      </section>
    </section>
    <section anchor="Sec2" numbered="true" removeInRFC="false" toc="include" pn="section-2">
      <name slugifiedName="name-s-expressions-informal-intr">S-expressions -- Informal Introduction</name>
      <t indent="0" pn="section-2-1">Informally, an S-expression is either:</t>
      <ul spacing="compact" bare="false" empty="false" indent="3" pn="section-2-2">
        <li pn="section-2-2.1">an octet-string, or</li>
        <li pn="section-2-2.2">a finite list of simpler S-expressions.</li>
      </ul>
      <t indent="0" pn="section-2-3">An octet-string is a finite sequence of eight-bit octets. An
octet-string may be zero length.  There may be many different but
equivalent ways of representing an octet-string</t>
      <sourcecode markers="false" pn="section-2-4">
    abc         -- as a token
    "abc"       -- as a quoted string
    #616263#    -- as a hexadecimal string
    3:abc       -- as a length-prefixed "verbatim" encoding
    |YWJj|      -- as a base-64 encoding of the octet-string "abc"
</sourcecode>
      <t indent="0" pn="section-2-5">The above encodings are all equivalent in that they all denote the
same octet-string. Details of these encodings are given below, and how
to give a "display type" to a simple-string is also described in <xref target="DisplayHint" format="default" sectionFormat="of" derivedContent="Section 4.6"/>.</t>
      <t indent="0" pn="section-2-6">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:</t>
      <sourcecode markers="false" pn="section-2-7">
    (abc (de #6667#) "ghi jkl")
</sourcecode>
      <t indent="0" pn="section-2-8">As can be seen, 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 these S-expressions
aim to handle:</t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-2-9">
        <li pn="section-2-9.1">a "transport" or "basic" encoding for transporting the
  S-expression between computers</li>
        <li pn="section-2-9.2">a "canonical" encoding, used when signing the
  S-expression</li>
        <li pn="section-2-9.3">an "advanced" encoding used for input/output to people</li>
        <li pn="section-2-9.4">an "in-memory" encoding used for processing the S-expression
  in the computer</li>
      </ul>
      <t indent="0" pn="section-2-10">In this document, related encoding techniques for each of these
uses are provided.</t>
    </section>
    <section anchor="Sec3" numbered="true" removeInRFC="false" toc="include" pn="section-3">
      <name slugifiedName="name-character-set">Character Set</name>
      <t indent="0" pn="section-3-1">This document specifies encodings of S-expressions.  Except when
giving "verbatim" encodings, the character set used is limited to the
following characters in ASCII <xref target="RFC0020" format="default" sectionFormat="of" derivedContent="RFC0020"/>:</t>
      <t indent="0" pn="section-3-2">Alphabetic:</t>
      <sourcecode markers="false" pn="section-3-3">
    A B ... Z a b ... z
</sourcecode>
      <t indent="0" pn="section-3-4">Numeric:</t>
      <sourcecode markers="false" pn="section-3-5">
    0 1 ... 9
</sourcecode>
      <t indent="0" pn="section-3-6">Whitespace:</t>
      <sourcecode markers="false" pn="section-3-7">
    space, horizontal tab, vertical tab, form-feed
    carriage-return, line-feed
</sourcecode>
      <t indent="0" pn="section-3-8">The following graphics characters, which are called
  "pseudo-alphabetic" in this document:</t>
      <sourcecode markers="false" pn="section-3-9">
    -  hyphen or minus
    .  period
    /  slash
    _  underscore
    :  colon
    *  asterisk
    +  plus
    =  equal
</sourcecode>
      <t indent="0" pn="section-3-10">The following graphics characters, which are "reserved
  punctuation":</t>
      <sourcecode markers="false" pn="section-3-11">
    (  left parenthesis
    )  right parenthesis
    [  left bracket
    ]  right bracket
    {  left brace
    }  right brace
    |  vertical bar
    #  number sign
    "  double quote
    &amp;  ampersand
    \  backslash
</sourcecode>
      <t indent="0" pn="section-3-12">The following characters are unused and unavailable, except in
        "verbatim" and "quoted string" encodings:</t>
      <sourcecode markers="false" pn="section-3-13">
    !  exclamation point
    %  percent
    ^  circumflex
    ~  tilde
    ;  semicolon
    '  single-quote (apostrophe)
    ,  comma
    &lt;  less than
    &gt;  greater than
    ?  question mark
</sourcecode>
    </section>
    <section anchor="Sec4" numbered="true" removeInRFC="false" toc="include" pn="section-4">
      <name slugifiedName="name-octet-string-representation">Octet-String Representation Types</name>
      <t indent="0" pn="section-4-1">This section describes in detail the ways in which an octet-string may
be represented.</t>
      <t indent="0" pn="section-4-2">Recall that an octet-string is any finite sequence of octets and
that an octet-string may have length zero.</t>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-4.1">
        <name slugifiedName="name-verbatim-representation">Verbatim Representation</name>
        <t indent="0" pn="section-4.1-1">A verbatim encoding of an octet-string consists of three parts:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-4.1-2">
          <li pn="section-4.1-2.1">the length (number of octets) of the octet-string, given in
  decimal, most significant digit first, with no leading zeros</li>
          <li pn="section-4.1-2.2">a colon ":"</li>
          <li pn="section-4.1-2.3">the octet-string itself, verbatim</li>
        </ul>
        <t indent="0" pn="section-4.1-3">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.</t>
        <t indent="0" pn="section-4.1-4">Here are some sample verbatim encodings:</t>
        <sourcecode markers="false" pn="section-4.1-5">
    3:abc
    7:subject
    4:::":
    12:hello world!
    10:abcdefghij
    0:
</sourcecode>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-4.2">
        <name slugifiedName="name-quoted-string-representatio">Quoted-String Representation</name>
        <t indent="0" pn="section-4.2-1">The quoted-string representation of an octet-string consists of:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-4.2-2">
          <li pn="section-4.2-2.1">an optional decimal length field</li>
          <li pn="section-4.2-2.2">an initial double-quote (")</li>
          <li pn="section-4.2-2.3">the octet-string with the C programming language <xref target="C88" format="default" sectionFormat="of" derivedContent="C88"/> escape conventions (\n, etc.)</li>
          <li pn="section-4.2-2.4">a final double-quote (")</li>
        </ul>
        <t indent="0" pn="section-4.2-3">The specified length is the length of the resulting string after
any backslash escape sequences have been converted to the octet value
they denote.  The string does not have any "terminating NULL" that
<xref target="C88" format="default" sectionFormat="of" derivedContent="C88"/> includes, and the length does not count such an
octet.</t>
        <t indent="0" pn="section-4.2-4">The length is optional.</t>
        <t indent="0" pn="section-4.2-5">The escape conventions within the quoted string are as follows
(these follow the C programming language <xref target="C88" format="default" sectionFormat="of" derivedContent="C88"/> 
conventions, with an extension for ignoring line terminators of just
CR, LF, CRLF, or LFCR and more restrictive octal and hexadecimal value
formats):</t>
        <sourcecode markers="false" pn="section-4.2-6">
    \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)
    \&lt;carriage-return&gt;   -- causes carriage-return to be ignored.
    \&lt;line-feed&gt;         -- causes line-feed to be ignored.
    \&lt;carriage-return&gt;&lt;line-feed&gt;   -- causes
              CRLF to be ignored.
    \&lt;line-feed&gt;&lt;carriage-return&gt;   -- causes
              LFCR to be ignored.
</sourcecode>
        <t indent="0" pn="section-4.2-7">Here are some examples of quoted-string encodings:</t>
        <sourcecode markers="false" pn="section-4.2-8">
    "subject"
    "hi there"
    7"subject"
    "\xFE is the same octet as \376"
    3"\n\n\n"
    "This has\n two lines."
    "This has \
     one line."
    ""
</sourcecode>
      </section>
      <section anchor="token" numbered="true" removeInRFC="false" toc="include" pn="section-4.3">
        <name slugifiedName="name-token-representation">Token Representation</name>
        <t indent="0" pn="section-4.3-1">An octet-string that meets the following conditions may be given
directly as a "token":</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-4.3-2">
          <li pn="section-4.3-2.1">it does not begin with a digit;</li>
          <li pn="section-4.3-2.2">
            <t indent="0" pn="section-4.3-2.2.1">it contains only characters that are: alphabetic (upper or lower
  case), numeric, or one of the following eight "pseudo-alphabetic" punctuation
  marks:</t>
            <artwork align="left" pn="section-4.3-2.2.2">
-  .  /  _  :  *  +  =
</artwork>
          </li>
          <li pn="section-4.3-2.3">it is length 1 or greater.</li>
        </ul>
        <t indent="0" pn="section-4.3-3">Note: Upper and lower case are not equivalent.
A token may begin with punctuation, including ":".</t>
        <t indent="0" pn="section-4.3-4">Here are some examples of token representations:</t>
        <sourcecode markers="false" pn="section-4.3-5">
    subject
    not-before
    :=..
    class-of-1997
    //example.net/names/smith
    *
</sourcecode>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-4.4">
        <name slugifiedName="name-hexadecimal-representation">Hexadecimal Representation</name>
        <t indent="0" pn="section-4.4-1">An octet-string may be represented with a hexadecimal encoding
consisting of:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-4.4-2">
          <li pn="section-4.4-2.1">an (optional) decimal length of the octet-string</li>
          <li pn="section-4.4-2.2">a  sharp-sign "#"</li>
          <li pn="section-4.4-2.3">a hexadecimal encoding of the octet-string, with each octet
  represented with two hexadecimal digits, most significant digit
  first. There <bcp14>MUST</bcp14> be an even number of such digits.</li>
          <li pn="section-4.4-2.4">a final sharp-sign "#"</li>
        </ul>
        <t indent="0" pn="section-4.4-3">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.</t>
        <t indent="0" pn="section-4.4-4">Here are some examples of hexadecimal encodings:</t>
        <sourcecode markers="false" pn="section-4.4-5">
    #616263#    -- represents "abc"
    3#616263#   -- also represents "abc"
    # 616
      263 #     -- also represents "abc"
    ##          -- represents the zero-length string
</sourcecode>
      </section>
      <section anchor="base64string" numbered="true" removeInRFC="false" toc="include" pn="section-4.5">
        <name slugifiedName="name-base-64-representation-of-o">Base-64 Representation of Octet-Strings</name>
        <t indent="0" pn="section-4.5-1">An octet-string may be represented in a base-64 encoding <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> consisting of:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-4.5-2">
          <li pn="section-4.5-2.1">an (optional) decimal length of the octet-string</li>
          <li pn="section-4.5-2.2">a vertical bar "|"</li>
          <li pn="section-4.5-2.3">the base-64 <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> encoding of the
octet-string.</li>
          <li pn="section-4.5-2.4">a final vertical bar "|"</li>
        </ul>
        <t indent="0" pn="section-4.5-3">Base-64 encoding produces four characters of output for each three
octets of input.
  When the length of the input is divided by three:</t>
        <ul spacing="compact" bare="false" empty="false" indent="3" pn="section-4.5-4">
          <li pn="section-4.5-4.1">if the remainder is one, it produces an output block of length four
     ending in two equals signs.</li>
          <li pn="section-4.5-4.2">if the remainder is two, it produces an output block of length four
     ending in one equals sign.</li>
        </ul>
        <t indent="0" pn="section-4.5-5">These equals signs
<bcp14>MUST</bcp14> be included on output, but input routines <bcp14>MAY</bcp14> accept inputs where
one or two equals signs are dropped.</t>
        <t indent="0" pn="section-4.5-6">Whitespace inserted in the midst of the base-64 encoding is
ignored.  It is an error to have characters other than whitespace and
base-64 characters.</t>
        <t indent="0" pn="section-4.5-7">Here are some examples of base-64 encodings:</t>
        <sourcecode markers="false" pn="section-4.5-8">
    |YWJj|       -- represents "abc"
    | Y W
      J j |      -- also represents "abc"
    3|YWJj|      -- also represents "abc"
    |YWJjZA==|   -- represents "abcd"
    |YWJjZA|     -- also represents "abcd"
    ||           -- represents the zero-length string
</sourcecode>
        <t indent="0" pn="section-4.5-9">Note the difference between this base-64 encoding of an
octet-string using vertical bars ("| |") and the base-64 encoding of
an S-expression using curly braces ("{ }") in <xref target="base64sexp" format="default" sectionFormat="of" derivedContent="Section 6.1"/>.</t>
      </section>
      <section anchor="DisplayHint" numbered="true" removeInRFC="false" toc="include" pn="section-4.6">
        <name slugifiedName="name-display-hints-and-internati">Display-Hints and Internationalization</name>
        <t indent="0" pn="section-4.6-1">An octet-string can contain any type of data representable by a
finite octet-string, e.g., text, a fixed or variable-length
integer, or an image. Normally, the application producing and/or consuming
S-expressions will understand their structure, the data type, and
the encoding of the octet-strings within the S-expressions used by that
application. If the octet-string consists of text, use of UTF-8
encoding is <bcp14>RECOMMENDED</bcp14> <xref target="RFC2130" format="default" sectionFormat="of" derivedContent="RFC2130"/> <xref target="RFC3629" format="default" sectionFormat="of" derivedContent="RFC3629"/>.</t>
        <t indent="0" pn="section-4.6-2">The purpose of a display-hint is to provide information on how to
display an octet-string to a user.  It has no other function.  Many of
the media types <xref target="RFC2046" format="default" sectionFormat="of" derivedContent="RFC2046"/> work here.</t>
        <t indent="0" pn="section-4.6-3">A display-hint is an octet-string representation surrounded by
square brackets.  There may be whitespace separating the display hint
octet-string from the surrounding brackets.  Any of the legal
octet-string representations may be used for the display-hint string,
but a display-hint may not be applied to a display-hint string -- that
is, display-hints may not be nested.</t>
        <t indent="0" pn="section-4.6-4">A display-hint that can be used for UTF-8-encoded text is shown in
the following example where the octet-string represents "böb☺", that is, "bob" with an umlaut over the "o", followed by the Unicode <xref target="Unicode" format="default" sectionFormat="of" derivedContent="Unicode"/> character WHITE SMILING FACE (U+263A).</t>
        <sourcecode markers="false" pn="section-4.6-5">
    ["text/plain; charset=utf-8"]"b\xC3\xB7b\xE2\x98\xBA"
</sourcecode>
        <t indent="0" pn="section-4.6-6">Every octet-string representation is or is not preceded by a single
display-hint. There may be whitespace between
the close square bracket and the octet-string to which the hint
applies.</t>
        <t indent="0" pn="section-4.6-7">Here are some other examples of display-hints:</t>
        <sourcecode markers="false" pn="section-4.6-8">
    [image/gif]
    [charset=unicode-1-1]
    [  text/richtext  ]
    ["text/plain; charset=iso-8859-1"]
    [application/postscript]
    [audio/basic]
    ["http://example.com/display-types/funky.html"]
</sourcecode>
        <t indent="0" pn="section-4.6-9">An octet-string that has no display-hint may be considered to have
a media type <xref target="RFC2046" format="default" sectionFormat="of" derivedContent="RFC2046"/> specified by the application or
use. In the absence of such a specification, the default is as
follows:</t>
        <sourcecode markers="false" pn="section-4.6-10">
    [application/octet-stream]
</sourcecode>
        <t indent="0" pn="section-4.6-11">When an S-expression is being encoded in one of the representations
described in <xref target="Represent" format="default" sectionFormat="of" derivedContent="Section 6"/>, any display-hint present is
included.  If a display-hint is the default, it is not suppressed nor
is the default display-hint included in the representation for an
octet-string without a display-hint.</t>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-4.7">
        <name slugifiedName="name-comparison-of-octet-strings">Comparison of Octet-Strings</name>
        <t indent="0" pn="section-4.7-1">It is <bcp14>RECOMMENDED</bcp14> that two octet-strings be considered equivalent
for most computational and algorithmic purposes if and only if they
have the same display-hint and the same data octet-strings. However, a
particular application might need a different criterion. For example,
it might ignore the display hint on comparisons.</t>
        <t indent="0" pn="section-4.7-2">Note that octet-strings are "case-sensitive"; the octet-string
"abc" is not equal to the octet-string "ABC".</t>
        <t indent="0" pn="section-4.7-3">An octet-string without a display-hint may be compared to another
octet-string (with or without a display hint) by considering it as an
octet-string with the default display-hint specified for the
applications or, in the absence of such specification, the general
default display-hint specified in <xref target="DisplayHint" format="default" sectionFormat="of" derivedContent="Section 4.6"/> .</t>
      </section>
    </section>
    <section anchor="Sec5" numbered="true" removeInRFC="false" toc="include" pn="section-5">
      <name slugifiedName="name-lists">Lists</name>
      <t indent="0" pn="section-5-1">Just as with octet-strings, there are variations in representing 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. To be precise, an octet-string represented as a token (<xref target="token" format="default" sectionFormat="of" derivedContent="Section 4.3"/>) <bcp14>MUST</bcp14> be separated by whitespace from a following
token, verbatim representation, or any of the following if they are
prefixed with a length: quoted-string, hexadecimal, or base-64
representation. Also, whitespace may follow the initial left
parenthesis or precede the final right parenthesis of a list.</t>
      <t indent="0" pn="section-5-2">Here are some examples of encodings of lists:</t>
      <sourcecode markers="false" pn="section-5-3">
    (a bob c)

    ( a ( bob c ) ( ( d e ) ( e f ) )  )

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

    (|ODpFeGFtcGxlIQ==| "1997" murphy 3:XC+)

    ()
</sourcecode>
    </section>
    <section anchor="Represent" numbered="true" removeInRFC="false" toc="include" pn="section-6">
      <name slugifiedName="name-s-expression-representation">S-Expression Representation Types</name>
      <t indent="0" pn="section-6-1">There are three "types" of representation: </t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-6-2">
        <li pn="section-6-2.1">canonical</li>
        <li pn="section-6-2.2">basic transport</li>
        <li pn="section-6-2.3">advanced transport</li>
      </ul>
      <t indent="0" pn="section-6-3">The first two <bcp14>MUST</bcp14> be supported by any implementation; the last is
<bcp14>OPTIONAL</bcp14>. As part of basic representation, the base-64 <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> representation of an S-expression may be used as
described in <xref target="base64sexp" format="default" sectionFormat="of" derivedContent="Section 6.1"/>.</t>
      <section anchor="base64sexp" numbered="true" removeInRFC="false" toc="include" pn="section-6.1">
        <name slugifiedName="name-base-64-representation-of-s">Base-64 Representation of S-Expressions</name>
        <t indent="0" pn="section-6.1-1">An S-expression may be represented in a base-64 encoding <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> consisting of:</t>
        <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-6.1-2">
          <li pn="section-6.1-2.1">an opening curly brace "{"</li>
          <li pn="section-6.1-2.2">the base-64 <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> encoding of the
S-expression</li>
          <li pn="section-6.1-2.3">a final closing curly brace "}"</li>
        </ul>
        <t indent="0" pn="section-6.1-3">Base-64 encoding produces four characters of output for each three
octets of input.  If the length of the input divided by three leaves a
remainder of one or two, it produces an output block of length four
ending in two or one equals signs, respectively.  These equals signs
<bcp14>MUST</bcp14> be included on output, but input routines <bcp14>MAY</bcp14> accept inputs where
one or two equals signs are dropped.</t>
        <t indent="0" pn="section-6.1-4">Whitespace inserted in the midst of the base-64 encoding, after the
opening curly brace, or before the closing curly brace is ignored.  It
is an error to have characters other than whitespace and base-64
characters.</t>
        <t indent="0" pn="section-6.1-5">Note the difference between this base-64 encoding of an
S-expression using curly braces ("{ }") and the base-64 encoding of an
octet-string using vertical bars ("| |") in <xref target="base64string" format="default" sectionFormat="of" derivedContent="Section 4.5"/>.</t>
      </section>
      <section anchor="canonical" numbered="true" removeInRFC="false" toc="include" pn="section-6.2">
        <name slugifiedName="name-canonical-representation">Canonical Representation</name>
        <t indent="0" pn="section-6.2-1">This canonical representation is used for digital signature
purposes and transport over channels not sensitive to specific octet
values.  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, reasonably economical, and unique
for any S-expression. See <xref target="CANON1" format="default" sectionFormat="of" derivedContent="CANON1"/> and <xref target="CANON2" format="default" sectionFormat="of" derivedContent="CANON2"/>.</t>
        <t indent="0" pn="section-6.2-2">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. See also <xref target="ABNFc" format="default" sectionFormat="of" derivedContent="Section 7.2"/>.</t>
        <t indent="0" pn="section-6.2-3">Here are some examples of canonical representations of
S-expressions:</t>
        <sourcecode markers="false" pn="section-6.2-4">
    (6:issuer3:bob)
    (4:icon[12:image/bitmap]9:xxxxxxxxx)
    (7:subject(3:ref5:alice6:mother))
    10:foo)]}&gt;bar
    0:
</sourcecode>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-6.3">
        <name slugifiedName="name-basic-transport-representat">Basic Transport Representation</name>
        <t indent="0" pn="section-6.3-1">There are two forms of the "basic transport" representation:</t>
        <ol indent="adaptive" spacing="normal" start="1" type="1" pn="section-6.3-2">
  <li pn="section-6.3-2.1" derivedCounter="1.">The canonical representation</li>
          <li pn="section-6.3-2.2" derivedCounter="2.">A base-64 <xref target="RFC4648" format="default" sectionFormat="of" derivedContent="RFC4648"/> representation of the
  canonical representation, surrounded by braces (see <xref target="base64sexp" format="default" sectionFormat="of" derivedContent="Section 6.1"/>)</li>
        </ol>
        <t indent="0" pn="section-6.3-3">The basic transport representations (see <xref target="ABNFb" format="default" sectionFormat="of" derivedContent="Section 7.3"/>)
are 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 octets of some
special values, such as an octet of all zero bits (NULL) or an octet
of all one bits (DEL), or if the channel is sensitive to "line length"
such that occasional line terminating whitespace is needed.</t>
        <t indent="0" pn="section-6.3-4">Here are two examples of an S-expression represented in basic
transport mode:</t>
        <sourcecode markers="false" pn="section-6.3-5">
  (1:a1:b1:c)

  {KDE6YTE6YjE
     6Yyk= }
</sourcecode>
        <t indent="0" pn="section-6.3-6">The second example above is the same S-expression as the first
encoded in base-64.</t>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-6.4">
        <name slugifiedName="name-advanced-transport-represen">Advanced Transport Representation</name>
        <t indent="0" pn="section-6.4-1">The "advanced transport" representation is intended to provide more
flexible and readable notations for documentation, design, debugging,
and (in some cases) user interface.</t>
        <t indent="0" pn="section-6.4-2">The advanced transport representation allows all of the
octet-string representation forms described above in <xref target="Sec4" format="default" sectionFormat="of" derivedContent="Section 4"/>: quoted
strings, base-64, hexadecimal, tokens, representations of strings with
omitted lengths, and so on. See <xref target="ABNFa" format="default" sectionFormat="of" derivedContent="Section 7.1"/>.</t>
      </section>
    </section>
    <section anchor="ABNF" numbered="true" removeInRFC="false" toc="include" pn="section-7">
      <name slugifiedName="name-abnf-of-the-syntax">ABNF of the Syntax</name>
      <t indent="0" pn="section-7-1">ABNF is the Augmented Backus-Naur Form for syntax specifications as
defined in <xref target="RFC5234" format="default" sectionFormat="of" derivedContent="RFC5234"/>. The ABNF for advanced
representation of S-expressions is given first, and the basic and
canonical forms are derived therefrom.  The rule names below in all
capital letters are defined in <xref section="B.1" target="RFC5234" format="default" sectionFormat="of" derivedLink="https://rfc-editor.org/rfc/rfc5234#appendix-B.1" derivedContent="RFC5234"/>.</t>
      <section anchor="ABNFa" numbered="true" removeInRFC="false" toc="include" pn="section-7.1">
        <name slugifiedName="name-abnf-for-advanced-transport">ABNF for Advanced Transport</name>
        <sourcecode type="abnf" markers="false" pn="section-7.1-1">
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] simple-string

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

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

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

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

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

printable      =  %x20-21 / %x23-5B / %x5D-7E
                    ; All US-ASCII printable but double-quote and
                    ; backslash

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

quote          =  %x27   ; single quote

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

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

hexadecimal    =  [decimal] "#" *whitespace *hexadecimals "#"

hexadecimals   =  2(HEXDIG *whitespace)

base-64        =  [decimal] "|" *whitespace *base-64-chars
                     [base-64-end] "|"

base-64-chars  =  4(base-64-char *whitespace)

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

base-64-end    =  base-64-chars /
                  3(base-64-char *whitespace) ["=" *whitespace] /
                  2(base-64-char *whitespace) *2("=" *whitespace)
</sourcecode>
      </section>
      <section anchor="ABNFc" numbered="true" removeInRFC="false" toc="include" pn="section-7.2">
        <name slugifiedName="name-abnf-for-canonical">ABNF for Canonical</name>
        <sourcecode type="abnf" markers="false" pn="section-7.2-1">
c-sexp         =  c-string / ("(" *c-sexp ")")

c-string       =  [ "[" verbatim "]" ] verbatim
</sourcecode>
      </section>
      <section anchor="ABNFb" numbered="true" removeInRFC="false" toc="include" pn="section-7.3">
        <name slugifiedName="name-abnf-for-basic-transport">ABNF for Basic Transport</name>
        <sourcecode type="abnf" markers="false" pn="section-7.3-1">
b-sexp         =  c-sexp / b-base-64

b-base-64      =  "{" *whitespace *base-64-chars base-64-end "}"
                    ; encodes a c-sexp, which has a minimum
                    ; length of 2
</sourcecode>
      </section>
    </section>
    <section numbered="true" removeInRFC="false" toc="include" pn="section-8">
      <name slugifiedName="name-restricted-s-expressions">Restricted S-Expressions</name>
      <t indent="0" pn="section-8-1">This document has described S-expressions in general form.
Applications 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:</t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-8-2">
        <li pn="section-8-2.1">no advanced representations (only canonical and basic)</li>
        <li pn="section-8-2.2">no display-hints</li>
        <li pn="section-8-2.3">no lengths on hexadecimal, quoted-strings, or base-64 encodings</li>
        <li pn="section-8-2.4">no empty lists</li>
        <li pn="section-8-2.5">no empty octet-strings</li>
        <li pn="section-8-2.6">no lists having another list as its first element</li>
        <li pn="section-8-2.7">no base-64 or hexadecimal encodings</li>
        <li pn="section-8-2.8">fixed limits on the size of octet-strings</li>
      </ul>
      <t indent="0" pn="section-8-3">As provided in <xref target="Represent" format="default" sectionFormat="of" derivedContent="Section 6"/>, conformant
implementations will support canonical and basic representation, but
support for advanced representation is not generally required. Thus,
advanced representation can only be used in applications that mandate
its support or where a capability discovery mechanism indicates
support.</t>
    </section>
    <section anchor="Sec8" numbered="true" removeInRFC="false" toc="include" pn="section-9">
      <name slugifiedName="name-in-memory-representations">In-Memory Representations</name>
      <t indent="0" pn="section-9-1">For processing, the S-expression would typically be parsed and
represented in memory in a way that is more amenable to efficient
processing.  This document suggests two alternatives:</t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-9-2">
        <li pn="section-9-2.1">"list-structure"</li>
        <li pn="section-9-2.2">"array-layout"</li>
      </ul>
      <t indent="0" pn="section-9-3">These are only sketched here, as they are only suggestive. The
code in <xref target="SexpCode" format="default" sectionFormat="of" derivedContent="SexpCode"/> illustrates these styles in more
detail.</t>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-9.1">
        <name slugifiedName="name-list-structure-memory-repre">List-Structure Memory Representation</name>
        <t indent="0" pn="section-9.1-1">Here there are separate records for simple-strings, strings, and
lists or list nodes.  An S-expression of the form ("abc" "de") could
be encoded as two records for the simple-strings, two for the strings,
and two for the list elements where a record is a relatively small
block of memory and, except for simple-string, might have pointers in
it to other records. This is a fairly conventional representation as
discussed in Section 4 of <xref target="LISP2" format="default" sectionFormat="of" derivedContent="LISP2"/>.</t>
      </section>
      <section numbered="true" removeInRFC="false" toc="include" pn="section-9.2">
        <name slugifiedName="name-array-layout-memory-represe">Array-Layout Memory Representation</name>
        <t indent="0" pn="section-9.2-1">Here each S-expression is represented as a contiguous array of octets.
The first octet codes the "type" of the S-expression:</t>
        <sourcecode markers="false" pn="section-9.2-2">01   octet-string</sourcecode>
        <sourcecode markers="false" pn="section-9.2-3">02   octet-string with display-hint</sourcecode>
        <sourcecode markers="false" pn="section-9.2-4">03   beginning of list (and 00 is used for "end of list")</sourcecode>
        <t indent="0" pn="section-9.2-5">Each of the three types is immediately followed by a k-octet integer
indicating the size (in octets) of the following representation.  Here,
k is an integer that depends on the implementation. It might be
anywhere from 2 to 8, but it 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.</t>
        <t indent="0" pn="section-9.2-6">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.</t>
        <section numbered="true" removeInRFC="false" toc="include" pn="section-9.2.1">
          <name slugifiedName="name-octet-string">Octet-String</name>
          <t indent="0" pn="section-9.2.1-1">This is represented as follows:</t>
          <sourcecode markers="false" pn="section-9.2.1-2">
    01 &lt;length&gt; &lt;octet-string&gt;
</sourcecode>
          <t indent="0" pn="section-9.2.1-3">For example (here, k = 2):</t>
          <sourcecode markers="false" pn="section-9.2.1-4">
    01 0003 a b c
</sourcecode>
        </section>
        <section numbered="true" removeInRFC="false" toc="include" pn="section-9.2.2">
          <name slugifiedName="name-octet-string-with-display-h">Octet-String with Display-Hint</name>
          <t indent="0" pn="section-9.2.2-1">This is represented as follows:</t>
          <sourcecode markers="false" pn="section-9.2.2-2">
    02 &lt;length&gt;
      01 &lt;length&gt; &lt;octet-string&gt;    /* for display-type */
      01 &lt;length&gt; &lt;octet-string&gt;    /* for octet-string */
</sourcecode>
          <t indent="0" pn="section-9.2.2-3">For example, the S-expression: </t>
          <sourcecode markers="false" pn="section-9.2.2-4">
    [gif] #61626364#
</sourcecode>
          <t indent="0" pn="section-9.2.2-5">would be represented as (with k = 2):</t>
          <sourcecode markers="false" pn="section-9.2.2-6">
    02 000d
      01 0003  g  i  f
      01 0004 61 62 63 64
</sourcecode>
        </section>
        <section numbered="true" removeInRFC="false" toc="include" pn="section-9.2.3">
          <name slugifiedName="name-list">List</name>
          <t indent="0" pn="section-9.2.3-1">This is represented as:</t>
          <sourcecode markers="false" pn="section-9.2.3-2">
    03 &lt;length&gt; &lt;item1&gt; &lt;item2&gt; &lt;item3&gt; ... &lt;item&gt; 00
</sourcecode>
          <t indent="0" pn="section-9.2.3-3">For example, the list (abc [d]ef (g)) is represented in memory as
(with k = 2):</t>
          <sourcecode markers="false" pn="section-9.2.3-4">
    03 001b
      01 0003 a b c
      02 0009
        01 0001 d
        01 0002 e f
      03 0005
        01 0001 g
      00
    00
</sourcecode>
        </section>
      </section>
    </section>
    <section anchor="Sec10" numbered="true" removeInRFC="false" toc="include" pn="section-10">
      <name slugifiedName="name-security-considerations">Security Considerations</name>
      <t indent="0" pn="section-10-1">As a pure data representation format, there are few security
considerations to S-expressions. A canonical form is required for the
consistent creation and verification of digital signatures. This is
provided in <xref target="canonical" format="default" sectionFormat="of" derivedContent="Section 6.2"/>.</t>
      <t indent="0" pn="section-10-2">The default display-hint (see <xref target="DisplayHint" format="default" sectionFormat="of" derivedContent="Section 4.6"/>) can be
specified for an application. Note that if S-expressions containing
untyped octet-strings represented for that application are processed
by a different application, those untyped octet-string may be treated
as if they had a different display-hint.</t>
    </section>
    <section anchor="Sec12" numbered="true" removeInRFC="false" toc="include" pn="section-11">
      <name slugifiedName="name-iana-considerations">IANA Considerations</name>
      <t indent="0" pn="section-11-1">This document has no IANA actions.</t>
    </section>
  </middle>
  <back>
    <displayreference target="I-D.petithuguenin-ufmrg-formal-sexpr" to="Formal"/>
    <displayreference target="I-D.bormann-cbor-cddl-freezer" to="CDDL-freezer"/>
    <references pn="section-12">
      <name slugifiedName="name-references">References</name>
      <references pn="section-12.1">
        <name slugifiedName="name-normative-references">Normative References</name>
        <reference anchor="C88" quoteTitle="true" derivedAnchor="C88">
          <front>
            <title>The C Programming Language</title>
            <author surname="Kernighan" initials="B." fullname="Brian W. Kernighan"/>
            <author surname="Ritchie" initials="D." fullname="Dennis M. Ritchie"/>
            <date year="1988"/>
          </front>
          <seriesInfo name="ISBN" value="0-13-110370-9"/>
        </reference>
        <reference anchor="RFC0020" target="https://www.rfc-editor.org/info/rfc20" quoteTitle="true" derivedAnchor="RFC0020">
          <front>
            <title>ASCII format for network interchange</title>
            <author fullname="V.G. Cerf" initials="V.G." surname="Cerf"/>
            <date month="October" year="1969"/>
          </front>
          <seriesInfo name="STD" value="80"/>
          <seriesInfo name="RFC" value="20"/>
          <seriesInfo name="DOI" value="10.17487/RFC0020"/>
        </reference>
        <reference anchor="RFC2119" target="https://www.rfc-editor.org/info/rfc2119" quoteTitle="true" derivedAnchor="RFC2119">
          <front>
            <title>Key words for use in RFCs to Indicate Requirement Levels</title>
            <author fullname="S. Bradner" initials="S." surname="Bradner"/>
            <date month="March" year="1997"/>
            <abstract>
              <t indent="0">In many standards track documents several words are used to signify the requirements in the specification. These words are often capitalized. This document defines these words as they should be interpreted in IETF documents. This document specifies an Internet Best Current Practices for the Internet Community, and requests discussion and suggestions for improvements.</t>
            </abstract>
          </front>
          <seriesInfo name="BCP" value="14"/>
          <seriesInfo name="RFC" value="2119"/>
          <seriesInfo name="DOI" value="10.17487/RFC2119"/>
        </reference>
        <reference anchor="RFC3629" target="https://www.rfc-editor.org/info/rfc3629" quoteTitle="true" derivedAnchor="RFC3629">
          <front>
            <title>UTF-8, a transformation format of ISO 10646</title>
            <author fullname="F. Yergeau" initials="F." surname="Yergeau"/>
            <date month="November" year="2003"/>
            <abstract>
              <t indent="0">ISO/IEC 10646-1 defines a large character set called the Universal Character Set (UCS) which encompasses most of the world's writing systems. The originally proposed encodings of the UCS, however, were not compatible with many current applications and protocols, and this has led to the development of UTF-8, the object of this memo. UTF-8 has the characteristic of preserving the full US-ASCII range, providing compatibility with file systems, parsers and other software that rely on US-ASCII values but are transparent to other values. This memo obsoletes and replaces RFC 2279.</t>
            </abstract>
          </front>
          <seriesInfo name="STD" value="63"/>
          <seriesInfo name="RFC" value="3629"/>
          <seriesInfo name="DOI" value="10.17487/RFC3629"/>
        </reference>
        <reference anchor="RFC4648" target="https://www.rfc-editor.org/info/rfc4648" quoteTitle="true" derivedAnchor="RFC4648">
          <front>
            <title>The Base16, Base32, and Base64 Data Encodings</title>
            <author fullname="S. Josefsson" initials="S." surname="Josefsson"/>
            <date month="October" year="2006"/>
            <abstract>
              <t indent="0">This document describes the commonly used base 64, base 32, and base 16 encoding schemes. It also discusses the use of line-feeds in encoded data, use of padding in encoded data, use of non-alphabet characters in encoded data, use of different encoding alphabets, and canonical encodings. [STANDARDS-TRACK]</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="4648"/>
          <seriesInfo name="DOI" value="10.17487/RFC4648"/>
        </reference>
        <reference anchor="RFC5234" target="https://www.rfc-editor.org/info/rfc5234" quoteTitle="true" derivedAnchor="RFC5234">
          <front>
            <title>Augmented BNF for Syntax Specifications: ABNF</title>
            <author fullname="D. Crocker" initials="D." role="editor" surname="Crocker"/>
            <author fullname="P. Overell" initials="P." surname="Overell"/>
            <date month="January" year="2008"/>
            <abstract>
              <t indent="0">Internet technical specifications often need to define a formal syntax. Over the years, a modified version of Backus-Naur Form (BNF), called Augmented BNF (ABNF), has been popular among many Internet specifications. The current specification documents ABNF. It balances compactness and simplicity with reasonable representational power. The differences between standard BNF and ABNF involve naming rules, repetition, alternatives, order-independence, and value ranges. This specification also supplies additional rule definitions and encoding for a core lexical analyzer of the type common to several Internet specifications. [STANDARDS-TRACK]</t>
            </abstract>
          </front>
          <seriesInfo name="STD" value="68"/>
          <seriesInfo name="RFC" value="5234"/>
          <seriesInfo name="DOI" value="10.17487/RFC5234"/>
        </reference>
        <reference anchor="RFC8174" target="https://www.rfc-editor.org/info/rfc8174" quoteTitle="true" derivedAnchor="RFC8174">
          <front>
            <title>Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words</title>
            <author fullname="B. Leiba" initials="B." surname="Leiba"/>
            <date month="May" year="2017"/>
            <abstract>
              <t indent="0">RFC 2119 specifies common key words that may be used in protocol specifications. This document aims to reduce the ambiguity by clarifying that only UPPERCASE usage of the key words have the defined special meanings.</t>
            </abstract>
          </front>
          <seriesInfo name="BCP" value="14"/>
          <seriesInfo name="RFC" value="8174"/>
          <seriesInfo name="DOI" value="10.17487/RFC8174"/>
        </reference>
      </references>
      <references pn="section-12.2">
        <name slugifiedName="name-informative-references">Informative References</name>
        <reference anchor="BERN" target="https://datatracker.ietf.org/doc/html/draft-bernstein-netstrings-02" quoteTitle="true" derivedAnchor="BERN">
          <front>
            <title>Netstrings</title>
            <author initials="D. J." surname="Bernstein" fullname="D. J. Bernstein">
         </author>
            <date month="January" day="1" year="1997"/>
          </front>
          <seriesInfo name="Internet-Draft" value="draft-bernstein-netstrings-02"/>
          <refcontent>Work in Progress</refcontent>
        </reference>
        <reference anchor="CANON1" target="https://en.wikipedia.org/wiki/Canonical_S-expressions" quoteTitle="true" derivedAnchor="CANON1">
          <front>
            <title>Canonical S-expressions</title>
            <author surname="Wikipedia" fullname="Wikipedia"/>
          </front>
        </reference>
        <reference anchor="CANON2" target="https://github.com/ocaml-dune/csexp" quoteTitle="true" derivedAnchor="CANON2">
          <front>
            <title>Csexp - Canonical S-expressions</title>
            <author surname="Grinberg" initials="R." fullname="Rudi Grinberg"/>
            <date year="2023" month="3" day="24"/>
          </front>
        </reference>
        <reference anchor="I-D.bormann-cbor-cddl-freezer" target="https://datatracker.ietf.org/doc/html/draft-bormann-cbor-cddl-freezer-15" quoteTitle="true" derivedAnchor="CDDL-freezer">
          <front>
            <title>A feature freezer for the Concise Data Definition Language (CDDL)</title>
            <author fullname="Carsten Bormann" initials="C." surname="Bormann">
              <organization showOnFrontPage="true">UniversitÃ¤t Bremen TZI</organization>
            </author>
            <date day="28" month="February" year="2025"/>
            <abstract>
              <t indent="0">In defining the Concise Data Definition Language (CDDL), some features have turned up that would be nice to have. In the interest of completing this specification in a timely manner, the present document was started to collect nice-to-have features that did not make it into the first RFC for CDDL, RFC 8610, or the specifications exercising its extension points, such as RFC 9165. Significant parts of this draft have now moved over to the CDDL 2.0 project, described in draft-bormann-cbor-cddl-2-draft. The remaining items in this draft are not directly related to the CDDL 2.0 effort.</t>
            </abstract>
          </front>
          <seriesInfo name="Internet-Draft" value="draft-bormann-cbor-cddl-freezer-15"/>
          <refcontent>Work in Progress</refcontent>
        </reference>
        <reference anchor="I-D.petithuguenin-ufmrg-formal-sexpr" target="https://datatracker.ietf.org/doc/html/draft-petithuguenin-ufmrg-formal-sexpr-06" quoteTitle="true" derivedAnchor="Formal">
          <front>
            <title>A Formalization of Symbolic Expressions</title>
            <author fullname="Marc Petit-Huguenin" initials="M." surname="Petit-Huguenin">
              <organization showOnFrontPage="true">Impedance Mismatch LLC</organization>
            </author>
            <date day="4" month="May" year="2025"/>
            <abstract>
              <t indent="0">The goal of this document is to show and explain the formal model developed to guarantee that the examples and ABNF in the "SPKI Symbolic Expressions" Internet-Draft are correct.</t>
            </abstract>
          </front>
          <seriesInfo name="Internet-Draft" value="draft-petithuguenin-ufmrg-formal-sexpr-06"/>
          <refcontent>Work in Progress</refcontent>
        </reference>
        <reference anchor="GnuPG" target="https://www.gnupg.org/" quoteTitle="true" derivedAnchor="GnuPG">
          <front>
            <title>The GNU Privacy Guard</title>
            <author>
              <organization showOnFrontPage="true">GnuPG</organization>
            </author>
          </front>
        </reference>
        <reference anchor="Inferno" target="https://man.cat-v.org/inferno/6/sexprs" quoteTitle="true" derivedAnchor="Inferno">
          <front>
            <title>Inferno S-expressions</title>
            <author/>
          </front>
          <refcontent>Inferno Manual Page</refcontent>
        </reference>
        <reference anchor="Libgcrypt" target="https://www.gnupg.org/documentation/manuals/gcrypt/" quoteTitle="true" derivedAnchor="Libgcrypt">
          <front>
            <title>The Libgcrypt Library</title>
            <author>
              <organization showOnFrontPage="true">GnuPG</organization>
            </author>
            <date year="2023" month="4" day="6"/>
          </front>
          <refcontent>Libgcrypt version 1.10.2</refcontent>
        </reference>
        <reference anchor="LISP" target="https://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf" quoteTitle="true" derivedAnchor="LISP">
          <front>
            <title>LISP 1.5 Programmer's Manual</title>
            <author surname="McCarthy" initials="J." fullname="John McCarthy"/>
            <author fullname="Paul W. Abrahams"/>
            <author fullname="Daniel J. Edwards"/>
            <author fullname="Timothy P. Hart"/>
            <author surname="Levin" initials="M." fullname="Michael I. Levin">
              <organization showOnFrontPage="true">The Computer Center and Research Laboratory of Electronics, Massachusetts Institute of Technology</organization>
            </author>
            <date year="1962" month="August" day="15"/>
          </front>
          <seriesInfo name="ISBN-13" value="978-0-262-12011-0"/>
          <seriesInfo name="ISBN-10" value="0262130114"/>
        </reference>
        <reference anchor="LISP2" target="https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/PL/LISP.pdf" quoteTitle="true" derivedAnchor="LISP2">
          <front>
            <title>Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I</title>
            <author surname="McCarthy" initials="J." fullname="John McCarthy">
              <organization showOnFrontPage="true">Massachusetts Institute of Technology</organization>
            </author>
            <date year="1960" month="April"/>
          </front>
        </reference>
        <reference anchor="RFC2046" target="https://www.rfc-editor.org/info/rfc2046" quoteTitle="true" derivedAnchor="RFC2046">
          <front>
            <title>Multipurpose Internet Mail Extensions (MIME) Part Two: Media Types</title>
            <author fullname="N. Freed" initials="N." surname="Freed"/>
            <author fullname="N. Borenstein" initials="N." surname="Borenstein"/>
            <date month="November" year="1996"/>
            <abstract>
              <t indent="0">This second document defines the general structure of the MIME media typing system and defines an initial set of media types. [STANDARDS-TRACK]</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="2046"/>
          <seriesInfo name="DOI" value="10.17487/RFC2046"/>
        </reference>
        <reference anchor="RFC2130" target="https://www.rfc-editor.org/info/rfc2130" quoteTitle="true" derivedAnchor="RFC2130">
          <front>
            <title>The Report of the IAB Character Set Workshop held 29 February - 1 March, 1996</title>
            <author fullname="C. Weider" initials="C." surname="Weider"/>
            <author fullname="C. Preston" initials="C." surname="Preston"/>
            <author fullname="K. Simonsen" initials="K." surname="Simonsen"/>
            <author fullname="H. Alvestrand" initials="H." surname="Alvestrand"/>
            <author fullname="R. Atkinson" initials="R." surname="Atkinson"/>
            <author fullname="M. Crispin" initials="M." surname="Crispin"/>
            <author fullname="P. Svanberg" initials="P." surname="Svanberg"/>
            <date month="April" year="1997"/>
            <abstract>
              <t indent="0">This report details the conclusions of an IAB-sponsored invitational workshop held 29 February - 1 March, 1996, to discuss the use of character sets on the Internet. It motivates the need to have character set handling in Internet protocols which transmit text, provides a conceptual framework for specifying character sets, recommends the use of MIME tagging for transmitted text, recommends a default character set *without* stating that there is no need for other character sets, and makes a series of recommendations to the IAB, IANA, and the IESG for furthering the integration of the character set framework into text transmission protocols. This memo provides information for the Internet community. This memo does not specify an Internet standard of any kind.</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="2130"/>
          <seriesInfo name="DOI" value="10.17487/RFC2130"/>
        </reference>
        <reference anchor="RFC2692" target="https://www.rfc-editor.org/info/rfc2692" quoteTitle="true" derivedAnchor="RFC2692">
          <front>
            <title>SPKI Requirements</title>
            <author fullname="C. Ellison" initials="C." surname="Ellison"/>
            <date month="September" year="1999"/>
            <abstract>
              <t indent="0">The SPKI Working Group first established a list of things one might want to do with certificates (attached at the end of this document), and then summarized that list of desires into requirements. This document presents that summary of requirements. This memo defines an Experimental Protocol for the Internet community.</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="2692"/>
          <seriesInfo name="DOI" value="10.17487/RFC2692"/>
        </reference>
        <reference anchor="RFC2693" target="https://www.rfc-editor.org/info/rfc2693" quoteTitle="true" derivedAnchor="RFC2693">
          <front>
            <title>SPKI Certificate Theory</title>
            <author fullname="C. Ellison" initials="C." surname="Ellison"/>
            <author fullname="B. Frantz" initials="B." surname="Frantz"/>
            <author fullname="B. Lampson" initials="B." surname="Lampson"/>
            <author fullname="R. Rivest" initials="R." surname="Rivest"/>
            <author fullname="B. Thomas" initials="B." surname="Thomas"/>
            <author fullname="T. Ylonen" initials="T." surname="Ylonen"/>
            <date month="September" year="1999"/>
            <abstract>
              <t indent="0">This document gives the theory behind SPKI certificates and ACLs without going into technical detail about those structures or their uses. This memo defines an Experimental Protocol for the Internet community.</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="2693"/>
          <seriesInfo name="DOI" value="10.17487/RFC2693"/>
        </reference>
        <reference anchor="RFC3259" target="https://www.rfc-editor.org/info/rfc3259" quoteTitle="true" derivedAnchor="RFC3259">
          <front>
            <title>A Message Bus for Local Coordination</title>
            <author fullname="J. Ott" initials="J." surname="Ott"/>
            <author fullname="C. Perkins" initials="C." surname="Perkins"/>
            <author fullname="D. Kutscher" initials="D." surname="Kutscher"/>
            <date month="April" year="2002"/>
            <abstract>
              <t indent="0">The local Message Bus (Mbus) is a light-weight message-oriented coordination protocol for group communication between application components. The Mbus provides automatic location of communication peers, subject based addressing, reliable message transfer and different types of communication schemes. The protocol is layered on top of IP multicast and is specified for IPv4 and IPv6. The IP multicast scope is limited to link-local multicast. This document specifies the Mbus protocol, i.e., message syntax, addressing and transport mechanisms. This memo provides information for the Internet community.</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="3259"/>
          <seriesInfo name="DOI" value="10.17487/RFC3259"/>
        </reference>
        <reference anchor="RFC3275" target="https://www.rfc-editor.org/info/rfc3275" quoteTitle="true" derivedAnchor="RFC3275">
          <front>
            <title>(Extensible Markup Language) XML-Signature Syntax and Processing</title>
            <author fullname="D. Eastlake 3rd" initials="D." surname="Eastlake 3rd"/>
            <author fullname="J. Reagle" initials="J." surname="Reagle"/>
            <author fullname="D. Solo" initials="D." surname="Solo"/>
            <date month="March" year="2002"/>
            <abstract>
              <t indent="0">This document specifies XML (Extensible Markup Language) digital signature processing rules and syntax. [STANDARDS-TRACK]</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="3275"/>
          <seriesInfo name="DOI" value="10.17487/RFC3275"/>
        </reference>
        <reference anchor="RFC8259" target="https://www.rfc-editor.org/info/rfc8259" quoteTitle="true" derivedAnchor="RFC8259">
          <front>
            <title>The JavaScript Object Notation (JSON) Data Interchange Format</title>
            <author fullname="T. Bray" initials="T." role="editor" surname="Bray"/>
            <date month="December" year="2017"/>
            <abstract>
              <t indent="0">JavaScript Object Notation (JSON) is a lightweight, text-based, language-independent data interchange format. It was derived from the ECMAScript Programming Language Standard. JSON defines a small set of formatting rules for the portable representation of structured data.</t>
              <t indent="0">This document removes inconsistencies with other specifications of JSON, repairs specification errors, and offers experience-based interoperability guidance.</t>
            </abstract>
          </front>
          <seriesInfo name="STD" value="90"/>
          <seriesInfo name="RFC" value="8259"/>
          <seriesInfo name="DOI" value="10.17487/RFC8259"/>
        </reference>
        <reference anchor="RFC8949" target="https://www.rfc-editor.org/info/rfc8949" quoteTitle="true" derivedAnchor="RFC8949">
          <front>
            <title>Concise Binary Object Representation (CBOR)</title>
            <author fullname="C. Bormann" initials="C." surname="Bormann"/>
            <author fullname="P. Hoffman" initials="P." surname="Hoffman"/>
            <date month="December" year="2020"/>
            <abstract>
              <t indent="0">The Concise Binary Object Representation (CBOR) is a data format whose design goals include the possibility of extremely small code size, fairly small message size, and extensibility without the need for version negotiation. These design goals make it different from earlier binary serializations such as ASN.1 and MessagePack.</t>
              <t indent="0">This document obsoletes RFC 7049, providing editorial improvements, new details, and errata fixes while keeping full compatibility with the interchange format of RFC 7049. It does not create a new version of the format.</t>
            </abstract>
          </front>
          <seriesInfo name="STD" value="94"/>
          <seriesInfo name="RFC" value="8949"/>
          <seriesInfo name="DOI" value="10.17487/RFC8949"/>
        </reference>
        <reference anchor="Ribose" target="https://open.ribose.com/" quoteTitle="true" derivedAnchor="Ribose">
          <front>
            <title>Open-source projects for developers and designers</title>
            <author>
              <organization showOnFrontPage="true">Ribose Group Inc.</organization>
            </author>
          </front>
        </reference>
        <reference anchor="RNPGP_SEXPP" target="https://github.com/rnpgp/sexpp" quoteTitle="true" derivedAnchor="RNPGP_SEXPP">
          <front>
            <title>S-Expressions parser and generator library in C++ (SEXP in C++)</title>
            <author/>
            <date year="2025" month="March" day="22"/>
          </front>
          <refcontent>Version 0.9.2, commit 249c6e3</refcontent>
        </reference>
        <reference anchor="SDSI" target="https://people.csail.mit.edu/rivest/pubs/RL96.ver-1.1.html" quoteTitle="true" derivedAnchor="SDSI">
          <front>
            <title>A Simple Distributed Security Architecture</title>
            <author surname="Rivest" initials="R." fullname="Ronald L. Rivest"/>
            <author surname="Lampson" initials="B." fullname="Butler Lampson"/>
            <date year="1996" month="October" day="2"/>
          </front>
          <refcontent>Working document for SDSI version 1.1</refcontent>
        </reference>
        <reference anchor="SexpCode" target="https://github.com/jpmalkiewicz/rivest-sexp" quoteTitle="true" derivedAnchor="SexpCode">
          <front>
            <title>SEXP---(S-expressions)</title>
            <author/>
            <date year="2015" month="6" day="10"/>
          </front>
          <refcontent>commit 4aa7c36</refcontent>
        </reference>
        <reference anchor="SEXPP" target="https://github.com/seattlerb/sexp_processor" quoteTitle="true" derivedAnchor="SEXPP">
          <front>
            <title>SexpProcessor</title>
            <author/>
            <date year="2025" month="April" day="11"/>
          </front>
          <refcontent>commit a90f90f</refcontent>
        </reference>
        <reference anchor="SFEXP" target="https://github.com/mjsottile/sfsexp" quoteTitle="true" derivedAnchor="SFEXP">
          <front>
            <title>Small Fast X-Expression Library</title>
            <author/>
            <date year="2023" month="3" day="24"/>
          </front>
          <refcontent>commit b7d3bea</refcontent>
        </reference>
        <reference anchor="SPKI" target="https://people.csail.mit.edu/rivest/pubs/RL96.slides-maryland.pdf" quoteTitle="true" derivedAnchor="SPKI">
          <front>
            <title>SPKI/SDSI 2.0 A Simple Distributed Security Infrastructure</title>
            <author surname="Rivest" initials="R." fullname="Ronald L. Rivest">
              <organization showOnFrontPage="true">MIT Lab for Computer Science</organization>
            </author>
          </front>
        </reference>
        <reference anchor="Unicode" target="https://www.unicode.org/versions/latest/" quoteTitle="true" derivedAnchor="Unicode">
          <front>
            <title abbrev="Unicode">The Unicode Standard</title>
            <author>
              <organization showOnFrontPage="true">The Unicode Consortium</organization>
              <address/>
            </author>
            <date/>
          </front>
        </reference>
        <reference anchor="XML" target="https://www.w3.org/TR/2008/REC-xml-20081126/" quoteTitle="true" derivedAnchor="XML">
          <front>
            <title>Extensible Markup Language (XML) 1.0</title>
            <author surname="Bray" initials="T." fullname="Tim Bray">
              <organization showOnFrontPage="true">Textuality and Netscape</organization>
            </author>
            <author surname="Paoli" initials="J." fullname="Jean Paoli">
              <organization showOnFrontPage="true">Microsoft</organization>
            </author>
            <author surname="Sperberg-McQueen" initials="C.M." fullname="C. M. Sperberg-McQueen">
              <organization showOnFrontPage="true">W3C</organization>
            </author>
            <author surname="Maler" initials="E." fullname="Eve Maler">
              <organization showOnFrontPage="true">Sun Microsystems</organization>
            </author>
            <author surname="Yergeau" initials="F." fullname="François Yergeau"/>
            <date year="2008" month="11" day="26"/>
          </front>
          <refcontent>W3C Recommendation</refcontent>
          <annotation>Latest version available at <eref target="https://www.w3.org/TR/REC-xml/" brackets="angle"/>.</annotation>
        </reference>
      </references>
    </references>
    <section anchor="Code" numbered="true" removeInRFC="false" toc="include" pn="section-appendix.a">
      <name slugifiedName="name-implementations">Implementations</name>
      <t indent="0" pn="section-appendix.a-1">At this time there are multiple implementations, many open source,
available that are intended to read and parse some or all of the
various S-expression formats specified here. In particular, see the
following -- likely incomplete -- list:</t>
      <ul bare="false" empty="false" indent="3" spacing="normal" pn="section-appendix.a-2">
        <li pn="section-appendix.a-2.1">Project GNU's <xref target="Libgcrypt" format="default" sectionFormat="of" derivedContent="Libgcrypt"/></li>
        <li pn="section-appendix.a-2.2">Ribose's RNP <xref target="RNPGP_SEXPP" format="default" sectionFormat="of" derivedContent="RNPGP_SEXPP"/> in C++</li>
        <li pn="section-appendix.a-2.3">Github project of J. P. Malkiewicz <xref target="SexpCode" format="default" sectionFormat="of" derivedContent="SexpCode"/> in C</li>
        <li pn="section-appendix.a-2.4">The Inferno implementation <xref target="Inferno" format="default" sectionFormat="of" derivedContent="Inferno"/></li>
        <li pn="section-appendix.a-2.5">Small Fast X-Expression Library <xref target="SFEXP" format="default" sectionFormat="of" derivedContent="SFEXP"/></li>
        <li pn="section-appendix.a-2.6">S-expression Processor <xref target="SEXPP" format="default" sectionFormat="of" derivedContent="SEXPP"/> in Ruby</li>
        <li pn="section-appendix.a-2.7">Canonical S-expressions <xref target="CANON2" format="default" sectionFormat="of" derivedContent="CANON2"/> (OCAML)</li>
      </ul>
    </section>
    <section anchor="Acknowledgements" numbered="false" removeInRFC="false" toc="include" pn="section-appendix.b">
      <name slugifiedName="name-acknowledgements">Acknowledgements</name>
      <t indent="0" pn="section-appendix.b-1">Special thanks to <contact fullname="Daniel K. Gillmor"/> for his extensive
  comments.</t>
      <t indent="0" pn="section-appendix.b-2">The comments and suggestions of the following are gratefully
  acknowledged: <contact fullname="John Klensin"/> and <contact fullname="Caleb Malchik"/>.</t>
    </section>
    <section anchor="Contributors" numbered="false" removeInRFC="false" toc="include" pn="section-appendix.c">
      <name slugifiedName="name-contributors">Contributors</name>
      <t indent="0" pn="section-appendix.c-1">Special thanks to <contact fullname="Marc Petit-Huguenin"/>, particularly for his
  extensive work and advice on the ABNF and on locating and fixing
  unclear parts of earlier draft versions of this document:</t>
      <contact fullname="Marc Petit-Huguenin" initials="M." surname="Petit-Huguenin">
        <organization showOnFrontPage="true">Impedance Mismatch LLC</organization>
        <address>
          <email>marc@petit-huguenin.org</email>
        </address>
      </contact>
    </section>
    <section anchor="authors-addresses" numbered="false" removeInRFC="false" toc="include" pn="section-appendix.d">
      <name slugifiedName="name-authors-addresses">Authors' Addresses</name>
      <author fullname="Ronald L. Rivest" initials="R." surname="Rivest">
        <organization showOnFrontPage="true">MIT CSAIL</organization>
        <address>
          <postal>
            <street>32 Vassar Street, Room 32-G692</street>
            <city>Cambridge</city>
            <region>Massachusetts</region>
            <code>02139</code>
            <country>United States of America</country>
          </postal>
          <email>rivest@mit.edu</email>
          <uri>https://www.csail.mit.edu/person/ronald-l-rivest</uri>
        </address>
      </author>
      <author fullname="Donald E. Eastlake 3rd" initials="D." surname="Eastlake 3rd">
        <organization showOnFrontPage="true">Independent</organization>
        <address>
          <postal>
            <street>2386 Panoramic Circle</street>
            <city>Apopka</city>
            <region>Florida</region>
            <code>32703</code>
            <country>United States of America</country>
          </postal>
          <phone>+1-508-333-2270</phone>
          <email>d3e3e3@gmail.com</email>
        </address>
      </author>
    </section>
  </back>
</rfc>
