第三章 生成表

3.1?簡介

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

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

3.2?Cons單元和表

3.2.1?Cons單元

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

在前端輸入(cons 1 2)

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

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

一個Cons單元

Cons單元也可以被串起來。

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

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

串連Cons單元

Cons單元可以存放不同類型的數(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)

這是因為Scheme可以通過地址操作所有的數(shù)據(jù)。（#\c代表了一個字符c。例如，#\a就代表字符a）

3.2.2?表

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

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

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

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

3.3?原子

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

練習(xí)1

使用cons來構(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?引用

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

例如，(+ 2 3)會被求值為5，然而(quote (+ 2 3))則向程序返回(+ 2 3)本身。因為quote的使用頻率很高，他被簡寫為’。

比如：

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

實際上，’()是對空表的引用，也就是說，盡管解釋器返回()代表空表，你也應(yīng)該用’()來表示空表。

3.4.1?特殊形式

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

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

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

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

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

練習(xí)2

求值下列S-表達式。

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ù)個元素的表。函數(shù)list有任意個數(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)心前三章有些無趣。我希望下一章能有趣點，它主要講述了如何編寫函數(shù)。我也會講解如何用編輯器來編輯代碼，如何將代碼加載到解釋器中，以及如何定義函數(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)