UNITY (programming language): Difference between revisions

Revision as of 00:25, 15 March 2006

Revision as of 00:29, 15 March 2006

Line 1:

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[[statement]]s in the program run in a [[random]] order, until none of the statements causecauses change if run. A correct program converges into a ''fix-point''.

== Description ==

All statements are assignments[[assignment]]s, 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'', <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:

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