For years I have admired the work of Edsger W. Dijkstra. His book,
_A_Discipline_of_Programming_, Prentice-Hall is one of the most
important books on programming that I own. (Fair warning, one does
not read this book -- one works through it -- but the journey is well
worth the effort!)
Inspired by Dijkstra's "guarded command" notation, and empowered by
recent contributions from Gabriele and Eric, I'm offering an
experimental implementation of Dijkstra's nondeterministic control
structures.
Below I include the source code, some description, and a couple of
examples. After some time for experimentation, comments, feedback,
and enhancements, I'll provide a final version to the script
library.
CODE ========
ewd: make object! [
_reduce: func [ args [block!] /local opts ] [
opts: copy []
while [not empty? args] [
args: system/words/do/next args
system/words/if all [ not unset? first args first args ] [
append/only opts first second args
]
args: skip second args 1
]
return opts
]
if: func [ [catch throw] args [block!] /local opts ] [
system/words/if 0 = length? opts: _reduce args [
throw make error! "aborting if; no condition true"
]
system/words/do pick opts random length? opts
]
do: func [ [throw] args [block!] /local opts ] [
while [0 < length? opts: _reduce args] [
system/words/do pick opts random length? opts
]
]
]
DESCRIPTION ========
Both ewd/if and ewd/do take as the only argument a block of paired
conditional expressions ("guards") and code blocks ("commands").
ewd/if evaluates all guards, then picks an arbitrary command whose
guard is true and evaluates it. If only one guard is ever true,
then this is just a conventional multi-way decision. But if more
than one guard is true, the selection is nondeterministic.
If none of the guards is true, ewd/if will barf; it has been asked
to choose an action, and then given no valid alternatives.
To have a "do nothing" alternative, an explicit empty block MUST
be supplied with an appropriate guard.
ewd/do also evaluates all guards, then picks an arbitrary command
whose guard is true and evaluates it. This process is repeated
until all guards are false, at which point the iteration terminates.
No guards true simply means that there's nothing left to do.
Obviously there is some overhead in always evaluating all guards.
Dijkstra's arguments (regarding the notation itself, obviously not
my implementation of it) had to do with:
1) the value of always making explicit exactly what conditions
had to be satisfied for a command to be acted on (how many
times have programmers gotten lost in elseif/else nests?);
2) the beauty and symmetry that emerge when we don't get lazy
and let "fall through the default" take over our thinking;
3) our need to understand nondeterminism better, since modern
computers really do exhibit nondeterminism anyway (think of
interrupts, network communication, multitasking, user input,
event timings, etc. -- I usually NEVER know enough to predict
all the details of my computers' behaviors, but need to be
able to write code that can ensure that all behaviors are
reasonable even when not totally determined in advance.)
EXAMPLES ========
First, to address Ladislav's original example:
signum: func [n [number!]] [
ewd/if [
n < 0 [-1]
n = 0 [ 0]
n > 0 [ 1]
]
]
with test cases
>> signum -12
== -1
>> signum 12
== 1
>> signum 2 - 2
== 0
Dijkstra argues that if it doesn't matter which action is taken, the
code should make that clear! If two values are equal, then either
one of them can serve as the maximum.
maxn: func [a b] [
ewd/if [
a >= b [a]
b >= a [b]
]
]
>> maxn 23 14
== 23
>> maxn 14 23
== 23
>> maxn 12 12
== 12
Another example from Dijkstra is the greatest common divisor:
gcd: func [a b] [
ewd/if [
all [a > 0 b > 0] [
ewd/do [
a > b [a: a - b]
b > a [b: b - a]
]
a
]
]
]
where the ewd/if simply ensures that both arguments are positive, and
the ewd/do repeatedly subtracts the smaller value from the larger
until they are equal (neither a>b nor b>a is true). Thus,
>> gcd 51 12
== 3
>> gcd -5 45
** User Error: aborting if; no condition true.
** Where: ewd/if [
all [a > 0 b > 0] [ewd/do [
a > b [a: a - b]
b > a [b: b - a]
]
a
]
]
A tidy-looking solution to a not-very-large problem: find the median
(middle) of three argument values.
medianof3: func [a b c] [
ewd/do [
a > b [set [a b] reduce [b a]]
b > c [set [b c] reduce [c b]]
]
b
]
All guards being false terminates the loop, but a bit of boolean
algebra gives us
not any [a > b b > c]
=
all [not a > b not b > c]
=
all [a <= b b <= c]
which means that upon termination all three values are in order,
therefore b is the median value.
This one is small enough to test all code paths exaustively.
>> medianof3 10 20 30
== 20
>> medianof3 10 30 20
== 20
>> medianof3 20 10 30
== 20
>> medianof3 20 30 10
== 20
>> medianof3 30 10 20
== 20
>> medianof3 30 20 10
== 20
Finally -- just for fun -- give this function two numeric arguments,
and it will make a true statement about them. Since it is non-
deterministic, you never know WHICH true statement it will make.
observe: func [a [number!] b [number!]] [
print [ "I observe that"
a
ewd/if [ a < b ["is less than"]
a <= b ["is at most"]
a = b ["is equal to"]
a >= b ["is at least"]
a > b ["exceeds"]
a <> b ["differs from"]
true ["is a number, as is"]
]
b
]
]
Thus...
>> loop 4 [observe 7 9]
I observe that 7 differs from 9
I observe that 7 is less than 9
I observe that 7 is at most 9
I observe that 7 is less than 9
>> loop 4 [observe 9 7]
I observe that 9 exceeds 7
I observe that 9 is at least 7
I observe that 9 is a number, as is 7
I observe that 9 is at least 7
>> loop 4 [observe 8 8]
I observe that 8 is a number, as is 8
I observe that 8 is at least 8
I observe that 8 is at most 8
I observe that 8 is equal to 8
-jn-
