Article about McCarthy's Ambiguous Operator in Ruby

I just discovered an article about an implementation of McCarthy's amb operator in Ruby, written by Erid Kidd. What a gem, it's a beautiful construction.

It uses continuations to implement backtracking and provides a straight-forward way of representing constraint satisfaction problems in Ruby.

Find the details, implementation and article here: www.randomhacks.net.
It's also the subject of a Ruby Quiz. Here is an other implementation in scheme with a detailed description.

A short introduction to CHR

Constraint Handling Rules (CHR) is a declarative language for solving constraint problems. It's mainly used in conjunction with Prolog, but implementations for Java and Haskell are also available. I am currently working on making a Ruby implementation (as a Ruby DSL of course).

What is interesting about CHR is that it can be used to express constraint problems in a concise manner. It has successfully been applied to a wide range of constraint problems such as planning and language processing.

The language is quite simple. It consists of three kinds of rules that modify a constraint store (a database of constraints). All the rule definitions have a similar syntax:
rule :- head, operator, body.
The head and the body is basically a list of constraints. A rule is used when the head of the rule is matched by existing constraints in the constraint store. The constraints specified in the body gets added to the constraint store.

Propagation rules

c1, ..., c ==> Guard | cn+1, ... , cm
Propagation rules create new rules in the constraint store. Thee rules in the body (cn+1 .. cm) are added to the constraint store given that the guard is true. The rules from the head (c1 ... cn) remains in the constraint store.

Simplification rules

c1, ..., cn <=> Guard | cn+1, ... , cm
Simplification rules, has purpose of simplifying constraints in a particular way.
Rules in head (c1 .. cn) are removed from constraint store and rules in the body (cn+1 ... cm) is added to the store, provided that the Guard is true.

Simpagation rules

c1, ..., ci \ ci+1, ..., cn <=> Guard | cn+1, ..., cm
Simpagation rules is a sort of combination of the two others. The head is separated by a backslash. The rules before the backslash (c1 .. ci) stays in constraint store, while the rules after (ci+1 .. cn) is removed. The rules in the body (cn+1 .. cm) is added, provided the guard is true.

Generate and Test in Ruby

The Generate and Test algorithm (GT) is without comparison the simplest and most inefficient way of solving constraints. Actually, it's not useful for anything but very, very small problems. But it is serves as a nice little illustrating of the concept of constraint solving. Just for fun I wrote a very small GT constraint solver in Ruby the other day, that I decided sharing.

Here is a small toy problem for it to solve and a demonstration of how it works:

gt = GT.new
 
gt.add_var("a", 0..4)
gt.add_var("b", 0..4)
gt.add_var("c", 0..4)
 
gt.add_constraint("a % 3 == 0")
gt.add_constraint("b + a < c")
gt.add_constraint("c-a > b")
gt.solve

Running this code will print:

Solutions:
{"a"=>0, "b"=>0, "c"=>1}
{"a"=>0, "b"=>0, "c"=>2}
{"a"=>0, "b"=>0, "c"=>3}
{"a"=>0, "b"=>0, "c"=>4}
{"a"=>0, "b"=>1, "c"=>2}
{"a"=>0, "b"=>1, "c"=>3}
{"a"=>0, "b"=>1, "c"=>4}
{"a"=>0, "b"=>2, "c"=>3}
{"a"=>0, "b"=>2, "c"=>4}
{"a"=>0, "b"=>3, "c"=>4}
{"a"=>3, "b"=>0, "c"=>4}


The implementation:

class GT
  def initialize
    @variables = Hash.new
    @constraints = Array.new
  end
  
  def add_var(varname, domain)
      @variables[varname] = domain
  end
  
  def add_constraint(constraint)
    constraint.freeze
    @constraints << constraint
  end
  
  def generate
    gen(@variables, Hash.new,nil)
  end
  
  def gen(variables, partial_assignment, solutions)
    solutions = Array.new if solutions.nil?

    if variables.empty?
      if test(partial_assignment)
        solutions << partial_assignment.clone
      end
      return nil # termination
    end

    # pick the first available variable:
    vars = variables.clone
    var_name = variables.keys.first
    domain = vars[var_name] 
    vars.delete(var_name)
    
    # Loop over each variable in domain
    domain.each do |value|
      partial_assignment[var_name] = value
      gen(vars, partial_assignment, solutions)
    end
    solutions
  end
    
  def test(assignment)
    @constraints.each do |constraint|
      c = String.new(constraint)
      assignment.each do |key,val|
        c.gsub!(key,val.to_s)
      end
      result = instance_eval(c)
      return false if result == false
    end
  end
  
  def solve
    puts "Solutions:"
    solutions = generate
    solutions.each do |s|
      pp s
    end

  end
end

It is not useful for solving anything interesting though. I tried to make it solve the the send more money puzzle. But this poor algorithm searches it self to death in vain. It took so long, that it was never allowed to terminate...

[ "s", "e", "n", "d", "m", "o", "r", "n", "y" ].each { |var| gt.add_var(var, 0..9) }

gt.add_constraint("m != 0")
gt.add_constraint("s != 0")
gt.add_constraint("m < 3")
gt.add_constraint("(1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e) == (10000*m + 1000*o + 100*n + 10*e + y)")  

gt.solve

Update:Also heck out amb