探讨一下数据驻留模型

下面我谈一下我的理解:

正如刚才所谈到的, 实际上图灵机在解决 io 问题时必须纳入到冯诺依曼体系或其它如哈佛体系等进行研究, 那么在使用 lambda 演算解决 io 问题时, 我想我们同样需要将 lambda 演算放到一个计算机体系里来看.

在图灵机处理时它有一个纸带, 关机后下次再开机可以接着运行. 那么在 lambda 体系如果要做到同样的事情,我们或许需要:

放一个一次写多次读的纸带, 以便将函数保存下来.下次从此处再开启运算即可.

需要注意的是, 和图灵机里的纸带不同, 这个纸带是供控制器用的, 而不是给运算器用的, 不是 lambda 演算的标配.

不知道我这样说能不能解释的通.

图灵机和 lambda 演算都是一种数学模型，拿来描述抽象的计算过程的，它们的本质是描述一个定义在字符集合上的函数。最好不要把一个图灵机对应于一台实际存在的机器或是实际机器中的一个部件，这么做貌似能够帮助理解，实际上只会带来混乱。

T1 兄久不回应, 考虑到马上要放假了, 我急不可耐的公布最后结论:

erlang vm 实际上是一个函数式语言的虚拟机, 其体系大概可以理解为以 lambda 演算为运算器, 自己实现了控制器.

我们编写的代码, 如 fun() -> 1+1 这种指令由运算器执行, 而 receive 指令则由控制器执行, 当调用 receive 后, 控制器就将函数挂起, 挂起的实质是将函数写到控制器用的内存, 当有输入(input)后, 控制器恢复函数.

关于挂起的解释:

函数式语言巧妙之处体现在函数持有自己的上下文(参数栈, 闭包), 由于函数的这个有趣特性, 我们可以将函数(连同它的上下文)转到另一个机器上执行.

挂起后, 函数的上下文全部放在此函数私有的内存中. 需要注意的是, 挂起意味着这轮演算已经彻底完结, 而不是暂停.

btw. 在函数式语言中, 函数可理解为数据, 数据也可以理解为函数, 故函数是可以持久化的.

关于收数据后的解释:

控制器负责将输入数据填在下次调用的函数上下文中(编译时确定填在哪个内存位置),之后再次恢复现场. 在这个步骤, 控制器将会操作记录在内存上的函数的上下文.之后调用内存中的函数. 这次调用是重新启动新的演算, 而不是继续上次的演算.

例:
(- 1) 的过程, 编译之后的伪代码大致如:

mov param1, 1   // 填写函数上下文(参数) 由控制器执行
mov func1, (- param1)         // 负运算. 由运算器执行. 过程是调用负函数.
// 运算器执行完后, 产生(归约?)出一个新的函数(这次是一个数字) -1, 放于 func1 处, 由运算器执行
mov out, func1    // 输出函数

一个(+ 1 1) 的过程

mov param1, 1   // 填写函数上下文(参数) 由控制器执行
mov func1,(+ 1)           // 按第一个参数展开函数, 由运算器执行. 按函数式程序原理, (+ a b) 解释为 ((+ a) b). 
mov param2, 2   // 填写函数上下文(参数) 由控制器执行
mov func2,((+1) 2)         // 加法运算. 由运算器执行.
mov out, func2  // 输出函数

一个有 receive 的加法机演算过程

receive         // 收取数据
mov param1, input   // 填写函数上下文(参数) 由控制器执行, 设 input = 1
mov func1,(+ 1)           // 按第一个参数展开函数, 由运算器执行. 按函数式程序原理, (+ a b) 解释为 ((+ a) b). 
receive
mov param2, input   // 填写函数上下文(参数) 由控制器执行, 设 input = 2
mov func2,((+1) 2)          // 加法运算. 由运算器执行.
mov out,func2      // 输出函数

需要注意的是,一次函数归约实际上会对应若干条指令, 这里这样写只是为了突出控制器和运算器的合作关系.

可以说, 图灵机的模型只记忆纸笔运算中的数据, 而 lambda 演算则连带每一步公式推导都记下来了, 这样看来 lambda 演算似乎更适合符号处理问题.

“时钟”这个概念同样可以转换。有一个现实的例子，subversion的revision。svnserve是机器B，两个svn分别是A、C。B在t时刻，给A、C发信号，带有revision，那么A、C可以用这个revision去获得B在t时刻的状态（如某个文件内容），而且完全相同。也就是说，用revision来表示t，那么StateB(t)就是幂等的，取值总是相同的。
现实中，我们需要的是可以观察的结果，无论实体在物理上如何并发，当我们用计算机去实现时，总是有方法按照需求得到可观察的宏观上的确定性。用一个具体数据表示“时钟”，那么实体交互时，“时钟校准”就基于现实的数据传输，虽然传输需要时间，但具有可接受的不变性。将这个“时钟”作为数据的一部分，使得时间的函数转化成了无状态无side effect的纯函数。


使用lambda演算，可以描述一个数据的计算图，和某个唯一的时间函数没有必然联系。只要对这个计算图的归约符合lambda演算的规则，就可以得到确定性的结果。符合规则的归约顺序有很多，这就可以并行、并发的方式来完成这个计算图的归约，而仍然保持整个计算图及其任何局部的无状态无side effect。并发和side effect并不是本质相关的。

这种办法叫做全局钟,但是全局钟的首要条件是，必须在A,B,C之间建立起同步的revision,你才能拿到同样的State(t).问题是你如何去同步revision呢?于是这个问题就变成了revision成为本地时钟的函数,revision(t).然后在tA,tB,tC三个时钟源上对revision(t)函数的取值.





lambda演算本身是顺序性的,他可以被并行，但是绝对不可能被并发.可被并行的一定是no-side effect的,可被并发的一定是side effect.
计算必然需要时间，计算是从混乱到有序因此总是熵减的，从物理上说要商减就必须有外界的能量激励这种激励就是时间信号.就如图灵机的读写头,他如何移动?在目前来看只能是时间信号的激励.
当你讨论Lambda演算是否是并行的时候请注意。并行这个词汇就意味着你的系统中引入了时钟信号.如果只有一个信号那么Lambda演算只能是串行工作的.当然你可以在Lambda系统中引入多个时钟来达到并行目的,但是请注意一旦引入了多个时钟那么你就必须面对多个时钟之间的同步问题,互不相干的两个图分支的运算最终都需要交换运算结果,于是我们又回到了上面的问题.我说lambda本身就默认了一个均匀流逝的时钟，因为lambda没有给出任何时钟之间信息交换的结构.

revA、revB、revC不需要同步，A、C用revB就可以得到StateB，无论revA、revC是多少，是不是时间的函数，StateB(revB)总是相同值。需要的只是数据的传递。
既然stateA、stateB、stateC都是无状态的函数，从模型上就不再需要时间这个概念，它不过是转化成了普通数据，关键就是数据的使用、依赖关系。无论用哪种模型，数据的使用不可避免，依赖关系总是存在的。最终，程序依赖我们提供的输入数据，我们使用程序的输出数据。

物理上当然有时间，但是在模型上不是必须的，lambda演算需要的是数据的依赖。实现数据传递、依赖都需要时间的先后关系，但这并不必以可观察的形式从程序中表现出来。物理上的side effect是存在的，但是程序中的side effect可以被完全消除，即使是并发。
这实际是在不同层面上对side effect的讨论，但对大多数程序员影响最大的还是程序上的side effect。如何执行这个程序，执行中物理上的side effect，可以对程序员透明。

如果不需要同步,你如何保证A上的StateB(revB)和B上的StateB(revB)是一样的呢?要么在机器启动之前就同步过了，要么就是在机器运行的过程中进行同步.无论哪一种同步,都是同步.当然对于前一种来说,信号的同步有可能是人工完成的,但是这并不能说明不需要进行同步.

所谓的side effect的意思是，就是这种效应会进行传播.物理上的side effect 必定会传播到程序语言中,在程序语言只能依靠特定的设施将两者隔离,而无法消除.

首先是数据传递的正确性，A拿到的revB和C拿到的是一样，都是B传给他们的，但revA、revB、revC本身的取值，相互可以没有关系
接下来就是一个循环：如果StateB(revB)是无状态的，取值相同的，那么StateB所依赖的包括revB、输入、闭包的所有数据都必须是无状态的，那么这些数据所依赖的其他数据、闭包也都必须是无状态的，那么这些其他数据....
整个程序的数据依赖关系是个有限集，最后就变成，如果整个程序的输入是无状态的，数据传递是正确不变的，那整个程序和任意局部都是无状态的，整个输出都是不变的。
那么，A、C拿到的State(revB)就是一样的。
如果这里的任何一个点被打破，加入了可观察到的side effect，那当然就完全不同了