第一章 構造過程抽象

心智的活動， 除了盡力生産各種簡單的認識之外，主要表現在如下三個方面：

1）

将若幹簡單的認識組合為一個複合的認識， 由此産生出各種複雜的認識。

2）将兩個認識放在一起對照，不管它們如何簡單或者複雜，在這樣做時并不将它們合而為一。由此得到有關它們的互相關系的認識。

3）将有關認識與那些在實際中和它們同在的所有其他認識隔離開，這就是抽象，所有具有普遍性的認識都是這樣得到的。

​ -- John Locke. （有關人類了解的随筆， 1690）

Lisp 語言包含了 9 種思想

1. 條件結構（即"if-then-else"結構）。現在大家都覺得這是理所當然的，但是 Fortran I 就沒有這個結構，它隻有基于底層機器指令的 goto 結構。
2. 函數也是一種資料類型。在 Lisp 語言中，函數與整數或字元串一樣，也屬于資料類型的一種。它有自己的字面表示形式（literal representation），能夠儲存在變量中，也能當作參數傳遞。一種資料類型應該有的功能，它都有。
3. 遞歸。Lisp 是第一種支援遞歸函數的進階語言。
4. 變量的動态類型。在 Lisp 語言中，所有變量實際上都是指針，所指向的值有類型之分，而變量本身沒有。複制變量就相當于複制指針，而不是複制它們指向的資料。
5. 垃圾回收機制。
6. 程式由表達式（expression）組成。Lisp 程式是一些表達式區塊的集合，每個表達式都傳回一個值。這與 Fortran 和大多數後來的語言都截然不同，它們的程式由表達式和語句（statement）組成。區分表達式和語句，在 Fortran I 中是很自然的，因為它不支援語句嵌套。是以，如果你需要用數學式子計算一個值，那就隻有用表達式傳回這個值，沒有其他文法結構可用，因為否則就無法處理這個值。
7. 符号（symbol）類型。符号實際上是一種指針，指向儲存在哈希表中的字元串。是以，比較兩個符号是否相等，隻要看它們的指針是否一樣就行了，不用逐個字元地比較。
8. 代碼使用符号和常量組成的樹形表示法。
9. 無論什麼時候，整個語言都是可用的。Lisp 并不真正區分讀取期、編譯期和運作期。你可以在讀取期編譯或運作代碼；也可以在編譯期讀取或運作代碼；還可以在運作期讀取或者編譯代碼。

應用序與正則序

正則序： 解釋器首先對運算符和各個運算對象求值，而後将得到的過程應用于實際的參數。舉個粒子：

預先定義：

(define (square x)
    (* x x))
(define (sum-of-squares x y)
    (+ (square x) (square y)))
(define (f a)
(sum-of-squares (+ a 1) (+ a 2)))
           

求表達式 (f, 5) 的值。

(sum-of-squares (+ 5 1) (+ 5 2))
(+ (square (+ 5 1)) (square (+ 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (+ 5 2) (+ 5 2)))
(+ (* 6 6) (* 7 7))
(+ 36 49)
85
           

這種“完全展開而後歸約”的求值模型稱為正則序求值。與之相對的是現代解釋器采用的是先求值參數而後應用的方式，它稱為應用序求值。

條件表達式和謂語

(cond (<e1> <p1>)
(<e2> <p2>)
..
(<en> <pn>))
           

(if <pred> <conse> <alter>)
(and <e1> <e2> ...<en>)
(or <e1> <e2> ... <en>)
(not <e>)
           

執行個體

Ben 發明了一種方法檢測解釋器采用哪種方式求值，他定義了一個過程：

(define (p) (p))
(define (test x y)
(if (= 0 x)
    0
    y))
           

而後他求下面表達式的值：

(test 0 (p))
           

如果解釋器采用應用序求值， Ben 将會看到什麼？ 如果解釋器采用正則器求值， Ben 又會看到什麼？假設 if 語句在兩種求值方式中的規則是一樣的， 即謂詞總是先被執行。

答： 如果解釋器采用應用序求值， 那麼必須知道表達式 (p) 的值， (p) 是一個調用自己的函數。

(test 0 (p))
(test 0 (p))
...
           

反之如果解釋器采用正則序求值，那麼

(test 0 (p))
(if (= 0 0)
0
(p))
0
           

說明性知識與行動性知識

采用牛頓法求平方根

平方根函數可定義為： 根号 x = 存在這樣的 y, y >= 0 并且 y^2 = x;

(define (sqrt x)
(the y (and (>= y 0)
(= (sqrt y) x)
))
           

這樣又重新提出了原來的問題。函數隻不過是描述一件事情的特征，并沒有描述如何計算的過程。在數學裡，人們通常關心的是說明性的描述（是什麼），而在計算機科學，人們通常更關心行動性的描述（怎麼做）。

計算機如何計算平方根呢？ 最常用的就是牛頓的逐漸逼近法。這一方法告訴我們：如果。。。