习惯经验的强大惯性源自于背景的长期稳定性。软件体系的快速变革让我们忽视了硬件体系的长期稳定。这种稳定性使得很多习惯经验变成了不言自明的信条大多數的软件设计方法的革新只不过是用旧石斧打造出来新石斧。在C中我们使用getc,putc来进行IO,在Java中无非是变成了System.in.read(),System.out.print ()为什么IO必定是这种形式呢?这是因为峩们长期使用着同一种计算机。我们知道PC/Mac这样的计算机中CPU与IO设备进行通信需要通过各种总线。下面这张图演示了CPU与IO设备之间通信的基本過程.

以C语言为代表的传统的IO,实际上是单CPU上单任务工作模式的投影在单台计算机上, 传统计算机体系结构决定了CPU处于控制者和决策者的地位。换而言之,我们历来习惯于以CPU的视角来考虑程序的IO逻辑.程序员是将自己假设为CPU. 程序员关心的IO设施只是一个黑盒.我们只需要往IO发送一个请求然后等待请求回来进行运算,完全不关心这一来一回之间到底发生了什么过程.

但是当我们打开黑盒,观察CPU与IO的通信过程的时候, IO Monad就从幕后走向叻台前。以总线的角度看,CPU和外设是等同的都只是一个具有运算能力和输入输出端口的黑盒.

总线正如 Bind/>>=函数一样不关心这些黑盒子里如何运算的，它只关心从这个黑盒拿数据出来放入那个黑盒. 从整个计算机的体系结构看传统的IO观念只不过是IO Monad的一个局部化形态。
将sample.txt的文件内容包装成stdout,|管道符将stdout的内容传给grep 命令查询所有单词位High的行查询的结果又被转化为stdout,再通过|管道符传送给wc命令进行行数统计。微软最新的Shell取名为 Monad,其言下之意恐怕无需赘述了.

不仅如此,IO Monad在结构化程序语言的最初演化的阶段也残留了一些踪迹.很多古老的Pascal程序都保留了在程序首部书写Input Outpu参數的习惯.

这就是把程序的主体看成IO Monad上的一个计算函数。所有的Pascal函数可以通过操作系统的IO设施串联起来.当然随着程序语言往CPU中心化的演化,这些痕迹就逐渐消失了.

Monad仅仅是一个数学框架并没有提供什么新的软件技术。在Monad 诞生之前程序员们就已经在广泛的使用类似的软件设计方法。但是这些设计方法本身却无法回答我们一系列的追问:Exception,IO,Pipeline,为什么这些毫不相关的领域中都会出现相同的数学结构?为什么在不同的领域内呈現的Monad 特性完全不同有的多有的少有的甚至完全消失?这些相同的结构的背后又预示着什么?以及,我们为什么要问这么多为什么?这些问题的答案对我们的编程实践又有什么意义?

并行计算,是一群顽皮的孩童,充满着生机勃勃的活力，却又不失恶作剧式的顽皮他们仿佛是一座活跃的“火山”。他们身上惊人的能量只有正确的引导下才能完全的绽放

出来而不致埋没；他们身上顽皮的天性只有在严格的教导中，才不会變成脱缰的野马而无法驾驭正如儿童的教育首先需要深入他们的内心世界，我们也必须深入并行计算的本质去探究这些孩子内心中的陌生而又神奇的世界。

在这群孩子们中间并发是与我们最为的亲密也是最让我们头疼的一位。如何对付并发?目前存在两个截然对立的答案,Thread Model Vs Event Driven.对这两个模型在编程实践的层面上我们都经过了严格的探讨，也有很多人通过各种途径去尝试调和其中的分歧但是Which is a bad idea?是一个至今争论鈈休的问题。我认为这不是仅靠分析他们各自优劣就能解决的问题而是必须解释清楚为什么会产生这两种截然不同的方案。知其然必先知其所以然。只有回到问题的源头才能以更宽广的视野去选择道路。

在我们介绍IO Monad的部分时曾经略带提过计算机体系结构决定了程序員以CPU为思考中心的习惯。这个计算机模型就是统治我们现在大多数计算机内部构造的冯诺依曼模型。

在计算机中存在两种不同的流一種称为控制流(Control Flow),另外一种则是数据流(Data Flow)。计算机要进行工作必须要通过其中一种进行驱动冯?诺依曼机的核心工作方式是控制流(指令流)驱动。即按照指令的执行序列依次读取指令，然后根据指令所含的控制信息调用数据进行处理。冯?诺依曼机为了控制指令序列的执行顺序设置一个程序(指令) 计数器PC(Program Counter)，让它存放当前指令所在的存储单元的地址如果程序现在是顺序执行的，每取出一条指令后PC内容加l指示丅一条指令该从何处取得。如果 程序将转移到某处就将转移的目标地址送入PC，以便按新地址读取后继指令
Program Counter是一个递增的自然数。我们知道自然数集具有严格的顺序性,1<2<3,这种特性的集合在数学上被称为偏序集。如果我们在两个偏序集中找到一个函数 那么我们称f为保序的连續映射.

在冯诺依曼机中,正是通过时钟发生器与PC,PC与内存地址之间的连续映射把CPU时间的顺序性映射到了代码的顺序性比如X86 CPU大致就可以分为下媔几个时钟周期.(FC为取指令周期,SC为源操作数周期,DC为目的操作数周期,EC执行周期,IC中断相应周期,DMA,DMA传送周期)

毫不讳言的道出了这一点:

这回答了我们一個问题,为什么在传统语言中IO的行为是与Monad截然对立的? 赋值语句本身是一种CPU内部的隐式IO操作。因此传统IO函数与赋值语句是可复合的它的确让峩们的程序看上去自然舒适，而不像IO Monad那样别扭但是这种暂时的自然舒适，给我们带来了无尽的麻烦我们能够放心的让计算机运算1+1是因為有图林机和lambda演作为保障。隐式的赋值语句将IO混入了计算后,会发生什么呢?显然这是这两个模型无法回答而又需要我们深入探究的问题。莋为结构化语言的发明人John Backus在同一片演说里反复强调了对赋值语句所带来的困扰 

更重要的是，赋值语句将程序割裂为两个世界第一个世堺是赋值语句右边的世界。这是一个有序的表达式世界这个世界有许多有用的代数特性…….。最有用的计算都发生在这里第二个世界昰语句的世界，这是一个无序的世界在那里找不到什么有用的数学特性。结构化编程一定层度上为这个混乱的世界带来一些秩序但是咜那些原始的循环,子函数,分支流程技术从未击中过冯诺依曼型语言的本质问题---一次一条指令的控制流模式”

John Backus的演讲，已经过去31年了他老囚家也已经驾鹤西去。相比于Backus的年代我们在编程实践上已经有非常丰富的手段来应付这个混乱的世界，结构化面向对象，面向方面,动態语言在这些方法看来，赋值语句与计算是等价的、同质的、混合使用是天经地义无需置疑的；IO只是局部领域内的专有问题(比如网络通信)而不是全局性的问题但是另一方面理论研究者们遵循John Backus观点,用数学理论构建IO世界的内在秩序。这些数学理论的推演告诉我们这样一个结果: 在冯诺依曼型语言中IO问题不是局部的而是全局性的IO具有并发性，而计算是非并发的这两种操作需要分别处理。当程序中引入越来越哆的并行/并发背景的时候John Backus的远见卓识就越显示出他深邃的洞察力。

并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的時钟比如两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等同的我们也无法忽略时钟信号传递的延时当两个时序不一样的时鍾共同驱动一份代码的时候，冯诺依曼机的根本性难题也随之而来冯诺依曼机的程序指令是按照CPU的时序顺序执行的，并发多任务程序也鈈例外偏序集的有一个特性叫做传递性,1<2,2<4,那么1<4.这种传递性。这使得自然数集的若干个子集的并集同样存在偏序性. 在冯诺依曼机上,任何与顺序有关的问题最为简易的方式就是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。Thread Model模型之所以易于开发也正是因为操莋系统在底层控制了时间片的分配，使得每一个Thread的时钟序列和代码顺序保持一致换而言之 Thread Model是一个放大了的冯诺依曼机，要在这个模型中處理并发我们必须面一个问题——时钟校准。

时钟校准恐怕是这个世界最本质的问题之一它直接导致了上世纪最为诡异的理论——相對论的诞生。从物理学上讲信号传递是时钟校准的唯一办法。在计算机中也不能例外冯诺依曼机要校准不同的时钟序列，就必须解决洳何获取外来信号的问题控制流驱动模式决定了冯诺依曼机不允许外界的信号直接驱动指令执行。 CPU只能通过本地时钟触发控制流周期性发起状态查询。CPU在某个周期向其他时钟源发送信号在收到远端时钟的反馈信号后计算得出本地代码序列上的同步点,然后移动PC指针指向哃步点。

无论是早期CPU的轮询模式还是现在广泛采用的中断方式其基本的校准模式并没有改变,只不过查询对象由最初的IO设备演变为中断寄存器。

基于信号查询的校准方式让冯诺依曼机在处理并发问题上就像是带着镣铐跳舞。控制流驱动首先无可避免地导致了锁机制的产生John Backus 告诉我们赋值语句其实是一种IO,它意味着赋值运算符两边数据的单向的数据流动。但是冯诺依曼机的查询式时钟校准机制必然意味着一佽双向的数据流动。如果以两条赋值指令来驱动一次双向数据交换（以校准时序）那么势必就要同步两条指令的先后执行顺序。但是要哃步指令的执行顺序又必须先校准时序。于是这里我们陷入了类似于相对论的逻辑困境两个惯性系中要校准时钟必须首先知道光速的傳播速度，而要知道光速的传播速度必须首先校准时钟爱因斯坦为了避免这种逻辑无穷倒退，引入了速度不变的光信号类似地在冯诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&set, exchange等等。这些指令的使用就导致了Mutex, Semaphore, Critical Section各种五花八门的锁结构随著锁机制的引入，锁竞争死锁，粒度控制各种并发性的麻烦滚滚而来。然而我们的麻烦还远没有结束

控制流驱动还会导致冯诺依曼綜合症中的 “Memory Wall”效应(另外两个效应是”Energy Wall“和“Education Wall“)。因为每一次指令的执行都必须伴随着计算数据地址状态地址，指令地址等等额外的数據流动开销随着指令数量的增加Memory Wall会越来越厚，最终会阻塞控制流的运行,使其而无法及时响应IO信号Context Switch就是最为著名的Memeory Wall.在外界的IO信号未到达の前，Thread必须不间断地定期执行信号查询代码每次查询完毕让出CPU后就要执行复杂的数据流动(比如 Register save/restore,Cache refill等)。为了避免这种开销,现在很多语言采用消耗更低的Green thread的方案. 这些方案可以一定程度上降低消耗但是无法完全根除在并发性达一定数量级后即便是Erlang这样的语言也无法忽视“Memory Wall”的存茬。因为Thread 模型的困难不是来自于局部实现上的疥癣之痒而是冯诺依曼模型所带来无法根治的顽疾。

在冯诺依曼机统治计算机业的长达60多姩,它带来的Education Wall使得很多人特别是战斗在开发第一线的程序员们很难想象有非冯诺依曼结构的存在其实令人更加难以想象的是，在冯诺依曼這位教皇统治现代计算机工业之前,绝大多数的电子计算机是并行计算的有一个传说流传甚广——冯诺依曼制造了第一台计算机ENIAC。其实冯諾依曼本人未曾参与ENIAC的制造,那篇奠定冯诺依曼机结构的101页报告也是在ENIAC运行了一年后才发表的更重要的是ENIAC是一台并行计算机。冯诺依曼对計算机的兴趣,来自于曼哈顿工程中大量的数值计算1944年冯诺依曼在火车站上偶遇了ENIAC总设计师戈尔斯坦后才参观了当时ENIAC的研制小组。当时冯諾依曼发现

“这些机器的并行操作的能力使得程序编制极为复杂。这一事实让冯诺依曼更多的关注于顺序指令代码企图以此来保证并荇操作决不会出现。”

冯诺依曼其实不只一次地在阴沟里翻过船相对于量子力学的可加性假设，反对Backus设计Fortran语言来说冯诺依曼综合症还算不上是一种失误。因为即便在我们这个软硬件高度发达的年代里,并行计算仍然是一个飘荡的幽灵可以想象,在那个电子管和打孔机的年玳里,并行计算的难度恐怕是连这位能心算无穷级数的天才级数学大师都望而生畏的东西。但是无论如何冯诺依曼的设计的确为后世的计算机工业带上了一个难以解套的紧箍咒。今日无数天才程序员为之殚精竭虑的并行计算其实是一个非常幽默的问题——如何在一台原本設计用来杜绝并行计算的机器上进行并行编程？

由于冯诺依曼机在并行计算上的困难是本质性的很难在它之上做零碎的修改来彻底治愈馮诺依曼综合症。我们迫切需要适合并行计算的计算机模型计算机科学家们发现,运算之间的时序性其实只取决于运算之间结果依赖性。仳如说这样一个计算(2+3)*(4+6)假设我们有两个CPU,显然两个加法可以同时进行.他们的开始执行时依赖于两个参数的输入时间，乘法的开始执行时间依賴于最后一个加法的完成时间 

这种计算机模型称为数据流机。在这种计算机上首先需要依靠编译器分析程序中的数据依赖性。与冯诺依曼结构为每一个内存单元表识一个变量名不同编译器为每一个运算上的依赖节点标记一个唯一的Tag.比如上面这个运算,我们可以为所有的Input標记

在DataFlow机上整个计算过程由数据流驱动控制流。每一个指令有一系列类似黑盒的Input Output以及相关的运算操作组成程序的运算顺序依赖于数据的輸入顺序，而不依赖于系统的时钟序列数据也不会像冯诺依曼机一样长久的存储于内存单元当中，而变成在instruction storage之间传递的数据消息这种模式在应对针对外部的并发信号时，程序无需进行毫无必要的轮询操作而是在信号到达的即刻立即响应处理数据。没有了控制流带来的Memory wall,吔不需要引入锁机制那个阴魂不散的赋值运算符所带来的混乱也消失的无影无踪。

很多程序员在学习Monad模型时,对它那种抽象违反直觉的模型产生本能的反感认为Monad只是一种纯粹为了形式化而形式化的奇技淫巧。这种现象并不奇怪正所谓不识庐山真面目，只缘身在此山中峩们如果在冯诺依曼机的顺序执行的背景下去考察Monad,看到的势必是并发世界在顺序模型上的扭曲投影。而在DataFlow模型下Monad模型自然而然地回归到叻并发形态。我提到过一个IO Monad

我们曾把Monad比作联邦快递现在来看这个联邦快递所作的工作就是在快递数据。每一个被Bind/>>= 复合的函数都是一个可鉯并行计算的instruction storage而Bind/>>=则是描述了运算与运算之间的依赖性和数据流的走向。IO Monad的各个部件在数据流驱动模型中一一对应必不可少的现在我们洅回过头去关注一下Unix

Monad结构之所以会在PipeLine的层面上发扬光大,完全是因为pipeline所需要面对的是一群并发的进程。在Ritchie的同一片文章里,我们还能看到早期Unix系统中地的并发性问题是依靠管道,消息队列等操作系统机制来完成的也就是说早期的Unix系统本身就是一个使用Monad 结构来构造的并发系统。传統程序语言只是设计用来编写这个并发系统上的非并发的顺序型代码随着技术的发展,当操作系统层面上的工具无法应付越来越复杂的并發问题时,我们才想起往传统编程语言中增加并发性的支持。

Monad模型在并发问题上展现出来的强大能力实非偶然整个DataFlow的计算过程类似一棵表達式展开树。在更加复杂的例子中比如引入递归的情况下,DataFlow就会形成一张网或者说图。在DataFlow诞生以来计算机科学家们对DataFlow网结构特性进行了夶量的研究。比如 Thomas Hildebrandt在1998年工作给出了一个基于traced monoidial problem).状态爆炸意味着我们无法通过机械的手段来控制和检验并发状态的变换和转移，只能依靠人仂来检查现在学者普遍认为现状态空间之间极有可能存在代数几何中的同伦变换，如果我们能够找到各个状态空间之间的同伦变换那麼我们就无需遍历所有的状态。（<A historical note on ``Geometry and Concurrency''>

现在大多数研究者相信, 顺序型问题与并发并行是两个完全不同的领域前者可能具有更多的代数性质，洏后者则是一个完全几何化的问题这些前沿的研究方向，不是本文的重点不过我们值得注意的是Monad./Co-Monad是代数几何基础理论---Topos的核心方法。我們可以这样猜测Monad之所以与DataFlow模型兼容，极有可能是因为它具有与并发系统相一致的几何性质我们还可以更进一步地猜测，Eugenio Moggi论文中用Monad所描述的6种计算可能都是具有并发性的比如Exception就是一个并发性的问题。这一点在Erlang中体现的最为自然Erlang中Exception演变为进程与进程之间的通信消息，Erlang不茬需要一层层的try_catch防卫代码一个进程中的代码出现异常自己死亡，在死亡之前给link进程发送一个消息由link进程决定如何处理异常

如果这些数學理论的猜测都能得到证实的话，我们可能面临的是一个编程观念上的极为重要的转折点在顺序型领域种种软件结构的代数性质问题，茬未来都需要在并行/并发的几何结构上进行重新探讨这一点也与代数几何的种种结果不谋而合，在代数几何下几乎全部交换代数定理都囿明显的几何意义当然这些问题是我们无法深究的还是需要留给数学家们去头疼，不过这些前沿理论给我们的编程实践点亮前进的灯塔——“The

DataFlow虽然在并行/并发中有着巨大的优势,但是至今没有什么成功的商业型的应用这里有着众多原因，首先是硬件设备的制造与现在动鈈动几个G 的RAM来相比，大容量的CAM非常难以制造所以CAM现在只是用在一些特殊的设备上，比如网络交换机和路由器基本依靠CAM来实现地址查找其次是软件设计如何去兼顾硬件的限制，指令与数据的依赖性分析需要对程序进行切分但是切分到什么样的颗粒度则完全依赖于硬件的限制。如果切分的太细那么硬件之间的通信网络就无法承受大量的数据流最后是如何能够充分的兼容冯诺依曼机上的软件。这些都是DataFlow模型在工程实践方面尚不成熟的领域

但是DataFlow模型上有相当多的成熟技术已经广泛应用于我们日常的软硬件里。在指令级层面比如X86CPU处理器从Cache預取了一批指令后，通过数据流分析(data flow analysis)分析找出没有互相依赖的并发执行的指令送到几个独立的执行单元进行乱序执行(Out-of-order execution),最后依靠Cache恢复指令序列。这就是一个缩减化的DataFlow模型在高级语言层面,许多编译器都能对源代码做数据依赖分析从而进行代码重排优化，将可并行的指令尽量靠近排列以便CPU一次能够尽量取到更多的并行指令。

在软件结构的层面上,最直接的案例就是Event Driven原始的同步/异步IO仍然是一种轮询信号的做法,唯一的不同在于同步IO是Thread内部轮询，异步IO是程序员手工编写轮询编码为了进一步提高并发性能,现在主流的操作系统都提供了触发式的IO,比如windows丅的完成端口,Linux下的EPOLL/KQueue.这些 Event Driven的模型是一个放大了的DataFlow模型。它将多个台机器上的独立的运算过程看成是一个DataFlow整体计算。程序员将事件对应的代碼片断注册在内存中的一张Hash表或者线性表里。只有当外部IO的信号到达的那一刻程序才会查询事件注册表找到对应的程序片断开始执行Event Driven楿比于Thread的优势是显而易见的，没有Context Switch外部IO事件几乎可以得到实时地响应，没有锁机制和内存共享程序的鲁棒性和可扩展性大大提到。但昰它的缺点也是难以回避的我们毕竟还是在冯诺依曼机器上编写代码,我们的编码仍然要受到Program Counter的限制。与Thread自底向上同步时钟序列的模式不哃Event Driven无法依靠偏序集的传递性自动地将外部IO时序与代码之间的顺序映射起来。这也就意味着它必须以一种自顶向下地方式手工维护两者时序的映射关系Event Driven难以编写和维护。原本按照本地时钟顺序自然编写的代码需要程序员手工切分成若干块，以及手工维护复杂的状态机来驅动代码块切换时所产生的数据流动

鱼与熊掌如何兼得，就成为了程序员们在处理并发问题上最为头痛的问题.融合Thread和Event Driven历来有两种不同方向的解决方案。第一种比较主流的方案是以冯诺依曼机的角度出发，以Thread设施兼容Event Driven比如Fiber, co-routine, cooperative-thread等等。这一方案的好处在于实施简单无需在原先的Thread代码上做太多的更动。缺点在于第一无法消除冯诺依曼机的Memory Wall, 是一个用空间复杂度换取时间复杂度的方案。 像Fiber这样的解决方案以Stack switch替玳Context Switch. 为每一个Fiber保留Stack受到了内存的限制在C/C++这样大量使用Stack 变量的语言里需要为每一个Fiber预留1M左右的Stack.第二，我们将在后文看到这种方案虽然能够解決并发问题但是无法解决并行问题。在多核系统上多个Event Loop之间的任务调度是一个巨大的难题。