函数的副作用及其他

Trustno1大人的天书, 不是我这样的凡人能看懂的.
AlbertLee大人的翻译, 很好, 很强大.
但是, 看不懂啊.

电影<功夫>里面,一个高手临死的时候,对周星驰说, (好像是这个剧情, 戏仿<蜘蛛侠>雷同情节)
the more powerful, the more responsible
周星驰含泪叫道, 听不懂啊, 说中文好不好?
高手重复了一遍, 能力越大, 责任越大.

没有数学功底,不懂范畴理论(category theory), 怎能窥得天书 ?

-----------------------------------------------------------

我觉得 Monad 的设计思路, 也许可以用在普通的编程中.
大部分函数都是 Pure Function. 需要 IO 的部分, 或者放到 AOP Advice/Proxy里面, 或者分离到一些 Monad Proxy 类里面.
而且, 在普通编程语言里面, 实现用 Monad Proxy 分离 IO 部分, 应该比 Haskell 简单许多.
因为普通编程语言是会保证执行顺序的.我们可以放心地写

IOMonad ( Pure1, Pure2, Pure3) {   
   return new Funciton() {   
      someIO();   
      Pure1();   
      anotherIO();   
      Pure2();   
      againIO();   
      onceMoreIO();   
      Pure3();   
   }   
}   
  
f = Monad(Pure1, Pure2, Pure3);   
  
f();   

而不需要生成 chain.

只是,我不能完全明白, 是否是因为执行顺序这个原因, Haskell Monad 才需要 Chain.
还是因为别的原因.

问题就在这儿。在普通语言中，这样写看起来是没问题的，但一遇到并发就全是问题了。（想想看也容易理解：如果只需要这样的话，那还要 Monad 的原子延续做什么呢？）最关键的不是执行的顺序，而是执行的态度。有了延续这样的能够安全访问执行栈上任意一点的技术，才能安全地在 do 中的 IO 语句中进行并发。Haskell 不是为了没事找事儿采用这样“奇怪”的 IO 方式（也是一种程序组织方式）。

好像有点明白了. thanks to Lichray 组长.

形成这样一个函数调用链, 是为了强制产生运行栈 Frame 的分隔.
强制把每一个 IO 操作, 加在里面的 Pure Function, 都分隔到不同的 Stack Frame里面.

这是为了保证并发时候的线程安全性.
为什么,分隔到不同的Stack Frame就能够保证并发时的线程安全呢?

看来关键应该在 Lichray 提到的 原子延续 上面.
延续应该就是Continuation.
Continuation 可以看作是当前运行栈(或者执行树)环境 (Context )的一个快照. (是这样吗?)
(好像,支持Continuation的语言,一般都不是用线性运行栈,而是采用树形运行堆. 是这样吗?)

什么叫原子延续呢?
Monad Continuation ?
Atomic Continuation ?
Monad可以翻译为单子. 也有原子的意思?

看来慢慢接触到问题的关键部分了.
还望 Lichray等各位大人 不吝赐教. :D

-----------------------------------

搜索 Monad 原子延续 的时候, 发现一些不错的资料.

Archive for the '函数式编程' Category
http://www.nirvanastudio.org/category/functional-programming

将函数的能力定义得和单子的功能一样微小
什么是单子？
简介延续“Continuation”

-----------------------------------

(1) IO操作, Pure Function 分隔到不同的Stack Frame
(2) Atomic (Monad?) Continuation

这两点能够保证并发状态下的线程安全性.Right ?
满足了这两点, 程序的执行, 就可以产生无状态(Stateless)的效果 ?

这些相关资料哪里能够获得? 不会是在 Haskell 编译器/解释器原理里面吧? :D
搜索了一下 Monad IO Thread Safe, 没有找到相关的资料.

------------------------------------


函数的副作用及其他 (Version 2)
http://wfp.group.javaeye.com/group/topic/4639

经过Lichray指点之后的修改版本, 发布在了圈子里.
圈子里面的显示格式怎么和论坛不一致呢. 好像不那么Rich.

经过一番思索. 我又想到了一些东西.
>>, >>, >>= 等一系列Monad Bind动作,产生的不仅仅是一个Chain,还是一个State Machine.
一个一个环节之间的状态进行迁移.这个状态就是Continuation, 或者说Context.
产生这个Chained State Machine的目的也许不是为了线程安全. 而是为了保证在同一个函数范围内, Referential Transparent特性的有效性.
IO会引入状态, 变量或者表达式在函数内的全文替换,可能会不成立.因此要强制把任何产生状态的语句分隔到不同的函数体内.

bind的代码可能是这样. 被Bind的函数,都多了一个Continuation(或者Context)参数.用来传递当前的运行环境状态.
bind(action, nextAction) {
return new Function(continuation) {
nextContinuation = action(continuation)
return nextAction(nextContinuation)
}
}
我们可以看到, 新产生的Continuation(即当前状态,当前运行环境)总是向下传递的(有点像Lichray说的Reduce下降?).
新产生的Continuation (即新状态)不会影响到外层的函数, 只影响到相关内层的函数.
这似乎是为了保证状态变化不扩散

如果有 action1(c), action2(c), action3(c)三个函数需要bind在一起.
我们运行
f = bind (action1, bind(action2, action3))
f(continuation)

就可以顺序执行
C1 = action1(continuation)
C2 = action2(C1)
C3 = action3(C2)

太高深了，我等凡人只有暗自伤心的份。

我可是一句数学名词, Category理论都没有写.就是希望咱凡人自己写一点凡人看的东西.
没想到写的文字如同天书一般面目可憎, 又没有天书那样有理论深度. 失败啊.

只有自己完全理解了的东西, 才能够通俗易懂地讲出来.
这个贴的内容, 我自己也不是完全明白. 还是在不断求证过程中.

这些函数都具体运用在哪里？ 能说说吗 ？

比如类似c#中的linq实现
对程序运行中的一个list of objects进行filter和transform

数据

var users=[
{name:'user1',age:21,password:'abc'},
{name:'user2',age:33,password:'abc'},
{name:'user3',age:21,password:'abc'},
{name:'user4',age:34,password:'abc'}
];

js代码,为了方便，里面的function我使用ruby中closure定义方式
查询

var query=where( { |user| user.name=='user1' || user.age==21}).select( {|user| {age:user.age*10 , pass:user.password} } );
var result=query(users);
/*
result=[
{age:210,pass:'abc'},
{age:210,pass:'abc'}
]
*/

范畴论很难吗?又不是要你去证费马大定理.不懂怎么办?简单阿学呗!谁生出来就是懂数学的?你又不是贾宝玉.

对,你质疑的都对,但是首先要搞清楚你的问题是什么！你教小孩子加法,加法法则只告诉你运算的结果是什么.如果这个小孩好奇心强，问你为什么一加一等于二呢?你难道回答他,因为一加一等于二所以一加一等于二?
同样的道理,对于某个东西怎么用?和这个东西的为什么会如此工作?为什么要用这个东西?是三个完全不同的问题.Monad law，do-nation syntax,并不比Java framework,Ruby rails更难,完全可以在应用层面用通俗的话语解释给任何人听,打比方,甚至可以扯上周易八卦量子力学相对论,搞得很科普,很通俗.(比如这里就一位).

但是对于,为什么要用Monad?想用应用层次的知识去回答,那么我只能引用王元的那句话:"这是骑自行车上月球".
应用层面的对某一种技术的形象阐述,事实上是对理论问题进行了种种简化或者异化.其中最重要的一种简化就是抽去了数学框架， 取而代之的是一些文字化的描述以及与日常经验的类比. 与这种对概念和理论的简化相平行的是对理论研究过程的简化.程序员与计算机理论研究者之间,在处理问题的对象上可以说非常的接近,程序员离不开的OO,同样也是程序语言理论研究的一个热点话题.古代杀猪的可以兼职刺客，理发的可以兼职外科医生.不信没有了张屠夫就要吃连毛猪的浪漫情节,可以让很多程序员认为任何技术问题的只是概念和术语的简单组合,卖油翁似的经验堆积,哲学家式的纯粹思辩.

现代的计算机理论的确有思辨和经验归纳的成分,但同时又有大量抽象的数学模型和复杂而扎实的数学演算.前者给人留下的印象往往远远逊于后者， 因为前者大体上是概念之旅,既新奇浪漫又富有戏剧性,而后者相形之下不仅显得枯燥乏味,而且往往不是文字叙述所能够完全涵盖的.当然最为重要的因素在于,程序员和理论研究者所惯用的方法是不同的.程序员通常习惯的方式是采用归纳的方法.一个函数如何保证不出现大的偏差?程序员的答案是写单元测试,在一定的容错度夏穷尽可能想到的各种情况.如何设计出一个优秀的框架?程序员答案是重构,对现有程序中重复类似的代码加以归纳总结和整理.

空穴来风,未必无因，程序员对归纳法的热衷是源于他们的工作性质,他们所需要面对的问题是:在有限的时间,有限的资源,面对有限的需求,在容错范围内的可以做出什么样的产品?在这种有限条件下反复训练出来的决策机制，使得程序员对归纳法有着特殊的偏好.我个人也是一个程序员,我承认它对于程序员开发的大部分工作都是行之有效的,但是我并不满足于更不偏执于这样的方法.在我看来归纳法的作用有非常大的局限性.归纳法的结果过度地依赖我们过往的经历,体验和积累,这就使得我们的思想和视界无法超越我们的经验.比如说,在GC机制大规模引入工业语言之前,无数的程序员在与指针的搏斗中积累了大量的经验,但是主要的几个GC算法除了referece counting之外没有一个是如同Design Pattern一样的经验归纳结果.归纳法的结果是零碎的孤立的，结果与结果之间的联系是微弱的难以察觉的,这就是归纳法的最大缺点.当然如果你精于归纳法的使用,那么这足以使你成为一个优秀的程序员,但是它却无法给让你得到更加深刻的理解,看到更加普遍的关联，创造更加新颖的技术.

一个人要想去月球他就不能骑自行车,就不能被火箭的庞大与精密所吓倒.程序员通常都讨厌抽象的数学模型和复杂的数学证明，因为他们认为理论研究者使用数学的目的不过是为他们的论文寻求精确性和严格性，但是在现实的开发过程中有限的条件下极端的精确性和严格性是没有必要的.的确,数学的精确性和严格性的确是理论研究者的一个追求,但这并不是形式化的主要目的,甚至可以说精确性和严格性只是使用数学过程中的副产品.计算机科学从祖师爷图林算起才不到一百年的时间,但是相对于从阿基米德开始的数学来说，它只是一个襁褓中的婴儿.计算机科学中种种问题所体现出的数学性质在数学中都早已经过几十年甚至上百年的严格探讨,特别是20世纪以来代数学的高度抽象性使得各个数学分支得以互通有无甚至纳入统一的数学框架成为现实的可能.我们软件内讲抽象,方法A和方法B能够抽象出接口C.那么你能不能回答，A和B到底是具有了什么样的结构才允许他们能够抽象到C?为什么某个方法D却不能?对于已经抽象出的接口C是否会是某个遥远甚至无关问题E的某种特化?这些问题恐怕是很难在应用层面回答的,即便能够回答也需要付出高昂的代价。不过一旦你能把这些问题都形式化成某种代数结构,那么在数学中通过各种同态同构同胚变换,这些问题之间的关联,就显得自然而然的明晰统一。数学和形式化的确是复杂的,抽象的,枯燥的,无味,但是它不是无病呻吟,不是故弄玄虚,更不是意淫,它是我们依靠在数百代伟人肩膀上吸收人类数千年的智慧结晶必经之途。下面这段Monad简史恰好就是这样一个经典案例。





很多,很多,很多口口口(此处省略400字)程序员,理解Monad都是从副作用和IO Monad开始,因为副作用和IO是他们最为熟悉的东西,
这当然无可厚非.从一个熟悉的突破口去理解某种概念理论当然是一个可行的办法.但是接下来,buaawhl以及上次某位读过Walder 92的大侠一条道走到黑,固执地,坚持地,非常自信地口口口(此处省略500字)认为Haskell引入Monad就是为了解决按顺序调用的问题.然后死也想不通,不就是一个write和print吗?搞那么复杂有什么优势吗?能写的让普通人清楚地理解难道不行吗?正是囿于归纳法的限制,让这些同学的思维仿佛永远凝固自己熟悉的领域中左右徘徊，永远停留在应用层面的水平上循环往复.我上面所说过,归纳法的最大缺点就是过度地依赖我们过往的经历,体验和积累;归纳法不提供任何新的知识.一个优秀程序员可以从几百个 需要按顺序调用的程序中,归纳出这种场景的模式,总结出它的工作机制，抽象出它的通用接口,但是这些结果往往就被他的习惯性思维打上了固定的标签,他们只是为某种特定的应用量身定做,要让这些结果产生更加普遍的结果是非常困难的。在与那位读过Walder 92的大侠的有关Monad讨论中我们就可以看到，这种思维的惯性有多么的强烈.Walder 92在FP历史上是一篇非常漂亮的论文,详细讨论了有关Monad在程序语言上的诸多应用,直接为Haskell引入Monad奠定了坚实的理论基础,但是这位大侠却只盯住Monad解决按顺调用的部分可谓是买珠还椟.

如果我们要正本清源地把Monad进入程序设计语言的过程讲清楚,恐怕要先跳过从Walder 92这篇内容丰富的论文，从最基础的Lambda calculus讲起.我们经常会听到有人说,Lambda calculus与图灵机等价.但是真正能够理解这句话真实含义的其实并不多.当年Church在证明这个等价性的时候，引入了一个巨大的简化---Church把程序简化为从值到值的全函数(total functions from values to values,实际上可以直接看成集合论中定义的函数).这个模型在那个计算机还在草稿纸上的年代来说已经是非常完备了,但是以现在的观点来看这种简化恐怕是大大脱离编程实践的.

当然随着计算机的诞生和程序语言的发展，人们发现计算机能够执行的任务种类已经大大超过了total function的范畴，我们有了不同的求值方式 call-by-name(LISP的求职方式),call-by-value(C的求值方式),partial computation(C++ template的计算方式).我们有不同于顺序性计算的no-determinisim(非确定性计算，最为程序员熟悉的就是求随机数和并发的问题，这也是很多人不明白为何Haskell中的random是IO类型的),continuation(最近已经成为越来越重要的一种编程手段),exception(这已经是绝大多数程序语言的标配)还有不参与实际计算的IO等等.计算机科学家,为了对研究这些计算方式的解释实现(interperter)，优化等等问题，建立了各种各样的模型.比如说Partial computation的计算模型就是带有一个最小元的偏序集,no-determinisim的计算模型就是某个集合的powerset,exception是两个集合之间的coproduct.各种数学模型实际上就对应了不同的解释或者编译方式,在整个80年代一个语言要整合所有这些特性是极为困难的.

如果你去看Haskell 1.0的实现，你就会发现那是一个非常非常庞杂的系统.拿IO系统来说，当时Haskell并非采用的是Monad,而是备选了两种方案.一种称为Dialogue这种方案原理上就是SICP第三章中描述的stream，在实现上非常像Erlang的Message passing.它把Input,Ouput想象成两条无穷列表,往外output就是像输出表中发送一系列request,而input就是读取输入表中的response.另外一种则是基于continuations方式的，设计了get和put两个原语.
以continuation的方式将其组合起来比如说
当时Haskell的作者们发现Dialogue和contiuation实则上并不互相冲突,而且在形式上两者可以互相转换,因此在到底选取哪一个当作标准原语的问题上争执不下.一方面continuation方式比较适合程序员的思维而且与Haskell的原生语法保持一致,但是在效率上需要线性空间和平方时间的开销,另一方面流放式难以被程序员们接受并且需要引入一个独特的no-determinisim操作符来解决并发问题使得语法和解释器都要引入对特殊语法的支持，但是这个方案有着常数空间和线性时间的高效率.最后效率派占上风，以dialogue方式作为原语，用continuation包装上层的API.


这种计算方式各自为政的状况,随着1989年Eugenio Moggi划时代的论文<Notions of computation and monads>的发表，一切都得到了改观.Eugenio Moggi本质上是一个形式语义学家,他在研究的领域是指称语义，而指称语义对程序语言来说就是解释器实现的翻版(所以在我看来JS2.0使用操作语义来定义Spec就是一个特脑残的选择)。他在89年的这篇论文中引入了Category theory和Monad.Category theory的一大优点就是能够忽略具体的数学结构，无论是集合还,群,格都能在Category theory中得到完备的表达.Eugenio Moggi就使用这一特性,将partial computation,nodeterminsim,state-transform,exceptions,continuations,i/o的数学模型统一到了Kleisli Monad框架下，使得用基于Category theory的Monad成为了一个解释计算的大统一模型.两年之后，Philp Walder意识到了这篇文章的重要性，就以Haskell作为蓝本，实现了Eugenio Moggi所提出的6个Monadic 模型,这就是著名的Walder 92<Comprehending Monads>.从这一方面来说,某位大侠说认为Walder 92提高了大家的积极性,恐怕有些言过其实,Walder 92的确是一篇优秀的论文但是充其量不过是一个implementation report,其实任何人即便没有数学基础只要是草草的浏览过Walder 92的introduction,应该很明显的发现这一点.

以上是Monad进入程序语言的简单历史,如果我们在回过头来看，很多人对Monad提出的问题,

答案是No,计算随机数,exception不是IO问题,no-determinisim不是按序调用。

答案是No,在Haskell1.0中6中Monadic模型都存在隐藏副作用的解决方案.


答案是Yes,但是我们这里的所谓的简化并非是在Haskell 98下，而是对前80-90年代初FP的混沌年代而言.


答案是Yes,如果没有这些数学性质,那么我们就无法把各种不同类型的计算类型驯服在一个统一模型之下.当然现在计算机科学家正在探讨一些更加简洁，解释力更强的工具比如说arrow,但是这是另外一个话题.

答案是depends on,如果你只想理解Monad在某种特定计算上的工作机制(比如说IO)那么可以直观地讲解可以帮助你理解它。但是抽去数学框架的直观讲解无助于你理解对Monad在程序语义上的深刻含义，无助于你去理解Monad在通用计算大框架下的巨大作用.



答案 nearly impossible.当你没有涉足到Monad时,你能通过简单归纳想象出随机数的计算和IO之间有什么本质联系吗?

答案是no,因为他们不具备Monad那样的普遍的性质.你能想象Decorate模式可以实现exception和continuations吗?

答案是depends on,
如果你想深入学习程序设计理论那么这是一个绕不过的槛,
如果你想挑战自己的数学或者推理能力开拓自己的视野这是一个很好的实践范例，
如果你只是想学习编程那么没有这个必要,即便是在Haskell中也不必要,do-nation sytanx已经能够满足大多数的需要.

就我的观点来看Monad是一个非常low level的技术,其地位正如OO中的virtual table,而Haskell好比Bjarne当初设计的C with class.要知道一个语言特性从大学的论文到工业界的大规模应用承受30年的考验是很平常的,OO从simula67到C++前后将近30年,GC从John McCarthy的第一篇论文到Java是30年,Monad从几篇论文到一个第一个成熟的语言并且得到不小范围的应用才不到20年的时间.这相比于大学里一茬一茬自生自灭的语言来说已经是非常幸运了.但是我相信Monad的实用化及其后继技术会是今后一段时间的程序语言的研究方向,比如Linq在Monad和Monad comprehension上的尝试就是一个很好的范例.

Monad is not the end. it is not even the beginning of the end. but it is perhaps the end of the beginning.

一直无法理解Monad，搬个小板凳，学习中！