Guarded Command Language (also Guarded commands) is a language defined by Edsger Dijkstra for predicate transformer semantics ^[1]. It has a special set of conditional and loop statements. The most basic element of the language is the guarded command, composed of two parts: C, the condition or guard; and S, the statement/command. Edsger Dijkstra (courtesy Brian Randell) Prof Dr Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ... Predicate transformer semantics is an extension of Floyd-Hoare Logic invented by Dijkstra and extended and refined by other researchers. ... The term conditional is used in linguistics and logic to refer to related concepts about sentences of the form If X, then Y (ie. ... // A loop is generally something that closes back on itself such as a circle or ring. ... A statement is the minimal unit of structuring in imperative programming languages. ... In computer programming, a guard is a boolean expression that must evaluate to true if the program execution is to continue in the branch in question. ...

A guarded command is usually written:

C S

The conditions are expressed as propositions over the variables of the program. Statements change state: Proposition is a term used in logic to describe the content of assertions. ... In computer science and mathematics, a variable (sometimes called a pronumeral) is a symbol denoting a quantity or symbolic representation. ...

x, z := y, y + 1 the new value of x is y and the new value of z is y + 1

or perform I/O: In computing, Input/output, or I/O, is the collection of interfaces that different functional units (sub-systems) of an information processing system use to communicate with each other, or the signals (information) sent through those interfaces. ...

print "Output is the greatest!"

Naturally, an implementation of guarded commands may allow arbitrary breadth of both conditions and statements. A guarded command may occur on its own as a statement; for commands that are always executed, the guard may be omitted:

true print 5

is equivalent to:

print 5

Conditional command if

The if command is written:

if

[command1]

[command2]

...

fi

where [command] is a guarded command.

The statement part is executed if and only if the condition is true. Moreover, if more than one command is applicable — that is, its condition is true — only one will be chosen (randomly or nondeterministically).

Example

Given an expression in pseudocode: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

if then print "More or equal";

else if a < b then print "Less";

The equivalent in guarded commands is:

if

print "More or equal"

print "Less"

fi

The power of guarded commands is illustrated in the following expression:

if

print "More or equal"

print "Less or equal"

fi

When a = b, the result of command can be one "More or equal" or "Less or equal".

Loop command do

The do command is written:

do

[command1]

[command2]

...

od

Every applicable command is executed (possibly more than once) until no commands are applicable.

Example

Below are two implementations of the Euclidean algorithm to find the greatest common divisor. The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. ...

Variant 1:

x, y := X, Y a statement (unguarded)

do a loop command — this loop will terminate when x = y

if a conditional command (itself guarded)

x := x-y a guarded statement in the if

y := y-x

fi

od

print x ; another statement, also unguarded

Variant 2:

x, y := X, Y

do again, termination when x = y

x := x-y

y := y-x

od

print x

Note that this second version takes advantage of do's termination condition, making the if of the first variant implicit.

Applications

Asynchronous Circuits

Guarded commands are suitable for Quasi Delay Insensitive circuit design because the do-od construct allows arbitrary relative delays for the selection of different commands. In this application, a logic gate driving a node y in the circuit consists of two guarded commands, as follows: Quasi Delay Insensitive Circuits are a class of delay-insensitive asynchronous circuit which are invariant to (and make no assumptions about) the delays of any of the circuits elements, except to assume that certain fanouts are isochronic forks. ...

PulldownGuard and PullupGuard here are functions of the logic gate's inputs, which describe when the gate pulls the output down or up, respectively. Unlike classical circuit evaluation models, the do-od model for a set of guarded commands (corresponding to an asynchronous circuit) can accurately describe all possible dynamic behaviors of that circuit. Depending on the model one is willing to live with for the electrical circuit elements, additional restrictions on the guarded commands may be necessary for a guarded-command description to be entirely satisfactory. Common restrictions include stability, non-interference, and absence of self-invalidating commands.^[2]

References

1. ^ Dijkstra, Edsger W. EWD472: Guarded commands, non-determinacy and formal. derivation of programs.. Retrieved on August 16, 2006.
2. ^ Martin, Alain J. Synthesis of Asynchronous VLSI Circuits.