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)

Last updated

Was this helpful?