SICP學習·第一章·第一節

2019-11-08 02:21:37

字體：大中小

來源：轉載

供稿：網友

第一章構造過程抽象

第一章構造過程抽象1程序設計的基本元素11表達式12命名和環境13 組合式的求值14 復合過程15 過程應用的代換模型16 條件表達式和謂詞17 實例采用牛頓法求平方根18過程作為黑箱抽象

1.1程序設計的基本元素

為了將簡單的認識組合成復雜的認識，每一種強有力的語言都會提供的三種機制： 基本表達式：代表該語言所關心的最簡單的實體。組合：從較為簡單的實體出發，構造出復合實體。抽象：為復合實體命名并將其作為一個整體進行操作。

1.1.1表達式

本節第一次講到的scheme語法：;;基本表達式：數，算數運算符;;組合表達式：(<運算符> n個<運算對象>);;其中運算對象是一個表達式。

1.1.2命名和環境

本節第一次講到的scheme語法：定義對象：(define <標識符> <表達式>);;進行了define后就可以直接通過對應的標識符來引用表達式了。;;而為了實現通過標識符引用表達式，解釋器必須擁有某種存儲能力來保證標識符和表達式的對應，這種存儲被稱為環境。

1.1.3 組合式的求值

scheme對于組合式的求值方法： 獲得組合表達式中的子表達式的值。使用運算對象作為運算符的參數，對組合式進行求解。

1.1.4 復合過程

本節第一次講到的scheme語法：;;定義過程：(define (<標識符> <該過程的形式參數>) <表達式>)

1.1.5 過程應用的代換模型

復合過程應用的計算模型： 將過程的形式參數替換為過程所在表達式中的運算對象，再進行求值(只是為了便于理解，事實上并不是解釋器的具體工作方式)。應用序與正則序： 正則序：先將作為參數的表達式代入過程中，展開后一一求值。應用序：先求出作為參數的表達式的值，再代入過程中。由于參數在過程中可能被多次用到，使用正則序會導致多次展開而重復求值，降低效率。在超出替換方式模擬模型的過程范圍后，正則序的操作將會復雜很多(本小節沒有具體說明)。但有時正則序可以成為特別有用的工具(本小節沒有具體說明)。

1.1.6 條件表達式和謂詞

本節第一次講到的scheme語法：;;基本表達式：邏輯表達式#t和#f，謂詞<,>,=，復合運算符and,or,not;;條件判斷表達式：(cond n個(<條件判斷表達式> <操作表達式>));;運算方法：;;從第一個條件判斷表達式開始查找，直到查找到條件判斷表達式為真的表達式，執行其對應的操作表達式。;;條件判斷表達式：(if <條件判斷表達式> <操作表達式1> <操作表達式2>);;運算方法：;;若條件判斷表達式為真則執行操作表達式1，否則執行操作表達式2。練習1.1：求對于每個表達式的輸出結果10;;Value: 10(+ 5 3 4);;Value: 12(- 9 1);;Value: 8(/ 6 2);;Value: 3(+ (* 2 4) (- 4 6));;Value: 6(define a 3)(define b (+ a 1))(+ a b (* a b));;Value: 19(= a b);;Value: #f(if (and (> b a) (< b (* a b))) b a);;Value: 4(cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25));;Value: 16(+ 2 (if (> b a) b a));;Value: 6(* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1));;Value: 16練習1.2：將下面的表達式變為前綴形式(5+4+(2-(3-(6+4/5))))/(3*(6-2)*(2-7))(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)));;Value: -37/150練習1.3：請定義一個過程，以三個數為參數，返回其中較大的兩個數之和(define (PRoduce a b c) (cond ((and (< a b) (< a c)) (+ b c)) ((and (< b a) (< b c)) (+ a c)) ((and (< c a) (< c b)) (+ a b)) ))(produce 5 8 3);;Value: 13練習1.4：請仔細考察上面給出的允許運算符為復合表達式的組合式的求值模型，根據對這一模型的認識描述下面過程的行為(define (a-plus-abs-b a b) ((if (> b 0) + -) a b));;若參數b大于0，則運算符為+，運算結果為a+b，否則運算結果為a-b。練習1.5：若某個解釋器采用的是應用序求值，Ben會看到什么樣的情況？如果解釋器采用正則序求值，他又會看到什么情況？請對你的回答做出解釋(define (p) (p))(define (test x y) (if (= x 0) 0 y))(test 0 (p));;若解釋器采用應用序求值：;;解釋器在調用test時，優先求出參數的值，其中(p)會不斷求值得到它自己，進入死循環。;;若解釋器采用正則序求值：;;(test 0 (p))會展開為(if (= 0 0) 0 (p))，由于判斷表達式(= 0 0)值為#t，將直接得到0而不會去求(p)的值。

1.1.7 實例：采用牛頓法求平方根

實例代碼(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))(define (improve guess x) (average guess (/ x guess)))(define (average x y) (/ (+ x y) 2))(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))(define (sqrt x) (sqrt-iter 1.0 x))練習1.6：定義過程new-if如下，若將牛頓法sqrt-iter過程中的if替換為new-if，計算平方根時將會發生什么(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)));;由于解釋器采用的是應用序求值，在使用new-if過程時將會求else-clause的值，而每次計算else-clause的值時sqrt-iter過程都會調用自身，從而導致死循環。練習1.7：解釋并用例子說明原代碼對于很大的數和很小的數來說是不適合的，并設計通過檢測兩次迭代之間差與猜測值的比值來確定迭代結束的方法并用例子檢測其對于很大和很小的輸入是否適用(sqrt 0.00000001);;Value: .03125010656242753;;true answer: 0.0001;;對于較小的數而言，正確答案本身與原代碼中的0.001相近或遠小于，此時猜測值的誤差過大(sqrt 4000000000000000000000000000000000000000000000000000000000000);;死循環;;對于較大的數而言，由于精度限制，可能即使與答案最近的兩個數與答案的差也大于0.001，此時good-enough過程永遠不可能為真。(define (good-enough? old-guess new-guess) (< (abs (/ (- new-guess old-guess) old-guess)) 0.001))(define (sqrt-iter guess x) (if (good-enough? guess (improve guess x)) guess (sqrt-iter (improve guess x) x)));;未涉及的過程與原過程相同(sqrt 0.00000001);;Value: 1.0000040611237676e-4;;true answer: 0.0001;;答案較為準確(sqrt 4000000000000000000000000000000000000000000000000000000000000);;Value: 2.000157691333889e30;;true answer: 2e30;;答案較為準確練習1.8：根據求立方根的牛頓迭代公式((x/y^2)+2*y)/3(y為猜測值)得到求立方根的過程。(define (improve guess x) (/ (+ (/ x (* guess guess)) (* 2 guess)) 3));;未涉及的過程與原過程相同(sqrt 8);;Value: 2.000004911675504(sqrt 27);;Value: 3.001274406506175

1.1.8過程作為黑箱抽象

本節第一次講到的scheme語法：;;對于define的提示：;;define過程中還可以定義define過程，如可以將上節牛頓迭代法的代碼改為：(define (sqrt x) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (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));;此時外部僅可調用sqrt過程而無法調用其他過程;;此外在上面的代碼中，可以將整個過程始終保持不變的變量x省略，從而簡化塊內過程傳遞的參數：(define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))

上一篇：通過繼承SecurityManager實現系統退出檢查

下一篇：Sublime Text 3 配置