1.1.1 表達(dá)式

數(shù)

數(shù)是一種最基本的表達(dá)式

> 486
486

過程

過程（內(nèi)置運(yùn)算符或函數(shù)）是另一種基本表達(dá)式，例如：

• +
• -
• *
• /

組合式

• 過程和數(shù)可以組合成組合式
• 組合式中的第一個(gè)元素（最左邊）總是過程：

(+ 137 349)

嵌套表達(dá)式

如果組合式的元素也是組合式，他就是嵌套表達(dá)式

(+ (* 3 5) (- 10 6))

代碼格式

書寫代碼的時(shí)候要注意換行和縮排

(+  (* 3
    (+  (* 2 4)
        (+ 3 5)))
    (+ (- 10 7)
    6))

1.1.2 命名和環(huán)境

命名

命名將一個(gè)名字和一個(gè)對象關(guān)聯(lián)起來，命名是一種最基本的抽象

;將名字 size 和數(shù)字 2 關(guān)聯(lián)起來
> (define size 2)

> size
2

> (* 5 size)
10

環(huán)境

名字保存在環(huán)境中，不同環(huán)境中的名字互不干擾

1.1.3 組合式求值

求值過程

對組合式求值是一個(gè)遞歸過程

• 先求值各個(gè)子表達(dá)式
• 將求出的值作為參數(shù)應(yīng)用到過程
• 如果子表達(dá)式也是組合式，重復(fù)這一流程

如下表達(dá)式

(* (+ 2 (* 4 6))
    (+ 3 5 7))

可用下圖中的樹表示，遞歸特別適合處理像樹這樣的層次性結(jié)構(gòu)

表達(dá)式也可以用樹表示

環(huán)境和求值的關(guān)系

內(nèi)置運(yùn)算符也是一種名字，和普通名字沒太大區(qū)別，只不過他們是存在于全局環(huán)境中，并且已經(jīng)關(guān)聯(lián)到對應(yīng)的指令序列上而已

環(huán)境為求值提供了上下文，沒有環(huán)境，求值就沒有意義

特殊形式 define

define 是一種特殊的形式，和一般的求值規(guī)則有所不同

1.1.4 復(fù)合過程

定義復(fù)合過程

所謂的復(fù)合過程就是創(chuàng)建自定義的新過程

> (define (square x) (* x x))

上面的 define 創(chuàng)建了一個(gè)過程對象，并將這個(gè)對象和名字 square 相關(guān)聯(lián)

使用復(fù)合過程

我們可以像使用內(nèi)置過程一樣使用復(fù)合過程：

> (square 21)
441

> (square (+ 2 5))
49

> (square (square 3))
81

用復(fù)合過程定義復(fù)合過程

對解釋器來說，復(fù)合過程和內(nèi)置過程完全一樣，因此可以用復(fù)合過程繼續(xù)定義新的復(fù)合過程

> (define (sum-of-squares x y)
    (+ (square x) (square y)))
    
> (sum-of-squares 3 4)
25

繼續(xù)復(fù)合

> (define (f a)
    (sum-of-squares (+ a 1) (* a 2)))
    
> (f 5)
136

1.1.5 過程求值的代換模型

過程求值有兩種代換模型：

• 應(yīng)用序
• 正則序

下面讓我們分析一下組合式 (f 5) 求值的代換過程

應(yīng)用序代換

1. 總是先求值參數(shù)
2. 全部參數(shù)求值為基本表達(dá)式（即數(shù)值）后，開始求值過程名
3. 如果參數(shù)是一個(gè)組合式，則對其求值過程同樣遵循應(yīng)用序代換

應(yīng)用序代換過程

正則序代換

1. 總是現(xiàn)求值過程名
2. 過程名求值為基本過程（即內(nèi)置運(yùn)算符）后，開始求值參數(shù)。
3. 如果參數(shù)是一個(gè)組合式，則對其求值過程同樣遵循正則序代換

正則序代換過程

1.1.6 條件表達(dá)式和謂詞

到目前為止，我們能夠自定義的復(fù)合過程表達(dá)能力還非常有限，我們需要條件表達(dá)式

條件表達(dá)式

(cond   (p1 e1)
        (p2 e2)
        ......
        (pn en)
        (else e))

條件表達(dá)式也是一種特殊形式，因?yàn)樗粫θ繀?shù)求值。只要檢測到了為真的條件，他就會返回條件對應(yīng)的表達(dá)式，之后的參數(shù)不會再檢測

謂詞

謂詞就是返回真或者假的過程，常見的謂詞有：

• >
• <
• =

if 語句

if 語句只有一個(gè)判斷條件，為真返回表達(dá)式 1，為假返回表達(dá)式 2

邏輯運(yùn)算

• (and e1 e2 ...... en)，檢測到一個(gè)為假，則返回假；否則返回最后一個(gè)表達(dá)式的值
• (or e1 e2 ...... en) 返回第一個(gè)檢測到的為真的表達(dá)式的值，如果全部為假則返回假
• (not e)

注意：and 和 or 是特殊形式，因?yàn)樗麄儧]有對所有的參數(shù)進(jìn)行求值

練習(xí) 1.1

按順序求值下面的表達(dá)式

> 10
10


> (+ 5 3 4)
12


> (- 9 1)
8


> (/ 6 2)
3


> (+ (* 2 4) (- 4 6))
6


> (define a 3)


> (define b (+ a 1))


> (+ a b (* a b))
19


> (= a b)
#f


> (if (and (> b a) (< b (* a b)))
      b
      a)
4


> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16


> (+ 2 (if (> b a) b a))
6


> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

練習(xí) 1.2

將下面的數(shù)學(xué)公式轉(zhuǎn)化成前綴表達(dá)式

> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
 (* 3 (- 6 2) (- 2 7)))
 
-37/150

練習(xí) 1.3

定義一個(gè)過程，他有三個(gè)參數(shù)，返回其中較大的兩個(gè)數(shù)的平方和

;;;求兩個(gè)數(shù)的平方和
(define (sum-of-squares x y)
  (+ (* x x) (* y y)))


;;;計(jì)算三個(gè)數(shù)中兩個(gè)較大的數(shù)的平方和
(define (bigger-sum-of-squares x y z)
  (cond ((and (< x y) (< x z)) (sum-of-squares y z))
        ((and (< y x) (< y z)) (sum-of-squares x z))
        (else (sum-of-squares x y))))
        
        
        
>  (bigger-sum-of-squares 6 3 4)
52


> (bigger-sum-of-squares 1 2 3)
13


> (bigger-sum-of-squares 3 7 5)
74

sumOfSquares x y = x*x + y*y

biggerSumOfSquares  x y z
  | (x > y) && (y > z) = sumOfSquares x y
  | (x > y) && (z > y) = sumOfSquares x z
  | otherwise          = sumOfSquares y z

練習(xí) 1.4

描述下面這個(gè)自定義過程的求值步驟

;;;過程定義
(define (a-plus-abs-b a b)
    ((if (> b 0) + -) a b))

下面是求值步驟：

 ;;;調(diào)用
(a-plus-abs-b 10 99)
109



;;;參數(shù)已經(jīng)是基本表達(dá)式了，求值過程名得到
((if (> 99 0) + -) 10 99)
109


 ;;;參數(shù)已經(jīng)是基本表達(dá)式了,求值過程表達(dá)式得到
(+ 10 99)
109

練習(xí) 1.5

下面的過程可以判斷出你的解釋器是正則序還是應(yīng)用序，解釋其中的原理

;;;定義 1
(define (p) (p))

;;;定義 2
(define (test x y)
  (if (= x 0)
      0
      y))

解釋如下：

;;;求值表達(dá)式 (test 0 (p))



;;;對于應(yīng)用序 -----------------------------
> ;;;首先求值參數(shù)，得到
(test 0 (p))
;;;接下來會不斷的求值 (p)，導(dǎo)致死循環(huán)



;;;對于正則序 -----------------------------
> ;;;首先求值過程名，得到
(if (= 0 0)
    0
    (p))
0

;;;if 語句：因?yàn)闂l件滿足，所以只求值第一個(gè)表達(dá)式，返回 0；表達(dá)式 (p) 不會被求值

1.1.7 實(shí)例：采用牛頓法求平方根

到目前為止，我們學(xué)習(xí)的內(nèi)容已經(jīng)可以完成一些簡單的工作，比如下面求平方根的程序：

• 核心算法是不斷迭代改進(jìn)猜測值，直到足夠好
• 將算法中一些小的計(jì)算分離出來，作為輔助函數(shù)
• 沒有其他語言中的循環(huán)語句，但是仍然完成了迭代

#lang racket

;;;開方
(define (sqrt x)
  (sqrt-iter 1.0 x))


;;;開方算法：
;;;1. 如果猜測值足夠好，則返回猜測值；
;;;2. 否則改進(jìn)猜測值，然后迭代該過程
;;;參數(shù)：猜測值和開方數(shù)
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))


;;;判斷足夠好的算法
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))


;;;改進(jìn)猜測值的算法
(define (improve guess x)
  (average guess (/ x guess)))


;;;下面是輔助函數(shù)-------------------------

;;;求平均數(shù)
(define (average x y)
  (/ (+ x y) 2))


;;;求平方
(define (square x)
  (* x x))

習(xí)題 1.6

下面是一個(gè)模仿 if 的自定義過程，但是他會導(dǎo)致死循環(huán)，為什么？

;; 6-new-if.scm
(define   (new-if predicate then-clause else-clause)
    (cond  (predicate then-clause) 
                (else else-clause)))

解答：

因?yàn)閮?nèi)置的 if 是一種特殊形式，特殊形式有自己的求值規(guī)則，if 的求值規(guī)則如下：

• 只有條件為假，if 才會求值第二個(gè)表達(dá)式，導(dǎo)致遞歸調(diào)用
• 如果條件為真，if 會求值第一個(gè)表達(dá)式，整個(gè)過程可以退出

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess ;;;條件為真時(shí)會從這里退出
      (sqrt-iter (improve guess x) x)))

而自定義的 new-if 是一個(gè)函數(shù)，因此

• 按照函數(shù)求值規(guī)則，無論條件是真是假，他都會先對所有參數(shù)求值。而第二個(gè)表達(dá)式在這里僅僅是函數(shù)的一個(gè)參數(shù)
• 求值第二個(gè)表達(dá)式會導(dǎo)致遞歸調(diào)用，又會再次求值 new-if，導(dǎo)致死循環(huán)

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess 
      (sqrt-iter (improve guess x) x))) ;;;無論條件是真是假，都會求值這個(gè)表達(dá)式，導(dǎo)致死循環(huán)

習(xí)題 1.7

之前求平方根的算法，對于非常大或者非常小的數(shù)可能會出錯(cuò)：

• 出錯(cuò)的原因是什么？
• 怎么改進(jìn)？

解答：

首先看看 good-enough? 過程

;;;判斷足夠好的算法
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

這個(gè)算法認(rèn)為，猜測數(shù)的平方與被開方數(shù)之間的差值小于 0.001 就是足夠好，但是可能有下面兩種情況：

• 對于非常小的被開方數(shù)，比如 0.0001，其本身已經(jīng)小于判定差值，導(dǎo)致任意猜測數(shù)都是足夠好
• 對于非常大的被開方數(shù)，比如 100000000000000000000000000000000000000 ，由于精度問題，永遠(yuǎn)不可能滿足足夠好的條件，導(dǎo)致死循環(huán)

改進(jìn)算法

猜測數(shù)的改變量與舊的猜測數(shù)的比值小于一定范圍，則認(rèn)為是足夠好

;;; 新的足夠好算法
(define (good-enough? old-guess new-guess)
    (> 0.01
       (/ (abs (- new-guess old-guess))
          old-guess)))
          
          
;;;由于足夠好算法的參數(shù)發(fā)生了變化，因此主過程也要進(jìn)行相應(yīng)的改變    
(define (sqrt-iter old-guess x)
    (let ((new-guess (improve old-guess x)))
        (if (good-enough? old-guess new-guess)
            new-guess
            (sqrt-iter new-guess x))))

練習(xí) 1.8

設(shè)計(jì)一個(gè)求立方根的過程，下面這個(gè)公式可以改進(jìn)的猜測值

解答：

題目中給出的公式是改進(jìn)猜測數(shù)的公式，有了這個(gè)公式，我們可以模仿求平方根的算法進(jìn)行設(shè)計(jì)

;;;題目給出的公式就是改進(jìn)猜測數(shù)的公式
(define (improve guess x)                   
    (/ (+ (/ x (square guess)) (* 2 guess))
       3))
       
;;;給用戶使用的接口   
(define (cube-root x)
    (cube-root-iter 1.0 x))

;;;主過程
(define (cube-root-iter guess x)            
    (if (good-enough? guess x)              
        guess
        (cube-root-iter (improve guess x)
                        x)))

;;;檢測足夠好的過程
(define (good-enough? guess x)              
    (< (abs (- (cube guess) x))
       0.001))

1.1.8 過程作為抽象黑箱

對于一個(gè)計(jì)算問題，我們一般都可以將他分解為若干個(gè)子問題，例如之前的求平方根算法：

但是，定義過程的目的不僅僅是為了分解，而是為了抽象，過程也是一種抽象。

為什么過程是抽象的？

黑箱

過程的使用者不會考慮過程內(nèi)部的細(xì)節(jié)和使用的名字，這是一種抽象，也是一種隔離機(jī)制。

例如下面兩個(gè)求平方根的過程，雖然內(nèi)部使用了不同的算法，但是對使用者來說是沒有區(qū)別的

(define (square x) (* x x))

(define (square x) (exp (double (log x))))

局部名

過程內(nèi)部定義的名字（包括形參）都是局部的，其作用域只在過程體中，不會對外部造成影響。如果改變過程內(nèi)部某個(gè)名字，過程的功能不會有任何改變。

下面的兩個(gè)過程，參數(shù)名不同，但是對解釋器來說，他倆是相同的：

(define (square x) (* x x))

(define (square y) (* y y))

約束變量和自由變量

過程內(nèi)部的名字會被過程約束，因此這些名字也叫做約束變量。

而被過程使用，但是不被過程約束的名字就稱作自由變量。例如：+ - * 這些全局名字

在過程內(nèi)部使用自由變量，就說明過程對外部產(chǎn)生了依賴。因此，應(yīng)該盡量少使用不標(biāo)準(zhǔn)的外部名字

內(nèi)部定義和塊結(jié)構(gòu)

除了變量可以被約束在過程內(nèi)部，輔助過程也可以被約束在主過程內(nèi)部，這樣的程序內(nèi)聚性更好

下面改寫求平方根的程序，將輔助過程定義在主過程內(nèi)部

(define (sqrt x)
  
  ;;;是否足夠好
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))


  ;;;改進(jìn)猜測值
  (define (improve guess x)
    (average guess (/ x guess)))


  ;;;核心算法
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))

  ;;;迭代開始
  (sqrt-iter 1.0 x))

注意觀察上面的代碼，主函數(shù)傳入的參數(shù) x 會被所有輔助函數(shù)使用

其實(shí)可以不用傳來傳去，直接使用即可。改進(jìn)代碼如下：

(define (sqrt x)
  
  ;;;是否足夠好
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))


  ;;;改進(jìn)猜測值
  (define (improve guess)
    (average guess (/ x guess)))


  ;;;核心算法
  (define (sqrt-iter guess)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))

  ;;;迭代開始
  (sqrt-iter 1.0))

注意：參數(shù) x 在這里成為了詞法作用域（即主過程作用域）下的自由變量，輔助過程都會對 x 產(chǎn)生依賴，因此不要改變 x （外部依賴）的值