UNITY is a programming language that was constructed by K. Mani Chandy

K. Mani Chandy

Kanianthra Mani Chandy is the Simon Ramo Professor of Computer Science at the California Institute of Technology. He has been the Executive Officer of the Computer Science Department twice, and he has been a professor at Caltech since 1989....

 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

Flow control

In data communications, flow control is the process of managing the pacing of data transmission between two nodes to prevent a fast sender from outrunning a slow receiver. It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with...

. The statement

Statement (programming)

In computer programming a statement can be thought of as the smallest standalone element of an imperative programming language. A program written in such a language is formed by a sequence of one or more statements. A statement will have internal components .Many languages In computer programming...

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

Fixed point combinator

In computer science, a fixed-point combinator is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f. For example, 0 and 1 are fixed points of the function f = x2, because 0 = 02 and 1 = 12...

).

Description

All statements are assignment

Assignment (computer science)

In computer programming, an assignment statement sets or re-sets the value stored in the storage location denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements...

s, and are separated by #. A statement can consist of multiple assignments, of the form a,b,c := x,y,z, or a := x || b := y || c := z. You can also have a quantified statement list, <# x,y : expression :: statement>, where x and y are chosen randomly among the values that satisfy expression. A quantified assignment is similar. In <|| x,y : expression :: statement >, statement is executed simultaneously for all pairs of x and y that satisfy expression.

Bubble sort

Bubble sort

Bubble sort

Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...

 the array by comparing adjacent

Adjacent

Adjacent is an adjective meaning contiguous, adjoining or abuttingIn geometry, adjacent is when sides meet to make an angle.In graph theory adjacent nodes in a graph are linked by an edge....

 numbers, and swapping them if they are in the wrong order. Using expected time, processors and expected work. The reason you only have expected time, is that k is always chosen randomly from . This can be fixed by flipping k manually.

Program bubblesort
declare
n: integer,
A: array [0..n-1] of integer
initially
n = 20 #
<|| i : 0 <= i and i < n :: A[i] = rand % 100 >
assign
<# k : 0 <= k < 2 ::
<|| i : i % 2 = k and 0 <= i < n - 1 ::
A[i], A[i+1] := A[i+1], A[i]
if A[i] > A[i+1] > >
end

Rank-sort

You can sort in time with rank-sort. You need processors, and do work.

Program ranksort
declare
n: integer,
A,R: array [0..n-1] of integer
initially
n = 15 #
<|| i : 0 <= i < n ::
A[i], R[i] = rand % 100, i >
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 ::
A[R[i]] := A[i] >
end

Floyd–Warshall algorithm

Using the Floyd–Warshall algorithm all pairs shortest path

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...

algorithm, we include intermediate nodes iteratively, and get time, using processors and work.

Program shortestpath
declare
n,k: integer,
D: array [0..n-1, 0..n-1] of integer
initially
n = 10 #
k = 0 #
<|| i,j : 0 <= i < n and 0 <= j < n ::
D[i,j] = rand % 100 >
assign
<|| i,j : 0 <= i < n and 0 <= j < n ::
D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > ||
k := k + 1 if k < n - 1
end

We can do this even faster. The following programs computes all pairs shortest path in time, using processors and work.

Program shortestpath2
declare
n: integer,
D: array [0..n-1, 0..n-1] of integer
initially
n = 10 #
<|| i,j : 0 <= i < n and 0 <= j < n ::
D[i,j] = rand % 10 >
assign
<|| i,j : 0 <= i < n and 0 <= j < n ::
D[i,j] := min(D[i,j], ) >
end

After round , D[i,j] contains the length of the shortest path from to of length . In the next round, of length , and so on.

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.