UNITY (programming language)

The programming language UNITY 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.

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.

Examples

Bubble sort

Bubble sort the array by comparing adjacent numbers, and swapping them if they are in the wrong order. Using $\Theta (n)$ expected time, $\Theta (n)$ processors and $\Theta (n^{2})$ expected work. The reason you only have $\Theta (n)$ expected time, is that k is always chosen randomly from $\{0,1\}$. This can be fixed by flipping k manually.

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

Merge sort

Merge sort the array using a constant time merge. Using $\Theta (\log n)$ time, $\Theta (n^{2})$ processors and $\Theta (n^{2})$ work. It should have CREW PRAM complexity. The array A is sorted in an array of arrays B, with sentinels of negative and positive infinity.

Program mergesort
declare
    n,m: integer,
    A,N: array [0..n-1] of integer,
    B: array [0..n,0..n+1] of integer
initially
    n = 15 #
    m = n #
    <|| i : 0 <= i < n :: 
        A[i], N[i] = rand() % 100, 1 > 
    #
    <|| i,j : 0 <= i < n and 0 <= j < n+2 :: 
        B[i,j] = -infi if j = 0 ~
                 A[i]  if j = 1 ~
                 infi  if j > 1 > 
assign
    <|| s : 0 <= s < m - 1 and s % 2 = 0 ::
        <|| a,b : 0 <= a <= N[s] and 0 <= b <= N[s+1] ::
            B[s / 2, a+b] := B[s, a] 
                if 1 <= a <= N[s]   and B[s+1, b] <  B[s, a]   <= B[s+1, b+1] ||
            B[s / 2, a+b] := B[s+1, b] 
                if 1 <= b <= N[s+1] and B[s, a]   <= B[s+1, b] <  B[s, a+1] > ||
        N[s/2] := N[s] + N[s+1] > ||
    N[(m-1)/2] := N[m-1] if m%2 = 1 ||
    <|| a : m%2 = 1 and 1 <= a <= N[m-1] ::
        B[(m-1)/2, a] := B[m-1, a] > ||
    m := (m/2) + m%2 ||
    <|| i : 0 <= i < n :: A[i] := B[0,i+1] >
end

Below is the same program rewritten to sort in-place. As you see, a bit more code is needed when you don't have the sentinels.

Program mergesort2
declare
    n,m: integer,
    A,S,N: array [0..n-1] of integer
initially
    n = 20 #
    m = n ||
    <|| i : 0 <= i < n :: A[i], N[i], S[i] = rand() % 100, 1, i >
assign
    <|| s : 0 <= s < m - 1 and s % 2 = 0 ::
        <|| a,b : (a = 0 and b = 1) or (a = 1 and b = 0) ::
            <|| sa : 0 <= sa < N[s+a] ::
                A[S[s]+sa] := A[S[s+a]+sa] 
                    if a = 0 and A[S[s+a]+sa] <= A[S[s+b]] 
                    or a = 1 and A[S[s+a]+sa] <  A[S[s+b]] || 
                <|| sb : 0 < sb < N[s+b] ::
                    A[S[s]+sa+sb] := A[S[s+a]+sa] 
                        if a = 0 and A[S[s+b]+sb-1] <  A[S[s+a]+sa] <= A[S[s+b]+sb]      
                        or a = 1 and A[S[s+b]+sb-1] <= A[S[s+a]+sa] <  A[S[s+b]+sb] > || 
                A[S[s]+sa+N[s+b]] := A[S[s+a]+sa] 
                    if a = 0 and A[S[s+b]+N[s+b]-1] <  A[S[s+a]+sa]
                    or a = 1 and A[S[s+b]+N[s+b]-1] <= A[S[s+a]+sa] > > ||
        S[s/2] := S[s] ||
        N[s/2] := N[s] + N[s+1] > ||
    S[(m-1)/2], N[(m-1)/2] := S[m-1], N[m-1] if m%2 = 1 ||
    m := m/2 + m%2
end

Rank-sort

If you don't like big ugly programs, you can try the much nicer Rank-sort. $\Theta (\log n)$ time, $\Theta (n^{2})$ prosessors, and $\Theta (n^{2})$ 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 $\Theta (n)$ time, using $\Theta (n^{2})$ processors and $\Theta (n^{3})$ work.

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 $\Theta (\log ^{2}n)$ time, using $\Theta (n^{3})$ processors and $\Theta (n^{3}\log n)$ 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 $0\dots r$. In the next round, of length $0\dots 2r$, and so on.

References

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