# Constraint Processing (#70)

**URL:** <https://www.ruby-forum.com/t/constraint-processing-70/82555>\
**Category:** Ruby\
**Created:** [March 16, 2006, 3:07pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/82555 "2006-03-16T15:07:15Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 3:07pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/82555/1 "2006-03-16T15:07:15Z")

</div>

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…