View source for Crunode

{{multiple issues|
{{expert-subject|1=Computer science|date=September 2011}}
{{technical|date=September 2011}}
}}

'''UNITY''' is a programming language that 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 (data)|flow control]]. The [[statement (programming)|statement]]s in the program run in a [[random]] order, until none of the statements causes change if run. This allows for programs that run indefinitely (auto-pilot or power plant safety system) as well as programs that would normally terminate (which here converge to a [[Fixed point combinator|fixed point]]).

== Description ==

All statements are [[assignment (computer science)|assignment]]s, and are separated by <code>#</code>. A statement can consist of multiple assignments, of the form <code>a,b,c := x,y,z</code>, or <code>a := x || b := y || c := z</code>. You can also have a ''quantified statement list'', <code>&lt;# x,y : ''expression'' :: ''statement''&gt;</code>, where x and y are chosen randomly among the values that satisfy ''expression''. A ''quantified assignment'' is similar. In <code><|| x,y : ''expression'' :: ''statement'' &gt;</code>, ''statement'' is executed simultaneously for ''all'' pairs of <code>x</code> and <code>y</code> 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 <math>\Theta(n)</math> expected time, <math>\Theta(n)</math> processors and <math>\Theta(n^2)</math> expected work. The reason you only have <math>\Theta(n)</math> ''expected'' time, is that <code>k</code> is always chosen randomly from <math>\{0,1\}</math>. This can be fixed by flipping <code>k</code> 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 <math>\Theta(\log n)</math> time with rank-sort. You need <math>\Theta(n^2)</math> processors, and do <math>\Theta(n^2)</math> 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 problem|shortest path]] algorithm, we include intermediate nodes iteratively, and get <math>\Theta(n)</math> time, using <math>\Theta(n^2)</math> processors and <math>\Theta(n^3)</math> 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 <math>\Theta(\log^2 n)</math> time, using <math>\Theta(n^3)</math> processors and <math>\Theta(n^3 \log n)</math> 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 <math>r</math>, <code>D[i,j]</code> contains the length of the shortest path from <math>i</math> to <math>j</math> of length <math>0 \dots r</math>. In the next round, of length <math>0 \dots 2r</math>, and so on.

==References==
* K. Mani Chandy and Jayadev Misra (1988) ''Parallel Program Design: A Foundation''.

[[Category:Experimental programming languages]]