hab*_*ing 6 lisp representation data-representation s-expression
所有 Lisp 开发人员似乎都知道什么是 S 表达式。但有人能为非 Lisp 开发者解释一下这一点吗？
已经有一个维基百科条目（https://en.wikipedia.org/wiki/S-expression）。但如果您不想深入了解细节，那么这并没有多大帮助。
什么是 S 表达式？我可以用 S-Expression 表达什么？Lisp 通常使用 S 表达式的目的是什么？S 表达式只与 Lisp 开发人员相关吗？
S 表达式是 Lisp 中的基本存储单元。根据最初的定义，S 表达式是以下两种情况之一。
原子是基本情况。在经典 Lisp（约翰·麦卡锡提出的原始语言）中，原子只是一个独特的单位，我们通常用名称来指定它。从概念上讲，您可以将其视为一个字符串，尽管这不是任何现代 Lisp 内部存储它的方式。foobar原子也是如此， 也是如此potato。它们只是原子字符串，因为它们不再递归地包含任何 S 表达式。
请注意，现代 Lisp 方言扩展了“原子”的定义以包括数字等内容，因此在 Common Lisp 中，“原子”1.0将是代表数字的有效原子。
cons 单元是 Lisp 中组成的基本单位。cons 单元是指向另外两个 S 表达式的结构。我们将这些 S 表达式中的第一个称为car，将第二个称为cdr。这些名称很古老，最初是指 cons 单元在旧计算机上的存储方式，但如今 Lisp 程序员仍在使用它们。您会听到有些人将汽车称为“第一”或“头”，并且您会听到有些人将 cdr 称为“尾”或“其余”。（尽量不要将 cdr 称为“第二个”术语，因为这是不明确的，并且可能被解释为其他内容，我们稍后会讨论）
现在，我们将 cons 单元格写在括号中，并在它们之间加一个点。因此，汽车和 cdr 都是原子的 cons 单元看起来像
(foo . bar)
这是一个 cons 单元，其 car 是atom foo，其 cdr 是atom bar。我们还可以嵌套 con 单元格。
((foo . bar) . (baz . potato))
然后我们最终得到一种类似二叉树的结构，其中每个分支都有一个左分支和一个右分支（用我们的术语来说是一辆汽车和一个 cdr），每个叶子都是一个原子。
那么我们能用这个做什么呢？嗯，一方面，我们可以存储链接列表。有多种方法可以做到这一点，但 Lisp 社区的流行惯例是使用 car 来存储当前值，并使用 cdr 来存储指向列表其余部分的 cons 单元。然后，当我们到达列表的末尾时（null如果我们在 C 或 Java 中执行此操作，我们可能会在其中存储指针），我们会挑选一个特定的原子，称为NIL。NIL上面定义中的原子没有什么特别之处；我们只是挑选了一个，因为我们需要一个作为约定。
因此，为了表示列表[a, b, c, d]，我们将其存储为
(a . (b . (c . (d . NIL))))
最外面的 cons 单元格的汽车是列表的第一个元素，或a。cdr 存储列表的其余部分。cdr的汽车是第二个元素，b，以此类推。（这就是为什么我说不要将 cdr 称为“第二”元素，因为“第二”通常用来表示“cdr 的汽车”）
事实上，我们经常这样做，以至于 Lisp 中还有另一种符号约定。如果 cdr 是另一个 cons 单元，那么我们只需删除.和 括号即可理解它的含义。因此，一般来说，对于任何 S 表达式a、b和 ，我们说以下两个是等价的c。
(a . (b . c)) === (a b . c)
再说一次，我没有改变定义。仍然只有两个有效的 S 表达式：原子和 cons 单元。我刚刚发明了一种更紧凑的方式来编写它们。
同样，由于我们将使用NIL很多结束列表，因此我们只需删除它即可。如果我们有 aNIL作为 cons 单元的 cdr，那么按照惯例，我们删除.和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 中，它为 的每个元素加一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 方言在我们已经讨论过的约定之上添加了新的约定。在大多数 Lisp 方言中，撇号或单引号用于表示对特殊形式的调用。那是，NILquote
'x === (quote x) == (quote . (x . NIL))
对于任何 S 表达式x。不同的方言为原始的 McCarthy 定义添加了不同的功能，但核心概念是：我们需要能够舒适地存储Lisp 程序的代码和数据的绝对最小定义是什么。
术语S 表达式是指 Lisp 对象的打印形式。例如，整数零对象可以显示为书面 S 表达式0，如000、 或#x0。文本(0 . 1)是表示 cons 单元对象的 S 表达式，其字段为整数 0 和 1。在 Common Lisp 中，在默认读取表下，标记Foo、fOO、和, 都是表示相同符号FOO的S 表达式。它们是不同的读取语法，通过表示同一对象的语义是等效的。|FOO|foo
为什么我们不把这些东西称为表达式呢？首先，有时我们会这样做，从上下文中可以清楚地看出我们正在谈论字符语法。由于这个原因，术语“表达式”是不明确的：它有时可以指文本的、打印的表达式，例如，某人键入文本文件或交互式侦听器。大多数时候，表达式指的是内存中表示代码的 Lisp 对象。
我们可以说打印表达式而不是S 表达式，但这个术语在历史上是根深蒂固的，可以追溯到 Lisp 也有M 表达式的时候。另外，只有当我们知道我们已经在谈论 Lisp 之外的任何内容时，打印表达式才具有与S 表达式相同的含义。Lisp 之外的上下文中的术语S 表达式意味着“来自 Lisp 系列的打印对象符号之一，其符号不带引号，嵌套列表带有括号，其中项仅由空格分隔”。
请注意，ANSI Common Lisp 标准不使用术语S 表达式或符号表达式。术语表中没有出现此类术语，只有表达式，其定义如下：
表达式n. 1. 对象，通常用于强调使用对象以专门的格式编码或表示信息，例如程序文本。“let 形式中的第二个表达式是绑定列表。” 2. 用于标记源文件中的对象的文本标记。“表达式‘样本相当于（引用样本）。”
S 表达式或多或少是 (2) 的含义，具有历史联系，并且在任何一种 Lisp 方言之外都有更广泛的解释。例如，Ron Rivest，他最出名的身份可能是 RSA 密码系统的作者之一。撰写了一份互联网草案，描述了一种用于数据交换的 S 表达式形式。