2008-03-28
函数的副作用及其他
函数的副作用及其他
Pure Function、Impure Function、副作用、Referential Transparent
纯函数（Pure Function）是这样一种函数——输入输出数据流全是显式（Explicit）的。
显式（Explicit）的意思是，函数与外界交换数据只有一个唯一渠道——参数和返回值；函数从函数外部接受的所有输入信息都通过参数传递到该函数内部；函数输出到函数外部的所有信息都通过返回值传递到该函数外部。
如果一个函数通过隐式（Implicit）方式，从外界获取数据，或者向外部输出数据，那么，该函数就不是Pure Function，叫作Impure Function。
隐式（Implicit）的意思是，函数通过参数和返回值以外的渠道，和外界进行数据交换。比如，读取全局变量，修改全局变量，都叫作以隐式的方式和外界进行数据交换；比如，利用I/O API（输入输出系统函数库）读取配置文件，或者输出到文件，打印到屏幕，都叫做隐式的方式和外界进行数据交换。
如果用社会现象来比喻，显式（Explicit）就是显规则，隐式（Implicit）就是潜规则。
Pure Function就是那种一根筋的理想主义者，绝不搞歪门邪道，没有什么灰色收入，数据入口和出口只有一条唯一途径——参数和返回值。只要卡住参数、返回值的出入口，就可以监控所有的数据流向。这对征税很有好处。比如一般的工薪阶层，只有工资一条收入渠道，扣税是银行直接代缴的。
Impure Function就不一样了，为了行事方便，大开后门，各种暗地手段无所不用其极，路子很宽很野。从函数签名（函数名，参数列表，返回值）定义上，你不知道Impure Function内部实现中有多少潜在的条数据交换的通路。监控Impure Function的数据流向是比较困难的。对Impure Function征税，也是比较困难的。只能期望灰色收入的人群自己申报。
下面举几个例子。
f(x) { return x + 1 }
f(x)函数就是Pure Function。
a = 0
q(x) {
b = a
}
q(x) 访问了函数外部的变量。q(x)是Impure Function。
p(x){
print “hello”
}
p(x)通过I/O API输出了一个字符串。p(x)是Impure Function。
c(x) {
data = readConfig() // 读取配置文件
}
c(x)通过I/O API读取了配置文件。c(x)是Impure Function。
Pure Function内部有隐式（Implicit）的数据流，这种情况叫做副作用（Side Effect）。我们可以把副作用想象为潜规则。上述的I/O，外部变量等，都可以归为副作用。因此，Pure Function的定义也可以写为，没有副作用的函数，叫做Pure Function。
I/O API可以看作是一种特殊的全局变量。文件、屏幕、数据库等输入输出结构可以看作是独立于运行环境之外的系统外全局变量，而不是应用程序自己定义的全局变量。
上述只讨论了一般的情况，还有一种特殊的情况，我们没有讨论。有些函数的参数是一种In/Out作用的参数，即函数可能改变参数里面的内容，把一些信息通过输入参数，夹带到外界。这种情况，严格来说，也是副作用。也是Impure Function。
比如下面的函数。
process(context) {
a = context.getInfo()
result = calculate( a )
context.setResult( result )
}
这种情况下，context参数同时作为输入和输出渠道。严格意义上，这也叫作副作用。参数只作为输入，返回值只作为输出，这才符合严格的Pure Function定义。
一般情况下，Pure Function的参数应该是只读的。函数不应该改变参数内部的任何状态。
除此之外，还有一种特殊情况。比如，函数调用了获取系统时间的API。这种API是有状态的API，也可以看作是特殊的I/O API。这也是Impure Function。
Pure Function有这么多限制，那么Pure Function到底有什么好处呢？难道就是监控数据流方便？还是征税方便？
我能想到的，Pure Function的好处主要有几点：
（1）无状态，Stateless。线程安全。不需要线程同步。
（2）Pure Function相互调用组装起来的函数，还是Pure Function。
（3）应用程序或者运行环境（Runtime）可以对Pure Function的运算结果进行缓存，运算加快速度。
上述的好处（3）需要说明一下。Pure Function的输入、输出都是固定的。输入是同样的参数，输出结果一定是同样的结果。而Impure Function的副作用是无法用（参数、结果）缓存的。参见前面的例子。
没有副作用，也可以叫做Referential Transparent（引用透明）。
Referential Transparent的意思好像这样的。在一个范围内，一个变量或者表达式出现在多个地方，那么这些地方的值都是一样的，可以进行值替换。
比如，
f(x) {
a = f(x)
b = f(x)
}
编译器或者运行环境发现程序里面出现了两次f(x)，就可以放心地用第一个f(x)的结果，代替另一个f(x)。（这是我的个人理解，不能确保就是如此。）
---------------------------------------
副作用、状态、I/O、AOP、Monad
Pure Function是无状态的。很好，很干净。清净琉璃体，玲珑剔透心。
Haskell就是这样一种理想主义的Pure Functional Language（纯函数式编程语言）。
但是，世界是复杂的，有很多潜规则，华丽的外表下有很多暗流在涌动。无状态的Pure Function不足以表达充满了状态和副作用的现实需求。
我们来看一看，哪些副作用是可以避免的，那些副作用是无法避免的。
首先，全局变量的副作用是很容易避免的。全局变量的读写，可以用参数和返回值代替。我们可以比较容易地消除代码中的全局变量。同样，参数里面放置返回值的情况，也可以很容易用返回值避免。
比较难以处理的情况是I/O的情况。一个应用系统总是需要输入输出的。如果一个应用系统只是在启动的时候，需要输入，在结束的时候，进行输出，那么还好处理一点。我们可以把I/O集中在系统的最外层处理，系统内部不需要处理任何I/O。但这只是一种良好的愿望。常见的应用系统都是交互式的，而且系统经常需要吐出一堆堆的log，经常需要重新接受用户的配置选项更改。
I/O又是一种非常特殊的全局变量。I/O设备（或者结构）独立于应用系统之外（比如，文件，网络，数据库系统）。应用系统很难在程序设计的层次上，用参数、返回值代替I/O API。
输出部分还是比较容易收集。我们可以把所有的输出都收集到一个巨大的List结构中，作为返回值，一层层返回到最外层。最外层统一把List中的数据全部输出到对应设备。
输入部分，就难办了。应用程序可能随时需要访问一下配置文件、数据库、系统时钟等设备。我们无法预料到程序内部什么时候需要读取什么样的设备和信息，我们无法提前准备这些输入信息作为参数。
怎么办呢？我们联想一下。AOP（Aspect Oriented Programming）最著名的例子就是Log（系统日志）。
在AOP中，函数出入口的Log等脏活累活都可以统一集中地交给几个Advice类处理。Advice类就是那种Interceptor、Filter、Proxy之类的东西。通常会有intercept、around等方法。
主体程序本身是高贵的，不需要处理Log。编译过程或者运行过程中，AOP系统负责把Advice类里面的Log处理代码夹杂到主体程序中，工作过程非常类似于计算机病毒感染的过程。
于是，进到AOP系统这个大染缸之前，主体程序还是冰清玉洁的；主体程序进入AOP系统，并从AOP系统出来之后，主题程序就已经被感染了，具有了Log等功能。
正如马克.吐温在<竞选州长>中描述的。
“你忠实的朋友，过去是正派人，现在却成了伪证犯、小偷、拐尸犯、酒疯子、贿赂犯和讹诈犯的马克•吐温。”
同样的思路，能否应用到Pure Function中呢？
比如，我们可以保持Pure Function的纯洁性，把IO这样的操作，移动到Advice（or Proxy）类里面。然后通过某种类似于AOP的机制，把两者绑定起来。
正如表面看上去，凯撒的归凯撒，上帝的归上帝，世俗王权和宗教神权互不干涉。但实际上，对于权力、金钱的渴望，通常会导致王权神权两种权力的冲突和勾结。
Haskell是Pure Functional Language。Haskell处理IO的方法之一叫作Monad。
Monad是一种臭名昭著的难以理解的东西。
Monad不是我所能理解的东西。我只能对Monad进行猜想。
我猜想，Monad是一种类似于Advice、Proxy的类型定义。
Monad是一种类型定义。可能和C++ Template有些相似。
Monad类型就是专门做IO杂事的特殊类型。除了Monad类型，其他的函数或者类型都是Pure。
如果一个Pure Function，需要输入输出，就必须被Monad包装。
我们可以想象几个IO Monad Proxy的例子。
InputProxy ( function ) { // function 就是被截获的Pure Function
a = readSomething // 读取输入设备
f( a )
}
OutputProxy( function) { // function 就是被截获的Pure Function
b = function()
print b
}
在Monad Proxy中，（我猜想）应该只能存在一条输入输出语句。如上例所示。
如果要同时输入输出。那么就必须把上述的Monad Proxy串起来。
比如，先输入，再输出。应该这么写。OutputProxy( InputProxy ( function ) )
如果用嵌套函数的写法，应该写成这样。
OutputProxy() {
b = InputProxy() {
a = readSomething()
function( a ) {
// process a
}
}
print b
}
为什么一定要保证一个函数中的输入输出语句只有一条？为什么一定要写成这样？
我猜想，这可能和Haskell的Referential Transparent的特性有关。Haskell支持Referential Transparent，支持同名变量或者同字符串表达式的任意替换。在一定程度上，Haskell程序的代码是顺序无关的。如果是Pure Function，编译器处理起来比较容易。
如果引入了和外界交换状态的输入输出语句，就必须强制代码的顺序性了。必须保证代码顺序执行。在Haskell中，要强制顺序，只能通过函数的一层层调用来保证。
正如前面所说的。Haskell中，
a = f(x)
b = g(x)
这种同一层的两次f(x)调用，不一定能够保证这两条语句的执行顺序。
要保证f在g之前执行，我们只能写成 g ( f (.. ) ) 的形式，才能保证 f 在 g 之前执行。
Haskell的do语句可能就是把看起来是平级顺序语句转化成层层嵌套调用的语法糖。
比如，
do
readSomething
print something
实际上会被翻译成函数调用的嵌套形式。
g() {
readSomething
f() {
print something
}
}
Monad类型定义其实就是为了生成这样的函数调用嵌套结构。这个生成过程好像也叫作bind（绑定）。
bind就有点类似于AOP系统的那种夹杂绑定过程，把干净的东西和副作用揉合到一起。
注，上述只是猜想。
那些城里人动不动就搞些Category之类的名词吓唬我们乡下人。不讲人话，总是讲神话。
我希望，咱老百姓能够讲述自己的故事。不整那些神鬼莫测的名词，也照样能把话说清楚。
显然，这是一种奢望。至少我还说不清楚。话语权还是握在城里人的手里。
参见
农民对城里人的抱怨
http://www.javaeye.com/topic/165962
Pure Function、Impure Function、副作用、Referential Transparent
纯函数（Pure Function）是这样一种函数——输入输出数据流全是显式（Explicit）的。
显式（Explicit）的意思是，函数与外界交换数据只有一个唯一渠道——参数和返回值；函数从函数外部接受的所有输入信息都通过参数传递到该函数内部；函数输出到函数外部的所有信息都通过返回值传递到该函数外部。
如果一个函数通过隐式（Implicit）方式，从外界获取数据，或者向外部输出数据，那么，该函数就不是Pure Function，叫作Impure Function。
隐式（Implicit）的意思是，函数通过参数和返回值以外的渠道，和外界进行数据交换。比如，读取全局变量，修改全局变量，都叫作以隐式的方式和外界进行数据交换；比如，利用I/O API（输入输出系统函数库）读取配置文件，或者输出到文件，打印到屏幕，都叫做隐式的方式和外界进行数据交换。
如果用社会现象来比喻，显式（Explicit）就是显规则，隐式（Implicit）就是潜规则。
Pure Function就是那种一根筋的理想主义者，绝不搞歪门邪道，没有什么灰色收入，数据入口和出口只有一条唯一途径——参数和返回值。只要卡住参数、返回值的出入口，就可以监控所有的数据流向。这对征税很有好处。比如一般的工薪阶层，只有工资一条收入渠道，扣税是银行直接代缴的。
Impure Function就不一样了，为了行事方便，大开后门，各种暗地手段无所不用其极，路子很宽很野。从函数签名（函数名，参数列表，返回值）定义上，你不知道Impure Function内部实现中有多少潜在的条数据交换的通路。监控Impure Function的数据流向是比较困难的。对Impure Function征税，也是比较困难的。只能期望灰色收入的人群自己申报。
下面举几个例子。
f(x) { return x + 1 }
f(x)函数就是Pure Function。
a = 0
q(x) {
b = a
}
q(x) 访问了函数外部的变量。q(x)是Impure Function。
p(x){
print “hello”
}
p(x)通过I/O API输出了一个字符串。p(x)是Impure Function。
c(x) {
data = readConfig() // 读取配置文件
}
c(x)通过I/O API读取了配置文件。c(x)是Impure Function。
Pure Function内部有隐式（Implicit）的数据流，这种情况叫做副作用（Side Effect）。我们可以把副作用想象为潜规则。上述的I/O，外部变量等，都可以归为副作用。因此，Pure Function的定义也可以写为，没有副作用的函数，叫做Pure Function。
I/O API可以看作是一种特殊的全局变量。文件、屏幕、数据库等输入输出结构可以看作是独立于运行环境之外的系统外全局变量，而不是应用程序自己定义的全局变量。
上述只讨论了一般的情况，还有一种特殊的情况，我们没有讨论。有些函数的参数是一种In/Out作用的参数，即函数可能改变参数里面的内容，把一些信息通过输入参数，夹带到外界。这种情况，严格来说，也是副作用。也是Impure Function。
比如下面的函数。
process(context) {
a = context.getInfo()
result = calculate( a )
context.setResult( result )
}
这种情况下，context参数同时作为输入和输出渠道。严格意义上，这也叫作副作用。参数只作为输入，返回值只作为输出，这才符合严格的Pure Function定义。
一般情况下，Pure Function的参数应该是只读的。函数不应该改变参数内部的任何状态。
除此之外，还有一种特殊情况。比如，函数调用了获取系统时间的API。这种API是有状态的API，也可以看作是特殊的I/O API。这也是Impure Function。
Pure Function有这么多限制，那么Pure Function到底有什么好处呢？难道就是监控数据流方便？还是征税方便？
我能想到的，Pure Function的好处主要有几点：
（1）无状态，Stateless。线程安全。不需要线程同步。
（2）Pure Function相互调用组装起来的函数，还是Pure Function。
（3）应用程序或者运行环境（Runtime）可以对Pure Function的运算结果进行缓存，运算加快速度。
上述的好处（3）需要说明一下。Pure Function的输入、输出都是固定的。输入是同样的参数，输出结果一定是同样的结果。而Impure Function的副作用是无法用（参数、结果）缓存的。参见前面的例子。
没有副作用，也可以叫做Referential Transparent（引用透明）。
Referential Transparent的意思好像这样的。在一个范围内，一个变量或者表达式出现在多个地方，那么这些地方的值都是一样的，可以进行值替换。
比如，
f(x) {
a = f(x)
b = f(x)
}
编译器或者运行环境发现程序里面出现了两次f(x)，就可以放心地用第一个f(x)的结果，代替另一个f(x)。（这是我的个人理解，不能确保就是如此。）
---------------------------------------
副作用、状态、I/O、AOP、Monad
Pure Function是无状态的。很好，很干净。清净琉璃体，玲珑剔透心。
Haskell就是这样一种理想主义的Pure Functional Language（纯函数式编程语言）。
但是，世界是复杂的，有很多潜规则，华丽的外表下有很多暗流在涌动。无状态的Pure Function不足以表达充满了状态和副作用的现实需求。
我们来看一看，哪些副作用是可以避免的，那些副作用是无法避免的。
首先，全局变量的副作用是很容易避免的。全局变量的读写，可以用参数和返回值代替。我们可以比较容易地消除代码中的全局变量。同样，参数里面放置返回值的情况，也可以很容易用返回值避免。
比较难以处理的情况是I/O的情况。一个应用系统总是需要输入输出的。如果一个应用系统只是在启动的时候，需要输入，在结束的时候，进行输出，那么还好处理一点。我们可以把I/O集中在系统的最外层处理，系统内部不需要处理任何I/O。但这只是一种良好的愿望。常见的应用系统都是交互式的，而且系统经常需要吐出一堆堆的log，经常需要重新接受用户的配置选项更改。
I/O又是一种非常特殊的全局变量。I/O设备（或者结构）独立于应用系统之外（比如，文件，网络，数据库系统）。应用系统很难在程序设计的层次上，用参数、返回值代替I/O API。
输出部分还是比较容易收集。我们可以把所有的输出都收集到一个巨大的List结构中，作为返回值，一层层返回到最外层。最外层统一把List中的数据全部输出到对应设备。
输入部分，就难办了。应用程序可能随时需要访问一下配置文件、数据库、系统时钟等设备。我们无法预料到程序内部什么时候需要读取什么样的设备和信息，我们无法提前准备这些输入信息作为参数。
怎么办呢？我们联想一下。AOP（Aspect Oriented Programming）最著名的例子就是Log（系统日志）。
在AOP中，函数出入口的Log等脏活累活都可以统一集中地交给几个Advice类处理。Advice类就是那种Interceptor、Filter、Proxy之类的东西。通常会有intercept、around等方法。
主体程序本身是高贵的，不需要处理Log。编译过程或者运行过程中，AOP系统负责把Advice类里面的Log处理代码夹杂到主体程序中，工作过程非常类似于计算机病毒感染的过程。
于是，进到AOP系统这个大染缸之前，主体程序还是冰清玉洁的；主体程序进入AOP系统，并从AOP系统出来之后，主题程序就已经被感染了，具有了Log等功能。
正如马克.吐温在<竞选州长>中描述的。
“你忠实的朋友，过去是正派人，现在却成了伪证犯、小偷、拐尸犯、酒疯子、贿赂犯和讹诈犯的马克•吐温。”
同样的思路，能否应用到Pure Function中呢？
比如，我们可以保持Pure Function的纯洁性，把IO这样的操作，移动到Advice（or Proxy）类里面。然后通过某种类似于AOP的机制，把两者绑定起来。
正如表面看上去，凯撒的归凯撒，上帝的归上帝，世俗王权和宗教神权互不干涉。但实际上，对于权力、金钱的渴望，通常会导致王权神权两种权力的冲突和勾结。
Haskell是Pure Functional Language。Haskell处理IO的方法之一叫作Monad。
Monad是一种臭名昭著的难以理解的东西。
Monad不是我所能理解的东西。我只能对Monad进行猜想。
我猜想，Monad是一种类似于Advice、Proxy的类型定义。
Monad是一种类型定义。可能和C++ Template有些相似。
Monad类型就是专门做IO杂事的特殊类型。除了Monad类型，其他的函数或者类型都是Pure。
如果一个Pure Function，需要输入输出，就必须被Monad包装。
我们可以想象几个IO Monad Proxy的例子。
InputProxy ( function ) { // function 就是被截获的Pure Function
a = readSomething // 读取输入设备
f( a )
}
OutputProxy( function) { // function 就是被截获的Pure Function
b = function()
print b
}
在Monad Proxy中，（我猜想）应该只能存在一条输入输出语句。如上例所示。
如果要同时输入输出。那么就必须把上述的Monad Proxy串起来。
比如，先输入，再输出。应该这么写。OutputProxy( InputProxy ( function ) )
如果用嵌套函数的写法，应该写成这样。
OutputProxy() {
b = InputProxy() {
a = readSomething()
function( a ) {
// process a
}
}
print b
}
为什么一定要保证一个函数中的输入输出语句只有一条？为什么一定要写成这样？
我猜想，这可能和Haskell的Referential Transparent的特性有关。Haskell支持Referential Transparent，支持同名变量或者同字符串表达式的任意替换。在一定程度上，Haskell程序的代码是顺序无关的。如果是Pure Function，编译器处理起来比较容易。
如果引入了和外界交换状态的输入输出语句，就必须强制代码的顺序性了。必须保证代码顺序执行。在Haskell中，要强制顺序，只能通过函数的一层层调用来保证。
正如前面所说的。Haskell中，
a = f(x)
b = g(x)
这种同一层的两次f(x)调用，不一定能够保证这两条语句的执行顺序。
要保证f在g之前执行，我们只能写成 g ( f (.. ) ) 的形式，才能保证 f 在 g 之前执行。
Haskell的do语句可能就是把看起来是平级顺序语句转化成层层嵌套调用的语法糖。
比如，
do
readSomething
print something
实际上会被翻译成函数调用的嵌套形式。
g() {
readSomething
f() {
print something
}
}
Monad类型定义其实就是为了生成这样的函数调用嵌套结构。这个生成过程好像也叫作bind（绑定）。
bind就有点类似于AOP系统的那种夹杂绑定过程，把干净的东西和副作用揉合到一起。
注，上述只是猜想。
那些城里人动不动就搞些Category之类的名词吓唬我们乡下人。不讲人话，总是讲神话。
我希望，咱老百姓能够讲述自己的故事。不整那些神鬼莫测的名词，也照样能把话说清楚。
显然，这是一种奢望。至少我还说不清楚。话语权还是握在城里人的手里。
参见
农民对城里人的抱怨
http://www.javaeye.com/topic/165962
评论
lichray
2008-04-03
要是按这个思路来理解“要不要加 do”，那你要理解的东西就可能太多了。确实需要补充一些 Lambda 演算和状态方面的知识。
buaawhl
2008-04-03
又看了一遍这个帖子
回albertLee:关于Category Theory 和Monad
http://www.javaeye.com/post/428151
虽然还是没有看懂帖子内容.
但是,这次我仔细看了后面的回帖.才发现,早就有人已经提出了我提出的那些问题.汗颜.
而且,我连 Walder 1992 论文都没有看过. 也不知道有这样一篇论文.
ajoo 也早就提到了 Monad 和 chain of command 的关系.
这些理论上的差距, 不是一点半点.
拿IO系统来说，当时Haskell并非采用的是Monad,而是备选了两种方案.一种称为Dialogue这种方案原理上就是SICP第三章中描述的stream，在实现上非常像Erlang的Message passing.它把Input,Ouput想象成两条无穷列表,往外output就是像输出表中发送一系列request,而input就是读取输入表中的response.另外一种则是基于continuations方式的，设计了get和put两个原语.
以continuation的方式将其组合起来比如说
引用
echo:Result->Result
echo c=get(\a->if (a==eof)
then c
else put a (echo c))
当时Haskell的作者们发现Dialogue和contiuation实则上并不互相冲突,而且在形式上两者可以互相转换,因此在到底选取哪一个当作标准原语的问题上争执不下.一方面continuation方式比较适合程序员的思维而且与Haskell的原生语法保持一致,但是在效率上需要线性空间和平方时间的开销,另一方面流放式难以被程序员们接受并且需要引入一个独特的no-determinisim操作符来解决并发问题使得语法和解释器都要引入对特殊语法的支持，但是这个方案有着常数空间和线性时间的高效率.最后效率派占上风，以dialogue方式作为原语，用continuation包装上层的API.
原来, Dialogue 和 Continuation 是这么回事.
我看到一些资料里面提到 Haskell 的 Dialogue 和 Continuation. 但是没有看懂是怎么回事.
-----------------------------------------------
范畴论很难吗?又不是要你去证费马大定理.不懂怎么办?简单阿学呗!谁生出来就是懂数学的?你又不是贾宝玉.
难, 不难的话,咱也不会回到经验归纳的老路上.
T1自己也说了.
记得上次看到lich_ray讨论Monad实现state的时候也用了别扭两个字来概括，认为Monad在这方面不如continuation来的直观。.因此学习haskell,除非你是像ajoo那样脑瓜很不错的人，否则你就只能下苦功夫靠不断写程序去适应这种思维。
我就是听城里人讲了一些新鲜事, 引起了一点好奇心 (我们村里人娱乐活动不多,总看着城里人在搞些啥), 想弄明白城里人说的是什么.
事情要一步步来, 我是连经验总结/Walder 92的阶段都没有经过.就跳过去看城里人提到的那些资料.这超越了现阶段的生产力.
我还远远不到 Walder 92 大侠的水平, 这个经验总结的层次上, 我还要努力.
至于数学,范畴,这个我的起点就更低了.只能慢慢来,说不定,某天就开窍了.
---------------------------
Random, Error和 IO 的相似点.
我是这么认为的.
Random的生成,也是要根据系统的一些全局随机信息(比如系统时间).这有些象 input.
Error属于异常情况,可能要对系统发出一些警告,比如 throw, print.这有些象 output.
另外, do notation, 我还是没有彻底明白.
好像 input 前面不需要加 do, output 前面一定要加 do.
是这样吗?
回albertLee:关于Category Theory 和Monad
http://www.javaeye.com/post/428151
虽然还是没有看懂帖子内容.
但是,这次我仔细看了后面的回帖.才发现,早就有人已经提出了我提出的那些问题.汗颜.
而且,我连 Walder 1992 论文都没有看过. 也不知道有这样一篇论文.
ajoo 也早就提到了 Monad 和 chain of command 的关系.
这些理论上的差距, 不是一点半点.
Trustno1 写道
拿IO系统来说，当时Haskell并非采用的是Monad,而是备选了两种方案.一种称为Dialogue这种方案原理上就是SICP第三章中描述的stream，在实现上非常像Erlang的Message passing.它把Input,Ouput想象成两条无穷列表,往外output就是像输出表中发送一系列request,而input就是读取输入表中的response.另外一种则是基于continuations方式的，设计了get和put两个原语.
以continuation的方式将其组合起来比如说
引用
echo:Result->Result
echo c=get(\a->if (a==eof)
then c
else put a (echo c))
当时Haskell的作者们发现Dialogue和contiuation实则上并不互相冲突,而且在形式上两者可以互相转换,因此在到底选取哪一个当作标准原语的问题上争执不下.一方面continuation方式比较适合程序员的思维而且与Haskell的原生语法保持一致,但是在效率上需要线性空间和平方时间的开销,另一方面流放式难以被程序员们接受并且需要引入一个独特的no-determinisim操作符来解决并发问题使得语法和解释器都要引入对特殊语法的支持，但是这个方案有着常数空间和线性时间的高效率.最后效率派占上风，以dialogue方式作为原语，用continuation包装上层的API.
原来, Dialogue 和 Continuation 是这么回事.
我看到一些资料里面提到 Haskell 的 Dialogue 和 Continuation. 但是没有看懂是怎么回事.
-----------------------------------------------
Truston1 写道
范畴论很难吗?又不是要你去证费马大定理.不懂怎么办?简单阿学呗!谁生出来就是懂数学的?你又不是贾宝玉.
难, 不难的话,咱也不会回到经验归纳的老路上.
T1自己也说了.
Trustno1 写道
记得上次看到lich_ray讨论Monad实现state的时候也用了别扭两个字来概括，认为Monad在这方面不如continuation来的直观。.因此学习haskell,除非你是像ajoo那样脑瓜很不错的人，否则你就只能下苦功夫靠不断写程序去适应这种思维。
我就是听城里人讲了一些新鲜事, 引起了一点好奇心 (我们村里人娱乐活动不多,总看着城里人在搞些啥), 想弄明白城里人说的是什么.
事情要一步步来, 我是连经验总结/Walder 92的阶段都没有经过.就跳过去看城里人提到的那些资料.这超越了现阶段的生产力.
我还远远不到 Walder 92 大侠的水平, 这个经验总结的层次上, 我还要努力.
至于数学,范畴,这个我的起点就更低了.只能慢慢来,说不定,某天就开窍了.
---------------------------
Random, Error和 IO 的相似点.
我是这么认为的.
Random的生成,也是要根据系统的一些全局随机信息(比如系统时间).这有些象 input.
Error属于异常情况,可能要对系统发出一些警告,比如 throw, print.这有些象 output.
另外, do notation, 我还是没有彻底明白.
好像 input 前面不需要加 do, output 前面一定要加 do.
是这样吗?
yimlin
2008-04-03
一直无法理解Monad，搬个小板凳，学习中！
Trustno1
2008-04-03
引用
电影<功夫>里面,一个高手临死的时候,对周星驰说, (好像是这个剧情, 戏仿<蜘蛛侠>雷同情节)
the more powerful, the more responsible
周星驰含泪叫道, 听不懂啊, 说中文好不好?
高手重复了一遍, 能力越大, 责任越大.
没有数学功底,不懂范畴理论(category theory), 怎能窥得天书 ?
the more powerful, the more responsible
周星驰含泪叫道, 听不懂啊, 说中文好不好?
高手重复了一遍, 能力越大, 责任越大.
没有数学功底,不懂范畴理论(category theory), 怎能窥得天书 ?
范畴论很难吗?又不是要你去证费马大定理.不懂怎么办?简单阿学呗!谁生出来就是懂数学的?你又不是贾宝玉.
引用
那些城里人动不动就搞些Category之类的名词吓唬我们乡下人。不讲人话，总是讲神话。
我希望，咱老百姓能够讲述自己的故事。不整那些神鬼莫测的名词，也照样能把话说清楚。
对,你质疑的都对,但是首先要搞清楚你的问题是什么！你教小孩子加法,加法法则只告诉你运算的结果是什么.如果这个小孩好奇心强，问你为什么一加一等于二呢?你难道回答他,因为一加一等于二所以一加一等于二?
同样的道理,对于某个东西怎么用?和这个东西的为什么会如此工作?为什么要用这个东西?是三个完全不同的问题.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简史恰好就是这样一个经典案例。
引用
只是,我不能完全明白, 是否是因为执行顺序这个原因, Haskell Monad 才需要 Chain.
还是因为别的原因.
还是因为别的原因.
很多,很多,很多口口口(此处省略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的方式将其组合起来比如说
引用
echo:Result->Result
echo c=get(\a->if (a==eof)
then c
else put a (echo c))
当时Haskell的作者们发现Dialogue和contiuation实则上并不互相冲突,而且在形式上两者可以互相转换,因此在到底选取哪一个当作标准原语的问题上争执不下.一方面continuation方式比较适合程序员的思维而且与Haskell的原生语法保持一致,但是在效率上需要线性空间和平方时间的开销,另一方面流放式难以被程序员们接受并且需要引入一个独特的no-determinisim操作符来解决并发问题使得语法和解释器都要引入对特殊语法的支持，但是这个方案有着常数空间和线性时间的高效率.最后效率派占上风，以dialogue方式作为原语，用continuation包装上层的API.
echo c=get(\a->if (a==eof)
then c
else put a (echo c))
这种计算方式各自为政的状况,随着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提出的问题,
引用
Monad是因为解决IO问题或者按序调用的问题而引入的吗?
答案是No,计算随机数,exception不是IO问题,no-determinisim不是按序调用。
引用
Monad是因为副作用引入的吗?
答案是No,在Haskell1.0中6中Monadic模型都存在隐藏副作用的解决方案.
引用
Monad能简化某些编程问题吗?
答案是Yes,但是我们这里的所谓的简化并非是在Haskell 98下，而是对前80-90年代初FP的混沌年代而言.
引用
Monad的数学性质缺一不可吗?
答案是Yes,如果没有这些数学性质,那么我们就无法把各种不同类型的计算类型驯服在一个统一模型之下.当然现在计算机科学家正在探讨一些更加简洁，解释力更强的工具比如说arrow,但是这是另外一个话题.
引用
Monad可以被直观的讲解吗?
答案是depends on,如果你只想理解Monad在某种特定计算上的工作机制(比如说IO)那么可以直观地讲解可以帮助你理解它。但是抽去数学框架的直观讲解无助于你理解对Monad在程序语义上的深刻含义，无助于你去理解Monad在通用计算大框架下的巨大作用.
引用
Monad可以从编程经验中归纳出来吗?
答案 nearly impossible.当你没有涉足到Monad时,你能通过简单归纳想象出随机数的计算和IO之间有什么本质联系吗?
引用
我们平时遇到的类似编程模式也可以理解为Monad吗?
答案是no,因为他们不具备Monad那样的普遍的性质.你能想象Decorate模式可以实现exception和continuations吗?
引用
我们需要理解Monad吗?
答案是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.
gordon@java
2008-04-01
比如类似c#中的linq实现
对程序运行中的一个list of objects进行filter和transform
数据
js代码,为了方便，里面的function我使用ruby中closure定义方式
查询
对程序运行中的一个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'}
]
*/
coolyue 写道
这些函数都具体运用在哪里？ 能说说吗 ？
coolyue
2008-04-01
这些函数都具体运用在哪里？ 能说说吗 ？
buaawhl
2008-03-30
i_love_sc 写道
太高深了，我等凡人只有暗自伤心的份。
我可是一句数学名词, Category理论都没有写.就是希望咱凡人自己写一点凡人看的东西.
没想到写的文字如同天书一般面目可憎, 又没有天书那样有理论深度. 失败啊.
只有自己完全理解了的东西, 才能够通俗易懂地讲出来.
这个贴的内容, 我自己也不是完全明白. 还是在不断求证过程中.
i_love_sc
2008-03-30
太高深了，我等凡人只有暗自伤心的份。
buaawhl
2008-03-30
经过一番思索. 我又想到了一些东西.
>>, >>, >>= 等一系列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)
>>, >>, >>= 等一系列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)
buaawhl
2008-03-29
好像有点明白了. 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.
形成这样一个函数调用链, 是为了强制产生运行栈 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.
lichray
2008-03-29
问题就在这儿。在普通语言中，这样写看起来是没问题的，但一遇到并发就全是问题了。（想想看也容易理解：如果只需要这样的话，那还要 Monad 的原子延续做什么呢？）最关键的不是执行的顺序，而是执行的态度。有了延续这样的能够安全访问执行栈上任意一点的技术，才能安全地在 do 中的 IO 语句中进行并发。Haskell 不是为了没事找事儿采用这样“奇怪”的 IO 方式（也是一种程序组织方式）。
buaawhl
2008-03-29
Trustno1大人的天书, 不是我这样的凡人能看懂的.
AlbertLee大人的翻译, 很好, 很强大.
但是, 看不懂啊.
电影<功夫>里面,一个高手临死的时候,对周星驰说, (好像是这个剧情, 戏仿<蜘蛛侠>雷同情节)
the more powerful, the more responsible
周星驰含泪叫道, 听不懂啊, 说中文好不好?
高手重复了一遍, 能力越大, 责任越大.
没有数学功底,不懂范畴理论(category theory), 怎能窥得天书 ?
-----------------------------------------------------------
我觉得 Monad 的设计思路, 也许可以用在普通的编程中.
大部分函数都是 Pure Function. 需要 IO 的部分, 或者放到 AOP Advice/Proxy里面, 或者分离到一些 Monad Proxy 类里面.
而且, 在普通编程语言里面, 实现用 Monad Proxy 分离 IO 部分, 应该比 Haskell 简单许多.
因为普通编程语言是会保证执行顺序的.我们可以放心地写
而不需要生成 chain.
只是,我不能完全明白, 是否是因为执行顺序这个原因, Haskell Monad 才需要 Chain.
还是因为别的原因.
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.
还是因为别的原因.
lichray
2008-03-29
个人认为，差不多了。关于 bind 方法上的理解还有一些问题，但说起来很麻烦，就等 Trustno1 大人来仲裁吧。他的这个帖子：回albertLee:关于Category Theory 和Monad中说的比较详细，但还不够浅显。AlbertLee 的一些翻译结果可以去网上搜一下，如果里你很关心 Monad 的话。
buaawhl
2008-03-29
lichray 写道
do notation 是 Monad 传递“世界变量”进行延续调用的一个简化语法，展开后应该是一个以 >> 算符连接、以 >>= 算符结尾的一个 Monad 调用序列，
>>, >>=
这就是传说中的 Monad Bind 吗?
ajoo有一个JParsec项目, Haskell Parsec (一个parser combinator)的 Java 版本.
http://jparsec.codehaus.org/
里面的Parsers类的bind方法, 好像也是做这件事情的.
参照 JParsec Parser.bind() 方法的实现.
我发现 (或者说, 我猜想)
bind 做的事情, 有些类似于 Chain of Responsibility / Chain of Command.
bina 的主要目的把一串行为组装成一条链.
bind 的代码可能如下
bind ( action, nextAction) {
return new Function() {
action();
nextAction();
}
}
如果一串序列调用, action1, action2, action3
就是这样组合
f = bind( action1, bind(action2, action3))
当 f 执行的时候,
即调用 f()
就会顺序执行
action1(),
action2(),
action3().
do notaion 应该做的就是 bind 的工作.
利用 >>, >>= 等运算符组装一个 Chain of Command / Responsibility
是这样吗?
通过以上种种迹象,我总感觉到 Monad do notaion 对顺序执行的一种强制保证.
--------------------------
lichray 写道
而在于使所有的 IO 都使用一个“世界”，然后把函数调用做成一个类似 reduce 下降的执行链，避免 IO 的副作用污染到程序的其它部分。
我的感觉上, Monad类型定义本身就是用来包装并隔离副作用的.
其他的Pure Function还是Pure Function.
Monad是把 IO部分强加到 Pure Function的外部, 产生一个 Chain.
Pure Function 只是 Chain 上的一个环节.
每一条 IO 操作, 也只是 Chain 上的一个环节.
比如,Monad可能产生这样的一种 Chain,
我把它猜想为一个 List 形态的东西
f = [IO, Pure1, IO, Pure2, IO, IO, Pure3]
具体的产生过程可能是这样,
IOMonad = Monad { IO, _, IO, _,IO, IO, _ }
// 产生一个模板. 里面的 _ 表示空位, 用来放入 Pure Function 的.
f = IOMonad (Pure1, Pure2, Pure3)
结果就产生了一个 chain, 内容是 [IO, Pure1, IO, Pure2, IO, IO, Pure3]
不知道对不对?
因此我猜想, 最外层的Monad定义,已经起到了隔离包装的作用.
do notation 应该是主要用来生成 action chain 的.
假设 do notaion 是用来生成 action chain 的.
那么, 为什么一定要产生这种 chain 结构.
下面的方法
IOMonad ( Pure1, Pure2, Pure3) {
return new Funciton() {
someIO();
Pure1();
anotherIO();
Pure2();
againIO();
onceMoreIO();
Pure3();
}
}
f = Monad(Pure1, Pure2, Pure3);
f();
不是更加清楚, 更加方便吗?
我想不出来, 为什么一定要产生这个 Chain 结构.
所以, 我猜想, 可能是因为同一层次的代码, 可能不能保证顺序执行.
lichray
2008-03-29
有一点偏差。do notation 是 Monad 传递“世界变量”进行延续调用的一个简化语法，展开后应该是一个以 >> 算符连接、以 >>= 算符结尾的一个 Monad 调用序列，并非你想的那样。这样做的意义不在于对齐函数调用的顺序，而在于使所有的 IO 都使用一个“世界”，然后把函数调用做成一个类似 reduce 下降的执行链，避免 IO 的副作用污染到程序的其它部分。
PS: 啊，那个“申请”过程是 JavaEye 的一个小 Bug，关闭了申请之后这提示还会出现。申请了就已经是成员了。
PS: 啊，那个“申请”过程是 JavaEye 的一个小 Bug，关闭了申请之后这提示还会出现。申请了就已经是成员了。
buaawhl
2008-03-29
:D
不是谦虚, 也不是婉拒. 只是这贴还是个半成品.
以后, 经过整理, 可能还会重新发一份综合了大家意见修正了谬误的贴.
已经申请加入.有机会好好阅读圈子里面现有的资料.
网上现有的很多资料的学术性/数学性太强,以至于我们民科(对科学有兴趣但是却苦于文化不够的农民科学家)很难真正理解.如果有更多的通俗版本(下里巴人看的)就好了.或者,函数式的一些思想注定是阳春白雪.
------------------------
另外一个问题是,
如果不是因为执行顺序的问题,
Haskell Monad 为什么要强制把一条条的 IO 语句, 分在不同层次的函数调用中. 比如, do notaion 做的那样?
Haskell的do语句可能就是把看起来是平级顺序语句转化成层层嵌套调用的语法糖。
比如，
do
readSomething
print something
实际上会被翻译成函数调用的嵌套形式。
g() {
readSomething
f() {
print something
}
}
不知道我对 do notation 的理解是否正确?
不是谦虚, 也不是婉拒. 只是这贴还是个半成品.
以后, 经过整理, 可能还会重新发一份综合了大家意见修正了谬误的贴.
已经申请加入.有机会好好阅读圈子里面现有的资料.
网上现有的很多资料的学术性/数学性太强,以至于我们民科(对科学有兴趣但是却苦于文化不够的农民科学家)很难真正理解.如果有更多的通俗版本(下里巴人看的)就好了.或者,函数式的一些思想注定是阳春白雪.
------------------------
另外一个问题是,
如果不是因为执行顺序的问题,
Haskell Monad 为什么要强制把一条条的 IO 语句, 分在不同层次的函数调用中. 比如, do notaion 做的那样?
引用
Haskell的do语句可能就是把看起来是平级顺序语句转化成层层嵌套调用的语法糖。
比如，
do
readSomething
print something
实际上会被翻译成函数调用的嵌套形式。
g() {
readSomething
f() {
print something
}
}
不知道我对 do notation 的理解是否正确?
lichray
2008-03-29
引用
Haskell是Lazy语言,替换表达式的时候,可能会忽略掉“不可到达的计算”里面的表达式.
Exactly Right.
引用
这是不是说明, 程序执行的顺序, 有可能和代码书写顺序不一致呢?
这个并不完全是。代码书写的顺序是从左到右，但有些编程语言就是规定了参数代入顺序是从右到左。对于惰性语言，优势在于这只是一个实现问题，无关程序执行效果。当然，还有一些执行优化上的优势。例如可以放手进行循环不变量外提优化而不需考虑对逻辑结构的影响。
PS: 这是在谦虚还是在婉拒呢...你应该能感觉到，你的水平已经远超圈子里80%的人了，我是组长我怎么不知道。。。
buaawhl
2008-03-29
lichray 写道
引用透明性，《为什么函数式编程至关重要？》一文中是这样描述的：
事实上它是等式推理的一部分：支持 α-替换 全部并支持 β-替换的一个子集。α-替换表现为在词法作用域范围内，对任意一个变量的所有次出现进行全体换名，程序执行效果完全不变。β-替换表现为将表达式作为函数参数代入，等效于对函数体中该表达式的所有次出现替换为该表达式，程序执行效果完全不变。但 β-替换 因为可能导致“不可到达的计算”不被执行的问题，在非惰性的函数式编程语言中不能总是成立。
附：建议把这篇文章发到 函数式编程の道 圈子。
引用
因为没有副作用能够改变表达式的值，因此可以在任何时刻对它求值。这一特性将程序员从规定控制流的重担之下拯救出来。由于表达式可以在任何时刻被求值，程序员便可以随心所欲地使用自己要的值来代替变量，反之亦然——也就是说，程序是“引用透明”的。这一自由使得函数式程序与它们传统的对应物相比，更容易数学化地控制。
事实上它是等式推理的一部分：支持 α-替换 全部并支持 β-替换的一个子集。α-替换表现为在词法作用域范围内，对任意一个变量的所有次出现进行全体换名，程序执行效果完全不变。β-替换表现为将表达式作为函数参数代入，等效于对函数体中该表达式的所有次出现替换为该表达式，程序执行效果完全不变。但 β-替换 因为可能导致“不可到达的计算”不被执行的问题，在非惰性的函数式编程语言中不能总是成立。
附：建议把这篇文章发到 函数式编程の道 圈子。
Thanks.
lichray的内容, 我大致看懂了.解除了很多疑惑.
关于β替换.我的猜想如下.
β替换是替换表达式.Haskell是Lazy语言,替换表达式的时候,可能会忽略掉“不可到达的计算”里面的表达式. 因此替换结果可能和 Eager语言(Not Lazy)不同.
---------------------
引用
因为没有副作用能够改变表达式的值，因此可以在任何时刻对它求值。这一特性将程序员从规定控制流的重担之下拯救出来。由于表达式可以在任何时刻被求值，
这是不是说明, 程序执行的顺序, 有可能和代码书写顺序不一致呢?
---------------------
函数式编程の道 圈子, 不错.
原来很多内容藏在这里.
这个帖子的后半部分主要是征求解惑篇,充满了自相矛盾的猜想,漏洞百出.
尤其是关于保证调用顺序的部分, 几段代码表达的思路都是不一致的.
还不够进入 函数式编程の道 圈子.
lichray
2008-03-29
引用透明性，《为什么函数式编程至关重要？》一文中是这样描述的：
事实上它是等式推理的一部分：支持 α-替换 全部并支持 β-替换的一个子集。α-替换表现为在词法作用域范围内，对任意一个变量的所有次出现进行全体换名，程序执行效果完全不变。β-替换表现为将表达式作为函数参数代入，等效于对函数体中该表达式的所有次出现替换为该表达式，程序执行效果完全不变。但 β-替换 因为可能导致“不可到达的计算”不被执行的问题，在非惰性的函数式编程语言中不能总是成立。
附：建议把这篇文章发到 函数式编程の道 圈子。
引用
因为没有副作用能够改变表达式的值，因此可以在任何时刻对它求值。这一特性将程序员从规定控制流的重担之下拯救出来。由于表达式可以在任何时刻被求值，程序员便可以随心所欲地使用自己要的值来代替变量，反之亦然——也就是说，程序是“引用透明”的。这一自由使得函数式程序与它们传统的对应物相比，更容易数学化地控制。
事实上它是等式推理的一部分：支持 α-替换 全部并支持 β-替换的一个子集。α-替换表现为在词法作用域范围内，对任意一个变量的所有次出现进行全体换名，程序执行效果完全不变。β-替换表现为将表达式作为函数参数代入，等效于对函数体中该表达式的所有次出现替换为该表达式，程序执行效果完全不变。但 β-替换 因为可能导致“不可到达的计算”不被执行的问题，在非惰性的函数式编程语言中不能总是成立。
附：建议把这篇文章发到 函数式编程の道 圈子。
buaawhl
2008-03-29
Trustno1 写道
引用
正如前面所说的。Haskell中，
a = f(x)
b = g(x)
这种同一层的两次f(x)调用，不一定能够保证这两条语句的执行顺序。
要保证f在g之前执行，我们只能写成 g ( f (.. ) ) 的形式，才能保证 f 在 g 之前执行。
a = f(x)
b = g(x)
这种同一层的两次f(x)调用，不一定能够保证这两条语句的执行顺序。
要保证f在g之前执行，我们只能写成 g ( f (.. ) ) 的形式，才能保证 f 在 g 之前执行。
？？
这个地方, 我一直不明白.
Referential Transparent 到底是什么意思?
难道就是 Final Variable(变量是Final的,只能赋值一次)的意思?
忘了从哪里看到的. 里面说, Referential Transparent 的意思是,
在一定范围内, 只要表达式的字符串一样, 那么值必定一样.
比如, f(x + 2), 在另一个地方也出现了 f(x + 2).
由于 x 是final的, f() 函数是 pure funciton. 那么两个 f (x + 2) 必然是一样的.
因此, 编译器可能进行优化. 执行顺序不一定和代码顺序相同.
不知道是否如此?
发表评论
提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则
buaawhl
- 浏览: 585659 次
- 性别:
- 来自: china
- 详细资料
搜索本博客
最近加入圈子
最新评论
-
网上银行的安全操作设计探 ...
有道理，不知道建设银行的UKey有啥用？
-- by sjz209 -
网上银行的安全操作设计探 ...
有道理，不知道建设银行的UKey有啥用？
-- by sjz209 -
网上银行的安全操作设计探 ...
1、据了解，动态口令采用的就是楼主说的第2种机制，所以动态口令发生器会有一个容错 ...
-- by jxb8901 -
谁说搞技术的没有幽默感？
yyliuliang 写道部门老大宣布放一年长假，大伙欢呼雀跃，连作三个俯卧撑表 ...
-- by hongfei3 -
谁说搞技术的没有幽默感？
幸存者 写道为什么我觉得不好笑？是因为我没有幽默感么？ bingoo
-- by roger
评论排行榜