procedure do_od: Dijkstra's do_od construct procedure if_fi: Dijkstra's if_fi construct
link dijkstra
December 9, 2003; Frank J. Lhota
This file is in the public domain.
The procedures do_od and if_fi implement the "do ... od" and "if ... fi"
control structures used in the book "A Discipline of Programming" by
Edsger W. Dijkstra. This book uses a programming language designed to
delay implementation details, such as the order in which tests are
performed.
Dijkstra's programming language uses two non-ASCII characters, a box and
a right arrow. In the following discussion, the box and right arrow
characters are represented as "[]" and "->" respectively.
The "if ... fi" control structure is similar to multi-branch "if" statements
found in many languages, including the Bourne shell (i.e. the
"if / elif / fi" construct). The major difference is that in Dijkstra's
notation, there is no specified order in which the "if / elif" tests are
performed. The "if ... fi" structure has the form
if
Guard1 -> List1
[] Guard2 -> List2
[] Guard3 -> List3
...
[] GuardN -> ListN
fi
where
Guard1, Guard2, Guard3 ... GuardN are boolean expressions, and
List1, List2, List3 ... ListN are lists of statements.
When this "if ... fi" statement is performed, the guard expressions are
evaluated, in some order not specified by the language, until one of the
guard expressions evaluates to true. Once a true guard is found, the list
of statements following the guard is evaluated. It is a fatal error
for none of the guards in an "if ... fi" statement to be true.
The "do ... od" control is a "while" loop structure, but with multiple
loop conditions, in style similar to "if ... fi". The form of a Dijkstra
"do" statement is
do
Guard1 -> List1
[] Guard2 -> List2
[] Guard3 -> List3
...
[] GuardN -> ListN
od
where
Guard1, Guard2, Guard3 ... GuardN are boolean expressions, and
List1, List2, List3 ... ListN are lists of statements.
To perform this "do ... od" statement, the guard expressions are
evaluated, in some order not specified by the language, until either a
guard evaluates to true, or all guards have been evaluated as false.
- If all the guards are false, we exit the loop.
- If a guard evaluates to true, then the list of statements following this
guard is performed, and then we loop back to perform this "do ... od"
statement again.
The procedures if_fi{} and do_od{} implement Dijkstra's "if ... fi" and
"do ... od" control structures respectively. In keeping with Icon
conventions, the guard expressions are arbitrary Icon expressions. A guard
is considered to be true precisely when it succeeds. Similarly, a statement
list can be represented by a single Icon expression. The Icon call
if_fi{
Guard1, List1,
Guard2, List2,
...
GuardN, ListN
}
suspends with each result produced by the expression following the true
guard. If none of the guards succeed, runerr() is called with an appropriate
message.
Similarly, the Icon call
do_od{
Guard1, List1,
Guard2, List2,
...
GuardN, ListN
}
parallels the "do ... od" statement. As long as at least one guard
succeeds, another iteration is performed. When all guards fail, we exit
the loop and do_od fails.
The test section of this file includes a guarded command implementation of
Euclid's algorithm for calculating the greatest common denominator. Unlike
most implementations of Euclid's algorithm, this version handles its
parameters in a completely symmetrical fashion.