S表达式

S 表达式是二叉树的一种线性编码，是 Lisp 语言的特色，它让开发者可以像处理数据一样处理代码（代码和数据有相同的表现形式），以此可以构建其他语言无法比拟的宏系统。

二叉树

二叉树是一种经典的树结构，每个节点有两个子节点：

        *
     /     \
   *         *
 /   \     /   \
a     b   c     d

为了表示二叉树结构，人们发明了 点对表示法 ，比如上面的二叉树结构可以这样表示（其中 . 表示一个叶子节点）：

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

而 S 表达式就是点对表示法的形式定义：

为了避免书写过多的点，Lisp 有一套化简规则：

如果一个点号右邻一个左括号，那么就可以将这个点号、左括号以及匹配的右括号一起去掉。
```
(a . (b . c)) <=> (a b . c)
```
如果一个点号右邻 nil，那么就可以把这个点号和 nil 一起去掉。
```
(a . (b . nil)) <=> (a b . nil) <=> (a b)
```

列表是一种特殊类型的 S 表达式，如果一个 S 表达式不是原子，而且经过化简可以把点号都去掉，就称这个 S 表达式为一个列表。

(a . (b . (c . nil))) <=> (a b c)

为了使用方便，还允许有空表，而且定义空表等价于原子 nil。

() <=> nil