神奇的scheme表结构

scheme并没有提供一种类似数组的数据结构，也没有C++那样的容器、字典，但它却提供了一种特殊的数据结构——表结构。表的基本结构由cons,car,cdr组成，叫作“序对”（pair）。

(define a (cons 1 2))
(car a)
;;=> 1
(cdr a)
;;=> 2

咋看一眼，很像是“字典”那种数据结构，但事实上它们的区别很大，我们可以建立元素本身也是序对的序对，组合起来的数据对象的结果可以通过同样的操作再进行组合，这也就是scheme下的闭包性质。通过闭包性质，我们可以得到一种更强大的构建表结构的操作——list操作。list操作如下：

(define a (list 1 2 3 4))
;;这里ａ就是(1 2 3 4)，该操作相当于：

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

那么cons和list到底有什么区别呢？举个例子说明：

(define a (cons 1 2))
(define b (list 1 2))
(car a)
;;=> 1
(cdr a)
;;=> 2
(car b)
;;=> 1
(cdr b)
;;=> (2)

发现了吧，当对ｂ使用cdr操作时，得到的是个表而不是数值。其实(list 1 2)相当于(cons 1 (cons b nil))，如前文所示，它的结尾有个空表（nil），当你用cdr处理ｂ时，得到的将会是一个表，该表是(b nil)。也就是说，对于一个list，使用cdr操作，一定得到的是一个表而不会是一个数值。这其实就是append的操作原理，append可以将某一元素添加到一个list的后面。

(append (list 1 2) 3)
;;=> (1 2 3)
(append (list 1 2) (list 3 4))
;;=> (1 2 3 4)

append的第一个操作元素必须是个list，它相当于把第一个list的nil指向了下个元素（也可能是下个list的第一个数值）。

表结构有很多我们喜欢的优点，没有复杂的指针，没有捣乱的下标，但是也许你会说，一个长的list，遍历起来岂不是要许多个car,cdr了么？其实scheme提供了很多过程使操作更加方便，我试举一例：

(map (lambda (x) (* x x))
     (list 1 2 3 4))
;;=> (1 4 9 16)

map做了如下事情，先是提取list中的第一个元素，进行平方;接下来将list缩短至(2,3,4)，即取(cdr list)，再提取第一个元素，进行平方;重复该过程，直到list为空。再举一个稍微复杂的例子：

(define lst1 (list 1 2 3 4))
(define lst2 (list 2 3 4 5))

(define test
  (map (lambda (x)
         (map (lambda (y) (+ x y))
		      lst1))
       lst2))

;;=> test
;;=> ((3 4 5 6) (4 5 6 7) (5 6 7 8) (6 7 8 9))

上段代码实现了将lst1中的每个元素依次与lst2中的第一个元素相加，得到一个新的list，再依次与lst2中的第二个元素相加得到第二个list，直到lst2为空，得到4个list。

如果你想要更加复杂的功能，只需更改lambda，再配合map操作，很复杂的过程都可能很简单的实现（SICP中有很多例子，八皇后问题等）。

我们可以想到lisp的命名也是由于表结构吧。

听过这么一个故事:

在 ILC 2002 大会上前Lisp大神，当今的Python倡导者Peter Norvig，由于某些原因，做一个类似于马丁路德在梵蒂冈宣扬新教的主题演讲，因为他在演讲中大胆地声称Python就是一种Lisp。

讲完后进入提问环节，出乎我意料的是，Peter点了我过道另一侧，靠上面几排座位的一个老头，他衣着皱褶，在演讲刚开始的时候踱步进来，然后就靠在了那个座位上面。

这老头满头凌乱的白发，邋遢的白胡须，像是从旅行团中落下的游客，已经完全迷路了，闲逛到这里来歇歇脚，随便看看我们都在这里干什么。我的第一个念头是，他会因为我们的奇怪的话题感到相当失望；接着，我意识到这位老头的年纪，想到斯坦福就在附近，而且我想那人也在斯坦福 —— 难道他是……

“嗨，John，有什么问题？” Peter说。

虽然这只是10个字左右的问题，我不会假装自己记住了Lisp之父约翰麦卡锡说的每一个字。他在问Python程序能不能像处理数据一样，优雅地处理Python代码。

“不行。John, Python做不到。” Peter就回答了这一句，然后静静地等待，准备接受教授的质疑，但老人没有再说什么了。此时，无语已胜千言。

确实，我们发现scheme的代码不就都是括号吗，这不就是用表结构表示代码么，这就是麦肯锡说的，lisp(scheme是lisp的一种方言)可以像处理数据一样处理代码吧。