From: Ruby Quiz <james@...>
Date: 2005-07-07T22:05:51+09:00
Subject: [SUMMARY] Inference Engine (#37)

	irb(main):005:0> are any programmers happy programmers?
	=> Yes, some programmers are happy programmers.
	irb(main):006:0> are all Ruby programmers happy programmers?
	=> Yes, all ruby programmers are happy programmers.
	irb(main):007:0> are any Python programmers happy programmers?
	=> I don't know.

True artificial intelligence doesn't seem that far off after all.

Did you know you could use irb as an interface like that?  I didn't!  Be sure
and glance at Pit Capitain's code to see just how that is done.

Daniel Sheppard sent in a nice object model, translating the rules into a class
hierarchy.  I recommend browsing through that too.

Here though, I want to look into Paulo Capriotti's code.  Paulo decided to model
the relationships as a directed graph, where vertices are the groups and edges
represent their relationships.  To save a little work, Paulo used the graph Ruby
library as a starting point.  Here's the beginning of the solution:

	require 'graph'

	def opposite_type(type)
	  type == :provable_true ? :provable_false : :provable_true
	end

	class Property
	  attr_reader :name, :type
	  def initialize(name, type)
	    @name = name
	    @type = type
	  end

	  def opposite
	    Property.new(@name, @type == :positive ? :negative : :positive)
	  end

	  def Property.create(x)
	    if x.respond_to?(:opposite)
	      x
	    else
	      Property.new(x, :positive)
	    end
	  end

	  def hash
	    "#{@name}##{@type}".hash
	  end

	  def eql?(other)
	    @name == other.name and @type == other.type
	  end

	  alias == eql?

	  def to_s
	    res = @name
	    if @type == :negative
	      "not-" + res
	    else
	      res
	    end
	  end
	end
	
	# ...

First we see the definition of a simple helper method to convert between two
opposites:  Things we can prove to be true and things we can prove are false.

Next, we have a helper class for a Property.  I wasn't sure what that meant at
first, so I had to dig a little.  Obviously, much of this class is just support
for hashing the object (hash() and eql?()).  We have a class method to create()
a Property when needed and an interesting method to give us an opposite()
Property.  The to_s() method is also interesting.  We can see from it that a
negated Property gets a leading "not-" when converted to a String.

All of this clicked into place for me when I turned on Paulo's debug mode and
watched the code work.  Here's an example:

	> All dogs are mammals
	adding edge dog, not-dog, provable_false
	adding edge not-dog, dog, provable_false
	adding edge dog, dog, provable_true
	adding edge not-dog, not-dog, provable_true
	adding edge mammal, not-mammal, provable_false
	adding edge not-mammal, mammal, provable_false
	adding edge mammal, mammal, provable_true
	adding edge not-mammal, not-mammal, provable_true
	...
	adding edge dog, mammal, provable_true
	adding edge not-mammal, not-dog, provable_true
	...
	adding edge not-mammal, dog, provable_false
	adding edge not-dog, mammal, provable_false
	...
	adding edge mammal, not-dog, provable_false
	adding edge dog, not-mammal, provable_false
	...

As you can see, a Property is a representation of the groups we are describing
to the inference engine.  Opposites represent everything not in that Property,
or group.  So the "dog" Property has an opposite of "not-dog", or non-dog, if
it's easier to think of that way.

What's the rest of that stuff about edges and what we can prove though?  That's
the graph being built, as I mentioned earlier.  Let's examine that code now:

	# ...
	
	class Knowledge < DirectedHashGraph
	  attr_reader :contradiction

	  def initialize
	    @contradiction = false
	    super
	  end

	  # Add a property and some tautologies.
	  # Here we assume that the property and
	  # its opposite are not void.
	  def add_property(x)
	    x = Property.create(x)
	    safe_add_edge(x, x.opposite, :provable_false)
	    safe_add_edge(x.opposite, x, :provable_false)
	    safe_add_edge(x, x, :provable_true)
	    safe_add_edge(x.opposite, x.opposite, :provable_true)
	    x
	  end

	  # Add en edge. Never throw.
	  def safe_add_edge(x, y, type)
	    catch(:add_edge_throw) do 
	      add_edge(x, y, type)
	    end
	  end

	  # Add an edge. Throw if the edge already exists.
	  def add_edge(x, y, type)
	    debug_msg "adding edge #{x}, #{y}, #{type}"
	    if self[x,y]
	      unless self[x,y] == type
	        @contradiction = true
	        debug_msg " \tcontradiction"
	        throw :add_edge_throw, :contradiction
	      else
	        debug_msg "\ti know"
	        throw :add_edge_throw, :i_know
	      end
	    else
	      super(x, y, type)
	    end
	  end

	  # Add an edge and its contrapositive.
	  def add_assertion(*args)
	    x, y, type = get_stmt(*args)
	    catch(:add_edge_throw) do
	      add_edge(x, y, type)
	      add_edge(y.opposite, x.opposite, type)
	      :normal
	    end
	  end

	  # Extract statement values.
	  def get_stmt(*args)
	    case args.size
	    when 1
	      x, y, type = args[0].x, args[0].y, args[0].type
	    when 3
	      x, y, type = args[0], args[1], args[2]
	    else
	      raise "Invalid argument list in #{caller.first}"
	    end  
	    return add_property(x), add_property(y), type
	  end

	  # Discover all possible deductions
	  # and add the corresponding edges to the graph.
	  def deduce
	    each_vertex do |v1|
	      each_vertex do |v2|
	        each_vertex do |v3|

	          if self[v1,v2] == :provable_true and
	             self[v2,v3] == :provable_true
	            add_assertion(v1, v3, :provable_true)
	          end

	          if self[v2,v1] == :provable_false and
	             self[v2,v3] == :provable_true
	            add_assertion(v3, v1, :provable_false)
	          end

	          if self[v1,v2] == :provable_true and
	             self[v3,v2] == :provable_false
	            add_assertion(v3, v1, :provable_false)
	          end

	          break if @contradiction
	        end
	      end
	    end
	  end

	  # Return true if a statement is provable.
	  # Return false if its negation is provable.
	  # Return nil if it is undecidable.
	  def test(*args)
	    x, y, type = get_stmt(*args)
	    case self[x,y]
	    when nil
	      return nil
	    when type
	      return true
	    else
	      return false
	    end
	  end
	end
	
	# ...

This class isn't as complicated as it appears, once you grasp the flow of how
it's used.  When an assertion is made to the engine, it will first call test()
to see if it already knows that information or if it contradicts any other
information.

Assuming the test passes, add_assertion() gets called.  That method starts by
calling get_stmt() to turn its arguments into two properties and a type
(:provable_true or :provable_false).  Note that the return sequence of
get_stmt(), uses add_property() to ensure that the graph already contains basic
relationships for that property (all dogs are dogs, for example).  These basic
relationships are added using safe_add_edge(), which is really just a shell over
add_edge() that filters out the symbols that are thrown by the latter.  Getting
back to add_assertion(), we can see that it too uses add_edge(), but it returns
the symbol thrown or its own :normal to indicate if we already knew about the
assertion or if it contradicts what we did know.  I know that's a lot to take
in, but if you just follow the chain of method calls it's pretty basic stuff.

Finally, deduce() is called after an assertion has been added.  By walking the
edges, deduce() will fill in any details the new assertion uncovers.  This is
done by checking relationships between three independent complete sets of
vertices, so relationships of the form one -> two -> three will be spotted.

You can see that this class is always monitoring for a @contradiction in each of
these methods.  However, I don't think this ever comes into play, since each
assertion is tested before it's added.  (Correct me if I'm wrong Paulo!)

On to the user interface:

	# ...
	
	["Assertion", "Question"].each do |c|
	  Struct.new(c, :x, :y, :type)
	end

	class UI

	  # Parse input and return a statement
	  def get_statement(line)
	    case line
	    # assertions
	    when /^all (.*)s are (.*)s\.?$/
	      return Struct::Assertion.new( Property.create($1),
	                                    Property.create($2),
	                                    :provable_true )
	    when /^no (.*)s are (.*)s\.?$/
	      return Struct::Assertion.new( Property.create($1),
	                                    Property.create($2).opposite,
	                                    :provable_true )
	    when /^some (.*)s are not (.*)s\.?$/
	      return Struct::Assertion.new( Property.create($1),
	                                    Property.create($2),
	                                    :provable_false )
	    when /^some (.*)s are (.*)s\.?$/
	      return Struct::Assertion.new( Property.create($1),
	                                    Property.create($2).opposite,
	                                    :provable_false )
	    # questions
	    when /^are all (.*)s (.*)s\?$/
	      return Struct::Question.new( Property.create($1),
	                                   Property.create($2),
	                                   :provable_true )
	    when /^are no (.*)s (.*)s\?$/
	      return Struct::Question.new( Property.create($1),
	                                   Property.create($2).opposite,
	                                   :provable_true )
	    when /^are any (.*)s not (.*)s\?$/
	      return Struct::Question.new( Property.create($1),
	                                   Property.create($2),
	                                   :provable_false )
	    when /^are any (.*)s (.*)s\?$/
	      return Struct::Question.new( Property.create($1),
	                                   Property.create($2).opposite,
	                                   :provable_false )
	    # description
	    when /^describe (.*)s\.?$/
	      return Property.create($1)
	    else 
	      return nil
	    end
	  end

	  # Return a description of the relation
	  # between x and y. 
	  # Assume that x is positive and that
	  # x -> y is not undecidable.
	  def describe_edge(x, y, aff = true)
	    case @k[x,y]
	    when :provable_true
	      case y.type
	      when :positive        
	        return "All #{x.name}s are #{y.name}s"
	      when :negative
	        return "No #{x.name}s are #{y.name}s"
	      end
	    when :provable_false
	      case y.type
	      when :positive
	        if aff
	          return "Some #{x.name}s are not #{y.name}s"
	        else
	          return "Not all #{x.name}s are #{y.name}s"
	        end
	      when :negative
	        if aff
	          return "Some #{x.name}s are #{y.name}s"
	        else
	          return "Not all #{x.name}s are not #{y.name}s"
	        end
	      end
	    end
	  end

	  # Return a list of sentences which describe
	  # the relations between x and each other node.
	  # Assume that x is positive.
	  def describe_node(x)
	    res = []
	    @k.each_vertex do |y|
	      if y.type == :positive and not x == y
	        if @k[x,y] == :provable_true
	          res << describe_edge(x,y)
	        elsif @k[x,y.opposite] == :provable_true
	          res << describe_edge(x,y.opposite)
	        elsif @k[x,y]
	          res << describe_edge(x,y)
	        elsif @k[x,y.opposite]
	          res << describe_edge(x,y.opposite)
	        end
	      end
	    end

	    res
	  end  

	  def say(value)
	    case value
	    when true
	      "Yes"
	    when false
	      "No"
	    else
	      "I don't know"
	    end
	  end

	  def initialize
	    @k = Knowledge.new
	  end

	  def wait_for_input
	    print '> '
	    gets
	  end

	  def run
	    while line = wait_for_input
	      line.chomp!
	      line.downcase!
	      stmt = get_statement(line)
	      if stmt.class == Struct::Assertion
	        case @k.test(stmt)
	        when true
	          puts "I know"
	        when false
	          puts "Sorry, that contradicts what I already know"
	        else
	          @k.add_assertion(stmt)
	          @k.deduce
	          puts "OK"
	        end
	      elsif stmt.class == Struct::Question
	        value = @k.test(stmt)
	        print say(value)
	        if value.nil?
	          print "\n"
	        else
	          puts ", #{describe_edge(stmt.x, stmt.y, value).downcase}"
	        end
	      elsif stmt.class == Property
	        describe_node(stmt).each do |sentence|
	          puts sentence
	        end
	      else
	        puts "I don't understand"
	      end
	    end
	  end
	end
	
	def debug_msg(msg)
	  puts msg if $debug
	end

	if $0 == __FILE__
	  ui = UI.new
	  ui.run
	end

Again, this looks like a lot of code, but it's not overly complicated, once you
find the flow.  Look at the last few lines to get a hint about where to begin. 
First, initialize() creates a Knowledge object to keep tract of our assertions
and answer our questions.  From that point on, run() handles the interactive
session.

The first thing you need to know is that run() uses a couple of helper methods: 
say() for output and wait_for_input() for input.  It also calls get_statement()
to parse input.  The return from get statement is either a single Property (the
"describe" command), a Struct::Assertion representing an assertion made, or a
Struct::Question representing a question asked.  You can see those Structs
defined just before the UI class starts.  They're just two properties and a
type.

The other thing to notice about get_statement() is that it does very basic
Regexp based parsing.  It uses a super clever trick of spotting a trailing "s"
to find the two groups in a line like, "Are all Ruby programmers happy
programmers?"  Of course, this does not work across all legal inputs:

	> All oxen are mammals.
	I don't understand
	> All James's pets are Dana's pets.
	OK
	> Are all James's pets Dana's pets?
	I don't know

To see another approach, examine Pit Capitain's parsing, especially the
IE.split() method.

Getting back to run() in Paulo's UI class, you'll see that the rest of the
method just handles the three different returns from get_statement(). 
Assertions are handled as I explained earlier.  Questions rely on
describe_edge() for answers and the "describe" command triggers a call to
describe_node().  That's the entire UI.

I promise to end this long summary very soon now, but I wanted to mention just
one more detail.  Paulo uses a helper method all through the code that's defined
near the end.  Here's another look at it:

	def debug_msg(msg)
	  puts msg if $debug
	end

The goal here is obvious, print a lot of extra information if I set this global
variable to true.  This is a trick that we all use sometimes in testing.  I just
wanted to suggest one minor change to enhance this trick:  Switch $debug to
$DEBUG.  Then you can trigger the messages with a command-line switch like so:

	$ ruby -e 'p $DEBUG'
	false
	$ ruby -d -e 'p $DEBUG'
	true

Slide that one into your bag of tricks, because it comes in handy.

My thanks to all three submitters for some really great code to poke around in
and play with.

Tomorrow, we have a simple but handy hack to explore.  It's an easy quiz so I
want to see all you beginners out there playing along!