[TOC=2] ## 3.1?簡介 作為Lisp語言大家族的一員，Scheme同樣擅長于處理表。你應該理解表以及有關表的操作以掌握Scheme。表在在后面章節中的遞歸函數和高階函數中扮演重要角色。 在本章中，我會講解基本的表操作，例如`cons`，`car`，`cdr`，`list`和`quote`。 ## 3.2?Cons單元和表 ### 3.2.1?Cons單元 首先，讓我解釋一下表的元素：**Cons單元（Cons cells）**。Cons單元是一個存放了兩個地址的內存空間。Cons單元可用函數`cons`生成。 在前端輸入`(cons 1 2)` ~~~ (cons 1 2) ;Value 11: (1 . 2) ~~~ 系統返回`(1 . 2)`。如圖一所示，函數`cons`給兩個地址分配了內存空間，并把存放指向`1`的地址放在一個空間，把存放指向`2`的地址放在另一個空間。存放指向`1`的地址的內存空間被稱作`car`部分，對應的，存放指向`2`的地址的內存空間被稱作`cdr`部分。`car`和`cdr`分別是**寄存器地址部分（Contents of the Address part of the Register）**和**寄存器減量部分（Contents of the Decrement part of the Register）**的簡稱。這些名字最初來源于Lisp首次被實現所使用的硬件環境中內存空間的名字。這些名字同時也表明Cons單元的本質就是一個內存空間。`cons`這個名字是術語**構造（construction）**的簡稱。  一個Cons單元 Cons單元也可以被串起來。 ~~~ (cons 3 (cons 1 2)) ;Value 15: (3 1 . 2) ~~~ ·(3 . (1 . 2))·可以更方便地表示為`(3 1 . 2)`。這種情況的內存空間如圖2所示。  串連Cons單元 Cons單元可以存放不同類型的數據，也可以嵌套。 ~~~ (cons #\a (cons 3 "hello")) ;Value 17: (#\a 3 . "hello") (cons (cons 0 1) (cons 1 2)) ;Value 23: ((0 . 1) 1 . 2) ~~~ 這是因為Scheme可以通過地址操作所有的數據。（`#\c`代表了一個字符`c`。例如，`#\a`就代表字符`a`） ### 3.2.2?表 表是Cons單元通過用`cdr`部分連接到下一個`Cons`單元的開頭實現的。表中包含的`’()`被稱作空表。就算數據僅由一個Cons單元組成，只要它的`cdr`單元是`’()`，那它就是一個表。圖3展示了表`(1 2 3)`的內存結構。  表(1 2 3)的內存結構 事實上，表可以像下面這樣遞歸地定義： 1. `‘()`是一個表 2. 如果`ls`是一個表且`obj`是某種類型的數據，那么`(cons obj ls)`也是一個表 正因為表是一種被遞歸定義的數據結構，將它用在遞歸的函數中顯然是合理的。 ## 3.3?原子 不使用Cons單元的數據結構稱為**原子（atom）**。數字，字符，字符串，向量和空表`’()`都是原子。`’()`既是原子，又是表。 > 練習1 > > 使用`cons`來構建在前端表現為如下形式的數據結構。 > > 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?引用 所有的記號都會依據Scheme的求值規則求值：所有記號都會從最內層的括號依次向外層括號求值，且最外層括號返回的值將作為S-表達式的值。一個被稱為**引用（quote）**的形式可以用來阻止記號被求值。它是用來將符號或者表原封不動地傳遞給程序，而不是求值后變成其它的東西。 例如，`(+ 2 3)`會被求值為`5`，然而`(quote (+ 2 3))`則向程序返回`(+ 2 3)`本身。因為`quote`的使用頻率很高，他被簡寫為`’`。 比如： * `’(+ 2 3)`代表列表`(+ 2 3)`本身； * `’+`代表符號`+`本身； 實際上，`’()`是對空表的引用，也就是說，盡管解釋器返回`()`代表空表，你也應該用`’()`來表示空表。 ### 3.4.1?特殊形式 Scheme有兩種不同類型的操作符：其一是函數。函數會對所有的參數求值并返回值。另一種操作符則是特殊形式。特殊形式不會對所有的參數求值。除了`quote`，`lambda`，`define`，`if`，`set!`，等都是特殊形式。 ## 3.5?car函數和cdr函數 返回一個Cons單元的`car`部分和`cdr`部分的函數分別是`car`和`cdr`函數。如果`cdr`部分串連著Cons單元，解釋器會打印出整個`cdr`部分。如果Cons單元的`cdr`部分不是`’()`，那么其值稍后亦會被展示。 ~~~ (car '(1 2 3 4)) ;Value: 1 (cdr '(1 2 3 4)) ;Value 18: (2 3 4) ~~~ > 練習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函數 `list`函數使得我們可以構建包含數個元素的表。函數`list`有任意個數的參數，且返回由這些參數構成的表。 ~~~ (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?小結 本章講解了表和表的基本操作。我擔心前三章有些無趣。我希望下一章能有趣點，它主要講述了如何編寫函數。我也會講解如何用編輯器來編輯代碼，如何將代碼加載到解釋器中，以及如何定義函數。 ## 3.8?習題解答 ### 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) ~~~