探讨一下数据驻留模型

Good. 精彩的解释.

http://www.sics.se/~joe/thesis/armstrong_thesis_2003.pdf
这是Erlang创世人的论文，
他自己写的
p87


Abstracting out concurrency is one of the most powerful means available for structuring large sodware systems. Despite the ease with which concurrent programs can be written in Erlang it is still desirable to restrict code which explicitly handles concurrency to as few modules as possible.

The reason for this is that concurrent code cannot be written in a side effcect free manner, and as such, is more diecult to understand and analyse than purely sequential side-ecect free code. In a system involving large numbers of processes, issues of message passing ordering and potential dead- or live-lock problems can make concurrent systems very diecult to understand and program.

我觉得从命令式语言转过来的程序员，在学Erlang之前最好先把Joe的论文看一遍。看过这个论文基本上可以避免在函数式语言和并发上的很多事实而非的认识。

这篇论文我看过中文版的, 段先得翻译的.

翻译后是这样的:

抽象出并发是用来划分一个大型软件系统的最有力的手段之一。运用该方法不仅可以轻轻松松地用Erlang来编写并发程序，更是可以把显式地对并发进行处理的代码约束在尽量少的模块中。
这样做的原因是，并发处理的代码一般都很难以无副作用（side-effect free）
的方式来编写，就使得并发程序比纯顺序化的、无副作用的代码更难以理解和分析。在一个包含大量进程的系统中，消息传递顺序化问题和潜在的死锁（dead-lock）或活锁（live-lock）问题会使得并发系统非常难以理解和编写。

这个翻译没有问题.

这段文字貌似和现在的话题没有关系吧. 如果你是说访问同一片内存会死锁,请回到主贴. 我已经明确表达过, 用一个进程做为数据持有进程. 其它进程通过发消息给它进行数据读写. 我想我对这套观念还是比较了解的.

第一原文写的是cannot be written ,cannot be 的意思是不能,而不是一般都,Joe的用词是非常准确的，我想他作为并发应用的大牛是不会不了解基于pi-calculus并发模型的本质是无法用lambda calculus来表述这一常识的.如果你不熟悉pi-calculus的基础概念请请参阅下面这个J. M. Wing 的FAQ on pi calculus
http://www.eecs.harvard.edu/nr/cs257/archive/jeannette-wing/pi.pdf

5. What is the analogy between π-calculus and λ-calculus?
λ-calculus is to sequential programs as π-calculus is to concurrent programs.
More precisely, λ-calculus is the core language of functional computation, in which “everything is a function” and all computation proceeds by function application; π-calculus is the core calculus of message-based concurrency, in which “everything is a process” and all computation proceeds by communication on channels. 
......
An interesting aside: λ-calculus can be encoded in π-calculus.
第一句很明确，把λ-calculus 和  π-calculus 的解决问题的领域分的很清楚了。
第二句说明， π-calculus 是研究基于message passing 并发的核心模型,它的地位，如同λ-calculus 在顺序型编程中一样重要。
第三句说明，λ-calculus 只是 π-calculus 的一个子集。λ-calculus可以通过π-calculus 来进行从新诠释。换而言之π-calculus 是高于λ-calculus，λ-calculus是无法解决π-calculus所需要面对的并发问题.


第二，Joe在这里说的也很清楚，
issues of message passing ordering and potential dead- or live-lock problem.这里讨论的我们无法把并发进程写成side effects free是因为，在message passing和/SMT两个模型中都存在着根本的困难，前者是因为我们无法把message passing 顺序化,后者我们必须面对活锁和死锁的问题也就是著名的dead lock问题，这是两个问题是目前根本无法解决的。

对于技术类文章，请多读原文，多找英语参考资料。中文翻译固然是捷径，但是抄小路很多时候都会害人不浅.

先佩服一下 Trustno1 的渊博。和你一起讨论能学到不少东西。

我拜读了一番你推荐的 pi 演算的内容，重点看了他所给的incr server例子。大概理解了其中的意思了，这是一个为并行而设计的形式系统，实现是基于进程和消息的。
在我上文提到的中译本中，Joe非常幽默的提出了一个！！运算符，也暗示了pi演算是lambda演算的超集。
这里有一个问题先商讨一下：
正如文章所言：
Rather, π-calculus is best viewed as a formal framework for providing the underlying semantics for a high-level concurrent or distributed programming language.
又
To illustrate how large this gap can be, consider again the modeling of remote procedure call in Question 4. An implementation of RPC would have to consider details such as marshalling and unmarshalling arguments and results, handling failures such as links or servers going down, synchronizing clocks, locating the server in the first place, and so on. Clearly, at a level of understanding a high-level protocol, where you are interested in only the interactions between various clients and servers (e.g., users making reservations through an on-line travel agency), you want to ignore that level of detail. Here, π-calculus as a modeling language is a win. But, eventually you have to implement not just RPC, but also the application-specific protocol (e.g., travelers should not double book). How to guarantee you have correctly implemented your communications protocol such as RPC as well as your application-specific protocol is still a hard problem.

下面谈谈我的理解。

我认为作者实际上是将PI演算视为一个框架，一个模型叙述体系，一个有趣的形式系统，相信作者也不至于疯狂到将mov ax,bx实现为向“mov server” 发送bx，然后将收到的结果放进ax。

很直观的，所有PI模型的实现无不建立在“PI模型的子集”的基础上——所有的并行运算必然建立於顺序运算。我认为，并行运算是顺序运算的扩充，不宜过度渲染并行的地位。
比如这套PI形式系统，对于描述并行是很有意义的，甚至可以说是并行的灵魂，但其实现依然依托于顺序运算。没有顺序运算所提供的进程和消息，PI系统只能是纸上谈兵。

从这个角度来说，像前文我分解receive的实现原理，是在试图解剖消息系统是怎么建立的，解释erlang这个神奇的并行语言其背后顺序的故事。

综上，pi演算可以分解为lambda演算，因为它本身即可以用也必须用 lambda演算来实现。兄台认为receive属pi演算，就不能再当成lambda演算来看待，我以为不尽恰当。

我希望多有些明白晓畅的中文资料，毕竟不在外国，没有环境熏陶，很多单词无法咬准其意义，这个方面真的希望国内的高手多出点力，一天译一节，一个月就有 20节，大家都受益无穷。编程方面，要我看国外的资料，我不介意，毕竟是主业，看过的资料也不少。但编程的范围那么广，天上飞的水里游的，从金融到GIS，从汽车到居民楼，无所不包，方方面面都去看外文资料，很头痛。像段先得同志翻译的这个资料，非常顺畅，非常口语化，比书店那些用金山词霸翻译的书强多啦。

好像我怎么也没有从这段文字里看出，所谓的

人家只是说，实现特定应用的protocol并不是pi calculus关心的事情。

即便是如此，那么Joe的那句concurrent code cannot be written in a side effcect free manner.你又如何反驳呢?


这也是毫无根据的自我引申,question 1已经明确说明了，An interesting aside: λ-calculus can be encoded in π-calculus.

最后不要忘了，现在的计算机还是基于图灵机的，那么Erlang搞函数式语言又有什么意义呢?大把大把的c++ Message passing framework又不是没有。




你提出的这种方式对于调度器来说就成了大麻烦.这种回调方式，正是gen_server的实现机制。gen_server内部实现一个loop负责接收消息，而通过几个handle callback来负责处理消息。从handle callback层面上来看，的确是side effect free的.但是我们要反过来问，为何Erlang不把gen_server这种机制做成语言级别的呢?原因很简单,因为这并没有避免side effect而是把side effect引入调度器不仅仅增加了代码的复杂度，而且调度器的side effect仍然会反馈到代码里，使得side effect更加难以控制。
这里的关键就是所谓的Enviroment.我们先来看正常的Erlang调度器是如何工作的，当你执行spawn的时候，Erlang的调度器就会启动一个该进程的Enviroment,并且把spawn(Moudle,Fun,Args)传入这个Enviroment,这和你的方案是没有区别的。然后环境会对Moudle:Fun（Args）进行求值，如果这个Fun什么都不干，那么它直接退出。如果它干一些事情的话，那么调度器就会给这个环境分配一定额度的reduction比如1000,所谓的reduction就是指调用函数的次数，因为Erlang是函数式语言，不考虑BIF的情况下,每对一个函数进行一次函数调用,那么就相当于执行一次指令，这个时候就把reduction减1，比如说写一个每调一次inifinite_loop()就进行一次reduction.如果该进程的reduction减为0，那么该进程让给其他进程运算，直到下一次调度到这个进程那么就从上一次循环的地方继续往下reduction.如果这个时候给inifinite_loop()内部加一个receive,

receive_loop()->
     receive 
       msg-> do something.   
    end,
receive_loop().

如果该进程的mailbox没有message,那么该进程的reduction就自动归0让给其他进程，这就相当于在receive函数上进行同步.
那么再来看你的方案，你的方案实则上就是把这个receive_loop()，移动到调度器里，写成伪代码就是这样



好了，那么我们来看看这样一个需求

receive_loop()->
     Config=config:read_config(self()).
     receive 
       Msg-> do_something(Config, Msg）
    end,
    
receive_loop().

在这里,第一行中的意思是,我要在进程开启前不接收任何数据
Config=config:read_config().
那么换成你的写法就是


好了，这个时候如果func完成再次进入while循环,还是没有任何数据，那么是否要执行func呢?调度器是无从得知的。当然也不是没有解决办法，比如说你可以在X上设置一个flag,保证每次进入func的时如果flag为false就不读config.但是这意味着什么呢?这意味着无论是否有message,调度器必须对每一个进程的func运算完它的reduction,然后才能进入下一个进程。这无疑就大大降低了Erlang的实时性.当然我们可以把这个放在一边不谈，毕竟这样的写法在语义上没有什么问题。
现在假设,config是某个第三方的lib库，并且它的某一个函数也必须要用到Env，那么代码就变成了这样


那么这个时候你能否保证,config:do_something当中，不对  Env.remember_notice做任何破坏性的修改呢?这恐怕是无法保证的.于是do_something就可能从一个遥远的代码上对Env产生了一个side-effect,使得下一次的receive到底进行到哪里根本无法预料。
其实这样一种Enviroment,其后果和ETS是一模一样的。ETS是可修改的,于是ETS是带状态的.只要ETS带上状态，那么它就会产生side_effect.同样你的Env，也是一个可修改的状态，side-effect便无可避免。那么gen_server为什么可以这么做呢?很简单，gen_server的四个handler全部是静态的module function,在代码运行时你无法对他们进行更新.

这个话题已经扯的比较远了。我先修正一下你对 Env::remember_notice 的实现

Env::remember_notice(pid,func,X)
{
put_into_handler_table(pid,func,X).//把call back存放在某处，比如一个变量或者某个表中
}

// code for message loop
while(hasNewMessage(pid) || isTimeout(pid))   // 这样表达才合理。其中 timeout 应在呼叫 remember_notice 函数时传入
{
Receiver rec= env->receive_message(Pid)；
Callback= env->get_callback(pid）;
Callback(rec).
} 

这个“遥远的代码”不足以当作立论的依据吧。没有充分的理由显示这种“遥远的代码”必然存在。

至于这种对 receive 的解释和 Joe 的言论是不是冲突，我并不关心。在我看来，随机事件都来自中断向量表，而这个是回调可以做到的内容。

最后再谈一下 PI 演算。我认为 PI 演算在原子级别是 lambda 演算，或图灵演算（？），由于后两者等价，简单的说 PI 演算在原子级别必定是 lambda 演算。这种关系不是文章中提到的太平洋（pi）与东海（lambda）的关系这么简单，而是基础建筑和上层建筑的关系，没有 lambda 演算 pi 演算根本无法进行。我认为这一点是可以完备的证明的，囿于知识积累和精力有限，仅从直观上得知。不信请来证伪。

很简单，一个C的buffer,被随意改写是否必然存在呢?当然是不一定的，只要我代码维护的好，只要我做够单元测试,只要........
一个互锁的代码，是否必然存在互锁呢?当然是不一定的，只要......




请参看这里:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.5


This is precisely the same constraint that we had to deal with in section 3.4.1, where we found the need to introduce explicit synchronization to ensure a ``correct'' order of events in concurrent processing of objects with state. Thus, in an attempt to support the functional style, the need to merge inputs from different agents reintroduces the same problems that the functional style was meant to eliminate.
以及下面的注释footnote 75
Observe that, for any two streams, there is in general more than one acceptable order of interleaving. Thus, technically, ``merge'' is a relation rather than a function -- the answer is not a deterministic function of the inputs. We already mentioned (footnote 39) that nondeterminism is essential when dealing with concurrency. The merge relation illustrates the same essential nondeterminism, from the functional perspective. In section 4.3, we will look at nondeterminism from yet another point of view.

这里面的理由说的非常清楚了，concurreny的本质问题在于nondeterminism ，从而导致对ordering interleaval message这一过程，已经不是一个function,而是relation.如果对nondeterminism 有什么疑问请准寻footnote 39的解释.

39 A more formal way to express this idea is to say that concurrent programs are inherently nondeterministic. That is, they are described not by single-valued functions, but by functions whose results are sets of possible values. 
In section 4.3 we will study a language for expressing nondeterministic computations.
如果再有不懂可以看第四章，有关amb的实现。另外如果你熟悉Haskell，可以去参考他的random实现，很容易理解什么是nondeterminism 。


至于是否离题。我觉得不是，在我前面很早就声明过,只要引入了concurrency，那么就无法避免状态变更,无法写出side-effects free的代码。因此函数式语言能做的仅仅是，把这些状态变更现在一定的范围之内。在Erlang里面把他们限制在receive块中，在Haskell里把他们限制在monad里。无论如何你都逃不掉，因此在并发程序中使用ETS这样的特性是很正常的，因为虽然它不是与lambda calculus同构的，但是却是与并发模型同构的。

这说的未免有点太简单了吧....听起来就好像在C里面加个异步/同步块也能实现优秀的并发似的。稍微详细一点：事实上，为了实现并发，λ-演算 和 π-演算 都要求增加新的、侵入式的编码风格。前者要求使用CPS，增加延续参数，后者要求使用消息通道。而在实际的编程语言中，提供了语法来免去用户自己使用这种机械的编码风格的义务。Haskell 只在 monad 引入延续，Erlang 只在 receive 块中使用通道。

刚才有事出门。经过和两位兄弟，特别是 Trustno1 的讨论，我表达一下我的理解。

首先，Erlang 的 receive 确实可以像我说的那样实现为中断形式，也因此可以归结为 lambda 演算的范畴。事实上也不会有“遥远的代码”的影响，由于进程各自独立，这种遥远的代码已经失去容身之所。

但是，关键，并发不是中断就足够的。Erlang 只有进入 receive 后，进程挂起后，才打开通道，接受消息，然后，在接受一条消息后，它要处理完这条消息再能处理下一条，和真正的并发还有一大步。真正的并发期望能时时刻刻接受消息处理。

不知道这样理解有没有问题。

如果没有问题，我将继续谈一点看法。