UNITY (programming language): Difference between revisions

Revision as of 13:18, 13 September 2010

Latest revision as of 03:09, 29 December 2023

(18 intermediate revisions by 17 users not shown)

Line 1:

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

'''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 focus on ''what'', instead of ''where'', ''when'' or ''how''. The peculiar thing about the language is that it has no [[flow control]]. The [[statement (programming)|statement]]s in the program run in a [[random]] order, until none of the statements causes change if run. This allows for programs that run indefinitely (auto-pilot or power plant safety system) as well as programs that would normally terminate (which here converge to a [[Fixed point combinator|fixed 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 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 ==

All statements are [[assignment (computer science)|assignment]]s, and are separated by <code>#</code>. A statement can consist of multiple assignments, of 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==

===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 44 ⟶ 52:

end

===Floyd–Warshall algorithm===

===Floyd-Warshall===

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