UNITY (programming language): Difference between revisions

Revision as of 22:29, 8 November 2005

Latest revision as of 03:09, 29 December 2023

(43 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==

===InsertionsortBubble sort===

[[InsertionBubble 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>. This can be fixed by flipping <code>k</code> manually.

Program sort2bubblesort

declare

n: integer,

Line 16 ⟶ 24:

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

===MergesortRank-sort===

[[MergeYou can sort]] the array using a constant time merge. Usingin <math>\Theta(\log n)</math> time andwith rank-sort. You need <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 thedo <codemath>&lt;=\Theta(n^2)</codemath> operator. If you expand the <code>a,b</code> quantification, you can get CREW [[PRAM]] complexitywork.

Program sort3ranksort

declare

n,m: integer,

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

initially

n = 2015 #

m<|| i : 0 <= i < n ||::

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

assign

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

R[i] := <||+ a,bj : (a0 <= 0j < n and b(A[j] =< 1)A[i] or (aA[j] = 1A[i] and bj =< 0i)) :: 1 > >

#
<|| sai : 0 <= sai < N[s+a]n ::

A[SR[si]+sa] := A[S[s+a]+sai] >

end

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

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

===Floyd–Warshall algorithm===

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

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

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.

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

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

Program shortestpath

S[s/2] := S[s] ||

declare

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

n,k: integer,

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

m D:= m/2array [0..n-1, 0..n-1] +of m%2integer

initially

end

n = 10 #

k = 0 #

<|| i,j : 0 <= i < n and 0 <= j < n ::

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

assign

<|| i,j : 0 <= i <|| sbn :and 0 <= sbj < N[s+b]n ::

ND[s/2i,j] := Nmin(D[si,j], D[i,k] + ND[s+1k,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 ::

SD[s/2i,j] := S[s]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:EsotericExperimental programming languages]]