Constraint processing is a form of declarative programming which, in the
words
of Dave B., “…allows you to find solutions to mathematical problems
by
stating the problem rather than the steps to the solution.” As
indicated in the
quiz, this can be used to solve all manner of problems without the
programmer
needing to find clever algorithms for each one.
Generally, satisfying constraints will involve some form of backtracking
search.
We can try some values and then back up to make different choices when
the
conditions of the problem begin failing. Jim W.'s mystical amb.rb
library
handles the back up with continuations, so let’s see if we can make some
sense
of that. Here’s Jim’s solution to the trivial quiz example:
require 'amb'
A = Amb.new
begin
a = A.choose(*(0..4))
b = A.choose(*(0..4))
c = A.choose(*(0..4))
A.assert a < b
A.assert a + b == c
puts "a=#{a}, b=#{b}, c=#{c}"
A.failure
rescue Amb::ExhaustedError
puts "No More Solutions"
end
Running that gives the expected results:
a=0, b=1, c=1
a=0, b=2, c=2
a=0, b=3, c=3
a=0, b=4, c=4
a=1, b=2, c=3
a=1, b=3, c=4
No More Solutions
Let’s change the program ever so slightly though, so we can watch it
work.
Here’s the same code, with a bunch of debugging statements added:
require 'amb'
A = Amb.new
begin
a = A.choose(*(0..4))
puts "a=#{a}" if $DEBUG
b = A.choose(*(0..4))
puts "b=#{b}" if $DEBUG
c = A.choose(*(0..4))
puts "c=#{c}" if $DEBUG
puts 'Asserting a < b...' if $DEBUG
A.assert a < b
puts 'Asserting a + b == c...' if $DEBUG
A.assert a + b == c
puts "a=#{a}, b=#{b}, c=#{c}"
puts 'Forcing failure to search for the next solution...' if $DEBUG
A.failure
rescue Amb::ExhaustedError
puts "No More Solutions"
end
Now, if we run that with Ruby’s -d switch, we learn a lot more:
a=0
b=0
c=0
Asserting a < b...
c=1
Asserting a < b...
c=2
Asserting a < b...
c=3
Asserting a < b...
c=4
Asserting a < b...
b=1
c=0
Asserting a < b...
Asserting a + b == c...
c=1
Asserting a < b...
Asserting a + b == c...
a=0, b=1, c=1
Forcing failure to search for the next solution...
c=2
...
Notice that initially a, b, and c all equal the first choice. When we
get to
the point of asserting that a < b, the program magically backs up and
begins
trying different choices for c. It runs through all of those choices,
but none
of them will satisfy a condition involving a and b. The program is then
forced
to back up again, but this time to try new choices for b. The first new
choice
finally satisfies a < b so c is set back to the first option of 0 and we
get to
move on. Asserting a + b == c triggers a final retry for c and then we
have an
actual solution that gets printed. At that point, a failure is
triggered
manually, so the search can continue for more solutions.
Seeing that work is almost mystical. The program leaps all over the
place
without a control structure in sight. How does it accomplish this?
Continuations. It’s time we look into amb.rb:
class Amb
class ExhaustedError < RuntimeError; end
def initialize
@fail = proc { fail ExhaustedError, "amb tree exhausted" }
end
def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
if choice.respond_to? :call
sk.call(choice.call)
else
sk.call(choice)
end
}
}
@fail.call
}
end
def failure
choose
end
def assert(cond)
failure unless cond
end
end
Not much to it is there? Only one tricky method to resolve, but let’s
tackle
the little stuff first. We can see that Amb creates a new error type to
represent the search being exhausted and initialize() sets @fail to a
Proc
object that will throw this error.
Now skip down to assert(). That just checks the condition for true or
false,
and calls failure() if needed. failure() itself is just as simple.
It’s just
another name for choose() with no arguments. Even choose() with no
arguments is
trivial. First it assigns prev_fail and steps into a continuation
block, but
neither of those are actually used in this case. There are no choices,
so most
of the method is just skipped. The only meaningful result of the call
is to
trigger the Proc object in @fail.
Now we are ready to tackle choose() with arguments, which is the source
of the
magic. Here’s the method one more time, with some comments added by me:
# ...
def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
if choice.respond_to? :call # a feature not used in this
example
sk.call(choice.call) # a feature not used in this
example
else # a feature not used in this
example
sk.call(choice)
end # a feature not used in this
example
} # end fk: fk.call(…) will pick up execution on the next
line
}
@fail.call
} # end sk: sk.call(arg) with return from the method the value of
arg
end
# ...
As the comments indicate, you can safely forget about four lines of this
method
right off the bat. These are part of a clever, but not used in this
example,
feature.
Now, the sk continuation is the easier one to understand. When it is
triggered,
it will cause the method to return its call() argument. There’s not
really a
lot of magic there, the continuation block is just the last statement in
the
method and we know that is always returned in Ruby. Furthermore,
Contuation.call() always sets the value of the block to an argument, if
provided. In other words, this is just used to exit from some nested
constructs
later in this method (similar to a labeled goto in some languages).
That leaves just one continuation between us and enlightenment. You can
see
that the fk continuation is used inside an each iterator for the
choices. Each
time a new choice is reached a continuation is generated.
The first thing that continuation block does is to change the value in
@fail.
When called, the new @fail will restore the previous value of @fail and
then
invoke the fk continuation. Remember, @fail is first set to an
ExhaustedError,
but because that keeps getting pushed down on this stack of Proc
objects, it
won’t trigger until we have run out of continuations to try.
After that, the current choice is simply returned, via the sk
continuation we
have already discussed. Now, when the fk continuation is eventually
triggered,
execution will pick up right after this return. In other words, we will
go to
the next iteration for that set of choices, @fail will be reset, and the
new
choice returned. When we finally run out of choices, we will hit the
@fail.call
line, causing the code to back up and try another path. That’s the
magic that
keeps the search going.
As always, all the solutions were educational and looking over them
could really
teach you some new tricks. My thanks to all who provided them and to
Jim for
taking us for a walk on the wild side with continuations.
Tomorrow’s quiz will require a little cooperation from your fellow
Rubyists to
complete…