Think Stitch
PRINCIPIA  最近の更新


並行プログラミング言語 4:改名

並行プログラミング言語に改名(rename)を追加します。 改名があるとプロセスのインターフェイスを変えられるので,プロセスを再利用できるようになります。場合によってはプロセスパラメータでインターフェイスを指定する(使用するイベントとチャネルを渡す)よりも便利なことがあります。

過去の記事は以下のとおりです。

改名の構文

改名の構文を以下のように定めます。

(rename 改名連想リスト プロセス式)

改名は改名連想リストで指定します。改名連想リストは元のイベントと,改名先イベントのペアのリストです。 改名連想リストは評価されるものとします。 例えばイベント a を a1 に,イベント b を b1 に改名する場合は次のように指定します:

(rename (list (cons a a1) (cons b b1)) P)

バッククオート記法を使えばもう少し見やすいかもしれません。

(rename `((,a . ,a1) (,b . ,b1)) P)

例えば次のように定義したプロセスは (b b c) とイベントを発生させることになります:

(rename `((,a . ,b))
  (! a (! b (! c SKIP))))

チャネルの改名をしたい場合は,とりあえず各チャネルイベントを指定することにします(面倒ですけど)。

(define-channel ch  '(0 1 2))
(define-channel chx '(0 1 2))

(rename `((,(ch 0) . ,(chx 0))
          (,(ch 1) . ,(chx 1))
          (,(ch 2) . ,(chx 2)))
  P)

チャネルに属するチャネルイベントのリストは (lookup-chev-list ch) で取得できます。 また (channel-event-arg e) でチャネルイベントからチャネルの引数を取り出すことができます。 そこで上の改名連想リストは次のように自動的に作ることもできます:

(define (rename-channel ch1 ch2)
  (map (lambda (chev)
         (cons chev
               (ch2 (channel-event-arg chev))))
       (lookup-chev-list ch1)))

もし ch1 の定義域が ch2 の定義域に含まれていなければエラー(out of domain)になります。

チャネルイベントを個別に指定するのですから当然ですが,チャネルの定義域の中で一部だけを改名することもできます:

(rename `((,(ch 1) . ,a)) P)

対応するのは1対1の改名だけです。理由については csp-par の修正部分で一部説明します。

改名に対する CSP カーネルのシステムコール

改名に対応するため CSP の実行カーネルに専用のシステムコール csp-rename を用意します。

(csp-rename rename-alist thunk)

rename-alistは改名連想リストそのまま,thunkはプロセスに対応する引数なしの手続きです。

expand-process の拡張

プロセス定義マクロ define-process で使用するヘルパ expand-process の修正は1カ所だけです。 ご覧のとおり,システムコール csp-rename の呼び出しに単純に置き換えるだけです。

(define (expand-process pexpr)
  (match pexpr
    ...
    (('rename rename-alist process)
     `(csp-rename ,rename-alist
                  (lambda ()
                    ,(expand-process process))))
    ...))

expand-process-in-alt は修正しません。つまり alt の引数として直接に改名されたプロセスを書くことはできません。 これは rename の引数であるプロセスの中を見てみないと同期リストが作れないからです(CSP の教科書でいうところの「ガードされたプロセス」であればなんとかできるはずだと思います)。

CSP カーネルの修正と csp-rename の実装

改名のためにカーネルを以下のように修正します。

レコード process

まず改名の情報を記録するために,プロセスコントロールブロック(PCB)に改名の情報を格納するためのフィールド rename-map を追加します。 改名はネストする可能性があるので,指定された改名連想リストをリストにして記録しておくことにします。

(define-record-type process make-process #t
  (state)         ; running ready wait-for-sync wait-for-children omega
  parent
  (children)      ; leaf: #f, node: list of child processes
  (sync)          ; leaf: event-cont-alist, node: sync-list
  (cont)
  (rename-map))   ; ★ 追加

改名システムコール csp-rename

システムコール csp-rename は指定された改名連想リストを現在までのものに追加します。 これは関数 extend-rename-map によります。 つづいて thunk を呼び出し,プロセスの実行を継続します。

(define (csp-rename rename-alist thunk)
  (process-rename-map-set!
   current-process
   (extend-rename-map rename-alist
                      (process-rename-map current-process)))
  (thunk))

extend-rename-map

rename-map は単純に連想リストのリストなので,cons するだけです。

(define (extend-rename-map rename-alist rename-map)
  (cons rename-alist rename-map))

csp-alt の修正

csp-alt を修正します。 おおまかにいうと,同期するかどうかを判定するときに rename-map によってイベントを改名し,改名後のイベントで同期判定を行うようにします。 やることは単純なのですが,少しやっかいなことがあります。

(define (csp-alt sync-list)
  (let ((rename-map (process-rename-map current-process))) ; ★1
    (let loop ((xs sync-list))
      (if (pair? xs)
          (let ((event (caar xs))
                (proc (cdar xs)))
            (let ((e (effective-event rename-map event))) ; ★2
              (let ((ps (find-signaling-processes e)))    ; ★3
                (if ps
                    (begin
                      (set! trace (cons e trace))
                      (release-processes e ps)
                      (process-state-set! current-process 'ready)
                      (process-cont-set! current-process (lambda () (proc event))) ; ★4
                      (set! ready-queue (cons current-process ready-queue))
                      (sched))
                    (loop (cdr xs))))))
          (begin
            (process-state-set! current-process 'wait-for-sync)
            (process-sync-set! current-process
                               (rename-sync-list rename-map sync-list)) ; ★5
            (sched))))))

★1. まず rename-map を取り出しておきます。

★2. 同期リストからイベントを取り出したら関数 effective-event で改名先のイベントを求めます。改名されない場合は元のイベントがそのまま戻ってきます。

★3. 改名後のイベントを使って同期判定を行います。

★4. もし同期した場合は改名後のイベントでトレースを記録し,他のプロセスも解放しますが,呼び出したプロセスだけには改名前のイベントを渡します。なぜかというと,rename の引数であるプロセスは改名されていることなど知らないからです。これは指定されたイベントがチャネルイベントであったときに重要です。チャネル受信の継続 cont は受け取ったチャネルイベントから引数を取り出すからです。

★5. この csp-alt の呼び出しで同期しなかった場合は同期リストを保存して待ち状態に入るわけですが,いままでのように単純に同期リストを保存するわけにいきません。同期リストは改名前のイベントで作られており,かつ他のプロセスはこのプロセスの改名のことなど知らないからです。そこで関数 rename-sync-list を使って,同期リストそのものを改名してから保存します。

effective-event

関数 effective-event は rename-map を使って指定されたイベントを改名します。

改名はネストする場合があります。例えば次の例を見てください。

(rename `((,a . ,x) (,u . ,w))
  (rename `((c . ,u) (,d . ,z))
    P))

この場合,a -> x, d -> z, c -> w となるはずです。

必要な処理はつぎのようになります。rename-map が (r0 r1 r2 ...) となっていた場合:

0. rename-map が空ならば元のイベントを返します。

1. r0 から順に調べていきます。

2. もし対応するイベントがなければ元のイベントを返します。

3. もし対応するイベント e が rk で見つかったら,さらに rk+1 から再度検索します。

(define (effective-event rename-map event)
  (if (null? rename-map)
      event
      (let ((p (assq event (car rename-map))))
        (if p
            (effective-event (cdr rename-map) (cdr p))
            (effective-event (cdr rename-map) event)))))

rename-sync-list

関数 rename-sync-list は csp-alt に渡された同期リストを改名します。 同期リストの要素はイベントと継続のペア (event . cont) です。 継続 cont はイベントを引数としてとります。

イベントの部分を改名するのは当然ですが,継続の部分にも変換が必要です。 カーネルは同期の際に同期したイベントを継続に渡してくれますけど,これは改名後のイベントです。 しかし継続に対応するプロセスは改名のことを知りませんから改名前のイベントを渡さなければならないからです。

(define (rename-sync-list rename-map sync-list)
  (map (lambda (p)
         (let ((event (car p))
               (cont (cdr p)))
           (let ((e (effective-event rename-map event)))
             (if (eq? e event)
                 p
                 (cons e
                       (lambda (dummy) (cont event)))))))
       sync-list))

csp-par の修正

CSP の理論では並行合成されたプロセスは逐次プロセスと同じ単なる1つのプロセスとして扱うことができます。しかし実装系である CSP カーネルでは par はプロセスの生成としての意味を持っていて,合成されたプロセスというものが存在するわけではありません。(休眠している PCB ノードはありますが。)すると次の例のように並行合成された結果としてのプロセスを改名した場合をどのように処理するかということが問題になります。P, Q それぞれは独立して動いており,par に対応するプロセスは休眠していて,したがって改名の対象となる同期リストを出すわけではないからです。

(rename R (par X P Q))

ここで有用な代数的規則があります。イベントの改名を表す数学的な関数を f とします。 もし f が1対1対応(one-to-one, injective)ならば,次の式が成り立ちます。 (Theory and Practice of Concurrency, p.88)

\[ f(P\ \underset{X}{||}\ Q) = f(P) \underset{f(X)}{||} f(Q) \]

つまり,並行合成された結果のプロセスを改名するには,各子プロセスを改名して,かつ同期リストも改名しておけばよいということです。

なぜ1対1でなければならないかというと,次のような場合があるからです:

(rename `((,a . ,c) (,b . ,c))
  (par (list a b) P Q))

イベント a, b ともに c に改名されるので,多対1の対応です。 もし機械的に上の代数規則を当てはめると次のようになるでしょう:

(par (list c)
  (rename `((,a . ,c) (,b . ,c)) P)
  (rename `((,a . ,c) (,b . ,c)) Q))

これだとプロセス P がイベント a だけを提示し,プロセス Q がイベント b だけを提示した場合に,本来ないはずの同期が発生してしまいます。

話を実装に戻します。上の代数規則を使うには csp-par を次のように修正します。

(define (csp-par sync-list thunk-list)
  (let ((rename-map (process-rename-map current-process))) ; ★1
    (let ((ps
           (map (lambda (thunk)
                  (make-process
                   'ready               ; state
                   current-process      ; parent
                   #f                   ; children (leaf: #f)
                   '()                  ; sync
                   thunk                ; cont
                   rename-map))         ; rename-map ★2
                thunk-list)))
      (set! ready-queue (append ps ready-queue))
      (process-state-set! current-process 'wait-for-children)
      (process-children-set! current-process ps)
      (process-sync-set! current-process
                         (map (lambda (e)
                                (effective-event rename-map e))
                              sync-list)) ; ★3
      (sched))))

★1. 親プロセスの rename-map を取り出しておきます。

★2. 子プロセスは親の rename-map を継承するようにします。つまり f(P), f(Q) 等とするということです。

★3. 同期リストを改名します。f(X) に対応します。

start-process の修正

カーネルの起動手続き start-process で rename-map の初期値として空リストを指定するようにします。

(define (start-process thunk)
  (let ((p (make-process
            'running               ; state
            #f                     ; parent (root: #f)
            #f                     ; children (leaf: #f)
            '()                    ; sync
            thunk                  ; cont
            '())))                 ; rename-map ★
    (set! root-process p)
    (set! current-process p)
    (set! ready-queue '())
    (set! trace '())
    (thunk)))

修正は以上です。

実行例

実際に動かしてみます。

単純な例

単純にイベント a を b に改名します。

(define-process P
  (rename `((,a . ,b))
    (! a SKIP)))
(start-process P)
(map de (reverse trace))
=> (b)

改名されるイベントとされないイベント

(define-process P
  (rename `((,b . ,d))
    (! a (! b (! c SKIP)))))
(start-process P)
(map de (reverse trace))
=> (a d c)

チャネルイベントの改名

(define-channel ch '(0 1 2))

(define-process P
  (rename `((,b . ,(ch 1)))
    (! a (! b (! c SKIP)))))
(start-process P)
(map de (reverse trace))
=> (a (ch 1) c)

チャネルイベントの改名 2

(define-process P
  (rename `((,(ch 0) . ,a)
            (,(ch 1) . ,b)
            (,(ch 2) . ,c))
    (? ch (x) SKIP)))

(define-process Q
  (! b SKIP))

(define-process R
  (par (list a b c) P Q))
(start-process P)
(map de (reverse trace))
=> (b)

チャネルの改名

(define-channel chx '(0 1 2 3 4))

(define-process P
  (rename (rename-channel ch chx)
    (! (ch 2) SKIP)))
(start-process P)
(map de (reverse trace))
=> ((chx 2))

交換

(define-process P
  (rename `((,a . ,b) (,b . ,a))
    (! a (! b SKIP))))
(start-process P)
(map de (reverse trace))
=> (b a)

2重の改名 1

(define-process P
  (rename `((,a . ,b))
    (rename `((,c . ,d))
      (! a (! b (! c (! d SKIP)))))))
(start-process P)
(map de (reverse trace))
=> (b b d d)

2重の改名 2

(define-process P
  (rename `((,a . ,b))
    (rename `((,b . ,a))
      (! a (! b (! c (! d SKIP)))))))
(start-process P)
(map de (reverse trace))
=> (b b c d)

2重の改名 3

(define-process P
  (rename `((,a . ,b) (,f . ,g))
    (rename `((,c . ,d) (,e . ,f))
      (! a (! b (! c (! d (! e (! f SKIP)))))))))
(start-process P)
(map de (reverse trace))
=> (b b d d g g)

合成プロセスの改名

(define-process P
  (rename `((,a . ,c))
    (par (list a b)
      (! a SKIP)
      (! a SKIP))))

(define-process Q
  (par (list c)
    P
    (! c SKIP)))
(start-process P)
(map de (reverse trace))
=> (c)
(start-process Q)
(map de (reverse trace))
=> (c)

プロセス再利用の例

1-place バッファを改名して2つ連結します。

(define D '(0 1 2))
(define-channel in D)
(define-channel out D)
(define-channel mid D)

(define-process P
  (? in (x) (! (out x) SKIP)))

(define-process Q
  (par (list mid)
    (rename (rename-channel out mid) P)
    (rename (rename-channel in mid) P)))

(define-process S
  (par (list in)
    (! (in 1) SKIP)
    Q))
(start-process S)
(map de (reverse trace))
=> ((in 1) (mid 1) (out 1))

コメント

結構たいへんな修正でした。

多対1がだめなら1対多はどうなんだということが気になります。 多対1は抽象化の意味があり,どちらかというと実装よりも検査で使うことが多いと思います。 1対多もあまり応用は見かけません。 検査では 条件変数のモデルのところで使いました。 離散的な時間のモデルやπ計算との関係で使われているのを見たような気がします。 実装するとなると,csp-alt で複数の改名の可能性を調べるということになるでしょうか。 先に理論的に整合性を調べる必要がありそうです。

2014/04/05
© 2013,2014,2015 PRINCIPIA Limited