S表現

コンピュータプログラミングにおいて、S式（または記号式、略してsexprまたはsexp ）とは、ネストされたリスト（ツリー構造）データを表す同名の表記法による式のことです。S式は、データだけでなくソースコードにも使用されるプログラミング言語Lispのために考案され、普及しました。

Lispの通常の括弧構文では、S式は古典的に次のように定義されます^{[ 1 ]。}

1. xの形の原子、または
2. ( x . y )の形式の式。ここでxとyは S 式です。

この定義は、LISP におけるリストの表現が、それぞれ順序対である一連の「セル」として表されることを反映しています。通常のリストでは、y は次のセル (存在する場合) を指し、リストを形成します。定義の再帰節は、この表現と S 式表記の両方が任意の二分木を表現できることを意味します。ただし、この表現は原則として循環参照を許容する可能性があり、その場合、構造は木ではなく循環グラフとなり、SQL の外部キー、SGML / XML の IDREFなどと同様の相互参照の規則が提供されない限り、古典的な S 式表記では表現できません。Common Lisp [ 2 ] や Scheme [ 3 ] などの最新の Lisp 方言では、データ ラベルを介してこのような構文が提供され、オブジェクトにマークを^{付けることが}でき、^{その後、他}の場所で再帰して、重複した構造ではなく共有された構造を示し、リーダーまたはプリンタが無限に再帰することなく循環を検出して評価または表示をトリガーできるようにします。

#n=(xy . #n#)

原子の定義は文脈によって異なる。ジョン・マッカーシーによる元の定義^{[ 1 ]}では、「単一の空白が埋め込まれた大文字のラテン文字と数字の文字列」（文字文字列と数値リテラルのサブセット）として表現される「識別可能な原子記号の無限セット」が存在すると想定されていた。

ほとんどの最新のsexpr表記法は、より一般的な引用符付き文字列（句読点や完全なUnicodeを含むなど）を許可し、2つ以上のメンバーを持つリストを表すために省略表記法を使用するため、

(xyz)

は

(x . (y . (z . NIL)))

NILは特別なリスト末尾オブジェクトです（ とも表記され、これはScheme ^{[ 4 ]}()における唯一の表現です）。

Lisp系のプログラミング言語では、S式はソースコードとデータの両方を表現するために使用されます。S式は、 DSSSLなどのLisp派生言語や、IMAPやJohn McCarthy氏のCBCLといった通信プロトコルのマークアップなどにも使用されています。また、 WebAssemblyのテキスト表現としても使用されています。構文の詳細やサポートされるデータ型は言語によって異なりますが、これらの言語に共通する最も特徴は、S式と接頭辞表記の使用です。

S式フォーマットには多くのバリエーションがあり、さまざまなデータ型に対して多様な構文をサポートしています。最も広くサポートされているのは以下のとおりです。

• リストとペア：(1 () (2 . 3) (4))
• 記号：with-hyphen?@!$|a symbol with spaces|
• 文字列:"Hello, world!"
• 整数：-9876543210
• 浮動小数点数：-0.06.283186.022e23

この文字は#、構文への拡張機能の接頭辞としてよく使用されます。たとえば、#x1016進整数や#\C文字などです。

S式はXMLと比較されることが多いですが、重要な違いの一つは、S式はドットペアという単一の包含形式しか持たないのに対し、XMLタグは単純な属性、他のタグ、またはCDATAをそれぞれ異なる構文で包含できる点です。もう一つの違いは、S式は参照メカニズムを定義していないのに対し、XMLは一意の識別子とその参照という概念を提供している点です。単純なユースケースではS式の方がXMLよりも簡単ですが、より高度なユースケースでは、XMLにはXPathと呼ばれるクエリ言語があり、多くのツールやサードパーティライブラリがXMLデータの処理を簡素化するためにこれを使用しています。

Lisp から派生したプログラミング言語の標準規格には、S 式構文の仕様が含まれています。これには、Common Lisp (ANSI 標準文書 ANSI INCITS 226-1994 (R2004))、Scheme (R5RS およびR6RS ^{[ 6 ]} )、およびISLISP が含まれます。

1997 年 5 月、Ron Rivest は、RFCとして公開することを検討してもらうためにインターネット ドラフト^{[ 7 ]}を提出しました。このドラフトは Lisp S 式に基づく構文を定義していましたが、プログラミング専用ではなく、汎用的なデータ ストレージと交換 ( XMLと同様) を目的としていました。RFC として承認されることはありませんでしたが、その後、他の RFC (RFC 2693 など) やいくつかの出版物で引用され、使用されています。^{[ 8 ]}元々はSPKIで使用することを意図していました。

Rivestのフォーマットでは、S式はオクテット文字列（一連のバイト）または他のS式の有限リストのいずれかであると定義されています。この構造を表現するための3つの交換フォーマットが記述されています。1つは「高度なトランスポート」で、フォーマットに関して非常に柔軟性があり、構文的にはLispスタイルの式に似ていますが、同一ではありません。たとえば、高度なトランスポートでは、オクテット文字列をそのまま（文字列の長さの後にコロンと文字列全体が続く）、エスケープ文字を許可した引用符形式、16進数、Base64、または特定の条件を満たす場合は「トークン」として直接配置することができます。（Rivestのトークンは、利便性と美観のためだけに用いられ、他の文字列とまったく同じように扱われるのに対し、Lispのトークンは特定の構文上の意味を持つという点でLispのトークンとは異なります。）

リベスト氏の草案では、 「デジタル署名目的」の標準表現が定義されています。これは、コンパクトで解析しやすく、あらゆる抽象S式に対して一意であるように設計されています。文字列のみをそのまま使用でき、文字列外の書式として空白文字は禁止されています。最後に、「基本転送表現」があり、これは標準形式か、Base64でエンコードして中括弧で囲んだ形式のいずれかです。後者は、間隔が変わる可能性のあるシステム（例えば、行幅が80文字で、それより長い行は折り返す電子メールシステムなど）で、標準形式でエンコードされたS式を安全に転送することを目的としています。

この形式は、SPKI 以外での使用に広く適応されていません (一部のユーザーにはGnuPG、libgcrypt、Nettle、GNU lsh などがあります)。Rivest の S 式ウェブ ページには、パーサーとジェネレータのCソース コード ( MIT ライセンスで利用可能) が提供されており、これを適応させて他のプログラムに組み込むことができます。^{[ 9 ]}さらに、この形式を独自に実装することに制限はありません。

• CARとCDR
• フェックスプ
• ラムダ計算
• M表現
• データシリアル化フォーマットの比較

• sfsexpは、GitHubで公開されているC/C++用の小型で高速なS式ライブラリです。
• minilisp、Léon Bottou 著。
• RosettacodeのS式には、多くの言語に対応した読み書き機能の実装があります。