UNITY (programming language): Difference between revisions

Revision as of 22:39, 8 November 2005

Revision as of 10:03, 9 November 2005

Line 1:

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 focusefocus on ''what'', andinstead notof ''where'', ''when'' or ''how''. The peculiar thing about the language is that it has nowno 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''.

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''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 &lt; x &lt; y &lt; n</code>''expression''.

Line 8:

===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> processorsexpected 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>. You could fix this by flipping <code>k</code> manually.

Program sort2bubblesort

declare

n: integer,

Line 20:

<# 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 <math>\Theta(\log n)</math> time and, <math>\Theta(n^2)</math> processors. In this example, a value may be written many times simultaneously, and values might be duplicated, since we are not carefull with the <codemath>&lt;=\Theta(n^2)</codemath> operatorwork. If you expand the <code>a,b</code> quantification, youIt canshould gethave CREW [[PRAM]] complexity.

Program sort3mergesort

declare

n,m: integer,

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

Line 34 ⟶ 35:

n = 20 #

m = n ||

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

assign

<|| s : 0 <= s < m - 1 and s % 2 = 0 ::

Line 40 ⟶ 41:

<|| 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]+sa+N[s+b]+sb-1] :<= A[S[s+a]+sa] < A[S[s+b]+sb] > ||

if A[S[s+b]+sa+N[s+b]-1] <:= 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

===Floyd-Warshall===

Using the [[Floyd-Warshall_algorithm|Floyd-Warshall]] 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