In 1975, Dijkstra proposed an alternative set of selection and looping constructs for programming languages. The idea of guarded commands introduced nondeterminism to programs.

A guarded command is a statement, or list of statements, that is "guarded" by a boolean expression. For example:

        x >= y  -> max := x;
        (guard)    (command)

The idea being that the command cannot be executed unless the guard evaluates to true. So far, this construct is nothing special. What adds nondeterminism is how these guarded commands are used for selection and looping.

Dijkstra's selection structure looks like this:

     if <boolean expression> -> < statement >
     [] <boolean expression> -> < statement >
     ...
     [] <boolean expression> -> < statement >
     fi
There are several guarded commands in the structure, separated by the square brackets. The selection goes like this: if none of the boolean expressions evaluate to true, the program exits with an error. If one of the expressions evaluate to true, then the statement associated with that guard is executed. Finally, if more than one of the expressions are true, then one of the expressions is nondeterministically chosen, and the command associated with it is performed.

Here's an example: suppose you want to create a program that gets the maximum value between x and y. Using guarded commands, we would write the program like this:

     if x >= y -> max := x;
     [] y >= x -> max := y; 
     fi
That is, max is assigned whichever is greater of x or y. If x and y are the same value, then it does not matter whether max gets assigned either x or y.

The looping structure is similar:

     do <boolean expression> -> < statement >
     [] <boolean expression> -> < statement >
     ...
     [] <boolean expression> -> < statement >
     od
The semantics is that all the expressions are evaluated simultaneously, if one of the expressions is true, then the statement associated with it is performed. If more that one is true, then one statement is picked nondeterministically. Finally, if all of the expressions evaluate to false, the program exits the loop.

Both Ada and Hoare's CSP use guarded commands as a way to handle concurrency.


References:
Edsger Dijsktra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, Vol. 18, #8, August, 1995.
Robert W. Sebesta,Concepts of Programming Languages, 5th edition, Addison Wesley, 2002

Log in or register to write something here or to contact authors.