UNITY（プログラミング言語）

Theoretical programming language for describing concurrent computations

UNITYは、 K. Mani ChandyとJayadev Misraが著書『Parallel Program Design: A Foundation』のために構築したプログラミング言語です。これは、どこで、いつ、どのようにではなく、何をするかに焦点を当てた理論的な言語です。この言語にはフロー制御の手法がなく、プログラム文は実行中に変更を起こさなくなるまで非決定的に実行されます。これにより、自動操縦や発電所の安全システムなどのプログラムを無期限に実行できるだけでなく、通常は終了するプログラム（ここでは固定点に収束します）も実行できます。

説明

すべての文は代入 であり、 で区切られます#。文は、 、a,b,c := x,y,z、または の形式の複数の代入で構成できます。また、量化された文リスト、a := x || b := y || c := zを持つこともできます。ここで、 x と y は、式 を満たす値の中からランダムに選択されます。量化された代入も同様です。 では、文 は、式を満たすすべてのとのペアに対して同時に実行されます。<# x,y : expression :: statement><|| x,y : expression :: statement >xy

例

バブルソート

隣接する数値を比較し、順序が間違っている場合は入れ替えることで、配列をバブルソートします。期待時間、プロセッサ数、期待作業量を使用します。期待時間しか存在しないのは、常に からランダムに選択されるためです。これは手動で反転することで修正できます。 ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle \Theta (n)}$ k ${\displaystyle \{0,1\}}$k

プログラムバブルソート宣言する n: 整数、 A: 整数の配列 [0..n-1]当初 n = 20 # <|| i : 0 <= i かつ i < n :: A[i] = rand() % 100 >割り当てる <# k : 0 <= k < 2 :: <|| i : i % 2 = k かつ 0 <= i < n - 1 :: A[i], A[i+1] := A[i+1], A[i] A[i] > A[i+1]の場合 >>終わり

ランクソート

ランクソートを使えば、時間内にソートできます。プロセッサと作業が必要です。 ${\displaystyle \Theta (\log n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle \Theta (n^{2})}$

プログラムランクソート宣言する n: 整数、 A,R: 整数の配列 [0..n-1]当初 n = 15 # <|| i : 0 <= i < n :: A[i], R[i] = rand() % 100, i >割り当てる <|| i : 0 <= i < n :: R[i] := <+ j : 0 <= j < n かつ (A[j] < A[i] または (A[j] = A[i] かつ j < i)) :: 1 >> # <|| i : 0 <= i < n :: A[R[i]] := A[i] >終わり

フロイド・ワーシャルアルゴリズム

フロイド・ワーシャル アルゴリズムの全ペア最短経路アルゴリズムを使用して、中間ノードを反復的に含め、プロセッサと作業を使用して時間を取得します。 ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle \Theta (n^{3})}$

プログラム最短経路宣言する n,k: 整数、 D: 整数の配列 [0..n-1, 0..n-1]当初 n = 10 # k = 0 # <|| i,j : 0 <= i < n かつ 0 <= j < n :: D[i,j] = ランド() % 100 >割り当てる <|| i,j : 0 <= i < n かつ 0 <= j < n :: D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > || k < n - 1 の場合、k := k + 1終わり

これをさらに高速化できます。以下のプログラムは、プロセッサと作業量を使用して、すべてのペアの最短経路を時間内で計算します。 ${\displaystyle \Theta (\log ^{2}n)}$ ${\displaystyle \Theta (n^{3})}$ ${\displaystyle \Theta (n^{3}\log n)}$

プログラム shortestpath2宣言する n: 整数、 D: 整数の配列 [0..n-1, 0..n-1]当初 n = 10 # <|| i,j : 0 <= i < n かつ 0 <= j < n :: D[i,j] = ランド() % 10 >割り当てる <|| i,j : 0 <= i < n かつ 0 <= j < n :: D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) >終わり

ラウンド の後、から までの最短経路の長さが格納されます（長さ ）。次のラウンドでは、 は長さ となり、以下同様に続きます。 ${\displaystyle r}$D[i,j] ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 0\dots r}$ ${\displaystyle 0\dots 2r}$

参考文献

• K. マニ チャンディおよびジャヤデフ ミスラ (1988)並列プログラム設計: 基礎。

Retrieved from "https://en.wikipedia.org/w/index.php?title=UNITY_(programming_language)&oldid=1192395750"