1

Scala で「CSP」のパーサーとセマンティックを実装しようとしています。私はすでにパーサーを実装しており、現在は言語のセマンティック部分の作業で忙しくしています。私は並行システムと非決定論的選択の世界にまったく慣れていません。ここに私の質問があります：

ここで説明されているように、「非決定論的選択」と「インターフェース並列」を実装したいと考えて います。

手順を理解できるようになりましたが、非決定論に関しては頭をまっすぐにすることができません。これを Scala で実装するには、適切なデータ型が必要です。すべてのプロセスをリストに入れてから、リストをランダム化し、変更されたリストから要素を選択することを考えています。しかし、それは私にとってそれほど非決定論的に聞こえません。

以前にこの問題を経験したことがあり、優れたアルゴリズムを知っている人はいますか?

4

2 に答える 2

1

CSP に関する私の非常に限定的な理解は、CSP 演算子が次の Haskell 型に対応するということです。

-- Prefixing corresponds to functions
x :: A
P :: B
x -> P :: A -> C

-- Choice corresponds to product
P :: A
Q :: B
P □ Q :: (A, B)

-- Non-determinism corresponds to sum
-- I don't know how to make the non-determinism symbol, so I use (△)
P :: A
Q :: B
(P △ B) :: Either A B

次に、代数的同型を使用して CSP 式を削減できます。ウィキペディアの例を使用します。

(coin -> STOP) □ (card -> STOP)

-- translates to the following Haskell type:
(coin -> Stop, card Stop)

-- which is algebraically isomorphic to:
(Either coin card -> Stop)

-- translates in reverse back to CSP:
coin □ card -> STOP

また、ウィキペディアの例の 1 つが間違っていると思います (または、私が間違っています)。この式は次のように縮小する必要があると思います。

(a -> a -> STOP) □ (a -> b -> STOP)

-- translates to the following Haskell type:
(a -> a -> STOP, a -> b -> STOP)

-- which is algebraically isomorphic to:
a -> Either a b -> STOP

-- translates in reverse back to CSP:
a -> (a △ b) -> STOP

ただし、インターフェイスの並列に相当するものはまだわかりません。エレガントなコンセプトに対応していないようです。

于 2013-06-20T00:19:16.227 に答える