3.2 函数式编程
现代计算机上运行的软件，是用各种编程语言写成的。其中有物理层面的语言，比如专为某台计算机设计的机器语言。这类语言关心的是，如何用一个个存储位和基本的机器指令来表示数据和控制。写机器语言的程序员关心的是，如何用给定的硬件搭建系统和工具，以便高效实现受资源限制的计算。高级语言搭建在机器语言的基础上，把「数据是一堆二进制位」「程序是一串基本指令」这类表示问题隐藏起来。这些语言有组合和抽象的手段，比如函数定义，很适合组织规模更大的软件系统。
本节介绍一门提倡函数式风格的高级语言。它就是 Scheme 语言的一个子集，计算模型和 Python 很像，但只用表达式、不用语句，擅长符号计算，而且只使用不可变的值（immutable）。
Scheme 是 Lisp 的一个方言。Lisp 是至今仍被广泛使用的第二古老的语言（仅次于 Fortran）。几十年来，Lisp 程序员社区一直蓬勃发展，而 Clojure 等 Lisp 新方言的开发者社区，增长速度在现代编程语言中名列前茅。想跟着本文的例子动手试试，可以下载一个 Scheme 的解释器。
3.2.1 表达式
Scheme 程序由表达式构成，表达式要么是调用表达式，要么是特殊形式。调用表达式由运算符表达式和跟在后面的零个或多个操作数子表达式组成，和 Python 一样。不同的是，Scheme 把运算符和操作数都括在一对括号里：
Scheme 只用前缀表示法。运算符常常就是 +、* 这样的符号。调用表达式可以嵌套，也可以跨多行：
和 Python 一样，Scheme 表达式可以是基本的，也可以是复合的。数字字面量是基本的，而调用表达式是复合形式，可以包含任意子表达式。求值调用表达式的过程和 Python 一样：先求值运算符和操作数表达式，再把运算符的值（也就是函数）施加到操作数的值（也就是参数）上。
在 Scheme 里，if 表达式是一种特殊形式：它在语法上看起来像调用表达式，求值过程却不一样。if 表达式的一般形式是：
(if <predicate> <consequent> <alternative>)要求值一个 if 表达式，解释器先求值表达式中的 <predicate> 部分。如果 <predicate> 求值为真，解释器再求值 <consequent> 并返回它的值；否则就求值 <alternative> 并返回它的值。
数字可以用常见的比较运算符来比较，不过这里同样要用前缀表示法：
Scheme 的布尔值是 #t（或 true）和 #f（或 false），可以用布尔特殊形式把它们组合起来，求值过程和 Python 里很像。
(and <e1> ... <en>)解释器按从左到右的顺序，一次求值一个<e>表达式。只要有一个<e>求值为假，and表达式的值就是假，剩下的<e>不再求值。如果所有<e>都求值为真，and表达式的值就是最后一个<e>的值。(or <e1> ... <en>)解释器按从左到右的顺序，一次求值一个<e>表达式。只要有一个<e>求值为真，就返回那个值作为or表达式的值，剩下的<e>不再求值。如果所有<e>都求值为假，or表达式的值就是假。(not <e>)当<e>求值为假时，not表达式的值是真，否则是假。
3.2.2 定义
可以用 define 特殊形式给值命名：
define 特殊形式还有另一种写法，可以用来定义新函数（在 Scheme 中称为「过程」）。例如，要定义求平方，可以这样写：
定义过程（procedure）的一般形式是：
(define (<name> <formal parameters>) <body>)<name> 是一个符号，用来与环境中的这个过程定义关联。<formal parameters> 是在过程体内指代该过程对应参数的名称。<body> 是一个表达式，当形式参数被替换成该过程实际作用到的参数时，它会产生过程应用的值。<name> 和 <formal parameters> 一起括在括号里，就像实际调用所定义的过程时一样。
定义好 square 之后，就可以在调用表达式中使用它了：
用户自定义的函数可以接受多个参数，也可以包含特殊形式：
Scheme 支持局部定义，词法作用域规则和 Python 相同。下面用嵌套定义和递归，定义一个求平方根的迭代过程：
匿名函数用 lambda 特殊形式创建。lambda 创建过程的方式和 define 一样，只是不用给过程指定名称：
(lambda (<formal-parameters>) <body>)得到的过程和用 define 创建的过程没什么两样，唯一的区别是它没有在环境中关联任何名称。事实上，下面两个表达式是等价的：
和任何值是一个过程的表达式一样，lambda 表达式也可以用作调用表达式里的运算符：
3.2.3 复合值
对（pair）内置于 Scheme 语言。出于历史原因，对用内置函数 cons 创建，元素用 car 和 cdr 访问：
语言里也内置了递归列表，用对来构建。特殊值 nil 或 '() 表示空列表。递归列表的值这样表示：把元素放进括号，用空格隔开：
列表是否为空，可以用基本的 null? 谓词判定。有了它，我们就能定义计算长度、选择元素这些标准的序列操作：
3.2.4 符号数据
到目前为止，我们用过的复合数据对象，最终都由数字构成。Scheme 的长处之一，就是能把任意符号当作数据来处理。
为了操作符号，语言里需要一个新的元素：引用（quote）数据对象的能力。假设我们要构造列表 (a b)。用 (list a b) 做不到，因为这个表达式构造的列表里是 a 和 b 的值，而不是符号本身。在 Scheme 中，只要在符号前面加一个单引号，就能引用 a 和 b 这两个符号，而不是它们的值：
在 Scheme 中，任何不求值的表达式，都称为被引用。这种引用的概念源自一个经典的哲学区分：事物（比如一只狗）会到处跑、会叫，而「狗」这个词是一个用来指代这类事物的语言构造。我们在引号里写「狗」时，指的并不是某只具体的狗，而是一个词。在语言里，引号让我们能谈论语言本身，Scheme 也是这样：
引用还让我们能直接输入复合对象，用的是列表传统的打印表示：
完整的 Scheme 语言还有更多功能，比如突变操作（mutation operations）、向量（vectors）和映射（maps）。不过，我们到目前为止介绍的这部分，已经是一门丰富的函数式编程语言，足以实现本文中讨论过的许多想法。
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
整套海龟过程也内置在 Python 里，就是 turtle 库模块。
最后一个例子：Scheme 能用海龟图形，以极其简洁的形式画出递归图形。谢尔宾斯基三角形是一种分形，每个三角形都画成三个相邻的小三角形，它们的顶点在包含它的大三角形三条边的中点。用下面这个 Scheme 程序，就能把它画到有限的递归深度：
> (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，填满这条边长度的前一半，再把海龟移到下一个顶点。penup 和 pendown 两个过程通过抬起和放下画笔，让海龟在移动时不画线。sier 和 leg 相互递归，得到这样的结果：
> (sier 400 6)