The UNITY programming languages was constructed by K. Mani Chandy and Jayadev Misra for their book Parallel Program Design: A Foundation. It is a rather theoretical language, which tries to focus on what, instead of where, when or how. The peculiar thing about the language is that it has no flow control. The statements in the program run in a random order, until none of the statements causes change if run. A correct program converges into a fix-point. The flow control mechanism is used for controlling the flow of data in a network under well-defined conditions, while congestion control is used for controlling the flow of data when congestion has actually occurred . ... The term statement can have several meanings: In programming, a statement is an instruction to execute something that will not return a value. ... // About Bees This article is about completely random and illogical things. ...

Description

All statements are assignments, and are separated by #. A statement can consist of multiple assignments, on the form a,b,c := x,y,z, or a := x || b := y || c := z. You can also have a quantified statement list, <# x,y : expression :: statement>, where x and y are chosen randomly among the values that satisfy expression. A quantified assignment is similar. In <|| x,y : expression :: statement >, statement is executed simultaneously for all pairs of x and y that satisfy expression. In computer programming, an assignment is the defining of a variable. ...

Examples

Bubble sort

Bubble sort the array by comparing adjacent numbers, and swapping them if they are in the wrong order. Using Θ(n) expected time, Θ(n) processors and Θ(n²) expected work. The reason you only have Θ(n) expected time, is that k is always chosen randomly from {0,1}. This can be fixed by flipping k manually. Bubble sort, also known as exchange sort, is a simple sorting algorithm. ... A graph with 6 vertices (nodes) and 7 edges. ...

 Program bubblesort declare n: integer, A: array [0..n-1] of integer initially n = 20 # <# i : 0 <= i and i < n :: A[i] = rand() % 100 > assign <# k : 0 <= k < 2 :: <|| i : i % 2 = k and 0 <= i < n - 1 :: A[i], A[i+1] := A[i+1], A[i] if A[i] > A[i+1] > > end 

Rank-sort

You can sort in Θ(logn) time with rank-sort. You need Θ(n²) prosessors, and do Θ(n²) work.

 Program ranksort declare n: integer, A,R: array [0..n-1] of integer initially n = 15 # <|| i : 0 <= i < n :: A[i], R[i] = rand() % 100, i > assign <|| i : 0 <= i < n :: R[i] := <+ j : 0 <= j < n and (A[j] < A[i] or (A[j] = A[i] and j < i)) :: 1 > > # <|| i : 0 <= i < n :: A[R[i]] := A[i] > end 

Floyd-Warshall

Using the Floyd-Warshall all pairs shortest path algorithm, we include intermediate nodes iteratively, and get Θ(n) time, using Θ(n²) processors and Θ(n³) work. In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshalls algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...

 Program shortestpath declare n,k: integer, D: array [0..n-1, 0..n-1] of integer initially n = 10 # k = 0 # <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] = rand() % 100 > assign <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > || k := k + 1 if k < n - 1 end 

We can do this even faster. The following programs computes all pairs shortest path in Θ(log²n) time, using Θ(n³) processors and Θ(n³logn) work.

 Program shortestpath2 declare n: integer, D: array [0..n-1, 0..n-1] of integer initially n = 10 # <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] = rand() % 10 > assign <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) > end 

After round r, D[i,j] contains the length of the shortest path from i to j of length . In the next round, of length , and so on.

References

• K. Mani Chandy and Jayadev Misra (1988) Parallel Program Design: A Foundation.