我们将注意力转向过程抽象，这是一种将复杂程序分解成 functions (也称为 procedures 或 subroutines 。这些术语在不同语境中的用法有细微差别，但就我们的目的而言，我们将把它们视为同义词) 形式的较小代码片段的策略。函数将某些计算封装在一个接口之后，与任何抽象概念一样，函数的用户只需知道函数做了什么，而不需要知道函数是如何完成计算的。函数还通过接收影响其计算的参数来概括计算。计算的结果就是函数的返回值。
在本单元中，我们首先介绍 Lisp 家族中的函数式语言 Scheme。然后，我们将讨论与所有 procedural languages 相关的函数方面的问题，然后再仔细研究 functional programming，这是一种以数学函数为计算模型的编程范式。
Introduction to Scheme #
R5RS Scheme 语言采用了与 Python 非常相似的计算模型，但只使用 expressions (不使用statements)，擅长 symbolic computation。
Scheme 是 Lisp 的一种方言，Lisp 是当今仍在广泛使用的第二古老的编程语言（仅次于 Fortran）。几十年来，Lisp 程序员社区一直在蓬勃发展，而新的 Lisp 方言（如 Clojure）也是所有现代编程语言中开发者社区发展最快的。要跟上本文的示例，可以下载 Scheme 解释器或使用在线解释器。
Expressions #
Scheme 程序由 expressions 组成，expressions 可以是简单表达式，也可以是列表形式的组合。简单表达式由一个文字或符号组成。组合表达式是一种 compound expression，由一个运算符表达式和零个或多个操作数子表达式组成。运算符和操作数都包含在括号中：
> (quotient 10 2)
5
Scheme 只使用前缀符号。操作符通常是符号，如 + 和 *。复合表达式可以嵌套，也可以跨一行以上：
> (+ (* 3 5) (- 10 6))
19
> (+ (* 3
(+ (* 2 4)
(+ 3 5)
)
)
(+ (- 10 7)
6
)
)
57
对组合进行求值时，首先需要检查运算符是否代表 special form，因为 special form 有自己的求值程序。如果运算符不是 special form，那么运算符和操作数表达式将按照任意顺序进行求值。然后，作为运算符值的函数将应用于作为操作数值的参数。
在 Scheme 中，if 表达式是特殊形式的一个例子。虽然它在语法上看起来与调用表达式相似，但它的评估过程却与调用表达式不同。if 表达式的一般形式是
(if <predicate> <consequent> <alternative>)
要对 if 表达式进行求值，解释器首先会对表达式的 <predicate> 部分进行求值。如果 <predicate> 求值为 true，解释器将求值 <consequent> 并返回其值。否则，解释器将求值 <alternative>，并返回其值，<alternative>可省略。
Numerical values 可以使用熟悉的比较运算符进行比较，但在这种情况下也使用 prefix notation：
> (>= 2 1)
#t
在 Scheme 中，真值 (包括布尔值 #t 表示真， #f 表示假) 可以与布尔特殊形式相结合，它们的求值过程如下：
(and <e1> ... <en>)解释器按从左到右的顺序逐次求值表达式<e>。如果任何<e>的值为 false，则and表达式的值就是该 false，其余<e>的值不予求值。如果所有<e>的值都为 true，那么and表达式的值就是最后一个<e>的值。(or <e1> ... <en>)解释器按从左到右的顺序，一次评估一个<e>表达式。如果任何<e>的值为 true，该值将作为or表达式的值返回，其余的<e>将不被求值。如果所有<e>的值都为 false，则 or 表达式的值就是最后一个<e>的值。
true 也可以用 not 程序来处理：
(not <e>)当表达式<e>的值为假值时，not 表达式的值为#t，否则为#f。
Definitions #
可以使用 define 特殊形式对值进行命名：
> (define pi 3.14)
> (* pi 2)
6.28
新函数（在 Scheme 中通常称为 procedures）可以使用 define 特殊形式的第二个版本来定义。例如，要定义平方，我们可以写下
(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 支持具有 static scope 的局部函数定义。我们将推迟到讨论 高阶函数时再讨论这个问题。
匿名函数也称为 lambda 函数，是使用 lambda 特殊形式创建的。使用 lambda 创建存储过程的方法与定义相同，只是不指定存储过程的名称：
(lambda (<formal-parameters>) <body>)
由此产生的存储过程与使用 define 创建的存储过程一样。唯一不同的是，它没有与环境中的任何名称相关联。事实上，下面的表达式是等价的：
> (define (plus4 x) (+ x 4))
> (define plus4 (lambda (x) (+ x 4)))
与任何以 procedure 为值的表达式一样，lambda 表达式也可以用作 call expression 中的操作符：
> ((lambda (x y z) (+ x y (square z))) 1 2 3)
12
Compound Values #
Pairs 是内置于 Scheme 语言中的。由于历史原因，Pairs 使用 cons 内置函数创建，因此，Pairs 也被称为 cons 单元，Pairs 中的元素使用 car 和 cdr 访问：
> (define x (cons 1 2))
> x
(1 . 2)
> (car x)
1
> (cdr x)
2
该语言还使用成对的方式建立 Recursive lists 。用 '() 表示的特殊值代表 empty list。递归列表值的呈现方式是将其元素放在括号内，中间用空格隔开：
> (cons 1
(cons 2
(cons 3
(cons 4 '())
)
)
)
(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)
下图为文本表示为 (1 2 3 4) 的列表对应的结构由一连串的对组成，以空列表在图中表示为包含符号 $\emptyset$：
以空列表以外的其他元素结束的数对序列称为 improper list。如上面的 (cons 1 2) 的结果就是一个例子，它只包含序列中的 pair。下面演示的是一个更复杂的序列：
> (cons 1
(cons 2
(cons 3 4)
)
)
(1 2 3 . 4)
证明了 pairs 和其他 compound objects 具有引用语义 – 配对的 cdr 部分存储了对序列中下一对配对的引用。下面的代码通过变量进一步演示了这些引用语义：
> (define x (cons 1 2))
> (define y x)
> (eqv? x y)
#t
> (set-car! y 7)
> x
(7 . 2)
在这里，定义 (define y x) 的结果是 x 和 y 指向同一个数据 pair object。只有当两个参数指向同一个对象对时，存储过程 eqv? 才会返回 true（而 equal? 则从结构上对对象对进行比较）。此外，当我们使用 set-car! 变量修改 y 所引用的配对的第一个项目时，我们可以看到 x 引用了同一个配对，因为它也显示了修改。
一个对象是否为空列表，可以使用原始的 null? 。利用它，我们可以定义用于计算适当列表长度和选择元素的标准序列操作：
> (define (list-length items)
(if (null? items)
0
(+ 1 (list-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
内置的 length 和 list-ref 程序提供了与这里的 list-length 和 getitem 相同的功能。
Symbolic Data #
我们迄今为止使用过的所有复合数据对象最终都是由数字构建的。使用任意符号作为数据是 Scheme 的优势之一。
为了操作符号，我们需要在语言中加入一个新元素：引用数据对象的能力。假设我们要构造列表 (a b)。我们不能用 (list 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 中，任何未被求值的表达式都被称为 quoted。引号的概念源于一个经典的哲学，即一个事物，如到处乱跑并吠叫的狗与 “狗” 这个词之间的区别，“狗” 这个词是用于指定此类事物的语言结构。当我们使用带引号的 “狗” 时，我们指的并不是某只狗，而是一个词。在语言中，引号允许我们谈论语言本身，在 Scheme 中也是如此：
> (list 'define 'list)
(define list)
引号还允许我们使用传统的列表打印表示法键入复合对象。我们已经看到，'() 表示空列表。下面是其他例子：
> (car '(a b c))
a
> (cdr '(a b c))
(b c)
Scheme 中的引号与字符串不同，后者表示字符格式的原始、非结构化数据，而前者表示结构化数据。
> "(- 3)" ; a string containing the characters #\( #\- #\space #\3 #\)
"(- 3)"
> '(- 3) ; produces a list containing the symbol - and number 3
(- 3)
> (car '(- 3))
-
> (cdr '(- 3))
(3)
> (- 3) ; calls the - procedure on the number 3
-3
在上面的示例中，字符串字面形式 "(- 3)" 的值为其本身，带引号的表达式 '(- 3) 求值为一个列表，列表的第一个元素是符号 -，第二个元素是数字 3。最后一个示例对符号 - 进行求值以获得相应的存储过程，将数字 3 求值为自身，然后在数字 3 上调用存储过程 -，得到 -3。换句话说，字符串字面量中的数据仍然是字符数据，既不会被求值，也不会被解析。带引号表达式会被解析，但不会被求值，而是产生数据的结构化表示。未加引号的表达式会被解释器解析和求值。
完整的 Scheme 语言还包含其他功能，如 mutation operations、vectors 和 maps。不过，我们迄今为止介绍的子集提供了一种丰富的函数式编程语言，能够实现我们迄今为止讨论过的许多想法。
Functions #
我们首先要考虑的是以参数形式向函数传递数据的各种方案。我们将出现在函数定义中的参数，也称为 formal parameters，与调用函数时传递给函数的实际值区分开来，后者通常被称为 actual parameter。
- 本文将使用 argument 一词来指代 actual parameter，
- 用 parameter 一词指代 formal parameters。
Keyword Arguments #
有些语言允许甚至要求在调用函数时提供参数名，这种策略称为 named parameters 或 keyword arguments。
关键字参数通常允许以不同于函数参数列表的顺序提供参数。例如，在 Python 中，keyword argument 可以用于任何参数。请看下面的代码：
def foo(x, y):
print(x, y)
调用不带关键字参数的 foo() 时，第一个参数会作为第一个参数传递，第二个参数会作为第二个参数传递：
>>> foo(1, 2)
1 2
不过，参数可以使用参数名重新排序：
>>> foo(y = 1, x = 2)
2 1
Python 还提供了将参数定义为 positional-only 或 keyword-only 的机制，但我们不会在这里讨论这些机制。
有少数语言要求默认为所有或大部分参数提供名称，并要求以与参数相同的顺序提供参数。下面是 Swift 3 中的一个示例：
func greet(name: String, withGreeting: String) {
print(withGreeting + " " + name)
}
greet(name: "world", withGreeting: "hello")
以相反的参数顺序调用 greet() 是错误的。
Swift 允许为一个参数指定不同的参数名和参数名，这一点也很罕见。这意味着调用函数时为参数提供的名称可能与函数主体中使用的参数内部名称不同。
Default Arguments #
在某些语言中，函数声明或定义可能会提供一个 default argument，允许在没有该参数的情况下调用函数。这可以替代重载，即编写单独的函数定义来处理存在或缺少参数的情况。
下面是一个 Python 示例：
def power(base, exponent=2):
return base ** exponent
power() 函数可以调用一个参数，在这种情况下，默认参数 2 用于计算数字的平方。也可以使用两个参数来计算任意幂：
>>> power(3)
9
>>> power(3, 4)
81
有 default arguments 一般必须出现在参数列表的末尾。对于何时以及在哪种环境下评估默认参数，不同语言的做法各不相同。最常见的策略是每次调用函数时都评估缺省参数，但在定义 environment (static scope) 中进行。Python 的罕见之处在于，它只在函数定义语句执行时评估一次缺省参数。这意味着，如果在函数中修改了参数值，那么对同一函数的后续调用可能会对同一参数使用不同的缺省值。例如
def test(x=[]):
x.append(1)
print(x)
test()
test()
// output
[1]
[1, 1]
C 和 C++ 有许多关于缺省参数的规则，这是因为一个实体可以声明多次。默认参数既可以在独立声明中提供，也可以在定义中提供。但是，同一实体的多个可见声明为同一参数提供默认参数是非法的，即使提供的值是相同的。缺省参数集是同一作用域内所有可见声明的集合，只有在前面和当前声明已为所有后续参数提供缺省参数的情况下，声明才能为参数引入缺省参数。缺省参数中使用的名称在声明时进行解析，但参数表达式在调用函数时进行求值。
下面是 C++ 中多重声明的一个合法示例：
int foo(int x, int y = 4);
int foo(int x = 3, int y) {
return x + y;
}
除函数参数外，C++ 还允许模板参数使用默认参数，其有效性规则与此类似。
Variadic Functions #
一种语言可能会提供一种机制，让函数在调用时可以使用数量可变的参数。这种特性通常被称为 varargs，使用这种特性的函数被称为变量函数 (variadic)。这种机制可能提供类型安全，也可能允许不安全的使用，从而导致错误或未定义的行为。可变参数一般必须出现在参数列表的末尾，它匹配的是非可变参数匹配后剩余的参数。通常只允许使用一个变量参数。
在提供安全变量函数的语言中，一种常见的机制是自动将变量参数打包到一个 container 中，例如 array 或 tuple。例如，下面的 Python 函数计算其参数的乘积：
def product(*args):
result = 1
for i in args:
result *= i
return result
参数名前面的 * 表示变量参数，变量参数以绑定到参数名的元组形式传递。上述函数遍历元组中的元素，更新总乘积。要调用 product()，必须提供 0 个或更多参数：
>>> product()
1
>>> product(1, 2, 3)
6
Python 还提供了可变关键字参数，这些参数被打包成一个字典。在参数前面加上 ** 表示它是一个可变关键字参数，并且这样的参数必须是最后一个。例如，下面的函数同时包含一个非关键字可变参数和一个可变关键字参数，打印出前者对应的元组和后者对应的字典：
def print_args(*args, **kwargs):
print(args)
print(kwargs)
>>> print_args(3, 4, x = 5, y = 6)
(3, 4)
{'x': 5, 'y': 6}
最后，Python 允许使用 * 或 ** 操作符对序列或字典进行 “解包”，从而将解包后的值用于需要值列表的地方。例如，下面的代码将一个列表解包，以调用 product()：
product(*[1, 2, 3])
6
此外，Scheme 还支持可变参数。一个存储过程可以使用一个不恰当的列表作为参数列表，并以一个符号而不是空列表结束，这样就可以定义一个存储过程来接受可变参数。可变参数与任意数量的参数绑定，并打包成一个列表：
> (define (func . args)
args
)
> (func)
()
> (func 1 2 3)
(1 2 3)
存储过程 func 可以接收任意数量的参数，并返回包含这些参数的 list。因此，它的行为与内置的 list 存储过程相同。我们还可以定义一个存储过程，同时接收必参数和可变参数，例如下面的 average 定义：
> (define (average x . nums)
(/ (apply + x nums)
(+ 1 (length nums))
)
)
> (average 1)
1
> (average 1 3)
2
> (average 1 3 5 7)
4
procedure 接收一个或多个参数，其中第一个参数与参数 x 绑定，其余参数封装在一个与变量 nums 参数绑定的列表中。我们可以使用 apply 来转发变量参数，它接收一个存储过程、任意数量的常规参数，最后是一个包含其余参数的列表。例如，(apply + 1 2 '(3 4)) 相当于调用 (+ 1 2 3 4)。在上面第一个使用 average 的示例中，nums 在调用 (average 1) 时绑定为一个空列表，而 (apply + x nums) 相当于 (apply + 1 '()) ，后者本身相当于 (+ 1)。在第三个例子中，nums 绑定到一个列表 (3 5 7)，因此 (apply + x nums) 等价于 (apply + 1 '(3 5 7))，而 (apply + 1 '(3 5 7)) 又等价于 (+ 1 3 5 7)。
在 Python 和 Scheme 中，可变参数可以匹配任何类型的参数，因为这两种语言都是动态类型的。然而，在静态类型语言中，可变参数通常被限制为单一类型，尽管该类型可能是多态的。例如，下面是 Java 中的一个变量方法：
public static void print_all(String... args) {
for (String s : args) {
System.out.println(s);
}
}
print_all() 的参数必须是字符串，并将它们打包成一个字符串数组。Java 也允许将单个字符串数组作为参数传递：
print_all("hello", "world");
print_all(new String[] { "good", "bye" });
C 和 C++ 也有一种可变参数机制，但它存在严重的安全问题。尤其是，它无法向被调用的函数提供关于参数个数及其类型的信息。下面是一个返回参数之和的函数示例：
#include <stdarg.h>
int sum(int count, ...) {
va_list args;
int total = 0;
int i;
va_start(args, count);
for (i = 0; i < count; i++) {
total += va_arg(args, int);
}
va_end(args);
return total;
}
在该函数中，第一个参数被假定为其余参数的个数，而后一个参数被假定为 int 类型。如果违反其中任何一个条件，都会产生未定义的行为。另一种策略是使用格式字符串来确定参数的数量和类型，如 printf() 和类似函数中使用的方法。可变参数缺乏安全性，会导致 格式字符串攻击等漏洞。
C++11 提供了类型安全的 variadic templates。
Parameter Passing #
语言的另一个不同之处在于函数与其调用者之间传递参数的 semantics 和 mechanism。函数参数可以是单向的，仅用于向函数传递输入或仅用于从函数向调用者传递输出，也可以是双向的。这些情况被称为 input、output 和 input/output 参数。一种语言不必支持所有三种参数类别。
各种语言使用不同的参数传递技术或调用模式。这些技术会影响参数和参数的语义以及支持的参数类别。以下是不同语言使用的具体调用模式：
Call by value，参数代表函数调用框架中的一个新变量。参数值被复制到与新变量相关的存储空间中。按值调用参数只为函数提供输入，如下面的 C++ 示例：
void foo(int x) {
x++;
cout << x << endl;
}
int main() {
int y = 3;
foo(y); // prints 4
cout << y << endl; // prints 3
}
即使 foo() 修改了输入值，修改后的值也不会传回 caller。
Call by reference，参数必须传递一个 l-value，因为参数 aliases 了传递进来的对象。对参数的任何修改都会反映在参数对象中。因此，引用调用参数同时提供输入和输出。在 C++ 中，引用参数提供了引用调用，并且可以通过声明 const 将其限制为仅提供输入。下面的 C++ 示例使用引用调用交换了两个对象的值：
void swap(int &x, int &y) {
int tmp = x;
x = y;
y = tmp;
}
int main() {
int x = 3, y = 4;
swap(x, y);
cout << x << " " << y << endl; // prints 4 3
}
引用调用有时用来指使用指针间接传递对象。下面的 C/C++ 函数使用指针交换对象值：
void swap(int *x, int *y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
int main() {
int x = 3, y = 4;
swap(&x, &y);
printf("%d %d\n", x, y); // prints 4 3
}
但从技术上讲，参数和参量是独立的指针对象，通过值传递。尽管如此，这种效果模拟了引用调用，使输入和输出都能通过一个参数来实现。
Call by result，在这种模式下，参数代表一个新变量，调用者不对其进行初始化。相反，调用者会为参数指定一个 l-value，当函数调用结束时，参数的最终值会被复制到 l-value 中。因此，按结果调用只提供输出参数。下面是一个使用类似 C 的语法、按结果调用的示例：
void foo(result int x) {
x = 3;
x++; // x is now 4
}
int y = 5;
foo(y); // y is now 4
print(y); // prints 4
Call by value-result，这是 Call by value 和 Call by result 的组合。参数值被复制到与参数相对应的新变量中，然后从函数返回时，参数值又被复制到调用者提供的 l-value 值中。这与引用调用的不同之处在于，在进入和退出函数时都会进行复制。可以通过将相同的 l-value 传递给多个参数来说明这一点，例如在下面的示例中使用了类似于 C 语言的语法，即按 Call by value-result：
int foo(value-result int x, value-result int y) {
x++;
return x - y;
}
int z = 3;
print(foo(z, z)); // prints 1
print(z); // prints 3 or 4, depending on the semantics
在这段代码中，x 和 y 是新变量，它们被初始化为 z 的值，即 3。x 的增量不会影响 y，因为它们是独立的变量，所以调用 foo() 返回 1。因此，1 会被打印出来。z 的最终值取决于从 x 还是从 y 复制的语言语义。如果使用引用调用，那么 x 和 y 将 alias 为同一个对象，调用 foo() 将返回 0。
Call by name，在这种模式下，可以提供一个完整的表达式作为参数，但在调用函数时不会对其进行求值。相反，在函数中出现参数名的地方，参数名会被表达式替换，而表达式会在主体中遇到时进行求值。这是一种 lazy evaluation，即在需要时才计算值。下面是一个使用 C-like syntax、按名称调用的示例：
void foo(name int a, name int b) {
print(b); // becomes print(++y)
print(b); // becomes print(++y)
}
int x = -1, y = 3;
foo(++x, ++y); // prints 4, then 4 or 5 depending on the exact
// language semantics; y is now 4 or 5
print(x); // prints -1 -- x is unchanged
在本例中，参数表达式 ++x 从未被求值，因为相应的逐名调用参数 a 从未被使用。另一方面，表达式 ++y 被计算，因为相应的参数 b 确实被使用了。根据语言语义的不同，表达式可能只被求值一次，其值被缓存以备后续使用，也可能在每次使用参数时都被求值。
按名称调用会产生一个微妙的问题。请看下面这段代码，它使用了 C-like syntax 和按名称调用：
void bar(name int x) {
int y = 3;
print(x + y);
}
int y = 1;
bar(y + 1);
如果我们用参数表达式替换 bar() 中出现的参数 x，就会得到 y + 1 + y 作为 print() 的参数。如果在 bar() 的环境中求值，结果将是 7。这是不可取的，因为这意味着局部声明 y 的实现细节改变了函数的行为。
相反，参数表达式应在调用者的环境中进行评估。这就要求在函数调用时同时传递参数及其环境。使用名称调用的语言通常使用编译器生成的局部函数，称为 thunk ，来封装参数表达式及其环境。然后将 thunk 传递给被调用的函数，当遇到参数时，就会调用 thunk。
在某些语言中，与 call-by-name parameter 相对应的表达式仅在首次引用该参数时进行评估，并缓存评估结果。缓存的结果将用于随后每次出现的参数。
call by value 是大多数现代语言使用的调用模式，包括 C、C++（用于非引用参数）、Java、Scheme 和 Python。程序员经常误以为后三种语言使用 call by reference，但实际上，它们将 call by value 与 call by reference 语义结合在一起。这种组合有时被称为 object reference 。下面的示例说明 Python 使用的是 call by value：
def swap(x, y):
tmp = x
x = y
y = tmp
>>> x, y = 1, 2
>>> swap(x, y)
>>> x, y
(1, 2)
错误的 swap() 函数只是改变了局部变量的值，从而改变了它们所引用的对象，而没有影响作为参数的变量。这表明全局 x 和 y 的存储空间与参数的存储空间是不同的，因此 Python 没有使用引用调用。事实上，Python 甚至不能像 C 和 C++ 指针那样模拟引用调用。
l-value and r-value #
l-value 和 r-value 是 C++ 表达式的基础。简单地说，l-value 是对象引用，r-value 是值。l-value 和 r-value 之间的区别在表达式的编写和理解中起着重要作用。
- l-value 是产生对象引用的表达式，例如变量名、数组下标引用、取消引用指针或返回引用的函数调用。l-value 总是有一个定义的存储区域，因此可以获取其地址。
- r-value 是指不是 l-value 的表达式。r-value 的例子包括字面量、大多数运算符的结果以及返回非引用的函数调用。r-value 不一定与任何存储空间相关联。
严格来说，函数是一个 l-value，但它的唯一用途是用于调用函数或确定函数的地址。大多数情况下，l-value 指的是对象 l-value。
Evaluation of Function Calls #
下面我们总结一下函数调用的实现过程：
第一步是确定嵌套函数调用的非本地环境。在使用嵌套函数和静态作用域的语言中，当执行嵌套函数定义本身时，非本地环境的引用会存储在关联的函数对象中。在具有深绑定的动态作用域下，非本地环境是在函数名称被引用时确定的。最后，在浅绑定的动态作用域中，非本地环境是函数被调用时处于活动状态的环境。
下一步是使用新创建的函数调用激活记录将参数传递给函数。参数在现有环境中进行评估，并按如下方式传递给被调用者：
- Call by value and call by value-result : 对参数进行评估以获得其 r-value。r-value 将被复制到新激活记录中相应参数的存储空间。
- Call by reference : 参数的 l-value。相应的参数会绑定到与 l-value 相关的对象上。
- Call by result : 参数进行评估，以获得其 l-value 。在新的激活记录中，存储空间会被分配，但不会被初始化。
- Call by name : 参数表达式会被打包到一个包含当前环境的 thunk 中。参数绑定到 thunk 的引用上。
一旦参数被传递，调用者的执行就会暂停，而被调用者的主体将在一个由新创建的激活记录和被调用者的非本地环境组成的环境中执行。对于 call by name，根据语言的语义，call by name 参数的出现会在参数第一次被指名或每次被指名时调用相应的 thunk。
当被调用的函数返回时，其返回值（如果有的话）会被放置在指定的存储位置，通常是在调用者的激活记录中。对于 call-by-result 或 call-by-value-result 参数，参数的当前 r-value 会被复制到与相应函数调用参数的 l-value 相关联的对象中。然后，被调用者的激活记录将被销毁，调用者将在函数调用后恢复执行。函数调用本身的评估结果就是函数的返回值。
Recursion #
Recursion 是一种利用函数和函数应用进行重复的机制。它涉及函数直接或间接地调用自身，通常使用在某种意义上比前一个参数 “小 “的参数。递归计算在达到基数时终止，基数是指无需进行任何递归调用即可直接计算出结果的输入。
一种语言要想达到图灵完备性，只需提供 recursion 和 conditionals 即可。
Activation Records #
在机器上，递归之所以起作用，是因为函数的每次调用都有自己的激活记录，将局部变量映射为值。请看下面的阶乘递归定义：
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
调用 factorial(4) 会导致五次调用 factorial()，参数从 4 到 0，每次都有自己的激活记录和参数 n 的绑定：
factorial(4): n --> 4
factorial(3): n --> 3
factorial(2): n --> 2
factorial(1): n --> 1
factorial(0): n --> 0
在执行 factorial() 主体时查找 n，每次调用都会获得自己的 n 值，而不会受到其他激活记录的影响。
要使函数调用生效，激活记录需要的不仅仅是参数和局部变量的存储空间。临时值也需要存储在某个地方，由于每个调用都需要自己的临时值存储空间，因此这些临时值通常也要放在激活记录中。调用还需要知道在哪里存储其返回值，通常是在调用者框架中的临时存储区。最后，函数需要知道如何将执行返回给调用者。具体细节不在本文讨论范围之内，但这些信息包括调用者函数调用后的指令地址和调用者激活记录的地址。
临时对象集可以通过静态方式保守地确定，因此激活记录的大小以及对象在其中的位置都可以在编译时确定。对于上面的 factor()，需要临时存储 n - 1 以及递归调用 factorial() 的结果。递归调用会使用后者在调用程序中的位置来存储其返回值。根据不同的实现，调用 factorial(0) 的激活记录中可能仍然有这些临时对象的空间，即使它们不会被使用。
Tail Recursion #
递归计算对函数的每次调用都使用单独的激活记录。存储这些记录所需的空间与激活函数调用的次数成正比。在上面的 factorial(n) 中，当计算达到 factorial(0) 时，所有 n + 1 次调用都同时激活，需要的空间为 O(n)。与之相比，下面的迭代实现使用的空间是恒定的：
def factorial_iter(n):
result = 1
while n > 0:
result *= n
n -= 1
return result
然而，递归版本的 factorial() 所需的空间并不是使用递归的内在原因，而是函数编写方式的结果。事实上，由于在递归调用之后还需要完成调用的工作，因此在递归调用期间必须保留其激活记录，这就导致了线性空间需求。
考虑另一种阶乘递推计算方法：
def factorial_tail(n, partial_result = 1):
if n == 0:
return partial_result
return factorial_tail(n - 1, n * partial_result)
请注意，在完成递归调用后，factorial_tail() 函数不做任何工作。这意味着在进行递归调用时，它不再需要存储参数、局部变量或临时对象。此外，由于 factorial(n, k) 直接返回递归调用 factorial(n - 1, n * k) 的结果，因此后者可以将其返回值存储在 factorial(n, k) 的调用者中用于存放 factorial(n, k) 返回值的位置，并直接将执行返回给该调用者。因此，优化后的实现可以为 factorial_tail(n - 1, n * k) 重用 factorial_tail(n, k) 的激活记录空间，因为前者不再需要激活记录。
这个过程可以推广到任何函数调用，而不仅仅是递归调用。如果函数的调用者直接返回调用值，而不执行任何额外的计算，那么该函数调用就是尾调用。如果一个函数的所有递归调用都是尾调用，那么这个函数就是尾递归函数。因此，factorial_tail() 是尾部递归函数。
尾递归计算只使用固定数量的激活记录，因此其空间使用量与等效的迭代计算相当。事实上，许多函数式语言并不提供迭代的构造，因为它们可以等效地使用尾递归来表达。这些语言通常要求实现执行尾调用优化，尽可能重复使用激活记录的空间。
由于尾调用要求在返回后不执行任何计算，因此在语法上看似尾调用的调用可能不是尾调用，因为隐式计算可能发生在函数的末尾。这方面的一个具体例子是基于作用域的资源管理，如下例所示：
int sum(vector<int> values, int index, int partial_result = 0) {
if (values.size() == index) {
return 0;
}
return sum(values, index + 1, partial_result + values[index])
}
虽然这段代码在递归调用后似乎没有进行计算，但本地 vector<int> 对象有一个析构函数，必须在递归调用完成后运行。因此，对 sum() 的递归调用不是尾部调用，该计算也不是尾部递归计算。
另一种阻碍尾调用优化的情况是，在使用静态作用域并支持高阶函数全部功能的语言中，函数内部包含一个函数定义。嵌套函数需要访问其定义环境，因此如果嵌套函数可以在其外层函数调用完成后或在尾调用中使用，则必须保留该环境。
Higher-Order Functions #
first-class entity 是一种支持对语言中的其他 entities 进行操作的 entity，包括作为参数传递、从函数返回和动态创建。
- 在 functions 是 first-class entity 的语言中，可以编写 higher-order functions，将另一个 function 作为参数传递或返回一个 function。
- 其他语言也可能支持 higher-order functions，但是在这些语言中 function 不是可以在运行时动态创建的 entity 。
Function Objects #
在某些语言中，可以定义本身不是函数但提供与函数相同接口的对象。这些对象被称为函数对象或函数器。一般来说，语言通过允许重载函数调用操作符来编写函数器。请看下面的 C++ 示例：
class Counter {
public:
Counter : count(0) {}
int operator()() {
return count++;
}
private:
int count;
};
Counter 类实现了一个函数，可以返回它被调用的次数。可以同时存在多个 Counter 对象，每个对象都有自己的计数：
Counter counter1, counter2;
cout << counter1() << endl; // prints 0
cout << counter1() << endl; // prints 1
cout << counter1() << endl; // prints 2
cout << counter2() << endl; // prints 0
cout << counter2() << endl; // prints 1
cout << counter1() << endl; // prints 3
函数允许 function-like object 存在多个实例，每个实例都有自己的状态，并在函数的生命周期内持续存在。这与 function 截然不同，function 中的自动对象不会在单次调用后持续存在，而静态对象则会在整个程序执行过程中持续存在。
Python 还允许通过定义特殊的 __call__ 方法来编写函数：
class Counter:
def __init__(self):
self.count = 0
def __call__(self):
self.count += 1
return self.count - 1
一般来说，在重载函数调用操作符时，可以指定额外的参数，以模拟可以接收这些参数的函数。
有些语言不允许重载函数调用操作符本身，但规定了允许定义和使用类函数对象的约定。例如，下面是 Counter 在 Java 中使用 Supplier<T> 接口的实现，该接口指定了一个产生 T 的零参数方法：
class Counter implements Supplier<Integer> {
public Integer get() {
return count++;
}
private int count = 0;
}
然后通过明确调用 get() 方法来调用这个类函数对象：
Supplier<Integer> counter1 = new Counter();
Supplier<Integer> counter2 = new Counter();
System.out.println(counter1.get()); // prints 0
System.out.println(counter1.get()); // prints 1
System.out.println(counter1.get()); // prints 2
System.out.println(counter2.get()); // prints 0
System.out.println(counter2.get()); // prints 1
System.out.println(counter1.get()); // prints 3
再比如，Java 中的 Predicate 接口是通过 functor-like objects 实现的，这些对象接收一个参数并返回一个布尔值：
interface Predicate<T> {
boolean test(T t);
...
}
class GreaterThan implements Predicate<Integer> {
public GreaterThan(int threshold) {
this.threshold = threshold;
}
public boolean test(Integer i) {
return i > threshold;
}
private int threshold;
}
使用这些 functor-like objects 的代码会调用 test() 方法，而不是直接调用对象：
GreaterThan gt3 = new GreaterThan(3);
System.out.println(gt3.test(2)); // prints out false
System.out.println(gt3.test(20)); // prints out true
java.util.function 函数库包中为常见模式提供了单独的接口。
Functions as Parameters #
higher-order function 可以将另一个函数作为参数。我们首先研究那些只有 top-level functions 并允许将函数指针或引用作为参数传递的语言。然后，我们将研究将函数作为参数传递会如何影响函数代码的执行环境。
Function Pointers #
在某些语言中，函数可以作为参数或返回值传递，但不能在另一个函数的上下文中创建。在这些语言中，所有函数都是在顶层定义的，只有指向函数的指针或引用才能作为值使用。下面是 C 语言中的一个例子，C 语言提供了函数指针：
void apply(int *array, size_t size, int (*func)(int)) {
for (; size > 0; --size, ++array) {
*array = func(*array);
}
}
int add_one(int x) {
return x + 1;
}
int main() {
int A[5] = { 1, 2, 3, 4, 5 };
apply(A, 5, add_one);
printf("%d, %d, %d, %d, %d\n", A[0], A[1], A[2], A[3], A[4]);
return 0;
}
apply() 函数接收数组、数组大小和一个指向接收 int 并返回 int 的 function pointer。它将函数应用于数组中的每个元素，并用结果替换原值。add_one() 函数作为参数传递给 apply()，C 语言会自动将函数转换为函数指针，其结果是 A 中的每个元素都被递增。
Binding Policy #
在上面的代码中，有三个环境与 add_one() 函数相关联：定义环境、在 main() 中引用环境和在 apply() 中调用环境。根据语言的语义，这三个环境中的任何一个都可能是 add_one() 主体执行环境的组成部分。
在静态作用域中，函数中的代码可以访问其定义环境中的名称，而在动态作用域中，它可以访问其使用环境中的名称。考虑到动态作用域，函数的非本地环境是函数被引用的环境还是函数被调用的环境？下面是一个与这种区别有关的示例：
int foo(int (*bar)()) {
int x = 3;
return bar();
}
int baz() {
return x;
}
int main() {
int x = 4;
print(foo(baz));
}
在动态作用域中，函数可以访问其使用环境。然而，在上面的示例中，根据 baz() 的使用环境是函数被引用的地方还是被调用的地方，结果是不同的。
- 函数被引用的地方的情况下，
baz()的非本地环境是main()的环境，baz()主体中的x将引用main()中定义的x。这就是所谓的深度绑定。 - 函数被调用的地方的情况下，
baz()的非本地环境是foo()的环境，baz()中的x将引用foo()中定义的x。这就是所谓的浅绑定。这两种方法都是有效的，语言的绑定策略决定了使用哪种方法。
使用静态作用域时，绑定策略也会对递归函数内部本地定义的函数产生影响。然而，在使用静态作用域的语言中，深度绑定被普遍使用，因此函数定义时所建立的环境就是函数所能访问的环境。
Nested Functions #
函数式编程的一个主要特点是可以在另一个函数中定义一个函数，从而动态创建一个函数。在具有静态作用域的语言中，这种嵌套函数可以访问其定义环境，函数与其定义环境的组合称为 closure。嵌套函数中使用但在外层环境中定义的变量被称为 closure 所捕获。如果嵌套函数从外层函数中返回或泄漏，外层函数的环境通常必须在函数返回后继续存在，因为嵌套函数可能会访问其中的绑定。
举例来说，请看下面这个返回嵌套函数的 Python higher-order function：
def make_greater_than(threshold):
def greater_than(x):
return x > threshold
return greater_than
make_greater_than() 函数接收一个阈值，并构造一个嵌套函数来判断其输入是否大于阈值。threshold 变量位于 make_greater_than() 的激活记录中，但被 greater_than() 捕获。由于后者会返回阈值，因此激活记录必须持续存在，这样 greater_than() 的调用才能访问 threshold 的绑定。
请注意，每次调用 make_greater_than()，都会创建一个不同的 greater_than() 实例，并拥有自己的外层环境。因此，不同的 make_greater_than() 调用会产生不同的函数：
>>> gt3 = make_greater_than(3)
>>> gt30 = make_greater_than(30)
>>> gt3(2)
False
>>> gt3(20)
True
>>> gt30(20)
False
>>> gt30(200)
True
调用的父框架是 threshold 绑定为 3 的框架，因此 x > threshold 的值为 false。
非纯函数式语言可能允许修改捕获的变量。例如，下面使用嵌套函数定义了一个银行账户的数据抽象：
def make_account(balance):
def deposit(amount):
nonlocal balance
balance += amount
return balance
def withdraw(amount):
nonlocal balance
if 0 <= amount <= balance:
balance -= amount
return amount
else:
return 0
return deposit, withdraw
Python 需要 nonlocal ，因为它默认赋值给本地变量。然后，我们可以如下使用创建的函数：
>>> deposit, withdraw = make_account(100)
>>> withdraw(10)
10
>>> deposit(0)
90
>>> withdraw(20)
20
>>> deposit(0)
70
>>> deposit(10)
80
>>> withdraw(100)
0
>>> deposit(0)
80
Decorators #
Python 中的一种常见模式是通过应用高阶函数来转换函数或类。这样的高阶函数被称为 decorator，Python 有专门的语法来装饰函数：
@<decorator>
def <name>(<parameters>):
<body>
这在很大程度上相当于
def <name>(<parameters>):
<body>
<name> = <decorator>(<name>)
被装饰函数的定义被正常执行，然后在函数上调用装饰器。调用的结果与函数名称绑定。
举个例子，假设我们想通过打印函数名称及其参数来跟踪函数被调用的时间。我们可以定义一个高阶函数，接收一个函数并返回一个新的嵌套函数，该函数首先打印出原始函数的名称及其参数，然后调用该函数：
def trace(fn):
def tracer(*args):
args_string = ', '.join(repr(arg) for arg in args)
print(f'{fn.__name__}({args_string})')
return fn(*args)
return tracer
在这里，我们使用变量参数为原始函数传递任意数量的参数。为了简单起见，我们忽略了关键字参数。然后，我们可以使用装饰器语法将其应用到函数中：
@trace
def factorial(n):
return 1 if n == 0 else n * factorial(n - 1)
现在，只要调用 factorial()，我们就能得到参数的打印输出：
>>> factorial(5)
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
120
请注意，递归调用也会调用转换后的函数。这是因为在 factorial() 的外层环境中，factorial 这个名称现在与嵌套的跟踪函数绑定在一起，因此查找这个名称时，会调用跟踪函数，而不是原来的函数。这样做的一个副作用是产生了相互递归，即一组函数通过彼此间接地进行递归调用。
Lambda Functions #
嵌套函数定义允许在运行时构造函数，从而满足了函数成为 first-class entity 的要求之一。不过，到目前为止，我们只看到了嵌套函数定义的命名，即在定义环境中引入了绑定。这与其他一流实体，如数据值，形成了鲜明对比，后者可以在不绑定名称的情况下创建。就像构造不带名称的值很有用一样，比如将其作为参数传递或返回时，构造不带名称的函数也很有用。这些函数被称为匿名函数或 lambda 函数。
lambda 函数在函数式语言中无处不在，但许多常用的命令式语言也提供某种形式的 lambda 函数。不同语言的语法和功能各不相同，我们将研究几个具有代表性的示例。
Scheme #
在以函数式为主的 Lisp 系列语言中，lambda 是一种常见的构造，Scheme 也不例外。lambda 特殊形式构造了一个匿名函数：
(lambda (<parameters>) <body>)
使用 define 形式的函数定义可视为变量定义和 lambda 的简写：
(define (<name> <parameters>) <body>)
-->
(define <name> (lambda (<parameters>) <body>))
例如，下面的函数创建并返回一个匿名函数，该函数将给定的数字添加到参数中：
(define (make-adder n)
(lambda (x)
(+ x n)
)
)
这比只使用 define 的等价定义更简单、更恰当：
(define (make-adder n)
(define (adder x)
(+ x n)
)
adder
)
然后，我们就可以在各个参数上调用 make-adder 的结果：
> (define add3 (make-adder 3))
> (add3 4)
7
> (add3 5)
8
> ((make-adder 4) 5)
9
Scheme 中的嵌套函数使用静态作用域，因此匿名函数可以访问其定义环境中的变量 n。然后，它将自己的参数 x 与 n 相加，返回总和。
Scheme 并非纯函数式，它允许变量和复合数据的变异。嵌套函数，无论是否匿名，都可以修改其非本地环境中的变量。下面的函数创建了一个计数器函数，返回它被调用的次数：
(define (make-counter)
(let ((count 0))
(lambda ()
(set! count (+ count 1))
(- count 1)
)
)
)
set! 将变量变为给定值。这样，我们就可以使用 make-counter 函数了：
> (define counter (make-counter))
> (counter)
0
> (counter)
1
> (counter)
2
Python #
Python 支持使用 lambda 表达式的匿名函数。其形式如下：
lambda <parameters>: <body expression>
Python 中 lambda 表达式的语法对匿名函数产生了命名嵌套函数所没有的限制：主体必须是一个表达式，该表达式的值自动成为函数的返回值。在实践中，这个限制通常不是问题，因为 lambda 通常用于语句和副作用可能不合适的函数式上下文中。