3.2 函数式编程

在任何现代计算机上运行的软件都是用各种编程语言编写的。有物理语言，比如特定计算机的机器语言。这些语言关注的是数据和控制的表示，以单个的存储位和基本的机器指令的形式。机器语言程序员关心的是使用给定的硬件来建立系统和实用程序，以便有效地实现资源有限的计算。建立在机器语言基础上的高级语言，隐藏了将数据表示为比特的集合，将程序表示为基本指令序列的问题。这些语言具有组合和抽象的方法，如函数定义，适合于更大规模的软件系统组织。

在本节中，我们将介绍一种鼓励函数式风格的高级编程语言。我们研究的对象是Scheme语言的一个子集，它采用与Python非常相似的计算模型，但只使用表达式(没有语句)，专门从事符号计算，并且只使用不可变值。

Scheme是Lisp的一种方言，Lisp是第二古老的编程语言，至今仍被广泛使用(仅次于Fortran)。 Lisp程序员社区已经持续繁荣了几十年，新的Lisp方言(如Clojure)拥有一些发展最快的现代编程语言开发人员社区。要学习本文中的示例，您可以下载一个Scheme解释器。

3.2.1 表达式

Scheme程序由表达式组成，表达式要么是调用表达式，要么是特殊形式。调用表达式由一个操作符表达式和零个或多个操作数子表达式组成，就像在Python中一样。操作符和操作数都包含在圆括号中：

(quotient 10 2)
5

Scheme只使用前缀表示法。操作符通常是符号，如+和*。调用表达式可以嵌套，它们可以跨一行：

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

与Python一样，Scheme表达式可以是原语或组合。数字文字是原语，而调用表达式是包含任意子表达式的组合形式。调用表达式的求值过程与Python的求值过程相匹配：首先求值操作符和操作数表达式，然后将作为操作符值的函数应用于作为操作数值的实参。

Scheme中的if表达式是一种特殊形式，这意味着尽管它在语法上看起来像一个调用表达式，但它具有不同的求值过程。if表达式的一般形式是：

(if <predicate> <consequent> <alternative>)

要计算if表达式，解释器首先计算表达式的部分。如果<谓词>求值为真，解释器就会求值<结果>并返回它的值。否则，它将计算<可选>并返回其值。

数值可以使用熟悉的比较运算符进行比较，但在这种情况下也使用前缀表示法：

(>= 2 1)
true

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 pi 3.14)
(* pi 2)
6.28

可以使用define特殊形式的第二个版本定义新函数(Scheme中称为过程)。例如，为了定义平方，我们这样写：

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

过程定义的一般形式是：

(define (<name> <formal parameters>) <body>)

<name> 是要与环境中的过程定义关联的符号。<formal parameters> 是在过程体中用于引用过程的相应参数的名称。< body> 是一个表达式，当形式参数被应用于过程的实际参数替换时，该表达式将生成过程应用程序的值。<name> 和<formal parameters>在括号内分组，就像它们在对所定义的过程的实际调用中一样。

定义了square之后，我们就可以在调用表达式中使用它了：

(square 21)
441
(square (+ 2 5))
49
(square (square 3))
81

用户定义函数可以接受多个参数并包含特殊形式：

(define (average x y)
  (/ (+ x y) 2))
(average 1 3)
2
(define (abs x)
    (if (< x 0)
        (- x)
        x))
(abs -3)
3

Scheme支持具有与Python相同的词法作用域规则的局部定义。下面，我们使用嵌套定义和递归定义了计算平方根的迭代过程：

(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))
(sqrt 9)
3.00009155413138

匿名函数使用lambda特殊形式创建。Lambda用于以与define相同的方式创建过程，不同的是没有为过程指定名称：

(lambda (<formal-parameters>) <body>)

生成的过程与使用define创建的过程一样。唯一的区别是它没有与环境中的任何名称相关联。实际上，下面的表达式是等价的：

(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))

与任何以过程作为值的表达式一样，lambda表达式可以用作调用表达式中的操作符：

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

3.2.3 复合值

对被内置到Scheme语言中。由于历史原因，pair是用cons内置函数创建的，pair的元素是用car和cdr访问的：

(define x (cons 1 2))
x
(1 . 2)
(car x)
1
(cdr x)
(cdr x)
2

递归列表也使用对构建到语言中。一个特殊值nil或'()表示空列表。递归列表值的呈现方式是将其元素放在用空格分隔的圆括号内：

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))
(1 2 3 4)
(list 1 2 3 4)
(1 2 3 4)
(define one-through-four (list 1 2 3 4))
(car one-through-four)
1
(cdr one-through-four)
(2 3 4)
(car (cdr one-through-four))
2
(cons 10 one-through-four)
(10 1 2 3 4)
(cons 5 one-through-four)
(5 1 2 3 4)

列表是否为空可以使用原语null?谓词。利用它，我们可以定义计算长度和选择元素的标准序列操作：

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define (getitem items n)
  (if (= n 0)
      (car items)
      (getitem (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(length squares)
5
(getitem squares 3)
16

3.2.4 象征数据

到目前为止，我们使用的所有复合数据对象最终都是由数字构造的。 Scheme的优点之一是将任意符号作为数据处理。

为了操作符号，我们的语言中需要一个新元素：引用数据对象的能力。假设我们想构造一个列表(a b)，但不能用(a b)来完成，因为这个表达式构造了一个包含a和b的值的列表，而不是符号本身。在Scheme中，我们引用符号a和b而不是它们的值，在它们前面加一个单引号：

(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)

在Scheme中，任何未求值的表达式都称为引用。“quotation”这个概念来源于一个经典的哲学区别，一个事物，比如一只会跑来跑去吠叫的狗，和“dog”这个词之间的区别，“dog”是一个用来表示这种事物的语言结构。当我们在引号中使用“dog”时，我们不是指某只狗，而是指一个单词。在语言中，引语使我们能够谈论语言本身，因此，它是这样的：

(list 'define 'list)
(define list)

Quotation还允许我们输入复合对象，使用传统的列表打印表示：

(car '(a b c))
a
(cdr '(a b c))
(b c)

完整的Scheme语言包含其他特性，如可变操作、向量和映射。然而，到目前为止我们所介绍的子集提供了一种丰富的函数式编程语言，能够实现到目前为止我们在本文中讨论的许多思想。

3.2.5 龟图

Scheme的实现作为本文的伴随，包括Turtle graphics，这是作为Logo语言(另一种Lisp方言)的一部分开发的一个说明环境。这只海龟从画布的中心开始，根据程序移动和旋转，并在移动时在后面画线。虽然海龟是为了让孩子们参与编程而发明的，但即使对于高级程序员来说，它仍然是一个吸引人的图形工具。

在执行Scheme程序过程中的任何时刻，海龟在画布上都有一个位置和标题。像forward和right这样的单参数过程会改变海龟的位置和方向。常见的程序有缩写：forward也可以称为fd，等等。 Scheme中的begin特殊形式允许单个表达式包含多个子表达式。此形式用于发出多个命令：

> (define (repeat k fn) (if (> k 0)
                            (begin (fn) (repeat (- k 1) fn))
                            nil))
> (repeat 5
          (lambda () (fd 100)
                     (repeat 5
                             (lambda () (fd 20) (rt 144)))
                     (rt 144)))
nil

Turtle过程的全部指令集也作为Turtle库模块内置在Python中。

最后一个例子是Scheme可以使用turtle图形以非常紧凑的形式表示递归绘图。谢尔平斯基三角形是一种分形，它将每个三角形画成三个相邻的三角形，这些三角形的顶点位于包含它们的三角形腿的中点上。通过本方案程序可以将其绘制成有限递归深度：

> (define (repeat k fn)
    (if (> k 0)
        (begin (fn) (repeat (- k 1) fn))
        nil))

> (define (tri fn)
    (repeat 3 (lambda () (fn) (lt 120))))

> (define (sier d k)
    (tri (lambda ()
           (if (= k 1) (fd d) (leg d k)))))

> (define (leg d k)
    (sier (/ d 2) (- k 1))
    (penup)
    (fd d)
    (pendown))

triangle过程是将一个绘图程序重复三次，每次重复后左转的一种通用方法。 sier过程取长度d和递归深度k。如果深度为1，则绘制一个普通三角形，否则绘制一个由对leg的调用组成的三角形。leg过程通过递归调用sier来绘制递归Sierpinski三角形的一条leg, sier填满了leg的前半部分长度，然后将turtle移动到下一个顶点。 penup和pendown这两个程序可以让海龟在移动时停止绘图，方法是把笔向上举起，然后再放下。 sier和leg之间的相互递归产生了这个结果

> (sier 400 6)

Previous3.1 引言 Next3.3 异常

Last updated 3 years ago

Was this helpful?