版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領
文檔簡介
函數式程序設計語言Scheme語言控制抽象第二部分第二章Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象參考教材計算機程序的構造和解釋（原書第2版）StructureandInterpretationofComputerPrograms,SecondEditionMassachusettsInstituteofTechnology
（美）HaroldAbelson,GeraldJaySussman,JulieSussmanScheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象引言
任何強有力的程序設計語言都必須能表述基本的數據和過程，還需要提供對數據和過程進行組合和抽象的方法?！浴队嬎銠C程序的構造和解釋》Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象程序設計基本元素1表達式⑴元表達式常量
數486字符串，例如：“hello”布爾值，例如：#f,#t名字例如：+//內部過程例如：pi//由define或其他過程創(chuàng)建的變量⑵組合表達式（前綴表示法）組合:(<operator><operand><operand>…)(+2135127)(+(*3(+(*24)(+35)))(+(-107)6))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象2命名命名(definepai3.14159)(defineradius10)(*pai(*radiusradius))(definecircumference(*2pairadius))circumferenceScheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象3復合過程過程定義的一般形式：
過程定義在環(huán)境中關聯符號name例如：
(define
(<name>
<formal
parameters>)
<body>)(define
(square
x)
(*
x
x))(square
21)
441
(square
(+
2
5))
49
(square
(square
3))
81Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象3復合過程定義過程x2+y2
將sum-of-squares作為構件，進一步構造其它過程：(define
(f
a)
(sum-of-squares
(+
a
1)
(*
a
2)))
(f
5)
136(define
(sum-of-squares
x
y)
(+
(square
x)
(square
y)))(sum-of-squares
3
4)
25Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象
4求值模型①應用序求值（代換模型）先求值參數，后應用的求值模型（Scheme采用該模型）②正則序求值先完全展開，后歸約的求值模型(f5)(sum-of-squares(+a1)(*a2))(sum-of-squares(+51)(*52))(+(square6)(square10))(+(*66)(*1010))(+36100)136(f5)(sum-of-squares(+a1)(*a2))(sum-of-squares(+51)(*52))(+(square(+51))(square(*52)))(+(*(+51)(+51))(*(*52)(*52)))(+(*66)(*1010))(+36100)136Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象5條件表達式和謂詞條件表達式語法形式：例如：求
(define(absx)(cond((>x0)x)((=x0)0)((<x0)(-x))))(cond
(<p1>
<e1>)
(<p2>
<e2>)
(<pn>
<en>)(else<e>))(define(absx)(cond((<x0)(-x))(elsex)))(define(absx)(if(<x0)(-x)x))(if
<predicate>
<consequent>
<alternative>)Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象5條件表達式和謂詞其它復合謂詞(and<e1>...<en>)(or<e1>...<en>)
(not<e>)例如：檢測某個數是否大于或等于另一個數
(define
(>=
x
y)
(or
(>
x
y)
(=
x
y)))(define
(>=
x
y)
(not
(<
x
y)))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象實例：采用牛頓法求平方根平方根函數——牛頓逐步逼近法求猜測商平均值（更好的猜測）1(2/1)=2(2+1)/2=1.51.5(2/1.5)=1.3333(1.3333+1.5)/2=1.41671.4167(2/1.4167)=1.4118(1.4167+1.4118)/2=1.41421.4142…………Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象實例：采用牛頓法求平方根(define
(sqrt
x)
(sqrt-iter
1.0
x))(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))(define
(improve
guess
x)
(average
guess
(/
x
guess)))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象實例：采用牛頓法求平方根sqrtsqrt-itergood-enough？improveaveragesquareabs求解復雜問題的一種方法歸約原理：復雜問題分解為子問題Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象6內部定義和塊結構塊結構：允許嵌套定義Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象6內部定義和塊結構塊結構：詞法作用域Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象素數檢測從2開始的連續(xù)整數去檢查能否整除n(define
(smallest-divisorn)
(find-divisor
n2))(define
(find-divisorntest-divisor)
(
cond((>(squaretest-divisor)
n)
n)
((divides?test-divisorn)
test-divisor)
(else
(find-divisorn
(+test-divisor1)))))(define
(divides?ab)
(=(remainderba)0))(define
(prime?n)
(=n(smallest-divisorn)))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象過程計算1線性的遞歸和迭代線性的遞歸過程例如：(define
(factorial
n)
(if
(=
n
1)
1
(*
n
(factorial
(-
n
1)))))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象考察6！(factorial6)(*6(factorial5))(*6(*5(factorial4)))(*6(*5(*4(factorial3))))(*6(*5(*4(*3(factorial2)))))(*6(*5(*4(*3(*2(factorial1))))))(*6(*5(*4(*3(*21)))))(*6(*5(*4(*32))))(*6(*5(*46)))(*6(*524))(*6120)720Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象線性迭代過程product
counterproductcounter
counter+1*(define
(factorial
n)
(fact-iter
1
1
n))
(define
(fact-iter
product
counter
max-count)
(if
(>
counter
max-count)
product
(fact-iter
(*
counter
product)(+
counter
1)
max-count)))
Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象考察6！Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象線性的遞歸和迭代兩種計算過程的分析比較：①線性的遞歸計算過程代換模型揭示出一種先展開后收縮的形狀。解釋器需要維護以后將要執(zhí)行的操作的軌跡。對應的計算稱為遞歸計算過程。②線性迭代計算過程狀態(tài)可以用固定數目的狀態(tài)變量描述。解釋器只需要保存有限的狀態(tài)變量的軌跡。對應的計算稱為迭代計算過程。③注意：遞歸過程和遞歸計算過程是兩個不同的概念。遞歸過程的計算也可能是迭代的計算過程。Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習1求冪(define(expt1bn)(if(=n0)1(*b(expt1b(-n1)))))(define(expt2bn)(expt-iterbn1))(define(expt-iterbcounterproduct)(if(=counter0)product(expt-iterb(-counter1)(*bproduct))))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習快速求冪(define(fast-exptbn)(cond((=n0)1)((even?n)(square(fast-exptb(/n2))))(else(*b(fast-exptb(-n1))))))(define(even?n)(=(remaindern2)0))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象過程計算2樹形遞歸【例】Fibonacci數列
Fib（n）=01Fib（n-1）+Fib（n-2）ifn=0ifn=1其它(define
(fib
n)
(cond
((=
n
0)
0)
((=
n
1)
1)
(else
(+
(fib
(-
n
1))(fib
(-
n
2))))))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象樹形遞歸Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象樹形遞歸改進：使用迭代計算過程。規(guī)則：(define
(fib
n)
(fib-iter
1
0
n))
(define
(fib-iter
a
b
count)
(if
(=
count
0)
b
(fib-iter
(+
a
b)
a
(-
count
1))))a
a+bb
a<??><??><??><??>Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習1線性遞歸線性迭代兩種方法求解函數f<??>Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習1線性遞歸線性迭代兩種方法求解函數f<??><??><??><??>Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象用高階函數做抽象回顧：過程抽象機制為公共的模式命名，建立抽象。
問題：能否將同樣的程序設計模式用于不同的過程？
以過程作為參數，或者以過程作為返回值。高階過程能夠操作過程的過程，稱為高階過程。(define
(cube
x)
(*
x
x
x))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象過程1：計算給定范圍內的各整數之和。過程2：計算給定范圍內的整數的立方和。過程3：序列求和(define
(sum-integers
a
b)
(if
(>
a
b)
0
(+
a
(sum-integers
(+
a
1)
b))))(define
(sum-cubes
a
b)
(if
(>
a
b)
0
(+
(cube
a)
(sum-cubes
(+
a
1)
b))))(define
(pi-sum
a
b)
(if
(>
a
b)
0
(+
(/
1.0
(*
a
(+
a
2)))
(pi-sum
(+
a
4)
b))))(define
(<name>
a
b)
(if
(>
a
b)
0
(+
(<term>
a)
(<name>
(<next>
a)
b))))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-過程作為參數公共模式（更高級別的抽象）
高階過程sum注：term和next為過程參數。(define
(sum
term
a
next
b)
(if
(>
a
b)
0
(+
(term
a)
(sum
term
(next
a)
next
b))))<??>Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象過程1：計算給定范圍內的各整數之和。過程2：計算給定范圍內的整數的立方和。(define
(sum-integers
a
b)
(sumidentityainc
b))(define
(sum-cubes
a
b)
(sum
cube
a
inc
b))(define
(inc
n)(+n1))(define
(identityx)x)(define
(cube
x)
(*
x
x
x))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象過程3：序列求和(define
(pi-term
x)
(
/
1.0
(*
a
(+
a
2))))(define
(pi-sum
a
b)
(sum
pi-term
a
pi-next
b))(define
(pi-next
x)
((+
a
4))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習1用sum構造f的定積分Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習2重寫sum使之能夠迭代執(zhí)行(define(sumtermanextb)(define(iteraresult)(if<??><??>(iter<??><??>)))(iter<??><??>))(>ab)result(nexta)a(+(terma)result)0Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象練習4構造sum的抽象概念accumulate5用accumulate構造sum<??><??>Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程問題：能否不定義作為高階函數參數的pi-term和pi-next簡單函數，而直接使用高階函數？引入Lambda特殊形式來創(chuàng)建所需的過程
(lambda
(x)
(+
x
4))(lambda
(x)
(/
1.0
(*
x
(+
x
2))))(define
(pi-sum
a
b)
(sum
(lambda
(x)
(/
1.0
(*
x
(+
x
2))))
a
(lambda
(x)
(+
x
4))
b))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程用lambda構造過程(lambda(<formal-parameters>)<body>)該過程以x為參數過程體((lambda
(x
y
z)
(+
x
y
(square
z)))
1
2
3)lambda可以用在任何使用過程名的上下文中Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程如何創(chuàng)建局部變量？Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程方法一：利用輔助過程約束局部變量。(define
(f
x
y)
(define
(f-helper
a
b)
(+
(*
x
(square
a))
(*
y
b)
(*
a
b)))
(f-helper
(+
1
(*
x
y))
(-
1
y)))輔助過程Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程方法二：利用lambda表達式描述約束局部變量的匿名過程。(define
(f
x
y)
((lambda
(a
b)
(+
(*
x
(square
a))
(*
y
b)
(*
a
b)))
(+
1
(*
x
y))
(-
1
y)))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象高階過程-用lambda構造過程方法三：利用define的內部定義功能(define
(f
x
y)
(define
a
(+
1
(*
x
y)))
(define
b
(-
1
y))
(+
(*
x
(square
a))
(*
y
b)
(*
a
b)))Scheme語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象語言控制抽象let創(chuàng)建局部變量方法四：利用特殊形式let創(chuàng)建局部變量：(define
(f
x
y)
(let
((a
(+
1
(*
x
y)))
(b
(-
1
y)))
(+
(*
x
(square
a))
(*
y
b)
(*
a
b))))(let
((<var1>
<exp1>)
(<var2>
<exp2>)
(<varn>
<expn>))
<body>)((lambda
(<var1>
﹒﹒﹒<varn>)
<body>)<exp1><expn>)
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 人教A版高一（下）數學必修第二冊6.1平面向量的概念【教學設計】
- 五年級上冊數學教案-2.1 軸對稱再認識（一）｜北師大版
- 2025年外國游戲大陸推廣代理合同韓文版
- （高清版）DB45∕T 477-2022 綠色食品 黑木耳生產技術規(guī)程
- 《第2課電視與生活 1 電視百寶箱》（教學設計）-2023-2024學年四年級下冊綜合實踐活動安徽大學版
- 2025年海南工商職業(yè)學院單招職業(yè)傾向性測試題庫學生專用
- 第3課 建造塔臺（教學設計）-2023-2024學年六年級下冊科學 教科版
- 2025年度個人單位間借款擔保合同
- 產業(yè)園區(qū)室內外裝修合同
- 2025年度商鋪房屋租賃與智能管理系統(tǒng)合作協議
- 2024-2029年擴展塢行業(yè)市場現狀供需分析及市場深度研究發(fā)展前景及規(guī)劃投資研究報告
- SH/T 3003-2024 石油化工合理利用能源設計導則（正式版）
- 中國人民大學613衛(wèi)生統(tǒng)計歷年真題12-16
- 人事聘用合同范本標準版
- 新疆地方教材可愛的中國第二單元教學設計
- 米-伊林《十萬個為什么》閱讀練習+答案
- 三年級奧數專項練習-和差問題
- 強化學習 課件 第1章 強化學習概述
- 《鄧稼先》省公開課一等獎全國示范課微課金獎課件
- GJB9001C-2017管理手冊、程序文件及表格匯編
- 核心素養(yǎng)目標新課標北師大版小學數學三年級下冊全冊教案
評論
0/150
提交評論