Think Stitch
PRINCIPIA  最近の更新


並行プログラミング言語 5:隠蔽

並行プログラミング言語に隠蔽を追加します。

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

実装における隠蔽の意味

隠蔽は並行システムにおいて理論的にも概念的にも重要な役割を果たします。しかし実装の世界では必ずしも機能的に必要というわけではありません。

例えば下図のように2つのコンポーネント P と Q を合成してサブシステム S を作るという状況は並行システムの設計において頻繁に行われます。設計としては P と Q の間で行われる相互作用に関わるイベント b は隠蔽されていると考えます。サブシステム S の内部イベントであるということです。しかし実装ではイベント b をそのままにしておいてもそのこと自体が問題というわけではありません。もちろんイベント b が他でも使われているということは除いての話です。

ただ,このままではイベント b を外から観測することができますし,やろうと思えば同期をしてサブシステムの振る舞いに影響を与えることもできます。これは一般には問題を起こすでしょう。ただ観測をするだけとしても,サブシステム S 内部の設計が変われば,イベント b の観測に依存している部分は動かなくなるかもしれません。

そこで実装においてもイベント b を隠蔽するようにすれば,このような問題を避けることができます。その意味で,実装における CSP の隠蔽(concealment)はオブジェクト指向でいう情報隠蔽(encapsulation)に近いと思います。

隠蔽の構文

隠蔽の構文を以下のように定めます。

(hide 隠蔽するイベントのリスト プロセス式)

チャネルを隠蔽する場合は,改名のときと同じで,個別にチャネルイベントを指定するか,あるいは関数 (lookup-chev-list ch) を使うことにします。

隠蔽に対する CSP カーネルのシステムコール

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

(csp-hide event-list thunk)

event-list は隠蔽するイベントのリスト,thunk はプロセスに対応する引数なしの手続きです。

expand-process の拡張

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

(define (expand-process pexpr)
  (match pexpr
    ...
    (('hide event-list process)
     `(csp-hide ,event-list
                (lambda ()
                  ,(expand-process process))))
    ...))

並行合成や改名と同様,隠蔽も alt の引数として直接に改名されたプロセスを書くことはできません。したがって expand-process-in-alt に修正はありません。

csp-hide の実装

理論において隠蔽とはイベントを内部イベント τ に置き換えることでした。しかし実装ではそう簡単にはいきません。なぜかというと実装では並行合成したプロセスが1つのプロセスになるわけではないからです。並行合成

\[ P\ \underset{X}{||}\ Q \]

において,P, Q それぞれの隠蔽すべきイベントを τ に置き換えてしまったら,同期しなくなってしまうからです。別のいい方をすれば,隠蔽は並行合成に対して分配法則を満たさないということです。

実装の隠蔽で必要なことは,プロセスの振る舞いが変わらないように各イベントの区別を残しつつ,かつそれらが外から見えないようにすることです。そこで隠蔽すべき各イベントに対応する“内部でしか見えない”イベントを用意して,τ の代わりにこれらに置き換えると考えます。

すると結局,隠蔽は置き換える先のイベントがちょっと特殊であることを除けば改名とまったく同じだということになります。1対1の改名の場合は並行合成に対して分配法則が成り立ちました。

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

この改名 f で見えないイベントを指定すると,並行合成の子プロセス P, Q は改名 f を継承しますから,P も Q も見えないけど区別できるイベントを発生させて同期することができます。そしてこれらのイベントを知らない外のプロセスは観測も,もちろん同期もすることができないというわけです。

具体的な話に入りましょう。実装ではイベントは2種類ありました。アトミックイベントとチャネルイベントです。アトミックイベントはシンボルで,チャネルイベントはレコードでした。実際にところ,同期の判定では eq? を使っているだけなので,同値判定ができればどのようなオブジェクトもイベントとして使うことができます。

同値判定ができて所有者以外が手に入れることができないオブジェクトといえば,インターンされていないシンボルがぴったりです。ペアでもいいのですけど,区別する名前が自動的につくという点でシンボルの方が少し楽です。幸い Gauche にはインターンされていないシンボルと gensym がありますので,これを使うことにします。

見えないイベントを生成する方法が決まってしまえば,csp-hide は改名連想リストを作って csp-rename に渡すだけになります。

(define (csp-hide event-list thunk)
  (csp-rename (map (lambda (e)
                     (cons e (gensym (event-name e))))
                   event-list)
              thunk))

ここでちょっと贅沢をして,gensym で生成するイベントのプリフィックスに元のイベントの名前を指定しておくことにします。チャネルイベントの場合は ch.a のような形にします。こうしておくとデバッグのときにどのイベントが隠蔽されたのかわかるからです。

(define (event-name e)
  (if (channel-event? e)
      (format #f "~A.~A."
              (channel-event-name e)
              (channel-event-arg e))
      (format #f "~A." e)))

隠蔽の実装はこれだけです。

実行例

実際に動かしてみます。

単純な例

イベント a を隠蔽します。

(define-process P
  (hide (list a)
    (! a (! b SKIP))))
(start-process P)
(map de (reverse trace))
=> (#:a.446 b)

隠蔽したイベントとの同期

隠蔽したイベントと同期できないことを確認します。

(define-process P
  (par (list a)
    (! a SKIP)
    (hide (list a)
      (! a SKIP))))
(start-process P)
(map de (reverse trace))
=> *** ERROR: sched "deadlock"

並行プロセスの隠蔽

並行合成したプロセスを隠蔽してみます。

(define-process P
  (hide (list c)
    (par (list c)
      (! a (! c SKIP))
      (! c (! b SKIP)))))
(start-process P)
(map de (reverse trace))
=> (a #:c.468 b)

チャネルの隠蔽

チャネルの隠蔽は,すべてのチャネルイベントの取得する関数 lookup-chev-list を使うと楽にできます。

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

(define-process P
  (hide (lookup-chev-list ch)
    (? ch (x)
       (! (ch2 x) SKIP))))
(start-process P)
(map de (reverse trace))
=> (#:ch.0.479 (ch2 0))

理論的には最初のイベントは非決定的に選ばれますが,実装では csp-alt に渡された同期リストの中で最初に同期したものが選ばれます。この場合は ch.0 ということになります。内部イベントの名前を工夫したおかげで見れば分かるようになっています。内部イベントが表示されているので,正確にはこれはトレースではないですね^^;。

改名,隠蔽,並行合成

最後に改名,隠蔽,並行合成をすべて組み合わせた例を見てみます。

(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
  (hide (lookup-chev-list mid)
    (par (lookup-chev-list mid)
      (rename (rename-channel out mid) P)
      (rename (rename-channel in mid) P))))

(define-process R
  (par (lookup-chev-list in)
    (! (in 2) SKIP)
    Q))
(start-process R)
(map de (reverse trace))
=> ((in 2) #:mid.2.503 (out 2))

let や hpar が欲しくなりますね。

コメント

この隠蔽の実装にはちょっと無駄なところがあります。内部イベントの同期判定を行うときにも,ふつうのイベントと同じようにプロセス木を根から探索していますが,内部イベントが同期する可能性があるのは隠蔽を行ったプロセス木の部分木の中だけです。そこで探索を隠蔽のところから始めるという効率化を行うことができます。そのためには内部イベントと部分木を関連づける必要があります。

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