UNITY (programming language): Difference between revisions

Revision as of 22:25, 19 August 2013

Latest revision as of 03:09, 29 December 2023

(11 intermediate revisions by 10 users not shown)

Line 1:

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

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

{{multiple issues|

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

{{technical|date=September 2011}}

{{primary sources|date=July 2019}}

}}

'''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 focusfocuses on ''what'', instead of ''where'', ''when'' or ''how''. The peculiar thing about the language iscontains thatno itmethod has noof [[flow control (data)|flow control]]., Theand program [[statement (programming)|statement]]s in the program run in a [[randomNondeterministic programming|nondeterministic]] order,way until nonestatements ofcease theto statementscause causeschanges changeduring if runexecution. This allows for programs thatto run indefinitely, such as (auto-pilot or power plant safety system)systems, as well as programs that would normally terminate (which here converge to a [[Fixed point combinator|fixed point]]).

== Description ==

Line 34 ⟶ 36:

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.

<source>

Program ranksort

declare

Line 50 ⟶ 51:

A[R[i]] := A[i] >

end

</source>

===Floyd–Warshall algorithm===

Line 56:

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.

<source>

Program shortestpath

declare

Line 71 ⟶ 70:

k := k + 1 if k < n - 1

end

</source>

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.

<source>

Program shortestpath2

declare

Line 88 ⟶ 85:

D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) >

end

</source>

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.