UNITY (programming language): Difference between revisions

Revision as of 17:32, 8 November 2005

Latest revision as of 03:09, 29 December 2023

(44 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|Theoretical programming language for describing concurrent computations}}

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 focuse on ''what'', and not ''where'', ''when'' or ''how''. The peculiar thing about the language is that it has now flow control. The statements in the program run in a random order, until none of the statements any longer may cause change if run. A correct program converges into a ''fix-point''.

{{about|the 1988 theoretical language|other uses|Unity (disambiguation)#Software{{!}}Unity § Software}}

{{multiple issues|

{{technical|date=September 2011}}

{{primary sources|date=July 2019}}

}}

'''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 (data)|flow control]], and program [[statement (programming)|statement]]s run in a [[Nondeterministic programming|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 combinator|fixed point]]).

All statements are assignments, and are separated by <code>#</code>. A statement can consist of multiple assignments, on 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'', for example <code>&lt;# x,y : 0 &lt; x &lt; y &lt; n :: ''statement''&gt;</code>, where x and y are chosen randomly among the values that satisfy the quantification. A ''quantified assignment'' is similar. In <code><|| x,y : 0 &lt; x &lt; y &lt; n :: ''statement'' &gt;<code>, the statement is executed simultaneously for ''all'' <code>x</code> and <code>y</code> satisfying <code>0 &gt; x &gt; y &lt; n</code>.

== Description ==

All statements are assignments[[assignment (computer science)|assignment]]s, and are separated by <code>#</code>. A statement can consist of multiple assignments, onof 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'', for example <code>&lt;# x,y : 0 &lt; x &lt; y &lt; n''expression'' :: ''statement''&gt;</code>, where x and y are chosen randomly among the values that satisfy the quantification''expression''. A ''quantified assignment'' is similar. In <code><|| x,y : 0 &lt; x &lt; y &lt; n''expression'' :: ''statement'' &gt;</code>, the ''statement'' is executed simultaneously for ''all'' pairs of <code>x</code> and <code>y</code> satisfyingthat <code>0satisfy &gt; x &gt; y &lt; n</code>''expression''.

==Examples==

===RandomsortBubble sort===

[[RandomBubble sort]] the array by randomly choosing chosingcomparing twoadjacent numbers, and swapswapping them if they are in the wrong order. Using expected<math>\Theta(n)</math> exponentialexpected time, one<math>\Theta(n)</math> processorprocessors and <math>\Theta(n^2)</math> expected exponential 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 sortbubblesort

declare

n: integer,

Line 15 ⟶ 24:

initially

n = 20 #

<#|| i : 0 <= i and i < n :: A[i] = rand() % 100 >

assign

<# i,jk : 0 <= ik < n and 0 <= j < n2 ::

A[i],<|| A[j]i := A[j], A[i] if% i2 <= jk and A[0 <= i] >< A[j]n >- 1 ::

A[i], A[i+1] := A[i+1], A[i] if A[i] > A[i+1] > >

if A[S[s+a]+sai] <=> A[S[si+b]1] ||> >

end

===InsertionsortRank-sort===

[[InsertionYou can sort]] the array by comparing adjacent numbers, and swapping them if they are in the wrong order. Using <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 sort2ranksort

declare

n: integer,

A,R: array [0..n-1] of integer

initially

n = 2015 #

<#|| i : 0 <= i and i < n ::
A[i], R[i] = rand() % 100, i >

assign

<#|| ki : 0 <= ki < 2n ::

<|| R[i] := i<+ %j 2: 0 <= kj < n and 0(A[j] < A[i] or (A[j] = A[i] <and nj -< 1i)) :: 1 > >

#

A[i], A[i+1] := A[i+1], A[i] if A[i] > A[i+1] > >

<|| sbi : 0 <= sbi < N[s+b]n ::

NA[s/2R[i]] := NA[s] + N[s+1i] > ||

end

===Floyd–Warshall algorithm===

===Mergesort===

Using the [[MergeFloyd–Warshall sortalgorithm]] theall arraypairs using[[Shortest apath constantproblem|shortest timepath]] merge.algorithm, Usingwe include intermediate nodes iteratively, and get <math>\Theta(\log n)</math> time, using <math>\Theta(n^2)</math> processors and <math>\Theta(n^2 \log n3)</math> work. In this example, a value may be written many times simultaneously, since we are not carefull with the <code>&lt;=</code> operator. If you expand the <code>a,b</code> quantification, you can get CREW [[PRAM]] complexity.

Program sort3shortestpath

declare

n,mk: integer,

A,S,ND: array [0..n-1, 0..n-1] of integer

initially

n = 2010 #

mk = n0 ||#

<|| i,j : 0 <= i and i < n ::and A[i],0 N[i],<= S[i]j =< rand()%100,n 1, i:: >

D[i,j] = rand() % 100 >

assign

<|| si,j : 0 <= si < m - 1n and s0 %<= 2j =< 0n ::

<|| aD[i,bj] := min(aD[i,j], =D[i,k] 0+ and b = 1D[k,j]) or> (a = 1 and b = 0) ::||

k := k + 1 if k <|| san :- 0 <= sa < N[s+a] ::1

end

A[S[s]+sa] := A[S[s+a]+sa]

if A[S[s+a]+sa] <= A[S[s+b]] ||

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.

<|| sb : 0 < sb < N[s+b] ::

A[S[s]+sa+sb] := A[S[s+a]+sa]

Program shortestpath2

if A[S[s+b]+sb-1] <= A[S[s+a]+sa] <= A[S[s+b]+sb] > ||

declare

A[S[s]+sa+N[s+b]] := A[S[s+a]+sa]

n: integer,

if A[S[s+b]+N[s+b]-1] <= A[S[s+a]+sa] > > ||

D: array [0..n-1, S[s/20..n-1] := S[s]of ||integer

initially

N[s/2] := N[s] + N[s+1] > ||

n = 10 #

S[(m-1)/2], N[(m-1)/2] := S[m-1], N[m-1] if m%2 = 1 ||

m<|| i,j : 0 <= m/2i +< m%2n and 0 <= j < n ::

D[i,j] = rand() % 10 >

end

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:EsotericExperimental programming languages]]