201611 SICP系列 第7讲 流计算模型 学习笔记 (一) - xiaoxianfaye/Learning GitHub Wiki
- 1 Preface
- 2 An Example
- 3 Previously On Lecture 5
- 4 OO’s View & Stream’s View
- 5 Two Procedures
- 6 Data Abstraction
孙鸣老师在课程介绍中写到：
换个角度看世界——流计算模型
我们本可以生活在一个美丽的童话世界里，没有变量、没有副作用、每个函数闪耀着数学上极致的美。在这里，时间似乎是静止的，无论你何时去调用它，只要参数相同，它都会给予同样的结果。
但是，也许这种美只能存在于童话世界里，现实的残酷和复杂性使得我们无法忽视时间的存在，我们引入了赋值，就像打开了潘多拉魔盒，它带给我们强大的模块化力量，那种“现实照进程序”的魔力让我们无法抵挡；但同时黑暗面也随之而来，替换模型失效了；程序变得复杂、难以理解了；更为重要的是组合性变差了，从而应对现实世界复杂性的能力变弱了，而这本来正是我们引入赋值的初衷……
事情真的是这样么？有没有想过，或者某个瞬间，冒出一个念头，造成所有这一切的真正原因是我们对现实的认知就是错误的。也许时间只是一种错觉，根本就没有变化发生。
在这次课程中，我们将通过一些实例探讨这个计算问题，或许我们不能对这个问题给出完美、明确的答案，但是至少我们有勇气将它显式化出来，去直面思考它，这可能就是我们应对黑暗面的第一步。
我们先来看一个例子。
用数学家Cesaro提出的一种方法估算Pi。取两个随机数，计算它们的最大公约数。最大公约数有两种情况：一种是1，一种不是1。做很多次这样的实验。在这样的大样本实验中，两个随机数的最大公约数为1的次数在整个实验次数中所占的比例，或者说概率，跟Pi的关系如上图所示。
这个估算方法中用到了Monte Carlo方法，它是用概率统计来指导的方法。用做大量随机的试验的方法来对数值进行估计，随着试验次数越来越多，这个估计就会越来越逼近。Monte Carlo实验有两种停的方法：一种是估计足够逼近或两个估计值之间的误差非常小，一种是次数足够多。这样的方法多用于数值统计等方面，AlphaTTT、AlphaGo中也用到了这样的大样本随机试验方法。
一部分是Monte Carlo方法，还有一部分是取两个随机数，计算它们的最大公约数跟1之间的相等关系，即Cesaro实验。之所以分成两个部分，是因为Monte Carlo大样本随机跟实验本身没有关系。
先来看一下Erlang中的随机数。
Erlang中有一个random模块，它的uniform方法有两种形式：带参和不带参的。不带参的uniform/0，给你的是0到1之间的随机实数。带参的uniform/1，假设参数是整数N，且N≥1，给你的是1到N之间的随机整数。
计算当前的随机数是需要一个种子的，用这个种子算出随机数的同时再产生出为计算下一个随机数所用的种子。random:seed()用于生成种子。
如果两次调用random:uniform()，两次返回的结果是不一样的。说明random:uniform()不是一个纯数学函数，在看不见的地方有一个内部状态。
调用get(random_seed)，从进程字典中取random_seed这个key对应的值。
再调用一次random:uniform()，再调用get(random_seed)，random_seed这个key对应的值变了，产生了新的种子。也就是说，每次调用random:uniform()，它都会用当前随机数的种子，或者说是当前的状态，产生一个新的随机数，同时再产生一个新的种子，或者说新的状态，用来作为产生下一个随机数的种子。
在以上过程中，一开始是没有设置种子的。random:uniform()不带参，但有状态，状态保存在Erlang的进程字典中。只要在同一个进程中，调用random的任何uniform带参或不带参方法，用的都是进程字典的种子，状态放在进程字典中了。
如果起两个Shell，不事先设置种子，都调用random:uniform()，会发现返回值往往是一样的。也就是说这两个Shell的random:uniform()用的种子序列是一样的。
random模块中有一个seed0()方法，返回默认种子的初始值。
现在调用random:seed0()，它会返回固定的种子。
如果不调用random:seed()方法事先设置种子，直接调用random:uniform()获取随机数的话，它会通过seed0()把默认的种子设置到进程字典中。
我们可以看到，random是一个有自己内部可独立变化状态的计算对象，每次都是把新的种子保存在进程字典中。在使用random模块的时候，一定要记得设置种子。如果不这么做，产生的随机数序列根本不随机。
-define(RANGE, 100000).
estimate_pi(N) ->
random:seed(erlang:now()),
math:sqrt(6 / monte_carlo(N, cesaro(?RANGE))).
cesaro(N) ->
fun() ->
gcd(random:uniform(N), random:uniform(N)) =:= 1
end.
monte_carlo(N, Fun) ->
monte_carlo(N, Fun, 0, N).
monte_carlo(0, _Fun, Cnt, Total) ->
Cnt / Total;
monte_carlo(N, Fun, Cnt, Total) ->
case Fun() of
true ->
monte_carlo(N - 1, Fun, Cnt + 1, Total);
false ->
monte_carlo(N - 1, Fun, Cnt, Total)
end.
gcd(X, 0) -> X;
gcd(X, Y) -> gcd(Y, X rem Y).其实这里的设置种子的方式已经不太推荐使用了，在Erlang的crypto模块中有更好的方法。
运行结果：
在前面的内容中，random是一个有自己内部状态的模块，它有自己的状态，即当前随机的种子，所以它可以根据这个种子计算出下一个随机数和下一个状态。Monte Carlo只关注把你给我的实验做你要求的指定次数，返回通过的实验次数跟总实验次数的概率关系。Cesaro只关注Cesaro实验本身，即取两个随机数，看他们的最大公约数和1之前的关系。
在random模块中还有另外一类方法uniform_s，在uniform后面加了“_s”，s是State。
一开始获取进程字典，发现它是空的。这时，调用一下random:uniform_s()，并传入一个seed，它返回一个Tuple，Tuple的第一个元素是生成的随机数，第二个元素是下一个要用的种子。这时，在获取进程字典，它还是空的。也就是说，uniform_s()方法返回的随机数和下一个种子完全取决于你给的参数。用同样的参数多次调用uniform_s()，它们返回的结果都是一样的。
所以random: uniform_s()方法是一个纯数学函数。
现在还是要用Cesaro实验估算Pi值，但不用random:uniform，用random:uniform_s。
estimate_pi_2(N) ->
math:sqrt(6 / random_gcd_test(N, erlang:now())).
random_gcd_test(N, Ran) ->
random_gcd_test(N, Ran, 0, N).
random_gcd_test(0, _Ran, Cnt, Total) ->
Cnt / Total;
random_gcd_test(N, Ran, Cnt, Total) ->
{N1, Ran1} = random:uniform_s(?RANGE, Ran),
{N2, Ran2} = random:uniform_s(?RANGE, Ran1),
case gcd(N1, N2) of
1 ->
random_gcd_test(N - 1, Ran2, Cnt + 1, Total);
_ ->
random_gcd_test(N - 1, Ran2, Cnt, Total)
end.在用random:uniform_s写的程序中，把所有状态显式化在参数中了。这是一种迭代式的编程方式，在任何时候断下来都行，因为所有的状态都在参数中。
可以看到Cesaro和Monte Carlo纠缠在一起了，分不开了，也没法重用了。
- Assignment
- Side-effects
- State, Computational Objects & Identity
- Modularity
- OO
在第一讲到第四讲中，我们讲的都是纯数学函数，没有任何副作用，变量其实就是值，只不过带了一个Symbol。有非常简单的机制、模型来帮助我们理解这样的语义。在第五讲中，我们引入了赋值。看上去很简单的一个“赋值”语义的引入，带来的变化是翻天覆地的。
在第一讲到第四讲中，我们已经做了很多非常复杂的程序，例如Picture Language、泛型算子等，已经非常复杂了，但都不需要引入赋值，就是因为Procedure或函数是一等公民，它本身既可以作为结果返回又可以作为参数，而且还具有非常强大的组合性，再加上一些抽象手段、闭包特性，所以根本不需要引入赋值。
但在第五讲中还是引入了赋值，原先的替换模型就失效了。替换模型就是说，一个变量跟一个值能对应，每次拿到语句之后，把变量的地方换成值，生成一个新的语句，对它进行执行，就可以得到语义的含义了。替换模型失效以后，我们引入了更加复杂的环境模型。大多数语言中都有赋值，所以我们用到的大多数都是环境模型。用到了平时经常讲的作用域、自由变量、绑定变量，在第五讲中对自由变量和绑定变量做了明确的定义。
在环境模型中，环境是由一个个的Frame被链接起来的。Frame之间的链接叫Parent Link。Frame中存放着变量和值。在替换模型中，变量指的是值，变量跟值可以划等号。在环境模型中，变量跟值不能划等号，变量指向了一个地方，这个地方放着一个值，而且这个值可能会发生变化。
random:uniform()不是一个纯数学函数，进程字典就是可以改变变量的地方，状态能够发生改变，就有了副作用。原先函数的调用跟时间没有任何关系，什么时候去调用它都一样。现在因为引入了赋值，引入了时间，在赋值的前后去调用，作用是不一样的，返回的结果也是不一样的，这就是我们说的副作用。
引入赋值，有了状态，能力变得强大了。random是一个可计算对象，它自己有内部状态，它可以进行一些计算，它可以跟别人进行一些信息交互。有了对象以后，就有了唯一性问题，Identity标识性的问题。我们怎么知道这个对象是同一个对象，也就是说对象的属性没有发生变化，我们怎么知道对象的属性没有发生变化，就得知道同一个对象的同一个属性没有发生变化，那我们又怎么知道是同一个对象的同一个属性呢，这是一个哲学问题。
引入赋值以后，能力是变得强大了，但也带来了很多麻烦，那引入赋值到底是为了什么呢？Modularity，模块化的能力。模块化的能力是非常强大的。假如我们不具备模块化的能力，所有的程序可能就像刚才的estimate_pi_2程序一样，一个东西囊括了所有的东西，因为每个对象都不能有自己独立可变化的状态，不能把自己的影响受控在自己的范围内，而泄漏到了外面。
OO面向对象，不是说我们看到的东西一切皆对象，而是说我们用这样的方式来思考问题。我们希望对现实世界中的东西建模，那怎么建模呢？我们希望现实世界对我们的程序能有引导作用，或者说现实能够照进程序。我们希望在现实世界中看到的对象，在计算机中能有相应的对象进行对应；在现实世界中在对象上所发生的一些事情，对象上所具备的一些功能，在计算机中模拟的对象上也复制一份过来；在现实世界中两个对象之间的关系，也能体现在计算机中模拟的对象上。这样的好处在于，如果我们认为这样是一个合理的方式，我们就自然而然地获得了模块化的能力，也就是说，现实世界中我们看到什么样子，我们就直接把它弄到计算机中，我们就自然而然地以为在现实世界中仅在这个对象上发生影响的事，在程序世界里也仅在这个对象上发生。我们现在就需要在计算机中去模拟现实世界中的对象，每个对象有自己的状态，跟其它对象的交互都通过传递消息，我们传递消息是我们状态改变，别人传递消息是他们状态改变，共同交互协同来模拟现实世界。
这是OO的视角。从这样的视角出发就会看到，有了可计算对象，加上它自己内部的状态；在现实世界中有时间，我们希望在计算机中的时间去模拟它，现实世界中的对象本身随着时间变化，在计算机中也让这个模拟的对象随着计算机里的时间变化，计算机中模拟的对象随着时间变化是通过赋值体现出来的。
现实世界中有对象，计算机中也有模拟的对象；现实世界中对象之间有关系，计算机中模拟的对象之间也有关系；在现实世界中对象上体现的功能，在计算机中模拟的对象上也有。这样我们自然而然地认为，变化被局限化了。在现实世界中仅在xxx身上发生的事情，在计算机中仅在对应的模拟的对象上发生。这就是模块化。我们经常说需求模块化，其实我们希望达到的就是这样的效果。如果真的能做到像这样的隔离，肯定就很好。
我们把现实世界中的时间也引入了计算机的模型，我们希望模型能够随着时间的变化模拟现实世界中对象随着时间的变化。在计算机中模拟对象状态随着时间变化是通过赋值体现出来的。赋值刻画了时刻。在没有赋值的时候，原先所有的东西都是纯数学的，就是因为它们相对来说跟时间没有关系，任何时候去调用它们都是一样的。一旦引入赋值，它刻画了任何一个时间，这时才会有在某个时间的前后作用是不一样的，才会发生两次调用不一样，即函数的副作用。
在前面的例子中，random、monte_carlo、cesaro这三个可以认为是从OO的视角构建的，每一个都可以独立，特别是random它有自己独立的可变化的状态。如果不这样做，它们全部被纠缠在一起了，不具备模块化的能力，控制软件复杂性的能力就会大大降低，因为我们平常所遇到的程序的复杂性肯定是要超过这个例子的。
这是在前面做过的练习——电路系统，用OO模拟了数字电路。从OO的视角，我们会把电路系统分成好几块，每块都有自己独立的内部状态。两个与门、一个或门、一个非门，它们之间游走的信息都体现在线(wire)上，它们的状态都保存在wire上。
OO的视角毕竟给我们带来了很大的复杂性，当然这个复杂性是为了能够给我们带来模块化的能力，或者说控制软件复杂性的能力，但这到底是否值得呢？我们可能是采用了一种我们自己认为比较合理的方式。我们认为时间是要存在的，我们要用计算机中的时间去模拟现实世界的时间，用模型中对象的变化模拟现实世界中的对象随着时间的变化，这是不是唯一的模块化或控制软件复杂性的技术呢？会不会我们本身的认识就是错误的呢？有可能我们认为时间是必须要解决的问题，状态就是在随着时间变化，就是要通过对象之间的交互来传递状态，但可能时间并不存在呢？
把一支笔以抛物线扔出去。从OO的视角来看，对象的位置、速度无时无刻都在发生变化。稍微引入一丁点儿相对论，把时间纳入到整个范畴来讨论。笔扔出去的抛物线路径就是整个时空中的一个路径，在整个时空中间是不变的存在，因为时间已经被考虑进去了，就是一条不变的时空路径。这就是另外一种能够把程序模块化、组织程序的方式。
OO其实是一个Message Passing方式，通过消息传递来改变对象内部状态。但其实还有另外一种思考的方式——Stream Processing，即流处理的方式。
在OO中，是深入到系统里面看有多少电路对象、多少线、线上游走的是哪些状态、这些状态又是如何互相改变。从流处理(Stream Processing)的角度，或者从信号工程师的角度，会把它们看作一个整体，看成一个滤波器，图中左边的波形图经过滤波器产生右边的波形图。
现在有两种看待世界的方式。一个是变量随着时间在变化，把它描述成一个跟时间相关的函数f(t)。如果我们关注的是每一个时间的点的话，扔出去的笔在每一个点上它的属性(速度、加速度等)都是不一样的。但如果我们关注的是整个的变换，把时间也放到空间中来考虑的话，f(t)这个函数是不变的，只是把时间更加显式化地表达了。这就是另外一种方式。
遍历由整数构成的完整二叉树(就是一个tuple：左边是left，右边是right、可以嵌套)，如果节点是计数，就把它平方，遍历完了以后，把奇数的平方求和。
sum_odds_square({Left, Right}) ->
sum_odds_square(Left) + sum_odds_square(Right);
sum_odds_square(N) ->
case is_odd(N) of
true ->
N * N;
false ->
0
end.
is_odd(N) ->
N rem 2 =/= 0.
test_sum_odds_square() ->
411 = sum_odds_square({{1, {2, 7}}, {19, {12, 14}}}),
test_sum_odds_square_ok.
给一个整数N，针对1到N中的每个数，计算它的Fibonacci数，如果Fibonacci数是奇数，把它对应的索引收集到一个列表中。
odd_fibs(N) -> odd_fibs(1, N).
odd_fibs(C, N) when C > N -> [];
odd_fibs(C, N) ->
case is_odd(fib(C)) of
true ->
[C | odd_fibs(C + 1, N)];
false ->
odd_fibs(C + 1, N)
end.
fib(N) -> fib(N, 0, 1).
fib(0, A, _) -> A;
fib(N, A, B) -> fib(N - 1, B, A + B).
test_odd_fibs() ->
[1, 2, 4, 5] = odd_fibs(6),
test_odd_fibs_ok.看看这个Procedure是否有共同之处？
都是收集动作，true/false的分支判断体现的是过滤，sum_odds_square的平方计算对应odd_fibs的Fibonacci数计算。
从一个整体到另外一个整体来考虑，不考虑中间那些复杂的控制结构，比如判断是否是奇数，是否到了整数的边界，是两棵完整的树还是已经到了叶子节点，其实都可以表述成下面的方式。
如果从流的视角看待Procedure 1：
先把二叉树中的叶子节点都排列出来，过滤出奇数，对它们做平方，最后做一个累积的操作(累加、初始值为0)。
如果从流的视角看待Procedure 2：
列举出1到N的数，对它们做Fibonacci数的映射操作，过滤出奇数，最终做一个累积的操作(Construct操作、初始值为[])。
Commonality is completely obscured in previous procedures!
按照之前的程序的书写方式，这些共同点完全被掩盖在其中了，没有办法把这些在概念上非常清楚的概念(Enumerate 枚举、Map 映射、Filter 过滤、Accumulate 累积)从中抽取出来。
其实，大部分程序都能表示成这样的结果。
sum_odds_square({Left, Right}) ->
sum_odds_square(Left) + sum_odds_square(Right);
sum_odds_square(N) ->
case is_odd(N) of
true ->
N * N;
false ->
0
end.在这个Procedure中，模式匹配和整个递归结构都是在Enumerate，“sum_odds_square(Left) + sum_odds_square(Right);”是Accumulate操作，0是初始值。递归结构中有一部分是Map、有一部分是Accumulate操作以及Enumerate操作。
odd_fibs(C, N) when C > N -> [];
odd_fibs(C, N) ->
case is_odd(fib(C)) of
true ->
[C | odd_fibs(C + 1, N)];
false ->
odd_fibs(C + 1, N)
end.在这个Procedure中，指定初始值、“when C>N”、递归结构都是在Enumerate，“[C | odd_fibs(C + 1, N)];”是Accumulate操作，[]是初始值。
接下来，引入流处理。流是为了描述在那些方框中通过箭头流向的数据。
在此之前，我们把原来的课程稍微复习一下。有一些原生的数据、原生的过程，通过一些组合的手段，能够组合成更复杂的过程去描述更复杂的现实世界或程序，再通过抽象的手段赋予他们名字，使得我们能够利用。
我们有一些原生的数据，但这些原生的数据可能不足以描述更复杂的一些应用，需要对数据进行组合。上图是有理数的运算，在这里用到了一种编程手段“数据抽象”来表达有理数。数据抽象可以帮助我们表达更加复杂的组合的数据，它解决的问题是数据的使用层跟数据的表示层的分离。Wishful Thinking，你不用管下面是怎么做的，那是George的事情。它提供了一个良好的界面，使得你在上面在组合复杂数据的同时，又不用关心这些复杂数据到底是如何组合的，甚至不用关心它到底是不是数据。
在这个例子中，我们希望对有理数做四则运算，我们头脑中有一个有理数的概念，有理数到底体现在程序中的哪里呢？有理数是两个整数，可以用两个整数来表示，但如果这样去写程序的话，就会困扰有理数到底在哪里，这就需要一层数据抽象。
我们既然要去组织一个复合数据，要有手段能够把复合数据构造出来，也要有手段把这些数据中的部分给取出来，也就是构造器和选择器。
通过构造器产生一个有理数，具体怎么产生是George要做的事儿。当一个有理数用这样的数据抽象表示出来以后，符合公约，用numer得到分子，用denom得到分母。
用数据抽象表达的是数据本身在使用跟在表示上的一个公约。
有理数是由两个整数构造的“那朵云”。落实到具体的语言中，必定还要有一个手段把这两个数粘合到一起。
在Erlang中，这个粘合手段就是List。[X|Y]是List的Constructor，hd()和tl()是Selector。
上面第一幅图是Pair的公约。上面第二幅图是一个Pair，或者可以认为是一个List，前面是head，后面是tail。
每个语言基本都会提供类似这样的数据结构，帮助我们把原生的数据粘合在一起。数据抽象能够将数据的表示和使用分离，但下面真的一定要是列表吗？
上面第一幅图是数据抽象Pair在使用和表示时要遵循的公理。上面第二幅图是一种数据表示方法，只要满足公理就行。
控制软件复杂性的一个特点是，越来越分不清什么是数据、什么是过程，不再像传统编程中那么泾渭分明。数据抽象给我们带来的好处就在这里。
上图是有理数数据抽象的公理，不仅仅只是获取。既是跟George签订的协议，也是有理数本身是什么的公理。