什么是S表达式？

Question

所有Lisp开发者似乎都知道什么是S-Expression，但有谁能为非Lisp开发者解释一下这个概念吗？

已经有一个维基百科条目了（https://en.wikipedia.org/wiki/S-expression），但是如果你不想深入了解，那并没有什么帮助。

什么是S-Expression？我可以用S-Expression表达什么？Lisp通常使用S-Expression的目的是什么？S-Expression只与Lisp开发者相关吗？

- habrewning

---

任何语言中代表一个值的代码都是一个表达式。Lisp 代码只是由元素组成的列表，这是 Lisp 中的一个基本数据结构。然而计划是使用类似于 Java 和 Python 的语法（m-表达式），但最初版本只是将代码以数据形式进行评估，这被称为 s-表达式。S-表达式生成的结构化树与其他语言解析器生成的树结构非常相似，因此在 Lisp 语言中，人们可以说代码和 AST 是同一件事情。 - Sylwester

Answer 1

S表达式是Lisp中存储的基本单元。按照原始定义，S表达式指的是以下两种情况之一：

- 原子（atom）。 - cons单元。

原子是基本情况。在经典Lisp（由John McCarthy最初提出的语言）中，原子仅仅是一个我们约定俗成用名称标志的不同单元。从概念上讲，你可以把它看作字符串，尽管任何现代Lisp都不会以这种方式在内部存储它。因此，“foobar”和“potato”都是原子。它们只是被称为是“原子”的字符串，意思是它们不会递归地包含任何更多的S表达式。

需要注意的是，现代Lisp方言扩展了“原子”的定义以包括数字等内容。因此，在Common Lisp中，“1.0”将是一个有效的代表数字的原子。

cons单元是Lisp中组合的基本单元。cons单元是指向其他两个S表达式的结构。我们称其中第一个S表达式为car，第二个S表达式为cdr。这些名称已经过时，最初是指对老式计算机上的cons单元的存储方式，但今天的Lisp程序员仍然沿用它们。你会听到有些人将car称为“first”或“head”，将cdr称为“tail”或“rest”（尽量不要将cdr称为“second”项，因为这是模棱两可的，可能会被解释为其他内容，我们稍后会讨论）。

现在，我们用括号和点号将cons单元写入。因此，一个car和cdr都是原子的cons单元看起来像：

(foo . bar)

这是一个cons单元，其car是原子foo，cdr是原子bar。我们还可以嵌套cons单元。

((foo . bar) . (baz . potato))

然后我们得到了一种类似于二叉树的结构，其中每个分支都有左右（在我们的术语中是 car 和 cdr），而每个叶子则是一个原子。

那么我们可以拿这个结构做什么呢? 首先，我们可以存储链表。有几种方法可以实现，但Lisp社区中普遍的约定是使用car来存储当前值，而cdr则存储指向列表剩余部分的cons单元。然后，当我们到达列表的末尾（如果我们在C或Java中执行此操作，可能会存储一个null指针），我们会选择一个特定的原子，称为NIL。上面的定义中，NIL原子没有什么特别之处；我们只是挑选它作为惯例。

所以，要表示列表[a, b, c, d]，我们将其存储为：

(a . (b . (c . (d . NIL))))

最外一层 cons cell 的 car 是列表中的第一个元素，即 a。cdr 存储了列表的其余部分。cdr 的 car 是第二个元素 b，以此类推。（这就是为什么我说不要将 cdr 称为“第二”个元素，因为“第二”通常用来表示“cdr 的 car”）

事实上，我们经常这样做，以至于 Lisp 中还有另一种符号惯例。如果 cdr 是另一个 cons cell，则我们简单地删除 . 和括号并理解其含义。因此，通常情况下，对于任何 S 表达式 a、b 和 c，以下两个表达式等价。

(a . (b . c)) === (a b . c)

我并未更改定义，仍然只有两种有效的S表达式：原子和cons cell。我只是发明了一种更紧凑的写法。

同样地，由于我们将经常使用NIL来结束列表，因此我们可以简单地删除它。如果我们在cons单元格的cdr中有一个NIL，那么根据惯例，我们会去掉 . 和NIL。对于任何S表达式a，以下写法是等效的。

(a . NIL) === (a)

再次说明，我只是在创造一种新的紧凑写法，而不是改变定义。

最后，作为一种符号上的便利，我们可能有时会将原子NIL写成一对空括号，因为它应该看起来像一个空列表。

NIL === ()

现在，回顾一下我们之前列出的清单

(a . (b . (c . (d . NIL))))

我们可以使用这些规则来简化它

(a . (b . (c . (d . NIL))))
(a b . (c . (d . NIL)))
(a b c . (d . NIL))
(a b c d . NIL)
(a b c d)

现在这看起来非常像Lisp语法。这就是S表达式的优美之处。你所编写的Lisp代码只是一堆S表达式。例如，考虑下面的Lisp代码：

(mapcar (lambda (x) (+ x 1)) my-list)

以下是普通的Lisp代码，这种代码在任何日常程序中都能看到。在Common Lisp中，它将1添加到my-list的每个元素上。但美妙之处在于它只是一个大的S表达式。如果我们移除所有的语法糖，就得到了：

(mapcar . ((lambda . ((x . NIL) . ((+ . (x . (1 . NIL))) . NIL))) . (my-list . NIL)))

至少在美学上并不好看，但现在更容易看出这实际上只是一堆细胞与原子结尾的列表。你整个Lisp语法树就是那样：一个充满代码的二叉树。而且你可以像操作数据结构一样操作它。你可以编写接受该树作为数据结构的宏，并对其进行任何操作。你的Lisp程序的抽象语法树不是语言内部的不透明构造；它只是一棵树：一种非常简单的数据结构，在日常编程中已经使用了。你在Lisp程序中用来存储数据的相同列表和其他结构也用于存储代码。

现代Lisp方言通过新的约定和在某些情况下引入新的数据类型来扩展此功能。例如，Common Lisp添加了一个数组类型，因此#(1 2 3 4 5)是一个由五个元素组成的数组。它不是链表（由于在实践中，链表随机访问速度较慢），它完全是另一种东西。同样，Lisp方言在我们已经讨论过的NIL之上添加了新的约定。在大多数Lisp方言中，撇号或单引号用于表示对quote特殊形式的调用。

'x === (quote x) (quote . (x . NIL))

对于任何S表达式x，不同的方言会向原始的McCarthy定义添加不同的特性，但核心概念是：我们需要什么绝对最少的定义来舒适地存储Lisp程序的代码和数据。

- Silvio Mayolo

Answer 2

术语“S表达式”指的是Lisp对象的打印形式。例如，整数零对象可以出现为书面S表达式，如0、000或#x0。文本(0 . 1)是表示cons单元对象的S表达式，其字段是整数零和一。在Common Lisp中，在默认读取表下，标记Foo、fOO、FOO、|FOO|和foo都是表示相同符号的S表达式。它们是不同的读取语法，通过它们表示相同对象的语义等效。

为什么我们不直接称呼这些为表达式呢？首先，有时候我们确实会这样做，当从上下文清楚地知道我们正在谈论字符语法时。由于这个原因，“表达式”这个术语是有歧义的：它有时可以指一个文本上的打印表达式，例如，某人键入到文本文件或交互式监听器中。大多数情况下，“表达式”指的是表示代码的Lisp对象。

我们可以使用“打印表达式”来代替“S表达式”，但这个术语在历史上已经根深蒂固，可以追溯到Lisp还有“M表达式”的时候。此外，“打印表达式”只有在我们知道我们正在谈论的是Lisp时才与“S表达式”具有相同的含义。在Lisp之外的上下文中，“S表达式”的术语意味着“来自Lisp家族的一种打印对象表示法之一，其中符号不带引号，嵌套列表用括号分隔，其中项目仅由空格分隔”。

请注意，ANSI Common Lisp标准不使用“S表达式”或“符号表达式”这些术语。词汇表中没有出现这样的术语，只有“表达式”，其定义如下：

“表达式”n. 1.一个对象，通常用于强调对象的使用，以便使用该对象以特定格式编码或表示信息，例如程序文本。“在let形式中的第二个表达式是绑定列表。”2.用于在源文件中表示对象的文本符号。“表达式‘sample等效于(quote sample)’”。

S表达式或多或少是指具有历史联系和更广泛解释的含义，超出了任何一个Lisp方言。例如，Ron Rivest，也许最知名的RSA加密系统作者之一，写了一篇互联网草案，描述了一种用于数据交换的S表达式形式。

- Kaz

---

我可以用S-表达式表达什么？Lisp通常使用S-表达式的目的是什么？S-表达式只与Lisp开发人员相关吗？为什么有一个互联网标准草案，它只在一种编程语言中使用？ - habrewning

@habrewning S表达式可用于通信和存储结构化数据，类似于JSON和XML。Lisp不是一种编程语言，而是一个家族。Common Lisp有自己的S表达式，Scheme也是如此，不同的方言有自己的扩展：例如Gauche Scheme和Chicken Scheme的S表达式并不完全相同。对于语言和平台无关的通信，您肯定需要一些标准。看看JSON，它是与Javascript分开规范的。 - Kaz

Answer 3

其他答案都很特定于Lisp，但实际上S表达式在Lisp世界之外也很有用。

S表达式是表示树的一种（方便的）方式，其叶子是符号（名称、字符串等）。每个S表达式的括号部分都是一个节点，包含其子节点列表。

例如：(this (s expression) (could (be represented)) as (this tree))

       [..........]
       /|   | |  |
      / .   | as .
     / / \  |   / \
    /  s |  . this |
  this   |  |\    tree
         |  | \
 expression |  \
          could .
                |\
               be represented

在Lisp中，由S表达式表示的树对应于具体语法树，这就是为什么Lisp如此易于解析的原因。

然而，由于这种树的表示方式很方便（它相对紧凑，非常人性化，对于机器来说解析和生成都很直观），因此它也被用于其他上下文。例如，Ocaml的Core库（它是该语言的另一种标准库）提供了S表达式的序列化和反序列化功能。

此外，Lisp还将其某些数据结构命名为S表达式。这与Lisp的同像性很搭配，即代码可以像数据一样被操作。

因此，回答你的问题：

• S表达式既是一种表示树的语法方式，也是Lisp中一种树形数据结构。
• 使用S表达式可以表达树形结构；您为树形结构附加的含义（如果您愿意，可以称之为其解释）不特定于S表达式。S表达式告诉您如何编写树形结构，而不是它的含义 - 实际上，人们会将其用于不同的目的，具有不同的含义。
• Lisp使用S表达式来表示自己的源代码，打印值并作为数据结构，从nil和cons递归构建（所有Lisp方言的确切细节都有很大差异）。
• S表达式不仅对Lisp开发人员有影响，例如，Ocaml序列化/反序列化库Sexp也使用了S表达式。实际上，在可以使用S表达式的地方，更常用的是具有更强类型的其他表示数据的方式，例如JSON。

- jthulhu

---

OCaml对S表达式的定义非常狭窄（只能是字符串或表达式列表），这可能是你说它们不适用于表示更强类型值（如JSON，其中包含数字和字典）的原因，但对我来说这是无关紧要的；首先，有关S表达式的定义可以嵌入各种类型的原子，其次，即使只有字符串，你仍然可以附加类型元数据：((map string single-float) (a 1e12) (b 0.5)) 是一种有效的表示从字符串到浮点数值的哈希映射的方式。 - coredump

@coredump 这不是我想表达的意思：在JSON中，“6”无论如何都是一个字符串，而6是一个数字；而在S表达式中，没有办法区分数字和字符串，除非“解释”它。但我的观点更多是：JSON比S表达式更常用，其中一个原因可能是需要（至少在某种程度上）解释S表达式以理解所表示数据的“类型”。OCaml决定将它们解释为字符串树并不是我的重点。 - jthulhu

OCaml只是S表达式在Lisp之外被使用的一个例子。 - jthulhu

使用S表达式时，没有办法在不“解释”它的情况下区分数字和字符串：这取决于您对S-expr的定义；如果您的S-expr定义是一个字符串树，则是；如果您支持更多类型，则不是，您可以有一个专用的@2022-10-24T16:24:12.913732Z语法来读取日期（JSON没有这个功能）。所以我认为我的观点是，S-expr被相当宽泛地用来谈论许多事情；至少有一次尝试规范化格式：http://people.csail.mit.edu/rivest/Sexp.txt，这有点像JSON RFC。 - coredump

我认为在s表达式中，数字6表示为6，字符串6表示为"6"。 - Rainer Joswig

Answer 4

s表达式是符号表达式的缩写。

基本上，它们是符号和符号嵌套列表。

一个符号由字母数字字符构成。

符号和符号嵌套列表的示例：

foo
berlin
fruit
de32211
(apple peach)
(fruit (seller fruit-co))
((apple one) (peach two))

这些列表由cons单元组成，表示为(one . two)，而空列表则表示为nil。

例如：

(a . (b . nil))  -> (a b)
((a . nil) (b . nil))   -> ((a) (b))

编程语言Lisp（缩写为List Processor）被设计用于处理这些列表。Lisp包含各种基本操作来处理嵌套列表。s表达式的元素也可以是数字、字符、字符串、数组和其他数据结构。

符号表达式与JSON和XML具有相同的目的：它们编码数据。

Lisp中的符号表达式也用于编码Lisp程序本身。

示例：

((lambda (a b)
   (+ a (* 2 b)))
 10
 20)

上面的内容既是s表达式，也是有效的Common Lisp / Scheme程序。

符号表达被认为是一种通用符号，可以让人类和机器在某些计算中读取/编写/处理各种数据。例如，s表达式可以对数学公式、Lisp程序、逻辑表达式或规划问题配置数据进行编码。当时缺少的是一种描述声明性有效数据模式的方法。s表达式通常是过程化地处理和验证的。

s表达式在Lisp中如何使用？

- 用于编码源代码 - 用于各种数据 - 混合源代码和数据

s表达式仅与Lisp开发人员相关吗？

大多数情况下是这样，但有时代码或数据以s表达式的形式存在，并且使用其他语言编写的程序想要处理此数据。有时甚至不使用Lisp的开发人员也选择s表达式作为数据表示格式。

总的来说，在Lisp之外使用s表达式的情况很少。尽管如此，还是有一些例子。 XML和JSON比s表达式更受欢迎。

- Rainer Joswig

---

如果你解释一下“cons”单元是什么，或者以某种方式解释一下这个例子(a . (b . nil)) -> (a b)的意思，或者也许你移除这个例子，我都会接受这个答案。 - undefined