Arjen Markus Reading the book "Concepts of programming languages" by Robert Sebesta, I stumbled on two special control constructs designed by Edsger Dijkstra, the guarded if-statement and the guarded do-loop. The motivation is simple: provide if-statements and do-loops that can be thoroughly analysed.
I lack the time right now to describe their properties in detail, but here is a script that implements them and illustrates their use (up to a point :).
Guarded if-statements:
Guarded do-loops:
I can recommend the book, but I regret it only mention Tcl in the introduction :(
# dijkstra.tcl --
# Experiment with Dijkstra's guarded constructs
# (Is it easy to implement them? Yes, remarkably easy)
#
# I took the description from R. Sebesta's
# Concepts of Programming Languages (fifth edition).
# This book showed the syntax of the two constructions as:
#
# if cond1 --> statement1
# [] cond2 --> statement2
# ...
# fi
#
# do cond1 --> statement1
# [] cond2 --> statement2
# ...
# od
#
# and I gave this a small Tclish twist
#
namespace eval ::Guarded {
# Simply create the namespace
}
# d-if --
# Guarded if-construct
# Arguments:
# cond_actions List of conditions and actions
# Result:
# None
# Side effects:
# Whatever the actions involve or an error if the conditions
# turn out to be incomplete
#
proc ::Guarded::d-if { cond_actions } {
#
# Create a list of those actions that can trigger
#
set triggerable_actions {}
foreach {cond action} $cond_actions {
if { [uplevel [list expr $cond]] } {
lappend triggerable_actions $action
}
}
#
# Do we have any? Then randomly select one
# Otherwise, issue an error!
#
set number [llength $triggerable_actions]
if { $number > 0 } {
set selected [expr {int($number*rand())}]
uplevel [lindex $triggerable_actions $selected]
} else {
error "Conditions logically incomplete"
}
}
# d-do --
# Guarded do-loop
# Arguments:
# cond_actions List of conditions and actions
# Result:
# None
# Side effects:
# Whatever the actions invol ve (The do-loop stops when
# no conditions are true)
#
proc ::Guarded::d-do { cond_actions } {
while { 1 } {
#
# Create a list of those actions that can trigger
#
set triggerable_actions {}
foreach {cond action} $cond _actions {
if { [uplevel [list expr $cond]] } {
lappend triggerable_actions $action
}
}
#
# Do we have any? Then randomly select one
# Otherwise, break out of the while loop
#
set number [llength $triggerable_actions]
if { $number > 0 } {
set selected [expr {int($number*rand())}]
uplevel [lindex $triggerable_actions $selected]
} else {
break
}
}
}
# main --
# Some test code and demonstration
#
#
# Maximum of x and y
#
foreach {x y} {1.0 2.0 3.0 3.0 5.0 4.0 6.0 6.0} {
::Guarded::d-if {
{$x <= $y} {puts "y = maximum"; set max $y}
{$x >= $y} {puts "x = maximum"; set max $x}
}
puts "max = $max"
}
#
# Do-loop: two separate ranges with overlap
#
set x 0
set y 0
::Guarded::d-do {
{$x < 4} {puts "Range X (x,y = $x,$y)"; incr x}
{$y < 5} {puts "Range Y (x,y = $x,$y)"; incr y}
}
#
# Overlapping ranges with gap. Note: last illustrates
# incompleteness. (This must be last)
#
foreach {x y} {1.0 2.0 3.0 7.0 5.0 6.0 7.0 8.0} {
puts "x, y: $x, $y"
::Guarded::d-if {
{$x < 4.0 && $y > 5.0} {puts "Range 1"}
{$x > 4.0 && $y < 7.0} {puts "Range 2"}
{$y < 4.5} {puts "Range 3"}
}
}Lars H: "Nondeterministic" almost never means "random" in Computer Science (more commonly "I don't want to tell you how/why/what"), but then again, "random" doesn't always mean random either (Random Access Memory -- never knowing where the next bit is coming from). I couldn't resist making another implementation of the d-if, though. This one is quite non-random:
proc ::Guarded::d-if {cond_actions} {
set if ::if
set call [list]
foreach {cond action} $cond_actions {
lappend call $if $cond then $action
set if elseif
}
uplevel 1 [lappend call else {error "Conditions logically incomplete"}]
}One might also wonder to what extent switch already is this d-if... \rant{A preference for numerical conditions in a language is often a way of coping with inferior string handling.}
NEM (New Year's Eve,2003): The guarded do-loop sounds a bit like the mechanism of a forward-chaining rule interpreter, such as CLIPS. The program cycles until none of the rules are satisfied. If more than one rule satisfies then conflict resolution is used to pick one - this could be done randomly (but usually isn't, for reasons of sanity). Are there any particular differences?
DKF (New Year's Day,2004): The guarded-if is really just a different way to write an if-elseif-else, and the differences are really just syntactic as long as exactly one clause is enabled. The differences come when you have multiple clauses enabled or none at all. There are various ways of describing the behaviour in the multi-enabled case; pick-one-in-order is one rule, but pick-one-in-reverse-order (which you might get from scanning each condition to see whether it is valid and storing which one was actually most recently valid) is also fairly reasonable. There are two other ways of doing it though, being random-choice (such as illustrated above) and simultaneous-execution, where the result states are those that are in the intersection of result states for the two arms (which is semantically nice, but tricky to implement!) In the no-match case, the classic Dijkstra semantics state that that is a deadlock case; the program becomes unable to proceed further. Many practical languages using Dijkstra conditions add a separate compilation step first that disambiguates cases and adds a do-nothing else case if none is specified...
More interesting is the use of a variation of Dijkstra conditions within a communications infrastructure, where the conditions state what messages may be received from where and where everything pauses until one of the arms may execute. That's a really powerful scheme, which can do some really tricky stuff. Here's a message-passing AND gate:
A +-----.
------+ | C
B | & +-----
------+ |
+-----'
synch
A?1 , B?1 --> C!1
[] A?_ , B?_ --> C!0
end-synch(chan?val is syntax for reading a value from a channel, and chan!val is for writing a value to a channel.)
APN Erlang uses this paradigm described by DKF. I found it useful enough to implement in my Fiber package.