3.2 函数式编程
在任何现代计算机上运行的软件都是用各种编程语言编写的。 有物理语言,比如特定计算机的机器语言。这些语言关注的是数据和控制的表示,以单个的存储位和基本的机器指令的形式。 机器语言程序员关心的是使用给定的硬件来建立系统和实用程序,以便有效地实现资源有限的计算。 建立在机器语言基础上的高级语言,隐藏了将数据表示为比特的集合,将程序表示为基本指令序列的问题。 这些语言具有组合和抽象的方法,如函数定义,适合于更大规模的软件系统组织。
在本节中,我们将介绍一种鼓励函数式风格的高级编程语言。 我们研究的对象是Scheme语言的一个子集,它采用与Python非常相似的计算模型,但只使用表达式(没有语句),专门从事符号计算,并且只使用不可变值。
Scheme是Lisp的一种方言,Lisp是第二古老的编程语言,至今仍被广泛使用(仅次于Fortran)。 Lisp程序员社区已经持续繁荣了几十年,新的Lisp方言(如Clojure)拥有一些发展最快的现代编程语言开发人员社区。 要学习本文中的示例,您可以下载一个Scheme解释器。
3.2.1 表达式
Scheme程序由表达式组成,表达式要么是调用表达式,要么是特殊形式。调用表达式由一个操作符表达式和零个或多个操作数子表达式组成,就像在Python中一样。操作符和操作数都包含在圆括号中:
Scheme只使用前缀表示法。操作符通常是符号,如+和*。调用表达式可以嵌套,它们可以跨一行:
与Python一样,Scheme表达式可以是原语或组合。数字文字是原语,而调用表达式是包含任意子表达式的组合形式。调用表达式的求值过程与Python的求值过程相匹配:首先求值操作符和操作数表达式,然后将作为操作符值的函数应用于作为操作数值的实参。
Scheme中的if表达式是一种特殊形式,这意味着尽管它在语法上看起来像一个调用表达式,但它具有不同的求值过程。if表达式的一般形式是:
要计算if表达式,解释器首先计算表达式的部分。如果<谓词>求值为真,解释器就会求值<结果>并返回它的值。否则,它将计算<可选>并返回其值。
数值可以使用熟悉的比较运算符进行比较,但在这种情况下也使用前缀表示法:
Scheme中的布尔值#t(或true)和#f(或false)可以与布尔特殊形式组合,它们的求值过程类似于Python中的求值过程。
(and <e1> … <en>) 解释器计算表达式<e> 一次一个,从左到右的顺序。 如果任何<e> 计算结果为false,and表达式的值为false,而其余的<e>则不计算。 如果所有的<e>的值都为真值,and表达式的值就是最后一个的值。
(or & <e1> … <en>) 解释器计算表达式<e> 一次一个,从左到右的顺序。 如果任何<e> 求值为真值,该值作为or表达式的值返回,而其余的<e>则不求值。 如果所有<e>的值都为假,or表达式的值为假。
(not <e>) 当表达式<e> 计算结果为false,否则为false。
3.2.2 定义
可以使用define特殊形式来命名值:
可以使用define特殊形式的第二个版本定义新函数(Scheme中称为过程)。例如,为了定义平方,我们这样写:
过程定义的一般形式是:
<name> 是要与环境中的过程定义关联的符号。<formal parameters> 是在过程体中用于引用过程的相应参数的名称。< body> 是一个表达式,当形式参数被应用于过程的实际参数替换时,该表达式将生成过程应用程序的值。<name> 和<formal parameters>在括号内分组,就像它们在对所定义的过程的实际调用中一样。
定义了square之后,我们就可以在调用表达式中使用它了:
用户定义函数可以接受多个参数并包含特殊形式:
Scheme支持具有与Python相同的词法作用域规则的局部定义。下面,我们使用嵌套定义和递归定义了计算平方根的迭代过程:
匿名函数使用lambda特殊形式创建。Lambda用于以与define相同的方式创建过程,不同的是没有为过程指定名称:
生成的过程与使用define创建的过程一样。唯一的区别是它没有与环境中的任何名称相关联。实际上,下面的表达式是等价的:
与任何以过程作为值的表达式一样,lambda表达式可以用作调用表达式中的操作符:
3.2.3 复合值
对被内置到Scheme语言中。由于历史原因,pair是用cons内置函数创建的,pair的元素是用car和cdr访问的:
递归列表也使用对构建到语言中。一个特殊值nil或'()表示空列表。递归列表值的呈现方式是将其元素放在用空格分隔的圆括号内:
列表是否为空可以使用原语null?谓词。利用它,我们可以定义计算长度和选择元素的标准序列操作:
3.2.4 象征数据
到目前为止,我们使用的所有复合数据对象最终都是由数字构造的。 Scheme的优点之一是将任意符号作为数据处理。
为了操作符号,我们的语言中需要一个新元素:引用数据对象的能力。 假设我们想构造一个列表(a b),但不能用(a b)来完成,因为这个表达式构造了一个包含a和b的值的列表,而不是符号本身。 在Scheme中,我们引用符号a和b而不是它们的值,在它们前面加一个单引号:
在Scheme中,任何未求值的表达式都称为引用。“quotation”这个概念来源于一个经典的哲学区别,一个事物,比如一只会跑来跑去吠叫的狗,和“dog”这个词之间的区别,“dog”是一个用来表示这种事物的语言结构。当我们在引号中使用“dog”时,我们不是指某只狗,而是指一个单词。在语言中,引语使我们能够谈论语言本身,因此,它是这样的:
Quotation还允许我们输入复合对象,使用传统的列表打印表示:
完整的Scheme语言包含其他特性,如可变操作、向量和映射。然而,到目前为止我们所介绍的子集提供了一种丰富的函数式编程语言,能够实现到目前为止我们在本文中讨论的许多思想。
3.2.5 龟图
Scheme的实现作为本文的伴随,包括Turtle graphics,这是作为Logo语言(另一种Lisp方言)的一部分开发的一个说明环境。 这只海龟从画布的中心开始,根据程序移动和旋转,并在移动时在后面画线。 虽然海龟是为了让孩子们参与编程而发明的,但即使对于高级程序员来说,它仍然是一个吸引人的图形工具。
在执行Scheme程序过程中的任何时刻,海龟在画布上都有一个位置和标题。 像forward和right这样的单参数过程会改变海龟的位置和方向。 常见的程序有缩写:forward也可以称为fd,等等。 Scheme中的begin特殊形式允许单个表达式包含多个子表达式。 此形式用于发出多个命令:

Turtle过程的全部指令集也作为Turtle库模块内置在Python中。
最后一个例子是Scheme可以使用turtle图形以非常紧凑的形式表示递归绘图。谢尔平斯基三角形是一种分形,它将每个三角形画成三个相邻的三角形,这些三角形的顶点位于包含它们的三角形腿的中点上。通过本方案程序可以将其绘制成有限递归深度:
triangle过程是将一个绘图程序重复三次,每次重复后左转的一种通用方法。 sier过程取长度d和递归深度k。如果深度为1,则绘制一个普通三角形,否则绘制一个由对leg的调用组成的三角形。leg过程通过递归调用sier来绘制递归Sierpinski三角形的一条leg, sier填满了leg的前半部分长度,然后将turtle移动到下一个顶点。 penup和pendown这两个程序可以让海龟在移动时停止绘图,方法是把笔向上举起,然后再放下。 sier和leg之间的相互递归产生了这个结果

Last updated
Was this helpful?