S式

コンピュータ プログラミングにおいて、S 式(またはシンボリック式、略してsexprまたはsexp ) は、ネストされたリスト(ツリー構造) データを表す同名の表記法による式です。 S 式はプログラミング言語Lispのために発明され、普及しました。Lisp では、ソース コードとデータの両方に S 式を使用しています。

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

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

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

#n=(x y . #n#)

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

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

(x y z)

の略

(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.0 6.28318 6.022e23

この文字は、16 進整数や文字 など、#構文の拡張の接頭辞としてよく使用されます。#x10#\C

Lisp でソース コードを表す場合、S 式の最初の要素は通常、演算子または関数名であり、残りの要素は引数として扱われます。これは、「プレフィックス表記法」または「ポーランド表記法」と呼ばれます。たとえば、Cで記述されたブール式は、 Lisp の S 式ベースのプレフィックス表記法では として表されます。4 == (2 + 2)(= 4 (+ 2 2))

上で述べたように、「アトム」の正確な定義は LISP のような言語によって異なります。引用符で囲まれた文字列には通常、引用符以外の文字を含めることができますが、引用符で囲まれていない識別子アトムには通常、引用符、空白文字、括弧、角括弧、中括弧、バックスラッシュ、およびセミコロン以外の文字を含めることができます。どちらの場合も、禁止文字は通常、バックスラッシュを前に付けてエスケープすることで含めることができます。Unicodeのサポートは異なります。

s-expr 定義の再帰的なケースは、従来、コンス セルを使用して実装されています。

S 式はもともとM 式で操作されるデータのみを対象としていましたが、Lisp の最初の実装は M 式の S 式エンコードのインタープリタであり、Lisp プログラマはすぐにコードとデータの両方に S 式を使用することに慣れました。これは、Lisp が同図像的であることを意味します。つまり、プログラムの主な表現は、言語自体のプリミティブ型のデータ構造でもあります。

ネストされたリストは S 式として記述できます。((milk juice) (honey marmalade))は 2 要素の S 式で、その要素も 2 要素の S 式です。Lisp (およびこの記事) で使用される空白で区切られた表記法は一般的です。改行文字は通常、区切り文字として適しています。 これは、S 式として記述された英語のごく一部の単純な文脈自由文法です(Gazdar/Melish、Lisp での自然言語処理)。ここで、S は文、NP は名詞句、VP は動詞句、V は動詞です。

((( S ) ( NP VP )) (( VP ) ( V )) (( VP ) ( V NP )) (( V )死亡) (( V )雇用) (( NP )看護師) (( NP )患者) (( NP )メディセンター) (( NP ) 「Dr Chan」))  
  
   
  
  
  
  
  
  

プログラム コードは、通常はプレフィックス表記法を使用して S 式で記述できます。Common Lispの例:

(階乗( x )を定義します( if (ゼロ p x ) 1 ( * x (階乗( - x 1 )))))  
     
       
            

Lisp では、関数 READ を使用して S 式を読み取ることができます。READ は、S 式のテキスト表現を読み取り、Lisp データを返します。関数 PRINT を使用して S 式を出力することができます。すべての印刷されたデータ オブジェクトが読み取り可能な表現を持つ場合、出力は関数 READ を使用して読み取ることができます。Lisp には、数値、文字列、シンボル、リスト、およびその他の多くのデータ型の読み取り可能な表現があります。プログラム コードは、関数 PPRINT (注: 2 つの P はpretty -print の略) を使用して、きれいに印刷される S 式としてフォーマットできます。

Lisp プログラムは有効な S 式ですが、すべての S 式が有効な Lisp プログラムであるとは限りません。(1.0 + 3.1)は有効な S 式ですが、有効な Lisp プログラムではありません。Lisp はプレフィックス表記を使用し、浮動小数点数 (ここでは 1.0) は演算 (式の最初の要素) として有効ではないためです。

のように、一重引用符が前に付いた S 式は、引用符で囲まれた S 式 (この場合は )の糖衣構文'xです。 (quote x)

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

いくつかのLisp由来のプログラミング言語の標準には、S式の構文の仕様が含まれています。これには、Common Lisp（ANSI標準文書ANSI INCITS 226-1994（R2004））、Scheme（R5RSおよびR6RS ^[5]）、およびISLISPが含まれます。

1997年5月、ロン・リベストはRFCとして公開することを検討するためにインターネットドラフト^[6]を提出した。ドラフトではLispのS式に基づいた構文を定義したが、プログラミング専用ではなく、汎用的なデータストレージと交換（XMLに類似）を目的としていた。RFCとしては承認されなかったが、それ以来他のRFC（RFC 2693など）や他のいくつかの出版物で引用され、使用されている。^{[7]もともとは}SPKIで使用することを意図していた。

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

Rivest の草案では、 「デジタル署名の目的」で正規表現を定義しています。これは、コンパクトで、解析しやすく、あらゆる抽象 S 式に対して一意となるように意図されています。文字列をそのまま使用できるのみで、文字列の外側の書式設定として空白文字を禁止しています。最後に、「基本トランスポート表現」があります。これは、正規形式か、Base64 としてエンコードされ、中括弧で囲まれた形式のいずれかです。後者は、スペースを変更する可能性のあるシステム (たとえば、80 文字幅の行があり、それより長い文字は折り返される電子メール システム) で、正規にエンコードされた S 式を安全にトランスポートすることを目的としています。

このフォーマットは、SPKI以外での使用には広く採用されていません（GnuPG、libgcrypt、Nettle、GNU lshなどが使用しています）。RivestのS式のウェブページには、パーサーとジェネレーターのCソースコード（MITライセンスの下で利用可能）が掲載されており、他のプログラムに採用したり埋め込んだりすることができます。^[8]さらに、このフォーマットを独自に実装することに制限はありません。

• 短所
• CARとCDR
• フェックス
• ラムダ計算
• M式
• 標準的なS式
• データシリアル化形式の比較

• GitHub 上の C/C++ 用の小型で高速な S 式ライブラリ sfsexp
• minilisp、Léon Bottou 著。
• Rosettacode の S 式には、多くの言語のリーダーとライターの実装があります。