版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
函数式程序设计语言Scheme语言控制抽象第二部分第二章Scheme语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象参考教材计算机程序的构造和解释（原书第2版）StructureandInterpretationofComputerPrograms,SecondEditionMassachusettsInstituteofTechnology
（美）HaroldAbelson,GeraldJaySussman,JulieSussmanScheme语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象引言
任何强有力的程序设计语言都必须能表述基本的数据和过程，还需要提供对数据和过程进行组合和抽象的方法。——摘自《计算机程序的构造和解释》Scheme语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象程序设计基本元素1表达式⑴元表达式常量
数486字符串，例如：“hello”布尔值，例如：#f,#t名字例如：+//内部过程例如：pi//由define或其他过程创建的变量⑵组合表达式（前缀表示法）组合:(<operator><operand><operand>…)(+2135127)(+(*3(+(*24)(+35)))(+(-107)6))Scheme语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象2命名命名(definepai3.14159)(defineradius10)(*pai(*radiusradius))(definecircumference(*2pairadius))circumferenceScheme语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象3复合过程过程定义的一般形式：
过程定义在环境中关联符号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开始的连续整数去检查能否整除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语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象线性的递归和迭代两种计算过程的分析比较：①线性的递归计算过程代换模型揭示出一种先展开后收缩的形状。解释器需要维护以后将要执行的操作的轨迹。对应的计算称为递归计算过程。②线性迭代计算过程状态可以用固定数目的状态变量描述。解释器只需要保存有限的状态变量的轨迹。对应的计算称为迭代计算过程。③注意：递归过程和递归计算过程是两个不同的概念。递归过程的计算也可能是迭代的计算过程。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语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象语言控制抽象树形递归改进：使用迭代计算过程。规则：(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使之能够迭代执行(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特殊形式来创建所需的过程
(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构造过程如何创建局部变量？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创建局部变量方法四：利用特殊形式let创建局部变量：(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. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年缙云县机关事业单位选调工作人员笔试真题
- 2025食堂承包合同书（15篇）
- 读《庄子》心得感悟
- 餐饮教学合同协议书范本
- 房屋转兑合同协议书
- 购买产品合同协议书范本
- 工地临建合同协议书范本
- 2025企业与个人租赁合同范本
- 工业互联网平台自然语言处理技术在工业设备故障预警中的应用报告
- 房屋租赁合同转租协议书
- 机械应力促进髓核诱导的软骨形成
- 社区居民积分制管理实施方案
- 2024年二建《法规》真题及参考答案
- 高中生物教材易错易混概念辨析（新人教版2019）
- 《创新创意设计》课件
- 初高中物理衔接讲座(初高中物理对比)
- 宠物酒店商业计划书创新创业计划书2024年
- 微观经济学课后习题答案-微观经济学课后习题
- 掬水月在手-古典诗词与现代人生智慧树知到期末考试答案章节答案2024年南开大学
- 2024年中级咖啡师技能鉴定考试题库大全-下（判断题）
- 中国法律史-第一次平时作业-国开-参考资料
评论
0/150
提交评论