Nondeterministic Iteration
This module reviews nondeterminism
in the form of
do-od loops.
The module describes states, transitions, and their graph
representations.
do-od loops
A
do-od loop consists of a set of
guarded commands. A guarded
command consists of a
guard and a
command with the syntax:
guard -> command
The execution of the do-od loop is as follows: Execute
any guarded command
of the loop for which the guard evaluates to True. Execution of the loop
terminates when all guards evaluate to False.
Nondeterministic Executions
Most programming languages are
deterministic; in a deterministic language the next
statement to be executed is uniquely determined by the current state
of the program.
By contrast, a do-od loop is
nondeterministic --- the
next statement to be executed can be
any guarded command with a true
guard. So,
different executions of the same do-od loop may execute commands in
different orders and result in different outputs.
Example: Sorting
Let \(X\) be an array of \(N\) numbers. The following loop sorts
the array in ascending order. (We assume that indices
start at 0.)
for all i where 0 < i < N:
X[i-1] > X[i] -> X[i-1], X[i] = X[i], X[i-1]
The loop has \(N-1\) guarded commands, where the
i-th command
is:
X[i-1] > X[i] -> X[i-1], X[i] = X[i], X[i-1]
Execution of the loop proceeds by
flipping
any adjacent pair of elements that is out of
order. Execution terminates when every adjacent pair is in order.
States and Transitions in do-od Loops
The state of a do-od loop is given by the values of its
variables.
The execution of a guarded command, whose guard evaluates to true,
may change values of variables, and thus cause a transition from
one state to another.
There are no transitions from a state in which the guards of all
commands are false.
If the guards of multiple commands are true in a state \(s\) then
there can be transitions from \(s\) to multiple different states;
any of these transitions from \(s\) could be taken.
Example
Consider a do-od loop that sorts an array \(x[0, 1, 2,
3]\) in increasing order by flipping adjacent out-of-order
pairs. The loop has a guarded command for each adjacent pair of
elements; the guard evaluates to true when the pair is out
of order, and the command switches the pair.
If \(x =[10, 5, 1]\) then one of two commands can be executed:
either flip \(x[0], x[1]\) or flip \(x[1], x[2]\).
The state-transition graph has edges from state \(x =[10, 5, 1]\)
to state \(x =[5, 10, 1]\) and to state \(x =[10, 1, 5]\).
Graph Representation of States and Transitions
The states and state transitions of a system are represented by a
directed graph
in which vertices represent states and edges represent
transitions.
We call this graph the state-transition graph.
A computation is a sequence of states where there exists a
transition from each state in the sequence to the next state of
the sequence.
A computation is represented by a path through the
state-transition graph.
In this chapter, we treat the following as equivalent: vertex and
state, edge and state transition, computation and path.
Review
- What is a do-od loop? What does nondeterministic execution mean?
- What are states of a program? How are states and transitions
represented as graphs?
K. Mani Chandy,
Emeritus Simon Ramo Professor,
California Institute of Technology