S式

S式の木構造 (* 2 (+ 3 4))

コンピュータプログラミングにおいて、S式^{[注 1]}（S-expression）はネストしたリスト（木構造）のデータである。

S式は、プログラミング言語Lispのために考案され、普及した。Lispでは、データだけでなく、ソースコードにもS式を使用する。

Lispの括弧書き文法では、S式は典型的には次のように定義される。

1. アトム
2. xとyがS式であるとき(x . y)という形式の式

この定義は、Lispがリストを一連の「セル」として表現していることを反映したもので、それぞれが順序付けられたペアになっている。一般的なリストでは、yは次のセル（もしあれば）を指し、リストを形成する。定義の再帰は、この表現とS式記法の両方が、任意の二分木を表現できることを意味する。

最近のほとんどのsexpr記法では、より一般的な引用文字列（例えば、句読点や完全なUnicodeを含む）を許容しており、おおまかには次のように定義される。

1. アトムや、データオブジェクトのリテラルはS式である
2. 空リストを表すnil(Common Lisp)または()もS式である（Schemeでは空リストはnilで表さない）
3. xとyがS式のとき(x . y)のように、ドットで区切られたペアもS式である
4. それぞれがs式であるx, y, zの連結リストの形をした(x . (y . (z . ())))を(x y z)のように、また(x . ())を(x)のように、省略した記法もS式である
5. その他の糖衣構文。たとえば(quote foo)を'fooなど

アトムの定義は文脈によって異なるが、ジョン・マッカーシーによるオリジナルの定義^[1]では、「区別可能なアトミックなシンボルの無限の集合」が存在すると仮定されており、「1つの空白が埋め込まれた大文字のラテン文字と数字の文字列」として表されていた（文字列と数値リテラルの部分集合）。

Lisp系のプログラミング言語では、ソースコードとデータの両方を表現するためにS式が使われている。S式は他にもDSSSLなどのLisp由来の言語や、IMAPやジョン・マッカーシーの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での扱い

Lispでソースコードを表現する場合、S式の最初の要素を演算子や関数名とし、残りの要素を引数として扱うのが一般的である。これを「前置記法」または「ポーランド記法」という。例えば、C言語で4 == (2 + 2)と書かれているブール式は、LispのS式の前置記法では(= 4 (+ 2 2))と表される。

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

S式定義の再帰的なケースは、伝統的にconsセルを使って実装される。

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

S式データの例

((milk juice) (honey marmalade))は2要素のS式であり、その要素も2要素のS式である。改行は通常、セパレータとして認められる。

これは、S式として書かれた英語の小さな部分集合のための簡単な文脈自由文法である。 (Gazdar/Melish, Natural Language Processing in Lisp)

ここで、S=主語, NP=名詞句, VP=動詞句, V=動詞、である。

(((S) (NP VP))
 ((VP) (V))
 ((VP) (V NP))
 ((V) died)
 ((V) employed)
 ((NP) nurses)
 ((NP) patients)
 ((NP) Medicenter)
 ((NP) "Dr Chan"))

S式ソースコードの例

Common Lispでの例:

(defun factorial (x)
   (if (zerop x)
       1
       (* x (factorial (- x 1)))))

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

Lispプログラムは有効なS式だが、すべてのS式が有効なLispプログラムになるわけではない。(1.0 + 3.1)は有効なS式だが、有効なLispプログラムではない。これは、Lispが前置記法を使用しており、浮動小数点数(ここでは1.0)は演算(式の最初の要素)として有効ではないからである。

構文解析

S式はよくXMLと比較されるが、主な違いは、S式には点.によるペアという1つの包含形式しかないのに対し、XMLのタグには単純な属性、他のタグ、CDATA（英語版）が含まれ、それぞれ異なる構文を使用できる。単純な用途では、S式はXMLよりもシンプルだが、より高度な用途になると、XMLにはXPathと呼ばれるクエリ言語があり、XMLデータの取り扱いを簡単にする多くのツールやサードパーティのライブラリがある。

標準化

Lisp由来のプログラミング言語の規格には、S式の構文の仕様が含まれているものがある。これには、Common Lisp（ANSI標準文書ANSI INCITS 226-1994 (R2004)）、Scheme（R5RSおよびR6RS）、ISLISP（英語版）などがある。

注釈

1. シンボリック式（symbolic expression）とも呼ばれ sexpr, sexp などと略記される。

出典

1. John McCarthy (1960/2006). Recursive functions of symbolic expressions Archived 2004-02-02 at the Wayback Machine.. Originally published in Communications of the ACM.

関連項目

• タプル