延迟求值和无穷(6)

发表于 2007-08-15 03:14 AM 作者: liuxinyu

5 stream in concurrent programming

上述的延迟求值计算，给出了无穷流模型，这一模型是函数式编程语言解决并发编程的一种有效方案。在针对并发编程的各种思路中，通常有如下解决思路[4]：

共享状态的原子操作(例如，Java/C++)
使用Active Object模式和消息传递(例如，Erlang, SALSA, Symbian)[5]
并发声明(在函数式编程语言种使用stream，例如Oz语言)

其中，最常见的，也是最难的就是第一个方法，这也就是在本文开头种提到的那个问题。这一方法的本质困难在于保持公共数据的一致性。也就是数据的状态改变，和并发竞争的矛盾。
使用函数式方法的好处在于，任何数据都不会被改变。因为函数式编程中无法通过赋值语句改变任何变量的值。所有处理过程都是针对输入数据加以计算，然后把计算结果输出。因此不会出现某个线程在某个未知的时刻，改变其他线程正在处理的数据的情况。所以，根本也就不需要任何诸如锁，信号量等显示同步手段。因此有时称函数式程序设计语言为“无副作用语言”。
那么如何实现并发计算呢？如果一个计算过程都不会改写另一计算过程正在使用的数据，就可以将这两个过程并发执行2。由于函数式语言无副作用，所以大多数计算都可以并发。在lisp方言scheme中，可以使用显示声明future去指定一个计算可以并发进行。在另一些函数式语言中，推断某个计算过程是否可以并发还可以直接交给编译器完成。[7]
如果某个并发计算过程A，需要另外一个并发计算过程B的计算结果，那么当这个结果被计算出来之前，过程A将进入等待状态（例如通过自旋）。如果B计算出的结果是一个流，那么整个计算过程就是就呈现如下的状态：B不断产生新的计算结果，被称为“生产者(producer)”，A不断使用计算结果，被称为“使用者(consumer)”，AB之间使用流进行通信。
由于，A，B并发执行，所以B生产的速度会和A使用的速度可能不一致，为了解决整个问题，延迟求值就可以发挥作用了，由于延迟求值是一种“按需求值(on demanding evaluate)”，所以实际的求值是由A驱动的。

6 Summary

本文给出的延迟求值和无穷流实现是基于C++的，实际上作者试图用C++模拟在函数式语言中的惰性求值，或称“正则序求值”。这种模拟只能实现非常简单的一些应用，一些复杂的应用就无法简单用C++来模拟了。在scheme中，缺省求值是“应用序”的，但是Scheme提供了delay和force去实现，其中一个简单的实现是使用lambda：

代码:

(define (delay exp) 
  (lambda () exp))
 
(define (force delayed-object) 
  (delayed-object))

此后就可以使用delay和force去实现流的构造和引用：

代码:

(define (cons-stream a b) 
  (cons a (delay b)) 
 
(define (stream-car stream) (car stream)) 
(define (stream-cdr stream) (force (cdr stream)))

下面是Scheme中利用无穷流定义的斐波那契数列：

代码:

(define fibs 
  (cons-stream 0 
    (cons-stream 1 
      (add -streams (stream-cdr fibs) 
        fibs))))

在另外一些函数式语言，如Haskell中，所有的函数都是按照正则序调用的，也就是惰性求值的。所以可以直接使用无穷流，下例是Haskell中的斐波那契数列定义：

代码:

fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]

函数式语言采用流的概念将计算机世界的时间和现时世界时间的概念分离开，提供了完全不同的并发计算思路。希望本文能够提供给读者一些额外的想法，在解决实际问题时能有所裨益。

7 Appendix

References

[1] wikipedia, “Lazy evaluation” http://en.wikipedia.org/wiki/Lazy_evaluation
[2] Harold Abelson and Gerald Jay Sussman with Julie Sussman. “Structure and Interpretation of Computer Programs.” second edition. The MIT Press.
[3] Liu Xinyu. “Lambda and High order function.” http://baredog.at.infoseek.co.jp/intl/chn/softdev/book2007/html/essay1/essay1.html
[4] Carlos Varela. “Declarative Concurrency (VRH 4)”. http://www.cs.rpi.edu/academics/courses/fall06/proglang/handouts/Chapter4.pdf
[5] Liu Xinyu. “刀耕火种的繁荣时代”. http://baredog.at.infoseek.co.jp/intl/chn/softdev/book1/essay4.htm
[6] Gamma, Erich; Richard Helm, Ralph Johnson, and John Vlissides. “Design Patterns: Elements of Reusable Object-Oriented Software.”, Addison-Wesley. 1995.
[7] 裘宗燕译Michael Scott. “Programming Language Pragmatics”, Morgen Kaufmann, 2000

*Liu Xinyu
5-2-201, ShiZiPo, Xi, DongZhiMenWai, DongCheng district, Beijing, 200027, P.R.China
Email: liuxinyu95@gmail.com
Tel: +86-1305-196-8666
Fax: N.A.

1 例如：要找出满足2nn + 1 形式(这样的数称为费马数)且不是素数的一个自然数。按照上面的计算模型，就需要先从自然数集合，产生全部的费马数集合，然后再用素数筛子进行过滤，最后取出结果集的第一个元素。
2 这里是指语义上的并发，实际物理上可以采用多处理器，或者调度器

评论总数 0

发表评论

作者为 liuxinyu 的最新文章

论坛存档
< > 十一月 2008
日	一	二	三	四	五	六
26	27	28	29	30	31	1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	1	2	3	4	5	6