探讨一下数据驻留模型

有几个问题不理解，讨教一下。

pi 演算不能以顺序编程实现，能不能举个不能以顺序编程实现的例子。
erlang 没有实现真正的 pi 演算，其未能实现之处何在。
erlang 是真正的并发，判断是否为真正的并发的依据是什么。
最后 pi 演算和真正的并发有何差别？做到哪一步叫真正的并发，做到哪一步叫满足 pi 演算。

谢谢。

“当 Erlang 的实现人员开始使用微线程的时候，就已经说明了 Erlang 只是对 PI 演算的模拟。”　—— lichray 的大号 Lich_Ray

PI 演算和传统上大家对并发的认识一样，假定了存在一个物理上的并发系统。对于计算机程序来说，这样的一个系统就类似于一个有无限 CPU 的计算机。这和用队列实现的多线程有什么区别呢？本质上的区别在于，前者是体系外并发，后者是体系内并发。所以说，当 Erlang 的实现人员开始使用微线程的时候，就已经说明了 Erlang 只是对 PI 演算的模拟。这就是对你前两个问题的回答。

需要注意的是，Erlang 对 PI 演算实现的这种“模拟”性质，和常见函数式编程语言对 Lambda 演算实现的“受现实约束”问题（比如内存不是无限大，数字不是函数等等）是两码事。前者是“是”，但不好，而后者是“不是”，好不好有待商榷。

当实际上已经不可能在现有的计算机（也许未来会有 DNA 计算机，那个另当别论）上产生体系外并发时，传统上就把会导致线程在系统的调度下轮流执行定义为“真正的并发”。真正的并发必然导致副作用。Erlang 就是这样的并发，它的线程在队列上依靠函数调用计数被“轮流执行”。

顺便解决一个你提出了很久的问题，关于外部打断一个长计算。其实这不算是个问题。你在你所认可的那些支持“真正的并发”的语言中，想立即打断一个原本不挂起接受信号的线程，不使用暴力手段也是不可能的。Erlang 中的暴力手段是虚拟机相关的。Erlang 的虚拟机每次执行一个函数，但这里的函数并非你所想的是“叫虚拟机执行的函数”，而是被用 Lambda 演算的思想彻底把一个拆开成n个调用后的“算子”。所以想从虚拟机打断一个长的函数调用是再简单不过的事，只要打断调用过程中的一个算子就行。

f(int * x)
{
 *x=0;
 g(x);
 printf("%d",*x);
}
g(int *x)
{
 *x=*x+1;
}

func(X, Receiver, Env) when Receiver is none -> %% Receiver 无值从此处调用    
Config=config:do_something(Env)，    
Env.remember_notice(self(), {func, [X]})   
end.   
  
config:do_something(Env)->   
  Env.remember_notice(self(), {config:receive, [X]});   
  end.  

你讲的很清楚，我想我明白你的意思了。所谓“真正的并发”大概是“实用的并发”翻译不当造成的。
但对于“真正的并发”造成副作用我依然有疑问。难道因为存在线程调度，所以就有副作用？

好, 我们抛开并发不谈, 假设一个纯粹的函数式语言, 也没有 receive 单词, 到底能不能改动内存某处的数据? 如不能改动, 它和命令式语言怎么分庭抗礼?

你仍然没有理解lichray的意思。你之前曾经提出一个断言，

而Lichray告诉你，Erlang这样的语言并没有实现PI演算，只不过是很好模拟了PI演算,而不是把PI演算还原为等价lambda 演算,因为这是在理论模型上根本做不到的。所以你这一断言的前提条件就已经完全错误了.

但是对于他说的，“真正的并发”无可避免存在副作用，我觉得这种说法混淆了。用进程调度下实现的"真正并发"所产生的副作用不是并发带来，而是图林机上模拟lambda 演算所固有的。而他所谓的实体并发，才是会产生副作用的并发。因为

为什么实体并发无法避免,side-effect?原因也非常的简单，side-effect实则上是状态的变迁。而所谓的状态的变迁实则上是一个对时间t的函数State(t).只要引入了时间,就会引入状态。在顺序式编程中，我们绝大部分忽略时间这个维度的.在单核CPU的顺序型编程中,只存在一个唯一的均匀流逝的时钟,那就是CPU时钟.这个时候我们可以把CPU时钟发生器看作一个函数t(),此时从机器内部看t()是一个无状态的数列.因此每一个并发实体的State(t)，都可以看成一个无副作用的函数。这就好比初中物理中讲述的牛顿时空观的概念,如果两个参考AB系相对于C参考系运动，他们在时刻t上观测C的某一点坐标是完全相同的。
但是一旦我们把程序,分布到多个CPU或者多台机器,那么那个唯一的均匀流逝的时钟就不存在了。各个CPU和各台机器之间的时间函数的流逝速度都是不同的，于是就必然会导致时钟校准问题。要做时钟校准，那么需要信号的传递。但是物理法则告诉我们，信号的传递不可能是无损耗也不可能是瞬时的。于是从A看B的时钟,与C看B的时钟是完全不同的.如果这时有三台机器,A,B,C，各自以自己CPU的时钟运行，同时以B的时钟进行校准。这时在B在t时刻，向A,和C发送信号让他们停止，并且让A和C拍下t时刻下B的数据,此时A和C所得到的数据就会产生不同。这样就产生了状态。在同一个时刻t,函数StateB(t)的取值完全不同。

lambda 演算和PI演算的不同之处也就在这里。在lambda演算中默认了一个唯一的均匀流逝的时间函数t(),并且每一个并发实体不可能同时对函数t()进行求值,因此从两个不同的并发实体CB去看某一个并发实体A的状态，总是State函数在两个不同时刻的取值，因此在lambda演算下，在某一个时刻t整个并发系统中每一个并发实体观测A状态的结果只有一个StateA(t)={StateA(TX(t))}.TX(t)=t.一个并发系统的中的某个并发实体在时刻t上的取值，就等于该并发实体在t时刻的状态，State的取值和时间t一定是一一对应，也就是说可以构成一个函数。

而在PI演算内,则完全不同,首先它不存在唯一的时间函数t(),其次一个并发实体A的本身状态，实则上是整个并发系统中其他各个并发实体观测A所得到值的集合，既StateA(t)={StateA(TB(t)),StateA(TC(t)),.......} t与状态变化不构成一一对应,只能是一个relation而不是function.

用更为数学化的语言来说就是，令时钟基准的机器的时间序列t={t1,t2,t3...},其他各机器的时钟校准函数集合T={TA，TB,TC,TD....}.那么基准机器相对于整个系统的的状态变迁态射就是S:Txt->s.


举个简单的例子，2*2=4,sqrt(2)=1.414.....。这在数学上都是没有问题，但是我们要问这样一个问题，把2*2应用到人是什么？很简单2个人的2倍是4个人。那么2个人的平方根是什么?这就没有什么意义了。
同样的道理,命令式语言的基础图林机和函数式语言的lambda演算是完全等价的。但是这并不是说在物理实现上他们也是等价的。虽然图林机和lambda演算都是一种理想模型，他们都需要无穷的计算资源。但是对于图林机来说，它需要的是一根无限长的可回写纸带，符号表的状态可以停留在纸带上。而lambda 演算则是没有状态停留，一旦对一个lambda演算进行求值，那么必须把它算完，这就相当于需要一根无限长但是单向的纸带。我们现在的物理资源都是可回写的，对图林机的实现不仅更简单而且更经济。

但是这种经济,仍然是不涉及时间前提条件下的。如果我们引入了时间这个维度,我们就会发现命令式语言就不那么经济。正如,我们物理实践中发现的规律那样，我们要在两个互相运动的参考系之间进行时间同步，那么首先要知道校准信号的传播速度，而要想测量校准信号的速度又必须首先校准不同参考系内的时钟。为了消除这种无穷倒退，那么我们就假设校准信号的速度在传播过程中是不变的。同样,在两个并发实体之间传递的信号必须保证是与两个并发实体的时钟流逝无关,是一个恒定的值。要保持这个恒定，命令式语言和函数式语言采用不同的办法，前者需要使用锁，后者本身天然就恒定不变。而两者相比较,显然后者更加合适，因为在并发环境下，锁的工作方式仍然是限制两个并发实体不可能再同一个时刻对函数t()进行求值。也就是当A向B传送一个信号，在B接收完之前，其他的并发实体都无法访问A。这种访问限制是通过其他并发实体不断发送探测信号给A询问是否可访问做到的。在单台计算机上，是依靠电信号的检测来实现的可以看作是瞬时的，但是在多台计算机上考虑到网络传输则无法近似瞬时的传递信号。在锁方式下，传递一个信号，计算机之间实际要发送接收许多无用的信号。这种消耗已经远远超过了无限长纸带模型所带来的存储消耗，同时并发实体运算速度带来的效率已经大大抵消了函数式语言模型的低效性。更为重要的是，函数式语言的恒定性使得,并发实体之间传递的信号种类大大增加了。最简单的就是，代码本身。在命令式语言之中，代码本身也是一个随着时间t而改变的relation.这就使得代码无法作为信号在并发实体之间传递。

函数式语言,在并发上优于命令式语言的关键,并不是它能否突破单CPU下的计算瓶颈问题,而是函数式语言可以把随着时间t进行状态迁移的对象的规模规约到最小。它只容许存在理论模型下与时间t流逝有关的无法规约为函数的relation，其他所有的对象都还原为时间t的流逝无关的function。

我又回来了.



说来说去还是绕不开状态, 你认为 monad 能不能算 lambda 演算? 作为现实物理世界存在的 io 问题是不是 lambda 演算无法解决的?

我想假如函数式编程的确已经以 pure 的方式解决了 io 问题, 那么下一步变成多个实体之间并发是顺理成章的.

不要老是挥舞着lambda与图林机等价，这种大杀器.
起码在这之前，请了解一下这句话的前提条件.




有人跟你说过Monad是Lambda演算了么?

不是我喜欢挥舞这玩意儿, 我真不懂等价在哪儿, 假如 lambda 演算不支持中断或其它可以驻留的形式, 它能解决的问题域就和图灵机的问题域完全不同. 如果目标问题域都不同, 还谈什么等价.

我不知道 monad 算 lambda 演算还是算 lambda 演算的一个补丁, 但是号称纯函数语言的 haskell 确实依靠他解决 io 问题, 而 io 问题可以算是中断问题的代表.

谁和你说图林机解决IO问题来着?