UNITY (programming language): Difference between revisions

Revision as of 00:25, 15 March 2006

Latest revision as of 03:09, 29 December 2023

(36 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 focus on ''what'', instead of ''where'', ''when'' or ''how''. The peculiar thing about the language is that it has no flow control. The statements in the program run in a random order, until none of the statements 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]]).

== 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'', <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==

Line 9 ⟶ 16:

===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>. YouThis couldcan fixbe thisfixed by flipping <code>k</code> manually.

Program bubblesort

Line 17 ⟶ 24:

initially

n = 20 #

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

assign

<# k : 0 <= k < 2 ::

Line 23 ⟶ 30:

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, <math>\Theta(n^2)</math> processors and <math>\Theta(n^2)</math> work. It should have CREW [[PRAM]] complexity. The array <code>A</code> is sorted in an array of arrays <code>B</code>, with sentinels of negative and positive infinity.

Program mergesort

declare

n,m: integer,

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

B: array [0..n,0..n+1] of integer

initially

n = 15 #

m = n #

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

A[i], N[i] = rand() % 100, 1 >

#

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

B[i,j] = -infi if j = 0 ~

A[i] if j = 1 ~

infi if j > 1 >

assign

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

<|| a,b : 0 <= a <= N[s] and 0 <= b <= N[s+1] ::

B[s / 2, a+b] := B[s, a]

if 1 <= a <= N[s] and B[s+1, b] < B[s, a] <= B[s+1, b+1] ||

B[s / 2, a+b] := B[s+1, b]

if 1 <= b <= N[s+1] and B[s, a] <= B[s+1, b] < B[s, a+1] > ||

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

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

<|| a : m%2 = 1 and 1 <= a <= N[m-1] ::

B[(m-1)/2, a] := B[m-1, a] > ||

m := (m/2) + m%2 ||

<|| i : 0 <= i < n :: A[i] := B[0,i+1] >

end

Below is the same program rewritten to sort in-place. As you see, a bit more code is needed when you don't have the sentinels.

Program mergesort2

declare

n,m: integer,

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

initially

n = 20 #

m = n ||

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

assign

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

<|| a,b : (a = 0 and b = 1) or (a = 1 and b = 0) ::

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

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

===Rank-sort===

If you don't like big ugly programs, youYou can trysort the much nicer Rank-sort.in <math>\Theta(\log n)</math> time, with rank-sort. You need <math>\Theta(n^2)</math> prosessorsprocessors, and do <math>\Theta(n^2)</math> work.

Program ranksort

Line 103 ⟶ 46:

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 ::

Line 109 ⟶ 52:

end

===Floyd–Warshall algorithm===

===Floyd-Warshall===

Using the [[Floyd-Warshall_algorithm|Floyd-WarshallFloyd–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

Line 148 ⟶ 91:

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

[[Category:EsotericExperimental programming languages]]