S 表达式是 Lisp 中的基本存储单元。根据最初的定义,S 表达式是以下两种情况之一。
原子是基本情况。在经典 Lisp(约翰·麦卡锡提出的原始语言)中,原子只是一个独特的单位,我们通常用名称来指定它。从概念上讲,您可以将其视为一个字符串,尽管这不是任何现代 Lisp 内部存储它的方式。所以foobar
是一个原子,所以也是potato
。它们只是字符串atomic,从某种意义上说,它们不再递归地包含任何更多的 S 表达式。
请注意,现代 Lisp 方言扩展了“原子”的定义以包括数字等内容,因此在 Common Lisp 中,1.0
将是代表数字的有效原子。
cons 单元是 Lisp 中组成的基本单位。 cons 单元是指向另外两个 S 表达式的结构。我们将这些 S 表达式中的第一个称为car第二个是cdr。这些名称很古老,最初是指 cons 单元在旧计算机上的存储方式,但如今 Lisp 程序员仍在使用它们。你会听到一些人提到car作为“第一个”或“头”,你会听到有些人提到cdr作为“尾巴”或“休息”。 (尽量不要将 cdr 称为“第二个”术语,因为这是不明确的,并且可能被解释为其他内容,我们稍后会讨论)
Now, we write括号中的 cons 单元格之间有一个点。因此,汽车和 cdr 都是原子的 cons 单元看起来像
(foo . bar)
这是一个细胞,其汽车是原子foo
其 cdr 是原子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
, and c
.
(a . (b . c)) === (a b . c)
再说一次,我没有改变定义。仍然只有两个有效的 S 表达式:原子和 cons 单元。我刚刚发明了一种更紧凑的方式来编写它们。
同样,由于我们将使用NIL
有很多要结束的清单,我们只是将其删除。如果我们有一个NIL
作为 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 代码writing只是一堆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)
is an array的五个元素。它不是一个链表(因为实际上,链表对于随机访问来说很慢),它完全是另一回事。同样,Lisp 方言在基础上添加了新的约定NIL
我们已经讨论过了。在大多数 Lisp 方言中,撇号或单引号用于表示对quote
特殊形式。那是,
'x === (quote x) (quote . (x . NIL))
对于任何 S 表达式x
。不同的方言为原始的 McCarthy 定义添加了不同的功能,但核心概念是:我们需要能够舒适地存储代码的绝对最小定义是什么and我们的 Lisp 程序的数据。