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).

Description

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.

Examples

Bubble sort

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

Rank-sort

You can sort in Θ ( log ⁡ n ) {\displaystyle \Theta (\log n)} time with rank-sort. You need Θ ( n 2 ) {\displaystyle \Theta (n^{2})} processors, and do Θ ( n 2 ) {\displaystyle \Theta (n^{2})} work.

Floyd–Warshall algorithm

Using the Floyd–Warshall algorithm all pairs shortest path algorithm, we include intermediate nodes iteratively, and get Θ ( n ) {\displaystyle \Theta (n)} time, using Θ ( n 2 ) {\displaystyle \Theta (n^{2})} processors and Θ ( n 3 ) {\displaystyle \Theta (n^{3})} work.

We can do this even faster. The following programs computes all pairs shortest path in Θ ( log 2 ⁡ n ) {\displaystyle \Theta (\log ^{2}n)} time, using Θ ( n 3 ) {\displaystyle \Theta (n^{3})} processors and Θ ( n 3 log ⁡ n ) {\displaystyle \Theta (n^{3}\log n)} work.

After round r {\displaystyle r}, D[i,j] contains the length of the shortest path from i {\displaystyle i} to j {\displaystyle j} of length 0 … r {\displaystyle 0\dots r}. In the next round, of length 0 … 2 r {\displaystyle 0\dots 2r}, and so on.

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

public class CarController : MonoBehaviour {

}