Erlang的乐趣犹如驾驭魅影

在电影<<阿凡达>>里,有一条超级大的翼龙,它叫做魅影,男主角为了赢得蓝色族人的信任必须学会骑魅影。一般来说,魅影不喜欢被骑,但如果你和它打一架,而且把它制服,然后把你的蓝马尾辫连接到魅影的尾巴上,你就能拥有它的生命。这就像拥有一辆你能控制的飞车,在与强敌作战时,你可以很方便地用你的思想控制它,给未来的同事留下深刻印象。但是学会骑魅影是很危险的,很少有人能成功。

我喜欢把Erlang编程语言看作是一条魅影。大多数人都害怕Erlang。关于其能力的传说比比皆是。为了掌握它,你必须与它战斗,征服它,并(最后)把你的思想与它联系起来。但假设你能活下来,你就可以控制世界上最先进的服务器平台,让它做事情的时候通常无需再思考。现在让我来告诉你:驾驭魅影是很有趣的。

本指南旨在教会你Erlang的思想,这样你就不会害怕而离开,而是可以战胜你自己的魅影。我将只介绍一些Erlang语言特性,但是我们将使用它们来解决大量实际问题。它的目的是让你想要并且有信心去学习并掌握Erlang语言其他知识。

欢迎您将这些示例输入到自己的Erlang shell中,并执行它们,不过这些示例的设计是为了便于阅读而设计的。我建议你把这份文件打印出来,在舒适的椅子上仔细地阅读,并且远离电子邮件、编译器、3D电影以及其他干扰。

目录

  1. 定义函数: 一个简单布尔逻辑库
  2. 递归地调用函数:一个简单算术运算库
  3. 整数列表:基本字符串处理
  4. Erlang算法的乐趣
  5. 下一步
  6. 源代码

定义函数: 一个简单布尔逻辑库

在Erlang里,函数由一个或多个分支语句组成。最后一个分支语句必须用 . 号结束;而其他分支语句必须用 ; 号结束。当函数被调用的时候,第一个和入参匹配的分支语句被执行。你可能会思考,如果C语言的switch语句暴露在有毒污泥中并成为超级英雄,那么函数将会怎样。

最简单的例子,一个函数只有一个语句。如下所示,函数 noop 简单地返回它的参数,即变量A(变量总是大写开头的):

1
noop(A) -> A.

注意,Erlang没有 return 语句。函数总是返回最后一个表达式的结果。因为每一个表达式都有一个结果,而且每一个函数分支语句至少有一个表达式,所以每一个函数总是有一个返回值。

现在假设我们希望实现一个布尔函数 not,它把true或false作为它的参数。not 函数需要两个子句:

1
2
not(true) -> false;
not(false) -> true.

每次 not 函数被执行,Erlang首先测试入参是否是true(如果是,执行第一个子句),然后再测试入参是否是false(如果是,则执行第二个子句)。用入参和函数定义进行匹配被称为模式匹配。模式匹配使得在不使用内部控制结构的情况下很容易编写复杂的函数。

我们可以使用模式匹配来判断同一变量是否在参数列表中出现不止一次。比如,如下函数实现相等操作符:

1
2
equals(A, A) -> true;
equals(A, B) -> false.

如果两个入参相同,则函数返回true;否则,函数返回false。

小心!在这个函数里子句的顺序很重要。如果像下面这样写,则是错误的:

1
2
equals(A, B) -> false; % 错
equals(A, A) -> true.

为什么会错呢?Erlang首先尝试匹配第一个子句。但是如果两个入参相同,第一个子句依然匹配,A和B被简单地绑定为相等的值。第二个子句永远不会被执行到。在形参列表里用不同名字到变量并不是说一定要给它们绑定不相等的值。

我们现在已经准备好实现更多的布尔逻辑。如下是 and 的实现:

1
2
3
4
5
% 与: 如果两个入参是true则是true, 否则是false
and(true, true) -> true;
and(false, true) -> false;
and(true, false) -> false;
and(false, false) -> false.

你可能认为所有这些真值表子句太啰嗦。它们的确是很啰嗦。我们可以用一个特别的匿名变量来将后面三个子句缩减到一个子句:

1
2
3
% 与: 如果两个入参是true则是true, 否则是false
and(true, true) -> true;
and(_, _) -> false.

匿名变量(_)总是匹配任何数据。它没有被赋值,所以正如我们在上面的第二个子句中看到的,参数列表中的两个或多个下划线变量不需要匹配相同的项。匿名变量通常用来“丢弃”我们不关心的一部分模式。

现在我们有了常规变量和下划线变量,我们的布尔逻辑库的其余部分就容易写了。花点时间了解一下为什么下面的每一个功能都正好符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% 或: 如果一个或两个参数是true则是true,否则为false。
or(false, false) -> false;
or(_, _) -> true.

% 异或: 两个参数不同则是true,否则为false。
xor(A, A) -> false;
xor(_, _) -> true.

% 非与: 两个参数是true则为false,否则为true。
nand(true, true) -> false;
nand(_, _) -> true.

% 非或: 两个参数是false则为true,否则为false。
nor(false, false) -> true;
nor(_, _) -> false.

如你所见,模式匹配给予Erlang函数极大的表达能力。在下一节中,我们将把模式匹配与递归相结合,建立一个新的算术运算库。在大多数语言中,递归通常是最后的手段,只用于实现复杂的算法。在Erlang,递归通常是最简单和最有效的方式来做一些平常的事情。

递归地调用函数:一个简单算术运算库

Erlang有一套丰富的算术运算符。不过在这一节里,我们不会使用它们。相反,我们将只使用我们目前为止学到的函数知识来构建我们自己的完整的算术运算库。

本节中的任务诚然是人为的,并且递归绝对不是在现实世界中解决这个问题的最简单的方法。然而,本节的练习将是好的方式来实践递归思维来为第3节做准备,在那里,递归是解决问题的最好方法。

回想一下递归函数至少有两部分:它们必须首先测试某种基本情况(算法终止),如果基本情况不满足,递归函数必须执行一些逻辑,然后发出对自身的调用。在Erlang,递归函数通常至少有两个子句:一个“基本情况”子句和“所有其他情况”子句。

事情将很快变得清晰。为解决问题,为将提供两个函数,算术运算库剩余的部分将以它们为基础来构建:incr 和 decr。假设incr增加入参,decr减少入参,如下所示:

1
2
incr(A) -> A + 1.
decr(A) -> A - 1.

我们可以用这两个函数将任何两个正整数加到一起吗?

事实上我们可以!

1
2
3
% 两个正整数相加
add(A, 0) -> A.
add(A, B) -> add(incr(A), decr(B)).

有时从底层到顶部阅读递归函数是最容易的。所以先看第二个子句,它说将A和B相加与将(A+1)和(B-1)相加是相等的,这明显是正确的。因此,这个函数一直给A加一,给B减一,直到B为0。当B为0的时候,函数结束(第一个子句)。这时,add函数被递归调用了B次,也就是说A被增加了B次,因此最后的结果就是 A+B。

现在有点有趣,不是吗?让我们来实现减法:

1
2
3
% 从A减去B(B是正整数)
sub(A, 0) -> A.
sub(A, B) -> sub(decr(A), decr(B)).

一样的思想。从第二个子句开始,我们看到(A - B)和((A - 1) - (B - 1))相等。这明显是对的。递归调用一直持续到B为0,这个时候,A被减少了B次,结果就是A - B。

当B是负整数的时候,这些函数都不无效。我们可以非常简单地修改add函数以适应负整数。

1
2
3
4
% 任意两个整数相加
add(A, 0) -> A;
add(A, B) when B < 0 -> add(decr(A), incr(B));
add(A, B) -> add(incr(A), decr(B)).

请注意,在第二个子句中Erlang卫句的使用(when B < 0)。我们可以在参数列表后用关键字 when 再加上表达式来指定条件判断。有许多种卫句,但是现在,我们只做整数的比较。

sub函数的修改也差不多:

1
2
3
4
% 从整数A减去任意整数B。
sub(A, 0) -> A;
sub(A, B) when B < 0 -> sub(incr(A), incr(B));
sub(A, B) -> sub(decr(A), decr(B)).

完成了加、减函数,乘法就很容易实现了。正如我们把加法作为一系列加一一样来实现,我们将把乘法作为一系列的加法来实现,还是使用递归。我们使用这样的等式:A × B = A + A × (B - 1)。

1
2
3
% A乘以B(正整数)
multiply(A, 0) -> 0;
multiply(A, B) -> add(A, multiply(A, decr(B))).

增加对负整数的支持也很容易,因为:A × (B + 1) - A = A × B:

1
2
3
4
% 整数A乘以任意整数B
multiply(A, 0) -> 0;
multiply(A, B) when B < 0 -> sub(multiply(A, incr(B)), A);
multiply(A, B) -> add(A, multiply(A, decr(B))).

除法呢?没问题。整数的除法,我们真正关心的是两个操作:求商和求余。这两个操作,我们都用被除数减去除数,直到我们接近0。求余操作更容易些:

1
2
3
% 求 A 除以 B 的余数
remainder(A, B) when A < B -> A;
remainder(A, B) -> remainder(sub(A, B), B).

至于求余函数,我们将使用Erlang里的通用模式,内部递归函数,以区别主接口。内部递归函数有一个额外参数,它跟踪我们已经减掉除数的次数。

1
2
3
4
5
6
% 求A 除以 B 的余
quotient(A, B) -> quotient(A, B, 0).

% 包括累加器的内部函数
quotient(A, B, Answer) when A < B -> Answer;
quotient(A, B, Answer) -> quotient(sub(A, B), B, incr(Answer)).

有了乘法和除法,我们就可以解决现实的一些问题。例如,让我们来实现一个幂函数。我们使用与前面完全相同的想法,认识求一个数的幂实际上只是一系列的乘法调用。也就是说,$$A^B = A × A^{B-1}$$

1
2
3
% 求A的B次幂(正整数)
pow(A, 0) -> 1;
pow(A, B) -> multiply(A, pow(A, decr(B))).

在实践中,所有这些功能都是非常低效的,因为他们把所有的一切都转变为一系列递增或递减。但是这种递归的思想框架对于充分利用Erlang是绝对必要的,正如我们将要构建的字符串处理库中所看到的。

整数列表:基本字符串处理

在Erlang里,字符串用整数列表来表示。这些整数是ASCII字符码或者是Unicode码点。例如,字符串”dog”就是表示为由100 (“d”), 111 (“o”), 103 (“g”)组成的列表。Erlang列表的字面量是由方括号括起来的,所以如果你愿意的话,”dog” 可以写为 [100, 111, 103]。要获得一个字符的编码,只要简单地在其前面加上美元符号\$。所以[\$d, \$o, \$g] 和 [100, 111, 103] 以及”dog”是相等的。

每一个列表都分为两部分:头部和尾部。头部是第一个元素,尾部则是除了头部外剩下的部分。列表是一个递归数据结构。列表的尾部是一个列表,它有自己的头部和尾部。以此类推。

空列表表示为[],它没有头部,也没有尾部。

在Erlang里,添加一个元素到列表的头部使用 | 操作符(管道符号):

1
NewList = [NewItem | OldList]

| 也可以用在模式匹配中,从一个列表中抽取头部元素:

1
2
some_function([FirstItem | RestOfList]) ->
... do something with FirstItem ...

反转一个列表,使用函数lists:reverse()。反转一个列表可能看起来是一个不太常用的操作,但正如我们将看到的,它在Erlang实现列表算法时一直使用。

我们现在对字符串了解得足够多了,可以开始做一个例子。让我们写一个函数,将输入的第一字符转换为大写字符。

这个函数的基本思想是简单的。我们检查输入字符串的第一个字符(头部)是否是小写ASCII字符。如果是,我们把它转换成大写(通过增加大写ASCII字符和小写字母之间的差值),然后把它和尾部重写组合成一个字符串。如果不是,我们就简单地返回输入字符串。

1
2
3
4
capfirst([Head | Tail]) when Head >= $a, Head =< $z ->
[Head + ($A - $a) | Tail];
capfirst(Other) ->
Other.

在这里,我们使用了一些新的数学运算符,它们其中的含义你可能会明白。还要注意,逗号用于分隔同一子句中的多个判断条件。

如果你认为很好玩,那就等到你尝试将整个字符串转换为大写。在一个没有for循环的世界,一个进程如何处理字符串的每个元素?是时候重新审视我们的老朋友:递归。

1
2
3
4
5
6
7
8
9
10
11
% 公共函数
uppercase(String) ->
uppercase(String, []).

% 内部函数
uppercase([], Output) ->
lists:reverse(Output);
uppercase([Char | Rest], Output) when Char >= $a, Char =< $z ->
uppercase(Rest, [Char + ($A - $a) | Output]);
uppercase([Char | Rest], Output) ->
uppercase(Rest, [Char | Output]).

和我们在第二节写的函数 quotient 一样,这个函数有一个公共接口以及一个有额外参数的内部递归函数。额外的参数称为累加器,它的初始值为空列表。一般的策略是从输入的头部弹出一个元素,转换它,并将其加到累加器的头部。当我们处理完输入,我们要的结果将存储在累加器里,只不过它的顺序是反的。因此,我们调用 lists:reverse 并返回结果给公共接口函数。

让我们一句一句地检查一下内部函数子句,看看这个策略是如何实现的。

在基准情况下,没有更多的输入。因此,我们反转累加器:

1
2
uppercase([], Output) ->
lists:reverse(Output);

如果还有输入,并且下一个字符是处于ASCII小写字母 a 和 z 之间的话,我们把它转换为大写字母,并把它加到累加器上,然后在剩下的输入上递归地调用 uppercase 函数:

1
2
uppercase([Char | Rest], Output) when Char >= $a, Char =< $z ->
uppercase(Rest, [Char + ($A - $a) | Output]);

当下一个字符不是小写的ASCII字符的时候,最后一个子句匹配。在这种情况下,我们只需将字符从输入毫无更改地直接移动到累加器:

1
2
uppercase([Char | Rest], Output) ->
uppercase(Rest, [Char | Output]).

这个算法到此就结束了。写一个将所有字符转为小写的函数 lowercase ,这个作为一个练习由读者自己实现。

我们接着来实现一个有趣的函数。把每个单词的第一个字母转成大写,而不是把单词的里的所有字母转成大写。我们叫这个函数做 titlecase 。

1
2
3
4
5
6
7
8
9
10
11
titlecase(String) ->
titlecase(String, []).

titlecase([], Output) ->
lists:reverse(Output);
titlecase([Char | Rest], [] = Output) when Char >= $a, Char =< $z ->
titlecase(Rest, [Char + ($A - $a) | Output]);
titlecase([Char | Rest], [$\ |_] = Output) when Char >= $a, Char =< $z ->
titlecase(Rest, [Char + ($A - $a) | Output]);
titlecase([Char | Rest], Output) ->
titlecase(Rest, [Char | Output]).

titlecase 和 uppercase 的不同是,我们在决定处理每个字符之前用模式匹配检查一下累加器。如果累加器是空的(第二个子句),说明我们在输入的开始之处,并且要将接下来的字母大写化。如果累加器有一个空的字符在它的头部(第三个子句),说明我们在一个单词的开始之处,并且要将接下来的字母大写化。注意,空格字符的整数表示是用美元符号加上一个空格(”$\ “)。在这里我们也使用了匹配操作符(”=”),这使得在参数列表里可以很好地结合模式匹配和变量赋值。

如你所见,递归、累加器和模式匹配是一个强大的组合。我们可以编写无状态变量或正则表达式的上下文相关算法。更重要的是,我们可以清楚地表达问题的解决方案,并对我们的算法的正确性有信心。Erlang的乐趣在于编写代码而不必担心忘记某些东西。

Erlang算法的乐趣

现在我们可以开始好好玩耍了。既然你现在知道Erlang的基本知识,我就不会花太多时间来解释下面的算法了。它们对你来说只是让你思考和享受。

面试中一个经典的问题是,如何将一个字符串转换为整数(如:C语言中的atoi函数)。如下是Erlang的实现:

1
2
3
4
5
6
7
8
9
10
11
% public
atoi([$- | String]) -> % negative
-1 * atoi(String, 0);
atoi(String) -> % non-negative
atoi(String, 0).

% internal
atoi([], Acc) ->
Acc;
atoi([C | Rest], Acc) when C >= $0, C =< $9 ->
atoi(Rest, 10 * Acc + (C - $0)).

注意,这里的累加器是一个整数,而不是我们前面例子里那样上一个字符串。当然,原则上,累加器可以是任何东西。

现在假设我们要做反向操作:将一个整数转换为字符串。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
% public
to_string(0) ->
[$0];
to_string(Integer) when Integer < 0 -> % negative
[$-|to_string(-1 * Integer, [])];
to_string(Integer) -> % positive
to_string(Integer, []).

% internal
to_string(0, Acc) ->
Acc;
to_string(Integer, Acc) ->
to_string(Integer div 10, [(Integer rem 10) + $0 | Acc]).

注意,在这里我用了两个整数操作符:div是整数除,rem是整数取模(在C风格语言里通常用%表示)。

让我们假设用Erlang来写一个工具套件,需要将正整数的列数字转换为大多数电子表格使用的字符串表示形式(“A”到“Z”,然后是“AA”到“ZZ”,以此类推)。代码如下:

1
2
3
4
5
6
7
8
9
% public
num2excel(Number) ->
num2excel((Number-1) div 26, (Number-1) rem 26, []).

% internal
num2excel(0, Remainder, Acc) ->
[(Remainder + $A)|Acc];
num2excel(Quotient, Remainder, Acc) ->
num2excel((Quotient-1) div 26, (Quotient-1) rem 26, [(Remainder + $A)|Acc]).

或者在我们的工具套件里的单词处理器需要单词统计函数。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
% public
wordcount(Input) ->
wordcount(Input, 0).

% internal
wordcount([], Count) ->
Count;
% End of the input. Count the last word, if we didn't already
wordcount([C1], Count) when C1 =/= $\ ->
Count+1;
% End of a word. Count it.
wordcount([C1, C2|Rest], Count) when C1 =/= $\ , C2 =:= $\ ->
wordcount([C2|Rest], Count + 1);
% Not the end of a word. Don't count it.
wordcount([_|Rest], Count) ->
wordcount(Rest, Count).

在这里我们用了两个新的操作符:=:= 是Erlang的相等操作符,=/=是Erlang的不等操作符。现在你明白了。

当然,如果我们计划构建一个产品来与Microsoft FrontPage竞争,那么我将需要一个方法来转义HTML特殊字符。这个功能实现起来不费吹灰之力,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% public
escape(String) ->
escape(String, []).

% internal
escape([], Acc) ->
lists:reverse(Acc);
escape([$< | Rest], Acc) ->
escape(Rest, lists:reverse("&lt;", Acc));
escape([$> | Rest], Acc) ->
escape(Rest, lists:reverse("&gt;", Acc));
escape([$& | Rest], Acc) ->
escape(Rest, lists:reverse("&amp;", Acc));
escape([C | Rest], Acc) ->
escape(Rest, [C | Acc]).

上述代码有一些新东西:有两个参数的lists:reverse()。它反转第一个参数,然后把第二个参数加在其后。这样的代码很方便,我们反向构建累加器(在字符串处理中经常如此)。

Outlook Express最好要小心了,因为我们现在有了编写杀手级电子邮件客户端的工具。让我们将即将发送出去的邮件用每行80个字符的方式来格式化。当我们扫描输入的时候,我们将有一个单词累加器,并且有一个输出累加器,我们要决定什么时候将累加的单词增加到输出累加器里,以及什么时候增加新行字符。在此你需要一个新的操作符:++ 将两个列表串起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
% 公共接口
wordwrap(Input) ->
wordwrap(Input, [], [], 0, 80).

% 内部函数
% 没有输入了,我们结束处理,输出结果
wordwrap([], Acc, WordAcc, LineLength, WrapAt) ->
lists:reverse(WordAcc ++ Acc);

% 遇到输入里的换行符
wordwrap([$\n | Rest], Acc, WordAcc, LineLength, WrapAt) ->
wordwrap(Rest, [$\n | WordAcc ++ Acc], [], 0, WrapAt);

% 当前行长度达到需要换行的长度,并且输入字符为空字符。新增一行
wordwrap([$\ | Rest], Acc, WordAcc, WrapAt, WrapAt) ->
wordwrap(Rest, [$\n | WordAcc ++ Acc], [], 0, WrapAt);

% 当前行长度未达到换行长度,输入字符为空字符。
wordwrap([$\ | Rest], Acc, WordAcc, LineLength, WrapAt) ->
wordwrap(Rest, [$\ | WordAcc ++ Acc], [], LineLength + 1 + length(WordAcc), WrapAt);

% 在建立单词时其长度大于需要换行长度
wordwrap([C | Rest], Acc, WordAcc, 0, WrapAt) when erlang:length(WordAcc) > WrapAt ->
wordwrap(Rest, Acc, [C | WordAcc], 0, WrapAt);
wordwrap([C | Rest], Acc, WordAcc, LineLength, WrapAt)
when erlang:length(WordAcc) + LineLength > WrapAt ->
wordwrap(Rest, [$\n | Acc], [C | WordAcc], 0, WrapAt);

% 构建一个单词
wordwrap([C | Rest], Acc, WordAcc, LineLength, WrapAt) ->
wordwrap(Rest, Acc, [C | WordAcc], LineLength, WrapAt).

上述就是我们实现的代码。

下一步

Erlang是一种丰富的语言,当你深入了解它时,你会更加欣赏它。为了直接讲解本文中的算法,我刻意避免覆盖Erlang的主要数据结构、库及其内置函数。但是如果你喜欢用Erlang的思维框架思考问题,我鼓励你阅读本文后去学习它其余的知识,并开始把Erlang用在工作中。Erlang拥有一个活跃的、不断增长的、友好的开发人员社区、令人兴奋的有潜力的应用程序以及许多有趣和有用的开源项目。

诚然,学习驾驭魅影是艰难的事情,但一旦你掌握了它,你一定会为你的付出而喜悦。

源代码

下载本文中所示的源代码

*原文链接http://www.evanmiller.org/joy-of-erlang.html