Think Stitch
PRINCIPIA  最近の更新


並行プログラミング言語 3:ガード

引き続き,並行プログラミング言語を拡張してみたいと思います。今日はガードを追加します。尚,過去の記事は以下のとおりです。

ガード

ここでいうガードとは,チャネルからの受信を行う際に受信を行うかどうかを決定する条件のことです。前回追加したチャネル受信の構文では,送信された値がチャネルの定義域に入っていさえすれば必ず受信されました。ガードを使うと,条件を満たす場合だけ受信を行うように指定することができます。

チャネル受信の構文を以下のように拡張します。

(? チャネル (パラメータ) [ガード] プロセス式)

パラメータの後にガードを置けるようにします。ガードはオプションです。もし指定されていない場合は常に真である条件,つまり #t が指定されているものと見なされます。

ガードではスコープ内にある変数を参照することができます。具体的にはプロセスパラメータとチャネル受信のパラメータということになります。ガードが指定されているチャネル受信のパラメータも参照することができます。したがって,まさに受信しようとしている値によって受信するかどうかを決定することができます。

SyncStitch のユーザガイドでも書きましたけれども,ガードが受信値を参照できるというのは少し奇妙な感じがするかもしれません。受信するかどうかを受信値によって決定し,しかもガードの評価結果が偽ならば受信しないというのですから。しかし実際には何のトリックもありません。前回見たとおり,チャネル受信は複数のイベントからの選択に過ぎません。チャネルの定義域はあらかじめわかっているわけですから,イベントの範囲もわかっています。ガードはこの範囲を限定するだけのことです。ガードを満たす引数に対応するイベントだけを提示するというだけのことです。このあとのマクロを見るとより明らかになると思います。

マクロの変更

ガードを実現するための修正は,マクロに対する2カ所だけです。ガードが指定されていない場合の処理はそのままにして,ガードが指定されている場合のパターンを match に追加します。

ご覧のとおりやっていることは単純で,チャネルに属するすべてのチャネルイベントの中から,関数 filter を使ってガードを満たすものだけを選んでいるだけです。

(define (expand-process pexpr)
  (match pexpr
    ...
    (('? ch (z) guard pexpr2)
     (let ((e (gensym)))
       `(let ((proc
               (lambda (,e)
                 (let ((,z (channel-event-arg ,e)))
                   ,(expand-process pexpr2)))))
          (csp-alt
           (map (lambda (chev) (cons chev proc))
                (filter (lambda (,e)
                          (let ((,z (channel-event-arg ,e)))
                            ,guard))
                        (lookup-chev-list ,ch)))))))
    ...))

選択 alt 式の中の受信についても同様です。

(define (expand-process-in-alt pexpr)
  (match pexpr
    ...
    (('? ch (z) guard pexpr2)
     (let ((e (gensym)))
       `(let ((proc
               (lambda (,e)
                 (let ((,z (channel-event-arg ,e)))
                   ,(expand-process pexpr2)))))
          (map (lambda (chev) (cons chev proc))
               (filter (lambda (,e)
                          (let ((,z (channel-event-arg ,e)))
                            ,guard))
                       (lookup-chev-list ,ch))))))
    ...))

実行例 1

まずガードのない例を準備します。

(define-channel ch '(0 1 2 3 4 5))

(define-process P
  (! (ch 2) SKIP))

(define-process Q
  (? ch (x) SKIP))

(define-process R
  (par (list ch) P Q))
(begin
  (start-process R)
  (map de (reverse trace)))
=> ((ch 2))

プロセス Q にガード (< x 4) をつけてみます。プロセス P が送信する値 2 はガードを満たしますから受信は行われます。

(define-process Q
  (? ch (x) (< x 4) SKIP))
(begin
  (start-process R)
  (map de (reverse trace)))
=> ((ch 2))

こんどはガードを (>= x 4) としてみます。ガードは成立しないので同期せず,デッドロックします。

(define-process Q
  (? ch (x) (>= x 4) SKIP))
(start-process R)
=> *** ERROR: sched "deadlock"

(map de (reverse trace))
=> ()

これは以下のように if 文で場合分けをしたものとは異なります。なぜなら,こちらの場合は受信が行われているからです。

(define-process Q
  (? ch (x) (>= x 4) SKIP))

(define-process Q
  (? ch (x)
     (if (< x 4)
         STOP
         SKIP)))
(start-process R)
=> *** ERROR: sched "deadlock"

(map de (reverse trace))
=> ((ch 2))

実行例 2: プロセスパラメータの参照

ガードの中でプロセスパラメータを参照する場合を見てみます。プロセス P はチャネル ch に対して順に 0, 1, 3 を送ろうとします。これに対してプロセス Q は次に受信すべき値をプロセスパラメータに保持していて,ガードで受信値と比較します。

(define-process P
  (! (ch 0) (! (ch 1) (! (ch 3) SKIP))))

(define-process (Q x)
  (? ch (z) (= x z)
     (Q (+ x 1))))

(define-process R
  (par (list ch) P (Q 0)))

(ch 0), (ch 1) までは同期しますが,(ch 3) はプロセス Q が拒否するので発生しません。

(start-process R)
=> *** ERROR: sched "deadlock"

(map de (reverse trace))
=> ((ch 0) (ch 1))

実行例 3: 場合分け

排他的で網羅的なガードの集合を使うと場合分けを表すことができます。以下の例ではチャネル in から受信した値に応じて出力先チャネルを切り替えています。

(define-event done)
(define-channel in '(0 1 2 3 4 5))
(define-channel out '(0 1 2 3 4 5))
(define-channel out2 '(0 1 2 3 4 5))

(define-process (P n)
  (if (= n 6)
      (! done SKIP)
      (! (in n) (P (+ n 1)))))

(define-process Q
  (alt
    (! done SKIP)
    (? in (x) (< x 4)
       (! (out x) Q))
    (? in (x) (>= x 4)
       (! (out2 x) Q))))

(define-process R
  (par (list done in) (P 0) Q))
(begin
  (start-process R)
  (map de (reverse trace)))
=> ((in 0) (out 0) (in 1) (out 1)
    (in 2) (out 2) (in 3) (out 3)
    (in 4) (out2 4) (in 5) (out2 5)
    done)

この場合は以下の if 文を使ったプロセスと同じ振る舞いになります。

(define-process Q
  (alt
    (! done SKIP)
    (? in (x)
       (if (< x 4)
           (! (out x) Q)
           (! (out2 x) Q)))))
2014/01/18
© 2013,2014,2015 PRINCIPIA Limited