UNITY (programming language): Difference between revisions

Revision as of 13:10, 1 October 2006

Latest revision as of 03:09, 29 December 2023

(31 intermediate revisions by 29 users not shown)

Line 1:

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

The '''UNITY''' programming languages 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 [[statement]]s in the program run in a [[random]] order, until none of the statements causes 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 [[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>. This can be fixed 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 27 ⟶ 34:

===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 45 ⟶ 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 84 ⟶ 91:

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

[[Category:EsotericExperimental programming languages]]