编程语言

SICP笔记（八）

并发

前面，我们引入了赋值操作，我们有了模拟对象状态的能力，可以描述时间的流逝；同时也失去了引用透明性，在处理并发问题时，也变得更加复杂。

在并发系统中，几个进程可能共享一个公共的状态变量，并发操作进行的时候，事件顺序的非确定性可能使并发操作交错进行，导致一些意想不到的结果。问题来源的关键就是在同一个时刻可能有不止一个进程试图操作共享状态。我们可以对并发操作增加一些限制，以便其正确执行。一种可行的策略是我们可以规定，任何时刻都不允许两个修改任意共享状态变量的操作同时发生。这个规定就很严格了，它可以保证并发操作正确地执行，不过有些过度了，造成资源浪费，低效率。我们可以更宽松地规定，保证并发系统计算的结果与按照某种顺序运行的各个进程计算的结果一致。如此一来，只需控制并发系统中的关键部分的正确执行便可保证并发系统的正确性，提高了计算的效率。
书中通过串行化组(serializer)控制并发操作，串行化创建一些不同的过程集合，并且在任何时刻，在任何一个串行化集合里至多只允许有一个过程的一个执行。串行化组允许集合外的过程并发进行，集合内至多只能有一个执行，保证改变公共状态变量的操作不会交错进行。串行化组的实现是又基于更基本的互斥元(mutex)。一个互斥元可以被获取或被释放，互斥元一旦被获取，对于这个互斥元的任何其他获取操作都必须等到该互斥元被释放之后。每个串行化组都关联着一个互斥元，这就能保证，由此串行化组产生的过程集合中至多只有一个执行。

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
;;; Serializer
(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire)
        (let ((val (apply p args)))
          (mutex 'release)
          val))
      serialized-p)))
      
(define (make-mutex)
  (let ((cell (list false)))
    (define (the-mutex m)
      (cond ((eq? m 'acquire)
             (if (test-and-set! cell)
                 (the-mutex 'acquire)))
            ((eq? m 'release)
             (clear! cell))))
    the-mutex))
    
(define (clear! cell)
  (set-car! cell false))
  
(define (test-and-set! cell)
  (if (car cell)
      true
      (begin (set-car! cell true)
             false)))

注意，test-and-set!必须是一个原子操作，保证不会被打断，一旦开始便运行至结束。互斥元的关键便是中的循环，一旦被获取，便不断地检查，获取，检查，获取…这大概是死循环的一个用处吧。
另外，函数式编程语言由于多个线程之间不共享状态，不会造成资源争用(Race condition)，也就不需要用锁来保护可变状态，也就不会出现死锁，这样可以更好地并发起来，在并发问题上有天然的优势。

流

引进赋值是为了模拟时间，赋值给我们带来了很多复杂的问题，流(stream)从另外一种连续的角度模拟时间，可以降低模拟过程中的复杂性。
流的角度中，以数学函数的观点，将变量随时间改变的行为看成与时间有关的函数关系，如果关注变化的整个过程，就不需要强调个别的变化，整个过程中函数关系本身并没有改变。与通过赋值改变状态变量的值以模拟时间的流逝的角度相比，流并没有时间，流强调整个过程的连续性。
流是一种数据结构，与序对类似，不过流采用了延时求值的技术(delayed evaluation)，流是一个初始值和一个延时对象的序对，流只会计算需要的部分。流通过延时求值将事件发生的逻辑顺序和实际顺序分开了，使用前面序列作为约定界面的技术和流进行编程，即有姿势，又有效率。

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
31
;;; Stream

;; delay
(define (memo-proc proc)
  (let ((already-run? false)
        (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

(define-syntax delay
  (syntax-rules ()
    ((_ exp) (memo-proc (lambda () exp)))))

;; force    
(define (force delayed-object)
  (delayed-object))


(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

(define (stream-car stream)
  (car stream))

(define (stream-cdr stream)
  (force (cdr stream)))

延时求值就是简单地对表达式套上一个无参的lambda函数，用lambda函数在编译器的眼皮子底下将求值的表达式藏起来了，就是如此短小精悍。此处，我们对delay进行了优化，使其有记忆属性，无需重复求值，提升了效率。注意memo-proc中使用了赋值操作，不过此处是一次性的赋值操作，一旦设定了值，便不会改变。在cons-stream和delay的实现中，根据我们的求值模型，我们会现对参数自动求值，因此采用特殊形式宏定义。
流采用了延时求值，因此流可以用自己定义自己，产生无穷流。我们可以用无时间的流模拟状态，在交互式系统中，传入一个流，输出一个流，这就使系统看起来有了“时间”。赋值可以增强系统的模块性，流也可以。流提供了一个没有时间的角度，但流并不能完美地解决问题，引入流我们有了两类过程，常规的过程和使用延时对象为参数的过程，这让我们必须时刻意识到这一点，以免造成混乱。当然，我们可以统一使用正则序，将所有对象都定义成延时对象，但是这个特性却在迭代过程中表现不佳，我们希望对参数求值，但得到的却是一个个“诺言”。
变动性和延时求值在程序设计语言中结合的并不好。A grand unification has yet to emerge!

参考资料：
什么是函数式编程思维？
SICP cons-stream

习题解答：传送门