Encyclopedia

UNITY (programming language)

Theoretical programming language for describing concurrent computations

Wikipedia contributorsAdapted for Fathomly · View authors

3 min read
Source updated August 25, 2026

UNITY is a programming language constructed by K. Mani Chandy and Jayadev Misra for their book Parallel Program Design: A Foundation. It is a theoretical language which focuses on what, instead of where, when or how. The language contains no method of flow control, and program statements run in a nondeterministic way until statements cease to cause changes during execution. This allows for programs to run indefinitely, such as auto-pilot or power plant safety systems, as well as programs that would normally terminate (which here converge to a fixed point).

01Description

All statements are assignments, and are separated by #. A statement can consist of multiple assignments, of 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.

02Examples

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

Rank-sort

You can sort in $\Theta (\log n)$ time with rank-sort. You need $\Theta (n^{2})$ processors, and do $\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 algorithm

Using the Floyd-Warshall algorithm 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.

Watch videos about UNITY (programming language)Explainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “UNITY (programming language)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.