amb in ruby

amb.rb

require 'continuation'
 
class Amb
  def initialize(all)
    @_all       = all
    @_backtrack = []
    @_values    = {}
    @_success   = default_success_message
    @_failure   = default_failure_message
    @_debug     = default_debug_message
  end
 
  def set(var, *choices)
    choices.each do |choice|
      instance_variable_set("@#{var}", choice)
      @_values[var] = choice
 
      callcc do |cc|
        @_backtrack.push(cc)
        return choice
      end
    end
 
    pass
  end
 
  def assert(&block)
    instance_eval(&@_debug)
 
    if instance_eval(&block)
      instance_eval(&@_success)
      pass if @_all
    else
      pass
    end
  end
 
  def pass
    if @_backtrack.empty?
      instance_eval(&@_failure)
      throw(:stop)
    else
      @_backtrack.pop.call
    end
  end
 
  def draw_message(message)
    message_length = message.length
 
    print("\n", 
          " ", "-" * message_length, "\n",
          "|", message, "|", "\n",
          " ", "-" * message_length, "\n",
          "\n")
  end
 
  def default_solve_all_failure_message
    ->(amb) { amb.draw_message("No more matching answers") }
  end
 
  def default_solve_failure_message
    ->(amb) { amb.draw_message("No matching answer") }
  end
 
  def default_success_message
    ->(amb) { amb.draw_message("Find a matching answer: #{values_message}") }
  end
 
  def values_message
    hash.map do |k, v|
      "@#{k} = #{v}"
    end.join(", ") 
  end
 
  def default_debug_message
    proc do 
      puts "> Checking #{values_message}"
    end
  end
 
  def default_failure_message
    @_all ? default_solve_all_failure_message : default_solve_failure_message
  end
 
  def success(&block)
    @_success = block
  end
 
  def fail(&block)
    @_failure = block
  end
 
  def debug(&block)
    @_debug = block
  end
 
  class << self
    def solve
      catch(:stop) do
        yield(self.new(false))
      end
    end
 
    def solve_all
      catch(:stop) do
        yield(self.new(true))
      end
    end
  end
  
  module Operator
    def backtrack
      @_backtrack ||= []
    end
 
    def pass
      if backtrack.empty?
        fail 'No matching answer'
      else
        backtrack.pop.call
      end
    end
 
    def amb *choices
      pass if choices.empty?
 
      choices.each do |choice|
        callcc do |cc|
          backtrack.push(cc)
          return choice
        end
      end
 
      pass
    end
  end
end
 
### Example 1
 
require 'amb'
 
Amb.solve_all do |amb|
  amb.set(:x, 1, 2, 3, 4)
  amb.set(:y, 1, 2, 3, 4)
 
  amb.assert do
    @x + @y == 5 && @x - @y == 1
  end
end
 
### Output
 
> Checking @x = 1, @y = 1
> Checking @x = 1, @y = 2
> Checking @x = 1, @y = 3
> Checking @x = 1, @y = 4
> Checking @x = 2, @y = 1
> Checking @x = 2, @y = 2
> Checking @x = 2, @y = 3
> Checking @x = 2, @y = 4
> Checking @x = 3, @y = 1
> Checking @x = 3, @y = 2
 
 -------------------------------------
|Find a matching answer: @x = 3, @y = 2|
 -------------------------------------
 
> Checking @x = 3, @y = 3
> Checking @x = 3, @y = 4
> Checking @x = 4, @y = 1
> Checking @x = 4, @y = 2
> Checking @x = 4, @y = 3
> Checking @x = 4, @y = 4
 
 -----------------------
|No more matching answers|
 -----------------------
 
### Example 2
 
require 'amb'
 
include Amb::Operator
 
x = amb 1, 2, 3
y = amb 2, 4, 5
 
amb unless x * y == 10
 
puts "Find a macting answer: x = #{x}, y = #{y}"
 
### Output
 
Find a macting answer: x = 2, y = 5