欢迎光临
我们一直在努力

π-calculus与资源模型设计

众所周知我是π的支持者。原因很简单,就是π有着对『并发』概念的最小化完备表述。

对于程序员来说我不推荐系统学习各种进程演算或者进程代数,根本上这是基于符号重写的逻辑系统,跟编程的关系不大而且,对逻辑学基础的要求太高了。

但如果要一窥大师思想,我推荐阅读Robin Milner的图灵奖演讲:Elements of interaction,这个网上一搜就有,而且很好读;而且我相信它里面把共享变量看作进程,把通讯拆成I和O两个部分的思想,都是大家可以看懂的,而且,是醍醐灌顶的。


本文是在实现RP协议的原型时的一个思考。RP协议是一个类似HTTP Restful的通讯协议,但是它不依赖HTTP,在一定程度上它更希望象网络文件系统那样完成通讯双方的交互,但操作语义上选择了Restful的资源模型,而不是文件系统的open/read/write/close流语义。


在π里,最基础的表达式之一是input prefix,c(x).P这样一个形式,它的意思是P要等到channel c收到一个x消息才开始运行,这非常接近事件驱动模式,实际上,事件和消息并没有真正的区别,在数学上都一样。

但是这里需要注意的是,一旦x出现,这个表达式就被估值了,或者说,发生reduction,它就不再存在了,相当于一个数学表达式计算完了。

这和另一种情况不一样,就像一个库函数,或者一个服务点,函数可以被调用无数次,服务点可以服务无数次,而不是调用一次或者服务一次就消失了;这个时候,在π里,是用!来表达的,这个符号叫做replication,意思是它后面的表达式有无数个,每次reduce一个之后还可以继续使用。


replication在编程中是广泛存在的,如果一个函数只能用一次大家都会觉得它没什么用了。

但是一个函数或者一个服务点是一次性消费掉的单例(以下称为sink),还是replication,这里区别很大。我们举个例子。

在RP协议里,通讯双方的所有通讯都是通过Message Passing完成的;在这种情况下如果想模拟一个简单的Request/Response:

Client在发出消息的时候要即时创建一个Path,也就是name,或者说channel,π意义上的channel,在π里一切name都是channel;它发出的消息可能是这样的:

{
  to: '/hello',
  from: '/requests/123-456-789', // 临时创建的
  method: 'GET'
}

在Server这端,很明显,/hello是一个replication,而且不是一个sink,如果你往这个Path发送一个message,没有method属性,它不知道怎么处理;换句话说,/hello是replication only的。

Client的from,这个资源很有意思,它首先是一个sink,这个id 123-456-789也应该是一次性的,客户端即时分配它而且应该避免冲突,就像TCP的ephemeral port;

当前面的这个消息发送给Server时,它和异步的π逻辑是一样的,就是Client发送给Server一个操作请求,同时给了它一个name/channel (from),服务端可以向这个name/channel发送结果,这样就『模拟』了一个异步函数或者RPC过程。

这个from路径可以是一次性的,在返回之后这个路径就『消失』了,和前面说的reduction之后表达式消失了一样;因为它象input prefix一样是接受消息的,所以称为Sink;Sink的反义词是Source,后面会遇到。

from可以同时是一个replication。比如可以接受GET,返回一下请求的参数之类。可能功能上没什么意义,如果它仅仅是一个一次性的Sink,生命周期仅限于一个request/response消息来回的过程。


但是它的生命周期可能是更长的,比如,服务端返回的并不是一个JSON对象,而是一个Stream,一个Object Stream或者一个Binary Chunk Stream,或者混合,看协议怎么设计。

这个时候这个from路径表示的资源就是一个Stream Sink了,即可以接收多个Message,那它需要表述的信息就丰富很多,比如可以有进度、速度等等。这个时候它兼有replication的服务能力,接受Restful method操作就更有意义。


更复杂的情况例子。

比如一个HTTP Post/Put/Patch,是需要upload一个stream的。

我们会发现HTTP的设计不是原子化的,它的内部实际上是先发出请求,等待了Server端应答100 Continue,然后继续上传内容的。

在RP里,这些语义被扁平化了。Post/Put/Patch如果需要上传流,Server端立刻返回一个即时创建的Sink Path。比如:

Client请求:

{
    to: '/files',
    from: '/requests/123-456-789',
    method: 'POST',
    ...
}

Server回答:

{
    to: '/requests/123-456-789',
    status: 100,
    sink: '/files/#/sinks/3223a6f3'
}

在Server的回答中,它即时分配了一个sink;之后客户端可以陆续向这个sink发送消息,构成一个stream。

显式创建一个Sink标识,一方面可以简化routing,另一方面,它更符合π的input prefix设计,即使用一个独立的name/channel完成一个独立计算任务;从流的意义上来说,这个input prefix可以使用多次,直到遇到EOF/Null-terminator后消失。

这里有趣的地方是,在Client一端的/requests/123-456-789,它是这个stream的Source标识。

它必须同时是一个replication,WHY?因为实际使用中必然会有取消流或者流控的需求,那服务端直接考虑操作这个资源就可以了,比如:

{
  to: `/requests/123-456-789`,
  method: 'PATCH',
  body: {
    flow: false
  }
}

相当于暂停这个流。

如果这个流暂停了。在一个良好的实现下,在应用层应该类似把request实现成了stream.Writable,这样在应用层应该考虑出现drain事件时才会继续向stream写入。

这是什么?这就是π里的output prefix,对吧,消息的发出可以block一个进程继续执行,直到消息发出为止。

虽然在π里常见的是没有buffer的情况,output prefix和input prefix直接reduce成一个新的表达式;而在实际程序中,buffer总是要用到的,但buffer也一定是有限空间的,最终buffer满了后output prefix会发生的。

异步编程和面向通讯的编程一定是这样的所谓Lazy的,只是在很多语言里实用producer-consumer模式实现,需要用很重的类和pattern;IMHO,在一个良好支持并发/异步的语言中,这个东西越轻越好,node.js里的emitter, stream, callback都是良好设计的典范。


总结:

  1. 区分Sink和Replication很重要,这是两种完全不同的职责;
  2. Sink不接受有动词的消息;Replication只接受有动词的消息;一个资源标识可以只有其中一个职责,也可以两者兼具;
  3. Stream的Source/Sink都需要独立和唯一的资源标识,更能体现π里的name/channel的含义;也大大简化编程和错误处理,例如在Sink一方已经抛弃了Stream,在Source一方还在发送,你会发现如果不独立建立Stream Sink这时不容易处理得即健壮又有效率;

设计哲学上,单向的Message Passing是底层;Request/Response,Stream,Stream Control,都是上层;但无论哪一层,基于路径的资源标识都是可用的,因为在π里,一切皆name,一切name皆channel,这就是Restful里的URI的真正含义,在RP里发挥到极致。


Alan Kay在直觉上解释了OO的本质是Message Passing,而Robin Milner在π里给出了最小化的数学定义,我觉得自己不可能比两个图灵奖获得者加起来更聪明了,就躺倒接受先贤先圣的理念就可以了,希望没有误读。

https://segmentfault.com/a/1190000022305924

赞(0)
未经允许不得转载:ITyet » π-calculus与资源模型设计
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址