第三章 生成表

3.1?簡(jiǎn)介

作為L(zhǎng)isp語(yǔ)言大家族的一員，Scheme同樣擅長(zhǎng)于處理表。你應(yīng)該理解表以及有關(guān)表的操作以掌握Scheme。表在在后面章節(jié)中的遞歸函數(shù)和高階函數(shù)中扮演重要角色。

在本章中，我會(huì)講解基本的表操作，例如cons，car，cdr，list和quote。

3.2?Cons單元和表

3.2.1?Cons單元

首先，讓我解釋一下表的元素：Cons單元（Cons cells）。Cons單元是一個(gè)存放了兩個(gè)地址的內(nèi)存空間。Cons單元可用函數(shù)cons生成。

在前端輸入(cons 1 2)

(cons 1 2)
;Value 11: (1 . 2)

系統(tǒng)返回(1 . 2)。如圖一所示，函數(shù)cons給兩個(gè)地址分配了內(nèi)存空間，并把存放指向1的地址放在一個(gè)空間，把存放指向2的地址放在另一個(gè)空間。存放指向1的地址的內(nèi)存空間被稱(chēng)作car部分，對(duì)應(yīng)的，存放指向2的地址的內(nèi)存空間被稱(chēng)作cdr部分。car和cdr分別是寄存器地址部分（Contents of the Address part of the Register）和寄存器減量部分（Contents of the Decrement part of the Register）的簡(jiǎn)稱(chēng)。這些名字最初來(lái)源于Lisp首次被實(shí)現(xiàn)所使用的硬件環(huán)境中內(nèi)存空間的名字。這些名字同時(shí)也表明Cons單元的本質(zhì)就是一個(gè)內(nèi)存空間。cons這個(gè)名字是術(shù)語(yǔ)構(gòu)造（construction）的簡(jiǎn)稱(chēng)。

一個(gè)Cons單元

Cons單元也可以被串起來(lái)。

(cons 3 (cons 1 2))
;Value 15: (3 1 . 2)

·(3 . (1 . 2))·可以更方便地表示為(3 1 . 2)。這種情況的內(nèi)存空間如圖2所示。

串連Cons單元

Cons單元可以存放不同類(lèi)型的數(shù)據(jù)，也可以嵌套。

(cons #\a (cons 3 "hello"))
;Value 17: (#\a 3 . "hello")

(cons (cons 0 1) (cons 1 2))
;Value 23: ((0 . 1) 1 . 2)

這是因?yàn)镾cheme可以通過(guò)地址操作所有的數(shù)據(jù)。（#\c代表了一個(gè)字符c。例如，#\a就代表字符a）

3.2.2?表

表是Cons單元通過(guò)用cdr部分連接到下一個(gè)Cons單元的開(kāi)頭實(shí)現(xiàn)的。表中包含的’()被稱(chēng)作空表。就算數(shù)據(jù)僅由一個(gè)Cons單元組成，只要它的cdr單元是’()，那它就是一個(gè)表。圖3展示了表(1 2 3)的內(nèi)存結(jié)構(gòu)。

表(1 2 3)的內(nèi)存結(jié)構(gòu)

事實(shí)上，表可以像下面這樣遞歸地定義：

1. ‘()是一個(gè)表
2. 如果ls是一個(gè)表且obj是某種類(lèi)型的數(shù)據(jù)，那么(cons obj ls)也是一個(gè)表 正因?yàn)楸硎且环N被遞歸定義的數(shù)據(jù)結(jié)構(gòu)，將它用在遞歸的函數(shù)中顯然是合理的。

3.3?原子

不使用Cons單元的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為原子（atom）。數(shù)字，字符，字符串，向量和空表’()都是原子。’()既是原子，又是表。

練習(xí)1

使用cons來(lái)構(gòu)建在前端表現(xiàn)為如下形式的數(shù)據(jù)結(jié)構(gòu)。

1. ("hi" . "everybody")
2. (0)
3. (1 10 . 100)
4. (1 10 100)
5. (#\I "saw" 3 "girls")
6. ("Sum of" (1 2 3 4) "is" 10)

3.4?引用

所有的記號(hào)都會(huì)依據(jù)Scheme的求值規(guī)則求值：所有記號(hào)都會(huì)從最內(nèi)層的括號(hào)依次向外層括號(hào)求值，且最外層括號(hào)返回的值將作為S-表達(dá)式的值。一個(gè)被稱(chēng)為引用（quote）的形式可以用來(lái)阻止記號(hào)被求值。它是用來(lái)將符號(hào)或者表原封不動(dòng)地傳遞給程序，而不是求值后變成其它的東西。

例如，(+ 2 3)會(huì)被求值為5，然而(quote (+ 2 3))則向程序返回(+ 2 3)本身。因?yàn)?code>quote的使用頻率很高，他被簡(jiǎn)寫(xiě)為’。

比如：

• ’(+ 2 3)代表列表(+ 2 3)本身；
• ’+代表符號(hào)+本身；

實(shí)際上，’()是對(duì)空表的引用，也就是說(shuō)，盡管解釋器返回()代表空表，你也應(yīng)該用’()來(lái)表示空表。

3.4.1?特殊形式

Scheme有兩種不同類(lèi)型的操作符：其一是函數(shù)。函數(shù)會(huì)對(duì)所有的參數(shù)求值并返回值。另一種操作符則是特殊形式。特殊形式不會(huì)對(duì)所有的參數(shù)求值。除了quote，lambda，define，if，set!，等都是特殊形式。

3.5?car函數(shù)和cdr函數(shù)

返回一個(gè)Cons單元的car部分和cdr部分的函數(shù)分別是car和cdr函數(shù)。如果cdr部分串連著Cons單元，解釋器會(huì)打印出整個(gè)cdr部分。如果Cons單元的cdr部分不是’()，那么其值稍后亦會(huì)被展示。

(car '(1 2 3 4))
;Value: 1

(cdr '(1 2 3 4))
;Value 18: (2 3 4)

練習(xí)2

求值下列S-表達(dá)式。

1. (car '(0))
2. (cdr '(0))
3. (car '((1 2 3) (4 5 6)))
4. (cdr '(1 2 3 . 4))
5. (cdr (cons 3 (cons 2 (cons 1 '()))))

3.6?list函數(shù)

list函數(shù)使得我們可以構(gòu)建包含數(shù)個(gè)元素的表。函數(shù)list有任意個(gè)數(shù)的參數(shù)，且返回由這些參數(shù)構(gòu)成的表。

(list)
;Value: ()

(list 1)
;Value 24: (1)

(list '(1 2) '(3 4))
;Value 25: ((1 2) (3 4))

(list 0)
;Value 26: (0)

(list 1 2)
;Value 27: (1 2)

3.7?小結(jié)

本章講解了表和表的基本操作。我擔(dān)心前三章有些無(wú)趣。我希望下一章能有趣點(diǎn)，它主要講述了如何編寫(xiě)函數(shù)。我也會(huì)講解如何用編輯器來(lái)編輯代碼，如何將代碼加載到解釋器中，以及如何定義函數(shù)。

3.8?習(xí)題解答

3.8.1?答案1

;1
(cons "hi" "everybody")
;Value 32: ("hi" . "everybody")

;2
(cons 0 '())
;Value 33: (0)

;3
(cons 1 (cons 10 100))
;Value 34: (1 10 . 100)

;4
(cons 1 (cons 10 (cons 100 '())))
;Value 35: (1 10 100)

;5
(cons #\I (cons "saw" (cons 3 (cons "girls" '()))))
;Value 36: (#\I "saw" 3 "girls")

;6
(cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 '())))) (cons "is" (cons 10 '()))))
;Value 37: ("Sum of" (1 2 3 4) "is" 10)

3.8.2?答案2

;1
(car '(0))
;Value: 0

;2
(cdr '(0))
;Value: ()

;3
(car '((1 2 3) (4 5 6)))
;Value 28: (1 2 3)

;4
(cdr '(1 2 3 . 4))
;Value 29: (2 3 . 4)

;5
(cdr (cons 3 (cons 2 (cons 1 '()))))
;Value 31: (2 1)